Tracing for tdb operations.
[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 /* FIXME: That 64-bit CRC takes a while to warm the lower bits.  Do
8  * some quantitative tests and replace it?  Meanwhile, use upper bits. */
9 static uint64_t mask_of(unsigned int crcbits)
10 {
11         return -1ULL << (64 - crcbits);
12 }
13
14 void crc_of_blocks(const void *data, size_t len, unsigned int block_size,
15                    unsigned int crcbits, uint64_t crc[])
16 {
17         unsigned int i;
18         const uint8_t *buf = data;
19         uint64_t crcmask = mask_of(crcbits);
20
21         for (i = 0; len >= block_size; i++) {
22                 crc[i] = (crc64_iso(0, buf, block_size) & crcmask);
23                 buf += block_size;
24                 len -= block_size;
25         }
26         if (len)
27                 crc[i] = (crc64_iso(0, buf, len) & crcmask);
28 }
29
30 struct crc_context {
31         size_t block_size;
32         uint64_t crcmask;
33
34         /* Saved old buffer bytes (block_size bytes). */
35         void *buffer;
36         size_t buffer_start, buffer_end;
37
38         /* Progress so far. */
39         uint64_t running_crc;
40         size_t literal_bytes;
41         size_t total_bytes;
42         int have_match;
43
44         /* Final block is special (if a different size) */
45         size_t tail_size;
46         uint64_t tail_crc;
47
48         /* Uncrc tab. */
49         uint64_t uncrc_tab[256];
50
51         /* This doesn't count the last CRC. */
52         unsigned int num_crcs;
53         uint64_t crc[];
54 };
55
56 /* Calculate the how the crc changes when we take a give char out of the
57  * crc'd area. */
58 static void init_uncrc_tab(uint64_t uncrc_tab[], unsigned int wsize)
59 {
60         unsigned int i;
61         uint64_t part_crc;
62         uint8_t buffer[wsize];
63
64         /* Calculate crc(buffer+1, wsize-1) once, since it doesn't change. */
65         memset(buffer, 0, wsize);
66         part_crc = crc64_iso(0, buffer+1, wsize-1);
67
68         for (i = 0; i < 256; i++) {
69                 buffer[0] = i;
70                 uncrc_tab[i] = (crc64_iso(0, buffer, wsize) ^ part_crc);
71         }
72 }
73
74 struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
75                                     const uint64_t crc[], unsigned num_crcs,
76                                     size_t tail_size)
77 {
78         struct crc_context *ctx;
79
80         assert(num_crcs > 0);
81         assert(block_size > 0);
82         assert(tail_size < block_size);
83
84         ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs);
85         if (ctx) {
86                 ctx->block_size = block_size;
87                 ctx->tail_size = tail_size;
88                 if (tail_size)
89                         ctx->tail_crc = crc[--num_crcs];
90
91                 ctx->crcmask = mask_of(crcbits);
92                 ctx->num_crcs = num_crcs;
93                 memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
94                 ctx->buffer_end = 0;
95                 ctx->buffer_start = 0;
96                 ctx->running_crc = 0;
97                 ctx->literal_bytes = 0;
98                 ctx->total_bytes = 0;
99                 ctx->have_match = -1;
100                 init_uncrc_tab(ctx->uncrc_tab, block_size);
101                 ctx->buffer = malloc(block_size);
102                 if (!ctx->buffer) {
103                         free(ctx);
104                         ctx = NULL;
105                 }
106         }
107         return ctx;
108 }
109
110 /* Return -1 or index into matching crc. */
111 static int crc_matches(const struct crc_context *ctx)
112 {
113         unsigned int i;
114
115         if (ctx->literal_bytes < ctx->block_size)
116                 return -1;
117
118         for (i = 0; i < ctx->num_crcs; i++)
119                 if ((ctx->running_crc & ctx->crcmask) == ctx->crc[i])
120                         return i;
121         return -1;
122 }
123
124 static bool tail_matches(const struct crc_context *ctx)
125 {
126         if (ctx->literal_bytes != ctx->tail_size)
127                 return false;
128
129         return (ctx->running_crc & ctx->crcmask) == ctx->tail_crc;
130 }
131
132 static uint64_t crc_add_byte(uint64_t crc, uint8_t newbyte)
133 {
134         return crc64_iso(crc, &newbyte, 1);
135 }
136
137 static uint64_t crc_remove_byte(uint64_t crc, uint8_t oldbyte,
138                                 const uint64_t uncrc_tab[])
139 {
140         return crc ^ uncrc_tab[oldbyte];
141 }
142
143 static uint64_t crc_roll(uint64_t crc, uint8_t oldbyte, uint8_t newbyte,
144                          const uint64_t uncrc_tab[])
145 {
146         return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
147 }
148
149 static size_t buffer_size(const struct crc_context *ctx)
150 {
151         return ctx->buffer_end - ctx->buffer_start;
152 }
153
154 size_t crc_read_block(struct crc_context *ctx, long *result,
155                       const void *buf, size_t buflen)
156 {
157         size_t consumed = 0, len;
158         int crcmatch = -1;
159         const uint8_t *old, *p = buf;
160
161         /* Simple optimization, if we found a match last time. */
162         if (ctx->have_match >= 0) {
163                 crcmatch = ctx->have_match;
164                 goto have_match;
165         }
166
167         /* old is the trailing edge of the checksum window. */
168         if (buffer_size(ctx) >= ctx->block_size)
169                 old = ctx->buffer + ctx->buffer_start;
170         else
171                 old = NULL;
172
173         while (ctx->literal_bytes < ctx->block_size
174                || (crcmatch = crc_matches(ctx)) < 0) {
175                 if (consumed == buflen)
176                         break;
177
178                 /* Increment these now in case we hit goto: below. */
179                 ctx->literal_bytes++;
180                 ctx->total_bytes++;
181                 consumed++;
182
183                 /* Update crc. */
184                 if (old) {
185                         ctx->running_crc = crc_roll(ctx->running_crc,
186                                                     *old, *p,
187                                                     ctx->uncrc_tab);
188                         old++;
189                         /* End of stored buffer?  Start on data they gave us. */
190                         if (old == ctx->buffer + ctx->buffer_end)
191                                 old = buf;
192                 } else {
193                         ctx->running_crc = crc_add_byte(ctx->running_crc, *p);
194                         if (p == (uint8_t *)buf + ctx->block_size - 1)
195                                 old = buf;
196                         /* We don't roll this csum, we only look for it after
197                          * a block match.  It's simpler and faster. */
198                         if (tail_matches(ctx)) {
199                                 crcmatch = ctx->num_crcs;
200                                 goto have_match;
201                         }
202                 }
203                 p++;
204         }
205
206         if (crcmatch >= 0) {
207                 /* We have a match! */
208                 if (ctx->literal_bytes > ctx->block_size) {
209                         /* Output literal first. */
210                         *result = ctx->literal_bytes - ctx->block_size;
211                         ctx->literal_bytes = ctx->block_size;
212                         /* Remember for next time! */
213                         ctx->have_match = crcmatch;
214                 } else {
215                 have_match:
216                         *result = -crcmatch-1;
217                         if (crcmatch == ctx->num_crcs)
218                                 assert(ctx->literal_bytes == ctx->tail_size);
219                         else
220                                 assert(ctx->literal_bytes == ctx->block_size);
221                         ctx->literal_bytes = 0;
222                         ctx->have_match = -1;
223                         ctx->running_crc = 0;
224                         /* Nothing more in the buffer. */
225                         ctx->buffer_start = ctx->buffer_end = 0;
226                 }
227         } else {
228                 /* Output literal if it's more than 1 block ago. */
229                 if (ctx->literal_bytes > ctx->block_size) {
230                         *result = ctx->literal_bytes - ctx->block_size;
231                         ctx->literal_bytes -= *result;
232                         /* Advance buffer. */
233                         if (*result >= buffer_size(ctx))
234                                 ctx->buffer_start = ctx->buffer_end = 0;
235                         else
236                                 ctx->buffer_start += *result;
237                 } else
238                         *result = 0;
239
240                 /* Now save any literal bytes we'll need in future. */
241                 len = ctx->literal_bytes - buffer_size(ctx);
242
243                 /* Move down old data if we don't have room.  */
244                 if (ctx->buffer_end + len > ctx->block_size) {
245                         memmove(ctx->buffer, ctx->buffer + ctx->buffer_start,
246                                 buffer_size(ctx));
247                         ctx->buffer_end -= ctx->buffer_start;
248                         ctx->buffer_start = 0;
249                 }
250
251                 /* Copy len bytes from tail of buffer. */
252                 memcpy(ctx->buffer + ctx->buffer_end, buf + buflen - len, len);
253                 ctx->buffer_end += len;
254                 assert(buffer_size(ctx) <= ctx->block_size);
255         }
256         return consumed;
257 }
258
259 long crc_read_flush(struct crc_context *ctx)
260 {
261         long ret;
262
263         /* We might have ended right on a matched block. */
264         if (ctx->have_match != -1) {
265                 ctx->literal_bytes -= ctx->block_size;
266                 assert(ctx->literal_bytes == 0);
267                 ret = -ctx->have_match-1;
268                 ctx->have_match = -1;
269                 ctx->running_crc = 0;
270                 /* Nothing more in the buffer. */
271                 ctx->buffer_start = ctx->buffer_end;
272                 return ret;
273         }
274
275         /* The rest is just a literal. */
276         ret = buffer_size(ctx);
277         assert(ctx->literal_bytes == ret);
278         ctx->buffer_start = ctx->buffer_end = 0;
279         ctx->literal_bytes = 0;
280         return ret;
281 }
282
283 /**
284  * crc_context_free - free a context returned from crc_context_new.
285  * @ctx: the context returned from crc_context_new, or NULL.
286  */
287 void crc_context_free(struct crc_context *ctx)
288 {
289         free(ctx->buffer);
290         free(ctx);
291 }