The Bootstrap Process

Basic BootStrap Process Requirements

• Who Loads the Loader? - If the Operating System provides the instructions necessary to load other programs, where do the instructions come from to load the Operating System? The traditional answer to this is that instructions to load the Operating System are contained in a ROM (Read Only Memory) which receives control on initial "power up". The instructions that perform this load of the Operating System (or of enough of the Operating System so that it can complete loading itself) is called a "bootstrap" program. Other possibilities (than ROM) exist, including a hardware facility to directly load values into memory locations through "toggle switches".
• Minimal Bootstrap Requirements - The bootstrap program must be able to read data from a secondary storage device into memory (typically from a non-file-structured area of a disk) into memory and "jump" to the area of memory where this data was stored.
• Possibility of Re-Use of Bootstrap ROM space - ROM memory is of no use once the function of its program has completed. The addresses used by the ROM become "wasted space", unavailable for other program use. In some systems this is overcome by having the ROM instructions include as a terminal action, the setting of an electronic switch which causes a separate "bank" of RAM memory to replace the ROM with respect to "address space".

LMC Bootstrap Loader Choices

Assumptions:

1. the bootstrap code will be stored in ROM memory; 20 locations will be reserved for this purpose.
2. the application program will be loaded from the "Input Slot"

Choices:

1. Bootstrap Code Location
   1. First 20 Mailboxes Will Be Bootstrap ROM: this means that all "application" programs must be re-translated to start at mailbox 20
   2. Last 20 Mailboxes Will Be Bootstrap ROM: this means that the "Reset" button will need to be "re-wired" to set the Counter to 80 (instead of 00)
   3. Bootstrap ROM Will Be Somewhere In The Middle Of The Mailbox Range: this will be considered "unworkable" since it divides the available memory for "application" programs into two small areas (note, however, this is how it is arranged for IBM PC machines with more than 1 Megabyte of memory).

   ---

2. Determining Size Of Application Program For Input
   1. Fixed Size Applications: all "application" programs will be the same size (padded with 00's or garbage if necessary to reach the maximum size)
   2. Terminated With A Sentinal Value: the problem with this method is determining what to use as a "terminal" value and how to permit this value to appear (for example as a DAT value) without signalling the end of the application program.
      The most common solution is to use a mechanism similar to that used for backslashes in C/C++ strings; in the string "...\t..." the \t has a "special meaning", namely "treate as a "tab" character; to get a single backslash, C/C++ requires that two be entered in a string e.g. "...\\t..." is treated as a single backslash followed by the letter "t". Similarly we could use the sequence 999 000 to signal end of input and require that 999 be duplicated when a single 999 value were intended (so the sequence ... 999 999 000 would be treated as a single 999 value followed by a 000 value, and not as an end of input signal).
   3. Prefix Run-Length Value: an initial number could be sent before the actual code, containing the number of mailbox values which were to follow in forming the "application" program/

Sample LMC Bootstrap Loader

Assumptions:

1. the bootstrap code will be stored in ROM memory; 20 locations with mailbox addresses 80 to 99 will be reserved for this purpose.
2. the application program will be loaded from the "Input Slot" and will be preceded by a "prefix run-length" value/

Code:

1. Pseudo-Code

      input length
      for (m=0; m<length; m++)
      {  input content
         mailbox[m] = content
      }
   

2. LMC Mnemonic Code (Version 1)

              ORG 80
      ** input length
              IN
              STO   length
      ** for (m=0; ...
              LDA   zero
              STO   m
      ** for (...; m<length; ...
      **  - we require a flag setting which will distinquish
      **   the case m<length from all other cases
      **  - comparisons are done using SUBtract but we
      **   have two options: (m-length) and (length-m)
      **
      **              | m<length      || m==length       m>length
      **   -----------|---------------||---------------|-------------
      **   (m-length) | N:1 Z:0 Pz:0  || N:0 Z:1 Pz:1  | N:0 Z:0 Pz:1
      **   -----------|---------------||---------------|-------------
      **   (length-m) | N:0 Z:0 Pz:1  || N:0 Z:1 Pz:1  | N:1 Z:0 Pz:0
      **
      **  observe that (m<length) is separated from the other two cases
      **  if we subtract (m-length) and check the N(egative) indicator
      forloop:LDA    m
              SUB    length
              SKN
              JMP    exitfor
      **  input content
              IN
              STO    content
      **  mailbox[m] = content
      **  -----------THIS IS THE UGLY PIECE-------
              LDA    m       ** mailbox address to assign content to
              ADD    store   ** a STO instruction with a zero address
              STO    assign  ** a STO with the address m
              LDA    content
      assign: DAT    000     ** this will be replaced with a STO [m]
      **  for (...; ...; m++)
              LDA    m
              ADD    one
              STO    m
              JMP    forloop
      ** end of bootstrap load
      exitfor:JMP    00      ** execute the code just loaded
      **
      ** ----------------------
      **
      zero    DAT    000
      one     DAT    001
      store   STO    00
      length  DAT
      m       DAT
      content DAT
   

3. LMC Mnemonic Code (Version 2)

   Notice there are a few problems with this code:

   1. As written the code rquires 26 mailboxes; but only 20 were allocated.
   2. The last 3 "variables" (length, m, and content) can not be locations in ROM, since they are variable values.

   The second problem helps reduce the first. The last 3 "variables" must be stored in the area before ROM:

              ORG  77   ## force next mailbox to be reset to 77
      length  DAT
      m       DAT
      content DAT
   

   But we still need to "make up" 3 more locations in order for our bootstrap code to fit in the allocated ROM.

   1. Note that the instruction at the mailbox labelled "forloop" reloads the calculator with the value of "m"; this value is already in the calculator reguardless of which of the two paths were taken to get to this point. Therefore this instruction can be dropped.

   2. At the end of the "for" loop we have: "STO m" followed by "JMP forloop"; the instruction immediately prior to the one labelled "forloop" is a "STO m". By moving the "forloop" label back one instruction, the "STO m" from the end of the "for" loop can be dropped.

   3. The only place the "zero" constant is used is in the instruction sequence:
      
      "STO length", "LDA zero", "STO m"
      
      by replacing this with:
      
      "STO length", "SUB length", "STO m"
      
      we can delete the entry:
      
      "zero DAT 000"

   Thus we can successfully reduce our bootstrap code size to fit in the available ROM. However, this type of "optimization" reduces the readability of the code and should only be done in extreme situations (like this particular case). Most programmers never need to concern themselves with "optimizing" at this level.