Close

The new version of PEAC16x2

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/08/2021 at 04:460 Comments

Here is the new version of the algorithm:

Voilà !

There are many refinements since the last versions, helping to solve the issues found in the last logs, while still maintaining simplicity and efficiency, both with hardware and software implementations.

Keep in mind that this diagram shows the "principles", the algorithm could be implemented "as is" (like the reference below) but several optimisations are possible in software for example.

#define PISANO_WIDTH (16)
#define PISANO_SIZE  (1<<PISANO_WIDTH)
#define PISANO_MASK  (PISANO_SIZE-1)
#define MAGIC_INIT   ( 0xABCD4567 )

uint32_t Pisano_Checksum32(
  uint16_t *buffer, // points to the data to scan
  uint32_t words    // number of 16-bit WORDS to scan
) { uint32_t
    Y = words + MAGIC_INIT,
    X = Y >> 16, // extract the MSB
    C = 0,  // The "magic number" takes care of proper 
    D = 0;  // initialisation so C & D can be left cleared
  Y &= 0xFFFF;

  while (words) {
    // C, D : range 0-1
    // X, Y : range 0-FFFFh
    C += X + Y;             // result range : 0-1FFFFh
    X = Y + *buffer + D;    // result range : 0-1FFFFh
    buffer++;
    Y = C & PISANO_MASK;    // result range : 0-FFFFh
    C = C >> PISANO_WIDTH;  // result range : 0-1
    D = X >> PISANO_WIDTH;  // result range : 0-1
    X = X & PISANO_MASK;    // result range : 0-FFFFh
    words--;
  }

  C += X + Y;               // result range : 0-1FFFFh
  return C+((X+D) << PISANO_WIDTH); // range : 0-FFFFFFFFh
}

uint16_t Pisano_Checksum16(
  uint16_t *buffer, // points to the data to scan
  uint32_t words    // number of 16-bit WORDS to scan
) {
  return (uint16_t)(Pisano_Checksum32(buffer, words));
}

Now, there is a lot of work to simplify the loop body while keeping the exact same external behaviour.

Discussions