Change arguments to crcsync code.
[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 tail_size;
39         uint32_t tail_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 tail_size)
70 {
71         struct crc_context *ctx;
72
73         assert(num_crcs > 0);
74         assert(block_size > 0);
75         assert(tail_size < block_size);
76
77         ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs);
78         if (ctx) {
79                 ctx->block_size = block_size;
80                 ctx->tail_size = tail_size;
81                 if (tail_size)
82                         ctx->tail_crc = crc[--num_crcs];
83
84                 /* Technically, 1 << 32 is undefined. */
85                 if (crcbits >= 32)
86                         ctx->crcmask = 0xFFFFFFFF;
87                 else
88                         ctx->crcmask = (1 << crcbits)-1;
89                 ctx->num_crcs = num_crcs;
90                 memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
91                 ctx->buffer_end = 0;
92                 ctx->buffer_start = 0;
93                 ctx->running_crc = 0;
94                 ctx->literal_bytes = 0;
95                 ctx->total_bytes = 0;
96                 ctx->have_match = -1;
97                 init_uncrc_tab(ctx->uncrc_tab, block_size);
98                 ctx->buffer = malloc(block_size);
99                 if (!ctx->buffer) {
100                         free(ctx);
101                         ctx = NULL;
102                 }
103         }
104         return ctx;
105 }
106
107 /* Return -1 or index into matching crc. */
108 static int crc_matches(const struct crc_context *ctx)
109 {
110         unsigned int i;
111
112         if (ctx->literal_bytes < ctx->block_size)
113                 return -1;
114
115         for (i = 0; i < ctx->num_crcs; i++)
116                 if ((ctx->running_crc & ctx->crcmask) == ctx->crc[i])
117                         return i;
118         return -1;
119 }
120
121 static bool tail_matches(const struct crc_context *ctx)
122 {
123         if (ctx->literal_bytes != ctx->tail_size)
124                 return false;
125
126         return (ctx->running_crc & ctx->crcmask) == ctx->tail_crc;
127 }
128
129 static uint32_t crc_add_byte(uint32_t crc, uint8_t newbyte)
130 {
131         return crc32c(crc, &newbyte, 1);
132 }
133
134 static uint32_t crc_remove_byte(uint32_t crc, uint8_t oldbyte,
135                                 const uint32_t uncrc_tab[])
136 {
137         return crc ^ uncrc_tab[oldbyte];
138 }
139
140 static uint32_t crc_roll(uint32_t crc, uint8_t oldbyte, uint8_t newbyte,
141                          const uint32_t uncrc_tab[])
142 {
143         return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
144 }
145
146 static size_t buffer_size(const struct crc_context *ctx)
147 {
148         return ctx->buffer_end - ctx->buffer_start;
149 }
150
151 size_t crc_read_block(struct crc_context *ctx, long *result,
152                       const void *buf, size_t buflen)
153 {
154         size_t consumed = 0, len;
155         int crcmatch = -1;
156         const uint8_t *old, *p = buf;
157
158         /* Simple optimization, if we found a match last time. */
159         if (ctx->have_match >= 0) {
160                 crcmatch = ctx->have_match;
161                 goto have_match;
162         }
163
164         /* old is the trailing edge of the checksum window. */
165         if (buffer_size(ctx) >= ctx->block_size)
166                 old = ctx->buffer + ctx->buffer_start;
167         else
168                 old = NULL;
169
170         while (ctx->literal_bytes < ctx->block_size
171                || (crcmatch = crc_matches(ctx)) < 0) {
172                 if (consumed == buflen)
173                         break;
174
175                 /* Increment these now in case we hit goto: below. */
176                 ctx->literal_bytes++;
177                 ctx->total_bytes++;
178                 consumed++;
179
180                 /* Update crc. */
181                 if (old) {
182                         ctx->running_crc = crc_roll(ctx->running_crc,
183                                                     *old, *p,
184                                                     ctx->uncrc_tab);
185                         old++;
186                         /* End of stored buffer?  Start on data they gave us. */
187                         if (old == ctx->buffer + ctx->buffer_end)
188                                 old = buf;
189                 } else {
190                         ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
191                         if (p == (uint8_t *)buf + ctx->block_size - 1)
192                                 old = buf;
193                         /* We don't roll this csum, we only look for it after
194                          * a block match.  It's simpler and faster. */
195                         if (tail_matches(ctx)) {
196                                 crcmatch = ctx->num_crcs;
197                                 goto have_match;
198                         }
199                 }
200                 p++;
201         }
202
203         if (crcmatch >= 0) {
204                 /* We have a match! */
205                 if (ctx->literal_bytes > ctx->block_size) {
206                         /* Output literal first. */
207                         *result = ctx->literal_bytes - ctx->block_size;
208                         ctx->literal_bytes = ctx->block_size;
209                         /* Remember for next time! */
210                         ctx->have_match = crcmatch;
211                 } else {
212                 have_match:
213                         *result = -crcmatch-1;
214                         if (crcmatch == ctx->num_crcs)
215                                 assert(ctx->literal_bytes == ctx->tail_size);
216                         else
217                                 assert(ctx->literal_bytes == ctx->block_size);
218                         ctx->literal_bytes = 0;
219                         ctx->have_match = -1;
220                         ctx->running_crc = 0;
221                         /* Nothing more in the buffer. */
222                         ctx->buffer_start = ctx->buffer_end = 0;
223                 }
224         } else {
225                 /* Output literal if it's more than 1 block ago. */
226                 if (ctx->literal_bytes > ctx->block_size) {
227                         *result = ctx->literal_bytes - ctx->block_size;
228                         ctx->literal_bytes -= *result;
229                         /* Advance buffer. */
230                         if (*result >= buffer_size(ctx))
231                                 ctx->buffer_start = ctx->buffer_end = 0;
232                         else
233                                 ctx->buffer_start += *result;
234                 } else
235                         *result = 0;
236
237                 /* Now save any literal bytes we'll need in future. */
238                 len = ctx->literal_bytes - buffer_size(ctx);
239
240                 /* Move down old data if we don't have room.  */
241                 if (ctx->buffer_end + len > ctx->block_size) {
242                         memmove(ctx->buffer, ctx->buffer + ctx->buffer_start,
243                                 buffer_size(ctx));
244                         ctx->buffer_end -= ctx->buffer_start;
245                         ctx->buffer_start = 0;
246                 }
247
248                 /* Copy len bytes from tail of buffer. */
249                 memcpy(ctx->buffer + ctx->buffer_end, buf + buflen - len, len);
250                 ctx->buffer_end += len;
251                 assert(buffer_size(ctx) <= ctx->block_size);
252         }
253         return consumed;
254 }
255
256 long crc_read_flush(struct crc_context *ctx)
257 {
258         long ret;
259
260         /* We might have ended right on a matched block. */
261         if (ctx->have_match != -1) {
262                 ctx->literal_bytes -= ctx->block_size;
263                 assert(ctx->literal_bytes == 0);
264                 ret = -ctx->have_match-1;
265                 ctx->have_match = -1;
266                 ctx->running_crc = 0;
267                 /* Nothing more in the buffer. */
268                 ctx->buffer_start = ctx->buffer_end;
269                 return ret;
270         }
271
272         /* The rest is just a literal. */
273         ret = buffer_size(ctx);
274         assert(ctx->literal_bytes == ret);
275         ctx->buffer_start = ctx->buffer_end = 0;
276         ctx->literal_bytes = 0;
277         return ret;
278 }
279
280 /**
281  * crc_context_free - free a context returned from crc_context_new.
282  * @ctx: the context returned from crc_context_new, or NULL.
283  */
284 void crc_context_free(struct crc_context *ctx)
285 {
286         free(ctx->buffer);
287         free(ctx);
288 }