15

Is there an easy way to visualize the step between assembling code to machine code?

For example if you open about a binary file in notepad you see a textually formatted representation of machine code. I assume that each byte(symbol) you see is the corresponding ascii character for it's binary value?

But how do we go from assembly to binary, what's going on behind the scenes??

27

Look at the instruction set documentation, and you will find entries like this one from a pic microcontroller for each instruction:

example addlw instruction

The "encoding" line tells what that instruction looks like in binary. In this case, it always starts with 5 ones, then a don't care bit (which can be either one or zero), then the "k"s stand for the literal you are adding.

The first few bits are called an "opcode," are are unique for each instruction. The CPU basically looks at the opcode to see what instruction it is, then it knows to decode the "k"s as a number to be added.

It's tedious, but not that difficult to encode and decode. I had an undergrad class where we had to do it by hand in exams.

To actually make a full executable file, you also have to do things like allocate memory, calculate branch offsets, and put it into a format like ELF, depending on your operating system.

10

Assembly opcodes have, for the most part, a one-to-one correspondence with the underlying machine instructions. So all you have to do is identify each opcode in the assembly language, map it to the corresponding machine instruction, and write the machine instruction out to a file, along with its corresponding parameters (if any). You then repeat the process for each additional opcode in the source file.

Of course, it takes more than that to create an executable file that will properly load and run on an operating system, and most decent assemblers do have some additional capabilities beyond simple mapping of opcodes to machine instructions (such as macros, for example).

7

The first thing you need is something like this file. This is the instruction database for x86 processors as used by the NASM assembler (which I helped write, although not the parts that actually translate instructions). Lets pick an arbitrary line from the database:

ADD   rm32,imm8    [mi:    hle o32 83 /0 ib,s]      386,LOCK

What this means is that it describes the instruction ADD. There are multiple variants of this instruction, and the specific one that is being described here is the variant that takes either a 32-bit register or memory address and adds an immediate 8-bit value (i.e. a constant directly included in the instruction). An example assembly instruction that would use this version is this:

add eax, 42

Now, you need to take your text input and parse it into individual instructions and operands. For the instruction above, this would probably result in a structure that contains the instruction, ADD, and an array of operands (a reference to the register EAX and the value 42). Once you have this structure, you run through the instruction database and find the line that matches both the instruction name and the types of the operands. If you don't find a match, that's an error that needs to be presented to the user ("illegal combination of opcode and operands" or similar is the usual text).

Once we've got the line from the database, we look at the third column, which for this instruction is:

[mi:    hle o32 83 /0 ib,s] 

This is a set of instructions that describe how to generate the machine code instruction that's required:

  • The mi is a descriptiuon of the operands: one a modr/m (register or memory) operand (which means we'll need to append a modr/m byte to the end of the instruction, which we'll come to later) and one an immediate instruction (which will be used in the description of the instruction).
  • Next is hle. This identifies how we handle the "lock" prefix. We haven't used "lock", so we ignore it.
  • Next is o32. This tells us that if we're assembling code for a 16-bit output format, the instruction needs an operand-size override prefix. If we were producing 16-bit output, we'd produce the prefix now (0x66), but I'll assume we aren't and carry on.
  • Next is 83. This is a literal byte in hexadecimal. We output it.
  • Next is /0. This specifies some extra bits that we will need in the modr/m bytem, and causes us to generate it. The modr/m byte is used to encode registers or indirect memory references. We have a single such operand, a register. The register has a number, which is specified in another data file:

    eax     REG_EAX         reg32           0
    
  • We check that reg32 agrees with the required size of the instruction from the original database (it does). The 0 is the register's number. A modr/m byte is a data structure specified by the processor, that looks like this:

     (most significant bit)
     2 bits       mod    - 00 => indirect, e.g. [eax]
                           01 => indirect plus byte offset
                           10 => indirect plus word offset
                           11 => register
     3 bits       reg    - identifies register
     3 bits       rm     - identifies second register or additional data
     (least significant bit)
    
  • Because we are working with a register, the mod field is 0b11.

  • The reg field is the number of the register we're using, 0b000
  • Because there's only one register in this instruction, we need to fill in the rm field with something. That's what the extra data specified in /0 was for, so we put that in the rm field, 0b000.
  • The modr/m byte is therefore 0b11000000 or 0xC0. We output this.
  • Next is ib,s. This specifies a signed immediate byte. We look at the operands and note we have an immediate value available. We convert it to a signed byte and output it (42 => 0x2A).

The complete assembled instruction is therefore: 0x83 0xC0 0x2A. Send it to your output module, along with a note that none of the bytes constitute memory references (the output module may need to know if they do).

Repeat for every instruction. Keep track of labels so you know what to insert when they're referenced. Add facilities for macros and directives that get passed to your object file output modules. And this is basically how an assembler works.

  • 1
    Thank you. Great explanation but shouldn't it be "0x83 0xC0 0x2A" rather than "0x83 0xB0 0x2A" because 0b11000000 = 0xC0 – Kamran Mar 23 '17 at 22:28
  • @Kamran - $ cat > test.asm bits 32 add eax,42 $ nasm -f bin test.asm -o test.bin $ od -t x1 test.bin 0000000 83 c0 2a 0000003 ... yeah, you're quite right. :) – Jules Mar 25 '17 at 4:05
2

In practice, an assembler usually don't produce directly some binary executable, but some object file (to be fed later to the linker). However, there are exceptions (you can use some assemblers to produce directly some binary executable; they are uncommon).

First, notice that many assemblers are today free software programs. So download and compile on your computer the source code of GNU as (a part of binutils) and of nasm. Then study their source code. BTW, I recommend using Linux for that purpose (it is a very developer-friendly and free-software friendly OS).

The object file produced by an assembler contains notably a code segment and relocation instructions. It is organized in a well documented file format, which depends upon the operating system. On Linux, that format (used for object files, shared libraries, core dumps, and executables) is ELF. That object file is later input to the linker (which finally produces an executable). Relocations are specified by the ABI (e.g. x86-64 ABI). Read Levine's book Linkers and Loaders for more.

The code segment in such an object file contains machine code with holes (to be filled, with the help of relocation information, by the linker). The (relocatable) machine code generated by an assembler is obviously specific to an instruction set architecture. The x86 or x86-64 (used in most laptop or desktop processors) ISAs are terribly complex in their details. But a simplified subset, called y86 or y86-64, has been invented for teaching purposes. Read slides on them. Other answers to this question also explain a bit of that. You may want to read a good book on Computer Architecture.

Most assemblers are working in two passes, the second one emitting relocation or correcting some of the output of the first pass. They use now usual parsing techniques (so read perhaps The Dragon Book).

How an executable is started by the OS kernel (e.g. how the execve system call works on Linux) is a different (and complex) question. It usually sets up some virtual address space (in the process doing that execve(2)...) then reinitialize the process internal state (including user-mode registers). A dynamic linker -such as ld-linux.so(8) on Linux- might be involved at runtime. Read a good book, such as Operating System : Three Easy Pieces. The OSDEV wiki is also giving useful information.

PS. Your question is so broad that you need to read several books about it. I have given some (very incomplete) references. You should find more of them.

  • 1
    Regarding object file formats, for a beginner I'd recommend looking at the RDOFF format produced by NASM. This was intentionally designed to be as simple as realistically possible and still work in a variety of situations. The NASM source includes a linker and a loader for the format. (Full disclosure - I designed and wrote all of these) – Jules Sep 1 '18 at 16:59

protected by user22815 Mar 23 '17 at 22:37

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.