(Damnit, the last log was exactly one year ago :-O )

.

(Warning ! wrong assumption ! w32's primary orbit is way larger than 13G ! See w32 wasn't such a dud)

.

Ideally, w32 would be perfect or maximal. It's neither. So it's not possible to design a mathematically sound CRC/checksum with 32-bit wide registers. In fact, w32's primary orbit is much smaller than expected...

So what's perfect ? w26.

It's suitable to checksum 16-bit wide words only, so it's slower than w32, which is used in some database code. But compare w32's primary orbit containing only 13.603.546.275 iterations, vs w26's 4.503.599.694.479.358 ! So w32 could be "good enough" for some cases but it doesn't benefit from the whole mathematical potential of the PEAC system.

I have not found any suitable candidate that is larger than 32. The sieve says the following widths should be tested: 51 52 54 55 59 60 and 63 (this last one is alluring right ?)

However this is now a 64-bit number and it's less suitable for embedded computing (often limited to 32 bits). It would work on a PC though.

The other solution is to take w16 and parallelize it, SIMD-style. Embedded CPUs seldom have this feature.

But I have found a trick.

So we're stuck with w26 and 32-bit registers. That's still a 64-bit checksum in the end. Now let's do the math.

32-26=6 bits are unused in the register and do not meaningfully contribute to the result. They are affected by the data but the carry output is lost, never recovered nor re-injected so it's like a dead-end.

26-16=10 bits are not affected by the data that is injected for checksumming. Normally the input data is added in the LSB for convenience.

I guess you'll agree that 10 > 6 : This means that the data that "escapes" the register can be fully re-injected in the lower bits, above or along the input data. In fact, the PEAC checksums a part of itself, while still preserving the w26 properties. There are now 32+32=64 bits worth of entropy, not just 52: that's 4K more codes that are now unlocked.

Of course, at this point, it's important to check the actual orbit's topology of this new generator. Is it still "perfect" ? This extended system still accepts 16 bits per cycle only so the advantage over PEAC16 is only when needing a larger signature. But using the extended w26 provides twice as many bits and works for 32-bit platforms.

...

Now, it's time to code.