# when and how is the machine language (binary stream) mapped to an existing instruction?

I'm trying to better understand the entire process of coding, which involves translating the higher level languages (c++/java/python and so on) into binary data that tells the CPU to execute operations based upon its native instruction set.

My question would be how, exactly, do the assembler instructions get translated into a sequence of 1s and 0s . Where does the mapping of a line of code like, say

addi $s0,$s0, 1


becomes a binary sequence based upon the opcode (addi) and so on. Where is the related mapping table (for assembler language to specific instructions) stored and how is it used to instruct the ALU part of the processor to, well, perform tasks?

I'm sorry for posing a great deal of questions, but I hope I'm making myself clear by expanding the issue.

Thank you!

Edit: I was mainly not aware of the loader's role (mainly the OS, in most of the nowadays programs) in the entire "compile-assemble-link-LOAD (and I have to emphasize on the next part: IN MEMORY)" process; that's what I found hard to understand - the whole memory storing process. Now it makes a lot more sense that, after the program is stored in memory, the required operations are performed by the CPU following the instruction set layout and the program executes it's intended task(s).

– G36
Aug 17 '19 at 19:52
• For a different and very simplistic approach how an actual CPU and a higher level language can meet, take a look at the J1 Forth CPU. That CPU is made that way it has the Forth primitives as its assembly language. Aug 17 '19 at 20:57
• the Assembler has to validate the syntax of each line of code and ensure your instruction expectations ( such as DSZ decrement-and-skip-if-zero from Data General machines) are legit; also the constants (such as ADD 13) are of valid range and base; also the JUMP offsets must be validated, and the named-jumps { JMP new_start) proven to be legit; then the lookup tables let you spit out the binary. Aug 18 '19 at 2:56
• Not really an answer, but I suggest watching Ben Eater's breadboard computer videos: youtube.com/… You'll understand it after that.
– Nyos
Aug 18 '19 at 14:39

The actual binary machine code instruction set, and/or the sub-fields that compose the instruction set, are usually encoded in look-up tables (software arrays), or switch/case statements. After parsing the human-readable text into tokens, numerical forms of these tokens can then be used to index into the lookup tables for the binary encodings. The binary subfields, and offsets perhaps derived later, can then be "assembled" into binary machine code instructions by concatenation.

The very first assemblers were mostly women (job title "computer") who did this look-up manually. (reference: history of the Eniac and Mark I, and the history book "When Computers were Human", by Grier).

On the other end, in the CPU hardware, there's usually an instruction register (or many for parallel execution models) followed by a decoder (or several), which (perhaps pipelined in layers) converts bit-fields into control signals, often a vast number. Older computer were sometimes implemented using microcode, where another semi-hidden processor does the decoding of the visible machine code in software (hard-coded or pre-loaded vertical or horizontal microcode, 2 layers on some CPUs, such as the 68000).

The assembly instruction itself has several sub-fields in it, including the opcode, the sources and the destinations, and in some cases a short integer immediate value.

For working with source-based assembly like your example, you will 'assemble' it into an executable to run on your machine. The assembler utility parses your human-readable text and translates the sub-fields that form the instruction into binary, based on tables (that is, the instruction set) given for the architecture. These fields are packed - assembled - into instructions. Hence the term, assembly code.

So you have these three things: the instruction set, your source code, and the assembler that translates the two into an executable binary. You’ve loaded your binary into the hardware and launched the program. What’s next?

The Secret Life Of Assembly

Within the CPU itself, the assembly instructions are unpacked and decoded into low-level signals that select the operation and steer the data to and from the appropriate places. This process is called, unsurprisingly, instruction decode.

Instruction decoding is accomplished with the help of an even lower-level type of software and logic called microcode.

Microcode: CISC vs. RISC vs. Reward

CISC (Complex Instruction Set Computers) rely on microcode to implement very complex instructions. Microcode is an expanded version of the assembly opcode that is itself a programming language, stored in a special memory called a control store. A single CISC instruction maps onto many micro-instructions and takes multiple cycles to complete.

This is great for instruction density, but the downside is it that because it takes multiple microcode clock cycles to complete, so machine throughput is slower.

RISC (Reduced Instruction Set Computer) architectures like ARM and MIPS seek to avoid the microcode bottleneck by using direct (logic-based) instruction decoding, and execute most instructions in a single cycle. So machine throughput is higher.

The trade-off is the RISC instruction set is simpler and less dense than CISC, so some operations that would be one instruction on a CISC machine take multiple operations on a RISC. This makes their work-per-opcode lower, and increases pressure on the code store to keep the RISC pipeline fed.

RISC architectures mitigate this somewhat by relying on a large number of fast registers for storing operands, and large, fast cache memory to reduce instruction fetch latency.

In reality, RISC techniques have flowed back to CISC (notably x86) making them faster as well, but nevertheless they are still more complex than RISC. RISC machines have also become more complex, while still adhering to the same low-cycle-count simple instruction philosophy.

• 'The assembler parses the human-readable form into the opcode and operands, which are assembled into machine instructions'. It's this exact bit that I have yet to fully understand. Where is the actual instruction set located? Aug 17 '19 at 19:36
• @tudorarion Have you ever written a text parser that tokenizes strings? It's not a complex process. I've written a C compiler, optimizing back-ends for other compilers, and I've written many assemblers. When you ask, "where is the actual instruction set located?", this tells me you probably need a small lecture about the divisions between hardware implementation (particularly, the decoding portion if not more) and the software that translates text files into bits that can be handled by that hardware. Can you elaborate your question more? (I don't want to write a book.)
– jonk
Aug 17 '19 at 19:47
• I understand that the inquiry is a bit lax and I apologize for that. What I'm having a bit of a problem understanding is the actual software to hardware translation of the said instruction given to the CPU. I can dig deeper into researching bit by bit the answer given by @hotpaw2 as it seems to cover my question pretty well. Also, now I'm going through " Computer Organization and Design " by David A. Patterson and John L. Hennessy . Have you got any other reputable references similar to this one? (or any good resource for learning the basics of CS) Thanks a lot! Aug 17 '19 at 19:57
• The Hennessy and Patterson books are currently one of the (if not the) authoritative sources on this technology. There's another good textbook that Patterson used in teaching his courses (before writing his own text). Can't remember the title, will have to hunt for it in storage. Aug 17 '19 at 20:02
• @tudorarion (I've met and worked with Dr. Hennessy.) That book is pretty good and it targets software types more than hardware types. So that would seem to be perfect, to me. (Their "Computer Architecture: A Quantitative Approach" is more for hardware types.) There is another book I really like if you want to seriously dig into designing an MCU, which is "Microprocessor Design Using Verilog HDL" by Dalrymple. There, you lay out your entire instruction map (excel tables, almost) and work out an approach that includes bus design and other details.
– jonk
Aug 17 '19 at 20:04

assembling the assembly language into machine code is one step completely independent of execution of machine code.

If you look at the documentation for the specific instruction set, for mips and arm and other IP vendors you go to them if the processor vendor also makes the chips like intel x86 you go there. Below I have a couple of instructions from the arm thumb instruction set,

add rd,rn,rm
and rd,rm


where d,n,m are 0-7 (registers r0 through r7).

VERY VERY brute force and crude but functional:

assuming a line from a file is in a string (C code) read from the file

char newline[256];
...
unsigned int gpr ( unsigned int ra, unsigned int *reg )
{
if(newline[ra]!='r')
{
printf("syntax error\n");
return(1);
}
ra++;
if((newline[ra]<0x30)||(newline[ra]>0x37))
{
printf("syntax error\n");
return(1);
}
*reg=newline[ra]&7;
return(0);
}
...
{
ra=4;
if(gpr(ra,&rd)) continue;
ra+=2;
if(newline[ra]!=',')
{
printf("syntax error\n");
continue;
}
ra++;
if(gpr(ra,&rn)) continue;
ra+=2;
if(newline[ra]!=',')
{
printf("syntax error\n");
continue;
}
ra++;
if(gpr(ra,&rm)) continue;
inst=0x1800|(rm<<6)|(rn<<3)|rd;
}
if(strncmp(newline,"and ",4)==0)
{
ra=4;
if(gpr(ra,&rd)) continue;
ra+=2;
if(newline[ra]!=',')
{
printf("syntax error\n");
continue;
}
ra++;
if(gpr(ra,&rm)) continue;
inst=0x4000|(rm<<3)|rd;
printf("0x%04X and r%u,r%u\n",inst,rd,rm);
}


VERY inflexible too, many (not all) assemblers will allow for white space.

So if I feed this simple assembler this code

add r1,r2,r3
and r1,r2


and run it I get

0x18D1 add r1,r2,r3
0x4011 and r1,r2
syntax error


The toolchain (compiler, assembler, linker) to be useful has a file format or set of file formats used for the source code languages plus some intermediate formats so an object file format and a final binary file format and some way to communicate the linker specs, what address space has read/write memory, maybe where if any read only (rom/flash) address space. Where computer science/convention concepts .text, .data, .bss ... are located (.text being the machine code and related binary information, .data being initialized read/write memory, think variables. and .bss being zeroed read/write memory, also think variables.

The file formats used are not relevant to the processor and how it works what the processor requires is that there is logic that can feed it instructions and data on some bus which is also not relevant, but part of the processor IMPLEMENTATION. MIPS as you have noted is used by the textbooks you mentioned to make textbook/academic style processors. Every Nth computer engineering degree major will make a mips processor in college, usually in verilog or vhdl, so there are hundreds of thousands if not another order of magnitude or two number of mips implementations out there. Most using wishbone (google it) but is again not relevant to making a mips processor.

I chose a couple of very simple ARM thumb instructions, IP that you buy from ARM and put in your chip. ARM itself has many cores and every generation is a new implementation, but somewhere in that logic a fetch happens and there is an instruction latched in the logic and some logic that in some form (pseudo code shown here)

inst_add = 0;
inst_and = 0;
rd = inst[2:0];

if(inst[15:9] == 7b0001100)
{
rn = inst[5:3];
rm = inst[8:6];
}

if(inst[15:6] == 10b0100000000)
{
inst_and = 1;
rm = inst[5:3]
}


and then somewhere else the add and and implementations with flags and all that.

There is no magic to it. If you can count from 0 to 1 and understand AND, OR, NOT then you understand logic that is used to make processors, they are no more complicated than that.

You can certainly try to use discreet logic elements and draw them on paper or use schematic capture if that is still a thing or you can use an HDL, hardware design language like VHDL or Verilog (or others, yes there are others, that usually compile into VHDL or Verilog, some tools are only VHDL and Verilog is compiled into VHDL first to be used by that tool).

You can just as easily make an instruction set simulator that you can program in some programming language of your choice.

    //AND
if((inst&0xFFC0)==0x4000)
{
rd=(inst>>0)&0x7;
rm=(inst>>3)&0x7;
if(DISS) fprintf(stderr,"ands r%u,r%u\n",rd,rm);
rc=ra&rb;
write_register(rd,rc);
do_nflag(rc);
do_zflag(rc);
return(0);
}


Back to assemblers or language parsing in general. For various reasons a very common way to solve the problem is using bison/flex which are derived from older tools (lex,yacc)(there are other derivatives no doubt). At the end of the day the parser is this massive state machine generated by the tool For my two instruction assembler it would go character by character in the line if the first character is not an 'a' then syntax error. Then it would look at the second character and compare with n or d if neither syntax error otherwise if n then the third must be a d, the fourth a space and then into the register parsing. if the second is a d then the third a d, the fourth a space and so on. So if/when you go down this path of googling bison/flex and following a tutorial examine the c or c++ output of one of the tools and see this state machine.

There is no rule/requirement that you have to use these or any other already made parsing tools or tools that generate parsers (code that generates code like the lexx/yacc, flex/bison solutions). You can certainly come up with the parser on your own as I have done above.

while very possible to write machine code, by hand on paper or in a text editor, getting that information into a format that will then be usable by one of these tools is often not worth it, depends on the tool. gnu assembler will accept

.hword 0x1801


and you could write machine code like that if you prefer. that is still assembly language being parsed by some parser and so on...

ultimately the processor and surrounding chip and memory infrastructure, the system needs to support the processors rules for booting and such, be able to feed the processor vectors and instructions and data to make it work. Somewhere in ram or rom that 0x1801 instruction lives it is then fed into the processor as the next instruction the processor picks apart the fixed portions in this case the upper 7 bits, and from that knows to parse the operand and result registers from the rest of the instruction. MIPS as you will see is not much different there is a first place you look in a mips instruction then depending on what you find there there is a secondary opcode field, and then from there the operands.

You can go to places like opencores and find a good mips or an old arm 2/3 or some others, remember you get what you pay for, there are a couple-few of good processors there, others are well...risc-v is becoming a fad for now, will see how that goes. There are some cores out there too, gnu has tools for arm, risc-v, mips and many others. as well as there being other toolchains. you can see working implementations of a processor in an HDL. some are easy to sim with verilator or icarus or ghdl or other. and from there you can use gtkwave or some other tool to see the processor in action.

Understand that the textbooks you are reading are just textbooks. An introduction to the terms, decode, execute, etc. No reason whatsoever to assume that processors buried in chips you can buy today only have a handful of pipeline steps. You can have fewer or more or no pipeline at all. The same steps have to happen fetch, decode, etc. And again if you take 100 engineers and give them an ISA and ask them to implement it you will get somewhere between 1 and 100 different implementations, assuming all are functional. More likely to be closer to the 100 than 1.

Same goes for compilers and assemblers give 100 fully capable folks a language specification and you will get somewhere between 1 and 100 different implementations that will do the job. The task is the output how you get there can vary.

Commenting on one of the other answers. Some (CISC) processors are still microcoded, it makes sense to microcode a CISC, kinda the reason RISC exists was to not be microcoded. But if you go way back and say look at visual6502, these processors were made by hand. Some folks a very well known man in particular, but anyway would draw on paper each layer of the chip and essentially hand make/draw each transistor and the metal layers that connected them. For financial and sanity reasons it made sense that we started with CISC in that era, you make a ROM based state machine, each high level CISC instruction essentially addresses into the rom and then the rom defines the sub instructions or microcode to actually implement the high level instruction. And these are not necessarily "instructions" they could be based on implementation be a bunch of discretes or mux inputs that route data to from memory busses or alus or the register file, etc. so you needed to implement the logic in a way that you could drive it from this rom, and then after you built it if there were problems you had a chance to solve it by changing the contents of the rom and not have to spin the chip at great expense esp since it was all hand drawn. It is still true today that the bulk of the cost is the layout and generating the masks essentially. Just like pcb design it is not all automated, part manual part automated.

If you are still in school there are resources where you can use I forget the term micro foundries, some colleges have equipment to make small runs of chips at a reasonable cost and/or if you take the right class at the right school is included. But you wont get the actual chip for many months just like the real world. I have not tried one of these but would like to. Am much closer to the end of my career than the college days, but some of these resources are available to the general public as well. Cheaper than spending the several to tens of millions to use a commercial fab for hire place.