TDD sur CPC : le radix sort, deux comptages pour des clés de 16 bits

24/10/2026Z80CPCTDDtri

Le tri par comptage de l’article précédent ne déplace rien : il compte les octets, puis il les réécrit. Il sait combien de #42 écrire, pas lesquels. Sur des octets seuls, cela ne gêne pas. Mais comment trier des clés de 16 bits, quand un compteur par clé possible ne tiendrait pas en mémoire ?

Le tri par base, le radix sort, y arrive avec deux comptages, un par octet de la clé. Les tests vont guider son écriture en Z80, un par un, puis le compte des NOPs dira ce que coûtent ces deux passes face au comptage seul.

La méthode est celle de l’article sur find_min, à lire d’abord si le TDD vous est nouveau.

Ce que fait la routine

HL pointe sur le tableau, B contient le nombre de clés (de 1 à 255), et la routine trie les clés sur place, de la plus petite à la plus grande. Chaque clé tient sur deux octets, l’octet faible d’abord. DE pointe sur un buffer de 2n octets, fourni par l’appelant, à l’écart du tableau. Le tri s’en sert de brouillon, et ce que le buffer contient en sortie ne compte pas.

Le radix sort trie les clés chiffre par chiffre. Ici, un chiffre est un octet, et une clé de 16 bits en a deux. On trie d’abord sur l’octet faible, puis sur l’octet fort. Chaque passe est un tri par comptage, mais d’une autre forme que dans l’article précédent :

1. On compte les chiffres, un compteur par valeur, comme avant.
2. Chaque compteur devient une case de la destination : celle de la première clé de son chiffre. C’est la somme des compteurs de tous les chiffres plus petits.
3. On lit les clés dans l’ordre, et chacune va dans la case de son chiffre, qui avance d’une case.

Ce comptage déplace les clés. Il lui faut donc une destination : la première passe va du tableau vers le buffer, la seconde revient du buffer vers le tableau.

Lancez l’animation, ou avancez étape par étape. La première rangée est le tableau, la dernière le buffer, et la flèche montre la clé lue. Entre les deux, la table montre les compteurs des chiffres présents, et « … » les compteurs vides. Après les sommes, un compteur devient une case, notée →2 : la case où ira la prochaine clé de ce chiffre. Les cases sont numérotées à partir de 0. Un fond coloré marque le compteur lu ou modifié et, pendant les déplacements, la case où va la clé. Un contour coloré marque les clés déjà écrites par la passe.

Tout repose sur la fin de la passe 2. Les trois clés en #01 ont le même octet fort, et elles sortent dans l’ordre où la passe 1 les a rangées. On dit que la passe est stable : deux clés au même chiffre gardent leur ordre. Ce comptage l’est sans rien de plus, car les clés d’un même chiffre remplissent leurs cases dans l’ordre de lecture. Sans cette stabilité, la passe 2 déferait le travail de la passe 1.

Sur des octets seuls, le radix n’apporte rien : un octet n’a qu’un chiffre en base 256, et un radix en une passe, c’est le tri par comptage.

Deux tables alignées

Le comptage gardait ses compteurs dans une table counts de 256 octets, alignée sur une page, et L choisissait le compteur à lui seul. Le radix garde cette table : avec 255 clés au plus, un compteur tient encore dans un octet.

Mais une case de la destination est une adresse de 16 bits. Les sommes mettent donc l’octet faible de l’adresse dans counts, à la place du compteur, et l’octet fort dans une seconde table, slots_hi, la page juste au-dessus. Un inc h passe de l’une à l’autre.

La table ne peut plus rester propre d’un appel à l’autre, comme dans le comptage : après une passe, elle contient des adresses. Chaque passe commence donc par l’effacer.

Le premier test

Le radix sort n’a pas besoin des routines des articles précédents. Le source principal n’inclut que la nouvelle routine :

 org #4000
 include "radix-sort.asm"

Dans les tests de cet article, HL vaut #8000, DE vaut #8200, et B le nombre de clés. Les tableaux de test ne montrent donc que les clés et le résultat attendu.

Une clé seule est déjà triée. Le premier test vérifie qu’elle reste en place :

// Runs radix_sort on the 16-bit `keys`, written little-endian at ARRAY.
function radixSort(keys: number[]) {
  const bytes = keys.flatMap((key) => [key & 0xff, key >> 8]);

  return program.run("radix_sort", {
    registers: { hl: ARRAY, b: keys.length, de: BUFFER },
    memory: [{ at: ARRAY, bytes }],
  });
}

// Reads back the `count` 16-bit keys at ARRAY after a Run.
function keysAfter(run: ReturnType<typeof radixSort>, count: number) {
  const bytes = run.memory(ARRAY, 2 * count);

  return Array.from({ length: count }, (_, i) => bytes[2 * i] | (bytes[2 * i + 1] << 8));
}

it("leaves a one-key array as it is", () => {
  expect(keysAfter(radixSort([0x1234]), 1)).toEqual([0x1234]);
});

Une clé, puis deux

Les premières étapes suivent celles des tris précédents. Le test d’une clé échoue faute de label (radix/01-red), et un simple ret le fait passer (radix/02-green). Deux clés dans le mauvais ordre démasquent cette triche. Elles ne diffèrent que par l’octet faible (radix/03-red) :

it("sorts two keys by their low byte", () => {
  expect(keysAfter(radixSort([0x0142, 0x0117]), 2)).toEqual([0x0117, 0x0142]);
});

AssertionError: expected [ 322, 279 ] to deeply equal [ 279, 322 ]

Vitest affiche les clés en décimal : 322 vaut #0142, et 279 vaut #0117.

Une passe sur l’octet faible

Le code vert fait une passe complète sur l’octet faible, du tableau vers le buffer. Puis un ldir recopie le buffer dans le tableau (radix/04-green) :

; Sorts in place, smallest first, the B 16-bit keys at HL (1 to 255), little-endian.
; DE: a buffer of 2B bytes, apart from the array. Its contents on exit are free.
; Each pass is a stable counting sort on one byte of the keys.
radix_sort:
 push hl        ; the array
 push bc        ; B: the key count
 push de        ; the buffer
 ex de,hl       ; DE: the array
 ld hl,counts
 xor a
.clear:
 ld (hl),a
 inc l
 jr nz,.clear
.count:         ; L: back at #00
 ld a,(de)
 ld l,a
 inc (hl)       ; one more key with this low byte
 inc de
 inc de
 djnz .count
 pop de         ; DE: the buffer, the slot of the first key
 push de
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.sums:          ; each count becomes the slot of the first key with its byte
 ld c,(hl)      ; BC: the count, as B is zero
 ld (hl),e
 inc h
 ld (hl),d
 dec h
 ex de,hl
 add hl,bc      ; two bytes for each key
 add hl,bc
 ex de,hl
 inc l
 jr nz,.sums
 pop de         ; DE: the buffer
 pop bc
 pop hl         ; HL: the array
 push hl
 push de
 ld c,b
 ld b,0
 sla c
 rl b           ; BC: 2B, the bytes to move
 push bc
.move:          ; LDI counts BC down: JP PE loops until the last byte
 ld a,(hl)      ; A: the low byte, the digit of this pass
 push hl
 ld l,a
 ld h,counts >> 8
 ld e,(hl)
 inc h
 ld d,(hl)      ; DE: the slot of this key
 pop hl
 ldi
 ldi
 push hl
 ld l,a
 ld h,counts >> 8 ; LD, not DEC H: the P/V flag of LDI must live until JP PE
 ld (hl),e      ; the next key with this digit goes in the next slot
 ld h,slots_hi >> 8
 ld (hl),d
 pop hl
 jp pe,.move
 pop bc         ; BC: 2B
 pop hl         ; HL: the buffer
 pop de         ; DE: the array
 ldir           ; the sorted keys go back to the array
 ret

 align 256
counts:         ; for each byte value: its count, then the low byte of its next slot
 defs 256
slots_hi:       ; for each byte value: the high byte of its next slot, one page above
 defs 256

On retrouve les trois temps de l’animation, après l’effacement de la table :

• .clear met les 256 octets de counts à zéro.
• .count compte les octets faibles. DE saute deux octets par clé, pour lire l’octet faible de la suivante.
• .sums transforme chaque compteur en case. DE part du début du buffer : chaque valeur reçoit DE dans les deux tables, puis DE avance de deux octets par clé comptée.
• .move déplace les clés. Le chiffre lu dans A choisit la case dans les deux tables, et deux ldi copient la clé. Puis la case avancée retourne dans les tables, pour la prochaine clé au même chiffre.

ldi sert aussi de compteur de boucle. Il décrémente BC, et son drapeau P/V tombe à zéro quand BC atteint zéro. BC part donc de 2n, deux octets par clé, et jp pe boucle jusqu’à la dernière. Entre le dernier ldi et le jp pe, rien ne doit toucher P/V. C’est pourquoi la routine met ld h,counts >> 8 à la place d’un dec h : dec h change P/V, et la boucle s’arrêterait au hasard des adresses.

L’octet fort

Le test suivant prend deux clés qui ne diffèrent que par l’octet fort (radix/05-red) :

it("sorts two keys by their high byte", () => {
  expect(keysAfter(radixSort([0x0201, 0x0102]), 2)).toEqual([0x0102, 0x0201]);
});

AssertionError: expected [ 513, 258 ] to deeply equal [ 258, 513 ]

513 vaut #0201, et 258 vaut #0102. Sur l’octet faible, #0201 passe avant #0102, et la passe 1 laisse le tableau tel quel. Le code vert ajoute une deuxième passe, sur l’octet fort, du buffer vers le tableau. C’est une copie de la première, avec des labels numérotés (radix/06-green). La passe 2 écrit directement dans le tableau, et le ldir disparaît. Elle lit le chiffre un octet plus loin : par un inc de avant la boucle de comptage, et au déplacement comme ceci :

.move2:         ; LDI counts BC down: JP PE loops until the last byte
 inc hl
 ld a,(hl)      ; A: the high byte, the digit of this pass
 dec hl

Le reste de la passe 2 ne change pas d’une instruction.

Ce code vert change aussi le rôle du test précédent. #0142 et #0117 ont le même octet fort, #01. La passe 2 doit donc les laisser dans l’ordre de la passe 1. Le test des octets faibles vérifie maintenant la stabilité de la passe 2, sans test à part : une passe 2 qui lit les clés de la fin vers le début le fait échouer.

La stabilité de la passe 1, elle, ne se voit pas sur des clés seules. Deux clés au même octet faible et au même octet fort sont la même clé, et l’ordre entre elles ne change rien au résultat.

Une passe, deux appels

Tout est vert, et le code compte deux passes presque identiques. Elles ne diffèrent que par l’octet qui sert de chiffre, le premier ou le second de la clé. Il reste à n’en écrire qu’une.

Trois idées se présentent :

• un code auto-modifié, qui change l’instruction de lecture entre les deux appels ;
• une macro RASM, dépliée deux fois ;
• une passe qui écrit chaque clé avec ses deux octets échangés.

On prend la troisième : le buffer reçoit les clés à l’envers, l’octet fort d’abord. La passe 2 lit alors le chiffre au premier octet, comme la passe 1, et remet chaque clé à l’endroit (radix/07-refactor) :

; Sorts in place, smallest first, the B 16-bit keys at HL (1 to 255), little-endian.
; DE: a buffer of 2B bytes, apart from the array. Its contents on exit are free.
radix_sort:
 push de        ; the buffer
 push bc
 push hl        ; the array
 call .pass     ; the low byte, from the array to the buffer
 pop de         ; DE: the array
 pop bc         ; B: the key count
 pop hl         ; HL: the buffer
 call .pass     ; the high byte, from the buffer back to the array
 ret

; A stable counting sort of the B keys at HL into DE, on the first byte of each key.
; Each key goes out with its two bytes swapped: the buffer holds the keys big-endian,
; so the second pass reads the high byte first, and swaps the keys back.
.pass:
 push hl        ; the source
 push bc        ; B: the key count
 push de        ; the destination
 ex de,hl       ; DE: the source
 ld hl,counts
 xor a
.clear:
 ld (hl),a
 inc l
 jr nz,.clear
.count:         ; L: back at #00
 ld a,(de)
 ld l,a
 inc (hl)       ; one more key with this byte
 inc de
 inc de
 djnz .count
 pop de         ; DE: the destination, the slot of the first key
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.sums:          ; each count becomes the slot of the first key with its byte
 ld c,(hl)      ; BC: the count, as B is zero
 ld (hl),e
 inc h
 ld (hl),d
 dec h
 ex de,hl
 add hl,bc      ; two bytes for each key
 add hl,bc
 ex de,hl
 inc l
 jr nz,.sums
 pop bc
 pop hl         ; HL: the source
 ld c,b
 ld b,0         ; BC: the key count
.move:          ; LDI counts BC down: JP PE loops until the last key
 ld a,(hl)      ; A: the first byte, the digit of this pass
 push hl
 ld l,a
 ld h,counts >> 8
 ld e,(hl)
 inc h
 ld d,(hl)      ; DE: the slot of this key
 pop hl
 inc hl
 ldi            ; the second byte goes first
 ld (de),a      ; then the digit
 inc de
 push hl
 ld l,a
 ld h,counts >> 8 ; LD, not DEC H: the P/V flag of LDI must live until JP PE
 ld (hl),e      ; the next key with this digit goes in the next slot
 ld h,slots_hi >> 8
 ld (hl),d
 pop hl
 jp pe,.move
 ret

 align 256
counts:         ; for each byte value: its count, then the low byte of its next slot
 defs 256
slots_hi:       ; for each byte value: the high byte of its next slot, one page above
 defs 256

Le chiffre est déjà dans A. La passe copie donc le second octet par ldi, puis écrit A derrière lui. Il ne reste qu’un ldi par clé : BC part de n, et le sla c / rl b disparaît. L’animation du début, elle, montre les clés du buffer à l’endroit : elle suit l’algorithme, pas l’ordre des octets.

La routine n’a ni paramètre ni code qui se modifie, et le source fond de moitié. Le gain en NOPs est plus mince. La passe 1 coûte 1 NOP de plus par clé, la passe 2 3 NOPs de moins. La partie fixe prend 6 NOPs de plus : les deux call et leurs ret en coûtent 16, le sla c / rl b des deux passes et un inc de en rendent 10. Les deux versions coûtent autant à trois clés, et le refactor passe devant à partir de quatre.

Les deux bouts des clés

Les tests suivants passent dès leur écriture : ce sont des guards. Un guard doit prouver qu’il sait échouer. On casse donc la routine exprès, et on vérifie qu’il devient rouge. Le premier vise les deux bouts des clés, #0000 et #FFFF (radix/08-guard) :

it("sorts #FFFF and #0000, the two ends of the keys", () => {
  expect(keysAfter(radixSort([0xffff, 0x0000]), 2)).toEqual([0x0000, 0xffff]);
});

La version cassée qu’il vise arrête .sums un compteur trop tôt. Il suffit d’un ld a,l et d’un inc a avant le jr nz,.sums : la boucle s’arrête dès que L atteint #FF, avant de traiter son compteur. Le compteur de #FF ne devient jamais une case. La clé #FFFF part donc à l’adresse #0001 : l’octet faible de sa case est resté son compteur, 1, et slots_hi contient zéro. Aucun autre test n’a de chiffre #FF, et seul ce guard tombe :

AssertionError: expected [ +0, +0 ] to deeply equal [ +0, 65535 ]

Vitest écrit le zéro +0, et 65535 vaut #FFFF. Le guard attendait #0000, #FFFF et trouve #0000, #0000.

Quatre plages, pas une de plus

Le contrat donne au tri quatre zones de mémoire : le tableau, le buffer et les deux tables. Le guard suivant vérifie qu’il n’écrit nulle part ailleurs, hors de sa pile (radix/09-guard) :

// The Memory changes of a Run that lie in none of the `ranges`: toChangeOnly takes one range.
function changesOutside(run: ReturnType<typeof radixSort>, ranges: MemoryRange[]) {
  return run.memoryChanges.filter(({ address }) =>
    ranges.every((range) => ((address - range.address) & 0xffff) >= range.length),
  );
}

// Out of its stack, which no test sees, radix_sort may write only these four ranges.
it("changes only the array, the buffer and its two tables", () => {
  const keys = [0x0142, 0xffff, 0x0117, 0x0000, 0x0142];
  const run = radixSort(keys);

  expect(
    changesOutside(run, [
      { address: ARRAY, length: 2 * keys.length },
      { address: BUFFER, length: 2 * keys.length },
      program.range("counts", 256),
      program.range("slots_hi", 256),
    ]),
  ).toEqual([]);
});

La version cassée qu’il vise garde le nombre de clés dans une variable, au lieu de la pile : un defb placé juste après le ret de radix_sort, avant .pass. Le tri reste juste, et seul ce guard voit l’octet de trop :

- Expected
+ Received

- []
+ [
+   {
+     "address": 16403,
+     "after": 5,
+     "before": 0,
+   },
+ ]

16403 vaut #4013, l’adresse de cette variable. Elle y reçoit 5, le nombre de clés.

Le compte à la main

Le dernier guard porte sur le temps. On compte d’abord, avec la table de Madram. Chaque boucle coûte un NOP de moins à son dernier tour, quand son saut ne saute pas. jp pe fait exception : il coûte 3 NOPs, qu’il saute ou non.

Une passe coûte donc 61n + 6 686 NOPs, et les deux passes avec leur appel 122n + 13 406 NOPs.

Ce total ne dépend pas des clés. Aucun saut de la routine ne dépend de leur valeur : chaque boucle tourne n fois ou 256 fois. Trié, à l’envers, égal ou au hasard, un tableau de n clés coûte toujours le même nombre de NOPs.

Le budget

Un seul guard de budget suffit donc, sur trois entrées à la fois (radix/10-guard) :

// No branch of radix_sort depends on the keys: every input of n keys costs the same.
it.each([2, 16, 255])("sorts %i keys in 122n + 13406 NOPs at most, in any order", (n) => {
  const equal = Array.from({ length: n }, () => 0x4242);
  const sorted = Array.from({ length: n }, (_, i) => i * 0x0101);
  const reversed = [...sorted].reverse();

  for (const keys of [equal, sorted, reversed]) {
    expect(radixSort(keys).nops).toBeLessThanOrEqual(122 * n + 13406);
  }
});

La version cassée qu’il attrape est le code de 06-green, avant le refactor. Elle coûte 124n + 13 400 NOPs : 6 NOPs de moins en partie fixe, 2 de plus par clé. À deux clés, elle passe encore, avec 13 648 NOPs pour un budget de 13 650. Elle tombe à 16 et à 255 clés :

AssertionError: expected 15384 to be less than or equal to 15358
AssertionError: expected 45020 to be less than or equal to 44516

Radix et comptage

Le comptage de l’article précédent coûtait de 19n + 2 573 à 20n + 2 572 NOPs. Le radix coûte 122n + 13 406 NOPs. Il est plus cher sur les deux termes, mais il ne trie pas la même chose.

La partie fixe est cinq fois plus lourde. Le radix fait deux passes, et chacune parcourt deux fois les 256 valeurs. Il efface counts, que le comptage rendait propre. Et une somme coûte 20 NOPs par valeur, quand le parcours du comptage en coûtait 10. Sur les deux passes, les sommes pèsent 10 238 NOPs, et les effacements 3 070.

Par clé, l’écart est de six fois. Le comptage ajoutait 1 à un compteur, puis réécrivait un octet. Le radix compte et déplace une clé de deux octets, deux fois. Le déplacement coûte cher : il lit la case dans deux tables, copie la clé, puis range la case suivante.

À 255 clés, le radix prend 44 516 NOPs, un peu plus de deux trames de 19 968 NOPs. Le comptage triait 255 octets en 7 672 NOPs au pire. Mais le comptage ne peut pas trier des clés de 16 bits : il lui faudrait 65 536 compteurs, soit 64 Ko, autant que toute la mémoire d’un 464. Le radix se contente de 512 octets de tables, et d’un buffer de 2n octets.

Conclusion

Le radix sort réutilise le comptage, sous une forme stable, comme passe interne. Il déplace les clés, ce qui manquait au comptage, et deux passes suffisent pour des clés de 16 bits, à un coût de 122n + 13 406 NOPs qui ne dépend pas de l’entrée. En route, le test des octets faibles a changé de rôle pour garder la stabilité de la deuxième passe, et un échange d’octets a réuni les deux passes en une routine.

La routine a aussi ses contraintes :

• de 1 à 255 clés, l’octet faible d’abord ;
• un buffer de 2n octets fourni par l’appelant, en plus des 512 octets de tables ;
• une partie fixe de 13 406 NOPs, payée même pour deux clés ;
• des clés seules, sans données : la même passe pourrait en déplacer, et la stabilité de la première passe compterait alors aussi.

Le prochain article quitte les nombres pour les chaînes, avec une routine qui compare deux noms au format du firmware.

Pour essayer chez vous

Il vous faut Node.js 24 ou plus, pnpm, et RASM v3.3.1 dans le PATH. Les étapes de cet article sont sur la branche radix du dépôt z80-tdd-sorts. Elle part de main, comme la branche counting. Pour rejouer une étape :

git checkout radix/01-red
pnpm install
pnpm test

Les tests du tri sont dans src/radix-sort.test.ts. Pour installer z80-tdd dans un projet à vous, voir la section Pour essayer chez vous de l’article sur find_min.

Liens

• L’article précédent : le tri par comptage et les quatre tris face à face
• Le tri à bulles, le tri par insertion et le tri par sélection
• L’introduction : find_min et le TDD sur CPC
• z80-tdd, l’outil de test
• z80-tdd-sorts, le dépôt de cet article (branche radix)
• RASM, l’assembleur d’Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), la table des durées en NOPs