monotone

monotone Mtn Source Tree

Root/src/adler32.hh

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
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#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:

Archive Download this file

Branches

Tags

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