The square root of 32 is not 4.02
A week ago I noticed that I had a problem with my CBASIC prime number generator running on an RC2040. My first thought was that I’d messed up the algorithm (not unheard of) as it told me there were 1,231 primes between 1 and 10,000 (there are 1,229). Eventually I thought I’d found a bug in the compiler, as it seemed to be generating incorrect values for some square roots – for example, SQR(32) was evaluating to 4.02ish, rather than 5.65ish. This was what was throwing off the prime number generator, rather than inherently dodgy Holyoake hacking. A couple of days later I tried the same code on a real Z80 based computer (the RC2014 that the RC2040 emulates) and … it worked. Hmm. So the problem didn’t lie in the CBASIC compiler after all, but in the Z80 emulation code used by the RC2040.
Being retired means that I have a little more time to play and that’s exactly what I’ve done over the last couple of days. First, I downloaded the source code for the RC2040 and got it to build and install for myself. The bug was still there – which bizarrely gave me some confidence that I’d managed to build the emulator correctly. After having identified the location of the Z80 emulation library, I had a quick glance at the code. It looked relatively understandable – unlike a lot of other emulators I’ve had a poke at in the past
I then wrote a small piece of code to recreate the issue. Hence my earlier comment about SQR(32), as this is the code fragment I used:
PRINT "Square root of 32 is ";SQR(32)Loading the code into DDT and tracing it generates around 6,000 lines of output. I was able to do exactly the same thing on the RC2014 (once I’d found a patched version of DDT that would work). A quick Linux diff narrowed the issue down to probably being somewhere in the SBC A,s instruction (SBB D in 8080-speak).
C1Z0M1E0I1 A=00 B=1EA1 D=21E7 H=2100 S=21E7 P=0146 SUB E
C1Z0M0E0I1 A=19 B=1EA1 D=21E7 H=2100 S=21E7 P=0147 MOV A,H
C1Z0M0E0I1 A=21 B=1EA1 D=21E7 H=2100 S=21E7 P=0148 SBB D
-C1Z0M1E0I1 A=FF B=1EA1 D=21E7 H=2100 S=21E7 P=0149 JC 0142
-C1Z0M1E0I1 A=FF B=1EA1 D=21E7 H=2100 S=21E7 P=0142 MVI M,00
-C1Z0M1E0I1 A=FF B=1EA1 D=21E7 H=2100 S=21E7 P=0144 INX H
-C1Z0M1E0I1 A=FF B=1EA1 D=21E7 H=2101 S=21E7 P=0145 MOV A,L
-C1Z0M1E0I1 A=01 B=1EA1 D=21E7 H=2101 S=21E7 P=0146 SUB E
+C1Z0M1E0I0 A=FF B=1EA1 D=21E7 H=2100 S=21E7 P=0149 JC 0142
+C1Z0M1E0I0 A=FF B=1EA1 D=21E7 H=2100 S=21E7 P=0142 MVI M,00
+C1Z0M1E0I0 A=FF B=1EA1 D=21E7 H=2100 S=21E7 P=0144 INX H
+C1Z0M1E0I0 A=FF B=1EA1 D=21E7 H=2101 S=21E7 P=0145 MOV A,L
+C1Z0M1E0I0 A=01 B=1EA1 D=21E7 H=2101 S=21E7 P=0146 SUB E
This is where it got more difficult for me, as I’ve done very little low-level work with the Z80 processor. Fortunately, I have a well-thumbed copy of the Rodney Zaks Z80 bible to hand, picked up for a few pennies from a charity bookshop a couple of years ago.
Pages 420/421 tells me that the operand plus any carry (borrow) is subtracted from the accumulator.
The Z80 emulation code had other ideas however – any carry was dealt with after the subtraction, meaning that the half carry flag F_H could be set incorrectly.
/** Do an arithmetic operation (ADD, SUB, ADC, SBC y CP) */
static byte doArithmetic (Z80Context* ctx, byte value, int withCarry, int isSub)
{
ushort res; /* To detect carry */
if (isSub)
{
SETFLAG(F_N);
VALFLAG(F_H, (((BR.A & 0x0F) - (value & 0x0F)) & 0x10) != 0);
res = BR.A - value;
if (withCarry && GETFLAG(F_C))
res--;
}
else
{
RESFLAG(F_N);
VALFLAG(F_H, (((BR.A & 0x0F) + (value & 0x0F)) & 0x10) != 0);
res = BR.A + value;
if (withCarry && GETFLAG(F_C))
res++;
}
...My adjusted code resolves this issue, tidies up some other areas and adjusts the 16 bit equivalent that follows this function to work in the same manner.
This certainly resolves the problem seen in the CBASIC SQR function, as it now returns 5.65ish as SQR(32). The prime number generator also correctly returns 1,229 primes between 1 and 10,000. I wonder if everything else still works though – more testing needed at the moment!
Postscript 12/02/2024
Although this ‘fixes’ the issue found with the CBASIC compiler, it breaks other things. Looking more closely at Zaks there appears to be a lot of subtlety in the way the Z80 treats a carry (or borrow) in and the order in which it’s dealt with, depending on the instruction and registers used. Back to the drawing board for the time being …
Second Postscript 12/02/2024
… but if you compile something under the faulty emulator and then try to run it under the corrected version, you may still get (a different) wrong result? So far compiling everything under the corrected emulator (or on the real hardware and transferring it across) works as expected. Still more testing needed before I’m happy, though.
14/02/2024
I now seem to have a fix that definitely works … programs compiled and linked under CBASIC and Turbo Pascal are all giving me correct results. I’m going to do a few more tests with different compilers (Aztec C and FTL Modula2) just to make absolutely sure. Finally, the zexdoc/zexall test suite looks like it could be useful, if long-winded (I may tweak the nominal CPU speed up a bit).
Holyoake’s first and second laws of bug fixing apply here:
- Fix the problem you’ve identified, and only that problem, before tidying other stuff up. (*)
- Never contaminate your test environment with (for example) executables that were created with a buggy version of your code and expect those executables to give correct results in the fixed environment. (**)
(*) AKA breaking things that were already working.
(**) AKA D’oh!
Zexall & Zexdoc 15/02/2024
I now have copies of the zexall (all Z80 instructions and flags, including undocumented features) and zexdoc (documented instructions and flags only) Z80 test rigs running (sourced from the yaze-ag emulator). Unsurprisingly a real RC2014 passes both sets of tests.
The revised Z80 emulation library for the RC2040 doesn’t do quite as well – 5 failures on zexdoc and 8 on zexall. But that’s better than the originally shipped library, so I’ve made some progress.
Do I want to turn fixing the entire library into a project? It looks like that’s starting to happen anyway …
Zexdoc failing tests:
aluop a,<b,c,d,e,h,l,(hl),a>.. ERROR **** crc expected:fe43b016 found:9e17dfdc
aluop a,<ixh,ixl,iyh,iyl>..... ERROR **** crc expected:a4026d5a found:88a56864
aluop a,(<ix,iy>+1)........... ERROR **** crc expected:e849676e found:14c405a8
<daa,cpl,scf,ccf>............. ERROR **** crc expected:9b4ba675 found:31255bf5
ld <bcdexya>,<bcdexya>........ ERROR **** crc expected:478ba36b found:8088c9d9
Zexall failing tests:
aluop a,<b,c,d,e,h,l,(hl),a>.. ERROR **** crc expected:06c7aa8e found:6693c544
aluop a,<ixh,ixl,iyh,iyl>..... ERROR **** crc expected:a886cc44 found:8421c97a
aluop a,(<ix,iy>+1)........... ERROR **** crc expected:d3f2d74a found:2f7fb58c
bit n,<b,c,d,e,h,l,(hl),a>.... ERROR **** crc expected:5e020e98 found:fe7d580c
cpi<r>........................ ERROR **** crc expected:2da42d19 found:6602a286
<daa,cpl,scf,ccf>............. ERROR **** crc expected:6d2dd213 found:c7432f93
ld <bcdexya>,<bcdexya>........ ERROR **** crc expected:478ba36b found:8088c9d9
<rrd,rld>..................... ERROR **** crc expected:ff823e77 found:2201b2c420/02/2024
After several attempts I now have algorithms for DAA / CPL / SCF / CCF which pass the zexdoc test. I suspect that the three aluop issues are a single underlying problem and that the ld issue is separate. I’m running zexall overnight to see if I’ve made any progress – hopeful that what I’ve done to DAA removes one failure from the eight.
21/02/2024
zexall ran overnight with six failures. Some more work today means zexdoc now fails just two tests – one of the aluop tests and an ld test. Running zexall overnight again – hopefully it will show four failing tests.
22/02/2024
Steady progress today. SQR(32) is still correct with the changes I’ve made to the z80 library and zexdoc now fails on only a single test (ld <bcdexya>, <bcdexya>). zexall fails three. One of these is the same ld test as zexdoc. The other two are rrd/rld which I believe has some interesting X and Y flag behaviour, as does bit n, <b,c,d,e,h,l,(hl),a>.
B>sqr32
Square root of 32 is 5.65685424949
B>n:
N>zexdoc
Z80 instruction exerciser
<adc,sbc> hl,<bc,de,hl,sp>.... OK
add hl,<bc,de,hl,sp>.......... OK
add ix,<bc,de,ix,sp>.......... OK
add iy,<bc,de,iy,sp>.......... OK
aluop a,nn.................... OK
aluop a,<b,c,d,e,h,l,(hl),a>.. OK
aluop a,<ixh,ixl,iyh,iyl>..... OK
aluop a,(<ix,iy>+1)........... OK
bit n,(<ix,iy>+1)............. OK
bit n,<b,c,d,e,h,l,(hl),a>.... OK
cpd<r>........................ OK
cpi<r>........................ OK
<daa,cpl,scf,ccf>............. OK
<inc,dec> a................... OK
<inc,dec> b................... OK
<inc,dec> bc.................. OK
<inc,dec> c................... OK
<inc,dec> d................... OK
<inc,dec> de.................. OK
<inc,dec> e................... OK
<inc,dec> h................... OK
<inc,dec> hl.................. OK
<inc,dec> ix.................. OK
<inc,dec> iy.................. OK
<inc,dec> l................... OK
<inc,dec> (hl)................ OK
<inc,dec> sp.................. OK
<inc,dec> (<ix,iy>+1)......... OK
<inc,dec> ixh................. OK
<inc,dec> ixl................. OK
<inc,dec> iyh................. OK
<inc,dec> iyl................. OK
ld <bc,de>,(nnnn)............. OK
ld hl,(nnnn).................. OK
ld sp,(nnnn).................. OK
ld <ix,iy>,(nnnn)............. OK
ld (nnnn),<bc,de>............. OK
ld (nnnn),hl.................. OK
ld (nnnn),sp.................. OK
ld (nnnn),<ix,iy>............. OK
ld <bc,de,hl,sp>,nnnn......... OK
ld <ix,iy>,nnnn............... OK
ld a,<(bc),(de)>.............. OK
ld <b,c,d,e,h,l,(hl),a>,nn.... OK
ld (<ix,iy>+1),nn............. OK
ld <b,c,d,e>,(<ix,iy>+1)...... OK
ld <h,l>,(<ix,iy>+1).......... OK
ld a,(<ix,iy>+1).............. OK
ld <ixh,ixl,iyh,iyl>,nn....... OK
ld <bcdehla>,<bcdehla>........ OK
ld <bcdexya>,<bcdexya>........ ERROR **** crc expected:478ba36b found:8088c9d9
ld a,(nnnn) / ld (nnnn),a..... OK
ldd<r> (1).................... OK
ldd<r> (2).................... OK
ldi<r> (1).................... OK
ldi<r> (2).................... OK
neg........................... OK
<rrd,rld>..................... OK
<rlca,rrca,rla,rra>........... OK
shf/rot (<ix,iy>+1)........... OK
shf/rot <b,c,d,e,h,l,(hl),a>.. OK
<set,res> n,<bcdehl(hl)a>..... OK
<set,res> n,(<ix,iy>+1)....... OK
ld (<ix,iy>+1),<b,c,d,e>...... OK
ld (<ix,iy>+1),<h,l>.......... OK
ld (<ix,iy>+1),a.............. OK
ld (<bc,de>),a................ OK
Tests complete If I can get the final zexdoc test to pass then I’m tempted to call it a day, as it seems unlikely that the RC2040 running CP/M 2.2 will care all that much about the undocumented flag behaviour.
I now need to start adding my fixes back into my github fork of libz80 (and test it again). However, there’s a breaking fix (pointer sizes) that’s been made to the original libz80 library since the RC2040 code cloned it, as well as what I think are some RC2040 specific additions to the Z80 context for the disassembler and debugger. So I may need to fork the RC2040 repository as well, as that’s all I’m currently interested in.
25/02/2024 – The End of the Beginning
I’ve still not managed to track down the final problem that stops zexdoc from passing the remaining ld test. I think it’s probably connected to some of the ‘undocumented and special’ behaviour of the IX and IY registers, but I’m not sure. Interestingly, the author of the unpublished neccy Spectrum emulator ran into the same issue four years ago – even down to an identical wrong CRC for the test. I wonder if they ever resolved it?
Anyway, I’m running out of time for the next couple of weeks due to other commitments, so I’ve spent the last couple of days going carefully over my fixes and reapplying them one by one. The result is a new fork of the libz80 library, compatible with both the RC2040 system software and EmulatorKit. It’s not perfect yet, but I don’t think there’s anything left to fix in this library that would impact the RC2040 too much, if at all.
Unless you know differently, of course …