Close

Add with carry : the macro

A project log for YGREC8

A byte-wide stripped-down version of the YGREC16 architecture

yann-guidon-ygdesYann Guidon / YGDES 11/03/2021 at 02:526 Comments

The Y8 core has a carry flag but no ADC opcode. That's a compromise, turned into a fact now. So how do we perform multi-precision add/sub ?

The first way uses the conditional form that can contains a small immediate. This can skip an instruction that increments the MSB but then comes the problem of the eventual secondary carry, which requires another conditional test.

Another way uses the rotate-through-carry instruction. Again, secondary carry and all...

The last way was imagined a few moments ago and exploits the fact that the SUB opcode force the carry to 1, the trick then is to negate the register operand, which could be simplified in some cases.

Y8 was not meant to be an efficient multi-precision core, but not plainly awkward either.

I'd like to run PEAC16 as a programmed BIST to exercise the RAM, ALU and decoder so the ability to use 16-bit numbers pushes the core to its limits.

The idea is to configure the debug probe to spy on the carry signal and observe the pattern that arrives, then compare to an internally programmed bitstream (this easily fits with a small FPGA or even EPLD). Slowly increase the clock speed and whatch when the output bistream diverges from the internally generated one, and you can bin the chips.

So it turns out that handling multi-precision addition is slightly more important than I thought but I'll find a pretty hack.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

So let's say we have two 16-bit integers in R1-R2 and D1-D2.

The LSB is added by ADD R1 D1 with result in D1. The Carry flag is set accordingly.

The carry can then be merged with D2 : ADD 1 D2 C

At this moment, we look if we need the extra carry, or 17th bit. If not, just do ADD R2 D2 and you're done.

But PEAC requires the 17th bit so the 2nd instruction does not work.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Let's go back to ADD R1 D1 which generates a carry. It must be included in the MSB and this can generate a carry by itself. The second ADD R2 D2 will generate a carry too though not both at the same time so a OR is possible. If a secondary carry occurs when incrementing D2, this means that its new value is 0 and no value of R2 could trigger another/tertiary carry.

The easy way to deal with it is to dedicate R3 to a sort of "carry register".

  1. SET 0 R3 ; init
  2. ADD R1 D1   ; primary add
  3. ADD 1 D2 C  ; secondary add
  4. SET 1 R3 C ; first correction, could also be a RCL 1 R3
  5. ADD R2 D2  ; tertiary add
  6. SET 1 R3 C ; final fix. No need of OR.

This code is branchless : 4 is executed only if 3 generates a carry, which only happens if 2 also generates the carry. The ADD opcode overwrites the carry so 4 only occurs when we really need it.

That's 6 instructions and half of them manage the external carry flag. The flag can be kept in place by using the "SUB trick". However a couple of branches are required.

  1. ADD R1 D1   ; primary add
  2. ADD 3 PC NC  ; conditional branch to normal ADD
  3. XOR -1 D2 ; pre-correction to compensate the SUB
  4. SUB R2 D2  ; tertiary add, +1
  5. ADD 1 PC ; Goto END.
  6. ADD R2 D2  ; tertiary add, normal
  7. the end.

That's still 6 instructions but we save one register. But wait ! The jump uses ADD which also destroys the carry flag ! Fortunately it's also possible to do a direct jump when no condition is needed.

  1. ADD R1 D1   ; primary add
  2. ADD 3 PC NC  ; conditional branch to normal ADD
  3. XOR -1 D2 ; pre-correction to compensate the SUB
  4. SUB R2 D2  ; tertiary add, +1
  5. SET theend PC ; Goto END.
  6. ADD R2 D2  ; tertiary add, normal
  7. theend:

Et voilà.

PEAC requires 2 consecutive byte adds with carry, and each takes 5 opcodes. Then the whole block is register-swapped to emulate the copy.

A macro could be created :

Define ADC SRC DST label
ADD 3 PC NC
XOR -1 DST
SUB SRC DST
SET label PC
ADD SRC DST
label: 

And the #PEAC16 could be coded as :

ADC R1 D1
ADC R2 D2
ADC D1 R1
ADC D2 R2 

phew.

It's still not as handy as a direct ADC opcode and there could be side effects (with the XOR -1) but it does the job.

Discussions

zpekic wrote 03/29/2023 at 06:25 point

TMS9900 only had an ADD instruction too - it generated a carry out but took no carry in. Instead, INC <dest> instruction was used to correct one of the operands of next ADD operation. 

  Are you sure? yes | no

Yann Guidon / YGDES wrote 03/29/2023 at 15:39 point

and managing the carry, carrying it from word to word, probably hurt the multiprecision performance....

Here, in Y8, it's not just a matter of speed, but also space : there are only 256 instructions per "overlay" so a common "simple" sequence that takes 5 instructions (80 bits) is a big problem.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 03/29/2023 at 05:26 point

https://hackaday.io/project/27280-ygrec8/log/217081-carry-on

a proper instruction (or something similar enough) is way better right ?

  Are you sure? yes | no

Yann Guidon / YGDES wrote 11/04/2021 at 16:50 point

Needless to say this method is also valid for SUB with borrow ;-)

  Are you sure? yes | no

WalkerDev wrote 11/04/2021 at 13:11 point

The methods you are using are crazy! Best of luck and looking forward to the next update!

  Are you sure? yes | no

Yann Guidon / YGDES wrote 11/04/2021 at 16:50 point

Thanks TKTS !

But I don't think it's crazy. We all know that A - B = A + (-B).

And in 2s-complement, -B = (not B) + 1

So I simply use SUB with the subtractand negated to get the +1 with proper carry.

I have not seen this method used anywhere yet but it was worth writing a log about it ;-)

  Are you sure? yes | no