· 7 years ago · Nov 13, 2018, 07:54 PM
1#!/usr/bin/env python
2#
3# Robot Odyssey chip disassembler.
4#
5# This program can disassemble chip designs saved by Robot Odyssey and
6# the stock chips which come with the game. The chips are stored in a
7# bytecode format that resembles an electrical netlist. Our output is
8# a textual representation of this bytecode.
9#
10# Understanding the output
11# ------------------------
12#
13# The resulting listing is similar to an electrical netlist. It lists
14# each component's type, inputs, and outputs. The listing could also
15# be viewed as a kind of assembly language. It is a series of
16# instructions, in the same order they are executed during actual chip
17# simulation in-game.
18#
19# The game parses through the chip's bytecode once per 'clock cycle'.
20# Each instruction reads its inputs, flip-flops update their internal
21# state, then one or two output values are produced. The order outputs
22# are applied in depends on the instruction:
23#
24# - All Node outputs propagate immediately.
25#
26# - Outputs which go to pins on the *current* chip are propagated
27# immediately.
28#
29# - All other outputs are put on a queue for later propagation.
30# They are propagated just prior to the Nodes at the end of
31# the chip.
32#
33# There may be slight differences between the way circuits are
34# simulated in chips and in the rest of the game. Flip-flops in chips
35# will not toggle if the inputs are both high. There is also an extra
36# clock of propagation delay for signals that cross a nested chip
37# boundary, since all I/O to a nested chip goes through its pin
38# values. Even though the interpreter allows this, chips are never
39# compiled such that an outer chip reads or writes a nested chip's
40# gates directly.
41#
42# Nets are assigned a unique name based on the part that they appeared
43# as an input to. Values inside <> represent the current state of an
44# object. All pins are labeled as <0> (off) or <1> on. Flip-flops can
45# be in the <01> or <10> state.
46#
47# Flip-flops have two inputs and two outputs, corresponding to their
48# two halves. They also have two internal 'pins' which keep track of
49# their current state. These pins don't show up as inputs or outputs.
50#
51# License
52# -------
53#
54# Copyright (c) 2009 Micah Dowty <micah@navi.cx>
55#
56# Permission is hereby granted, free of charge, to any person
57# obtaining a copy of this software and associated documentation
58# files (the "Software"), to deal in the Software without
59# restriction, including without limitation the rights to use,
60# copy, modify, merge, publish, distribute, sublicense, and/or sell
61# copies of the Software, and to permit persons to whom the
62# Software is furnished to do so, subject to the following
63# conditions:
64#
65# The above copyright notice and this permission notice shall be
66# included in all copies or substantial portions of the Software.
67#
68# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
69# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
70# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
71# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
72# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
73# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
74# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
75# OTHER DEALINGS IN THE SOFTWARE.
76#
77
78import struct
79import sys
80
81
82class FormatError(Exception):
83 pass
84
85class Pin:
86 """One electrical pin on a chip or gate. Pins always have a current
87 state, either 0 or 1. Pins can have a name, so we can uniquely
88 identify them in the disassembly.
89 """
90 def __init__(self, state, name=None):
91 if isinstance(state, str):
92 state = ord(state)
93
94 if state > 1:
95 raise FormatError("Pin state must be 0 or 1")
96
97 self.state = state
98 self.name = name
99
100 def __repr__(self):
101 return "%s<%d>" % (self.name, self.state)
102
103 def __str__(self):
104 return self.name
105
106
107def _formatLine(operation, args, outputs=None):
108 s = '%-10s %s' % (operation, ' '.join(map(repr, args)))
109 if outputs:
110 s += ' => %s' % ' '.join(map(repr, outputs))
111 return s
112
113
114class Gate:
115 """One logic gate. A gate has a name, a list of input pins,
116 and a list of output pins. This is an abstract base class,
117 each type of gate has a subclass of Gate.
118 """
119 def __init__(self, inputs, outputs, name=None, state=()):
120 if name is None:
121 self.__class__._index += 1
122 name = "%s%d" % (self.__class__.__name__, self.__class__._index)
123
124 self.inputs = inputs
125 self.outputs = outputs
126 self.name = name
127 self.state = state
128
129 self._assignNames(self.inputs, 'in')
130 self._assignNames(self.state, 'state')
131
132 def _assignNames(self, pins, prefix):
133 # Assign names to any unnamed pins
134 for i, pin in enumerate(pins):
135 if pin.name is None:
136 pin.name = '%s_%s%d' % (self.name, prefix, i)
137
138 def __repr__(self):
139 return _formatLine(self.__class__.__name__,
140 self.inputs, self.outputs)
141
142
143class AND(Gate):
144 _index = 0
145 def __init__(self, a, b, outputs, name=None):
146 Gate.__init__(self, (a, b), (outputs,), name)
147
148class OR(Gate):
149 _index = 0
150 def __init__(self, a, b, outputs, name=None):
151 Gate.__init__(self, (a, b), (outputs,), name)
152
153class XOR(Gate):
154 _index = 0
155 def __init__(self, a, b, outputs, name=None):
156 Gate.__init__(self, (a, b), (outputs,), name)
157
158class NOT(Gate):
159 _index = 0
160 def __init__(self, input, outputs, name=None):
161 Gate.__init__(self, (input,), (outputs,), name)
162
163class Node(Gate):
164 _index = 0
165 def __init__(self, input, outputs, name=None):
166 Gate.__init__(self, (input,), (outputs,), name)
167
168class FF(Gate):
169 _index = 0
170 def __init__(self, in0, in1, state0, state1, out0, out1, name=None):
171 Gate.__init__(self, (in0, in1,), (out0, out1), name, (state0, state1))
172
173 def __repr__(self):
174 name = '%s<%d%d>' % (self.__class__.__name__,
175 self.state[0].state, self.state[1].state)
176 return _formatLine(name, self.inputs, self.outputs)
177
178
179class AddressSpace:
180 """An address space for pins. Maintains a mapping from offset to
181 Pin object. Address spaces may be carved up into nested address
182 spaces, in order to support nested chips.
183 """
184 def __init__(self):
185 self._offset = 0
186 self._map = {}
187
188 def offset(self, x):
189 """Create a linked address space which is offset by 'x'."""
190 space = self.__class__()
191 space._offset = self._offset + x
192 space._map = self._map
193 return space
194
195 def lookupPin(self, data, offset, name=None):
196 """Return a Pin object for the specified offset in the chip data.
197 If it exists, return it. Otherwise, create the pin.
198 If the pin is not yet named, optionally name it.
199 """
200 myOffset = self._offset + offset
201
202 if len(data) <= offset:
203 raise FormatError("End of chip data or invalid pin address 0x%04x" % offset)
204
205 if myOffset in self._map:
206 pin = self._map[myOffset]
207 if pin.name is None:
208 pin.name = name
209 else:
210 pin = Pin(data[offset], name)
211 self._map[myOffset] = pin
212
213 return pin
214
215
216class Chip:
217 """A Robot Odyssey chip. 'data' is the chip's electrical data,
218 in the same format used in CSV files, CHP files, and in memory.
219 CSV files also contain pin directions, bytecode length, and
220 help text.
221
222 If 'data' is at least 1KB, we'll assume it's in CSV
223 format. Otherwise we assume it's in CHP format.
224
225 Chips can optionally have a name, so they can be identified in
226 the disassembly.
227 """
228
229 name = None
230 chipData = None
231 bcOffset = None
232 helpText = None
233 pinDirections = None
234 pins = None
235 parts = None
236 addrMap = None
237
238 _pinDirEnum = (None, 'in', 'out')
239 _index = 0
240
241 def __init__(self, data, name=None, format=None, addrSpace=None):
242 if format is None:
243 if len(data) >= 1024:
244 format = 'CSV'
245 else:
246 format = 'CHP'
247
248 if name is None:
249 self.__class__._index += 1
250 name = "%s%d" % (self.__class__.__name__, self.__class__._index)
251
252 self.name = name
253 self.addrSpace = addrSpace or AddressSpace()
254 getattr(self, '_parse%s' % format)(data)
255
256 def _parsePinObjects(self, data):
257 # Parse a chip's group of electrical Pins.
258 # Populates self.pins, and adds the pins to addrMap.
259
260 # WARNING: The pins aren't actually in the normal order.
261 # Pins are labeled like they are in electronics:
262 # counterclockwise from the top-left. But in the
263 # file, they're stored 1-4 then 8-5 (two top-down
264 # rows). We keep the pins in this order in our
265 # 'pins' and 'pinDirections' lists, but we rename
266 # them according to electronics conventions.
267
268 self.pins = []
269 for addr, byte in enumerate(data[:8]):
270 if addr < 4:
271 pinNum = addr + 1
272 else:
273 pinNum = 4 + 8 - addr
274
275 self.pins.append(self.addrSpace.lookupPin(
276 data, addr, '%s_pin%d' % (self.name, pinNum)))
277
278 def _parseCSV(self, data):
279 # CSV format. Normal electrical data occupies the first
280 # kilobyte of the file. The rest is:
281 #
282 # - A table of pin directions
283 #
284 # - The length of the CHP data. The rest of the first
285 # kilobyte appears to be unused, though it isn't always
286 # zeroed.
287 #
288 # - The help screen
289
290 if len(data) != 1333:
291 raise FormatError("Length of CSV file must always be 1333 bytes")
292
293 self._parsePIN(data[0x400:0x408])
294 self._parseHelpText(data[0x40A:])
295
296 chpSize = struct.unpack("<H", data[0x408:0x40A])[0]
297 self._parseCHP(data[:chpSize])
298
299 # XXX: I'd like to be able to verify that len(self.chipData)
300 # equals chpSize here, but that isn't always the case.
301 # The original WALLHUG.CSV, for example, claims the
302 # bytecode is one byte longer than it really is.
303
304 def _parsePIN(self, data):
305 # Parse the pin direction table included in CSV files
306 # or as a stand-alone PIN file.
307
308 if len(data) != 8:
309 raise FormatError("Pin direction table must be 8 bytes long")
310 self.pinDirections = []
311
312 for byte in data:
313 byte = ord(byte)
314 if byte > 2:
315 raise FormatError("Invalid byte 0x%02 in pin direction table" % byte)
316 self.pinDirections.append(self._pinDirEnum[byte])
317
318 def _parseHelpText(self, data):
319 # Parse the table of help text. This is an array of 9
320 # zero-terminated strings, all padded with spaces. The first
321 # line (title) is 18 characters. The others are 34 chars.
322
323 lines = data.split('\x00')
324
325 if len(lines) != 10:
326 raise FormatError("Incorrect number of lines in help text")
327 if lines[-1] != '':
328 raise FormatError("Help text missing final NUL byte")
329
330 if len(lines[0]) != 18:
331 raise FormatError("Help text title line has incorrect length")
332 self.helpText = [lines[0].rstrip()]
333
334 for line in lines[1:-1]:
335 if len(line) != 34:
336 raise FormatError("Help text line has incorrect length")
337 self.helpText.append(line.rstrip())
338
339 def _parseCHP(self, data):
340 # Chip electrical data. The first 8 bytes are the pin states,
341 # the rest is bytecode. Offsets are relative to the beginning
342 # of the chip data, so store the whole thing.
343 #
344 # In a nested chip, we don't know how long the chip data is
345 # until parsing the bytecode. So 'data' may be longer than the
346 # actual bytecode data for this chip. We'll truncate chipData
347 # to the length of this chip, so callers can check
348 # len(chipData) to see how long this chip actually was.
349
350 # Start a map which tracks pins by address
351 self.addrMap = {}
352
353 # Create pins. Bytecode starts immediately afterward.
354 self._parsePinObjects(data[:8])
355 bcOffset = 8
356
357 # Bytecode parsing loop. Each bytecode has a handler function
358 # that returns the next offset to parse from. After bytecode
359 # 0x07 has finished, this chip is done.
360
361 self.parts = []
362 while True:
363 byte = ord(data[bcOffset])
364 fn = getattr(self, '_bytecode_%02x' % byte, None)
365 if not fn:
366 raise FormatError("Unknown bytecode 0x%02x" % byte)
367 bcOffset = fn(data, bcOffset + 1)
368 if byte == 0x07:
369 break
370
371 # Now we know the end of the bytecode. Store chipData.
372 self.chipData = data[:bcOffset]
373
374 def _bytecodePin(self, data, offset):
375 # Parse a pin from the bytecode.
376 # Returns an offset, pin tuple.
377
378 pin = self.addrSpace.lookupPin(data, offset)
379 return offset + 1, pin
380
381 def _bytecodeAddrList(self, data, offset):
382 # Parse a list of pin addresses, terminated by an 0xFF byte.
383 # Returns an offset, pinList tuple.
384
385 pinList = []
386 while True:
387 if len(data) <= offset:
388 raise FormatError("Premature end of chip data")
389
390 if data[offset] == '\xFF':
391 return offset + 1, pinList
392
393 addr = struct.unpack('>H', data[offset:offset+2])[0]
394 pinList.append(self.addrSpace.lookupPin(data, addr))
395 offset += 2
396
397 def _bytecode_01(self, data, offset):
398 # AND gate
399 offset, in0 = self._bytecodePin(data, offset)
400 offset, in1 = self._bytecodePin(data, offset)
401 offset, outs = self._bytecodeAddrList(data, offset)
402 self.parts.append(AND(in0, in1, outs))
403 return offset
404
405 def _bytecode_02(self, data, offset):
406 # OR gate
407 offset, in0 = self._bytecodePin(data, offset)
408 offset, in1 = self._bytecodePin(data, offset)
409 offset, outs = self._bytecodeAddrList(data, offset)
410 self.parts.append(OR(in0, in1, outs))
411 return offset
412
413 def _bytecode_03(self, data, offset):
414 # XOR gate
415 offset, in0 = self._bytecodePin(data, offset)
416 offset, in1 = self._bytecodePin(data, offset)
417 offset, outs = self._bytecodeAddrList(data, offset)
418 self.parts.append(XOR(in0, in1, outs))
419 return offset
420
421 def _bytecode_04(self, data, offset):
422 # NOT gate
423 offset, input = self._bytecodePin(data, offset)
424 offset, outs = self._bytecodeAddrList(data, offset)
425 self.parts.append(NOT(input, outs))
426 return offset
427
428 def _bytecode_05(self, data, offset):
429 # Flip flop
430 offset, in0 = self._bytecodePin(data, offset)
431 offset, in1 = self._bytecodePin(data, offset)
432 offset, state0 = self._bytecodePin(data, offset)
433 offset, state1 = self._bytecodePin(data, offset)
434 offset, out0 = self._bytecodeAddrList(data, offset)
435 offset, out1 = self._bytecodeAddrList(data, offset)
436 self.parts.append(FF(in0, in1, state0, state1, out0, out1))
437 return offset
438
439 def _bytecode_06(self, data, offset):
440 # Nested chip.
441 chip = Chip(data[offset:], format='CHP', addrSpace=self.addrSpace.offset(offset))
442 self.parts.append(chip)
443 return offset + len(chip.chipData)
444
445 def _bytecode_07(self, data, offset):
446 # Propagate inputs, end chip.
447 #
448 # The arguments are a list of lists. Each inner list is a
449 # value to propagate. The first address is the source pin, the
450 # rest are destination pins.
451
452 while True:
453 offset, addrs = self._bytecodeAddrList(data, offset)
454 if not addrs:
455 break
456 self.parts.append(Node(addrs[0], addrs[1:]))
457 return offset
458
459 def __repr__(self):
460 lines = []
461 indent = ' '
462
463 lines.append('%s {' % (self.name or 'CHIP'))
464
465 if self.helpText:
466 for line in self.helpText:
467 lines.append(indent + _formatLine('HELP', [line]))
468 lines.append('')
469
470 for i, pin in enumerate(self.pins):
471 tokens = [pin]
472 if self.pinDirections:
473 dir = self.pinDirections[i]
474 if not dir:
475 continue
476 tokens.append(dir)
477 lines.append(indent + _formatLine('PIN', tokens))
478 lines.append('')
479
480 for part in self.parts:
481 for line in repr(part).split('\n'):
482 lines.append(indent + line)
483
484 lines.append('}')
485 return '\n'.join(lines)
486
487wires=[]
488regs=[]
489pinwires=[]
490def addwire(w):
491 global wires
492 wires.append(w)
493def addreg(r):
494 global regs
495 regs.append(r)
496
497def getinputs(p):
498 s=[]
499 for i in p.inputs:
500 s.append(i.name.lower())
501 addreg(i.name.lower())
502 return s
503def getoutputs(p):
504 s=()
505 if p.__class__.__name__=="FF":
506 s=(str(p.name).lower()+"_out0", str(p.name).lower()+"_out1")
507 for i in s: addwire(i.lower())
508 elif p.__class__.__name__.lower() in ("and", "or", "not", "xor"):
509 s= (str(p.name.lower())+"_out",)
510 for i in s: addwire(i.lower())
511 return s
512def connectWires(c):
513 s=""
514 name=c.name.lower()
515 op=c.__class__.__name__.lower()
516 if op in ("or", "and", "not", "xor"):
517 for i in c.outputs[0]:
518 s+="\t\t%s <= %s_out;" %(i.name.lower(), c.name.lower())
519 s+="\n"
520 elif op=="node":
521 for i in c.outputs[0]:
522 s+="\t\t%s <= %s;\n" % (i.name.lower(), str(c.inputs[0]).lower())
523
524 elif op == "ff":
525 for a in (0,1):
526 for b in c.outputs[a]:
527 s+="\t\t%s <= %s_out%s;\n" % (str(b).lower(), c.name.lower(), a)
528 if "chip" in s.split("=")[0]:
529 pinwires.append(s[:-1])
530 return ""
531 return s[:-1]
532def gateDefs(c):
533 s=""
534 if c.__class__.__name__=="HELP":
535 print dir(c)
536 if c.__class__.__name__.lower() in ("and", "or", "not", "xor", "ff"):
537 s+=c.__class__.__name__.lower()
538 s+="("+", ".join(getoutputs(c))+", "+", ".join(getinputs(c))+");"
539 return s
540if __name__ == '__main__':
541 if len(sys.argv) != 2:
542 sys.stderr.write("usage: %s <CHP or CSV file>\n" % sys.argv[0])
543 else:
544 c=Chip(open(sys.argv[1], 'rb').read())
545 s=[]
546 for i in c.parts:
547 s.append(gateDefs(i))
548 print ""
549 print "module %s(%s, ticks);" % (c.name.lower(), ", ".join(str(x).lower() for x in c.pins))
550 print "\t"+"\n\t".join("// "+x for x in c.helpText)
551 print "\t"+"input wire ticks, %s;" % ", ".join(x[0] for x in zip([str(y).lower() for y in c.pins], c.pinDirections) if x[1]=="in")
552 print "\t"+"output reg %s;" % ", ".join(x[0] for x in zip([str(y).lower() for y in c.pins], c.pinDirections) if x[1]=="out")
553 print "\t"+"reg %s;" % ", ".join((x) for x in regs)
554 print "\t"+"wire %s;" % ", ".join((x) for x in wires)
555 print "\n"
556 print "\t"+"\n\t".join(x for x in s if len(x)>0)
557 print "\n"
558 print "\talways @(posedge ticks) begin"
559 print "\n".join(y for y in [connectWires(x) for x in c.parts] if y !="")
560 print "\tend"
561 print "\talways begin"
562 print "\n".join(pinwires)
563 print "\tend"
564 print "endmodule"