1 // Copyright (C) 2002 Graydon Hoare <graydon@pobox.com>
2 //
3 // This program is made available under the GNU GPL version 2.0 or
4 // greater. See the accompanying file COPYING for details.
5 //
6 // This program is distributed WITHOUT ANY WARRANTY; without even the
7 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 // PURPOSE.
9 
10 #ifndef __ADLER32_HH__
11 #define __ADLER32_HH__
12 
13 // this is a pseudo-adler32. it does not use a prime modulus. it is not
14 // entirely clear that this matters; it is what rsync and xdelta both do
15 // and it seems to work.
16 
17 #include "numeric_vocab.hh"
18 #include "sanity.hh"
19 
20 struct
21 adler32
22 {
23   u32 s1, s2, len;
24   static const u32 mask = 0xffff;
25 
sumadler3226   inline u32 sum() const
27   {
28     return (s2 << 16) | s1;
29   }
30 
inadler3231   inline void in(u8 c)
32   {
33     s1 += widen<u32,u8>(c);
34     s1 &= mask;
35     s2 += s1;
36     s2 &= mask;
37     ++len;
38   }
39 
outadler3240   inline void out(u8 c)
41   {
42     s1 -= widen<u32,u8>(c);
43     s1 &= mask;
44     s2 -= (len * widen<u32,u8>(c)) + 1;
45     s2 &= mask;
46     --len;
47   }
48 
49   // monotone only uses the adler32 in order to do a rolling window over
50   // the data for the purpose of finding matches in xdelta.cc
51   // Optimize for this case avoiding a lot of unneeded masking.
replace_withadler3252   inline void replace_with(u8 const * ch, std::string::size_type count)
53   {
54     I(count < 255);
55     s1 = 1;
56     s2 = 0;
57     len = count;
58     // Can't overflow in this case as (for s1) 255*255 < 0xffff,
59     // and (for s2) (maxs1 = 255*255)*255 < 0xffff_ffff
60     while (count--)
61       {
62         u32 c = widen<u32,u8>(*(ch++));
63         s1 += c;
64         s2 += s1;
65       }
66     s1 &= mask;
67     s2 &= mask;
68   }
69 
adler32adler3270   adler32()
71     : s1(1), s2(0), len(0)
72   {}
73 
adler32adler3274   adler32(u8 const * ch, std::string::size_type count)
75   {
76     replace_with(ch, count);
77   }
78 };
79 
80 #endif // __ADLER32_HH__
81 
82 // Local Variables:
83 // mode: C++
84 // fill-column: 76
85 // c-file-style: "gnu"
86 // indent-tabs-mode: nil
87 // End:
88 // vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
89