The following article was printed in Julyy 1977 of the magazine „BYTE"1.
An interesting article about how to relocate machine code. But the problems involved may be solved more elegant with PRL (Page ReLocatable) files used by CP/M Plus.
A Machine Code Relocator
for the 8080
  When it became necessary to insert a routine between locations x and x+1 in memory, I found myself with two miserable options for manual patches.

Leor Zolman
362 Memorial Dr
Cambridge MA 02139

Many microcomputer hobbyists pass through an early stage in the development of their systems where machine language is the only mode available for programming. My system configuration at that point included an IMSAI mainframe and 4 K memory, a VDM-1 video driver and monitor, and a Tarbell cassette interface. The big problem when programming something like LIFE for the VDM in machine language occurs when it becomes necessary to insert a routine (call it routine y) between locations x and x+1 in memory. I found myself with two miserable options open:
  1. Replace three or so bytes (the exact number depending on where the new instruction begins, on byte 3, 4, or 5) with a patch to routine y, placed somewhere else in memory, then restore the lost bytes at the end of routine y and jump back to location x+4, or so. This is not exactly ideal.
  2. Manually relocate the program from location x+1 on down until the end of the program (unless you left plenty of NOPs to handle just such a situation then, when you're all finished, you're left with a bunch of useless NOPs!) to make room for routine y. This involves writing the whole thing out on paper first then toggling it in. Once again, far from optimal.

About the Author
Leor Zolman has been programming for years, including such applications as medical graphics for Cedars of Lebanon Hospital in his hometown of Los Angeles. He is currently working on a 2 K resident monitor for the 8080, and characterizes himself as a BASIC games enthusiast. Mr Zolman is 17 years old and a freshman at MIT.

My solution to this dilemma was to write a machine language program which performs the second type of relocation above quickly and painlessly when given just 11 bytes of relocation data as shown in table 1.

LabelNumber
of Bytes
AddressComments 
a20DDD,
0DDE
First address of block to be relocated
 
b20DDF,
0DE0
Last address of block to be relocated
 
c20DE1,
0DE2
Destination address (ie: where the byte at location a should go)
 
d20DE3,
0DE4
First address to have references fixed
 
e20DE5,
0DE6
Last address to have references fixed
 00 = fix references only
f10DE7Function select:01 = move block and fix references
 02 = move block only
Table 1: These six key pieces of information must be entered into the locations shown (beginning at hexadecimal 0DDD for listing 1) before relocation can be performed.

The program, which I call the "relocator," performs its duty in two phases. Phase 1 simply takes the block whose first address is a, and whose last address is b, then transfers it as is to the area beginning with address c. That's it for phase 1. If the function select byte is equal to 02, then the relocator quits here and goes into an infinite loop which shows up as a known pattern in the lights of an Altair or IMSAI front panel. This is an indicator of the end of execution.
Phase 2 is the tricky part. All addresses (meaning all 2 byte operands of 3 byte instructions) which fall between items a and b above (inclusive) must have added to them the distance (number of bytes) which the block was moved. This value is easily computed by the expression c-a. For example, if a ten byte block was moved from starting location 10 to decimal starting location 75, then the value 65 must be added to any 2 byte operand in the program having a value from 10 to 20 inclusive.
The purpose of items d and e in the relocation data is to tell the relocator where it must look for such operands (references), so that they may be altered or "fixed" accordingly. Since the references may lie anywhere within the program (not necessarily just within the relocated block) d should be set equal to the very first location of the program, and e should be set to the last. The exception to this, which occurs when a data block lies in the way, will be covered later. [To avoid the exception, the "good" programming practice of keeping data separate from executable code is highly recommended ...CH] Phase 2 may be executed without phase 1 if the function select is set to 0.
The beauty of this program becomes apparent when a friend having 32 K in his machine hands you a tape of a program he wrote residing somewhere up in the sky (or so it seems to you, with only 4 K) and you would like to run it. All you have to do in this case is:
  1. Load in the relocator
  2. Load in your friend's program in any free memory space
  3. Feed the relocator this relocation data:
    1. the original first address of the program
    2. the original last address of the program
    3. the location where you loaded it (first location)
    4. same as c
    5. c + length of the program (this equals c + b - a + 1)
    6. 00 (function select to fix references only)
  4. Examine the start of the relocator and hit run. When the LEDs stop flickering (about 1 second for each 1 K between d and e) hit stop. You should see C3 in the data LEDs of an Altair or IMSAI.
That's it! Now the program should run right where you loaded it, unless one of the following problems occurs.

Relocating to a Lower Memory Location

The block move (phase 1) is done tail first. For a block of length n, then, byte n of the source would be transferrcd to byte n of the destination, then byte n-1 would be moved, then n-2, etc. up to byte 1. Therefore, relocating forward into higher memory always works, but relocating backward into lower memory fails if the difference between the source and destination addresses is not greater than the block length. In such a case, say moving a block at b to location a, an intermediate relocation must be done from b to c (where |c-a| > length of block), and then a second relocation must be performed from c to a. Note: I could have had the relocator check the direction of the move and proceed either tail or head first accordingly, but the program is long enough to cause toggling headaches as it is.

Problems with the LXI instruction

LXI instructions in which the operand happens to equal an address in the block between a and b but doesn't actually refer to an address (LXI H, 0000 is a good example) present a problem. If you are in the process of writing the program try to use LHLD instead (or, if worse comes to worse, LHLD with MOV B, H and MOV C, L for LXI B, xxxx) and set aside two bytes of storage at the end of the program for the data.
If the program was not written by you, or if you really want to use LXI, then the only alternative is to go through your listing (if you have one!) and change the locations in question. But this problem never caused me much trouble.

Data Block Problems

Avoid relocating data whenever possible. If relocation is necessary do not try passing through it with phase 2. Here is an example of how to handle data areas: In a program residing from location d to location e, a block starting at a and eriding at b is to be moved to location c. As a complication, a data block resides from location f to location g. See figure 1 for a memory map of this situation. The relocation should be performed in two runs of the relocator as follows:

Figure 1: A special case in program relocation. The program block a thru b is to be moved to locarion c, but the integrity of the data block from f thru g must be preserved. The technique in this case is to change program references in two passes: up to, but not including, the data block, and then after the block. Locating all data at the end of programs will of course prevent this type of problem.
Run 1. Give relocation data of a, b, c, d, f-1, 1. This moves the block and fixes all references up to location f, the start of the data area.
Run 2. Give data of a, b, c, g+1, e, 0. This simpiy fixes up the remaining references after skipping the data area.
[Here again the practice of keeping data separate from executable code should alleviate this problem...CH]

In the listing provided the relocator resides at locations 0D00 to 0DFF, but it is self-relocatable. of course. The six key items of relocation data must be set up at locations 0DDD to 0DE7 as shown in table 1, with the low byte coming first numerically in each case.
I sincerely hope that this program repays your understanding und toggling efforts with a vast reduction in relocation frustration.
The value of this program becomes apparent when a friend having 32 K in his machine hands you a tape of a program he wrote residing somewhere up in the sky (or so it seems to you, with only 4 K) and you would like to run it.

1. In January 1980 a follow up article was published: "Relocating 8080 System Software"

Scanned by Werner Cirsovius
September 2012
© BYTE Publications Inc.