Convert to 64 bit crcs: change semantics of crcbits field to be *upper* not *lower...
authorRusty Russell <rusty@rustcorp.com.au>
Sun, 7 Jun 2009 03:10:47 +0000 (12:40 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Sun, 7 Jun 2009 03:10:47 +0000 (12:40 +0930)
ccan/crcsync/_info
ccan/crcsync/crcsync.c
ccan/crcsync/crcsync.h
ccan/crcsync/test/run-crash.c
ccan/crcsync/test/run-crc.c
ccan/crcsync/test/run-roll.c
ccan/crcsync/test/run.c

index 52e2ebe2febdc65f8e0831500567edd3cb13d50c..e28e517e5e35276dcefe711b863a980c84fe1f4d 100644 (file)
@@ -76,6 +76,7 @@ int main(int argc, char *argv[])
 
        if (strcmp(argv[1], "depends") == 0) {
                printf("ccan/crc\n");
+               printf("ccan/array_size\n");
                return 0;
        }
 
index b6eb65b007fb891339689ad297f9f03ae0709cfd..7864751902edaf86c0d64fa937ae08b67102487a 100644 (file)
@@ -4,68 +4,75 @@
 #include <assert.h>
 #include <stdbool.h>
 
+/* FIXME: That 64-bit CRC takes a while to warm the lower bits.  Do
+ * some quantitative tests and replace it?  Meanwhile, use upper bits. */
+static uint64_t mask_of(unsigned int crcbits)
+{
+       return -1ULL << (64 - crcbits);
+}
+
 void crc_of_blocks(const void *data, size_t len, unsigned int block_size,
-                  unsigned int crcbits, uint32_t crc[])
+                  unsigned int crcbits, uint64_t crc[])
 {
        unsigned int i;
        const uint8_t *buf = data;
-       uint32_t crcmask = crcbits < 32 ? (1 << crcbits) - 1 : 0xFFFFFFFF;
+       uint64_t crcmask = mask_of(crcbits);
 
        for (i = 0; len >= block_size; i++) {
-               crc[i] = (crc32c(0, buf, block_size) & crcmask);
+               crc[i] = (crc64_iso(0, buf, block_size) & crcmask);
                buf += block_size;
                len -= block_size;
        }
        if (len)
-               crc[i] = (crc32c(0, buf, len) & crcmask);
+               crc[i] = (crc64_iso(0, buf, len) & crcmask);
 }
 
 struct crc_context {
        size_t block_size;
-       uint32_t crcmask;
+       uint64_t crcmask;
 
        /* Saved old buffer bytes (block_size bytes). */
        void *buffer;
        size_t buffer_start, buffer_end;
 
        /* Progress so far. */
-       uint32_t running_crc;
+       uint64_t running_crc;
        size_t literal_bytes;
        size_t total_bytes;
        int have_match;
 
        /* Final block is special (if a different size) */
        size_t tail_size;
-       uint32_t tail_crc;
+       uint64_t tail_crc;
 
        /* Uncrc tab. */
-       uint32_t uncrc_tab[256];
+       uint64_t uncrc_tab[256];
 
        /* This doesn't count the last CRC. */
        unsigned int num_crcs;
-       uint32_t crc[];
+       uint64_t crc[];
 };
 
 /* Calculate the how the crc changes when we take a give char out of the
  * crc'd area. */
-static void init_uncrc_tab(uint32_t uncrc_tab[], unsigned int wsize)
+static void init_uncrc_tab(uint64_t uncrc_tab[], unsigned int wsize)
 {
        unsigned int i;
-       uint32_t part_crc;
+       uint64_t part_crc;
        uint8_t buffer[wsize];
 
        /* Calculate crc(buffer+1, wsize-1) once, since it doesn't change. */
        memset(buffer, 0, wsize);
-       part_crc = crc32c(0, buffer+1, wsize-1);
+       part_crc = crc64_iso(0, buffer+1, wsize-1);
 
        for (i = 0; i < 256; i++) {
                buffer[0] = i;
-               uncrc_tab[i] = (crc32c(0, buffer, wsize) ^ part_crc);
+               uncrc_tab[i] = (crc64_iso(0, buffer, wsize) ^ part_crc);
        }
 }
 
 struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
-                                   const uint32_t crc[], unsigned num_crcs,
+                                   const uint64_t crc[], unsigned num_crcs,
                                    size_t tail_size)
 {
        struct crc_context *ctx;
@@ -81,11 +88,7 @@ struct crc_context *crc_context_new(size_t block_size, unsigned crcbits,
                if (tail_size)
                        ctx->tail_crc = crc[--num_crcs];
 
-               /* Technically, 1 << 32 is undefined. */
-               if (crcbits >= 32)
-                       ctx->crcmask = 0xFFFFFFFF;
-               else
-                       ctx->crcmask = (1 << crcbits)-1;
+               ctx->crcmask = mask_of(crcbits);
                ctx->num_crcs = num_crcs;
                memcpy(ctx->crc, crc, sizeof(crc[0])*num_crcs);
                ctx->buffer_end = 0;
@@ -126,19 +129,19 @@ static bool tail_matches(const struct crc_context *ctx)
        return (ctx->running_crc & ctx->crcmask) == ctx->tail_crc;
 }
 
-static uint32_t crc_add_byte(uint32_t crc, uint8_t newbyte)
+static uint64_t crc_add_byte(uint64_t crc, uint8_t newbyte)
 {
-       return crc32c(crc, &newbyte, 1);
+       return crc64_iso(crc, &newbyte, 1);
 }
 
-static uint32_t crc_remove_byte(uint32_t crc, uint8_t oldbyte,
-                               const uint32_t uncrc_tab[])
+static uint64_t crc_remove_byte(uint64_t crc, uint8_t oldbyte,
+                               const uint64_t uncrc_tab[])
 {
        return crc ^ uncrc_tab[oldbyte];
 }
 
-static uint32_t crc_roll(uint32_t crc, uint8_t oldbyte, uint8_t newbyte,
-                        const uint32_t uncrc_tab[])
+static uint64_t crc_roll(uint64_t crc, uint8_t oldbyte, uint8_t newbyte,
+                        const uint64_t uncrc_tab[])
 {
        return crc_add_byte(crc_remove_byte(crc, oldbyte, uncrc_tab), newbyte);
 }
index f4d6f686f88d9f6ba6173c424cddccfdce54c127..db64b0f662ae809a4a9c388e38c1fba3ede3f7ec 100644 (file)
@@ -8,19 +8,19 @@
  * @data: pointer to the buffer to CRC
  * @len: length of the buffer
  * @blocksize: CRC of each block (final block may be shorter)
- * @crcbits: the number of bits of crc you want (currently 32 maximum)
+ * @crcbits: the number of bits of crc you want (currently 64 maximum)
  * @crc: the crcs (array will have (len + blocksize-1)/blocksize entries).
  *
  * Calculates the CRC of each block, and output the lower @crcbits to
  * @crc array.
  */
 void crc_of_blocks(const void *data, size_t len, unsigned int blocksize,
-                  unsigned int crcbits, uint32_t crc[]);
+                  unsigned int crcbits, uint64_t crc[]);
 
 /**
  * crc_context_new - allocate and initialize state for crc_find_block
  * @blocksize: the size of each block
- * @crcbits: the bits valid in the CRCs (<= 32)
+ * @crcbits: the bits valid in the CRCs (<= 64)
  * @crc: array of block crcs (including final block, if any)
  * @num_crcs: number of block crcs
  * @tail_size: the size of final partial block, if any (< blocksize).
@@ -29,7 +29,7 @@ void crc_of_blocks(const void *data, size_t len, unsigned int blocksize,
  * or NULL.  Makes a copy of @crc.
  */
 struct crc_context *crc_context_new(size_t blocksize, unsigned crcbits,
-                                   const uint32_t crc[], unsigned num_crcs,
+                                   const uint64_t crc[], unsigned num_crcs,
                                    size_t final_size);
 
 /**
index 9987f8dc1d91d34e1d7af3199f532a310bec5651..c2561e5d69134862aca8bd651186d18a9cd5858a 100644 (file)
 
 typedef struct {
        int block_count;
-       unsigned int *crcs;
+       uint64_t *crcs;
 } crc_info_t;
 
 static void crcblocks(crc_info_t *crc_info, char *data, int datalen, int blocksize)
 {
        crc_info->block_count = (datalen+blocksize-1)/blocksize;
-       crc_info->crcs = malloc(sizeof(unsigned int)*(crc_info->block_count + 1));
-       crc_of_blocks(data, datalen, blocksize, 30, crc_info->crcs);
+       crc_info->crcs = malloc(sizeof(uint64_t)*(crc_info->block_count + 1));
+       crc_of_blocks(data, datalen, blocksize, 60, crc_info->crcs);
 }
 
 #define BLOCKSIZE 5
@@ -61,7 +61,7 @@ int main(int argc, char *argv[])
        plan_tests(ARRAY_SIZE(expected) + 2);
        crcblocks(&crc_info1, data1, strlen(data1), BLOCKSIZE);
 
-       crcctx = crc_context_new(BLOCKSIZE, 30, crc_info1.crcs, crc_info1.block_count,
+       crcctx = crc_context_new(BLOCKSIZE, 60, crc_info1.crcs, crc_info1.block_count,
                                 tailsize);
        while ( offset < len2)
        {
index 0325cce045ec46e6af1a3652fad7b8d0d619f955..fbbcd68b5d487a07b3fdfcc61a57498ca8c76008 100644 (file)
@@ -6,29 +6,29 @@ int main(int argc, char *argv[])
 {
        char buffer[1024];
        unsigned int i, j;
-       uint32_t crcs[12] = { 0xFFFFF, 0xdeadf00d };
+       uint64_t crcs[12] = { 0xFFFFF, 0xdeadf00d };
 
        plan_tests(3 + 8192);
 
        /* Simple test (we know currently crc of 0s is 0) */
        memset(buffer, 0, sizeof(buffer));
-       crc_of_blocks(buffer, sizeof(buffer), sizeof(buffer), 32, crcs);
+       crc_of_blocks(buffer, sizeof(buffer), sizeof(buffer), 64, crcs);
        ok1(crcs[0] == 0);
-       crc_of_blocks(buffer, sizeof(buffer), sizeof(buffer)/2, 32, crcs);
+       crc_of_blocks(buffer, sizeof(buffer), sizeof(buffer)/2, 64, crcs);
        ok1(crcs[0] == 0);
        ok1(crcs[1] == 0);
 
-       /* We know they're using crc32c. */
+       /* We know they're using crc64_iso. */
        for (i = 0; i < sizeof(buffer); i++) {
                buffer[i] = i;
                crc_of_blocks(buffer, sizeof(buffer), sizeof(buffer)/7,
-                             32, crcs);
+                             64, crcs);
                for (j = 0; j < sizeof(buffer); j += sizeof(buffer)/7) {
                        unsigned int len = sizeof(buffer)/7;
                        if (j + len > sizeof(buffer))
                                len = sizeof(buffer) - j;
                        
-                       ok1(crc32c(0, buffer + j, len) == crcs[j/(sizeof(buffer)/7)]);
+                       ok1(crc64_iso(0, buffer + j, len) == crcs[j/(sizeof(buffer)/7)]);
                }
        }
 
index 106e9023ea096023a68dfd8a8cd4b21f59443461..a07a450683197a8d6028f88b5832e4cefe2a6294 100644 (file)
@@ -10,7 +10,7 @@
 static void test_roll(unsigned int wsize)
 {
        uint8_t data[wsize * 2];
-       uint32_t uncrc_tab[256];
+       uint64_t uncrc_tab[256];
        unsigned int i;
 
        init_uncrc_tab(uncrc_tab, wsize);
@@ -19,10 +19,10 @@ static void test_roll(unsigned int wsize)
                data[i] = random();
 
        for (i = 1; i < ARRAY_SIZE(data) - wsize; i++) {
-               uint32_t rollcrc, crc;
+               uint64_t rollcrc, crc;
 
-               crc = crc32c(0, data+i, wsize);
-               rollcrc = crc_roll(crc32c(0, data+i-1, wsize),
+               crc = crc64_iso(0, data+i, wsize);
+               rollcrc = crc_roll(crc64_iso(0, data+i-1, wsize),
                                   data[i-1], data[i+wsize-1], uncrc_tab);
 
                ok(crc == rollcrc, "wsize %u, i %u", wsize, i);
index 49f203360ca9781503efa5bbcbd635d3eb1b2b1d..ffc2bc1f5517444fbdf345e246438a11e14ee8dc 100644 (file)
@@ -67,14 +67,14 @@ static void test_sync(const char *buffer1, size_t len1,
        struct crc_context *ctx;
        size_t used, ret, i, curr_literal, tailsize;
        long result;
-       uint32_t crcs[num_blocks(len1, block_size)];
+       uint64_t crcs[num_blocks(len1, block_size)];
 
-       crc_of_blocks(buffer1, len1, block_size, 32, crcs);
+       crc_of_blocks(buffer1, len1, block_size, 64, crcs);
 
        tailsize = len1 % block_size;
 
        /* Normal method. */
-       ctx = crc_context_new(block_size, 32, crcs, ARRAY_SIZE(crcs),
+       ctx = crc_context_new(block_size, 64, crcs, ARRAY_SIZE(crcs),
                              tailsize);
 
        curr_literal = 0;
@@ -93,7 +93,7 @@ static void test_sync(const char *buffer1, size_t len1,
        crc_context_free(ctx);
 
        /* Byte-at-a-time method. */
-       ctx = crc_context_new(block_size, 32, crcs, ARRAY_SIZE(crcs),
+       ctx = crc_context_new(block_size, 64, crcs, ARRAY_SIZE(crcs),
                              tailsize);
 
        curr_literal = 0;
@@ -121,7 +121,7 @@ int main(int argc, char *argv[])
 {
        char *buffer1, *buffer2;
        unsigned int i;
-       uint32_t crcs1[NUM_BLOCKS], crcs2[NUM_BLOCKS];
+       uint64_t crcs1[NUM_BLOCKS], crcs2[NUM_BLOCKS];
 
        plan_tests(664);
 
@@ -130,9 +130,9 @@ int main(int argc, char *argv[])
 
        /* Truncated end block test. */
        crcs1[ARRAY_SIZE(crcs1)-1] = 0xdeadbeef;
-       crc_of_blocks(buffer1, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 32, crcs1);
+       crc_of_blocks(buffer1, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs1);
        ok1(crcs1[ARRAY_SIZE(crcs1)-1] == 0xdeadbeef);
-       crc_of_blocks(buffer2, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 32, crcs2);
+       crc_of_blocks(buffer2, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs2);
        ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*(ARRAY_SIZE(crcs1)-1)) == 0);
 
        /* Fill with non-zero pattern, retest. */
@@ -140,16 +140,16 @@ int main(int argc, char *argv[])
                buffer1[i] = buffer2[i] = i + i/BLOCK_SIZE;
 
        crcs1[ARRAY_SIZE(crcs1)-1] = 0xdeadbeef;
-       crc_of_blocks(buffer1, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 32, crcs1);
+       crc_of_blocks(buffer1, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs1);
        ok1(crcs1[ARRAY_SIZE(crcs1)-1] == 0xdeadbeef);
-       crc_of_blocks(buffer2, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 32, crcs2);
+       crc_of_blocks(buffer2, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs2);
        ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*(ARRAY_SIZE(crcs1)-1)) == 0);
 
        /* Check that it correctly masks bits. */
-       crc_of_blocks(buffer1, BUFFER_SIZE, BLOCK_SIZE, 32, crcs1);
+       crc_of_blocks(buffer1, BUFFER_SIZE, BLOCK_SIZE, 64, crcs1);
        crc_of_blocks(buffer2, BUFFER_SIZE, BLOCK_SIZE, 8, crcs2);
        for (i = 0; i < NUM_BLOCKS; i++)
-               ok1(crcs2[i] == (crcs1[i] & 0xFF));
+               ok1(crcs2[i] == (crcs1[i] & 0xFF00000000000000ULL));
 
        /* Now test the "exact match" "round blocks" case. */
        {