RE: Re: Adler-32 Checksum

The problem is not whether we would like the additive/subtration property to
hold vs to recompute the checksum. Even if we recompute the checksum, there
might be inconsistency if the ordering of the elements is different. It is
for this reason that Alder-32 algorithm might not be the solution for the
audit mechanism. This calls for a "descriptor" which is order-invariant and
it would be desirable to have it relatively easy to compute.

Best Wishes,
Anurag

-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf
Of Michael Tuexen
Sent: Tuesday, June 28, 2005 6:27 PM
To: Thomas Dreibholz
Cc: [email protected]; [email protected]; Silverton Aron-C1710C; Xie
Qiaobing-QXIE1
Subject: [Rserpool] Re: Adler-32 Checksum


Dear all,

see my comments in-line.

Best regards
Michael

On Jun 28, 2005, at 2:12 PM, Thomas Dreibholz wrote:

> -----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).
That is one question: Do we want such a function? Adler32 and CRC do not
have the property. The Internet checksum has. I would prefer the  
Internet
checksum to XOR.
But the question remains: Do we need the function which with 'an update
possibility' or can we just recompute the stuff?
The problem I see is that by computing we really compare stuff. But  
just doing
incremental updates we might report something we really do not have  
anymore
in the cache (due to sume bugs, for example). So it would be more  
robust to
use something like Adler32/CRC32 as the Internet Checksum, but it  
costs more
performance. But I'm not sure how critical that is.
>
>
> 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)
>
> iD8DBQFCwT7O32BbsHYPLWURAnYyAJ0ZC9dcA30KFDUwQa+7jkBuzqhhtgCfcMB7
> +B04WYiuaA4E+lF56LgHn9g=
> =k2EC
> -----END PGP SIGNATURE-----
>
>


_______________________________________________
rserpool mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/rserpool