1 /* $Id: rsyncsum.hh,v 1.2 2003/09/27 21:31:04 atterer Exp $ -*- C++ -*-
3 |_) /| Copyright (C) 2000-2002 | richard@
4 | \/¯| Richard Atterer | atterer.net
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License, version 2. See
8 the file COPYING for details.
10 A 32 or 64 bit rolling checksum
21 # define INLINE inline
29 #include <serialize.hh>
30 //______________________________________________________________________
32 /** A 32 bit checksum with the special property that you do not need
33 to recalculate the checksum when data is added to the front/end of
34 the checksummed area, or removed from it.
36 Currently only adding to the end and removing from the front is
37 supported. Adding to the end is very slightly faster.
39 Many thanks to Andrew Tridgell and Paul Mackerras for the
40 algorithm - NB none of rsync's code is used.
42 Unless described otherwise, if a method returns an RsyncSum&, then
43 this is a reference to the object itself, to allow chaining of
44 calls, e.g. obj.addBack(x).addBack(y) */
47 /// Initialises the checksum with zero
48 RsyncSum() : sum(0) { };
49 /// Initialises with the checksum of a memory area
50 RsyncSum(const byte* mem, size_t len) : sum(0) { addBack(mem, len); };
51 /// Compare two RsyncSum objects
52 bool operator==(const RsyncSum& x) const { return get() == x.get(); }
53 bool operator!=(const RsyncSum& x) const { return get() != x.get(); }
54 bool operator< (const RsyncSum& x) const { return get() < x.get(); }
55 bool operator> (const RsyncSum& x) const { return get() > x.get(); }
56 bool operator<=(const RsyncSum& x) const { return get() <= x.get(); }
57 bool operator>=(const RsyncSum& x) const { return get() >= x.get(); }
58 /** Append memory area to end of area covered by the checksum */
59 RsyncSum& addBack(const byte* mem, size_t len);
60 /// Append one byte at end of area covered by the checksum
61 inline RsyncSum& addBack(byte x);
62 /** Append the same byte n times at end of area covered by the
63 checksum. (addBack() is not overloaded for this in order to
64 avoid confusion with removeFront(byte, size_t), which has the
65 same signature, but only removes one byte.) */
66 inline RsyncSum& addBackNtimes(byte x, size_t n);
67 /** Remove memory area from start of area covered by the checksum
68 @param len Number of bytes to remove from area, so it will cover
69 area-len bytes after call
70 @param areaSize Size covered by area before call (necessary for
72 RsyncSum& removeFront(const byte* mem, size_t len, size_t areaSize);
73 /** Remove one byte from start of area covered by checksum */
74 inline RsyncSum& removeFront(byte x, size_t areaSize);
75 /// Read stored checksum
76 uint32 get() const { return sum; }
77 /// Reset to initial state
78 RsyncSum& reset() { sum = 0; return *this; }
79 /// Check whether sum is zero
80 bool empty() const { return sum == 0; }
81 // Using default dtor & copy ctor
83 // Nothing magic about this constant; just a random number which,
84 // according to the rsync sources, improves the quality of the
86 static const uint32 CHAR_OFFSET = 0xb593;
89 //________________________________________
91 /** Like RsyncSum, but the checksum is a 64 bit value. However, the
92 checksum quality would only improve very little if exactly the
93 same algorithm were used, so this uses an additional 256-word
94 lookup table for more "randomness". */
97 RsyncSum64() : sumLo(0), sumHi(0) { };
98 inline RsyncSum64(const byte* mem, size_t len);
99 inline bool operator==(const RsyncSum64& x) const;
100 inline bool operator!=(const RsyncSum64& x) const;
101 inline bool operator< (const RsyncSum64& x) const;
102 inline bool operator> (const RsyncSum64& x) const;
103 inline bool operator<=(const RsyncSum64& x) const;
104 inline bool operator>=(const RsyncSum64& x) const;
105 INLINE RsyncSum64& addBack(const byte* mem, size_t len);
106 INLINE RsyncSum64& addBack(byte x);
107 INLINE RsyncSum64& addBackNtimes(byte x, size_t n);
108 RsyncSum64& removeFront(const byte* mem, size_t len, size_t areaSize);
109 inline RsyncSum64& removeFront(byte x, size_t areaSize);
110 /// Return lower 32 bits of checksum
111 uint32 getLo() const { return sumLo; }
112 /// Return higher 32 bits of checksum
113 uint32 getHi() const { return sumHi; }
114 RsyncSum64& reset() { sumLo = sumHi = 0; return *this; }
115 bool empty() const { return sumLo == 0 && sumHi == 0; }
117 template<class Iterator>
118 inline Iterator serialize(Iterator i) const;
119 template<class ConstIterator>
120 inline ConstIterator unserialize(ConstIterator i);
121 inline size_t serialSizeOf() const;
124 RsyncSum64& addBack2(const byte* mem, size_t len);
125 static const uint32 charTable[256];
129 INLINE ostream& operator<<(ostream& s, const RsyncSum& r);
130 INLINE ostream& operator<<(ostream& s, const RsyncSum64& r);
131 //______________________________________________________________________
133 RsyncSum& RsyncSum::addBack(byte x) {
135 uint32 b = sum >> 16;
136 a += x + CHAR_OFFSET;
138 sum = ((a & 0xffff) + (b << 16)) & 0xffffffff;
142 RsyncSum& RsyncSum::addBackNtimes(byte x, size_t n) {
144 uint32 b = sum >> 16;
145 b += n * a + (n * (n + 1) / 2) * (x + CHAR_OFFSET); // Gauß
146 a += n * (x + CHAR_OFFSET);
147 sum = ((a & 0xffff) + (b << 16)) & 0xffffffff;
151 RsyncSum& RsyncSum::removeFront(byte x, size_t areaSize) {
153 uint32 b = sum >> 16;
154 b -= areaSize * (x + CHAR_OFFSET);
155 a -= x + CHAR_OFFSET;
156 sum = ((a & 0xffff) + (b << 16)) & 0xffffffff;
159 //________________________________________
161 RsyncSum64::RsyncSum64(const byte* mem, size_t len) : sumLo(0), sumHi(0) {
165 bool RsyncSum64::operator==(const RsyncSum64& x) const {
166 return sumHi == x.sumHi && sumLo == x.sumLo;
168 bool RsyncSum64::operator!=(const RsyncSum64& x) const {
169 return sumHi != x.sumHi || sumLo != x.sumLo;
171 bool RsyncSum64::operator< (const RsyncSum64& x) const {
172 return (sumHi < x.sumHi) || (sumHi == x.sumHi && sumLo < x.sumLo);
174 bool RsyncSum64::operator> (const RsyncSum64& x) const {
175 return (sumHi > x.sumHi) || (sumHi == x.sumHi && sumLo > x.sumLo);
177 bool RsyncSum64::operator<=(const RsyncSum64& x) const {
180 bool RsyncSum64::operator>=(const RsyncSum64& x) const {
185 RsyncSum64& RsyncSum64::removeFront(byte x, size_t areaSize) {
186 sumHi = (sumHi - areaSize * charTable[x]) & 0xffffffff;
187 sumLo = (sumLo - charTable[x]) & 0xffffffff;
191 template<class Iterator>
192 inline Iterator RsyncSum64::serialize(Iterator i) const {
193 i = serialize4(sumLo, i);
194 i = serialize4(sumHi, i);
197 template<class ConstIterator>
198 inline ConstIterator RsyncSum64::unserialize(ConstIterator i) {
199 i = unserialize4(sumLo, i);
200 i = unserialize4(sumHi, i);
203 inline size_t RsyncSum64::serialSizeOf() const { return 8; }
206 # include <rsyncsum.ih> /* NOINLINE */