1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
3 #include <ccan/crc/crc.h>
8 /* FIXME: That 64-bit CRC takes a while to warm the lower bits. Do
9 * some quantitative tests and replace it? Meanwhile, use upper bits. */
10 static uint64_t mask_of(unsigned int crcbits)
12 return -1ULL << (64 - crcbits);
15 void crc_of_blocks(const void *data, size_t len, unsigned int block_size,
16 unsigned int crcbits, uint64_t crc[])
19 const uint8_t *buf = data;
20 uint64_t crcmask = mask_of(crcbits);
22 for (i = 0; len >= block_size; i++) {
23 crc[i] = (crc64_iso(0, buf, block_size) & crcmask);
28 crc[i] = (crc64_iso(0, buf, len) & crcmask);
35 /* Saved old buffer bytes (block_size bytes). */
37 size_t buffer_start, buffer_end;
39 /* Progress so far. */
45 /* Final block is special (if a different size) */
50 uint64_t uncrc_tab[256];
52 /* This doesn't count the last CRC. */
53 unsigned int num_crcs;
57 /* Calculate the how the crc changes when we take a give char out of the
59 static void init_uncrc_tab(uint64_t uncrc_tab[], unsigned int wsize)
63 uint8_t buffer[wsize];
65 /* Calculate crc(buffer+1, wsize-1) once, since it doesn't change. */
66 memset(buffer, 0, wsize);
67 part_crc = crc64_iso(0, buffer+1, wsize-1);
69 for (i = 0; i < 256; i++) {
71 uncrc_tab[i] = (crc64_iso(0, buffer, wsize) ^ part_crc);
75 struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
76 const uint64_t crc[], unsigned num_crcs,
79 struct crc_context *ctx;
82 assert(block_size > 0);
83 assert(tail_size < block_size);
85 ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs);
87 ctx->block_size = block_size;
88 ctx->tail_size = tail_size;
90 ctx->tail_crc = crc[--num_crcs];
92 ctx->crcmask = mask_of(crcbits);
93 ctx->num_crcs = num_crcs;
94 memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
96 ctx->buffer_start = 0;
98 ctx->literal_bytes = 0;
100 ctx->have_match = -1;
101 init_uncrc_tab(ctx->uncrc_tab, block_size);
102 ctx->buffer = malloc(block_size);
111 /* Return -1 or index into matching crc. */
112 static int crc_matches(const struct crc_context *ctx)
116 if (ctx->literal_bytes < ctx->block_size)
119 for (i = 0; i < ctx->num_crcs; i++)
120 if ((ctx->running_crc & ctx->crcmask) == ctx->crc[i])
125 static bool tail_matches(const struct crc_context *ctx)
127 if (ctx->literal_bytes != ctx->tail_size)
130 return (ctx->running_crc & ctx->crcmask) == ctx->tail_crc;
133 static uint64_t crc_add_byte(uint64_t crc, uint8_t newbyte)
135 return crc64_iso(crc, &newbyte, 1);
138 static uint64_t crc_remove_byte(uint64_t crc, uint8_t oldbyte,
139 const uint64_t uncrc_tab[])
141 return crc ^ uncrc_tab[oldbyte];
144 static uint64_t crc_roll(uint64_t crc, uint8_t oldbyte, uint8_t newbyte,
145 const uint64_t uncrc_tab[])
147 return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
150 static size_t buffer_size(const struct crc_context *ctx)
152 return ctx->buffer_end - ctx->buffer_start;
155 size_t crc_read_block(struct crc_context *ctx, long *result,
156 const void *buf, size_t buflen)
158 size_t consumed = 0, len;
160 const uint8_t *old, *p = buf;
162 /* Simple optimization, if we found a match last time. */
163 if (ctx->have_match >= 0) {
164 crcmatch = ctx->have_match;
168 /* old is the trailing edge of the checksum window. */
169 if (buffer_size(ctx) >= ctx->block_size)
170 old = (uint8_t *)ctx->buffer + ctx->buffer_start;
174 while (ctx->literal_bytes < ctx->block_size
175 || (crcmatch = crc_matches(ctx)) < 0) {
176 if (consumed == buflen)
179 /* Increment these now in case we hit goto: below. */
180 ctx->literal_bytes++;
186 ctx->running_crc = crc_roll(ctx->running_crc,
190 /* End of stored buffer? Start on data they gave us. */
191 if (old == (uint8_t *)ctx->buffer + ctx->buffer_end)
194 ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
195 if (p == (uint8_t *)buf + ctx->block_size - 1)
197 /* We don't roll this csum, we only look for it after
198 * a block match. It's simpler and faster. */
199 if (tail_matches(ctx)) {
200 crcmatch = ctx->num_crcs;
208 /* We have a match! */
209 if (ctx->literal_bytes > ctx->block_size) {
210 /* Output literal first. */
211 *result = ctx->literal_bytes - ctx->block_size;
212 ctx->literal_bytes = ctx->block_size;
213 /* Remember for next time! */
214 ctx->have_match = crcmatch;
217 *result = -crcmatch-1;
218 if (crcmatch == ctx->num_crcs)
219 assert(ctx->literal_bytes == ctx->tail_size);
221 assert(ctx->literal_bytes == ctx->block_size);
222 ctx->literal_bytes = 0;
223 ctx->have_match = -1;
224 ctx->running_crc = 0;
225 /* Nothing more in the buffer. */
226 ctx->buffer_start = ctx->buffer_end = 0;
229 /* Output literal if it's more than 1 block ago. */
230 if (ctx->literal_bytes > ctx->block_size) {
231 *result = ctx->literal_bytes - ctx->block_size;
232 ctx->literal_bytes -= *result;
233 /* Advance buffer. */
234 if (*result >= buffer_size(ctx))
235 ctx->buffer_start = ctx->buffer_end = 0;
237 ctx->buffer_start += *result;
241 /* Now save any literal bytes we'll need in future. */
242 len = ctx->literal_bytes - buffer_size(ctx);
244 /* Move down old data if we don't have room. */
245 if (ctx->buffer_end + len > ctx->block_size) {
247 (uint8_t *)ctx->buffer + ctx->buffer_start,
249 ctx->buffer_end -= ctx->buffer_start;
250 ctx->buffer_start = 0;
253 /* Copy len bytes from tail of buffer. */
254 memcpy((uint8_t *)ctx->buffer + ctx->buffer_end,
255 (const uint8_t *)buf + buflen - len, len);
256 ctx->buffer_end += len;
257 assert(buffer_size(ctx) <= ctx->block_size);
262 long crc_read_flush(struct crc_context *ctx)
266 /* We might have ended right on a matched block. */
267 if (ctx->have_match != -1) {
268 ctx->literal_bytes -= ctx->block_size;
269 assert(ctx->literal_bytes == 0);
270 ret = -ctx->have_match-1;
271 ctx->have_match = -1;
272 ctx->running_crc = 0;
273 /* Nothing more in the buffer. */
274 ctx->buffer_start = ctx->buffer_end;
278 /* The rest is just a literal. */
279 ret = buffer_size(ctx);
280 assert(ctx->literal_bytes == ret);
281 ctx->buffer_start = ctx->buffer_end = 0;
282 ctx->literal_bytes = 0;
287 * crc_context_free - free a context returned from crc_context_new.
288 * @ctx: the context returned from crc_context_new, or NULL.
290 void crc_context_free(struct crc_context *ctx)