An LC-3 Disassembler in Haskell
LC-3 assembly is an educational programming language. It is simple enough that complex programs can be written directly in it without needing a compiler, and thus it is often used in teaching assembly. An LC-3 textual assembly program is compiled to a binary object file by an assembler, and then executed by a virtual machine . Writing a virtual machine for LC-3 is a fun little exercise. However, in this post, we implement a disassembler for compiled LC-3 binaries back to textual assembly programs. This post was originally published on abhinavsarkar.net . LC-3 has a simple instruction set with only 18 instructions. It works with eight 16-bit registers (numbered from 0 to 7), and 16-bit addressable memory. LC-3 instructions are also 16-bit, with first four bits used for opcodes, and the rest for instruction arguments. There are instructions for doing arithmetic and bitwise logical operations, conditional branching, executing subroutines, loading from and storing to memory, handling interrupts and doing system calls. Some of them take source, destination, and base registers as arguments ( , , and respectively in the diagram above). Some other take integer immediate values, program counter, and address offsets ( , , and respectively in the diagram above). The instruction take a code for the syscall to execute. Notice that we count the bits from right to left, zero-indexed. When written in the textual assembly format, we use mnemonics for the opcodes and syscalls. The eight registers are written as to . The instructions can be labeled and referred from other instructions using them. Let’s start by looking at a simple LC-3 assembly file: As seen above, the assembly file can also contain assembler directives such as , , , , and . Quoting the docs: We assemble the program with the assembler, and then execute the resultant binary with the VM 1 : It works as expected! As much fun as it would be to write an assembler and a VM, in this post, we don’t assemble or run LC-3 programs, we disassemble them. We don’t care what the instructions do, only how they are encoded. Unlike an object file generated from X86 or Arm assembly, an LC-3 object file does not contain section tables separating code from data, symbol tables indicating function and variable names, relocation information, or debug symbols 2 . It contains only raw binary instructions and data that are freely intermixed in a single address space. This is made necessary by the fact that LC-3 has only 16-bit addressable memory. So data blocks and read-write memory addressed from code has to be within \(2^{16}\) bits or 8192 bytes of the code addressing it. Consider these bytes: A disassembler looking only at binary code has no context. A 16-bit word that decodes perfectly as a legal instruction may actually be a character, a part of a packed string, a number/byte literal, or a memory address. We need context to decode correctly, so the disassembler works in multiple passes: Let’s go over the disassembler part-by-part. First, the imports: We use the vector library for instruction lists, and the monad for manipulating them mutably. We also use bytestring for doing binary IO. Here are the data types we use: The type enumerates the eight LC-3 registers. The type represents the condition codes used for conditional jumping, which are negative, zero and positive. The type enumerates the eight standard LC-3 trap codes used for doing IO and halting the programs: The type is the heart of the disassembler. It doesn’t represent only the real LC-3 instructions, but also adds more constructors that are useful for disassembling: This representation lets us handle ambiguous data. Also note that we capture the raw bytes in some instructions like and . Finally, represents entire 16-bit binary code, and is the type for representing an LC-3 object file with an origin address and the binary code. Since we work a lot with bits here, we define some patterns to make it easier and less error-prone: Each LC-3 instruction has a 4-bit opcode, and many have 3-bit register or flag fields. So, we define two new types: (3-bit) and (4-bit), with pattern synonyms for exhaustive pattern matching. By defining patterns through , we map directly to the ISA specification. For example, visually shows the bit pattern for the opcode. GHC’s pragma enforces exhaustiveness, so no fallback cases are needed. The smart constructor functions and take the least significant 3 or 4 bits of the passed 16-bit parameter respectively, and return respective typed bits. First, we decode the registers and trap routines: We see the bit patterns in action here. The trap routines codes are as defined in the ISA. Next, the function extracts the opcode nibble (the most significant four bits), and decodes the arguments by calling , which dispatches on the opcodes: Now, we go over decoding of each instruction one-by-one. has two variations: one that takes two source registers, and another that takes one source register and one immediate value. First, we extract and decode the destination and first source register. Then depending on the sixth bit, we either decode the second source register or the value. The value is sign extended by calling the helper function . When decoding the second register, if we find that the forth and fifth bits are not , that means this is not a valid instruction. In that case, we return the raw bytes wrapped in the constructor, because the malformed instructions are far more likely to be data that happens to have an opcode prefix. Capturing them as lets us treat them as data in the later steps. This same pattern is used in decoding other instructions as well: extract and decode registers, flags, and values, and check fixed bits for validity. If valid, return the decoded instruction, or else the raw bytes. The instruction has exactly same format as the instruction, except for the different opcode. To decode the instruction, we decode the registers and check for the fixed bits. Decoding the instruction requires us to decode the condition flags, which is a straightforward mapping from their bit patterns. In case no flags are set, the instruction is likely to be an ASCII character instead with the high byte set to , so we add a special check for that. Note that we capture the raw byte in the output instruction, to be used later. The and instructions have same opcode, but differ in the bits 7–9, which are set to for . Note that the function also checks for the fixed bits, failing which it returns a instruction. The and instructions have the same opcode, differing in the 12th bit. Decoding the , and instructions is a straightforward matter of decoding their registers and offsets. Notice that the and instructions also capture the raw bytes. Decoding the , and instructions is similar to the , and instructions. Again, straightforward decoding of register and offset: The instruction is a constant byte pattern. Decoding the instruction requires us to decode the trap routines. We don’t care about the rest of the bytes if the opcode is for the instruction. That’s it for decoding the bytes to instructions. But that was the easy part. Up next, we get into the heuristic operations. , the function below, is our main entry point to disassembling the binary code. It runs in the monad so that we can work with a mutable vector of instructions. First we allocate the mutable vector, and then we do a basic disassembly of the binary code into it by calling . After that, we go over the disassembled instructions in , and use heuristics to guess better ones. Finally, we clean up by combining the character data and inserting the labels, and return the final immutable vector of instructions. is where our first heuristic is applied. We go over the binary code vector element-by-element, decoding each raw word using the function we wrote earlier. But we don’t stop there, we do an additional check. If a freshly decoded instruction is one of some instructions, preceded by some particular instructions, we use it to further disassemble some data. We recognize these three patterns: These patterns are very common and almost standard, so we can confidently use them for detecting character and string data. Also, note the checks in the beginning of that prevent already disassembled char/string data from being overwritten. At this point, we have decoded the instructions and char/string data. But there are more possibilities of improving the disassembly quality. In this pass, we revisit the decoded instructions and correct them based on their targets and neighbours: runs till a fixed-point is reached, that is to say, till the instructions stop changing. It does a backward sweep with the function, then a forward sweep, then repeats until no changes occur. We do this because a rewrite can create conditions for another rewrite. Doing this till fixed-point is safe because of the way is written: it only changes code-like instructions to data-like instructions, and never the other way. That makes the whole pass monotonic, causing it to eventually terminate. We do the sweep in both directions to make the changes order-independent. Next up is : The idea behind is that, certain instructions that point to other instructions are likely to be data. Different instructions have different confidence levels for their target addresses, encoded as : below carries out the actual rewrites: The two helper predicates distinguish definite data and speculative data: checks for , , , and the original side of . checks for the speculative data alternative. Note how speculative data can cause neighbouring instructions to become data, but cannot alone cause a branch/call instruction to change, thus limiting speculation from spreading. After the previous pass the instructions become stable. We now process them to do some cleanups. First, we merge consecutive characters into strings: uses to walk the instruction list and combine: If a run is not -terminated, we revert the characters in it to . Finally, we insert the labels before the instructions that other instructions point to: We also change the pointing instructions to use the labels instead of offsets. This concludes the entire disassembly of LC-3 binary code. To finish off, we need functions to print the instructions and to read the binary files. is our top-level function that takes an object file and returns the disassembly as text: simply pretty prints each disassembled instruction and wraps the result with and directives from LC-3 assembler format. Here is the pretty printer: The instructions are rendered in the LC-3 assembly syntax. words become directives. values become with proper escape sequences. instructions are rendered with both interpretations: the speculated data form followed by the original instruction as a comment. This preserves ambiguity for human review. The helper pretty-printers: The registers are printed as – . Numeric values are prefixed with , and the escape sequences ( , , etc.) are properly encoded in strings. The trap routines are looked up by their standard codes and output as their names. After all we’ve been through, this is a piece of cake: Only important thing to note is to combine the byte pairs in the big-endian order. The function reads a binary file from STDIN, parses it, and disassembles it to STDOUT: Error messages are printed and the program exits with status 1 on failure. And, we are done! Let’s test it on the “Hello World!” program : Amazing! We assembled the disassembled program and ran it, and it produced the same output. The assembly is also pretty much the same. To make sure the disassembler works correctly, let’s run it on a the binary code for a larger program: lc3-fizzbuzz.asm that output the solution for the Fizzbuzz problem. It works perfectly. You can also see the word-wise diff between original and disassembled assembly below: Except for the data section at the end, the assembly is pretty much same other than the label names. Perfect! Building a disassembler for a format without metadata is a fun exercise. You have to find the patterns in the data, come up with heuristics, and use them to write your disassembler. You may need to go over the output multiple times to refine it. While the approach here is specific to LC-3, the principles generalize to other code/data separation problems in binary analysis and reverse engineering. The full code for this disassembler is available here . If you have any questions or comments, please leave a comment below. If you liked this post, please share it. Thanks for reading! I patched the VM to not print when halting. ↩︎ Most LC-3 assemblers produce .sym files containing the debug symbols. But we don’t use them for disassembling the binaries in this post. ↩︎ Actually, the ISA defines opcode as reserved for future use. ↩︎ Thanks for reading this post via feed. Feeds are great, and you're great for using them. ♥ This post was originally published on abhinavsarkar.net . Read more of my posts and notes . Introduction to LC-3 Problem in Disassembling LC-3 Decoding Instructions Basic Disassembly Fixed-Point Cleanup Postprocessing Pretty-Printing Reading the Binary Finishing Up First, we decode instructions that are unambiguous. Then, we use the context of the decoded instructions to speculatively decode the rest of the instructions/data. We repeat this till a fix-point is reached. Next, we clean up the data by combining bytes. Finally, we insert labels at the right places. to are the real LC-3 instructions. represents the one reserved opcode that the ISA defines as invalid 3 . is for capturing raw encoded binary data. represents a single character. represents a string, that is a sequence of characters. is a textual label used to annotate instructions that other instructions may jump to. It doesn’t exist in binary data, and is inserted by the disassembler. is a speculated instruction. It holds both the original instruction decoded from the binary data, and the guessed instruction depending on the context. followed by : This pattern loads a character at the relative into the registers and prints it. If we see this pattern, we know that the instruction at current index plus is a character. So we disassemble it immediately as a character in . followed by : This signals that the data at the relative is a null-terminated one-character-per-word string. So we disassemble it character-by-character till we reach the null bit in . followed by : This pattern is for a null-terminated two-characters-per-word string, so we disassemble accordingly in . , used for , : If the target is known to be data or does not exist, this instruction must be wrong, because these instructions are for jumping to code. Rewrite the instruction to . , used for : may or may not point to data. But if the instruction is in a neighbourhood that mostly has data, it is very likely to be data itself. Rewrite such instruction as , capturing both the data and instruction forms. , used for , , : The target doesn’t strongly indicate code or data. However, if is as well, the instruction is likely to be data if present in a data-heavy neighbourhood. In such case, rewrite as , otherwise ignore. a run of s followed by to become a single with the terminator, and a run of two-character entries followed by to become a single combined . I patched the VM to not print when halting. ↩︎ Most LC-3 assemblers produce .sym files containing the debug symbols. But we don’t use them for disassembling the binaries in this post. ↩︎ Actually, the ISA defines opcode as reserved for future use. ↩︎
AI
Programming
CSS
Business
Career
Gaming
HTML
UI
Hardware
Web Development
Marketing
Tutorial
C#
JavaScript
Open Source
Media
Entertainment