Close

Additions and consequences

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

yann-guidon-ygdesYann Guidon / YGDES 08/07/2021 at 16:030 Comments

So the last log has demonstrated that ADD mixing is superior to XOR mixing (at least when the 33-bit result must be compacted into 16 bits).

XOR was favoured for a few reasons:

There is a theoretical kink though: using a XOR operator in an ADD space creates a sort of conflict because the "numbers" have different types. You can consider the evolution of the state of the registers as if you "walked" through the state space:

The backwards part has a big influence when mixing small values because the "teleportation" range will be small and there is a high risk of overwriting past values. ADD does not suffer from this : going "forward" in the state space ensures that small values will always have distinct effects on the state.

The meaning of the ADD and XOR results are very different, I don't know the right term but XOR operates in a Hamming space (where bits are somewhat independent) while ADD works in a magnitude space (the bits are combined to give one value). This is why the Hamming distance of a single bit flip doesn't propagate much during the first iterations (compared to a good CRC which will flip half of the bits whenever it can).

So it makes sense to remain in the same type of realm during the whole checksum.

Now, another addition in the datapath creates a new kind of challenge, because so far we had to deal with only 1 carry bit, and now there are two !

Somehow it was not visible in the results because the source code handled it inherently well. Let's look at it

while (words) {
    C += X + Y;
    X = Y + *buffer;
    buffer++;
    Y = C & PISANO_MASK;
    C = C >> PISANO_WIDTH;
    words--;
}
  1. first line: C is expected to be 0 or 1, as the carry-in for the X+Y operation. Result of 0-FFFFh + 0-FFFFh is 0 to 1FFFEh.
  2. X becomes the sum of Y and the input datum. Note however that, unlike XOR, the sum's range become 0 to 1FFFEh, so there is a generated carry. XOR keeps the range within 0 to FFFFh.
  3. n/a
  4. Y now gets the lower part of the sum and range is back to 0 to FFFFh.
  5. C is re-normalised to 0 to 1, or at least that's what is intended.

But then, the new range of X breaks these assumptions.

  1. The operation X+Y works on Y=0-FFFFh and X=0-1FFFEh so the result is C=0-2FFFDh !
  2. n/a
  3. n/a
  4. n/a
  5. C is now renormalised to 0-2

This means there are 2 carry inputs to line 1), something that does not fit common hardware circuits. The software version however doesn't exhibit any problem, as C was defined as uint32_t and can accommodate the whole range. The increased range was not noticed and... it is also a great thing, because it reminds us that we can compute the renormalisation at the end of the loop, not necessarily at every step.

The challenge now is to create a single algorithm that works best both in software and hardware.

A normal adding circuit can only have one input signal because FFFFh+FFFFh+1=1FFFFh, fitting in 17 bits. Another carry in signal will bump the range to 20000h, or 18 bits. However, there are 2 adders, so 2 carry inputs. There are only 2 ways to connect the carry outs to the carry ins...

(tbc)

.

Discussions