8 // According to librsync/rollsum.h:
9 // "We should make this something other than zero to improve the
10 // checksum algorithm: tridge suggests a prime number."
11 // apenwarr: I unscientifically tried 0 and 7919, and they both ended up
12 // slightly worse than the librsync value of 31 for my arbitrary test data.
13 #define ROLLSUM_CHAR_OFFSET 31
17 uint8_t window[BUP_WINDOWSIZE];
22 // These formulas are based on rollsum.h in the librsync project.
23 static void rollsum_add(Rollsum *r, uint8_t drop, uint8_t add)
26 r->s2 += r->s1 - (BUP_WINDOWSIZE * (drop + ROLLSUM_CHAR_OFFSET));
30 static void rollsum_init(Rollsum *r)
32 r->s1 = BUP_WINDOWSIZE * ROLLSUM_CHAR_OFFSET;
33 r->s2 = BUP_WINDOWSIZE * (BUP_WINDOWSIZE-1) * ROLLSUM_CHAR_OFFSET;
35 memset(r->window, 0, BUP_WINDOWSIZE);
39 // For some reason, gcc 4.3 (at least) optimizes badly if find_ofs()
40 // is static and rollsum_roll is an inline function. Let's use a macro
41 // here instead to help out the optimizer.
42 #define rollsum_roll(r, ch) do { \
43 rollsum_add((r), (r)->window[(r)->wofs], (ch)); \
44 (r)->window[(r)->wofs] = (ch); \
45 (r)->wofs = ((r)->wofs + 1) % BUP_WINDOWSIZE; \
49 static uint32_t rollsum_digest(Rollsum *r)
51 return (r->s1 << 16) | (r->s2 & 0xffff);
55 static uint32_t rollsum_sum(uint8_t *buf, size_t ofs, size_t len)
60 for (count = ofs; count < len; count++)
61 rollsum_roll(&r, buf[count]);
62 return rollsum_digest(&r);
66 int bupsplit_find_ofs(const unsigned char *buf, int len, int *bits)
72 for (count = 0; count < len; count++)
74 rollsum_roll(&r, buf[count]);
75 if ((r.s2 & (BUP_BLOBSIZE-1)) == ((~0) & (BUP_BLOBSIZE-1)))
79 unsigned rsum = rollsum_digest(&r);
81 rsum >>= BUP_BLOBBITS;
82 for (*bits = BUP_BLOBBITS; (rsum >>= 1) & 1; (*bits)++)
92 #ifndef BUP_NO_SELFTEST
94 int bupsplit_selftest()
97 uint32_t sum1a, sum1b, sum2a, sum2b, sum3a, sum3b;
101 for (count = 0; count < sizeof(buf); count++)
102 buf[count] = random();
104 sum1a = rollsum_sum(buf, 0, sizeof(buf));
105 sum1b = rollsum_sum(buf, 1, sizeof(buf));
106 sum2a = rollsum_sum(buf, sizeof(buf) - BUP_WINDOWSIZE*5/2,
107 sizeof(buf) - BUP_WINDOWSIZE);
108 sum2b = rollsum_sum(buf, 0, sizeof(buf) - BUP_WINDOWSIZE);
109 sum3a = rollsum_sum(buf, 0, BUP_WINDOWSIZE+3);
110 sum3b = rollsum_sum(buf, 3, BUP_WINDOWSIZE+3);
112 fprintf(stderr, "sum1a = 0x%08x\n", sum1a);
113 fprintf(stderr, "sum1b = 0x%08x\n", sum1b);
114 fprintf(stderr, "sum2a = 0x%08x\n", sum2a);
115 fprintf(stderr, "sum2b = 0x%08x\n", sum2b);
116 fprintf(stderr, "sum3a = 0x%08x\n", sum3a);
117 fprintf(stderr, "sum3b = 0x%08x\n", sum3b);
119 return sum1a!=sum1b || sum2a!=sum2b || sum3a!=sum3b;
122 #endif // !BUP_NO_SELFTEST