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