Close

Cheap tricks for better results

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/06/2021 at 04:050 Comments

Oh damnit, forget about Pisano16x2.v2.c and test_Pisano16x2.v2.c because I just found a stupid off-by-one error!

Anyway, here is the old version.

___________________________________

I just modified the "reference code" for the checksum algorithm by "early-mixing" the size of the buffer. This helps in the case of comparing two blocks (or files) with a checksum collision: the metadata of the block size will help telling them apart.

I also added guidelines for the initial value, considering the worst case of input data:

Hence I have chosen 0xABCD in the reference code.

#define PISANO_WIDTH (16)  // Do NOT change.
#define PISANO_SIZE  (1<<PISANO_WIDTH)
#define PISANO_MASK  (PISANO_SIZE-1)
#define MAGIC_INIT   ( 0xABCD ) // do not use 0 or FFFF.
  // Odd, high values (> 30K) are better for early avalanche.

uint32_t Pisano_Checksum32(
  uint16_t *buffer,  // points to the data to scan
  int size           // number of 16-bit WORDS to scan
) { uint32_t
  // Init
    X = *buffer    ^ (size >> 16),
    Y = MAGIC_INIT + (size & 0xFFFF),
    C = 1;

  // Loop
  while (size) {
    C += X + Y;
    X = Y ^ *buffer;
    buffer++;
    Y = C & PISANO_MASK;
    C = C >> PISANO_WIDTH;
    size--;
  }
  // Finish
  return (uint32_t)(C+Y+(X << PISANO_WIDTH));
}

As a result, the generated values for checksumming empty buffers are:

 n  PEAC16  PEAC32
 1:  579D  ABCEABCF
 2:  0370  ABD057A0
 3:  5B15  57A10374
 4:  5E90  03765B1A
 5:  B9B7  5B1F5E98
 6:  1864  5EA0B9C4
 7:  D24B  B9D1187A
 8:  EAFB  188ED26D
 9:  BDC1  D28FEB32
10:  A984  EB69BE1B
11:  6888  BE73AA15
12:  1416  AAA46972
13:  7FEA  6A5A1590
14:  9954  1708824C
15:  21DD  84AE9D2F
16:  C925  A10A281B
17:  0194  2E57D33D
18:  EF3F  DD5511EA
19:  2BEB  223E09AD
20:  7AC6  241956AD
21:  4164  816FBFF5
22:  B67A  0524B156
23:  8CE2  21476B9B
24:  D2AF  20BBB1F4
25:  83E7  D705ACE2
26:  0A3F  8713832C
27:  6624  826FE3B5
28:  FC0A  BD2B3EDF
29:  C5D2  1798AE3A
30:  B126  606950BD
31:  C9E5  DBA6EE3F

It looks pretty well behaved, particularly if you compare with the standard Fletcher/Adler.

For now the reference code uses XOR mixing and the debate is not yet settled if the ADD mixing method is more robust.

Anyway this new version looks more adapted than the previous one for the comparison of files, for example (as long as you can mmap() them because I have not yet implemented a system for multi-part checksums).

Discussions