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 }