TDD on the CPC: strcmp, comparing two strings that end on bit 7

24/10/2026Z80CPCTDDsorting

So far, the series sorted numbers: bytes, then 16-bit keys with radix sort. To sort names, we sort pointers to the strings instead, and the strings stay where they are. But first we must know how to compare two strings. And the CPC firmware marks the end of a name in its last letter. How do we compare two strings, when this mark changes the byte of the letter?

The answer bears the name of its C cousin, strcmp, and it grows in Z80 out of the tests, one after the other. The next post will reuse it in a sort, as selection sort reused find_min, and in the end, the NOPs counted by hand will give each path of the routine a budget.

The method is the one of the post on find_min, to read first if TDD is new to you.

What the routine does

In C, a string ends with a zero byte. The name tables of the CPC firmware do it another way: they set bit 7 of the last letter. The names of the RSX commands are written like this. So “AB” is #41 #C2, and “A” is #C1.

This format has two results. A string has at least one letter, because a letter carries the end mark. And each letter takes 7 bits, from #00 to #7F. The letter #00 is part of the contract: here, it is not the end of a string.

HL points to the first string, S1, and DE to the second, S2. strcmp answers as CP would compare S1 with S2: Z if the strings are equal, C if S1 comes before S2. So a jr c or a jr z after the call reads as after a CP.

The order is that of the ASCII codes, with nothing more. “B” comes before “a”, because #42 is smaller than #61. A string comes before a longer string that starts with it: “A” before “AB”.

A, HL and DE are free. BC does not change: the sort that will call strcmp will keep its count in B.

Play the animation, or go step by step. The first row is S1, the second S2: each cell shows a byte, with its letter above it. The arrow shows the letter being compared, and a filled background marks the letter that decides. The animation follows the final version of the routine, written further down.

Comparing the raw bytes would give the opposite: #C1 is larger than #41. This is the trap of the format, and the tests will meet it twice.

The first test

The main source includes only the new routine:

 org #4000
 include "strcmp.asm"

In the tests of this post, S1 is at #8000 and S2 at #8100, in the firmware format. The answer is in the flags. Each test starts with Z and C set, which CP never gives: Z means equal, C means smaller. A routine that forgets to answer leaves these flags, and the test reads “unchanged”. It cannot pass by chance.

The first test compares “A” with “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("=");
});

The test fails for want of a label (strcmp/01-red):

Error: The Program has no label "strcmp"

In the radix post, a plain ret passed the first test. Here, it is not enough, because it leaves Z and C set. The least code that sets Z and clears C is a 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

For this version, all strings are equal. The next test will prove it wrong.

One letter, then a loop

The next test compares two one-letter strings, one way then the other (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

The green code compares the first byte of S1 with the first byte of S2 (strcmp/04-green):

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

CP compares A with a byte at HL, never at DE. So S1 goes into A, and ex de,hl puts S2 under HL.

The test after that takes two strings that differ only at the second letter (strcmp/05-red):

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

The first byte is the same, and the routine answers “equal”. We need a loop (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

The swap happens once, before the loop: DE follows S1, HL follows S2. The first different byte decides, and ret nz leaves with the flags of CP. If the two bytes are equal, they have the same bit 7: both strings end on this letter, or neither does. rla pushes this bit into C, and the loop goes on while it is 0. A has no more use after the CP, and rla costs 1 NOP. At the exit, cp a answers “equal”.

The bit 7 trap

The next case puts a string against a longer string that starts with it (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

The letter is the same, A, but not the byte. The end mark of “A” makes #C1 a larger byte than #41, and the short string goes behind. We cannot compare the raw bytes.

The first green code treats this case apart. An XOR of the two bytes gives the bits that differ. If it is #80, only the end mark differs: it is the same letter, and only one string ends on it (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

In .one_ends, A holds the byte of S1. If S1 ends, its bit 7 is set, and add a,a moves it into C: S1 comes first.

The next test takes letters that differ, with only one string that ends (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

Here, the XOR is #83, and the special case does not apply. CP compares #C1 with #42, and bit 7 decides again in place of the letter.

The right green code does not treat one more case. It gives the byte of S1 the bit 7 of S2, then it compares (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 keeps only bit 7 of the difference. An XOR of this mask with the byte of S1 flips its bit 7 if the two bits 7 differ. The two bytes then have the same bit 7, and CP compares the letters on 7 bits. If they differ, its flags answer. If they are equal, only one string ends on this letter, and add a,a answers as before.

The two ex de,hl are there because XOR does not read memory through DE. Keeping the byte of S1 in a register would be simpler, but E and D hold the pointer to S1, which ld a,(de) reads again below, and C is taken.

BC does not change

The contract takes C: BC does not change. The next guard checks it on four pairs, one for each case of the format so far (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 });
});

The broken version it targets is the one we would write without the contract: ld c,a keeps the byte of S1, and xor c replaces the two ex de,hl. All the comparisons stay right. Only the guard sees C change, on the three pairs that go through .differ. C gets the byte of S1 there: #C2 for “AB” and “AC”, #C1 for the other two. The first pair gives:

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

The letter #00

The letter #00 remains. “\0” is #80, and “\0\0” is #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 on #80 gives #00, with C set but Z set too. The test reads “unchanged”, an answer that CP never gives. For any other letter, the result is not zero, and the bug does not show.

The green code sets the seven low bits before the 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 is #FF or #7F, and add a,a gives #FE in both cases: never Z.

The byte of S1 in E

All is green, but .differ is heavy: two ex de,hl, a second read of S1, an or #7f.

So we look closer at the last path. After the cp (hl) that gives Z, A holds the byte of S1 with the bit 7 of S2: it is the byte of S2. The two original bytes differ only by bit 7. So S2 − S1 is +#80 or −#80, never zero. And the subtraction borrows if S1 has bit 7 set, that is, if S1 ends. A sub with the byte of S1 answers on its own: NZ, and C if S1 comes first, even for the letter #00.

We need the byte of S1 at hand. After the cp (hl), nothing reads S1 through DE any more: E is free, and it can keep the byte (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

The two ex de,hl go away, with the second read of S1 and the or #7f. .differ drops from 13 to 9 bytes. The ten tests stay green. The path of different letters saves 2 NOPs, the path of a string that ends saves 6. This is the version the animation shows.

Counting by hand

Before the last guard, which is about time, we must count, with Madram’s table. Here k stands for the letters equal on 7 bits before the letter that decides. A string that ends on the k-th letter counts it. So “A” and “AB” have one equal letter, the A, even though their first bytes differ.

An equal letter costs 14 NOPs: ld a,(de) 2, cp (hl) 2, jr nz not taken 2, inc de 2, inc hl 2, rla 1, jr nc taken 3. Each path starts with ex de,hl, 1 NOP.

Before the refactor, the last two paths cost 14k + 22 and 14k + 14 NOPs.

The budget

The budget guard gives each path its own test and its bound (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);
});

The three bounds are exact: with toBe in place of toBeLessThanOrEqual, the twenty tests pass too.

The first broken version it catches is the .differ of 13-green, before the refactor. The seven tests of the first two paths fail, by 2 NOPs for different letters, by 6 for a string that ends:

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

The second one changes the loop. It reads the end mark with bit 7,(hl), instead of pushing A into C with rla:

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

The code stays right, and it keeps A as it is, but A has no use at this point. bit 7,(hl) costs 3 NOPs and jr z 3, against 1 and 3: 16 NOPs per letter. The three tests of equal strings fail, with five more:

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

At k = 1, a string that ends makes no full turn of the loop. That test passes with the second broken version, but it catches the first one.

Conclusion

strcmp compares two strings in the firmware format, and answers like CP. The format hid three traps: the bit 7 of a string that ends must not count as a letter, nor hide the letter that decides, and the letter #00 is a letter like the others. The refactor kept the byte of S1 in E, and a single subtraction replaced the special case. Each path now has an exact budget: 14k + 20, 14k + 8 and 14k + 4 NOPs.

Its contract stays narrow:

• strings in the firmware format, of at least one letter, each letter on 7 bits;
• the order of the ASCII codes, with nothing more: “B” comes before “a”;
• A, HL and DE change, and only BC is kept.

The next post will sort an array of pointers to strings, by insertion, with strcmp as the comparison. The strings will not move, and B will keep its count.

Trying it yourself

You need Node.js 24 or later, pnpm, and RASM v3.3.1 on the PATH. The steps of this post are on the strcmp branch of the z80-tdd-sorts repository. It starts from main, like the others. To replay a step:

git checkout strcmp/01-red
pnpm install
pnpm test

The tests of the routine are in src/strcmp.test.ts. To install z80-tdd in a project of your own, see the Trying it yourself section of the post on find_min.

Links

• The previous post: radix sort on 16-bit keys
• Counting sort, bubble sort, insertion sort and selection sort
• The introduction: find_min and TDD on the CPC
• z80-tdd, the test tool
• z80-tdd-sorts, the repository of this post (branch strcmp)
• RASM, the assembler by Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), the table of durations in NOPs