NUT CPU BCD arithmetics in SETDEC mode (aka Goose hunt)

[ThomasF]

Hi all,

As have been noted in previous threads, the main reason for failing to fly the goose backwards in all emulators and simulators so far seems to be a shortage in the emulation of BCD arithmetics in the NUT CPU.

If the syntethic FIX 10 instruction is executed, this results in a hexadecimal value being decremented in decimal mode causing the emulators and simulators to differ from the real HP41 causing the goose to be missed!

I have tried to trace and understand the underlying logic (and as Christoph mentioned - this is of course the gate logic in the NUT CPU) when doing BCD arithmetics in decimal mode.

I have added some results taken from a real HP41. All arithmetic is done on the S&X field (12 bits) of register A.
I have added or subtracted 1, 5 and F from all possible values (000-FFF) and traced the result and checked if carry was set or not.

All logs have the same layout:

Code:

A[S&X] (original value)
 |
 v
A01 --> 400 CARRY
     ^   ^   ^
     |   |   +-- resulting in CARRY or not)
     |   +-- result in A[S&X]
     +-- instruction (e.g. A=A-1 [S&X])

The case with adding 1 was easy to understand. First the value is translated to decimal digit by digit (A=10, .. F=15)

Code:

  int d = 0;
  int n = 1;
  while( x ) {
    d += (x & 0xF) * n; // Hex to decimal and add to result
    n *= 10;
    x >>= 4;
  }
  return d;

The result is incremented by 1, and if the result overflows the field, then carry is set.
Some examples:

Code:

000 (000 + 00 + 0 = 000) --> 000 + 1 = 001 
012 (000 + 10 + 2 = 012) --> 011 + 1 = 013
00C (000 + 00 + 12 = 012) --> 012 + 1 = 013 
98E (900 + 80 + 14 = 994) --> 994 + 1 = 995
9A0 (900 + 100 + 0 = 1000) -> 1000 + 1 = 001 CARRY

Subtracting with 1 can not be done with a similar approach, eg:

Code:

00F --> 008
98E --> 987
A01 --> 400 CARRY
A00 --> 999

And adding/subtracting a different number makes it even worse.
E.g. adding 0xF in decimal mode results sometimes in hexadecimal values:

Code:

000 + 00F --> 015 
005 + 00F --> 01A 
01A + 00F --> 02F 
98F + 00F --> 994 
990 + 00F --> 005 CARRY

It is not too hard to come up with some code that will handle these cases, but I have trouble finding a common solution that will handle all cases and all fields.
Maybe someone with knowledge about BCD algorithms and/or gate logic can see some patterns here ... ?

Feel free to suggest some other tests that I could provide the results from.
(Will add some more traces in next post.)

Cheers,
Thomas

[ThomasF]

Added some more traces ...

Cheers,
Thomas

[Christoph Giesselink]

TNX Thomas,
verified the V41-Adder and fixed the Subtraction to base 10 with hexadecimal numbers.

With your delivered tables it would be a shame to verify only single points, so I created my own tables to compare them with your references.

Christoph

[ThomasF]

(04-03-2024 09:54 AM)Christoph Giesselink Wrote:  With your delivered tables it would be a shame to verify only single points, so I created my own tables to compare them with your references.

Hi Christoph,

Please let me know if you need to test some other corner cases!
I tried to implement a BCD-adder, and addition worked fine (gives 100% same result as my traces), but I can't manage to crack the subtraction ...

In general, a BCD subtraction is done by complementing (either by 9 or 10) one value and feed it to an adder (A - B = A + ~B).
But, it doesn't work, there seems to be some special handling when e.g. hex:A is part of the value, so it is not as straight forward as addition.

Cheers,
Thomas

[Christoph Giesselink]

(04-03-2024 11:34 AM)ThomasF Wrote:  I tried to implement a BCD-adder, and addition worked fine (gives 100% same result as my traces), but I can't manage to crack the subtraction ...

In general, a BCD subtraction is done by complementing (either by 9 or 10) one value and feed it to an adder (A - B = A + ~B).

I haven't tried it to make it by boolean operations. It's just a fix of the existing code using BASECY as BASE overflow indicator (opcode examples incomplete).

Code:

...
case 12:           // A=A-B
  {
  for (i=FirstTEF;i<=LastTEF;i++)
    A_REG[i]=Subtractor(A_REG[i],B_REG[i]);
  CARRY|=BASECY;
  break;
  }
case 13:           // A=A-1
  {
  CARRY=1;
  for (i=FirstTEF;i<=LastTEF;i++)
    A_REG[i]=Subtractor(A_REG[i],0);
  CARRY|=BASECY;
  break;
  }
...

Code:

/****************************/
// digit subtractor
/****************************/
byte HP41::Subtractor(
  byte nib1,
  byte nib2)
  {
  char result=nib1-nib2-CARRY;
  BASECY=0;
  if (result<0)
    {
    result+=BASE;
    CARRY=1;
    }
  else
    {
    CARRY=0;
    if (result>=BASE)
      {
      result-=(16-10);
      BASECY=1;
      }
    }
  return(result&0x0f);
  }

As old Z80 coder I remembered the Decimal Adjust (DAA) instruction in the Z80 CPU. So I had I look into a Zilog User Manual:

Decimal Adjust Accumulator Flag
The Decimal Adjust Accumulator (DAA) instruction uses this flag to distinguish between ADD and SUBTRACT instructions. For all ADD instructions, N sets to 0. For all SUBTRACT instructions, N sets to 1.

Half Carry Flag
The Half Carry Flag (H) is set (1) or cleared (0) depending on the Carry and Borrow status between bits 3 and 4 of an 8-bit arithmetic operation. This flag is used by the Decimal Adjust Accumulator (DAA) instruction to correct the result of a packed BCD add or subtract operation. The H Flag is set (1) or cleared (0) as shown in Table 23.

So for coding DAA it needs 3 flags, N-Flag, H-Flag und C-Flag, quite complex. No further investigation.

[ThomasF]

Thanks Christoph!

It was arithmetics like these that fooled me (subtraction with F):

Code:

A10 --> 40B CARRY
A0F --> 400 CARRY
A0E --> 999 
A0D --> 998

Why would A0F - F result in 400 with carry, but A0E - F results in 999 with no carry ... ?

Anyhow, using the algorithm in Subtractor that you provided works correct, so that could be used to implement BCD subtraction.

Using the following code, I could verify with all examples in previous traces!

Code:

byte Subtractor(byte nib1, byte nib2)
{
  char result=nib1-nib2-CARRY;
  BASECY=0;
  if (result<0) {
    result+=BASE;
    CARRY=1;
  } else {
    CARRY=0;
    if (result>=BASE) {
      result-=(16-10);
      BASECY=1;
    }
  }
  return(result&0x0f);
}

void bcd_sub(char *p1, char *p2, int n)
{
  CARRY=0;
  for (int i=0;i<n;i++) {
    p1[i] = Subtractor(p1[i],p2[i]);
  }
  CARRY|=BASECY;
}

Cheers,
Thomas

[Christoph Giesselink]

(04-04-2024 07:31 AM)ThomasF Wrote:  Using the following code, I could verify with all examples in previous traces!

Code:

byte Subtractor(byte nib1, byte nib2)
{
  char result=nib1-nib2-CARRY;
  BASECY=0;
  if (result<0) {
    result+=BASE;
    CARRY=1;
  } else {
    CARRY=0;
    if (result>=BASE) {
      result-=(16-10);
      BASECY=1;
    }
  }
  return(result&0x0f);
}

void bcd_sub(char *p1, char *p2, int n)
{
  CARRY=0;
  for (int i=0;i<n;i++) {
    p1[i] = Subtractor(p1[i],p2[i]);
  }
  CARRY|=BASECY;
}

On my request Thomas made an additional test with the ?A<C and ?A<B opcodes.

Like on other CPU's the compare function base on a subtraction without saving the result. So ?A<C base on the subtraction of A-C and has the same side effects on the Carry Flag like A=A-C.

So the less function for the NUT CPU could be implemented as:

Code:

void bcd_less(char *p1, char *p2, int n)
{
  CARRY=0;
  for (int i=0;i<n;i++) {
    Subtractor(p1[i],p2[i]);
  }
  CARRY|=BASECY;
}

The complete source code of V41 R9L with a reference implementation is now available.

Christoph