Add or XOR ?

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 06/20/2021 at 02:090 Comments

While studying the orbits of the Pisano-carry generator is good, let's not forget that the state will be mixed with more arbitrary bits. This "mixing" operation can be performed with a XOR or an ADD and both have their advantages and drawbacks, which are more or less prominent depending on the exact configuration.

I tend to like the XOR because it sounds so simple, uses less silicon area and is generally faster (at least not slower) than ADD. I also like it because it does not generate a carry signal that then must be taken into account. In turn this makes the new "non-masking" algorithms more efficient because the loopback bit is not affected and this saves one XOR operation, though there is not real impact in hardware (XOR gates are smaller than DFF).

OTOH the addition has more "avalanche effect" from the input data and, unless there is a wrap-around, the result is always above/greater than the addends, whereas the XOR can make the value jump up and down, particularly if the MSB are not yet set. In the worst case, this could prevent the whole state from evolving correctly. The ADD increases the spread of the checksums when the input data diverge very little (see RFC3309: Adler32 weakness).

This last argument makes the ADD method the preferred choice.