2 #include <ccan/crc/crc.h>
7 void crc_of_blocks(const void *data, size_t len, unsigned int block_size,
8 unsigned int crcbits, uint32_t crc[])
11 const uint8_t *buf = data;
12 uint32_t crcmask = crcbits < 32 ? (1 << crcbits) - 1 : 0xFFFFFFFF;
14 for (i = 0; len >= block_size; i++) {
15 crc[i] = (crc32c(0, buf, block_size) & crcmask);
20 crc[i] = (crc32c(0, buf, len) & crcmask);
27 /* Saved old buffer bytes (block_size bytes). */
29 size_t buffer_start, buffer_end;
31 /* Progress so far. */
37 /* Final block is special (if a different size) */
42 uint32_t uncrc_tab[256];
44 /* This doesn't count the last CRC. */
45 unsigned int num_crcs;
49 /* Calculate the how the crc changes when we take a give char out of the
51 static void init_uncrc_tab(uint32_t uncrc_tab[], unsigned int wsize)
55 uint8_t buffer[wsize];
57 /* Calculate crc(buffer+1, wsize-1) once, since it doesn't change. */
58 memset(buffer, 0, wsize);
59 part_crc = crc32c(0, buffer+1, wsize-1);
61 for (i = 0; i < 256; i++) {
63 uncrc_tab[i] = (crc32c(0, buffer, wsize) ^ part_crc);
67 struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
68 const uint32_t crc[], unsigned num_crcs,
71 struct crc_context *ctx;
74 assert(block_size > 0);
75 assert(final_size > 0);
76 assert(final_size <= block_size);
78 ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs);
80 ctx->block_size = block_size;
81 if (final_size != block_size) {
82 ctx->final_size = final_size;
83 ctx->final_crc = crc[--num_crcs];
85 /* If this is 0, we never compare against it. */
89 /* Technically, 1 << 32 is undefined. */
91 ctx->crcmask = 0xFFFFFFFF;
93 ctx->crcmask = (1 << crcbits)-1;
94 ctx->num_crcs = num_crcs;
95 memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
97 ctx->buffer_start = 0;
99 ctx->literal_bytes = 0;
100 ctx->total_bytes = 0;
101 ctx->have_match = -1;
102 init_uncrc_tab(ctx->uncrc_tab, block_size);
103 ctx->buffer = malloc(block_size);
112 /* Return -1 or index into matching crc. */
113 static int crc_matches(const struct crc_context *ctx)
117 if (ctx->literal_bytes < ctx->block_size)
120 for (i = 0; i < ctx->num_crcs; i++)
121 if ((ctx->running_crc & ctx->crcmask) == ctx->crc[i])
126 static bool final_matches(const struct crc_context *ctx)
128 if (ctx->literal_bytes != ctx->final_size)
131 return (ctx->running_crc & ctx->crcmask) == ctx->final_crc;
134 static uint32_t crc_add_byte(uint32_t crc, uint8_t newbyte)
136 return crc32c(crc, &newbyte, 1);
139 static uint32_t crc_remove_byte(uint32_t crc, uint8_t oldbyte,
140 const uint32_t uncrc_tab[])
142 return crc ^ uncrc_tab[oldbyte];
145 static uint32_t crc_roll(uint32_t crc, uint8_t oldbyte, uint8_t newbyte,
146 const uint32_t uncrc_tab[])
148 return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
151 static size_t buffer_size(const struct crc_context *ctx)
153 return ctx->buffer_end - ctx->buffer_start;
156 size_t crc_read_block(struct crc_context *ctx, long *result,
157 const void *buf, size_t buflen)
159 size_t consumed = 0, len;
161 const uint8_t *old, *p = buf;
163 /* Simple optimization, if we found a match last time. */
164 if (ctx->have_match >= 0) {
165 crcmatch = ctx->have_match;
169 /* old is the trailing edge of the checksum window. */
170 if (buffer_size(ctx) >= ctx->block_size)
171 old = ctx->buffer + ctx->buffer_start;
175 while (ctx->literal_bytes < ctx->block_size
176 || (crcmatch = crc_matches(ctx)) < 0) {
177 if (consumed == buflen)
180 /* Increment these now in case we hit goto: below. */
181 ctx->literal_bytes++;
187 ctx->running_crc = crc_roll(ctx->running_crc,
191 /* End of stored buffer? Start on data they gave us. */
192 if (old == ctx->buffer + ctx->buffer_end)
195 ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
196 if (p == (uint8_t *)buf + ctx->block_size - 1)
198 /* We don't roll this csum, we only look for it after
199 * a block match. It's simpler and faster. */
200 if (final_matches(ctx)) {
201 crcmatch = ctx->num_crcs;
209 /* We have a match! */
210 if (ctx->literal_bytes > ctx->block_size) {
211 /* Output literal first. */
212 *result = ctx->literal_bytes - ctx->block_size;
213 ctx->literal_bytes = ctx->block_size;
214 /* Remember for next time! */
215 ctx->have_match = crcmatch;
218 *result = -crcmatch-1;
219 if (crcmatch == ctx->num_crcs)
220 assert(ctx->literal_bytes == ctx->final_size);
222 assert(ctx->literal_bytes == ctx->block_size);
223 ctx->literal_bytes = 0;
224 ctx->have_match = -1;
225 ctx->running_crc = 0;
226 /* Nothing more in the buffer. */
227 ctx->buffer_start = ctx->buffer_end = 0;
230 /* Output literal if it's more than 1 block ago. */
231 if (ctx->literal_bytes > ctx->block_size) {
232 *result = ctx->literal_bytes - ctx->block_size;
233 ctx->literal_bytes -= *result;
234 /* Advance buffer. */
235 if (*result >= buffer_size(ctx))
236 ctx->buffer_start = ctx->buffer_end = 0;
238 ctx->buffer_start += *result;
242 /* Now save any literal bytes we'll need in future. */
243 len = ctx->literal_bytes - buffer_size(ctx);
245 /* Move down old data if we don't have room. */
246 if (ctx->buffer_end + len > ctx->block_size) {
247 memmove(ctx->buffer, 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(ctx->buffer + ctx->buffer_end, buf + buflen - len, len);
255 ctx->buffer_end += len;
256 assert(buffer_size(ctx) <= ctx->block_size);
261 long crc_read_flush(struct crc_context *ctx)
265 /* We might have ended right on a matched block. */
266 if (ctx->have_match != -1) {
267 ctx->literal_bytes -= ctx->block_size;
268 assert(ctx->literal_bytes == 0);
269 ret = -ctx->have_match-1;
270 ctx->have_match = -1;
271 ctx->running_crc = 0;
272 /* Nothing more in the buffer. */
273 ctx->buffer_start = ctx->buffer_end;
277 /* The rest is just a literal. */
278 ret = buffer_size(ctx);
279 assert(ctx->literal_bytes == ret);
280 ctx->buffer_start = ctx->buffer_end = 0;
281 ctx->literal_bytes = 0;
286 * crc_context_free - free a context returned from crc_context_new.
287 * @ctx: the context returned from crc_context_new, or NULL.
289 void crc_context_free(struct crc_context *ctx)