TDD sur CPC : trier des pointeurs vers des chaînes

25/10/2026Z80CPCTDDtri

Le dernier article a écrit strcmp, une comparaison de chaînes au format du firmware, en vue d’un tri. Ce tri est un tri par insertion, comme dans l’article sur l’insertion, mais sur un tableau de pointeurs : les chaînes ne bougent pas, seuls les pointeurs changent de place. Que change ce détour par les pointeurs, pour un tri déjà écrit une fois ?

Deux choses, que les tests font apparaître l’une après l’autre. Deux chaînes égales se distinguent enfin par leur adresse, et la stabilité du tri devient visible. Et une comparaison ne coûte plus un simple CP, car son coût dépend des lettres communes aux deux chaînes. Le budget dépend donc de n, mais aussi de k, le nombre de lettres égales en tête des deux chaînes comparées.

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 un tableau de n pointeurs, et B contient n, de 1 à 255. Chaque pointeur prend deux octets, l’octet faible d’abord, comme toute adresse sur Z80. Le tableau fait donc 2n octets, et il peut franchir une frontière de page. Les chaînes aussi, comme strcmp le permet.

string_sort range les pointeurs dans l’ordre de leurs chaînes, celui que donne strcmp. Les chaînes ne bougent pas. Deux pointeurs vers deux chaînes égales gardent leur ordre : le tri est stable.

Les articles précédents n’avaient pas besoin de ce dernier point. Deux octets égaux sont identiques, et si un tri les échange, personne ne peut le voir. Deux pointeurs vers deux “MODE”, eux, diffèrent : l’un vaut #9000, l’autre #9004. Un tri qui les échange laisse une trace dans le tableau.

Lancez l’animation, ou avancez étape par étape. Chaque case montre un pointeur, avec le texte de sa chaîne au-dessus, et les chaînes se suivent à partir de #9000, comme dans les tests. Les cases au contour coloré forment la suite triée. La case pleine est la clé, dans le trou, et la flèche montre le pointeur auquel strcmp la compare. L’animation suit la version finale du tri, écrite plus bas.

La troisième clé, #900D, s’arrête derrière l’autre “MODE” sans la dépasser. C’est la stabilité, et un test va la vérifier.

Le premier test

Les données sont des mots-clés du Basic du CPC : MODE, MOVE, MOVER, MEMORY, MERGE. Ils commencent tous par M, et MOVE est le début de MOVER : strcmp doit lire plusieurs lettres pour les départager. Les chaînes se suivent à partir de #9000, et les pointeurs commencent à #8000.

Le premier test donne un seul pointeur, et attend une mémoire intacte :

// Runs string_sort on pointers to `texts`. The strings follow one another
// from STRINGS, and the array holds a little-endian pointer to each one.
function runStringSort(texts: string[]) {
  const strings = texts.map(bytesOf);
  const pointers: number[] = [];
  let at = STRINGS;
  for (const bytes of strings) {
    pointers.push(at & 0xff, at >> 8);
    at += bytes.length;
  }

  return program.run("string_sort", {
    registers: { hl: ARRAY, b: texts.length },
    memory: [
      { at: ARRAY, bytes: pointers },
      { at: STRINGS, bytes: strings.flat() },
    ],
  });
}

it("leaves a one-pointer array as it is", () => {
  expect(runStringSort(["MODE"])).toLeaveMemoryUnchanged();
});

Sans label string_sort, le test échoue tout de suite (strsort/01-red) :

Error: The Program has no label "string_sort"

Le code vert tient en un ret, dans un nouveau fichier string-sort.asm. Le source principal l’inclut après strcmp, que le tri va appeler (strsort/02-green) :

 org #4000
 include "strcmp.asm"
 include "string-sort.asm"

Deux pointeurs

Le test suivant donne deux pointeurs dans le mauvais ordre (strsort/03-red) :

// Runs string_sort on pointers to `texts`, and returns the texts in the order
// of the pointers the array holds after the run.
function sortStrings(texts: string[]) {
  const starts = startsOf(texts);
  const bytes = runStringSort(texts).memory(ARRAY, 2 * texts.length);
  return texts.map((_, i) => texts[starts.indexOf(bytes[2 * i] | (bytes[2 * i + 1] << 8))]);
}

it("swaps two pointers in the wrong order", () => {
  expect(sortStrings(["MOVE", "MODE"])).toEqual(["MODE", "MOVE"]);
});

AssertionError: expected [ 'MOVE', 'MODE' ] to deeply equal [ 'MODE', 'MOVE' ]

Le code vert compare la chaîne du deuxième pointeur, la clé, à celle du premier. strcmp reçoit la clé dans HL (S1) et l’autre chaîne dans DE (S2). Elle répond C si la clé vient avant, et les deux pointeurs s’échangent (strsort/04-green) :

string_sort:
 dec b
 ret z
 push hl
 ld e,(hl)
 inc hl
 ld d,(hl)      ; DE: the string of the first pointer
 inc hl
 ld a,(hl)
 inc hl
 ld h,(hl)
 ld l,a         ; HL: the key, the string of the second pointer
 call strcmp
 pop hl
 ret nc         ; the key does not come before the first string
 ld e,(hl)      ; swap the two pointers
 inc hl
 ld d,(hl)
 inc hl
 ld c,(hl)
 ld (hl),e
 inc hl
 ld a,(hl)
 ld (hl),d
 dec hl
 dec hl
 ld (hl),a
 dec hl
 ld (hl),c
 ret

strcmp change HL et DE : l’adresse du tableau passe sur la pile pendant l’appel. L’échange de deux mots de 16 bits garde quatre octets en vol, dans E, D, C et A.

Le dernier pointeur

Le troisième test part d’une suite triée, avec un dernier pointeur à placer tout devant (strsort/05-red) :

it("moves the last pointer to the front of a sorted run", () => {
  expect(sortStrings(["MERGE", "MODE", "MOVE", "MEMORY"])).toEqual([
    "MEMORY",
    "MERGE",
    "MODE",
    "MOVE",
  ]);
});

AssertionError: expected [ 'MERGE', 'MODE', 'MOVE', 'MEMORY' ] to deeply equal [ 'MEMORY', 'MERGE', 'MODE', 'MOVE' ]

Comme dans l’article sur l’insertion, une seule clé suffit pour ce test : la dernière. Elle laisse un trou dans le tableau. Tant que la clé vient avant la chaîne du pointeur à gauche du trou, ce pointeur passe dans le trou, et le trou recule d’une case (strsort/06-green) :

string_sort:
 dec b
 ret z
 ld e,b
 ld d,0
 ex de,hl
 add hl,hl
 add hl,de      ; HL: the last pointer
 ld e,(hl)
 inc hl
 ld d,(hl)      ; DE: the key, the string to insert
 dec hl
.shift:
 push hl        ; the hole
 dec hl
 ld a,(hl)
 dec hl
 ld l,(hl)
 ld h,a         ; HL: the string of the pointer before the hole
 ex de,hl       ; HL: the key (S1), DE: that string (S2)
 push hl        ; the key
 call strcmp
 pop de
 pop hl
 jr nc,.place   ; the key does not come before this string
 dec hl         ; move the pointer before the hole into the hole
 ld a,(hl)
 dec hl
 ld c,(hl)
 inc hl
 inc hl
 ld (hl),c
 inc hl
 ld (hl),a
 dec hl
 dec hl
 dec hl         ; HL: the new hole
 jr .shift
.place:
 ld (hl),e
 inc hl
 ld (hl),d
 ret

Le dernier pointeur est à 2(n − 1) octets du début : add hl,hl double n − 1, puis add hl,de ajoute l’adresse du tableau.

Dans .shift, HL sert à tout. Il lit le pointeur à gauche du trou, puis il devient ce pointeur, et le trou passe donc sur la pile. Après ex de,hl, HL tient la clé et DE l’autre chaîne, comme strcmp les attend. Et comme strcmp change HL et DE, la clé passe aussi sur la pile. Deux push et deux pop par comparaison, c’est le prix d’une clé de 16 bits.

Un point compte pour la suite. Sur deux chaînes égales, strcmp répond Z et NC, et jr nc,.place arrête la clé. Elle ne passe jamais devant une chaîne égale.

Cette boucle n’a pas de borne au début du tableau, comme celle de l’article sur l’insertion, et un test plus bas va le montrer.

Tous les pointeurs

Avec cinq pointeurs mélangés, le code vert ne suffit plus (strsort/07-red) :

it("sorts five pointers in any order", () => {
  expect(sortStrings(["MOVE", "MERGE", "MOVER", "MEMORY", "MODE"])).toEqual([
    "MEMORY",
    "MERGE",
    "MODE",
    "MOVE",
    "MOVER",
  ]);
});

AssertionError: expected [ 'MOVE', 'MERGE', 'MOVER', …(2) ] to deeply equal [ 'MEMORY', 'MERGE', 'MODE', …(2) ]

Rien n’a bougé : la dernière clé, MODE, vient après MEMORY, et s’arrête tout de suite. La boucle externe insère chaque pointeur à son tour, à partir du deuxième. L’adresse de la clé va sur la pile, sous le trou, pour que la passe suivante reparte de là (strsort/08-green) :

string_sort:
 dec b          ; one pass for each pointer but the first
 ret z
.next:
 inc hl
 inc hl         ; HL: the next pointer to insert
 push hl        ; the next pass starts from there
 ld e,(hl)
 ; …
.place:
 ld (hl),e
 inc hl
 ld (hl),d
 pop hl
 djnz .next
 ret

B compte les passes, et rien ne le touche dans .shift. Le contrat de strcmp paie ici : BC ne bouge pas pendant l’appel.

Deux MODE

Le test de stabilité passe dès son écriture. Il lit les adresses, car les textes ne suffisent pas (strsort/09-guard) :

// The two strings are equal: only their addresses, #9000 then #9004, tell them apart.
it("keeps two pointers to equal strings in their order", () => {
  expect(runStringSort(["MODE", "MODE"]).memory(ARRAY, 4)).toEqual([0x00, 0x90, 0x04, 0x90]);
});

La version cassée qu’il vise décale aussi sur une égalité : un jr z vers le décalage, juste avant le jr nc,.place. Tous les autres tests passent. Pour qui ne lit que les textes, le tableau est trié, avec deux “MODE” côte à côte. Seules les adresses montrent l’échange :

AssertionError: expected [ 4, 144, +0, 144 ] to deeply equal [ +0, 144, 4, 144 ]

À cheval sur une page

Le contrat ne met aucune contrainte de page. Un inc l à la place d’un inc hl est un raccourci tentant, qui coûte 1 NOP au lieu de 2. Il est faux dès qu’un pointeur ou une chaîne franchit une page. Le guard suivant place tout à cheval (strsort/10-guard) :

// The array runs into the next page: from #80FC, the page ends between two
// pointers, and from #80FD, inside one. MOVER also runs into the next page,
// from #90FE. MOVER is the key against MODE, then MOVE is the key against
// MOVER: each comparison reads past the end of the page, in one string and
// then the other.
it.each(["80FC", "80FD"])("sorts pointers and strings that cross a page, from #%s", (array) => {
  expect(sortStrings(["MODE", "MOVER", "MOVE", "MEMORY", "MERGE"], parseInt(array, 16), 0x90fa)).toEqual([
    "MEMORY",
    "MERGE",
    "MODE",
    "MOVE",
    "MOVER",
  ]);
});

Le guard prend deux tableaux, car un seul ne suffit pas. Depuis une adresse paire, chaque pointeur commence à une adresse paire, et le pas de son octet faible à son octet fort ne franchit jamais une page : avec le seul tableau à #80FC, cinq des mutants inc l passaient. Depuis #80FD, le pointeur à #80FF a son octet fort à #8100.

On a essayé les neuf versions cassées, une par inc hl ou inc de des deux Routines. Le guard en attrape huit. Par exemple, un inc l dans .place écrit l’octet fort de la clé au début de la même page, et le pointeur ne mène plus à aucune chaîne :

AssertionError: expected [ 'MODE', undefined, 'MEMORY', …(2) ] to deeply equal [ 'MEMORY', 'MERGE', 'MODE', …(2) ]

La neuvième touche le chargement de la clé, et le guard ne la voit pas. Le pointeur à cheval sur la page est celui de MOVER, déjà à sa place après MODE. La passe ratée laisse ce pointeur où il est, et l’ordre reste juste. Un autre guard, plus bas, l’attrape.

Le mur avant le tableau

Comme dans l’article sur l’insertion, la boucle .shift ne connaît pas le début du tableau. Une clé plus petite que tout va lire le pointeur d’avant. Mais avant #8000, la mémoire neuve de z80-tdd vaut #00, et le pointeur #0000 mène à un octet #00. Cette chaîne vient avant toutes les autres : la clé s’y arrête, par chance.

Le test place donc, juste avant le tableau, un pointeur vers ZONE, qui vient après toutes les chaînes du tableau (strsort/11-red) :

it("ignores a pointer to a larger string right before the array", () => {
  // The pointer right before the array, at ARRAY, points to ZONE, which comes
  // after every string of the array: a shift past the first pointer would move
  // it. Fresh memory would hold #0000 there, a pointer to #00, which comes before
  // every string: no key would move past it.
  const texts = ["ZONE", "MOVE", "MERGE", "MOVER", "MEMORY", "MODE"];
  const run = program.run("string_sort", {
    registers: { hl: ARRAY + 2, b: 5 },
    memory: [
      { at: ARRAY, bytes: startsOf(texts, STRINGS).flatMap((at) => [at & 0xff, at >> 8]) },
      { at: STRINGS, bytes: texts.flatMap(bytesOf) },
    ],
  });

  expect(run).toChangeOnly({ address: ARRAY + 2, length: 10 });
  expect(textsOf(run.memory(ARRAY + 2, 10), texts, STRINGS)).toEqual([
    "MEMORY",
    "MERGE",
    "MODE",
    "MOVE",
    "MOVER",
  ]);
});

Le test échoue pour la bonne raison. Dès la première passe, la clé MERGE passe devant ZONE : le pointeur de ZONE entre dans le tableau, et celui de MERGE en sort, à #8000. À la fin, #8000 tient le pointeur de MEMORY, #9012. Son octet fort, #90, est celui de ZONE, et seul l’octet faible change :

Error: Memory changed outside #8002-#800B:
  #8000  #00 -> #12

La borne est un compteur, comme pour l’insertion. C compte les pointeurs de la suite triée, et B en reçoit une copie à chaque passe : la clé ne peut pas passer plus de B pointeurs. djnz .shift remplace jr .shift. Le compteur des passes et C vont sur la pile, avec un push bc (strsort/12-green) :

string_sort:
 dec b          ; one pass for each pointer but the first
 ret z
 ld c,0
.next:
 inc c          ; C: the pointers of the sorted run
 inc hl
 inc hl         ; HL: the next pointer to insert
 push bc
 push hl        ; the next pass starts from there
 ld b,c         ; B: the pointers the key can still move past
 ld e,(hl)
 inc hl
 ld d,(hl)      ; DE: the key, the string to insert
 dec hl
.shift:
 push hl        ; the hole
 dec hl
 ld a,(hl)
 dec hl
 ld l,(hl)
 ld h,a         ; HL: the string of the pointer before the hole
 ex de,hl       ; HL: the key (S1), DE: that string (S2)
 push hl        ; the key
 call strcmp
 pop de
 pop hl
 jr nc,.place   ; the key does not come before this string
 dec hl         ; move the pointer before the hole into the hole
 ld a,(hl)
 dec hl
 ld c,(hl)      ; C is free: the count is on the stack
 inc hl
 inc hl
 ld (hl),c
 inc hl
 ld (hl),a
 dec hl
 dec hl
 dec hl         ; HL: the new hole
 djnz .shift    ; at 0, the hole is the first pointer: the key goes first
.place:
 ld (hl),e
 inc hl
 ld (hl),d
 pop hl
 pop bc
 djnz .next
 ret

C sert encore au décalage : son compte est sur la pile, et pop bc le rend en fin de passe. L’astuce du dec l de l’insertion n’a pas d’équivalent ici. Quand B tombe à zéro, HL pointe déjà sur le trou, et .place écrit au bon endroit.

Le mur après le tableau

Le guard suivant pose, juste après le tableau, un pointeur vers AUTO, qui vient avant tout (strsort/13-guard) :

it("ignores a pointer to a smaller string right after the array", () => {
  // Right after the array, a pointer to AUTO, which comes before every string
  // of the array: a pass too many would move it. The array starts at #80FD, so
  // its second pointer lies across the end of the page: an inc l in place of an
  // inc hl would read its high byte at #8000, not at #8100.
  const array = 0x80fd;
  const texts = ["MOVE", "MERGE", "MOVER", "MEMORY", "MODE", "AUTO"];
  // …
  expect(run).toChangeOnly({ address: array, length: 10 });
  // …
});

Une passe de trop insérerait AUTO, mais elle fait déjà tomber les huit autres tests du tri. Le vrai gibier de ce guard est la neuvième version cassée du guard de page, celle qui charge la clé par inc l :

 ld e,(hl)
 inc l
 ld d,(hl)      ; DE: the key, the string to insert
 dec hl

Le tableau commence à #80FD, et son deuxième pointeur a son octet faible à #80FF. inc l lit l’octet fort à #8000, puis dec hl recule à #7FFF. La passe prend #7FFF pour le trou, et écrit hors du tableau :

Error: Memory changed outside #80FD-#8106:
  #7FFF  #00 -> #04

Avec ce guard, les neuf mutants inc l et inc e tombent.

Six façons de garder la clé

Tout est vert, et le code est juste. Mais la clé coûte cher : chaque comparaison la remet sur la pile, puis la reprend, car strcmp change HL et DE. Avant de fixer les budgets, on a mesuré d’autres plans de registres. La clé peut vivre dans IY, et revenir dans DE par ld e,iyl et ld d,iyh. Ces deux instructions ne sont pas documentées, mais RASM les assemble et z80-tdd les exécute. La clé pourrait aussi s’écrire dans l’opérande d’un ld hl,nn, par du code qui se modifie, mais ce code écrit dans le Program, et les deux tests toChangeOnly le rejettent. Le décalage peut passer par deux LDD. Et le tri peut entrer dans strcmp après son ex de,hl, par le label .loop.

Voici les six variantes qui ont tourné, pour n = 32. Les colonnes « triée », « inversée » et « égales » sont à k = 0. La colonne « préfixe » donne une entrée inversée dont les chaînes ont 16 lettres communes. « Par décalage » et « par passe » donnent le coût d’un pointeur décalé et d’une passe qui s’arrête à sa première comparaison, à k = 0.

Aucune variante ne gagne partout. IY économise 3 NOPs par comparaison : ld e,iyl et ld d,iyh coûtent 4 NOPs, contre 7 pour push hl et pop de. Mais charger la clé dans IY, puis l’écrire dans le trou, coûte 8 NOPs de plus par passe. Les deux LDD ne gagnent que si DE est libre. Avec la clé dans DE, il faut la sauver autour de la copie, et le décalage passe de 79 à 82 NOPs.

L’entrée par strcmp.loop lie le tri au code interne de strcmp, et donne à strcmp un second point d’entrée. Il reste IY avec deux LDD : 8 % de gain sur l’entrée inversée à k = 0, mais 2 % seulement avec un préfixe de 16 lettres, car strcmp pèse de plus en plus. Et cette variante perd 5 NOPs par passe sur une entrée triée ou égale.

On a gardé la version de 13-guard. Elle est la plus rapide sur une entrée triée ou égale, à égalité avec « pile, 2 LDD », et la plus petite. Elle ne touche ni IX ni IY.

IX et IY

Le contrat le dit maintenant, en tête de string-sort.asm :

; Sorts the n pointers of the array at HL, B = n from 1 to 255, in the order of
; their strings, as strcmp compares them. Each pointer takes two bytes, low byte
; first. The strings do not move. Two pointers to equal strings keep their
; order. AF, BC, DE and HL change, IX and IY do not.

Un guard le vérifie (strsort/14-guard) :

it("leaves IX and IY as they are", () => {
  expect(
    runStringSort(["MOVE", "MERGE", "MOVER", "MEMORY", "MODE"], ARRAY, STRINGS, { ix: 0x1234, iy: 0x5678 }),
  ).toHaveRegisters({ ix: 0x1234, iy: 0x5678 });
});

La version cassée est la variante « IY, copie » de la mesure. Elle trie juste, et seul ce guard tombe. IY garde la dernière clé, le pointeur de MODE :

Error: Registers differ:
  IY  expected #5678, received #9014

Les NOPs d’une passe

Chaque durée vient de la table de Madram. L’entrée coûte 5 NOPs : dec b 1, ret z non pris 2, ld c,0 2. Le ret final en coûte 3.

Chaque passe paie 38 NOPs hors comparaisons. Le début de .next en coûte 22 : inc c 1, deux inc hl 4, push bc 4, push hl 4, ld b,c 1, puis 8 pour charger la clé. .place en coûte 12, avec ses deux pop, et djnz .next 4. Le dernier djnz .next n’est pas pris, et ne coûte que 3. La partie fixe vaut donc 7 + 38(n − 1) NOPs.

Une comparaison coûte 29 NOPs autour de strcmp : les deux push 8, les cinq instructions qui lisent le pointeur 9, ex de,hl 1, call 5, les deux pop 6. On note c le coût de strcmp, son ret compris. Une clé qui s’arrête ajoute jr nc pris, 3 NOPs : 32 + c. Une clé qui décale ajoute jr nc non pris 2, les douze instructions du décalage 24, et djnz .shift 4 : 59 + c. Si la clé va en tête, le dernier djnz .shift n’est pas pris, et ce décalage coûte 58 + c.

À k = 0, strcmp coûte 20 NOPs, moins que les 29 NOPs de colle autour de l’appel.

Sur une entrée triée, chaque passe fait une comparaison, qui arrête la clé après k lettres égales. Avec c = 14k + 20, une passe coûte 38 + 32 + 14k + 20, soit 90 + 14k NOPs. Le total est (n − 1)(90 + 14k) + 7 NOPs.

Sur des chaînes égales de L lettres, c’est le même chemin, avec c = 14L + 4 : (n − 1)(74 + 14L) + 7 NOPs.

Sur une entrée inversée, la passe i décale i pointeurs, et la clé va en tête. Elle coûte 38 + i(59 + 14k + 20) − 1, soit 37 + i(79 + 14k) NOPs. La somme de i, de 1 à n − 1, vaut n(n − 1)/2. Le total est (n − 1)(n(79 + 14k)/2 + 37) + 7 NOPs.

Les budgets

Les entrées des budgets se fabriquent avec un helper, withPrefix : n chaînes de k lettres “A”, suivies d’une lettre qui les départage, dans l’ordre. Le premier budget les prend telles quelles, et chaque clé s’arrête à sa première comparaison (strsort/15-guard) :

// n strings with the same k letters, then a last letter that tells them
// apart, in order: each comparison finds k equal letters, then two different ones.
function withPrefix(n: number, k: number) {
  return Array.from({ length: n }, (_, i) => "A".repeat(k) + String.fromCharCode(i));
}

// Each key stops at its first comparison.
it.each([
  [2, 0],
  [2, 8],
  [16, 0],
  [16, 8],
  [128, 0],
  [128, 8],
])("sorts %i sorted pointers after %i equal letters in (n − 1)(90 + 14k) + 7 NOPs at most", (n, k) => {
  expect(runStringSort(withPrefix(n, k)).nops).toBeLessThanOrEqual((n - 1) * (90 + 14 * k) + 7);
});

La dernière lettre va de #00 à #7F : n s’arrête à 128, car une lettre tient sur 7 bits. La version cassée est encore « IY, copie ». Elle perd 5 NOPs par passe, et sept tests tombent, celui d’IX et IY compris :

AssertionError: expected 102 to be less than or equal to 97

Le budget de l’entrée inversée prend les mêmes chaînes à l’envers (strsort/16-guard) :

// Each key moves past the whole sorted run, with no comparison to stop it.
// 128 reversed pointers after 8 equal letters take more than a million NOPs.
it.each([
  [2, 0],
  [2, 8],
  [16, 0],
  [16, 8],
  [128, 0],
  [128, 8],
])("sorts %i reversed pointers after %i equal letters in n(n − 1)/2 · (79 + 14k) + 37(n − 1) + 7 NOPs at most", (n, k) => {
  const run = runStringSort(withPrefix(n, k).reverse(), ARRAY, STRINGS, { nopLimit: 2_000_000 });

  expect(run.nops).toBeLessThanOrEqual(((n * (n - 1)) / 2) * (79 + 14 * k) + 37 * (n - 1) + 7);
});

128 pointeurs inversés, après 8 lettres communes, demandent 1 557 154 NOPs. La limite par défaut d’un Run est 1 000 000 NOPs, d’où le nopLimit. La version cassée est « pile, 2 LDD » : elle passe le budget de l’entrée triée, car elle ne change que le décalage. Ici, elle perd 3 NOPs par décalage, et les six tests tombent :

AssertionError: expected 126 to be less than or equal to 123

Le troisième budget prend des chaînes égales de L lettres. Chaque clé s’arrête à sa première comparaison, qui lit les L lettres des deux chaînes (strsort/17-guard) :

// A key never moves past a string equal to it: each key stops at its first
// comparison, which reads the L letters of both strings.
it.each([
  [2, 1],
  [2, 8],
  [16, 1],
  [16, 8],
  [128, 1],
  [128, 8],
])("sorts %i pointers to equal strings of %i letters in (n − 1)(74 + 14L) + 7 NOPs at most", (n, length) => {
  const equal = Array.from({ length: n }, () => "A".repeat(length));

  expect(runStringSort(equal).nops).toBeLessThanOrEqual((n - 1) * (74 + 14 * length) + 7);
});

La version cassée ajoute un nop avant le ret des chaînes égales de strcmp. Les six tests tombent :

AssertionError: expected 96 to be less than or equal to 95

Les trois bornes sont exactes : chaque Run de budget tombe pile sur sa formule, et une version plus lente d’un seul NOP échoue.

Un seul helper

La dernière étape ne touche que les tests (strsort/18-refactor). Les deux tests des murs écrivaient leur propre Run : ils passent par runStringSort, qui prend un objet d’options. Les cinq chaînes mélangées et leur ordre trié deviennent deux constantes, UNSORTED et SORTED. Le budget de l’entrée inversée prend la forme des deux autres, (n − 1)(n(79 + 14k)/2 + 37) + 7, de même valeur.

Les 48 tests restent verts, 28 pour le tri et 20 pour strcmp.

Conclusion

string_sort trie un tableau de pointeurs vers des chaînes, et les chaînes ne bougent pas. Les tests ont d’abord suivi ceux de l’insertion des octets, puis ils ont posé ce que les octets ne pouvaient pas montrer : deux chaînes égales gardent leur ordre, et seules leurs adresses le prouvent. Un pointeur ou une chaîne peut franchir une page, et il faut deux tableaux pour le vérifier. La mesure des plans de registres a gardé la version la plus simple, avec la clé sur la pile. Chaque budget tombe pile sur sa formule : (n − 1)(90 + 14k) + 7 NOPs sur une entrée triée, (n − 1)(n(79 + 14k)/2 + 37) + 7 sur une entrée inversée, (n − 1)(74 + 14L) + 7 sur des chaînes égales.

Le tri a ses conditions d’emploi :

• 1 à 255 pointeurs, vers des chaînes au format du firmware, comme strcmp les attend ;
• un coût en n² sur une entrée inversée, que les lettres communes alourdissent encore : 1 557 154 NOPs pour 128 pointeurs après 8 lettres communes ;
• 29 NOPs de colle autour de chaque appel à strcmp, plus que strcmp elle-même à k = 0 ;
• AF, BC, DE et HL changent, IX et IY ne bougent pas.

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 strsort du dépôt z80-tdd-sorts. Elle part de strcmp/15-guard, et pas de main : le tri appelle strcmp, comme la sélection appelait find_min. Pour rejouer une étape :

git checkout strsort/01-red
pnpm install
pnpm test

Les tests du tri sont dans src/string-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 : strcmp, comparer deux chaînes à bit 7 final
• Le tri par insertion des octets, dont ce tri reprend la forme
• Le radix sort, le tri par comptage, le tri à bulles 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 strsort)
• RASM, l’assembleur d’Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), la table des durées en NOPs