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