64-bit fix (reported by Alex Wulms)
[ccan] / ccan / crcsync / crcsync.c
1 #include "crcsync.h"
2 #include <ccan/crc/crc.h>
3 #include <string.h>
4 #include <assert.h>
5
6 void crc_of_blocks(const void *data, size_t len, unsigned int block_size,
7                    unsigned int crcbits, uint32_t crc[])
8 {
9         unsigned int i;
10         const uint8_t *buf = data;
11         uint32_t crcmask = crcbits < 32 ? (1 << crcbits) - 1 : 0xFFFFFFFF;
12
13         for (i = 0; len >= block_size; i++) {
14                 crc[i] = (crc32c(0, buf, block_size) & crcmask);
15                 buf += block_size;
16                 len -= block_size;
17         }
18         if (len)
19                 crc[i] = (crc32c(0, buf, len) & crcmask);
20 }
21
22 struct crc_context {
23         size_t block_size;
24         uint32_t crcmask;
25
26         /* Saved old buffer bytes (block_size bytes). */
27         void *buffer;
28         size_t buffer_start, buffer_end;
29
30         /* Progress so far. */
31         uint32_t running_crc;
32         size_t literal_bytes;
33         size_t total_bytes;
34         int have_match;
35
36         /* Uncrc tab. */
37         uint32_t uncrc_tab[256];
38
39         unsigned int num_crcs;
40         uint32_t crc[];
41 };
42
43 /* Calculate the how the crc changes when we take a give char out of the
44  * crc'd area. */
45 static void init_uncrc_tab(uint32_t uncrc_tab[], unsigned int wsize)
46 {
47         unsigned int i;
48         uint32_t part_crc;
49         uint8_t buffer[wsize];
50
51         /* Calculate crc(buffer+1, wsize-1) once, since it doesn't change. */
52         memset(buffer, 0, wsize);
53         part_crc = crc32c(0, buffer+1, wsize-1);
54
55         for (i = 0; i < 256; i++) {
56                 buffer[0] = i;
57                 uncrc_tab[i] = (crc32c(0, buffer, wsize) ^ part_crc);
58         }
59 }
60
61 struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
62                                     const uint32_t crc[], unsigned num_crcs)
63 {
64         struct crc_context *ctx;
65
66         ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs);
67         if (ctx) {
68                 ctx->block_size = block_size;
69                 /* Technically, 1 << 32 is undefined. */
70                 if (crcbits >= 32)
71                         ctx->crcmask = 0xFFFFFFFF;
72                 else
73                         ctx->crcmask = (1 << crcbits)-1;
74                 ctx->num_crcs = num_crcs;
75                 memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
76                 ctx->buffer_end = 0;
77                 ctx->buffer_start = 0;
78                 ctx->running_crc = 0;
79                 ctx->literal_bytes = 0;
80                 ctx->total_bytes = 0;
81                 ctx->have_match = -1;
82                 init_uncrc_tab(ctx->uncrc_tab, block_size);
83                 ctx->buffer = malloc(block_size);
84                 if (!ctx->buffer) {
85                         free(ctx);
86                         ctx = NULL;
87                 }
88         }
89         return ctx;
90 }
91
92 /* Return -1 or index into matching crc. */
93 static int crc_matches(const struct crc_context *ctx)
94 {
95         unsigned int i;
96
97         if (ctx->literal_bytes < ctx->block_size)
98                 return -1;
99
100         for (i = 0; i < ctx->num_crcs; i++)
101                 if ((ctx->running_crc & ctx->crcmask) == ctx->crc[i])
102                         return i;
103         return -1;
104 }
105
106 static uint32_t crc_add_byte(uint32_t crc, uint8_t newbyte)
107 {
108         return crc32c(crc, &newbyte, 1);
109 }
110
111 static uint32_t crc_remove_byte(uint32_t crc, uint8_t oldbyte,
112                                 const uint32_t uncrc_tab[])
113 {
114         return crc ^ uncrc_tab[oldbyte];
115 }
116
117 static uint32_t crc_roll(uint32_t crc, uint8_t oldbyte, uint8_t newbyte,
118                          const uint32_t uncrc_tab[])
119 {
120         return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
121 }
122
123 static size_t buffer_size(const struct crc_context *ctx)
124 {
125         return ctx->buffer_end - ctx->buffer_start;
126 }
127
128 size_t crc_read_block(struct crc_context *ctx, long *result,
129                       const void *buf, size_t buflen)
130 {
131         size_t consumed = 0, len;
132         int crcmatch = -1;
133         const uint8_t *old, *p = buf;
134
135         /* Simple optimization, if we found a match last time. */
136         if (ctx->have_match >= 0) {
137                 crcmatch = ctx->have_match;
138                 goto have_match;
139         }
140
141         /* old is the trailing edge of the checksum window. */
142         if (buffer_size(ctx) >= ctx->block_size)
143                 old = ctx->buffer + ctx->buffer_start;
144         else
145                 old = NULL;
146
147         while (!old || (crcmatch = crc_matches(ctx)) < 0) {
148                 if (consumed == buflen)
149                         break;
150
151                 /* Update crc. */
152                 if (old) {
153                         ctx->running_crc = crc_roll(ctx->running_crc,
154                                                     *old, *p,
155                                                     ctx->uncrc_tab);
156                         old++;
157                         /* End of stored buffer?  Start on data they gave us. */
158                         if (old == ctx->buffer + ctx->buffer_end)
159                                 old = buf;
160                 } else {
161                         ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
162                         if (p == (uint8_t *)buf + ctx->block_size - 1)
163                                 old = buf;
164                 }
165
166                 ctx->literal_bytes++;
167                 ctx->total_bytes++;
168                 consumed++;
169                 p++;
170         }
171
172         if (crcmatch >= 0) {
173                 /* We have a match! */
174                 if (ctx->literal_bytes > ctx->block_size) {
175                         /* Output literal first. */
176                         *result = ctx->literal_bytes - ctx->block_size;
177                         ctx->literal_bytes = ctx->block_size;
178                         /* Remember for next time! */
179                         ctx->have_match = crcmatch;
180                 } else {
181                 have_match:
182                         *result = -crcmatch-1;
183                         ctx->literal_bytes -= ctx->block_size;
184                         assert(ctx->literal_bytes == 0);
185                         ctx->have_match = -1;
186                         ctx->running_crc = 0;
187                         /* Nothing more in the buffer. */
188                         ctx->buffer_start = ctx->buffer_end = 0;
189                 }
190         } else {
191                 /* Output literal if it's more than 1 block ago. */
192                 if (ctx->literal_bytes > ctx->block_size) {
193                         *result = ctx->literal_bytes - ctx->block_size;
194                         ctx->literal_bytes -= *result;
195                         ctx->buffer_start += *result;
196                 } else
197                         *result = 0;
198
199                 /* Now save any literal bytes we'll need in future. */
200                 len = ctx->literal_bytes - buffer_size(ctx);
201
202                 /* Move down old data if we don't have room.  */
203                 if (ctx->buffer_end + len > ctx->block_size) {
204                         memmove(ctx->buffer, ctx->buffer + ctx->buffer_start,
205                                 buffer_size(ctx));
206                         ctx->buffer_end -= ctx->buffer_start;
207                         ctx->buffer_start = 0;
208                 }
209                 memcpy(ctx->buffer + ctx->buffer_end, buf, len);
210                 ctx->buffer_end += len;
211                 assert(buffer_size(ctx) <= ctx->block_size);
212         }
213         return consumed;
214 }
215
216 /* We could try many techniques to match the final block.  We can
217  * simply try to checksum whatever's left at the end and see if it
218  * matches the final block checksum.  This works for the exact-match
219  * case.
220  *
221  * We can do slightly better than this: if we try to match the checksum
222  * on every block (starting with block_size 1) from where we end to EOF,
223  * we can capture the "data appended" case as well.
224  */
225 static size_t final_block_match(struct crc_context *ctx)
226 {
227         size_t size;
228         uint32_t crc;
229
230         if (ctx->num_crcs == 0)
231                 return 0;
232
233         crc = 0;
234         for (size = 0; size < buffer_size(ctx); size++) {
235                 const uint8_t *p = ctx->buffer;
236                 crc = crc_add_byte(crc, p[ctx->buffer_start+size]);
237                 if ((crc & ctx->crcmask) == ctx->crc[ctx->num_crcs-1])
238                         return size+1;
239         }
240         return 0;
241 }
242
243 long crc_read_flush(struct crc_context *ctx)
244 {
245         long ret;
246         size_t final;
247
248         /* We might have ended right on a matched block. */
249         if (ctx->have_match != -1) {
250                 ctx->literal_bytes -= ctx->block_size;
251                 assert(ctx->literal_bytes == 0);
252                 ret = -ctx->have_match-1;
253                 ctx->have_match = -1;
254                 ctx->running_crc = 0;
255                 /* Nothing more in the buffer. */
256                 ctx->buffer_start = ctx->buffer_end;
257                 return ret;
258         }
259
260         /* Look for truncated final block. */
261         final = final_block_match(ctx);
262         if (!final) {
263                 /* Nope?  Just a literal. */
264                 ret = buffer_size(ctx);
265                 ctx->buffer_start += ret;
266                 ctx->literal_bytes -= ret;
267                 return ret;
268         }
269
270         /* We matched (some of) what's left. */
271         ret = -((int)ctx->num_crcs-1)-1;
272         ctx->buffer_start += final;
273         ctx->literal_bytes -= final;
274         return ret;
275 }
276
277 /**
278  * crc_context_free - free a context returned from crc_context_new.
279  * @ctx: the context returned from crc_context_new, or NULL.
280  */
281 void crc_context_free(struct crc_context *ctx)
282 {
283         free(ctx->buffer);
284         free(ctx);
285 }