Position-Independent Code

Position-independent code runs correctly wherever it is loaded. It never names its own addresses: every jump inside it is a branch relative to the program counter, and every reference to its own data is worked out from the program counter at run time. Copy the same bytes to any address and they still work.

On most 8-bit machines that was a nuisance to achieve and rarely needed. One processor was designed around it. When Terry Ritter and Joel Boney, two of the architects of Motorola’s 6809, explained the chip in BYTE in January 1979, position independence was the first item on their list of what the industry needed, and “one of the highest priority design goals”.

The problem: ROMs that only fitted one machine

Ritter and Boney’s argument was about selling software in ROM. A ROM written for one computer was tied to that computer’s memory layout:

It is very difficult to use a read only memory in any other context than that for which it was originally developed. It is hard to use the same read only memory on systems built by different vendors. Simply having different input and output (IO) or using a different memory location is usually enough to make the read only memory product useless.

Their answer began “1. Position independent code”, followed by temporary variables on the stack, input and output through pointers on the stack, and indirect jumps for system branch tables. The February instalment gave the commercial reason in two sentences: “Only read only memories which may be used in arbitrary target systems are economically viable in the context of mass production. And only these read only memories can result in low cost firmware for us all.”

How the 6809 does it

The 6800 before it had only short relative branches, “limited position independent code capabilities for small programs”. The 6809 added a 16-bit long form of every branch, and program-counter-relative addressing for every instruction that reads or writes memory: “Program relative addressing uses the program counter much as indexing uses one of the indexable registers.” The last gap was getting the address of a table into a register, which on other processors meant loading an absolute number. The 6809’s LEA (load effective address) instructions close it “with one instruction”. Ritter and Boney reported that LEA was “the most used new 6809 instruction by far” in their benchmarks.

Motorola’s 1981 programming manual turned the design into a rule: “NEVER USE ABSOLUTE ADDRESSING.” The assembler stores the distance from the instruction to the label, and “during execution, the processor adds the value of the run time PC to the distance to get a position-independent absolute address”:

start   leax    table,pcr   ; X = run-time address of table
        lda     2,x         ; A = third entry, wherever the code was loaded
        rts
table   fcb     10,20,30,40

Assembled at $1000 or at $7F00, those 11 bytes come out identical: 30 8D 00 03 is “X = address of the next instruction + 3”. Replace the first line with ldx #table and the two assemblies differ, because the absolute address of table is now written into the code.

The manual’s one concession is hardware. “Some absolute locations are usually required, particularly for I/O”, so it recommends a small setup routine that pushes the device addresses onto the stack, after which every other module does its input and output through that pointer. Its price for the whole discipline: position-independent code “is usually 5 to 10% slower than normal code”.

OS-9: loaded wherever there is room

Microware’s OS-9 for the 6809 made the rule compulsory. Its kernel loaded each program module into whatever memory was free and gave it a separate data area, reached through the U register. Stephen Childress explained it to MICRO readers in 1983: an OS-9 module “may be placed anywhere in memory and executed without link-loading or other preparatory adjustments, thanks to the 6809’s powerful addressing”, and the familiar LDX #MSG had to become LEAX MSG,PCR, because the address in the listing “is just the address shown in the listing, not the address at which MSG falls”. That November he summed it up: a program is “loaded into memory wherever space exists (all code is position independent in OS-9)”. Because the code never changes and each user gets their own data area, two users could share one copy of a program such as BASIC09.

Radio Shack sold OS-9 for the 64K Color Computer at $69.95. Color Micro Journal’s review in October 1983 listed “Position Independent” among the new terms a buyer would meet, and noted a manual chapter on “how to write Position-Independent Code, Addressing Variables and Data Structures (which are almost NEVER at a fixed Memory Address location)”. Dragon Data’s version followed for the Dragon 64, which had the memory OS-9 needed; Dragon User’s April 1984 review explained that it supports “position-independent-code (PIC)” so that routines can “run at any point in memory”.

On the 6502: branches and a stack trick

The 6502 has relative conditional branches with a reach of about 128 bytes, and nothing else: JMP and JSR take absolute addresses, and no instruction reads data relative to the program counter. Position-independent 6502 code is possible, but the programmer has to build it.

Apple needed it anyway. Each Apple II expansion slot has its own 256-byte page for the card’s ROM, at $Cn00 for slot n, so the same card’s firmware appears at a different address depending on where it is plugged in. The Apple II Reference Manual asked card designers to make that firmware “portable”: “They should contain no absolute references to themselves. They should perform all JMPs with conditional or forced branches.” A forced branch is a conditional one whose condition is known to be true, such as CLC followed by BCC. The manual then shows how a card can find out where it is:

        jsr $FF4A       ; IOSAVE: save the registers
        sei             ; no interrupts while we look at the stack
        jsr $FF58       ; IORTS: the monitor's bare RTS
        tsx
        lda $0100,x     ; high byte of the return address just used: $Cn
        sta $07F8
        and #$0F
        tay             ; Y = slot number

$FF58 is a single RTS in the monitor ROM, listed in What’s Where in the Apple as “JSR HERE TO FIND OUT WHERE ONE IS”. The call leaves its return address in the stack page, and the RTS does not erase it, so the code reads back the high byte of its own address. Code running from slot 4’s page gets $C4. Card firmware that skipped this work was allowed, but “your only loss would be that the peripheral card would be slot-dependent”.

Hobbyists published routines in the same spirit. MICRO’s July 1980 issue carried Christopher Flynn’s file-handling subroutine for the AIM 65, “completely position-independent and ROMable”: “you can put it anywhere in memory that you like. You will not have to change a single byte of code.”

The 68000 and the Amiga

The 68000 has program-counter-relative modes for reading, which make tables in ROM easy to reach: “Data items in the instruction stream can be accessed with the program counter relative addressing modes”. Motorola’s reference manual classes those modes as not “alterable”, so a program can read through the program counter but cannot write through it.

The Amiga took the other route. AmigaDOS program files carry relocation tables: a hunk_reloc32 block lists every longword in the code that holds an address, and the loader adds the hunk’s real base address to each one as it loads the program. The code itself can then use absolute addresses freely, at the cost of a fix-up pass each time it is loaded.

See also

• Motorola 6809
• Self-modifying code: the opposite habit, which ROM code and OS-9’s shared modules ruled out
• Bank switching
• TRS-80 Color Computer
• Dragon 64
• Apple II