Encode a Small Run-length Block in BBC Micro BASIC

A long stretch of the same tile is a good candidate for run-length coding. A stretch of different tiles is not: each value needs its own count too. This encoder measures the runs first, so even the worst case cannot spill into the next array.

Include and initialise

Reserve B(8) for input, R(16) for output, public W/E/O/N/C and private I/J/K/V. Reserve numbered lines 3000–3300, combine routines.bas and your caller using build.py and put END, STOP or a jump before the helper. Use GOSUB on C64/BBC and GO SUB on Spectrum. Do not use private scratch as an outer loop variable.

Call 3000 at a new-block boundary. It clears input and output arrays and all public fields. Supply input after init. N selects the first zero to eight B elements; C supplies actual allocated output capacity, from zero to sixteen.

Encode a complete block

Call 3100. Success returns O=1,E=0 and even output length W. R(1)..R(W) contains positive count/value pairs. Equal adjacent values become one run; separate runs with the same value remain separate. Bytes after W are preserved.

Invalid N/C or a selected source value returns W=0,E=1,O=0. Valid input that needs more than C bytes returns W=0,E=2,O=1. Both failures preserve every output element. O=1 alone does not mean encoding succeeded: check E as well. Empty input succeeds with W=0, including C=0. Unselected source elements are ignored.

The reusable routine

Reusable numbered routines

3000 LET W=0: LET E=0: LET O=0: LET N=0: LET C=0
3010 FOR I=1 TO 8: LET B(I)=0: NEXT I
3020 FOR I=1 TO 16: LET R(I)=0: NEXT I: RETURN
3100 LET W=0: LET E=1: LET O=0
3110 IF N<0 OR N>8 OR N<>INT (N) THEN RETURN
3120 IF C<0 OR C>16 OR C<>INT (C) THEN RETURN
3130 IF N=0 THEN LET E=0: LET O=1: RETURN
3140 FOR I=1 TO N
3150 IF B(I)<0 OR B(I)>255 OR B(I)<>INT (B(I)) THEN RETURN
3160 NEXT I: LET K=1
3170 IF N=1 THEN GOTO 3210
3180 FOR I=2 TO N
3190 IF B(I)<>B(I-1) THEN LET K=K+1
3200 NEXT I
3210 LET O=1: LET E=2
3220 IF 2*K>C THEN RETURN
3230 LET E=0: LET I=1
3240 LET V=B(I): LET J=I+1
3250 IF J>N THEN GOTO 3280
3260 IF B(J)<>V THEN GOTO 3280
3270 LET J=J+1: GOTO 3250
3280 LET R(W+1)=J-I: LET R(W+2)=V: LET W=W+2: LET I=J
3290 IF I<=N THEN GOTO 3240
3300 RETURN

The first pass counts runs and checks twice that number against C. Only then does the second pass emit pairs. This extra scan buys an all-or-nothing destination contract. N never exceeds eight, so a run count cannot overflow its byte representation.

Encode and retry safely

The normal caller encodes AAABBCCC into 3,65,2,66,3,67, then tries an undersized destination and confirms the earlier output survives. It also covers empty and single-value requests. Source and input parameters remain available after each call.

Example calls from the maintained caller

100 GOSUB 3000: LET AA=0: LET BB=0
110 LET B(1)=65: LET B(2)=65: LET B(3)=65: LET B(4)=66
120 LET B(5)=66: LET B(6)=67: LET B(7)=67: LET B(8)=67
130 FOR JJ=1 TO 16: LET R(JJ)=99: NEXT JJ
140 LET N=8: LET C=16: GOSUB 3100: GOSUB 2000
150 IF W=6 THEN LET AA=1
160 LET BB=1
170 IF R(1)<>3 THEN LET BB=0
180 IF R(2)<>65 THEN LET BB=0
190 IF R(3)<>2 THEN LET BB=0
200 IF R(4)<>66 THEN LET BB=0
210 IF R(5)<>3 THEN LET BB=0
220 IF R(6)<>67 THEN LET BB=0
230 LET C=1: GOSUB 3100: GOSUB 2000
240 LET N=0: LET C=0: GOSUB 3100: GOSUB 2000
250 LET N=1: LET C=2: GOSUB 3100: GOSUB 2000
260 PRINT "RUN RESULTS";AA;BB
270 ?(MB+995)=AA: ?(MB+996)=BB: ?(MB+997)=GD: ?(MB+998)=WC-256*INT (WC/256): ?(MB+999)=INT (WC/256): ?(MB+1000)=239: STOP

The complete trace observes every field and output element after each request. The diagnostic’s line 2000, AA/BB, JJ/KK (Z/Q on Spectrum) and mailbox can be removed from a game. Your caller owns B/N/C/R and checks W/E/O after calling 3100.

Customise the source

The custom caller uses eight distinct values. That expands eight input cells into sixteen encoded bytes, the worst case here. Allocate for that bound unless you are prepared to reject incompressible input. Repetition can reduce encoded length; it does not remove the need to reserve enough destination space.

There is no file header, terminator or literal-packet scheme. This remains a small local count/value example. Bigger blocks need wider limits and updated tests. Precompressing immutable assets in the build avoids runtime encoding cost; live map edits or generated records may justify doing it in the game.

Mistake and repair

The wrong caller passes C=0 for nonempty input, confusing available capacity with the number of bytes currently filled. The encoder safely refuses the request and preserves all sixteen old output values. Both saved checks fail because no expected record was produced. The repair supplies the real reserved capacity. Its source and loaded program match the normal caller exactly.

Cost and Maths for Games

The encoder makes two bounded scans of at most eight input cells and writes at most sixteen output cells. Output count is twice the number of runs. BASIC numeric arrays themselves are not packed byte storage; the values describe a byte format that could later be written through a suitable byte-output routine.

Maths for Games connects worst-case size, runs and compression ratio. The Craft helps choose between runtime conversion and build-time assets. Compare encoder and decoder failure contracts: this encoder preserves the whole destination on failure, while the decoder can return a useful partial prefix.

Machine and measured size

BBC BASIC arrays include element zero; this one-based array interface leaves it unused. Its diagnostic uses MODE 7 and HIMEM=&6000 to separate program storage, mailbox and screen. The helper itself changes neither mode nor HIMEM.

The numbered helper occupies 564 tokenised program bytes on this interpreter, including line headers. This excludes the caller, test tables, numeric scalar/array storage, interpreter stacks and ROM. Tokenised size is not machine-code size or a hardware-cycle count. No real-time or whole-game performance budget is inferred from the diagnostic. The caller’s AA/BB, JJ/KK and RAM mailbox are observation machinery, not required game state.

Execution evidence

Working, custom, deliberately wrong and exact repaired callers executed through BBC Micro’s stock BASIC interpreter under Emu198x 0.44.2. Build198x 0.2.9 tokenises C64 PRG and Spectrum TAP programs. C64 enters stock RUN, Spectrum uses ROM tape loading, and BBC enters every numbered source line through MOS/BASIC. Actual loaded program bytes, complete state packets, positive completion/count/guards and visible result pixels are checked. After the positive completion marker, the observer advances two complete display frames before capturing, so a partially scanned final character cannot masquerade as a finished picture. Firmware is not distributed.

An independent mathematical/order model checks the trace and rejects altered source, configuration, loaded program, state, completion and image evidence. Host exhaustive checks complement the native boundary/sequential examples; those host ranges are not claimed as natively exhaustive. The supplied diagnostic callers deliberately end with STOP; the interpreter report is expected. The wrong caller prints 0,0 and the normal/custom/repaired callers print 1,1.

Public CI checks retained evidence; it does not execute restricted firmware. Refresh with python3 scripts/verify-basic-packing.py bounded-rle-encoder bbc-micro --tools /path/to/extracted/releases and inspect with python3 scripts/check-basic-packing.py bounded-rle-encoder.

Explore further

Compare the assembly technique. The BASIC game-flow routine makes session boundaries explicit. Complete source and native evidence.