Keep a Stable Priority Event Queue on NES | Pattern Library

An urgent event may need service before an older routine event, while equal priorities should remain fair.

NES shows the working diagnostic row 16 08 01 01 02 01 21 08. — A completed native caller displays 16 08 01 01 02 01 21 08. 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

A queue holds at most four event/priority pairs. MODE=0 inserts; MODE=1 removes the highest priority, with earlier insertion winning ties. COUNT must be 0–4. Return RESULT=1 on a change, VALID=0 for invalid count/mode. Full insertion and empty removal are valid no-ops. Failed operations return EVENT=255, PRIORITY=0.

Include component.inc once (MOS callers include the shared 6502 implementation through it). Reserve the public fields in this exact order: EVENT, PRIORITY, RESULT, VALID, COUNT, MODE, NEW_EVENT, NEW_PRIORITY, E0, E1, E2, E3, P0, P1, P2, P3. They occupy 16 contiguous bytes. Also reserve the private workspace: T0, T1, T2, EXPR_SAVE (4 bytes). Array names in the explanation refer to the numbered consecutive bindings, such as C0, C1 and so on.

Call priority_event_queue_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 priority_event_queue_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	COUNT, E0..E3 and P0..P3
Supply before service	MODE, NEW_EVENT and NEW_PRIORITY
Read after service	EVENT, PRIORITY, RESULT and VALID

Insertion shifts only lower-priority entries. Stopping at an equal priority keeps arrival order stable; removal takes the first pair and closes the gap.

Reusable initialisation and service

6502.inc

; SPDX-License-Identifier: MIT
; Keep a Stable Priority Event Queue. See README.md for the byte interface and ownership.
; init clears the public fields and private workspace; set inputs afterwards.
priority_event_queue_init:
    lda #0
    sta EVENT
    sta PRIORITY
    sta RESULT
    sta VALID
    sta COUNT
    sta MODE
    sta NEW_EVENT
    sta NEW_PRIORITY
    sta E0
    sta E1
    sta E2
    sta E3
    sta P0
    sta P1
    sta P2
    sta P3
    sta T0
    sta T1
    sta T2
    sta EXPR_SAVE
    rts
priority_event_queue_step:
; EVENT = 255
    lda #255
    sta EVENT
; PRIORITY = 0
    lda #0
    sta PRIORITY
; RESULT = 0
    lda #0
    sta RESULT
; VALID = 0
    lda #0
    sta VALID
; if COUNT > 4:
    lda COUNT
    cmp #4
    beq priority_event_queue_L5
    bcs priority_event_queue_L4
priority_event_queue_L5:
    jmp priority_event_queue_L2
priority_event_queue_L4:
    jmp priority_event_queue_L1
priority_event_queue_L1:
; return
    rts
    jmp priority_event_queue_L3
priority_event_queue_L2:
priority_event_queue_L3:
; if MODE > 1:
    lda MODE
    cmp #1
    beq priority_event_queue_L10
    bcs priority_event_queue_L9
priority_event_queue_L10:
    jmp priority_event_queue_L7
priority_event_queue_L9:
    jmp priority_event_queue_L6
priority_event_queue_L6:
; return
    rts
    jmp priority_event_queue_L8
priority_event_queue_L7:
priority_event_queue_L8:
; VALID = 1
    lda #1
    sta VALID
; if MODE == 0:
    lda MODE
    cmp #0
    beq priority_event_queue_L14
priority_event_queue_L15:
    jmp priority_event_queue_L12
priority_event_queue_L14:
    jmp priority_event_queue_L11
priority_event_queue_L11:
; if COUNT == 4:
    lda COUNT
    cmp #4
    beq priority_event_queue_L19
priority_event_queue_L20:
    jmp priority_event_queue_L17
priority_event_queue_L19:
    jmp priority_event_queue_L16
priority_event_queue_L16:
; return
    rts
    jmp priority_event_queue_L18
priority_event_queue_L17:
priority_event_queue_L18:
; T0 = COUNT
    lda COUNT
    sta T0
; while T0 != 0:
priority_event_queue_L21:
    lda T0
    cmp #0
    bne priority_event_queue_L24
priority_event_queue_L25:
    jmp priority_event_queue_L23
priority_event_queue_L24:
    jmp priority_event_queue_L22
priority_event_queue_L22:
; T1 = T0 - 1
    lda T0
    sec
    sbc #1
    sta T1
; T2 = P[T1]
    ldx T1
    lda P0,x
    sta T2
; if NEW_PRIORITY <= T2:
    lda NEW_PRIORITY
    cmp T2
    bcc priority_event_queue_L29
    beq priority_event_queue_L29
priority_event_queue_L30:
    jmp priority_event_queue_L27
priority_event_queue_L29:
    jmp priority_event_queue_L26
priority_event_queue_L26:
; break
    jmp priority_event_queue_L23
    jmp priority_event_queue_L28
priority_event_queue_L27:
priority_event_queue_L28:
; P[T0] = T2
    lda T2
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta P0,x
; T2 = E[T1]
    ldx T1
    lda E0,x
    sta T2
; E[T0] = T2
    lda T2
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta E0,x
; T0 = T0 - 1
    lda T0
    sec
    sbc #1
    sta T0
    jmp priority_event_queue_L21
priority_event_queue_L23:
; E[T0] = NEW_EVENT
    lda NEW_EVENT
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta E0,x
; P[T0] = NEW_PRIORITY
    lda NEW_PRIORITY
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta P0,x
; COUNT = COUNT + 1
    lda COUNT
    clc
    adc #1
    sta COUNT
; EVENT = NEW_EVENT
    lda NEW_EVENT
    sta EVENT
; PRIORITY = NEW_PRIORITY
    lda NEW_PRIORITY
    sta PRIORITY
    jmp priority_event_queue_L13
priority_event_queue_L12:
; if COUNT == 0:
    lda COUNT
    cmp #0
    beq priority_event_queue_L34
priority_event_queue_L35:
    jmp priority_event_queue_L32
priority_event_queue_L34:
    jmp priority_event_queue_L31
priority_event_queue_L31:
; return
    rts
    jmp priority_event_queue_L33
priority_event_queue_L32:
priority_event_queue_L33:
; EVENT = E0
    lda E0
    sta EVENT
; PRIORITY = P0
    lda P0
    sta PRIORITY
; COUNT = COUNT - 1
    lda COUNT
    sec
    sbc #1
    sta COUNT
; T0 = 0
    lda #0
    sta T0
; while T0 < COUNT:
priority_event_queue_L36:
    lda T0
    cmp COUNT
    bcc priority_event_queue_L39
priority_event_queue_L40:
    jmp priority_event_queue_L38
priority_event_queue_L39:
    jmp priority_event_queue_L37
priority_event_queue_L37:
; T1 = T0 + 1
    lda T0
    clc
    adc #1
    sta T1
; T2 = E[T1]
    ldx T1
    lda E0,x
    sta T2
; E[T0] = T2
    lda T2
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta E0,x
; T2 = P[T1]
    ldx T1
    lda P0,x
    sta T2
; P[T0] = T2
    lda T2
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta P0,x
; T0 = T0 + 1
    lda T0
    clc
    adc #1
    sta T0
    jmp priority_event_queue_L36
priority_event_queue_L38:
; E[T0] = 0
    lda #0
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta E0,x
; P[T0] = 0
    lda #0
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta P0,x
priority_event_queue_L13:
; RESULT = 1
    lda #1
    sta RESULT
    rts
component_end:

Machine contract

A/X/status may change; Y is preserved. The 2A03 has no decimal arithmetic mode. 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 NROM caller owns PPU setup and background display, with NMI and DMC disabled. Table and packet sizes are bounded to fit the cartridge caller and internal RAM; the helper owns no PPU registers.

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

.segment "HEADER"
.byte "NES",$1a,2,1,0,0,0,0,0,0,0,0,0,0
EVENT=$80
PRIORITY=$81
RESULT=$82
VALID=$83
COUNT=$84
MODE=$85
NEW_EVENT=$86
NEW_PRIORITY=$87
E0=$88
E1=$89
E2=$8a
E3=$8b
P0=$8c
P1=$8d
P2=$8e
P3=$8f
T0=$90
T1=$91
T2=$92
EXPR_SAVE=$93
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$0200
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
.include "caller.inc"
.include "exercise.inc"
component_start:
.include "component.inc"
.include "data.inc"
.include "cases.inc"
code_end:
.segment "VECTORS"
.word nmi,reset,irq
.segment "CHARS"
.include "../../input/controller-reading/edges-font.inc"
.res 8192-272,0

A client retaining state between calls

exercise.inc, excerpt

preview_rules:
.if CUSTOM
; NEW_EVENT = 7
    lda #7
    sta NEW_EVENT
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.if BROKEN
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.endif
    jsr checked_step
    jsr emit_state
; NEW_EVENT = 9
    lda #9
    sta NEW_EVENT
; NEW_PRIORITY = 255
    lda #255
    sta NEW_PRIORITY
.if BROKEN
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.endif
    jsr checked_step
    jsr emit_state
; MODE = 1
    lda #1
    sta MODE
.if BROKEN
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.endif
    jsr checked_step
    jsr emit_state
    rts
.else
; NEW_EVENT = 11
    lda #11
    sta NEW_EVENT
; NEW_PRIORITY = 2
    lda #2
    sta NEW_PRIORITY
.if BROKEN
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.endif
    jsr checked_step
    jsr emit_state
; NEW_EVENT = 22
    lda #22
    sta NEW_EVENT
; NEW_PRIORITY = 8
    lda #8
    sta NEW_PRIORITY
.if BROKEN
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.endif
    jsr checked_step
    jsr emit_state
; NEW_EVENT = 33
    lda #33
    sta NEW_EVENT
; NEW_PRIORITY = 8
    lda #8
    sta NEW_PRIORITY
.if BROKEN
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.endif
    jsr checked_step
    jsr emit_state
; MODE = 1
    lda #1
    sta MODE
.if BROKEN
; NEW_PRIORITY = 0
    lda #0
    sta NEW_PRIORITY
.endif
    jsr checked_step
    jsr emit_state
.endif
    rts

Customise it

Mix the minimum and maximum priorities. 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

.segment "HEADER"
.byte "NES",$1a,2,1,0,0,0,0,0,0,0,0,0,0
EVENT=$80
PRIORITY=$81
RESULT=$82
VALID=$83
COUNT=$84
MODE=$85
NEW_EVENT=$86
NEW_PRIORITY=$87
E0=$88
E1=$89
E2=$8a
E3=$8b
P0=$8c
P1=$8d
P2=$8e
P3=$8f
T0=$90
T1=$91
T2=$92
EXPR_SAVE=$93
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$0200
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
.include "caller.inc"
.include "exercise.inc"
component_start:
.include "component.inc"
.include "data.inc"
.include "cases.inc"
code_end:
.segment "VECTORS"
.word nmi,reset,irq
.segment "CHARS"
.include "../../input/controller-reading/edges-font.inc"
.res 8192-272,0

The custom diagnostic row is 09 FF 01 01 01 01 09 FF. The full client trace in the source explains how it gets there.

Mistake and repair

The wrong caller discards insertion priority. The queue then behaves like an ordinary FIFO and returns event 11 before urgent event 22. Preserve the requested priority.

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

.segment "HEADER"
.byte "NES",$1a,2,1,0,0,0,0,0,0,0,0,0,0
EVENT=$80
PRIORITY=$81
RESULT=$82
VALID=$83
COUNT=$84
MODE=$85
NEW_EVENT=$86
NEW_PRIORITY=$87
E0=$88
E1=$89
E2=$8a
E3=$8b
P0=$8c
P1=$8d
P2=$8e
P3=$8f
T0=$90
T1=$91
T2=$92
EXPR_SAVE=$93
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$0200
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
.include "caller.inc"
.include "exercise.inc"
component_start:
.include "component.inc"
.include "data.inc"
.include "cases.inc"
code_end:
.segment "VECTORS"
.word nmi,reset,irq
.segment "CHARS"
.include "../../input/controller-reading/edges-font.inc"
.res 8192-272,0

NES shows the deliberate error row 0B 00 01 01 02 01 21 00. — The wrong client completes with 0B 00 01 01 02 01 21 00; its changed inputs and state explain the result.

Cost and alternatives

The measured helper extent is 371 code bytes; public state is 16 bytes and private scratch is 4 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.

At most four pair moves. A binary heap costs more machinery but suits larger queues; a plain FIFO gives simpler fairness when urgency is unnecessary.

The retained queue must already be sorted by descending priority. This is not an interrupt-safe producer/consumer queue and can starve low-priority events.

Execution evidence

Four variants run on NTSC NROM, background only, DMC/NMI disabled, using Asm198x 0.0.72, Emu198x 0.44.2. Each executes 62 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

Event queues: Choose FIFO or priority order according to the rules of the game.

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