Encode a Small Run-length Block on C64 | Pattern Library

Repeated map values can take less room as a count and a value—but only if the output buffer is big enough.

C64 shows the working diagnostic row 06 00 01 06 10 41 41 41. — A completed native caller displays 06 00 01 06 10 41 41 41. The public field order below identifies these bytes; the capture is a state diagnostic, not a recording of a finished game.

Use it in a project

INPUT_COUNT selects 0–8 bytes B0–B7. Encode consecutive equal values as positive count/value byte pairs in R0–R15, up to CAPACITY 0–16. Preflight all runs before writing. Invalid bounds return VALID=0, ERROR=1; insufficient output returns VALID=1, ERROR=2. Both failures leave output bytes unchanged and WRITTEN=0. Success returns ERROR=0 and the even byte count; unused output bytes are preserved.

Include component.inc once (MOS callers include the shared 6502 implementation through it). Reserve the public fields in this exact order: WRITTEN, ERROR, VALID, INPUT_COUNT, CAPACITY, B0, B1, B2, B3, B4, B5, B6, B7, R0, R1, R2, R3, R4, R5, R6, R7, R8, R9, R10, R11, R12, R13, R14, R15. They occupy 29 contiguous bytes. Also reserve the private workspace: T0, T1, T2, T3, T4, EXPR_SAVE (6 bytes). Array names in the explanation refer to the numbered consecutive bindings, such as C0, C1 and so on.

Call bounded_rle_encoder_init once at the intended reset boundary. It clears inputs as well as outputs and workspace. Set your starting state and configuration afterwards, then call bounded_rle_encoder_step whenever the described event occurs. The helper reads no device, waits for no frame and installs no interrupt handler.

Ownership	Fields
Retain between calls	R0–R15 as the owned destination
Supply before service	INPUT_COUNT, CAPACITY and B0–B7
Read after service	WRITTEN, ERROR and VALID

A first pass counts runs and proves that every pair will fit. A second pass writes the pairs. That extra scan gives the caller an all-or-nothing output contract.

Reusable initialisation and service

6502.inc

; SPDX-License-Identifier: MIT
; Encode a Small Run-length Block. See README.md for the byte interface and ownership.
; init clears the public fields and private workspace; set inputs afterwards.
bounded_rle_encoder_init:
    lda #0
    sta WRITTEN
    sta ERROR
    sta VALID
    sta INPUT_COUNT
    sta CAPACITY
    sta B0
    sta B1
    sta B2
    sta B3
    sta B4
    sta B5
    sta B6
    sta B7
    sta R0
    sta R1
    sta R2
    sta R3
    sta R4
    sta R5
    sta R6
    sta R7
    sta R8
    sta R9
    sta R10
    sta R11
    sta R12
    sta R13
    sta R14
    sta R15
    sta T0
    sta T1
    sta T2
    sta T3
    sta T4
    sta EXPR_SAVE
    rts
bounded_rle_encoder_step:
; WRITTEN = 0
    lda #0
    sta WRITTEN
; ERROR = 1
    lda #1
    sta ERROR
; VALID = 0
    lda #0
    sta VALID
; if INPUT_COUNT > 8:
    lda INPUT_COUNT
    cmp #8
    beq bounded_rle_encoder_L5
    bcs bounded_rle_encoder_L4
bounded_rle_encoder_L5:
    jmp bounded_rle_encoder_L2
bounded_rle_encoder_L4:
    jmp bounded_rle_encoder_L1
bounded_rle_encoder_L1:
; return
    rts
    jmp bounded_rle_encoder_L3
bounded_rle_encoder_L2:
bounded_rle_encoder_L3:
; if CAPACITY > 16:
    lda CAPACITY
    cmp #16
    beq bounded_rle_encoder_L10
    bcs bounded_rle_encoder_L9
bounded_rle_encoder_L10:
    jmp bounded_rle_encoder_L7
bounded_rle_encoder_L9:
    jmp bounded_rle_encoder_L6
bounded_rle_encoder_L6:
; return
    rts
    jmp bounded_rle_encoder_L8
bounded_rle_encoder_L7:
bounded_rle_encoder_L8:
; VALID = 1
    lda #1
    sta VALID
; ERROR = 0
    lda #0
    sta ERROR
; if INPUT_COUNT == 0:
    lda INPUT_COUNT
    cmp #0
    beq bounded_rle_encoder_L14
bounded_rle_encoder_L15:
    jmp bounded_rle_encoder_L12
bounded_rle_encoder_L14:
    jmp bounded_rle_encoder_L11
bounded_rle_encoder_L11:
; return
    rts
    jmp bounded_rle_encoder_L13
bounded_rle_encoder_L12:
bounded_rle_encoder_L13:
; T0 = 1
    lda #1
    sta T0
; T1 = B[0]
    ldx #0
    lda B0,x
    sta T1
; T2 = 1
    lda #1
    sta T2
; while T0 < INPUT_COUNT:
bounded_rle_encoder_L16:
    lda T0
    cmp INPUT_COUNT
    bcc bounded_rle_encoder_L19
bounded_rle_encoder_L20:
    jmp bounded_rle_encoder_L18
bounded_rle_encoder_L19:
    jmp bounded_rle_encoder_L17
bounded_rle_encoder_L17:
; T3 = B[T0]
    ldx T0
    lda B0,x
    sta T3
; if T3 != T1:
    lda T3
    cmp T1
    bne bounded_rle_encoder_L24
bounded_rle_encoder_L25:
    jmp bounded_rle_encoder_L22
bounded_rle_encoder_L24:
    jmp bounded_rle_encoder_L21
bounded_rle_encoder_L21:
; T2 = T2 + 1
    lda T2
    clc
    adc #1
    sta T2
; T1 = T3
    lda T3
    sta T1
    jmp bounded_rle_encoder_L23
bounded_rle_encoder_L22:
bounded_rle_encoder_L23:
; T0 = T0 + 1
    lda T0
    clc
    adc #1
    sta T0
    jmp bounded_rle_encoder_L16
bounded_rle_encoder_L18:
; T2 = T2 << 1
    lda T2
    asl
    sta T2
; if T2 > CAPACITY:
    lda T2
    cmp CAPACITY
    beq bounded_rle_encoder_L30
    bcs bounded_rle_encoder_L29
bounded_rle_encoder_L30:
    jmp bounded_rle_encoder_L27
bounded_rle_encoder_L29:
    jmp bounded_rle_encoder_L26
bounded_rle_encoder_L26:
; ERROR = 2
    lda #2
    sta ERROR
; return
    rts
    jmp bounded_rle_encoder_L28
bounded_rle_encoder_L27:
bounded_rle_encoder_L28:
; T0 = 0
    lda #0
    sta T0
; T1 = 0
    lda #0
    sta T1
; while T0 < INPUT_COUNT:
bounded_rle_encoder_L31:
    lda T0
    cmp INPUT_COUNT
    bcc bounded_rle_encoder_L34
bounded_rle_encoder_L35:
    jmp bounded_rle_encoder_L33
bounded_rle_encoder_L34:
    jmp bounded_rle_encoder_L32
bounded_rle_encoder_L32:
; T2 = B[T0]
    ldx T0
    lda B0,x
    sta T2
; T3 = 1
    lda #1
    sta T3
; T0 = T0 + 1
    lda T0
    clc
    adc #1
    sta T0
; while T0 < INPUT_COUNT:
bounded_rle_encoder_L36:
    lda T0
    cmp INPUT_COUNT
    bcc bounded_rle_encoder_L39
bounded_rle_encoder_L40:
    jmp bounded_rle_encoder_L38
bounded_rle_encoder_L39:
    jmp bounded_rle_encoder_L37
bounded_rle_encoder_L37:
; T4 = B[T0]
    ldx T0
    lda B0,x
    sta T4
; if T4 != T2:
    lda T4
    cmp T2
    bne bounded_rle_encoder_L44
bounded_rle_encoder_L45:
    jmp bounded_rle_encoder_L42
bounded_rle_encoder_L44:
    jmp bounded_rle_encoder_L41
bounded_rle_encoder_L41:
; break
    jmp bounded_rle_encoder_L38
    jmp bounded_rle_encoder_L43
bounded_rle_encoder_L42:
bounded_rle_encoder_L43:
; T3 = T3 + 1
    lda T3
    clc
    adc #1
    sta T3
; T0 = T0 + 1
    lda T0
    clc
    adc #1
    sta T0
    jmp bounded_rle_encoder_L36
bounded_rle_encoder_L38:
; R[T1] = T3
    lda T3
    sta EXPR_SAVE
    ldx T1
    lda EXPR_SAVE
    sta R0,x
; T1 = T1 + 1
    lda T1
    clc
    adc #1
    sta T1
; R[T1] = T2
    lda T2
    sta EXPR_SAVE
    ldx T1
    lda EXPR_SAVE
    sta R0,x
; T1 = T1 + 1
    lda T1
    clc
    adc #1
    sta T1
    jmp bounded_rle_encoder_L31
bounded_rle_encoder_L33:
; WRITTEN = T1
    lda T1
    sta WRITTEN
    rts
component_end:

Machine contract

A/X/status may change; Y and decimal mode are preserved. Use CLD for binary arithmetic. A direct JSR needs two return-address stack bytes. The helper makes no nested calls and adds no other stack use. Its named scratch is private workspace, not a pointer, a ROM variable or shared zero-page space that the game may borrow concurrently. The samples use fixed symbol bindings. Scope or rename every label and binding, including the component_end measurement marker, and allocate a separate block for each independent instance. Different helpers can also use common field names, so combining them needs separate namespaces or explicitly renamed bindings. Give each block one mutation owner.

The diagnostic PRG owns screen, font and colour RAM and disables interrupts; it does not return to BASIC. The reusable helper does none of those things.

Adapt the caller

demo.asm supplies the bindings and include order. exercise.inc first runs table cases, then a separate client retaining state between calls. A game can call the public step entry directly and remove the diagnostic packet and display. Do not copy the diagnostic’s hardware takeover into an existing game loop.

Build with make ASM198X=/path/to/asm198x. The Makefile produces normal, custom, deliberately wrong and repaired programs. Tools must already be installed; the sample downloads nothing.

Bindings and include order

demo.asm

WRITTEN=$80
ERROR=$81
VALID=$82
INPUT_COUNT=$83
CAPACITY=$84
B0=$85
B1=$86
B2=$87
B3=$88
B4=$89
B5=$8a
B6=$8b
B7=$8c
R0=$8d
R1=$8e
R2=$8f
R3=$90
R4=$91
R5=$92
R6=$93
R7=$94
R8=$95
R9=$96
R10=$97
R11=$98
R12=$99
R13=$9a
R14=$9b
R15=$9c
T0=$9d
T1=$9e
T2=$9f
T3=$a0
T4=$a1
EXPR_SAVE=$a2
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$c000
preview=OUTPUT+1400
ready=OUTPUT+1408
CUSTOM=0
BROKEN=0
COYOTE_STEPS=4
BUFFER_STEPS=4
TEXT_CAP=8
PROPERTY_COUNT=16
STREAM_BYTES=13
CRC_POLY=7
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.inc"
!source "data.inc"
!source "cases.inc"
hex_font:
    !byte 0,0,0,0,0,0,0,0,0,56,40,40,40,56,0,0,0,16,48,16,16,56,0,0,0,56,8,56,32,56,0,0,0,56,8,56,8,56,0,0,0,40,40,56,8,8,0,0,0,56,32,56,8,56,0,0,0,56,32,56,40,56,0,0,0,56,8,8,8,8,0,0,0,56,40,56,40,56,0,0,0,56,40,56,8,56,0,0,0,16,40,56,40,40,0,0,0,48,40,48,40,48,0,0,0,56,32,32,32,56,0,0,0,48,40,40,40,48,0,0,0,56,32,48,32,56,0,0,0,56,32,48,32,32,0,0
code_end:

A client retaining state between calls

exercise.inc, excerpt

preview_rules:
!if CUSTOM {
; INPUT_COUNT = 8
    lda #8
    sta INPUT_COUNT
; CAPACITY = 16
    lda #16
    sta CAPACITY
; B0 = 0
    lda #0
    sta B0
; B1 = 1
    lda #1
    sta B1
; B2 = 2
    lda #2
    sta B2
; B3 = 3
    lda #3
    sta B3
; B4 = 4
    lda #4
    sta B4
; B5 = 5
    lda #5
    sta B5
; B6 = 6
    lda #6
    sta B6
; B7 = 7
    lda #7
    sta B7
!if BROKEN {
; CAPACITY = 0
    lda #0
    sta CAPACITY
}
    jsr checked_step
    jsr emit_state
    rts
} else {
; INPUT_COUNT = 6
    lda #6
    sta INPUT_COUNT
; CAPACITY = 16
    lda #16
    sta CAPACITY
; B0 = 65
    lda #65
    sta B0
; B1 = 65
    lda #65
    sta B1
; B2 = 65
    lda #65
    sta B2
; B3 = 66
    lda #66
    sta B3
; B4 = 66
    lda #66
    sta B4
; B5 = 67
    lda #67
    sta B5
!if BROKEN {
; CAPACITY = 0
    lda #0
    sta CAPACITY
}
    jsr checked_step
    jsr emit_state
}
    rts

Customise it

Encode eight distinct values, the worst expansion for this small block. The maintained custom caller changes its inputs or client sequence rather than hiding a different implementation behind the same label. Compare every state of the two clients, not only their final display.

Custom client selection

custom.asm

WRITTEN=$80
ERROR=$81
VALID=$82
INPUT_COUNT=$83
CAPACITY=$84
B0=$85
B1=$86
B2=$87
B3=$88
B4=$89
B5=$8a
B6=$8b
B7=$8c
R0=$8d
R1=$8e
R2=$8f
R3=$90
R4=$91
R5=$92
R6=$93
R7=$94
R8=$95
R9=$96
R10=$97
R11=$98
R12=$99
R13=$9a
R14=$9b
R15=$9c
T0=$9d
T1=$9e
T2=$9f
T3=$a0
T4=$a1
EXPR_SAVE=$a2
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$c000
preview=OUTPUT+1400
ready=OUTPUT+1408
CUSTOM=1
BROKEN=0
COYOTE_STEPS=2
BUFFER_STEPS=2
TEXT_CAP=4
PROPERTY_COUNT=16
STREAM_BYTES=13
CRC_POLY=49
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.inc"
!source "data.inc"
!source "cases.inc"
hex_font:
    !byte 0,0,0,0,0,0,0,0,0,56,40,40,40,56,0,0,0,16,48,16,16,56,0,0,0,56,8,56,32,56,0,0,0,56,8,56,8,56,0,0,0,40,40,56,8,8,0,0,0,56,32,56,8,56,0,0,0,56,32,56,40,56,0,0,0,56,8,8,8,8,0,0,0,56,40,56,40,56,0,0,0,56,40,56,8,56,0,0,0,16,40,56,40,40,0,0,0,48,40,48,40,48,0,0,0,56,32,32,32,56,0,0,0,48,40,40,40,48,0,0,0,56,32,48,32,56,0,0,0,56,32,48,32,32,0,0
code_end:

The custom diagnostic row is 10 00 01 08 10 00 01 02. The full client trace in the source explains how it gets there.

Mistake and repair

The wrong caller passes no output capacity for a nonempty block. The encoder rejects the whole request and preserves its output buffer. Pass the actual reserved capacity, rather than a count that has not yet been filled.

The BROKEN branch lives in the sequential client, not the reusable helper. wrong.asm selects it; repaired.asm restores the normal call sequence. The repaired executable matches the normal program (for Spectrum, compare loaded CODE rather than the tape filename).

Select the deliberately wrong client

wrong.asm

WRITTEN=$80
ERROR=$81
VALID=$82
INPUT_COUNT=$83
CAPACITY=$84
B0=$85
B1=$86
B2=$87
B3=$88
B4=$89
B5=$8a
B6=$8b
B7=$8c
R0=$8d
R1=$8e
R2=$8f
R3=$90
R4=$91
R5=$92
R6=$93
R7=$94
R8=$95
R9=$96
R10=$97
R11=$98
R12=$99
R13=$9a
R14=$9b
R15=$9c
T0=$9d
T1=$9e
T2=$9f
T3=$a0
T4=$a1
EXPR_SAVE=$a2
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$c000
preview=OUTPUT+1400
ready=OUTPUT+1408
CUSTOM=0
BROKEN=1
COYOTE_STEPS=4
BUFFER_STEPS=4
TEXT_CAP=8
PROPERTY_COUNT=16
STREAM_BYTES=13
CRC_POLY=7
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.inc"
!source "data.inc"
!source "cases.inc"
hex_font:
    !byte 0,0,0,0,0,0,0,0,0,56,40,40,40,56,0,0,0,16,48,16,16,56,0,0,0,56,8,56,32,56,0,0,0,56,8,56,8,56,0,0,0,40,40,56,8,8,0,0,0,56,32,56,8,56,0,0,0,56,32,56,40,56,0,0,0,56,8,8,8,8,0,0,0,56,40,56,40,56,0,0,0,56,40,56,8,56,0,0,0,16,40,56,40,40,0,0,0,48,40,48,40,48,0,0,0,56,32,32,32,56,0,0,0,48,40,40,40,48,0,0,0,56,32,48,32,56,0,0,0,56,32,48,32,32,0,0
code_end:

C64 shows the deliberate error row 00 02 01 06 00 41 41 41. — The wrong client completes with 00 02 01 06 00 41 41 41; its changed inputs and state explain the result.

Cost and alternatives

The measured helper extent is 372 code bytes; public state is 29 bytes and private scratch is 6 bytes. There are no immutable helper tables. Caller data, the test cases, return-address stack, alignment and display buffers cost additional space. These are assembled sizes, not cycle measurements.

Two bounded scans over at most eight bytes, plus sixteen destination writes in the worst case. A streaming encoder can avoid preflight but must report partial output and support continuation explicitly.

RLE can expand data: eight distinct bytes need sixteen encoded bytes. This uses the existing count/value idea, not a new project-wide asset container. A decoder must still validate its own lengths and output bounds.

Execution evidence

Four variants run on PAL stock-ROM PRG, using Asm198x 0.0.72, Emu198x 0.44.2. Each executes 34 boundary/varied/error table cases, dirty initialisation and the separate retained-state client. An independent mathematical/container model checks every public byte after every call. This is bounded example coverage, not exhaustive correctness for every possible state.

The records retain loaded immutable code, completion, register sentinels, full packets, source/tool/firmware hashes and captures. The public gate validates these retained observations and rejects altered evidence; it does not run restricted firmware. No firmware is distributed. The eight displayed bytes are the first eight public fields, zero-padded when shorter; the packet includes every field.

Where it fits

Bounded RLE decoding: Encoding and decoding share count/value semantics but need different buffer and failure contracts.

The Craft · Maths for Games · Source and native evidence.