if (strcmp(argv[1], "depends") == 0) {
printf("ccan/crc\n");
+ printf("ccan/array_size\n");
return 0;
}
#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;
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;
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);
}
* @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).
* 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);
/**
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
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)
{
{
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)]);
}
}
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);
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);
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;
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;
{
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);
/* 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. */
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. */
{
projects / ccan / commitdiff