crcsync change: better detection of final block.
[ccan] / ccan / crcsync / crcsync.c
1 #include "crcsync.h"
2 #include <ccan/crc/crc.h>
3 #include <string.h>
4 #include <assert.h>
5 #include <stdbool.h>
6
7 void crc_of_blocks(const void *data, size_t len, unsigned int block_size,
8                    unsigned int crcbits, uint32_t crc[])
9 {
10         unsigned int i;
11         const uint8_t *buf = data;
12         uint32_t crcmask = crcbits < 32 ? (1 << crcbits) - 1 : 0xFFFFFFFF;
13
14         for (i = 0; len >= block_size; i++) {
15                 crc[i] = (crc32c(0, buf, block_size) & crcmask);
16                 buf += block_size;
17                 len -= block_size;
18         }
19         if (len)
20                 crc[i] = (crc32c(0, buf, len) & crcmask);
21 }
22
23 struct crc_context {
24         size_t block_size;
25         uint32_t crcmask;
26
27         /* Saved old buffer bytes (block_size bytes). */
28         void *buffer;
29         size_t buffer_start, buffer_end;
30
31         /* Progress so far. */
32         uint32_t running_crc;
33         size_t literal_bytes;
34         size_t total_bytes;
35         int have_match;
36
37         /* Final block is special (if a different size) */
38         size_t final_size;
39         uint32_t final_crc;
40
41         /* Uncrc tab. */
42         uint32_t uncrc_tab[256];
43
44         /* This doesn't count the last CRC. */
45         unsigned int num_crcs;
46         uint32_t crc[];
47 };
48
49 /* Calculate the how the crc changes when we take a give char out of the
50  * crc'd area. */
51 static void init_uncrc_tab(uint32_t uncrc_tab[], unsigned int wsize)
52 {
53         unsigned int i;
54         uint32_t part_crc;
55         uint8_t buffer[wsize];
56
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);
60
61         for (i = 0; i < 256; i++) {
62                 buffer[0] = i;
63                 uncrc_tab[i] = (crc32c(0, buffer, wsize) ^ part_crc);
64         }
65 }
66
67 struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
68                                     const uint32_t crc[], unsigned num_crcs,
69                                     size_t final_size)
70 {
71         struct crc_context *ctx;
72
73         assert(num_crcs > 0);
74         assert(block_size > 0);
75         assert(final_size > 0);
76         assert(final_size <= block_size);
77
78         ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs);
79         if (ctx) {
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];
84                 } else {
85                         /* If this is 0, we never compare against it. */
86                         ctx->final_size = 0;
87                 }
88
89                 /* Technically, 1 << 32 is undefined. */
90                 if (crcbits >= 32)
91                         ctx->crcmask = 0xFFFFFFFF;
92                 else
93                         ctx->crcmask = (1 << crcbits)-1;
94                 ctx->num_crcs = num_crcs;
95                 memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
96                 ctx->buffer_end = 0;
97                 ctx->buffer_start = 0;
98                 ctx->running_crc = 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);
104                 if (!ctx->buffer) {
105                         free(ctx);
106                         ctx = NULL;
107                 }
108         }
109         return ctx;
110 }
111
112 /* Return -1 or index into matching crc. */
113 static int crc_matches(const struct crc_context *ctx)
114 {
115         unsigned int i;
116
117         if (ctx->literal_bytes < ctx->block_size)
118                 return -1;
119
120         for (i = 0; i < ctx->num_crcs; i++)
121                 if ((ctx->running_crc & ctx->crcmask) == ctx->crc[i])
122                         return i;
123         return -1;
124 }
125
126 static bool final_matches(const struct crc_context *ctx)
127 {
128         if (ctx->literal_bytes != ctx->final_size)
129                 return false;
130
131         return (ctx->running_crc & ctx->crcmask) == ctx->final_crc;
132 }
133
134 static uint32_t crc_add_byte(uint32_t crc, uint8_t newbyte)
135 {
136         return crc32c(crc, &newbyte, 1);
137 }
138
139 static uint32_t crc_remove_byte(uint32_t crc, uint8_t oldbyte,
140                                 const uint32_t uncrc_tab[])
141 {
142         return crc ^ uncrc_tab[oldbyte];
143 }
144
145 static uint32_t crc_roll(uint32_t crc, uint8_t oldbyte, uint8_t newbyte,
146                          const uint32_t uncrc_tab[])
147 {
148         return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
149 }
150
151 static size_t buffer_size(const struct crc_context *ctx)
152 {
153         return ctx->buffer_end - ctx->buffer_start;
154 }
155
156 size_t crc_read_block(struct crc_context *ctx, long *result,
157                       const void *buf, size_t buflen)
158 {
159         size_t consumed = 0, len;
160         int crcmatch = -1;
161         const uint8_t *old, *p = buf;
162
163         /* Simple optimization, if we found a match last time. */
164         if (ctx->have_match >= 0) {
165                 crcmatch = ctx->have_match;
166                 goto have_match;
167         }
168
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;
172         else
173                 old = NULL;
174
175         while (ctx->literal_bytes < ctx->block_size
176                || (crcmatch = crc_matches(ctx)) < 0) {
177                 if (consumed == buflen)
178                         break;
179
180                 /* Increment these now in case we hit goto: below. */
181                 ctx->literal_bytes++;
182                 ctx->total_bytes++;
183                 consumed++;
184
185                 /* Update crc. */
186                 if (old) {
187                         ctx->running_crc = crc_roll(ctx->running_crc,
188                                                     *old, *p,
189                                                     ctx->uncrc_tab);
190                         old++;
191                         /* End of stored buffer?  Start on data they gave us. */
192                         if (old == ctx->buffer + ctx->buffer_end)
193                                 old = buf;
194                 } else {
195                         ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
196                         if (p == (uint8_t *)buf + ctx->block_size - 1)
197                                 old = buf;
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;
202                                 goto have_match;
203                         }
204                 }
205                 p++;
206         }
207
208         if (crcmatch >= 0) {
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;
216                 } else {
217                 have_match:
218                         *result = -crcmatch-1;
219                         if (crcmatch == ctx->num_crcs)
220                                 assert(ctx->literal_bytes == ctx->final_size);
221                         else
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;
228                 }
229         } else {
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;
237                         else
238                                 ctx->buffer_start += *result;
239                 } else
240                         *result = 0;
241
242                 /* Now save any literal bytes we'll need in future. */
243                 len = ctx->literal_bytes - buffer_size(ctx);
244
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,
248                                 buffer_size(ctx));
249                         ctx->buffer_end -= ctx->buffer_start;
250                         ctx->buffer_start = 0;
251                 }
252
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);
257         }
258         return consumed;
259 }
260
261 long crc_read_flush(struct crc_context *ctx)
262 {
263         long ret;
264
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;
274                 return ret;
275         }
276
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;
282         return ret;
283 }
284
285 /**
286  * crc_context_free - free a context returned from crc_context_new.
287  * @ctx: the context returned from crc_context_new, or NULL.
288  */
289 void crc_context_free(struct crc_context *ctx)
290 {
291         free(ctx->buffer);
292         free(ctx);
293 }