Close

Start and stop

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 04/28/2021 at 20:130 Comments

I have already explored all the "low hanging fruits" I have found but I'll need more time to come up with a proper perspective and theory. However, practical implementations have some coding constraints that I will address in this log.

Let's have a look at this revised dependency graph, which I revised to consider the aspects covered here:

I tried to minimise the total number of operations. This would probably be adapted for a hardware implementation, of course, but let's first design a first working software version.

The first thing to consider is the last one, usually called the "Finish" step, where the final result is handled. Already, X, Y and C contain the whole state for the system but

  1. C is usually discarded, so should be better combined with the remaining bits
  2. X could be OK by itself but adding it to Y should increase the Hamming distance in the case of an alteration that hits the last word and/or the checksum.

So the Finish contains a simple addition with carry in, and no carry out.

Going up from there, we have the loop body. The X-Y swap has been moved up but this doesn't change much here.

Then we have the Start step where the variables are initialised. As we have learned, the carry must be set to a value that is coherent with Y, in order to prevent a "stuck state". So in fact, any value is OK except  { Y=FFFF, C=1} and { Y=0, C=0}. I have used 0x1234 to prove my point but you may choose another non-forbidden value.

One input value is pre-loaded into X and the pointer can be pre-incremented in the loop to save one instruction and prevent an off-by-one access (and/or TLB lookup for a block that will not be used).

From there, writing the code is quiet like a walk in the woods...

#include <stdint.h>
#include <inttypes.h>

#define PISANO_WIDTH (16)
#define SIZE  (1<<PISANO_WIDTH)
#define MASK  (SIZE-1)

uint32_t Pisano_Checksum(
  uint16_t *buffer,  // points to the data to scan
  int size           // number of 16-bit WORDS to scan
) {
  uint32_t
  // Start
    X = *buffer,
    Y = 0x1234, // anything except 0 or FFFF
    C = 1,
    t;

  // Loop
  while (size) {
    size--;
    buffer++;

    t = X + Y + C;   X = Y ^ *buffer;
    C = t >> PISANO_WIDTH;  Y = t & MASK;
  }
  // Finish
  return C+Y+(X << PISANO_WIDTH);
}

Aaaand that's it.

I provided a tiny main() to verify the basics.

gcc -Wall test_Pisano16x2.c -o test_pisano && ./test_pisano 
Checksum: 8573B7DA

What remains now to be done ?

Discussions