Machine Code Shell-Faulk Sort

This program implements a Shell-Faulk (Shell sort) algorithm entirely in machine code, sorting an array of random strings. The BASIC loader generates 100 random 10-character uppercase strings stored in a two-dimensional string array `N$(X+1, L)`, then passes control parameters to the machine code routine via POKEs to addresses 23296–23301. The machine code block of 249 bytes resides at address 61390, called via `RANDOMIZE USR 61402`. A key technique involves POKEing the address of `N$`’s data area by reading the system variable STRMS pointer at 23629–23630, and touching `N$(1)` and `N$(X+1)` before the USR call to ensure the array’s memory descriptor is current. After sorting, the program prints all 100 strings in order and halts.

---

Program Analysis

Program Structure

The program is divided into four logical phases:

1. Initialization (lines 1–10): REMs document the algorithm and data layout; line 10 dimensions N$(X+1, L) (101×10), fills it with random uppercase letters, and waits for a keypress.
2. Parameter passing (line 20): POKEs the sort parameters and the base address of N$ into fixed RAM locations at 23296–23301 for the machine code to read.
3. Machine code invocation (line 30): Touches N$(1) to force the array descriptor to be valid, then calls the sort routine via RANDOMIZE USR 61402.
4. Output and save (lines 100, 9990, 9999): Prints the sorted strings; lines 9990–9999 handle loading/saving the machine code binary and the BASIC program itself.

Parameter Passing Convention

Because machine code on the Spectrum cannot directly interrogate BASIC arrays, the program communicates with the sorter through a small parameter block poked into low RAM (23296–23301), well below the machine code at 61390:

Address	Contents
23296–23297	X (number of elements, 16-bit little-endian)
23298–23299	L (string length, 16-bit little-endian)
23300–23301	Base address of N$ data (copied from system variable STRMS at 23629–23630)

The 16-bit values are split manually with X-256*INT(X/256) (low byte) and INT(X/256) (high byte), a standard ZX Spectrum BASIC idiom for storing integers into two consecutive POKE addresses.

Array Address Resolution

Lines 20 and 30 use a two-step trick to locate the array data in RAM. The system variable area at 23629–23630 holds a relevant pointer (STRMS), which is read with PEEK and POKEd into the parameter block. Before calling USR, both N$(1)=N$(1) and N$(X+1)=N$(X+1) are evaluated; these null assignments force the interpreter to resolve the array’s current heap position, making the POKEd address reliable.

Machine Code Block

The 249-byte machine code routine lives at address 61390 (near the top of the 64 KB address space, safely above RAMTOP for typical configurations). The entry point used by RANDOMIZE USR is 61402, twelve bytes into the block — likely after a small header or data table. The sort implemented is the Shell-Faulk algorithm (a variant of Shell sort), which is well-suited to machine code because its diminishing-increment gap sequence requires only simple integer arithmetic and compare/swap loops, with no recursion.

Save/Load Mechanism

Line 9999 saves both the BASIC program (with LINE 9990 as the auto-run entry) and the machine code block ("sort" CODE 61390,249). Line 9990 uses CLEAR 61389 before loading, which sets RAMTOP just below the code destination so the Spectrum’s memory manager will not overwrite the freshly loaded binary. VERIFY calls confirm both blocks after saving.

Notable Techniques

• Placing the parameter block at 23296–23301 reuses the low system-variable workspace, avoiding any conflict with the BASIC program or the high-memory machine code.
• The DIM N$(X+1, L) allocates one extra row beyond the sort range, providing a scratch element the machine code can use as a temporary buffer during the shift phase of the sort without requiring separate workspace.
• RANDOMIZE USR is preferred over GO TO USR or direct POKE because it preserves the BASIC stack and cleanly returns to line 100 after the routine executes RET.
• The BEEP calls at lines 10 and 100 provide audible start/end cues — a common technique when benchmarking or timing machine code routines by ear.

Potential Anomalies

The address stored via PEEK 23629 / PEEK 23630 references the STRMS system variable, which maps stream channel addresses rather than array storage. This address is used as the base of N$‘s data; the exact interpretation depends on how the machine code was written to navigate from that pointer to the array body. If STRMS does not coincidentally hold the correct array base in all memory configurations, the sort could corrupt memory — this appears to be a deliberate but configuration-dependent design choice by the author rather than a general-purpose technique.