cb768806f6e03e829293f624ea06db540fe02e32
[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         if (buffer_size(ctx) >= ctx->block_size)
142                 old = ctx->buffer + ctx->buffer_start;
143         else
144                 old = NULL;
145
146         while (!old || (crcmatch = crc_matches(ctx)) < 0) {
147                 if (consumed == buflen)
148                         break;
149
150                 /* Update crc. */
151                 if (old) {
152                         ctx->running_crc = crc_roll(ctx->running_crc,
153                                                     *old, *p,
154                                                     ctx->uncrc_tab);
155                         old++;
156                         if (old == ctx->buffer + ctx->buffer_end)
157                                 old = buf;
158                 } else {
159                         ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
160                         if (p == (uint8_t *)buf + ctx->block_size - 1)
161                                 old = buf;
162                 }
163
164                 ctx->literal_bytes++;
165                 ctx->total_bytes++;
166                 consumed++;
167                 p++;
168         }
169
170         /* Make sure we have a copy of the last block_size bytes.
171          * First, copy down the old data.  */
172         if (buffer_size(ctx)) {
173                 memmove(ctx->buffer, ctx->buffer + ctx->buffer_start,
174                         buffer_size(ctx));
175                 ctx->buffer_end -= ctx->buffer_start;
176                 ctx->buffer_start = 0;
177         }
178
179         if (crcmatch >= 0) {
180                 /* We have a match! */
181                 if (ctx->literal_bytes > ctx->block_size) {
182                         /* Output literal first. */
183                         *result = ctx->literal_bytes - ctx->block_size;
184                         ctx->literal_bytes = ctx->block_size;
185                         /* Remember for next time! */
186                         ctx->have_match = crcmatch;
187                 } else {
188                 have_match:
189                         *result = -crcmatch-1;
190                         ctx->literal_bytes -= ctx->block_size;
191                         assert(ctx->literal_bytes == 0);
192                         ctx->have_match = -1;
193                         ctx->running_crc = 0;
194                 }
195         } else {
196                 /* Output literal if it's more than 1 block ago. */
197                 if (ctx->literal_bytes > ctx->block_size) {
198                         *result = ctx->literal_bytes - ctx->block_size;
199                         ctx->literal_bytes = ctx->block_size;
200                 } else
201                         *result = 0;
202
203                 /* Now save any literal bytes we'll need in future. */
204                 len = ctx->literal_bytes - buffer_size(ctx);
205                 memcpy(ctx->buffer + ctx->buffer_end, buf, len);
206                 ctx->buffer_end += len;
207                 assert(buffer_size(ctx) <= ctx->block_size);
208         }
209         return consumed;
210 }
211
212 /* We could try many techniques to match the final block.  We can
213  * simply try to checksum whatever's left at the end and see if it
214  * matches the final block checksum.  This works for the exact-match
215  * case.
216  *
217  * We can do slightly better than this: if we try to match the checksum
218  * on every block (starting with block_size 1) from where we end to EOF,
219  * we can capture the "data appended" case as well.
220  */
221 static size_t final_block_match(struct crc_context *ctx)
222 {
223         size_t size;
224         uint32_t crc;
225
226         if (ctx->num_crcs == 0)
227                 return 0;
228
229         crc = 0;
230         for (size = 0; size < buffer_size(ctx); size++) {
231                 const uint8_t *p = ctx->buffer;
232                 crc = crc_add_byte(crc, p[ctx->buffer_start+size]);
233                 if ((crc & ctx->crcmask) == ctx->crc[ctx->num_crcs-1])
234                         return size+1;
235         }
236         return 0;
237 }
238
239 long crc_read_flush(struct crc_context *ctx)
240 {
241         long ret;
242
243         /* In case we ended on a whole block match. */
244         if (ctx->have_match == -1) {
245                 size_t final;
246
247                 final = final_block_match(ctx);
248                 if (!final) {
249                         /* This is how many bytes we're about to consume. */
250                         ret = buffer_size(ctx);
251                         ctx->buffer_start += ret;
252                         ctx->literal_bytes -= ret;
253
254                         return ret;
255                 }
256                 ctx->buffer_start += final;
257                 ctx->literal_bytes -= final;
258                 ctx->have_match = ctx->num_crcs-1;
259         }
260
261         /* It might be a partial block match, so no assert */
262         ctx->literal_bytes = 0;
263         ret = -ctx->have_match-1;
264         ctx->have_match = -1;
265         return ret;
266 }
267
268 /**
269  * crc_context_free - free a context returned from crc_context_new.
270  * @ctx: the context returned from crc_context_new, or NULL.
271  */
272 void crc_context_free(struct crc_context *ctx)
273 {
274         free(ctx->buffer);
275         free(ctx);
276 }