[NUT-devel] Incomplete description of checksum algorithm

[Michael Niedermayer]

Hi

On Thu, Feb 16, 2006 at 01:47:32AM +0100, Alexander Strasser wrote:
[...]
> > crc32 checksum
> >     The checksum is choosen so that c(x) is a multiple of
> >     x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1 over GF(2)
> >     c(x) is the polynom coresponding to the block from and including the
> >     forward ptr and upto and including the checksum
> >     c(x)= (1&(d[0]>>8))*x^(n-1) + (1&(d[0]>>7))*x^(n- 2) + ...
> >         + (1&(d[1]>>8))*x^(n-9) + (1&(d[1]>>7))*x^(n-10) + ...
> >         + ...
> >         + ... + (1&(d[n/8-1]>>1))*x^1 + (1&(d[n/8-1]>>0))*x^0
> >     alternatively you can simply run
> >     crc=0;
> >     for(i=0; i<size; i++){
> >         crc ^= buf[i]<<24;
> >         for(j=0; j<8; j++)
> >             crc= (crc<<1) ^ (0x04C11DB7 & (crc>>31));
> >     }
> >     over the data  
> 
>   ok, while we are at it, should we use non zero initial value? if yes which?

personally i would simply include the forward ptr, so the all zero case would
naturally be gone, if the others are against this then we must either use a 
non zero initial value or xor some part of the whole (like the checksum) with
some non zero value
which? well -1 seems popular ...

so one of the following is needed
* add some guaranteed non zero element (iam not sure if width, sample_rate,...
  should be considered enough because IMHO it should be possible to find a
  undamaged packet purely with the checksum and without parsing the whole)
  IMHO the forward_ptr is ideal choice for this ...
* set the initial value to -1
* xor the checksum with -1

[...]

-- 
Michael