# bbbq VM — Instruction Set Reference

Reverse-engineered from the stripped Rust binary `bbbq` (IDA decompile `bbbq.c`, plus the
opcode jump table at file offset `0x3778`).

**Verification status:** every statement below is backed by disassembly *and* by
differential testing — 29 probe programs, each of which poisons its own output if the real
VM disagrees with this document, were run against the real binary and against a Python
model built from this document. All 29 return `"success":true` on the real binary and
produce identical behaviour in the model. See `probe.py`.

---

## 1. Program file format

Raw array of **little-endian `u32` instruction words**. No header, no magic, no metadata.

| Constraint | Violation behaviour |
|---|---|
| file size > 0 | `bbbq: empty input`, exit 2 |
| file size % 4 == 0 | `bbbq: ` (empty io error), exit 2 |

Word *i* of the file is instruction at `PC = i`. Program length (in words) is the PC bound.

---

## 2. Machine state

| Component | Type | Initial value |
|---|---|---|
| `Q0 Q1 Q2 Q3` | FIFO queues of `u64` (ring buffers, grow on demand) | empty |
| `ACC` | `u64` accumulator | 0 |
| `SCRATCH` | `Option<u64>`, a single hidden slot | `None` |
| `Z N C V` | flags | 0 |
| `EOF` | flag, set when the input stream is drained | 0 |
| `PC` | instruction index | 0 |
| `IN` | 256 × `u64`, read-once stream | seeded PRNG values |
| `OUT` | `Vec<u64>`, append-only | empty |

There is **no random-access memory** and **no general-purpose register file**. The four
queues plus `ACC` plus the one-slot `SCRATCH` are all the storage you get.

`Q0..Q3` are individually unbounded, but their **combined length must stay ≤ `0x0FFFFFFF`
(268 435 455)**; exceeding it halts with status 3.

---

## 3. Instruction encoding

```
 31    26 25 24 23 22 21                                    0
+--------+-----+-----+---------------------------------------+
| opcode |  q  |     |            immediate / offset          |
+--------+-----+-----+---------------------------------------+
         \-----  cond (4 bits, 25..22)  -----/
```

| Field | Bits | Extraction |
|---|---|---|
| `opcode` | 31..26 | `w >> 26` |
| `q` (queue index) | 25..24 | `(w >> 24) & 3` |
| `cond` | 25..22 | `(w >> 22) & 0xF` |
| `imm16` | 15..0 | `w & 0xFFFF` |
| `rel22` | 21..0 | `sign_extend_22(w & 0x3FFFFF)` |

`q` and `cond` overlap; each opcode uses exactly one of them.

### Reserved-bit enforcement

The VM **rejects any instruction with a non-zero reserved bit** (halt status 1). This is
strict — you cannot leave junk in unused fields.

| Group | Opcodes | Requirement |
|---|---|---|
| whole word | `0x00` | `w == 0` |
| queue operand | `0x01 0x02 0x0F 0x11 0x13–0x1F 0x22` | `w & 0x00FFFFFF == 0` |
| no operand | `0x0B 0x0E 0x10 0x28 0x29 0x2B 0x2C 0x2D 0x2E 0x3B` | `w & 0x03FFFFFF == 0` |
| imm16 | `0x0C 0x0D 0x12 0x20 0x21 0x23` | `(w >> 16) & 0x3FF == 0` |
| jump | `0x24` | `(w >> 22) & 0xF == 0` |
| cond branch | `0x25` | `1 ≤ cond ≤ 14` |
| queue branch | `0x26 0x27` | `(w >> 22) & 3 == 0` |
| eof branch | `0x2A` | `cond ∈ {1, 2}` |

Opcodes `0x03–0x0A`, `0x2F–0x3A` and `0x3C–0x3F` are **invalid** (`opcode > 0x3B` is
rejected by an explicit bound check).

### Branch target

```
PC_next = PC + rel22 + 1        (for a taken branch)
PC_next = PC + 1                (otherwise)
```

---

## 4. Instruction set

`a` = value popped first (queue front), `b` = value popped second.
**If the queue holds fewer than 2 elements the missing operand(s) read as `0`, and the
instruction still executes and still pushes a result.**

### Data movement

| Op | Mnemonic | Operand | Effect | Flags |
|---|---|---|---|---|
| `0x00` | `NOP` | — | nothing | — |
| `0x01` | `POP q` | q | `ACC = pop(Qq)` (0 if empty) | `Z N` |
| `0x02` | `PUSH q` | q | `Qq.push(ACC)` | — |
| `0x0B` | `CLR` | — | `ACC = 0` | `Z=1 N=0` |
| `0x0C` | `LDI imm16` | imm16 | `ACC = imm16` | `Z`, `N=0` |
| `0x0D` | `LDIH imm16` | imm16 | `ACC = (ACC << 16) \| imm16` | `Z`; `N` = sign of `ACC<<16` |
| `0x3B` | `SWAP` | — | `SCRATCH` empty → `SCRATCH = ACC; ACC = 0`; else `ACC = SCRATCH.take()` | — |

Build a 64-bit constant with `LDI hi16` followed by three `LDIH`.

### I/O

| Op | Mnemonic | Effect | Flags |
|---|---|---|---|
| `0x0E` | `IN` | `ACC = next input`; sets `EOF` when the last one is taken. If already drained: `ACC = 0` | `Z N` |
| `0x0F` | `INQ q` | `Qq.push(next input)`; no-op if drained; sets `EOF` | — |
| `0x10` | `OUT` | `OUT.push(ACC)` | — |
| `0x11` | `OUTQ q` | `OUT.push(pop(Qq))` | — |
| `0x12` | `OUTI imm16` | `OUT.push(imm16)` | — |
| `0x2E` | `VIN` | for `q` in 0..3: `Qq.push(next input)` if any remain (up to 4 values) | — |

### Queue ALU — pop two from `Qq`, push into a **fixed** destination queue

This is the defining quirk of the architecture: the *source* queue is encoded in the
instruction, but the *destination* queue is hardcoded per opcode.

| Op | Mnemonic | Result | Dest | Flags |
|---|---|---|---|---|
| `0x13` | `ADD q` | `sat_add(a, b)` | **Q0** | `C=V=1` on overflow |
| `0x14` | `SUB q` | `sat_sub(a, b)` (floor 0) | **Q1** | `C=V=1` on borrow |
| `0x15` | `MUL q` | `sat_mul(a, b)` | **Q0** | `C=V=1` on overflow |
| `0x16` | `DIV q` | `b == 0 ? 0 : a / b` | **Q1** | — |
| `0x17` | `MOD q` | `b == 0 ? 0 : a % b` | **Q1** | — |
| `0x18` | `AND q` | `a & b` | **Q0** | — |
| `0x19` | `OR q` | `a \| b` | **Q0** | — |
| `0x1A` | `XOR q` | `a ^ b` | **Q0** | — |
| `0x1B` | `SHL q` | `a << (b & 63)` | **Q1** | — |
| `0x1C` | `SHR q` | `a >> (b & 63)` logical | **Q1** | — |
| `0x1D` | `SAR q` | `a >> (b & 63)` arithmetic | **Q1** | — |

Saturation: `sat_add`/`sat_mul` clamp to `u64::MAX`, `sat_sub` clamps to `0`.

> **Trap.** These opcodes only ever *set* `C` and `V` (to 1) on overflow. They never clear
> them, and they never touch `Z` or `N`. Do not branch on flags after a queue-ALU op.

> **Trap.** `q = 0` on `ADD`/`MUL`/`AND`/`OR`/`XOR` means pop from Q0 and push back into
> Q0; `q = 1` on `SUB`/`DIV`/`MOD`/`SHL`/`SHR`/`SAR` likewise folds Q1 in place.

### Accumulator ALU

| Op | Mnemonic | Effect | Flags |
|---|---|---|---|
| `0x1E` | `ADDQ q` | `ACC = sat_add(ACC, pop(Qq))` | `Z N`, `C=V=`carry |
| `0x1F` | `SUBQ q` | `ACC = sat_sub(ACC, pop(Qq))` | `Z N`, `C=V=`borrow |
| `0x20` | `ADDI imm16` | `ACC = sat_add(ACC, imm16)` | `Z N`, `C=V=`carry |
| `0x21` | `SUBI imm16` | `ACC = sat_sub(ACC, imm16)` | `Z N`, `C=V=`borrow |
| `0x22` | `CMPQ q` | compare `ACC` with **front(Qq)** — a *peek*, nothing is popped (0 if empty) | `Z N C V` |
| `0x23` | `CMPI imm16` | compare `ACC` with `imm16` | `Z N C V` |

> **Trap — inconsistent carry convention.** `CMPQ`/`CMPI` use the ARM convention
> `C = (ACC >= operand)` (carry set means *no borrow*). `SUBQ`/`SUBI` use the **opposite**:
> `C = (ACC < operand)` (carry set means *borrow occurred*). Condition codes `CS/CC/HI/LS`
> therefore mean different things after `CMP` than after `SUB`. Use `CMP` for comparisons.

Flag definitions for `CMPQ`/`CMPI` (with `d = ACC - operand` computed wrapping):

```
Z = (ACC == operand)
C = (ACC >= operand)                                  # unsigned
N = d >> 63
V = ((operand ^ ACC) >> 63) & ((ACC ^ d) >> 63)       # signed overflow
```

### Vector ops (all four queues at once)

| Op | Mnemonic | Effect | Flags |
|---|---|---|---|
| `0x2B` | `VADD` | for `q` in 0..3: pop `a,b` from `Qq`, push `sat_add(a,b)` back into **`Qq`** | `C=V=1` on any lane overflow |
| `0x2C` | `VMUL` | same, with `sat_mul` | `C=V=1` on any lane overflow |
| `0x2D` | `VMAC` | for `q` in 0..3: pop `a,b` from `Qq`; `ACC = sat_add(ACC, sat_mul(a,b))` | `Z N` |

`VADD`/`VMUL` push a result into **every** queue, including empty ones (an empty queue
receives `0`). `VMAC` consumes but pushes nothing.

### Control flow

| Op | Mnemonic | Operand | Taken when |
|---|---|---|---|
| `0x24` | `JMP rel22` | rel22 | always |
| `0x25` | `B<cc> rel22` | cond 1..14, rel22 | see table |
| `0x26` | `BQZ q, rel22` | q, rel22 | `Qq` is **empty** |
| `0x27` | `BQNZ q, rel22` | q, rel22 | `Qq` is **non-empty** |
| `0x28` | `JMPA` | — | always; `PC = ACC` (absolute) |
| `0x29` | `HALT` | — | stops with status 0 |
| `0x2A` | `BEOF rel22` | cond = 1 | `EOF` set |
| `0x2A` | `BNEOF rel22` | cond = 2 | `EOF` clear |

Condition codes for `0x25` — the standard ARM set:

| cond | name | taken when |
|---|---|---|
| 1 | `EQ` | `Z` |
| 2 | `NE` | `!Z` |
| 3 | `CS` | `C` |
| 4 | `CC` | `!C` |
| 5 | `MI` | `N` |
| 6 | `PL` | `!N` |
| 7 | `VS` | `V` |
| 8 | `VC` | `!V` |
| 9 | `HI` | `!Z && C` |
| 10 | `LS` | `Z \|\| !C` |
| 11 | `GE` | `N == V` |
| 12 | `LT` | `N != V` |
| 13 | `GT` | `!Z && N == V` |
| 14 | `LE` | `Z \|\| N != V` |

---

## 5. Halt statuses

Checked after every instruction. Only status 0 can ever produce `"success":true`.

| Status | Cause |
|---|---|
| 0 | `HALT` (`0x29`) executed — clean |
| 1 | invalid opcode, or a reserved bit was non-zero |
| 2 | `PC >= program_length` (fell off the end, or a bad `JMPA`) |
| 3 | combined queue length exceeded `0x0FFFFFFF` |
| 4 | instruction count reached `2^32` |

The binary never tells you which status you hit — every failure prints the same
`"bad input"`. Build your own emulator.

---

## 6. Worked example

Selection sort of the 256 input values, ~285 words. `Q0` = working set, `Q1` = scratch
ring, `Q2` = current minimum (1 element), `Q3` = "already removed" flag.

```
    INQ 0                       ; ×256, load the whole input stream into Q0
outer:
    BQZ  0, end                 ; Q0 empty -> done
    LDI  0xFFFF                 ; min := u64::MAX
    LDIH 0xFFFF
    LDIH 0xFFFF
    LDIH 0xFFFF
    PUSH 2
p1:                             ; pass 1: rotate Q0 -> Q1, tracking the min in Q2
    BQZ  0, p2
    POP  0
    CMPQ 2                      ; peek at min, do not disturb it
    BCS  p1keep                 ; ACC >= min -> keep
    SWAP                        ; stash v, ACC = 0
    POP  2                      ; drop the old min
    SWAP                        ; restore v
    PUSH 2                      ; min := v
p1keep:
    PUSH 1
    JMP  p1
p2:                             ; pass 2: Q1 -> Q0, dropping exactly one copy of min
    BQZ  1, emit
    POP  1
    BQNZ 3, p2keep              ; already removed one -> keep
    CMPQ 2
    BNE  p2keep
    PUSH 3                      ; mark removed, drop this value
    JMP  p2
p2keep:
    PUSH 0
    JMP  p2
emit:
    OUTQ 2                      ; emit the minimum
    POP  3                      ; clear the flag
    JMP  outer
end:
    HALT
```

Cost: ~405 000 instructions. Confirmed `"success":true` against the real binary on
multiple seeds.

---

## 7. Tooling

| File | Purpose |
|---|---|
| `bq.py` | assembler (mnemonic helpers + label resolution) and a cycle-accurate emulator implementing this document, including the scoring model |
| `gen.py` | builds `sort.bbbq` — the selection sort above |
| `gen2.py` | builds `stuff.bbbq` — sort plus a queue-stuffing phase, takes the target queue length as an argument |
| `probe.py` | the 29-probe differential test suite that verified this document |