1 /*
2 * Copyright 2011 Avery Pennarun. All rights reserved.
3 *
4 * (This license applies to bupsplit.c and bupsplit.h only.)
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY AVERY PENNARUN AND CONTRIBUTORS ``AS
19 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
21 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
22 * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
23 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
29 * OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31 #include "bupsplit.h"
32 #include <stdint.h>
33 #include <memory.h>
34 #include <stdlib.h>
35 #include <stdio.h>
36
37 // According to librsync/rollsum.h:
38 // "We should make this something other than zero to improve the
39 // checksum algorithm: tridge suggests a prime number."
40 // apenwarr: I unscientifically tried 0 and 7919, and they both ended up
41 // slightly worse than the librsync value of 31 for my arbitrary test data.
42 #define ROLLSUM_CHAR_OFFSET 31
43
44 typedef struct {
45 unsigned s1, s2;
46 uint8_t window[BUP_WINDOWSIZE];
47 int wofs;
48 } Rollsum;
49
50
51 // These formulas are based on rollsum.h in the librsync project.
rollsum_add(Rollsum * r,uint8_t drop,uint8_t add)52 static void rollsum_add(Rollsum *r, uint8_t drop, uint8_t add)
53 {
54 r->s1 += add - drop;
55 r->s2 += r->s1 - (BUP_WINDOWSIZE * (drop + ROLLSUM_CHAR_OFFSET));
56 }
57
58
rollsum_init(Rollsum * r)59 static void rollsum_init(Rollsum *r)
60 {
61 r->s1 = BUP_WINDOWSIZE * ROLLSUM_CHAR_OFFSET;
62 r->s2 = BUP_WINDOWSIZE * (BUP_WINDOWSIZE-1) * ROLLSUM_CHAR_OFFSET;
63 r->wofs = 0;
64 memset(r->window, 0, BUP_WINDOWSIZE);
65 }
66
67
68 // For some reason, gcc 4.3 (at least) optimizes badly if find_ofs()
69 // is static and rollsum_roll is an inline function. Let's use a macro
70 // here instead to help out the optimizer.
71 #define rollsum_roll(r, ch) do { \
72 rollsum_add((r), (r)->window[(r)->wofs], (ch)); \
73 (r)->window[(r)->wofs] = (ch); \
74 (r)->wofs = ((r)->wofs + 1) % BUP_WINDOWSIZE; \
75 } while (0)
76
77
rollsum_digest(Rollsum * r)78 static uint32_t rollsum_digest(Rollsum *r)
79 {
80 return (r->s1 << 16) | (r->s2 & 0xffff);
81 }
82
83
rollsum_sum(uint8_t * buf,size_t ofs,size_t len)84 static uint32_t rollsum_sum(uint8_t *buf, size_t ofs, size_t len)
85 {
86 size_t count;
87 Rollsum r;
88 rollsum_init(&r);
89 for (count = ofs; count < len; count++)
90 rollsum_roll(&r, buf[count]);
91 return rollsum_digest(&r);
92 }
93
94
bupsplit_find_ofs(const unsigned char * buf,int len,int * bits)95 int bupsplit_find_ofs(const unsigned char *buf, int len, int *bits)
96 {
97 Rollsum r;
98 int count;
99
100 rollsum_init(&r);
101 for (count = 0; count < len; count++)
102 {
103 rollsum_roll(&r, buf[count]);
104 if ((r.s2 & (BUP_BLOBSIZE-1)) == ((~0) & (BUP_BLOBSIZE-1)))
105 {
106 if (bits)
107 {
108 unsigned rsum = rollsum_digest(&r);
109 rsum >>= BUP_BLOBBITS;
110 for (*bits = BUP_BLOBBITS; (rsum >>= 1) & 1; (*bits)++)
111 ;
112 }
113 return count+1;
114 }
115 }
116 return 0;
117 }
118
119
120 #ifndef BUP_NO_SELFTEST
121 #define BUP_SELFTEST_SIZE 100000
122
bupsplit_selftest()123 int bupsplit_selftest()
124 {
125 uint8_t *buf = malloc(BUP_SELFTEST_SIZE);
126 uint32_t sum1a, sum1b, sum2a, sum2b, sum3a, sum3b;
127 unsigned count;
128
129 srandom(1);
130 for (count = 0; count < BUP_SELFTEST_SIZE; count++)
131 buf[count] = random();
132
133 sum1a = rollsum_sum(buf, 0, BUP_SELFTEST_SIZE);
134 sum1b = rollsum_sum(buf, 1, BUP_SELFTEST_SIZE);
135 sum2a = rollsum_sum(buf, BUP_SELFTEST_SIZE - BUP_WINDOWSIZE*5/2,
136 BUP_SELFTEST_SIZE - BUP_WINDOWSIZE);
137 sum2b = rollsum_sum(buf, 0, BUP_SELFTEST_SIZE - BUP_WINDOWSIZE);
138 sum3a = rollsum_sum(buf, 0, BUP_WINDOWSIZE+3);
139 sum3b = rollsum_sum(buf, 3, BUP_WINDOWSIZE+3);
140
141 fprintf(stderr, "sum1a = 0x%08x\n", sum1a);
142 fprintf(stderr, "sum1b = 0x%08x\n", sum1b);
143 fprintf(stderr, "sum2a = 0x%08x\n", sum2a);
144 fprintf(stderr, "sum2b = 0x%08x\n", sum2b);
145 fprintf(stderr, "sum3a = 0x%08x\n", sum3a);
146 fprintf(stderr, "sum3b = 0x%08x\n", sum3b);
147
148 free(buf);
149 return sum1a!=sum1b || sum2a!=sum2b || sum3a!=sum3b;
150 }
151
152 #endif // !BUP_NO_SELFTEST
153