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