7 // According to librsync/rollsum.h:
8 // "We should make this something other than zero to improve the
9 // checksum algorithm: tridge suggests a prime number."
10 // apenwarr: I unscientifically tried 0 and 7919, and they both ended up
11 // slightly worse than the librsync value of 31 for my arbitrary test data.
12 #define ROLLSUM_CHAR_OFFSET 31
16 uint8_t window[BUP_WINDOWSIZE];
21 // These formulas are based on rollsum.h in the librsync project.
22 static void rollsum_add(Rollsum *r, uint8_t drop, uint8_t add)
25 r->s2 += r->s1 - (BUP_WINDOWSIZE * (drop + ROLLSUM_CHAR_OFFSET));
29 static void rollsum_init(Rollsum *r)
31 r->s1 = BUP_WINDOWSIZE * ROLLSUM_CHAR_OFFSET;
32 r->s2 = BUP_WINDOWSIZE * (BUP_WINDOWSIZE-1) * ROLLSUM_CHAR_OFFSET;
34 memset(r->window, 0, BUP_WINDOWSIZE);
38 // For some reason, gcc 4.3 (at least) optimizes badly if find_ofs()
39 // is static and rollsum_roll is an inline function. Let's use a macro
40 // here instead to help out the optimizer.
41 #define rollsum_roll(r, ch) do { \
42 rollsum_add((r), (r)->window[(r)->wofs], (ch)); \
43 (r)->window[(r)->wofs] = (ch); \
44 (r)->wofs = ((r)->wofs + 1) % BUP_WINDOWSIZE; \
48 static uint32_t rollsum_digest(Rollsum *r)
50 return (r->s1 << 16) | (r->s2 & 0xffff);
54 static uint32_t rollsum_sum(uint8_t *buf, size_t ofs, size_t len)
59 for (count = ofs; count < len; count++)
60 rollsum_roll(&r, buf[count]);
61 return rollsum_digest(&r);
65 int bupsplit_find_ofs(const unsigned char *buf, int len, int *bits)
71 for (count = 0; count < len; count++)
73 rollsum_roll(&r, buf[count]);
74 if ((r.s2 & (BUP_BLOBSIZE-1)) == ((~0) & (BUP_BLOBSIZE-1)))
78 unsigned rsum = rollsum_digest(&r);
80 rsum >>= BUP_BLOBBITS;
81 for (*bits = BUP_BLOBBITS; (rsum >>= 1) & 1; (*bits)++)
91 #ifndef BUP_NO_SELFTEST
93 int bupsplit_selftest()
96 uint32_t sum1a, sum1b, sum2a, sum2b, sum3a, sum3b;
100 for (count = 0; count < sizeof(buf); count++)
101 buf[count] = random();
103 sum1a = rollsum_sum(buf, 0, sizeof(buf));
104 sum1b = rollsum_sum(buf, 1, sizeof(buf));
105 sum2a = rollsum_sum(buf, sizeof(buf) - BUP_WINDOWSIZE*5/2,
106 sizeof(buf) - BUP_WINDOWSIZE);
107 sum2b = rollsum_sum(buf, 0, sizeof(buf) - BUP_WINDOWSIZE);
108 sum3a = rollsum_sum(buf, 0, BUP_WINDOWSIZE+3);
109 sum3b = rollsum_sum(buf, 3, BUP_WINDOWSIZE+3);
111 fprintf(stderr, "sum1a = 0x%08x\n", sum1a);
112 fprintf(stderr, "sum1b = 0x%08x\n", sum1b);
113 fprintf(stderr, "sum2a = 0x%08x\n", sum2a);
114 fprintf(stderr, "sum2b = 0x%08x\n", sum2b);
115 fprintf(stderr, "sum3a = 0x%08x\n", sum3a);
116 fprintf(stderr, "sum3b = 0x%08x\n", sum3b);
118 return sum1a!=sum1b || sum2a!=sum2b || sum3a!=sum3b;
121 #endif // !BUP_NO_SELFTEST