monotone

monotone Mtn Source Tree

Root/adler32.hh

1#ifndef __ADLER32_HH__
2#define __ADLER32_HH__
3
4// Copyright (C) 2002 Graydon Hoare <graydon@pobox.com>
5//
6// This program is made available under the GNU GPL version 2.0 or
7// greater. See the accompanying file COPYING for details.
8//
9// This program is distributed WITHOUT ANY WARRANTY; without even the
10// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
11// PURPOSE.
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
20struct
21adler32
22{
23 u32 s1, s2, len;
24 static const u32 mask = 0xffff;
25
26 inline u32 sum() const
27 {
28 return (s2 << 16) | s1;
29 }
30
31 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
40 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.
52 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
70 adler32()
71 : s1(1), s2(0), len(0)
72 {}
73
74 adler32(u8 const * ch, std::string::size_type count)
75 {
76 replace_with(ch, count);
77 }
78};
79
80// Local Variables:
81// mode: C++
82// fill-column: 76
83// c-file-style: "gnu"
84// indent-tabs-mode: nil
85// End:
86// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
87
88#endif // __ADLER32_HH__

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status