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