TDD sur CPC : strcmp, comparer deux chaînes à bit 7 final

24/10/2026Z80CPCTDDtri

Jusqu’ici, la série triait des nombres : des octets, puis des clés de 16 bits avec le radix sort. Pour trier des noms, on trie plutôt des pointeurs vers les chaînes, et les chaînes ne bougent pas. Mais il faut d’abord savoir comparer deux chaînes. Or le firmware du CPC marque la fin d’un nom dans sa dernière lettre. Comment comparer deux chaînes, quand cette marque change l’octet de la lettre ?

La réponse porte le nom de sa cousine du C, strcmp, et sort des tests un par un, en Z80. Le prochain article la réutilisera dans un tri, comme le tri par sélection a réutilisé find_min, et le compte des NOPs finira par donner un budget à chaque chemin de la routine.

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

En C, une chaîne finit par un octet nul. Les tables de noms du firmware du CPC font autrement : elles mettent à 1 le bit 7 de la dernière lettre. Les noms des commandes RSX sont écrits ainsi. “AB” s’écrit donc #41 #C2, et “A” s’écrit #C1.

Ce format a deux conséquences. Une chaîne a au moins une lettre, car la marque de fin est portée par une lettre. Et chaque lettre tient sur 7 bits, de #00 à #7F. La lettre #00 fait partie du contrat : elle n’a rien d’une fin de chaîne ici.

HL pointe sur la première chaîne, S1, et DE sur la seconde, S2. strcmp répond comme CP comparerait S1 à S2 : Z si les chaînes sont égales, C si S1 vient avant S2. Un jr c ou un jr z après l’appel se lit donc comme après un CP.

L’ordre est celui des codes ASCII, sans rien de plus. “B” vient avant “a”, car #42 est plus petit que #61. Une chaîne vient avant une chaîne plus longue qui commence par elle : “A” avant “AB”.

A, HL et DE sont libres. BC ne bouge pas : le tri qui appellera strcmp gardera son compteur dans B.

Lancez l’animation, ou avancez étape par étape. La première rangée est S1, la seconde S2 : chaque case montre un octet, avec sa lettre au-dessus. La flèche montre la lettre comparée, et un fond coloré marque la lettre qui décide. L’animation suit la version finale de la routine, écrite plus bas.

Comparer les octets bruts donnerait l’inverse : #C1 est plus grand que #41. C’est le piège du format, et les tests vont le rencontrer deux fois.

Le premier test

Le source principal n’inclut que la nouvelle routine :

 org #4000
 include "strcmp.asm"

Dans les tests de cet article, S1 est à #8000 et S2 à #8100, au format du firmware. La réponse est dans les drapeaux. Chaque test part de Z et C à 1, ce que CP ne donne jamais : Z veut dire égal, C veut dire plus petit. Une routine qui oublie de répondre laisse ces drapeaux, et le test lit « inchangé ». Elle ne peut pas passer par hasard.

Le premier test compare “A” à “A” :

// The bytes of `text`: one per letter, bit 7 set on the last one, as the CPC firmware writes them.
function bytesOf(text: string) {
  return Array.from(text, (letter, i) => letter.charCodeAt(0) | (i === text.length - 1 ? 0x80 : 0));
}

// Runs strcmp on `a` and `b`. The Run starts with Z and C both set, which no
// CP leaves.
function runStrcmp(a: string, b: string) {
  return program.run("strcmp", {
    registers: { hl: STRING_A, de: STRING_B },
    flags: { z: true, c: true },
    memory: [
      { at: STRING_A, bytes: bytesOf(a) },
      { at: STRING_B, bytes: bytesOf(b) },
    ],
  });
}

// Reads the answer of strcmp in the flags, as after CP: a Routine that keeps
// the flags as they are gives "unchanged", never a valid answer.
function compare(a: string, b: string) {
  const { z, c } = runStrcmp(a, b).flags;

  if (z && c) return "unchanged";
  if (z) return "=";
  return c ? "<" : ">";
}

it("finds two equal one-letter strings equal", () => {
  expect(compare("A", "A")).toBe("=");
});

Le test échoue faute de label (strcmp/01-red) :

Error: The Program has no label "strcmp"

Dans l’article du radix, un simple ret passait le premier test. Ici, il ne suffit pas, car il laisse Z et C à 1. Le moins de code possible met Z à 1 et C à 0, et c’est un cp a (strcmp/02-green) :

; Compares the strings at HL (S1) and DE (S2), as CP would compare S1 with S2:
; Z if they are equal, C if S1 comes first. Each letter takes 7 bits, and bit 7
; marks the last letter of a string, as in the CPC firmware. A string comes
; before a longer string that starts with it. A, HL and DE change, BC does not.
strcmp:
 cp a
 ret

Toutes les chaînes sont égales pour cette version. Le prochain test va la contredire.

Une lettre, puis une boucle

Le test suivant compare deux chaînes d’une lettre, dans un sens puis dans l’autre (strcmp/03-red) :

it("orders two one-letter strings by their letter", () => {
  expect(compare("A", "B")).toBe("<");
  expect(compare("B", "A")).toBe(">");
});

AssertionError: expected '=' to be '<' // Object.is equality

Le code vert compare le premier octet de S1 au premier octet de S2 (strcmp/04-green) :

strcmp:
 ld a,(hl)
 ex de,hl
 cp (hl)
 ret

CP compare A à un octet pointé par HL, jamais par DE. S1 passe donc dans A, et ex de,hl met S2 sous HL.

Le test d’après prend deux chaînes qui ne diffèrent qu’à la deuxième lettre (strcmp/05-red) :

it("orders two strings by their first different letter", () => {
  expect(compare("AB", "AC")).toBe("<");
  expect(compare("AC", "AB")).toBe(">");
});

Le premier octet est le même, et la routine répond « égales ». Il faut une boucle (strcmp/06-green) :

strcmp:
 ex de,hl       ; DE: S1, HL: S2
.loop:
 ld a,(de)
 cp (hl)
 ret nz         ; the first different byte decides
 inc de
 inc hl
 rla            ; C: bit 7, set on the last letter of both strings
 jr nc,.loop
 cp a           ; Z, NC: equal
 ret

L’échange se fait une fois, avant la boucle : DE suit S1, HL suit S2. Le premier octet différent décide, et ret nz sort avec les drapeaux de CP. Si les deux octets sont égaux, ils ont le même bit 7 : les deux chaînes finissent sur cette lettre, ou aucune. rla pousse ce bit dans C, et la boucle continue tant qu’il vaut 0. A ne sert plus après le CP, et rla coûte 1 NOP. À la sortie, cp a répond « égales ».

Le piège du bit 7

Le cas suivant met une chaîne face à une chaîne plus longue qui commence par elle (strcmp/07-red) :

// "A" is #C1 and "AB" is #41 #C2: the first bytes differ by bit 7 alone.
it("puts a string before a longer string that starts with it", () => {
  expect(compare("A", "AB")).toBe("<");
  expect(compare("AB", "A")).toBe(">");
});

AssertionError: expected '>' to be '<' // Object.is equality

La lettre est la même, A, mais pas l’octet. La marque de fin de “A” fait de #C1 un octet plus grand que #41, et la chaîne courte passe derrière. On ne peut pas comparer les octets bruts.

Le premier code vert traite ce cas à part. Un XOR des deux octets donne les bits qui diffèrent. S’il vaut #80, seule la marque de fin diffère : c’est la même lettre, et une seule chaîne finit dessus (strcmp/08-green) :

 jr nz,.differ
 ; …
.differ:
 xor (hl)       ; A: the bits where the two bytes differ
 cp #80
 ld a,(de)
 jr z,.one_ends ; the same letter, but only one string ends on it
 cp (hl)
 ret
.one_ends:
 add a,a        ; C: bit 7, set if S1 ends: the shorter string comes first
 ret

Dans .one_ends, A contient l’octet de S1. Si S1 finit, son bit 7 est à 1, et add a,a le fait passer dans C : S1 vient avant.

Le test suivant prend des lettres qui diffèrent, avec une seule chaîne qui finit (strcmp/09-red) :

// "A" is #C1 and "BC" is #42 #C3: bit 7 of #C1 must not make "A" larger than "B".
it("compares the last letter of a string without its end mark", () => {
  expect(compare("A", "BC")).toBe("<");
  expect(compare("BC", "A")).toBe(">");
});

AssertionError: expected '>' to be '<' // Object.is equality

Ici, le XOR vaut #83, et le cas à part ne s’applique pas. CP compare #C1 à #42, et le bit 7 décide encore à la place de la lettre.

Le bon code vert ne traite pas un cas de plus. Il donne à l’octet de S1 le bit 7 de S2, puis il compare (strcmp/10-green) :

.differ:
 xor (hl)
 and #80        ; A: #80 if only one string ends on this letter, else #00
 ex de,hl
 xor (hl)       ; A: the byte of S1, with the bit 7 of S2
 ex de,hl
 cp (hl)
 ret nz         ; the letters differ: they decide
 ld a,(de)      ; the same letter, but only one string ends on it
 add a,a        ; C: bit 7, set if S1 ends: the shorter string comes first
 ret

AND #80 garde le seul bit 7 de la différence. Un XOR de ce masque avec l’octet de S1 inverse son bit 7 si les deux bits 7 diffèrent. Les deux octets ont alors le même bit 7, et CP compare les lettres sur 7 bits. Si elles diffèrent, ses drapeaux répondent. Si elles sont égales, une seule chaîne finit sur cette lettre, et add a,a répond comme avant.

Les deux ex de,hl sont là car XOR ne lit pas la mémoire par DE. Garder l’octet de S1 dans un registre serait plus simple, mais E et D portent le pointeur de S1, que ld a,(de) relit plus bas, et C est pris.

BC ne bouge pas

C est pris par le contrat : BC ne bouge pas. Le guard suivant le vérifie sur quatre paires, une par cas du format vu jusqu’ici (strcmp/11-guard) :

// The sort that calls strcmp keeps its count in B.
it.each([
  ["A", "A"],
  ["AB", "AC"],
  ["A", "AB"],
  ["A", "BC"],
])("keeps BC as it is, on %s and %s", (a, b) => {
  expect(runStrcmp(a, b, 0x1234)).toHaveRegisters({ bc: 0x1234 });
});

La version cassée qu’il vise est celle qu’on écrirait sans le contrat : ld c,a garde l’octet de S1, et xor c remplace les deux ex de,hl. Toutes les comparaisons restent justes. Seul le guard voit C changer, sur les trois paires qui passent par .differ. C y reçoit l’octet de S1 : #C2 pour “AB” et “AC”, #C1 pour les deux autres. La première paire donne :

Error: Registers differ:
  BC  expected #1234, received #12C2

La lettre #00

Il reste la lettre #00. “\0” s’écrit #80, et “\0\0” s’écrit #00 #80 (strcmp/12-red) :

// "\0" is #80 and "\0\0" is #00 #80: twice #80 is #00, which sets Z.
it("puts a string that ends on the letter #00 before a longer one", () => {
  expect(compare("\0", "\0\0")).toBe("<");
  expect(compare("\0\0", "\0")).toBe(">");
});

AssertionError: expected 'unchanged' to be '<' // Object.is equality

add a,a sur #80 donne #00, avec C à 1 mais aussi Z à 1. Le test lit « inchangé », une réponse que CP ne donne jamais. Pour toute autre lettre, le résultat n’est pas nul, et le bug ne se voit pas.

Le code vert force les sept bits du bas à 1 avant l’addition (strcmp/13-green) :

 ld a,(de)      ; the same letter, but only one string ends on it
 or #7f         ; NZ after the ADD, even for the letter #00
 add a,a        ; C: bit 7, set if S1 ends: the shorter string comes first
 ret

A vaut #FF ou #7F, et add a,a donne #FE dans les deux cas : jamais Z.

L’octet de S1 dans E

Tout est vert, mais .differ pèse lourd : deux ex de,hl, une relecture de S1, un or #7f.

On regarde alors le dernier chemin de plus près. Après le cp (hl) qui donne Z, A contient l’octet de S1 avec le bit 7 de S2 : c’est l’octet de S2. Les deux octets d’origine ne diffèrent que par le bit 7. S2 − S1 vaut donc +#80 ou −#80, jamais zéro. Et la soustraction déborde si S1 a le bit 7 à 1, c’est-à-dire si S1 finit. Un sub avec l’octet de S1 répond tout seul : NZ, et C si S1 vient avant, même pour la lettre #00.

Il faut l’octet de S1 sous la main. Après le cp (hl), plus rien ne lit S1 par DE : E est libre, et il peut garder l’octet (strcmp/14-refactor) :

.differ:
 ld e,a         ; E: the byte of S1
 xor (hl)
 and #80        ; A: #80 if only one string ends on this letter, else #00
 xor e          ; A: the byte of S1, with the bit 7 of S2
 cp (hl)
 ret nz         ; the letters differ: they decide
 sub e          ; the same letter, but only one string ends on it. A: the byte
                ; of S2 minus the byte of S1, never zero, and C if S1 ends: the
                ; shorter string comes first
 ret

Les deux ex de,hl disparaissent, comme la relecture de S1 et le or #7f. .differ passe de 13 à 9 octets. Les dix tests restent verts. Le chemin des lettres différentes gagne 2 NOPs, celui de la chaîne qui finit en gagne 6. C’est cette version que montre l’animation.

Le compte à la main

Avant le dernier guard, qui porte sur le temps, il faut compter, avec la table de Madram. k y désigne les lettres égales sur 7 bits avant la lettre qui décide. Une chaîne qui finit sur la k-ième lettre la compte. “A” et “AB” ont donc une lettre égale, le A, même si leurs premiers octets diffèrent.

Une lettre égale coûte 14 NOPs : ld a,(de) 2, cp (hl) 2, jr nz non pris 2, inc de 2, inc hl 2, rla 1, jr nc pris 3. Chaque chemin commence par ex de,hl, 1 NOP.

Avant le refactor, les deux derniers chemins coûtaient 14k + 22 et 14k + 14 NOPs.

Le budget

Le guard du budget donne à chaque chemin son propre test et sa borne (strcmp/15-guard) :

// k counts the letters equal on 7 bits before the one that decides. A string
// that ends on the k-th letter counts it: "A" and "AB" have one equal letter.
it.each([0, 1, 10, 200])("compares after %i equal letters in 14k + 20 NOPs at most", (k) => {
  const prefix = "A".repeat(k);

  expect(runStrcmp(prefix + "B", prefix + "C").nops).toBeLessThanOrEqual(14 * k + 20);
});

it.each([1, 10, 200])("finds the end of a string after %i equal letters in 14k + 8 NOPs at most", (k) => {
  const prefix = "A".repeat(k);

  expect(runStrcmp(prefix, prefix + "B").nops).toBeLessThanOrEqual(14 * k + 8);
});

it.each([1, 10, 200])("finds two equal strings of %i letters in 14k + 4 NOPs at most", (k) => {
  const text = "A".repeat(k);

  expect(runStrcmp(text, text).nops).toBeLessThanOrEqual(14 * k + 4);
});

Les trois bornes sont exactes : avec toBe à la place de toBeLessThanOrEqual, les vingt tests passent aussi.

La première version cassée qu’il attrape est le .differ de 13-green, avant le refactor. Les sept tests des deux premiers chemins tombent, de 2 NOPs pour les lettres différentes, de 6 pour une chaîne qui finit :

AssertionError: expected 22 to be less than or equal to 20
AssertionError: expected 28 to be less than or equal to 22

La seconde touche la boucle. Elle lit la marque de fin par bit 7,(hl), au lieu de pousser A dans C par rla :

 inc de
 bit 7,(hl)
 inc hl
 jr z,.loop

Le code reste juste, et il garde A intact, mais A ne sert plus à rien à cet endroit. bit 7,(hl) coûte 3 NOPs et jr z 3, contre 1 et 3 : 16 NOPs par lettre. Les trois tests des chaînes égales tombent, avec cinq autres :

AssertionError: expected 3204 to be less than or equal to 2804

À k = 1, une chaîne qui finit ne fait aucun tour complet de boucle. Ce test-là passe avec la seconde version cassée, mais il attrape la première.

Conclusion

strcmp compare deux chaînes au format du firmware, et répond comme CP. Le format cachait trois pièges : le bit 7 d’une chaîne qui finit ne doit pas compter comme une lettre, ni écraser la lettre qui décide, et la lettre #00 est une lettre comme les autres. Le refactor a gardé l’octet de S1 dans E, et une seule soustraction a remplacé le cas à part. Chaque chemin a maintenant un budget exact : 14k + 20, 14k + 8 et 14k + 4 NOPs.

Son contrat reste étroit :

• des chaînes au format du firmware, d’au moins une lettre, chaque lettre sur 7 bits ;
• l’ordre des codes ASCII, sans rien de plus : “B” vient avant “a” ;
• A, HL et DE changent, et seul BC est gardé.

Le prochain article triera un tableau de pointeurs vers des chaînes, par insertion, avec strcmp comme comparaison. Les chaînes ne bougeront pas, et B gardera son compteur.

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 strcmp du dépôt z80-tdd-sorts. Elle part de main, comme les autres. Pour rejouer une étape :

git checkout strcmp/01-red
pnpm install
pnpm test

Les tests de la routine sont dans src/strcmp.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 radix sort sur des clés de 16 bits
• Le tri par comptage, 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 strcmp)
• RASM, l’assembleur d’Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), la table des durées en NOPs