From: Rusty Russell Date: Sun, 7 Jun 2009 03:10:47 +0000 (+0930) Subject: Convert to 64 bit crcs: change semantics of crcbits field to be *upper* not *lower... X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=8827948b1953c759042f174997c3d28d13988c9c Convert to 64 bit crcs: change semantics of crcbits field to be *upper* not *lower* bits. --- diff --git a/ccan/crcsync/_info b/ccan/crcsync/_info index 52e2ebe2..e28e517e 100644 --- a/ccan/crcsync/_info +++ b/ccan/crcsync/_info @@ -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; } diff --git a/ccan/crcsync/crcsync.c b/ccan/crcsync/crcsync.c index b6eb65b0..78647519 100644 --- a/ccan/crcsync/crcsync.c +++ b/ccan/crcsync/crcsync.c @@ -4,68 +4,75 @@ #include #include +/* 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); } diff --git a/ccan/crcsync/crcsync.h b/ccan/crcsync/crcsync.h index f4d6f686..db64b0f6 100644 --- a/ccan/crcsync/crcsync.h +++ b/ccan/crcsync/crcsync.h @@ -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); /** diff --git a/ccan/crcsync/test/run-crash.c b/ccan/crcsync/test/run-crash.c index 9987f8dc..c2561e5d 100644 --- a/ccan/crcsync/test/run-crash.c +++ b/ccan/crcsync/test/run-crash.c @@ -11,14 +11,14 @@ 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) { diff --git a/ccan/crcsync/test/run-crc.c b/ccan/crcsync/test/run-crc.c index 0325cce0..fbbcd68b 100644 --- a/ccan/crcsync/test/run-crc.c +++ b/ccan/crcsync/test/run-crc.c @@ -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)]); } } diff --git a/ccan/crcsync/test/run-roll.c b/ccan/crcsync/test/run-roll.c index 106e9023..a07a4506 100644 --- a/ccan/crcsync/test/run-roll.c +++ b/ccan/crcsync/test/run-roll.c @@ -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); diff --git a/ccan/crcsync/test/run.c b/ccan/crcsync/test/run.c index 49f20336..ffc2bc1f 100644 --- a/ccan/crcsync/test/run.c +++ b/ccan/crcsync/test/run.c @@ -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. */ {