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 <string>
18#include "numeric_vocab.hh"
19#include "sanity.hh"
20
21struct
22adler32
23{
24 u32 s1, s2, len;
25 static const u32 mask = 0xffff;
26
27 inline u32 sum() const
28 {
29 return (s2 << 16) | s1;
30 }
31
32 inline void in(u8 c)
33 {
34 s1 += static_cast<u32>(c);
35 s1 &= mask;
36 s2 += s1;
37 s2 &= mask;
38 ++len;
39 }
40
41 inline void out(u8 c)
42 {
43 s1 -= static_cast<u32>(c);
44 s1 &= mask;
45 s2 -= (len * static_cast<u32>(c)) + 1;
46 s2 &= mask;
47 --len;
48 }
49
50 // monotone only uses the adler32 in order to do a rolling window over
51 // the data for the purpose of finding matches in xdelta.cc
52 // Optimize for this case avoiding a lot of unneeded masking.
53 inline void replace_with(u8 const * ch, std::string::size_type count)
54 {
55 I(count < 255);
56 s1 = 1;
57 s2 = 0;
58 len = count;
59 // Can't overflow in this case as (for s1) 255*255 < 0xffff,
60 // and (for s2) (maxs1 = 255*255)*255 < 0xffff_ffff
61 while (count--)
62 {
63 u32 c = static_cast<u32>(*(ch++));
64 s1 += c;
65 s2 += s1;
66 }
67 s1 &= mask;
68 s2 &= mask;
69 }
70
71 adler32()
72 : s1(1), s2(0), len(0)
73 {}
74
75 adler32(u8 const * ch, std::string::size_type count)
76 {
77 replace_with(ch, count);
78 }
79};
80
81// Local Variables:
82// mode: C++
83// fill-column: 76
84// c-file-style: "gnu"
85// indent-tabs-mode: nil
86// End:
87// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
88
89#endif // __ADLER32_HH__

Archive Download this file

Branches

Tags

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