Apollo 11 AGC Interpreter — Kompletní technický popis

INTERPRETER.agc je srdcem softwaru Apollo 11. Jedná se o virtuální stroj (VM) implementovaný v 3 076 řádcích assembly kódu, který rozšiřuje 11-instrukční AGC hardware na plnohodnotný vědecký kalkulátor schopný vektorové algebry, maticových operací a trigonometrie.

1. Proč byl interpret nutný?

AGC Block II měl pouze 11 základních instrukcí (TC, CCS, CA, CS, TS, AD, MASK, XCH, DCA, DCS, INDEX) plus 23 rozšířených (EXTEND + MP, DV, SU, RAND, WAND, ROR, WOR, RXOR, QXCH, DXCH, LXCH, AUG, DIM, DAS, BZF, MSU, BZMF, READ, WRITE, EDRUPT, SQUARE).

Pro navigaci ve vesmíru potřebujete:

Vektorový křížový součin (cross product)
Skalární součin (dot product)
Násobení matice vektorem
Odmocninu, sinus, cosinus, arcsin, arccos
Polynomiální evaluaci

Řešení: vybudovat virtuální stroj s vlastní instrukční sadou, adresovým prostorem a zásobníkem.

2. Architektura — Řídící smyčka (Dispatch Loop)

Vstupní bod

INTPRET     RELINT                      # Povolení přerušení
            EXTEND
            QXCH    LOC                 # LOC = program counter VM
 +2         CA      BBANK              # Nastavení banku
            TS      BANKSET
            MASK    BIT15
            TS      INTBIT15            # Pro indexovatelné adresy
            TS      EDOP                # Vynulování zbylého op-kódu
            TCF     NEWOPS              # Začít dekódování

Hlavní smyčka — DANZIG

DANZIG je název hlavní dispatch smyčky (pojmenované po městě Gdaňsk). Každá instrukce po dokončení skočí zpět na DANZIG:

DANZIG      CA      BANKSET             # Obnovit BBANK
            TS      BBANK

NOIBNKSW    CCS     EDOP                # Zbývá op-kód z minulého páru?
            TCF     OPJUMP              # Ano → vykonat
                                        # (EDOP se vynuluje při editaci)
            CCS     NEWJOB              # ★ KOOPERATIVNÍ MULTITASKING ★
            TCF     CHANG2              # Vyšší priorita → přepnout kontext

            INCR    LOC                 # Posunout program counter

NEWOPS      INDEX   LOC                 # Načíst slovo na LOC
            CA      0                   # Může být op-kód pár nebo store kód
            CCS     A                   # Test znaménka
            TCF     DOSTORE             # Kladné → store instrukce

Kooperativní multitasking: Na řádku CCS NEWJOB interpret kontroluje, zda existuje úloha s vyšší prioritou. Pokud ano, přeruší interpretaci a přepne kontext. To je klíčové — interpret dobrovolně odevzdává řízení mezi každou dvojicí instrukcí.

3. Kódování instrukcí — Dva op-kódy v jednom slově

AGC slovo má 15 bitů. Interpret balí dva op-kódy do jednoho slova:

Bit 15 (znaménko): 0 = op-kód pár, 1 = store kód
Bity 8-14:         Levý op-kód (7 bitů)
Bity 1-7:          Pravý op-kód (EDOP)

Dekódování:

NEWOPS      INDEX   LOC
            CA      0                   # Načíst slovo
            CCS     A                   # Kladné = op-kód pár
            TCF     DOSTORE             # Záporné = store kód

            TS      EDOP                # Uložit pravý op-kód do EDOP
            MASK    LOW7                # Izolovat pravý (pro pozdější CCS)

OPJUMP      TS      CYR                # Rotace přes CYR registr
            CCS     CYR                 # Test prefix bitů → dispatch
            TCF     OPJUMP2             # Další test
            TCF     EXIT                # +0 = EXIT

Prefixové bity řídí typ instrukce:

Prefix	Typ	Příklady
`01xxx`	Adresovatelné operace	VLOAD, DAD, DSU, DMP, VXV, DOT
`10xxx`	Misc/index/branch	GOTO, CALL, BZE, BMN, BOV, SET
`11xxx`	Unární/shift	SQRT, SIN, COS, COMP, UNIT, ABS
`00000`	EXIT	Návrat do nativního kódu

4. Kompletní instrukční sada

4.1 Adresovatelné instrukce (INDJUMP tabulka)

INDJUMP     TCF  VLOAD      # 00 — Načíst vektor do MPAC
            TCF  TAD        # 01 — Triple-precision sčítání
            TCF  SIGN       # 02 — Podmíněný komplement
            TCF  VXSC       # 03 — Vektor × skalár
            TCF  CGOTO      # 04 — Computed GOTO
            TCF  TLOAD      # 05 — Načíst triple-precision
            TCF  DLOAD      # 06 — Načíst double-precision
            TCF  V/SC       # 07 — Vektor ÷ skalár
            TCF  SLOAD      # 10 — Načíst single-precision
            TCF  SSP        # 11 — Store single-precision
            TCF  PDDL       # 12 — Push-down + DP load
            TCF  MXV        # 13 — Matice × vektor
            TCF  PDVL       # 14 — Push-down + vektor load
            TCF  CCALL      # 15 — Computed CALL
            TCF  VXM        # 16 — Vektor × matice
            TCF  TSLC       # 17 — Normalize (shift left & count)
            TCF  DMPR       # 20 — DP multiply & round
            TCF  DDV        # 21 — DP dělení
            TCF  BDDV       # 22 — DP dělení (obrácené)
            TCF  GSHIFT     # 23 — Obecný shift
            TCF  VAD        # 24 — Vektorové sčítání
            TCF  VSU        # 25 — Vektorové odčítání
            TCF  BVSU       # 26 — Vektorové odčítání (obrácené)
            TCF  DOT        # 27 — Skalární součin
            TCF  VXV        # 30 — Vektorový součin (cross product)
            TCF  VPROJ      # 31 — Vektorová projekce
            TCF  DSU        # 32 — DP odčítání
            TCF  BDSU       # 33 — DP odčítání (obrácené)
            TCF  DAD        # 34 — DP sčítání
            TCF  (volné)    # 35 — Nepoužito
            TCF  DMP1       # 36 — DP násobení
            TCF  SETPD      # 37 — Nastavit push-down pointer

4.2 Unární instrukce (UNAJUMP tabulka)

UNAJUMP     TCF  SQRT       # 01 — Odmocnina
            TCF  SINE       # 02 — Sinus
            TCF  COSINE     # 03 — Cosinus
            TCF  ARCSIN     # 04 — Arcus sinus
            TCF  ARCCOS     # 05 — Arcus cosinus
            TCF  DSQ        # 06 — DP čtverec
            TCF  ROUND      # 07 — Zaokrouhlení na DP
            TCF  COMP       # 10 — Komplement (vektor/skalár)
            TCF  VDEF       # 11 — Definice vektoru
            TCF  UNIT       # 12 — Jednotkový vektor
            TCF  ABVALABS   # 13 — Absolutní hodnota / délka vektoru
            TCF  VSQ        # 14 — Čtverec délky vektoru
            TCF  STADR      # 15 — Push-up na store kód
            TCF  RVQ        # 16 — Return via QPRET
            TCF  PUSH       # 17 — Push MPAC na zásobník

4.3 Misc/branch instrukce (MISCJUMP)

MISCJUMP    TCF  AXT        # 00 — Address → index (true)
            TCF  AXC        # 01 — Address → index (complemented)
            TCF  LXA        # 02 — Load index z erasable
            TCF  LXC        # 03 — Load index (complemented)
            TCF  SXA        # 04 — Store index do erasable
            TCF  XCHX       # 05 — Exchange index s erasable
            TCF  INCR       # 06 — Increment index
            TCF  TIX        # 07 — Branch & decrement on index
            TCF  XAD        # 10 — Add erasable k indexu
            TCF  XSU        # 11 — Subtract erasable od indexu
            TCF  BZE/GOTO   # 12 — Branch if zero / Goto
            TCF  BPL/BMN    # 13 — Branch plus / Branch minus
            TCF  RTB/BHIZ   # 14 — Return to basic / Branch hi zero
            TCF  CALL/ITA   # 15 — Call / Store QPRET
            TCF  SW/        # 16 — Switch instrukce
            TCF  BOV(B)     # 17 — Branch on overflow

4.4 Switch instrukce (16 variant)

# 00  BONSET    Set switch + GOTO if was ON
# 01  SETGO     Set switch + GOTO
# 02  BOFSET    Set switch + GOTO if was OFF
# 03  SET       Set switch
# 04  BONINV    Invert + branch if was ON
# 05  INVGO     Invert + GOTO
# 06  BOFINV    Invert + branch if was OFF
# 07  INVERT    Invert switch
# 10  BONCLR    Clear + branch if was ON
# 11  CLRGO     Clear + GOTO
# 12  BOFCLR    Clear + branch if was OFF
# 13  CLEAR     Clear switch
# 14  BON       Branch if ON
# 16  BOFF      Branch if OFF

5. Registry interpretu

MPAC — Multi-Purpose Accumulator

MPAC je 7-registrový akumulátor (7 × 15 bitů = 105 bitů):

Registr	Skalární mód (DP)	Skalární mód (TP)	Vektorový mód
`MPAC`	Major part	Major	X major
`MPAC+1`	Minor part	Middle	X minor
`MPAC+2`	(zero/mode)	Minor	(nepoužit)
`MPAC+3`	—	—	Y major
`MPAC+4`	—	—	Y minor
`MPAC+5`	—	—	Z major
`MPAC+6`	—	—	Z minor

MODE registr

MODE = +1  →  Triple precision (3 slova)
MODE =  0  →  Double precision (2 slova)
MODE = -1  →  Vektor (6 slov)

Další klíčové registry

Registr	Funkce
`LOC`	Program counter interpretu
`BANKSET`	Uložený BBANK pro bank-switching
`INTBIT15`	Bit 15 FBANK pro adresování
`EDOP`	Uložený pravý op-kód z páru
`ADDRWD`	Dekódovaná adresa operandu
`PUSHLOC`	Pointer push-down zásobníku
`FIXLOC`	Bázová adresa VAC oblasti (work area)
`QPRET`	Návratová adresa (obdoba RET/LR)
`X1`, `X2`	Indexové registry
`S1`, `S2`	Dekrement registry pro TIX
`OVFIND`	Indikátor přetečení

6. Push-down zásobník

Interpret má vlastní zásobník pro mezivýsledky. PUSHLOC ukazuje na aktuální vrchol zásobníku ve VAC oblasti (work area):

PUSH        EXTEND                      # Push MPAC dolů bez změny
            DCA     MPAC
            INDEX   PUSHLOC
            DXCH    0                   # Uložit na zásobník
            INDEX   MODE
            CAF     NO.WDS              # 2 (DP), 3 (TP), 6 (vektor)
            ADS     PUSHLOC             # Posunout pointer

Push-up (automatický): Pokud instrukce nemá explicitní adresu, automaticky vezme operand ze zásobníku:

PUSHUP      CAF     OCT23               # Test, zda instrukce vyžaduje
            MASK    CYR                  # speciální push-up mód
            ...
REGUP       INDEX   MODE
            CS      NO.WDS              # Dekrementovat PUSHLOC
 +2         ADS     PUSHLOC              # podle módu (2/3/6 slov)
            TS      ADDRWD               # Nastavit adresu operandu

Díky push-up/push-down mechanismu mohl programátor psát výrazy ve stylu RPN (Reverse Polish Notation) — podobně jako kalkulátory HP. Například výpočet (A × B) + (C × D) by vypadal jako:
DLOAD   A       # MPAC = A
DMP     B       # MPAC = A*B
PUSH            # Zásobník: [A*B]
DLOAD   C       # MPAC = C
DMP     D       # MPAC = C*D
DAD             # MPAC = C*D + A*B (automatický push-up)

7. Klíčové algoritmy

7.1 DP násobení (DMPSUB) — 49 MCT

Rozklad 30-bit × 30-bit na čtyři 15-bit násobení:

    A_hi × B_lo  →  MPAC+1, MPAC+2 (akumulace)
    B_hi × A_lo  →  MPAC+1, MPAC+2 (akumulace)
    A_hi × B_hi  →  MPAC,   MPAC+1 (akumulace)
    A_lo × B_lo  →  (zahozen nízký řád)

Časování: 49 MCT = 0.573 ms (komentář v kódu)

7.2 DP dělení (DDV/BDDV)

Nejkomplexnější algoritmus v celém interpretu (~250 řádků). Postup:

Normalizace: Posuv dělitele doleva, dokud major part ≥ 0.5
Sign handling: Nucení obou operandů na kladné
Hlavní dělení: Využití DV nativní instrukce pro kvocient Q a zbytek R
Korekce: Aproximace (A + sB)/(C + sD) ≈ Q + s(R - QD)/C kde s = 2^(-14)
MAXDV: Speciální případ když se major parts rovnají

# Komentář z kódu (řádky 1968-1974):
# A + SB       (R - QD)
# ------ = Q + S(------) WHERE Q AND R ARE QUOTIENT AND REMAINDER
# C + SD        (  C   )

7.3 Odmocnina (SQRTSUB)

Využívá Newtonovu metodu (Heron’s method) s lineární počáteční aproximací:

Normalizace: Posuv argumentu, aby spadal do rozsahu [0.125, 0.5]
Lineární aproximace X0:

   X0 = SLOPEHI × MPAC + BIASHI    # pro argument ∈ [0.25, 0.5]
   X0 = SLOPELO × MPAC + BIASLO    # pro argument ∈ [0.125, 0.25]

Dvě iterace Newtonovy metody:

   X1 = X0/2 + (MPAC/2) / (X0/2)
   X2 = X1/2 + (MPAC/2) / X1       # DP dělení pro přesnost

Denormalizace: Zpětný posun výsledku

Konstanty přesně odpovídají optimální lineární aproximaci pro daný rozsah:

SLOPEHI     DEC     .5884           # Sklon pro [0.25, 0.5]
BIASHI      DEC     .4192 B-1       # Offset pro [0.25, 0.5]
SLOPELO     DEC     .8324           # Sklon pro [0.125, 0.25]
BIASLO      DEC     .2974 B-1       # Offset pro [0.125, 0.25]

7.4 Trigonometrie — SIN/COS

Sinus využívá Hastingsovu polynomiální aproximaci 4. stupně (celkově 9. stupně — polynom je vyhodnocen s argumentem x², pak vynásoben x):

sin(πx) ≈ x × (c₀ + c₁x² + c₂x⁴ + c₃x⁶ + c₄x⁸)

Koeficienty (řádky 2677-2685):

Koeficient	Hodnota
c₀	+0.3926990796 (≈ π/8)
c₁	-0.6459637111
c₂	+0.318758717
c₃	-0.074780249
c₄	+0.009694988

Cosinus využívá identitu: cos(x) = sin(π/2 - |x|):

COSINE      TC      BRANCH          # Test znaménka
            ...
            EXTEND
            DCS     MPAC            # Negace
            DXCH    MPAC
PRESINE     CAF     QUARTER         # Přičíst π/2
            ADS     MPAC

7.5 ARCSIN/ARCCOS

Arcus cosinus využívá Hastingsovu aproximaci 7. stupně:

arccos(x) = √(1-x) × P(x)

kde P(x) je polynom stupně 7 s koeficienty 2^i × C_i / (π√2).

Arcus sinus pak využívá identitu: arcsin(x) = π/2 - arccos(x)

7.6 Vektorový součin (VXV)

Cross product M × X = (M₃X₂ - M₂X₃, M₁X₃ - M₃X₁, M₂X₁ - M₁X₂) implementovaný jako 6 DP násobení s akumulací:

VXV         # 1. M₃ × X₁
            # 2. -(M₂ × X₁) → save
            # 3. -(M₃ × X₂) → Y partial
            # 4. M₁ × X₂    → add to Z
            # 5. -(M₁ × X₃) → add to Y
            # 6. M₂ × X₃    → add to X

7.7 Matice × Vektor (MXV/VXM)

Implementováno jako 3 dot producty s posuvem adresy:

VXM/MXV     TC      MPACVBUF        # Uložit vektor do VBUF
            TC      DOTSUB          # X složka = dot(row1, vec)
            ...přeházení...
            TC      DOTSUB          # Y složka = dot(row2, vec)
            ...přeházení...
            TC      DOTSUB          # Z složka = dot(row3, vec)

Rozdíl MXV vs VXM: MATINC = 2 (řádkové vektory) vs MATINC = -10, DOTINC = 6 (sloupcové vektory).

8. Adresovací módy

Mód	Popis	Příklad
Přímý	14-bit adresa za instrukcí	`DLOAD X`
Indexovaný	Adresa ± index registr	`DLOAD* X,1`
Push-up	Automaticky ze zásobníku	`DAD` (bez adresy)
Work area	Relativně k FIXLOC (adresy 0-44)	`STORE 20D`
General erasable	E-bank switched	`DLOAD THETAD`
Fixed	F-bank switched	`CALL ROUTINE`

9. Store kódy

Pokud interpretované slovo je záporné (bit 15 = 1), je dekódováno jako store kód:

STORE       — Ulož MPAC, pokračuj normálně
STODL       — Ulož MPAC, znovu načti DP
STOVL       — Ulož MPAC, znovu načti vektor
STCALL      — Ulož MPAC, proveď CALL
STORE,1     — Ulož s indexem X1
STORE,2     — Ulož s indexem X2

10. Výkon a kompromisy

Metrika	Hodnota
Režie dispatche	~15 MCT (0.175 ms) na instrukci
DP násobení	49 MCT (0.573 ms)
DP dělení	~100-150 MCT (1.2-1.8 ms)
SQRT	~200 MCT (2.3 ms)
SIN/COS	~250 MCT (2.9 ms)
Dot product	~160 MCT (1.9 ms)
Cross product	~350 MCT (4.1 ms)
Zpomalení vs nativní	~8-12×
Úspora kódu	Interpretivní program je ~3-5× kratší

Klíčový kompromis: Interpret byl ~10× pomalejší než nativní kód, ale programy byly 3-5× kratší. S pouhými 36 864 slovy ROM to byl rozhodující faktor — bez interpretu by se navigační software do paměti prostě nevešel.

11. Příklad interpretivního programu

Takhle vypadal typický interpretivní kód pro výpočet navigačních dat:

# Z LUNAR_LANDING_GUIDANCE_EQUATIONS.agc:
            TC      INTPRET         # Vstup do interpretu
            VLOAD   RN              # Načíst pozici
            STOVL   LAND            # Uložit, načíst rychlost
                    VN
            STORE   LANDVT          # Uložit rychlost
            UNIT                    # Jednotkový vektor pozice
            STODL   UNIT/R/         # Uložit, načíst čas TTF
                    TTF/8
            DMP     LEADTIME        # Násobení lead-time
            DAD     PIPTIME         # Přičtení PIP času
            STCALL  TDEC1           # Uložit a zavolat integraci
                    INTEGRV
            EXIT                    # Návrat do nativního kódu

Tento kód by v čistém nativním assembly zabral 4-5× více instrukcí a byl by mnohem hůře čitelný.

12. Shrnutí architektury

graph TD
    A[Nativní AGC kód<br/>TC INTPRET] --> B[INTPRET<br/>Inicializace LOC, BANKSET]
    B --> C[DANZIG<br/>Hlavní dispatch smyčka]
    C --> D{NEWJOB?}
    D -->|Vyšší priorita| E[CHANG2<br/>Context switch]
    D -->|Ne| F[NEWOPS<br/>Načíst op-kód pár]
    F --> G{Store kód?}
    G -->|Ano| H[DOSTORE<br/>+ případný reload]
    G -->|Ne| I[OPJUMP<br/>Dekódovat prefix]
    I --> J{Prefix}
    J -->|01| K[INDJUMP<br/>Adresovatelné ops]
    J -->|10| L[MISCJUMP<br/>Branch/misc ops]
    J -->|11| M[UNAJUMP<br/>Unární ops]
    J -->|00| N[EXIT<br/>Návrat do nativního kódu]
    K --> C
    L --> C
    M --> C
    H --> C

Interpret AGC je historicky jedním z prvních virtuálních strojů v produkčním nasazení — předchůdce dnešní Java Virtual Machine, Python bytecodu nebo WebAssembly. Byl navržen Margaret Hamilton a jejím týmem na MIT Instrumentation Laboratory a je dokladem toho, že principy softwarového inženýrství, které používáme dodnes, mají kořeny v programu Apollo.