The last log Periodicity has found an amazing property of the 2×16 configuration with carry: The period is 2³¹+32767, instead of 1,5×2¹⁶ ... Enabling the carry thrusts the checksum in a new dimension that Adler or Fletcher can't contemplate. There are still weird questions to address but let's first define this new design.
- Working code is in FiboSum16x2.html.txt; download it, rename it, open it and wait a bit :-)
- The combine operation uses a + to increase avalanche. Using xor only might make the sequence of values less sensitive to swaps.
- X and Y are 16-bits long, there is one carry that is input and output from particular additions. This makes it particularly attractive for 16-bits microcontrollers, or 8086 for example, which can use ADDC.
; Checksumming 4 bytes in 6 opcodes ; X=BX, Y=DX lodsw ax addc dx, bx xor bx, ax lodsw ax addc bx, dx xor dx, ax
6 simple instructions to process 4 bytes !
However the carry would be overwritten if data mixing used ADD so I use XOR here.
- If needed, 32 bits processors without carry support can simply shift the result to generate the carry, as I did in the following code :
tX = X + data; // Combine data tY = X + Y + C; // Fibonacci C = tY >> 16; // extract carry tY &= mask; tX &= mask; // truncate results X = tX + tY + C; Y = tY + data; C = X >> 16; X &= 0xFFFF; Y &= 0xFFFF;This is the version I use in the JS code. It's longer and requires careful masking of the results, otherwise the carry will be wrong.
The dataflow graph is almost like before BUT the whole width of the register is used (unless the register is too wide and the values MUST be truncated).
It appears that the graph should be reorganised :-)
The JS code runs 6.5B loops and its length is usually 2147516415, or 2³¹+32767. The behaviour is quite confusing and the orbit(s) must be now analysed...