Adler-32 Checksum

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Monday 27 June 2005 23:03, Michael Tuexen wrote:
Hi all!

>     Implementation Note: when the internal handlespace changes (e.g., a
>     new PE added or an existing PE removed), an implementation needs not
>     to re-calculate the affected PE checksum; it should instead simply
>     update the checksum by adding or subtracting the byte block of the
>     corresponding PE from the previous checksum value.
>     is at least miss-leading.

The problem of the Adler-32 checksum is that adding or subtracting a byte
block from the checksum value is not possible. Example: The handlespace
contains the pool "PoolTEST" with PEs 0x1234, 0x5000, 0x5001, ..., 0x5100.
The checksum of the handlespace is therefore
f(PoolTEST1234PoolTEST5000PoolTEST5001 ... PoolTEST5100). If PE 0x5000 is
removed, at least the Adler-32 checksum of PE 0x5001 to 0x5100 must be
recalculated, with the seed set to the checksum of PE 0x1234. The Adler-32
algorithm depends on the checksum of the previous elements as seed, therefore
it is not possible to store the checksum of each PE entry and finally combine
the checksums of PE 0x1234 and the checksum of PE 0x5000 to PE 0x5100 to the
new checksum.

This is the Adler-32 algorithm:

const uint32_t crcBase = 65521;
uint32_t adler32(const uint32_t seed, const char* buffer, const size_t size)
{
   uint32_t s1  = seed & 0xffff;
   uint32_t s2  = (seed >> 16) & 0xffff;
   for(size_t i = 0;i < size;i++) {
      s1 = (s1 + buffer[i]) % crcBase;
      s2 = (s2 + s1) % crcBase;
   }
   unsigned int adler32 = (s2 << 16) + s1;
   return(adler32);
}

Depending on the seed value (i.e. the checksum of the previous elements), a
counter wrap (due to modulo operation by crcBase) appears at different
positions in the buffer.


For the handlespace audit, it is necessary to have a checksum function f which
provides the property that when a PE entry b is deleted from the set of PE
entries a,b,c, then the checksum f(ac) has to be computable by f(abc) - f(b)
without re-computing f(a) or f(c). "-" denotes an appropriate subtraction
operation. Furthermore, it must be possible to add an element b to the set of
PE entries a,c and compute the checksum f(abc) = f(a) + f(b) + f(c) without
having to re-computing f(a) or f(c) ("+" denotes and appropriate
concatencation function).


A possible checksum function fulfilling the described requirements is XOR. But
this function seems to be too simple, the probability that a handlespace
inconsistency is not recognised may be too high?


Best regards
- --
=======================================================================
 Dipl.-Inform. Thomas Dreibholz

 University of Essen,                            Room ES210
 Inst. for Experimental Mathematics              Ellernstraße 29
 Computer Networking Technology Group            D-45326 Essen/Germany
- -----------------------------------------------------------------------
 E-Mail:     [email protected]
 Homepage:   http://www.exp-math.uni-essen.de/~dreibh
=======================================================================
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFCwUpN32BbsHYPLWURAmrfAKDLjR/V/iCcqLY4PABcFnhzzN6lHgCfX/Lc
xc6avZGu7wx1sszVebgEjPU=
=5Y+y
-----END PGP SIGNATURE-----