git.ozlabs.org Git - ccan/blob - 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 }