\chapter{Introduction to Intel Machine Language}
\label{chap:machlang}

\section{Overview}

This document serves as a brief introduction to Intel machine language.
It assumes some familiarity with Intel assembly language (using the
AT\&T syntax).

\section{Relation of Assembly Language to Machine Language}

Assembly language (AL) is essentially identical to machine language (ML). The
only difference is that ML expresses any machine instruction using the 1s and
0s on which the machine operates, while AL expresses the same instruction using
English-like abbreviations for specific bit patterns.

Consider for instance a register-to-register {}``move{}'' operation,
which copies the contents of one register to another.\footnote{ The term
{}``move{}'' is thus a misnomer, though by now entrenched in computer
jargon.} The bit pattern which signals this, called an \textbf{op
code}, is 1000100111.  The circuitry is set up so that when the CPU sees
1000100111 in the first ten bits of an instruction, it knows it must do a
register-to-register move.\footnote{ What do we mean by the
{}``first{}'' 10 bits? An Intel instruction can be several bytes in
length. When we speak of the {}``first{}'' byte of an instruction, we
mean the one contained in the lowest-numbered memory address. When we
speak of the {}``first{}'' bit within a byte, we mean the
most-significant bit within that byte.  }

As humans we get tired of writing long strings of 1s and 0s, and it
would also be burdensome to have to remember which ones signify which op
codes. As an alternative, we could hire a clerk. We would say to the
clerk, {}``Clerk, every time you see me write {\bf movl}, you enter
1000100111.{}'' The name {\bf movl} is a lot easier for us to remember
than 1000100111, so would be a great convenience for us (though the poor
clerk would have to deal with these things).

The circuity in the CPU is also set up to know that register-to-register
{}``move{}'' instructions, i.e. instructions whose first bits are
1000100111, are two bytes long.\footnote{Note that that means that the
circuity will advance the Program Counter register by 2, so as to
prepare for the fetch of the instruction which follows the move
instruction.}  Also, the circuity is set up to know that  the source and
destination operands of the move---which register is to be copied to
which other register---are stored in the remaining six bits in this
instruction: The eleventh, twelth and thirteenth bits specify the source
register, and the fourteenth, fifteenth and sixteenth indicate the
destination register, according to the following codes:

\begin{tabular}{|c|c|}
\hline 
EAX&
 000\\
\hline 
EBX&
 011\\
\hline 
ECX&
 001\\
\hline 
EDX&
 010  \\
\hline 
\end{tabular}

(The Intel CPU also has a number of other registers, but we will not list their
codes here.)

Again, instead of having to remember the code for say, EBX, we would
tell the clerk {}``Whenever I say \%ebx, I mean 011,{}'' and so on.
Well, our {}``clerk{}'' is the assembler, e.g. \textbf{as} in standard
Unix systems. We use a text editor to type those same abbreviations into
a file, and the assembler converts them to 1s and 0s just as a clerk
would. 

Remember, though, that we the programmer are still in full control of
which instructions (i.e. which operations and operands) to specify, in
contrast to a compiler.  If for example we type the line

\begin{verbatim}
movl %eax,%ebx
\end{verbatim} 

into a file, say {\bf x.s}, we know the assembler will convert it to the
machine instruction which does this operation, which we will see below
happens to be 1000100111000011, i.e. 0x89c3.  By contrast, if we run 

\begin{Verbatim}[fontsize=\relsize{-2}]
y = x + 3;
\end{Verbatim}

through a compiler, we have no idea what machine instructions the
compiler will generate from it.  Indeed, different compilers would
likely generate different machine instructions.

The assembler places the machine code it generates, e.g.
1000100111000011 above, into the object file, {\bf x.o}. 

\section{Example Program}

\subsection{The Code}

We ran an assembly language source file, {\bf Total.s}, through the
\textbf{as} assembler with the {\bf -a} option, the latter requesting the
assembler to print out for us the machine code it produces, side-by-side
with our original assembly language.  Here is the output:

\begin{Verbatim}[fontsize=\relsize{-2}]
GAS LISTING Total.s page 1

   1              
   2              # finds the sum of the elements of an array
   3              
   4              # assembly/linking Instructions:
   5              
   6              # as -a --gstabs -o total.o Total.s
   7              # ld -o total total.o
   8              
   9              .data  # start of data section
  10              
  11              x:    
  12 0000 01000000       .long   1
  13 0004 05000000       .long   5
  14 0008 02000000       .long   2
  15 000c 12000000       .long   18
  16              
  17              sum:
  18 0010 00000000       .long 0
  19              
  20              .text  # start of code section
  21              
  22              .globl _start
  23              _start:
  24 0000 B8040000       movl $4, %eax  # EAX will serve as a counter for 
  24      00
  25                                   # number of words left 
  26 0005 BB000000       movl $0, %ebx  # EBX will store the sum
  26      00
  27 000a B9000000       movl $x, %ecx  # ECX will point to the current 
  27      00
  28                                   # element to be summed
  29 000f 0319     top:  addl (%ecx), %ebx
  30 0011 83C104         addl $4, %ecx  # move pointer to next element
  31 0014 48             decl %eax      # decrement counter
  32 0015 75F8           jnz top        # if counter not 0, loop again
  33 0017 891D1000 done: movl %ebx, sum # done, store result in "sum"
  33      0000
  34 001d 8D7600   

DEFINED SYMBOLS
             Total.s:11     .data:00000000 x
             Total.s:17     .data:00000010 sum
             Total.s:23     .text:00000000 _start
             Total.s:29     .text:0000000f top
             Total.s:33     .text:00000017 done

NO UNDEFINED SYMBOLS
\end{Verbatim}

\subsection{Feedback from the Assembler}

Each line in this output is organized as follows:

\begin{tabular}{|c|c|c|c|}
\hline 
Display Line Number &
Memory Offset &
Contents &
Assembly Source Line \\
\hline 
\end{tabular}

The {\bf offset} is a relative memory address, i.e. the distance from
the given item to the beginning of its section ({\bf .data}, {\bf
.text}, etc.).  

Here the clerk is saying to us, ``Boss, here is what I did with that
assembly-language source line of yours, which I've shown here in the
fourth field.  I translated it to the coding you see in the third field,
and I arranged for this coding to go into the offset I've listed in the
second field.  For your convenience, I've also shown the line number
from your source file in the first field.''

What does the word {\it offset} mean?  For instance, look at Line 18.
It says that the word which we labeled {\bf sum} in our source code will
be located 0x10 = 16 bytes from the beginning of the {\bf .data}
section. 

\subsection{A Few Instruction Formats}

The Contents field shows us the bytes produced by the assembler from our
source code, {\it displayed byte-by-byte, in order of increasing address}.
Note the effect of little-endian-ness, for instance in Line 13.  That
line says that our assembly code

\begin{verbatim}
.long 5
\end{verbatim}

produced the sequence of bytes 05 00 00 00.  That makes sense, right?
In the number 00000005, the least significant byte is 05 (recall that a
byte is two hex digits), so it will have the lowest address, and thus it
will be displayed first.

The actual address of this word will be determined when the program is
linked by \textbf{ld}. The latter will choose a place in memory at which
to begin the {\bf .data} section, and that will determine everything
else goes.  If that section begins at, say, 0x2020, then for instance
the data corresponding to Line 15 will be at case 0x2020+0x0c = 0x202c.

Note that the addresses assigned to these items in the {\bf .data}
section of our source file are contiguous and follow the same order in
which we {}``declared{}'' them in the source file.

Now, let's learn a few more Intel machine-language formats, to add to
the register-to-register move we saw above. First, let's consider the
one on Line 24.

This instruction is an immediate-to-register move, where the word
{}``immediate{}'' means {}``the source operand is a constant which
appears in the instruction.{}'' Here the constant is 4; it is a 32-bit
integer occupying the last four bytes of this five-byte
instruction.

This type of instruction is coded by its first five bits being 10111.
The next three bits code the destination register, in this case being
000. So the first byte of the instruction is 10111000, i.e. 0xb8,
followed by the constant 04000000 (again, note the effect of
Intel CPUs being little-endian). We will describe the format for
immediate-to-register move as 10111DDDIMM4, where 10111 is the op code,
DDD denotes the destination register and IMM4 denotes a 4-byte immediate
constant.\footnote{We describe our earlier register-to-register move
format as 1000100111SSSDDD.}

Note also on Line 24 that the offset-field count has been reset back to
0000 again, since we are now in a new section ({\bf .text}). 

Lines 26 and 27 are similar, but one aspect must be noted in the latter.
The immediate constant here, {\bf \$x}, is the address of {\bf x}. But all the
assembler knows at this point is that later, when the program is linked,
{\bf x} will be 0 bytes from the start of the {\bf .data} section. If
\textbf{ld} allocates the {\bf .data} section at, say, 0x2000, then {\bf
x} will be at that address. So, ideally the immediate constant placed by
the assembler into the machine instruction here would be 0x2000 (or
wherever else the {\bf .data} section ends up). But, since this value is
unknown at assembly time, the assembler just puts the offset, 0, in the
instruction on a temporary basis, to be resolved later by the linker.

\checkpoint

In Line 29 we see an indirect-to-register add. Its op code is
0000001100, followed by three bits for the destination register and then
three bits for the source register (the latter being used in indirect
mode). We will state this notationally as 0000001100DDDSSS.
An add which is register-to-indirect, e.g. {\bf addl \%ecx,(\%ebx)}, has
the format 0000000100SSSDDD.

Of course, the choice of the codes for operations, registers and addressing
modes is arbitrary, decided by the hardware designers. Typically it is chosen
according to two considerations:

\begin{itemize}

\item Instructions which are expected to be more commonly used should
have shorter codes, in order to conserve memory and disk space. 

\item The circuitry may be easier to design, or made faster, with some codes.

\end{itemize}

In Line 31 we see a register decrement operation. A little
experimentation---changing the register to EBX and then observing how
the machine code changes---reveals that the format for this kind of
instruction is 01001DDD, where DDD is the destination register.

\subsection{Format and Operation of Jump Instructions}

There is quite a bit to discuss on Line 32. The format for this
jump-if-Zero-flag-not-set instruction is 01110101IMM1, where 01110101 is
the op code and IMM1 is a 1-byte immediate signed constant which
indicates the \textbf{target} of the jump, i.e.  where to jump to if the
Zero flag is not set. The constant is actually the (signed) distance to
the target, as follows.

Recall that any computer has a register whose generic name is the
Program Counter (PC) which points to the next instruction to be
executed. Let's say that the {\bf .text} part of the program starts at
0x300ba. Then the instruction shown here in Line 32 will be at
0x300ba+0x15 = 0x300cf, and our target (shown in Line 29) will be at
address 0x300ba+0xf = 0x300c9.

Recall also that as soon as an instruction is fetched for execution, the PC,
which had been pointing to that instruction, is incremented to point to the
next instruction. In the case of the instruction in Line 32, here is how the
incrementing occurred: The PC had contained 0x300cf, and the CPU fetched the
instruction from that location. Then the CPU, seeing that the instruction begins
with 01110101, realizes that this is a JNZ instruction, thus 2 bytes in length.
So, the CPU increments the PC by 2, to point to the instruction in Line 33,
at 0x300cf+2 = 0x300d1.

Now, to execute the JNZ instruction, the CPU checks the Zero flag. If
the flag is not set, the CPU adds the IMM1 part of the JNZ instruction
to the current PC value, treating IMM1 as an 8-bit 2s complement number.
As such, 0xf8 = -8, so the sum in question will be 0x300d1-8 = 0x300c9.
This latter quantity is exactly what we want, the address of our target.
The CPU puts this number in the PC, which means that the next
instruction fetch will be done from location 0x300c9---in other words,
we jump to the line we had named {\bf top} in our assembly language
source file, just as desired.

\checkpoint

Of course, the assembler knows that the CPU will add IMM1 to the current
PC value, and thus sets IMM1 accordingly. Specifically, the assembler
computes IMM1 to equal the distance from the instruction following the
JNZ instruction to the target instruction.\footnote{This implies that it
doesn't matter that the execution-time address of {\bf top} is unknown
at assembly time, unlike the case in Line 27, where the lack of
knowledge of the execution-time address of {\bf x} caused a problem.}

IMM1 is just 8 bits.  If the distance to the target is greater than what
can be expressed as an 8-bit 2s complement number, the Intel instruction
set does have an alternate version of JNZ with format
0000111110000101IMM4.

Keep in mind that the circuitry which implements JNZ will be quite
simple.  It will check the Zero Flag, and if that flag is 1, the
circuitry will then add the second byte of the instruction (-8 in our
example here) to the EIP register.  That's all!

\subsection{Other Issues}

The assembler goes through the {\bf .s} source file line by line,
translating each line to the corresponding machine code.  By the time
the assembler sees this JNZ instruction, it has already seen the line
labeled {\bf top}.  Thus it knows the offset of {\bf top} within the
{\bf .text} section, and can compute the distance to that target, as we
saw here.  But what if the jump target were to come \underline{after}
this line with JNZ?  In this case, the assembler won't know the offset
of the target yet, and thus will not be able to completely translate the
instruction yet.  Instead, the assembler will make a note to itself,
saying that it will come back and finish this line after it finishes its
first pass through the {\bf .s} file.  So, assemblers are {\bf
two-pass}, going through the {\bf .s} file twice.

In doing the computation 0x300d1-8, the CPU must first make the two
quantities compatible in terms of size. So, the CPU will do a
\textbf{sign extension}, extending the 8-bit version of -8, i.e.  0xf8,
to the 32-bit version, i.e. 0xfffffff8.  So, technically, the CPU is
performing 0x000300d1+0xfffffff8, which does indeed come out to 0x300c9.

The formats for some other conditional jump instructions are: JZ,
01110100IMM1; JS format 01111000IMM1; JNS 01111001IMM1; and so on. The
unconditional jump JMP has format 11101011IMM1.

The Intel instruction set contains hundreds of instructions, and their
formats become quite complex. We will not pursue this any further.

Note, though, that even in the few formats we've seen here, there is a
large variation in instruction length.  Some instructions are only one
byte long, some are two bytes, and so on, with lengths ranging up to six
bytes in the instructions here.  This is in great contrast to RISC CPUs
such as MIPS, in which all instructions are four bytes long.  RISC
architectures aim for uniformity of various kinds, which helps make a
``lean and mean'' machine.

\section{It Really Is Just a Mechanical Process}

As pointed out earlier, the assembler is just acting like a clerk,
mechanically translating English-like codes to the proper bits.  To
illustrate this, note that we could ``write'' our own machine language
in hex, right there in the middle of our assembly code!  For instance,
recall from our earlier example that the instruction {\bf decl \%eax}
has the machine language 0x48.  We could set that 0x48 ourselves:

\begin{verbatim}
... # same code as before, but not shown here
      movl $x, %ecx  
top:  addl (%ecx), %ebx
      addl $4, %ecx  
      .byte 0x48  # we write "directly" in machine language
      jnz top  
done: movl %ebx, sum  
\end{verbatim}

With that {\bf .byte} directive, we are simply saying to the assembler,
``After you translate {\bf addl \$4, \%ecx} to machine code, put a byte
0x48 right after that code.''  Since this is what the assembler would
have done anyway in assembling {\bf decl \%eax}, we get exactly the same
result.  Try assembling and running the program with this change; you'll
see that it works fine.

\section{You Could Write an Assembler!}

A common exercise in assembly language courses is to write a simple
assembler.  Even if you are not assigned to do so, it would be a very
enriching exercise if you were to at least give some thought as to how
you would do it.  For example, just stick to the few instructions
covered in this chapter.  Your job would be to write a program, say in C,
which translates assembly code for the instructions and addressing modes
covered in this chapter to machine language.

