2 #include <ccan/crc/crc.h>
6 void crc_of_blocks(const void *data, size_t len, unsigned int block_size,
7 unsigned int crcbits, uint32_t crc[])
10 const uint8_t *buf = data;
11 uint32_t crcmask = crcbits < 32 ? (1 << crcbits) - 1 : 0xFFFFFFFF;
13 for (i = 0; len >= block_size; i++) {
14 crc[i] = (crc32c(0, buf, block_size) & crcmask);
19 crc[i] = (crc32c(0, buf, len) & crcmask);
26 /* Saved old buffer bytes (block_size bytes). */
28 size_t buffer_start, buffer_end;
30 /* Progress so far. */
37 uint32_t uncrc_tab[256];
39 unsigned int num_crcs;
43 /* Calculate the how the crc changes when we take a give char out of the
45 static void init_uncrc_tab(uint32_t uncrc_tab[], unsigned int wsize)
49 uint8_t buffer[wsize];
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);
55 for (i = 0; i < 256; i++) {
57 uncrc_tab[i] = (crc32c(0, buffer, wsize) ^ part_crc);
61 struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
62 const uint32_t crc[], unsigned num_crcs)
64 struct crc_context *ctx;
66 ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs);
68 ctx->block_size = block_size;
69 /* Technically, 1 << 32 is undefined. */
71 ctx->crcmask = 0xFFFFFFFF;
73 ctx->crcmask = (1 << crcbits)-1;
74 ctx->num_crcs = num_crcs;
75 memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
77 ctx->buffer_start = 0;
79 ctx->literal_bytes = 0;
82 init_uncrc_tab(ctx->uncrc_tab, block_size);
83 ctx->buffer = malloc(block_size);
92 /* Return -1 or index into matching crc. */
93 static int crc_matches(const struct crc_context *ctx)
97 if (ctx->literal_bytes < ctx->block_size)
100 for (i = 0; i < ctx->num_crcs; i++)
101 if ((ctx->running_crc & ctx->crcmask) == ctx->crc[i])
106 static uint32_t crc_add_byte(uint32_t crc, uint8_t newbyte)
108 return crc32c(crc, &newbyte, 1);
111 static uint32_t crc_remove_byte(uint32_t crc, uint8_t oldbyte,
112 const uint32_t uncrc_tab[])
114 return crc ^ uncrc_tab[oldbyte];
117 static uint32_t crc_roll(uint32_t crc, uint8_t oldbyte, uint8_t newbyte,
118 const uint32_t uncrc_tab[])
120 return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
123 static size_t buffer_size(const struct crc_context *ctx)
125 return ctx->buffer_end - ctx->buffer_start;
128 size_t crc_read_block(struct crc_context *ctx, long *result,
129 const void *buf, size_t buflen)
131 size_t consumed = 0, len;
133 const uint8_t *old, *p = buf;
135 /* Simple optimization, if we found a match last time. */
136 if (ctx->have_match >= 0) {
137 crcmatch = ctx->have_match;
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;
147 while (!old || (crcmatch = crc_matches(ctx)) < 0) {
148 if (consumed == buflen)
153 ctx->running_crc = crc_roll(ctx->running_crc,
157 /* End of stored buffer? Start on data they gave us. */
158 if (old == ctx->buffer + ctx->buffer_end)
161 ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
162 if (p == (uint8_t *)buf + ctx->block_size - 1)
166 ctx->literal_bytes++;
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;
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;
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;
199 /* Now save any literal bytes we'll need in future. */
200 len = ctx->literal_bytes - buffer_size(ctx);
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,
206 ctx->buffer_end -= ctx->buffer_start;
207 ctx->buffer_start = 0;
209 memcpy(ctx->buffer + ctx->buffer_end, buf, len);
210 ctx->buffer_end += len;
211 assert(buffer_size(ctx) <= ctx->block_size);
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
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.
225 static size_t final_block_match(struct crc_context *ctx)
230 if (ctx->num_crcs == 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])
243 long crc_read_flush(struct crc_context *ctx)
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;
260 /* Look for truncated final block. */
261 final = final_block_match(ctx);
263 /* Nope? Just a literal. */
264 ret = buffer_size(ctx);
265 ctx->buffer_start += ret;
266 ctx->literal_bytes -= ret;
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;
278 * crc_context_free - free a context returned from crc_context_new.
279 * @ctx: the context returned from crc_context_new, or NULL.
281 void crc_context_free(struct crc_context *ctx)