This post relates to suspect calculations.  Apologies to all involved
if all of your calculations are right and I somehow got all of mine
wrong.  (Please confirm or debunk my suspicions if you can.)

Recently, I decided to try implementing the Adler-32 algorithm for
fun.  The algorithm is described in the last parts of RFC 1950 and at
its Wikipedia page (http://en.wikipedia.org/wiki/Adler-32).  The
calculations involve modulo addition.  Computer scientists know that
such calculations can be done by doing the modulo reduction after each
addition, or save the additions up and do the reduction right before
the register would overflow.  Assuming 8-bit bytes and 32-bit
registers, the RFC suggests that modulo reduction can be delayed for
5552 bytes.  The Wikipedia entry, however, suggests only a 5550-byte
limit.  Said web entry doesn't state its reasoning, except to mention
that the reasoning is intricate and involves detailed analysis of the
reading & reduction loop.

Question 1: can anyone give me the full reasoning the Wikipedia person
used?

Now that 64-bit integer arithmetic is common in computers, I wanted to
update the limit to the next generation, hopefully in a way that will
work no matter the register size in the future.  So I tried to
calculate the general limit before reduction.

An Adler-32 checksum is made from combining two variables.  The first
one is the sum of all bytes plus one.  The second is the sum of all
values of the first variable.  Both sums are taken modulo 65521 (the
largest prime within 16 bits).  The least non-negative residue of
those variables are combined by shifting the second residue up 16 bits
and combining it with the first residue, resulting in the checksum.
Finding the iteration limit supposes the worst case scenario where
each byte takes its maximum value.  Let's call the value CM, which is
255 for 8-bit bytes.  The two variables proceed as:

s1(1): 1 + CM, 1 + 2 * CM, 1 + 3 * CM, ... 1 + n * CM
s2(0): 1 + CM, 2 + 3 * CM, 3 + 6 * CM, ... n + n(n+1)/2 * CM

where n is the number of steps taken.  The n(n+1)/2 formula is the sum
of all whole numbers from 1 to n.  (I think Euler figured that out
first.)  Obviously, s2 will bust the limit first.  We have to keep a
next step from going over the register's maximum value so:

n + n(n+1)/2 * CM <= MAX_REGISTER - BASE

where BASE is 65521 and MAX_REGISTER is the largest value the register
type can take.  For (at the time) regular computers, the register was
32-bits long, giving a maximum value of 2^32 - 1 = 4,294,967,295.  We
can reduce the equation to:

n + (n^2 + n) * CM/2 <= MAX_REGISTER - BASE

CM/2 * n^2 + (1 + CM/2) * n <= MAX_REGISTER - BASE

CM/2 * n^2 + (1 + CM/2) * n + (BASE - MAX_REGISTER) <= 0

CM * n^2 + (2 + CM) * n + 2 * (BASE - MAX_REGISTER) <= 0

plugging in our system's variables gives:

255*n^2 + 257*n - 8,589,803,548 <= 0

(Hopefully, that "4" isn't a "9;" can't read my writing.)  The roots
of that equation are approximately 5,803.4 and -5,804.4.  Plugging in
values around the positive root results in n <= 5,803.  I tried to
send a private message to Mark Adler asking why my result differed,
but I haven't got anything back (yet).  I've done other stuff for a
week, but now I'm following up again.

I tried to Google for more useful information about Adler-32 to help.
I eventually found an old post of mine sent to the sci.math
newsgroups.  It had a different quadratic formula.  My post said that
I found it from some supplemental material.  Groping for answers, I
eventually found the material from looking at the zlib source code, in
"adler32.c":

//=============================================
#define BASE 65521UL    /* largest prime smaller than 65536 */
#define NMAX 5552
/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <=
2^32-1 */
//=============================================

This different quadratic equation reduces to:

255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1

255n(n+1) + 2(n+1)(BASE-1) <= 2(2^32-1)

(n+1)(255n + 2(BASE-1)) <= 2(2^32-1)

255n^2 + (255+2(BASE-1))n + 2(BASE-1) <= 2(2^32-1)

255n^2 + (255+2(BASE-1))n + 2((BASE-1) - (2^32-1)) <= 0

255 * n^2 + 131,295 * n - 8,585,803,550 <= 0

This has roots of 5,550.8 and -6,065.7.  Plugging in values around the
positive root gives n <= 5,550.  Yes, this is the same value from
Wikipedia.

Observation 2:  I guess the effort the Wikipedia guy in correcting the
limit through analyzing the read & reduce loop is commendable.
However,...

Observation 3:  The difference you saw between theory and practice
wasn't mysterious.  The two values do match; it's just that the theory
guy got his answer wrong.

Observation 4:  Either the first guy guesstimated the root or got his
exact calculations wrong, and then either got the confirmation wrong
or never bothered to check.  I have checked mine, but through the use
of Google's built-in calculator and visiting quadratic equation web
sites.  This wasn't feasible in 1995 (the earliest copyright on
"adler32.c"), and the large numbers make hand checks hard, and home
computers were less powerful.  So maybe we can forgive this mistake.

Observation 5:  I can't believe it took nearly 15 years for someone to
finally confirm (and actually debunk) the first guy's calculations!
And this checksum has been all over the place since then.

Now I got worried.  I calculations still had a different result
(5,803) and was based on a different formula.  Then I realized that if
the first guy messed up his computation, maybe he messed up the entire
formula.

Question 6: can anyone tell me how the "adler32.c" shorthand formula
was derived?

So I finally decided to manually crank out the steps and see what
happens.  I have an August 2002 eMac running Mac OS X 10.4.11 on a
PowerPC G4 and wrote this code:

//=============================================
#include <climits>
#include <iomanip>
#include <ios>
#include <iostream>

int  main( int argc, char * const argv[] )
{
    using std::setw;

    for ( unsigned long long  i = 0, s1 = 1, s2 = 0 ; i < 6000 ; ++i,
     s1 += UCHAR_MAX, s2 += s1 )
        std::cout << std::dec << setw(4) << i << '\t' << std::hex <<
         setw(8) << static_cast<unsigned long>(s1) << '\t' << setw(16)
<<
         s1 << '\t' << setw(8) << static_cast<unsigned long>(s2) <<
         '\t' << setw(16) << s2 << '\n';

    return 0;

on an 8-bit byte system with 32-bit longs and 64-bit double-longs.
The registers are 64 bits so I can check beyond what a 32-bit type
will turnover.  This prints a table with the following 5 columns: step
number, s1 within 32 bits, s1, s2 within 32 bits, and s2.  I'm always
entering the maximum byte-value.  This gives the following table:

//=============================================
   0     1             1     0             0
   1   100           100   100           100
   2   1ff           1ff   2ff           2ff
   3   2fe           2fe   5fd           5fd
   4   3fd           3fd   9fa           9fa
   5   4fc           4fc   ef6           ef6
   6   5fb           5fb  14f1          14f1
   7   6fa           6fa  1beb          1beb
   8   7f9           7f9  23e4          23e4
   9   8f8           8f8  2cdc          2cdc
  10   9f7           9f7  36d3          36d3
  11   af6           af6  41c9          41c9
  12   bf5           bf5  4dbe          4dbe
  13   cf4           cf4  5ab2          5ab2
  14   df3           df3  68a5          68a5
  15   ef2           ef2  7797          7797
  16   ff1           ff1  8788          8788
  17  10f0          10f0  9878          9878
  18  11ef          11ef  aa67          aa67
//...
//=============================================

Let's go to the conventional limit of 5,550:

//=============================================
//...
5547  159556       159556       e9e03cb9      e9e03cb9
5548  159655       159655       e9f5d30e      e9f5d30e
5549  159754       159754       ea0b6a62      ea0b6a62
5550  159853       159853       ea2102b5      ea2102b5
5551  159952       159952       ea369c07      ea369c07
5552  159a51       159a51       ea4c3658      ea4c3658
5553  159b50       159b50       ea61d1a8      ea61d1a8
//...
//=============================================

I don't see any turnover here yet.  Let's go to my limit of 5,803:

//=============================================
//...
5801  169258        169258      ffc86a8c      ffc86a8c
5802  169357        169357      ffdefde3      ffdefde3
5803  169456        169456      fff59239      fff59239
5804  169555        169555         c278e     1000c278e
5805  169654        169654        22bde2     10022bde2
5806  169753        169753        395535     100395535
//...
//=============================================

Well, it seems that a 32-bit register will turnover when it goes past
5,803 to the 5,804th step!  I did a modified program to help confirm:

//=============================================
// I guess any applicable copyrights are mine (Daryle Walker (c)
2008).
#include <climits>
#include <iomanip>
#include <ios>
#include <iostream>

struct adler32
{
    unsigned long long  s1, s2;
    adler32()  : s1( 1 ), s2( 0 )  {}
    void  operator ()( unsigned char byte ) { s1 += byte; s2 += s1; }
    unsigned long  operator ()() const
    { return ((s2 % 65521) << 16) | (s1 % 65521); }
    void  operator ()( void const *b, unsigned l )
    {
        unsigned char const *bb = static_cast<unsigned char
const*>(b);
        while ( l-- )  this->operator ()( *bb++ );
    }

    adler32  computer;

    computer( "Wikipedia", 9 );
    cout << computer() << '\n';
    computer = adler32();

    for ( int  i = 0 ; i < 6000 ; ++i, computer(UCHAR_MAX) )
        cout << std::dec << setw(4) << i << '\t' << std::hex <<
         setw(8) <<
...

read more »

There is no mistake in the zlib implementation of Adler-32.  A quick
look at the wikipedia article shows an error, in that the author
claims that "a" can be 0x1013a or 65850 after "a" has been modded by
65521.  That's not possible, since anything modulo 65521 will always
be in the range 0 to 65520.

The zlib derivation is simple.  Assume that sum1 and sum2 have their
maximum possible values at the start of the loop, which are 65520 and
65520.  Then run 255's through the loop until just before sum2
overflows 2^32 - 1.  If you run 5,552 255's through the loop, then
sum1 is 1,481,280 and sum2 is 4,294,690,200.  sum2 is less than 2^32
== 4,294,967,296.  So the maximum n is 5,552.

That's all there is to it.

Mark

1. You did only a partial worst case analysis: As Mark already said:
Because the Adler-32 update function can be used with the result of a
previous Adler-32 calculation the maximum starting values of s1 and s2
are both BASE-1 (s1=s2=BASE-1 can be produced with BASE-2 bytes of 1).
The 0 and 1 are the very first starting values (and with these s2
overflows for n=5804 if all input is 255).

2. With the starting values s1=s2=BASE-1 the formula from zlib.h is
correct
  255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1   or
  255/2*n^2 + n*(BASE-1+255/2) + BASE-1 - (2^32-1) <= 0
The roots are n1=5552.190793923682684283598574 (or n2=-6067.0...),
calculated with Pari/GP:
     BASE = 65520
     a = 255/2
     b = BASE-1 + 255/2
     c = BASE-1 - (2^32-1)
     d = sqrt(b^2 - 4*a*c)
     n1 = (-b + d)/(2*a)
     n2 = (-b - d)/(2*a)

3. Therefore the value n=5552 from RFC and zlib is correct. You could
also have easily shown this by experiment with a short program, which
determines the value n for which s2 overflows:

   program adlerovr;
   const
     BASE = 65521;
     lim  = int64(1) shl 32;
   var
     s1,s2: int64;
     n: longint;
   begin
     s1 := BASE-1;
     s2 := BASE-1;
     n := 0;
     repeat
       s1 := s1 + 255;
       s2 := s2 + s1;
       inc(n);
     until s2>=lim;
     writeln('Adler-32 overflow for n=',n);
   end.

As expected the result is: Adler-32 overflow for n=5553.

4. If you are aware that you make typos or other glitches you should
double check your calculation, your formula

  255 * n^2 + 131,295 * n - 8,585,803,550 <= 0

should read

  255 * n^2 + 131,295 * n - 8,589,803,550 <= 0

Wolfgang

--
In order to e-mail me a reply to this message, you will have
to remove PLEASE.REMOVE from the address shown in the header
or get it from http://home.netsurf.de/wolfgang.ehrhardt
(Free open source Crypto, AES, CRC, Hash for Pascal/Delphi)

(<http://en.wikipedia.org/w/index.php?title=Adler-32&oldid=179953130>
or older)

Mod was introduced by a person named Vicaya at 01:11, 3 January 2008.
either s/he does not know better or does not care (anyway: the
sentence "Because this implementation does not completely reduce a" is
now obviously wrong!) But because 5550 is safe, there is no bug in the
code, it is only slightly suboptimal.

Wolfgang
--
In order to e-mail me a reply to this message, you will have
to remove PLEASE.REMOVE from the address shown in the header
or get it from http://home.netsurf.de/wolfgang.ehrhardt
(Free open source Crypto, AES, CRC, Hash for Pascal/Delphi)

The correct numbers atre of course:  BASE=65521 and
n1 = 5552.187045454599584508943831

Wolfgang

On Aug 25, 2:50 am, Daryle Walker <dary...@gmail.com> wrote:
[SNIP]

s1(BASE - 1): BASE - 1 + CM, BASE - 1 + 2 * CM, BASE - 1 + 3 * CM,
              ... BASE - 1 + n * CM
s2(BASE - 1): 2(BASE-1) + CM, 3(BASE-1) + 3 * CM, 4(BASE-1) + 6 * CM,
              ... (n + 1)(BASE - 1) + n(n + 1)/2 * CM

Now the limit equation is:

(n + 1)(BASE - 1) + n(n + 1)/2 * CM <= MAX_REGISTER

which reduces to:

CM * n^2 + (CM + 2(BASE - 1)) * n + 2(BASE - 1 - MAX_REGISTER) <= 0

Using our default values gives:

255 * n^2 + 131,295 * n - 8,589,803,550 <= 0

which has roots around -6,067.07 and 5,552.19.  Testing around the
positive root gives Adler's result of 5,552!  So,... never mind.

Everyone can keep their entry limits to 5,552 to be safe.  And this
proves the Wikipedia entry, which has now been purged (not by me), to
be wrong.  However, you could use my 5,803 limit to start a check-sum
calculation from scratch, but reset it to 5,552 after the first
turnover.

By the way, I tried adapting my code for 64-bit registers and
retaining 8-bit bytes.  The quadratic equation computer web page
couldn't accurately go up that high because it used floating point,
but it gave me an estimate to run with manually.  The equivalent of
the 5,552 worse-case limit is 380,368,439.  The equivalent for my
5,803 initial limit is 380,368,696.  (Each run took over 20 minutes,
opposed to a few seconds for the 32-bit runs.)

Daryle Walker

Daryle Walker

All calculations took less than 1 ms each on Pari/GP:

BASE = precprime(2^32)
a = 255/2
b = BASE-1 + 255/2
c = BASE-1 - (2^64-1)
d = sqrt(b^2 - 4*a*c)
n1 = (-b + d)/(2*a)
n2 = (-b - d)/(2*a)

(time for script writing not included :)

Wolfgang

--
In order to e-mail me a reply to this message, you will have
to remove PLEASE.REMOVE from the address shown in the header
or get it from http://home.netsurf.de/wolfgang.ehrhardt
(Free open source Crypto, AES, CRC, Hash for Pascal/Delphi)

Thanks for that!  I figured there must be a sequence that gives the
maximum s1 and s2 values, but I never tried to find one.  I'm
surprised it's that easy.  In fact, for any odd BASE, s2 ends up as
BASE-1 (as well as s1 of course).

Mark

s1(1): 2, 3, 4, 5, ... n + 1
s2(0): 2, 5, 8, 14, ... (n + 1)(n + 2) / 2 - 1

and the two sequences equal when n is either +1 or -2, or due to
modulo arithmetic, when n is congruent to those values modulo BASE.
Now using 65,520 for n gives us what we want, but did we get lucky
there?  Or is there a way to find an n for any given value (less than
BASE) that we want s1 and s2 to simultaneously cover?

Daryle Walker

Mark

Daryle Walker

Just for kicks, I found the shortest sequence that gives s1 == s2 ==
65520.  It is 128 255's, a 239, and 128 more 255's.

There are many others of this length (257), but this is this simplest
one to describe.  There can't be any shorter sequences that give s1 ==
65520, since 256 bytes can't add up to 65519.

Mark

yes it was kind of luck, that the most obvious choice
for producing S1=BASE-1 gives S2=BASE-1 too. But that
result was not critical for the proof that n=5552 is
correct: From the simple fact that S1=BASE-1 is reachable
you can plug the min/max starting values of S2 in

255/2*n^2 + n*(BASE-1+255/2) + S2 - (2^32-1) <= 0

With the maximum S2=BASE-1 we have the old known value
5552.187045454599584508943831, and with the minimum
S2=0 you get 5552.231272070943830898881692. Therefore
the value is independent of the starting value of S2.

Mark,

if you start with any value S1(0) you can always
construct a sequence with S1=S2=BASE-1:

1. First feed in 1 bytes until you get S1=BASE-1

2. If S2=BASE-1 your done

3. Feed in a 0 byte. This does not change S1, and decrements
   S2 by 1.
4. If S2=-1 mod BASE your done, otherwise repeat 3.

Wolfgang

--
In order to e-mail me a reply to this message, you will have
to remove PLEASE.REMOVE from the address shown in the header
or get it from http://home.netsurf.de/wolfgang.ehrhardt
(Free open source Crypto, AES, CRC, Hash for Pascal/Delphi)

Step 0: Initialize Adler with starting values S1_Start, S2_Start

Step 1: If S1_Dest=0 goto step 6

Step 2: If S1=S1_Dest goto step 4.

Step 3: Feed in 1 and goto step 2

Step 4: Here S1=S1_Dest with S1<>0.

Step 5: If S2=S2_Dest then terminate, otherwise feed in 0
        and repeat step 5. Note that this step does not
        change S1=S1_Dest and increments S2 by S1_Dest.
        Because S1_Dest is nonzero and BASE is prime
        this step is repeated at most BASE times.

Step 6: Here S1_Dest=0. Use steps 0 to 6 to construct a
        sequence for S1_Dest=BASE-1 and the given S2_Dest.
        Feed in a final 1, this gives S1=0, S2=S2_Dest.

Wolfgang

--
In order to e-mail me a reply to this message, you will have
to remove PLEASE.REMOVE from the address shown in the header
or get it from http://home.netsurf.de/wolfgang.ehrhardt
(Free open source Crypto, AES, CRC, Hash for Pascal/Delphi)

Mark

Jeff

On Aug 25, 10:22 am, Mark Adler <mad...@alumni.caltech.edu> wrote:

Phil
--
The fact that a believer is happier than a sceptic is no more to the
point than the fact that a drunken man is happier than a sober one.
The happiness of credulity is a cheap and dangerous quality.
-- George Bernard Shaw (1856-1950), Preface to Androcles and the Lion