From: Rusty Russell Date: Sat, 4 Apr 2009 11:35:46 +0000 (+1030) Subject: crcsync change: better detection of final block. X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=c934a7a21d9ea8aa421d62a65a93f46c95adb535 crcsync change: better detection of final block. --- diff --git a/ccan/crcsync/crcsync.c b/ccan/crcsync/crcsync.c index 2301bc10..459010a7 100644 --- a/ccan/crcsync/crcsync.c +++ b/ccan/crcsync/crcsync.c @@ -2,6 +2,7 @@ #include #include #include +#include void crc_of_blocks(const void *data, size_t len, unsigned int block_size, unsigned int crcbits, uint32_t crc[]) @@ -33,9 +34,14 @@ struct crc_context { size_t total_bytes; int have_match; + /* Final block is special (if a different size) */ + size_t final_size; + uint32_t final_crc; + /* Uncrc tab. */ uint32_t uncrc_tab[256]; + /* This doesn't count the last CRC. */ unsigned int num_crcs; uint32_t crc[]; }; @@ -59,13 +65,27 @@ static void init_uncrc_tab(uint32_t uncrc_tab[], unsigned int wsize) } struct crc_context *crc_context_new(size_t block_size, unsigned crcbits, - const uint32_t crc[], unsigned num_crcs) + const uint32_t crc[], unsigned num_crcs, + size_t final_size) { struct crc_context *ctx; + assert(num_crcs > 0); + assert(block_size > 0); + assert(final_size > 0); + assert(final_size <= block_size); + ctx = malloc(sizeof(*ctx) + sizeof(crc[0])*num_crcs); if (ctx) { ctx->block_size = block_size; + if (final_size != block_size) { + ctx->final_size = final_size; + ctx->final_crc = crc[--num_crcs]; + } else { + /* If this is 0, we never compare against it. */ + ctx->final_size = 0; + } + /* Technically, 1 << 32 is undefined. */ if (crcbits >= 32) ctx->crcmask = 0xFFFFFFFF; @@ -103,6 +123,14 @@ static int crc_matches(const struct crc_context *ctx) return -1; } +static bool final_matches(const struct crc_context *ctx) +{ + if (ctx->literal_bytes != ctx->final_size) + return false; + + return (ctx->running_crc & ctx->crcmask) == ctx->final_crc; +} + static uint32_t crc_add_byte(uint32_t crc, uint8_t newbyte) { return crc32c(crc, &newbyte, 1); @@ -144,10 +172,16 @@ size_t crc_read_block(struct crc_context *ctx, long *result, else old = NULL; - while (!old || (crcmatch = crc_matches(ctx)) < 0) { + while (ctx->literal_bytes < ctx->block_size + || (crcmatch = crc_matches(ctx)) < 0) { if (consumed == buflen) break; + /* Increment these now in case we hit goto: below. */ + ctx->literal_bytes++; + ctx->total_bytes++; + consumed++; + /* Update crc. */ if (old) { ctx->running_crc = crc_roll(ctx->running_crc, @@ -161,11 +195,13 @@ size_t crc_read_block(struct crc_context *ctx, long *result, ctx->running_crc = crc_add_byte(ctx->running_crc, *p); if (p == (uint8_t *)buf + ctx->block_size - 1) old = buf; + /* We don't roll this csum, we only look for it after + * a block match. It's simpler and faster. */ + if (final_matches(ctx)) { + crcmatch = ctx->num_crcs; + goto have_match; + } } - - ctx->literal_bytes++; - ctx->total_bytes++; - consumed++; p++; } @@ -180,8 +216,11 @@ size_t crc_read_block(struct crc_context *ctx, long *result, } else { have_match: *result = -crcmatch-1; - ctx->literal_bytes -= ctx->block_size; - assert(ctx->literal_bytes == 0); + if (crcmatch == ctx->num_crcs) + assert(ctx->literal_bytes == ctx->final_size); + else + assert(ctx->literal_bytes == ctx->block_size); + ctx->literal_bytes = 0; ctx->have_match = -1; ctx->running_crc = 0; /* Nothing more in the buffer. */ @@ -219,37 +258,9 @@ size_t crc_read_block(struct crc_context *ctx, long *result, return consumed; } -/* We could try many techniques to match the final block. We can - * simply try to checksum whatever's left at the end and see if it - * matches the final block checksum. This works for the exact-match - * case. - * - * We can do slightly better than this: if we try to match the checksum - * on every block (starting with block_size 1) from where we end to EOF, - * we can capture the "data appended" case as well. - */ -static size_t final_block_match(struct crc_context *ctx) -{ - size_t size; - uint32_t crc; - - if (ctx->num_crcs == 0) - return 0; - - crc = 0; - for (size = 0; size < buffer_size(ctx); size++) { - const uint8_t *p = ctx->buffer; - crc = crc_add_byte(crc, p[ctx->buffer_start+size]); - if ((crc & ctx->crcmask) == ctx->crc[ctx->num_crcs-1]) - return size+1; - } - return 0; -} - long crc_read_flush(struct crc_context *ctx) { long ret; - size_t final; /* We might have ended right on a matched block. */ if (ctx->have_match != -1) { @@ -263,20 +274,11 @@ long crc_read_flush(struct crc_context *ctx) return ret; } - /* Look for truncated final block. */ - final = final_block_match(ctx); - if (!final) { - /* Nope? Just a literal. */ - ret = buffer_size(ctx); - ctx->buffer_start += ret; - ctx->literal_bytes -= ret; - return ret; - } - - /* We matched (some of) what's left. */ - ret = -((int)ctx->num_crcs-1)-1; - ctx->buffer_start += final; - ctx->literal_bytes -= final; + /* The rest is just a literal. */ + ret = buffer_size(ctx); + assert(ctx->literal_bytes == ret); + ctx->buffer_start = ctx->buffer_end = 0; + ctx->literal_bytes = 0; return ret; } diff --git a/ccan/crcsync/crcsync.h b/ccan/crcsync/crcsync.h index 8ea33457..4b25562b 100644 --- a/ccan/crcsync/crcsync.h +++ b/ccan/crcsync/crcsync.h @@ -23,12 +23,14 @@ void crc_of_blocks(const void *data, size_t len, unsigned int blocksize, * @crcbits: the bits valid in the CRCs (<= 32) * @crc: array of block crcs * @num_crcs: number of block crcs + * @final_size: the final block size (<= blocksize). * * Returns an allocated pointer to the structure for crc_find_block, * or NULL. Makes a copy of @crc and @num_crcs. */ struct crc_context *crc_context_new(size_t blocksize, unsigned crcbits, - const uint32_t crc[], unsigned num_crcs); + const uint32_t crc[], unsigned num_crcs, + size_t final_size); /** * crc_read_block - search for block matches in the buffer. diff --git a/ccan/crcsync/test/api.c b/ccan/crcsync/test/api.c deleted file mode 100644 index 2f07cb69..00000000 --- a/ccan/crcsync/test/api.c +++ /dev/null @@ -1,284 +0,0 @@ -#include "crcsync/crcsync.h" -#include "tap/tap.h" -#include -#include -#include - -/* FIXME: ccanize. */ -#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) - -struct result { - enum { - LITERAL, BLOCK - } type; - /* Block number, or length of literal. */ - size_t val; -}; - -static inline size_t num_blocks(size_t len, size_t block_size) -{ - return (len + block_size - 1) / block_size; -} - -static void check_finalized_result(size_t curr_literal, - const struct result results[], - size_t num_results, - size_t *curr_result) -{ - if (curr_literal == 0) - return; - ok1(*curr_result < num_results); - ok1(results[*curr_result].type == LITERAL); - ok1(results[*curr_result].val == curr_literal); - (*curr_result)++; -} - -static void check_result(long result, - size_t *curr_literal, - const struct result results[], size_t num_results, - size_t *curr_result) -{ - /* We append multiple literals into one. */ - if (result >= 0) { - *curr_literal += result; - return; - } - - /* Check outstanding literals. */ - if (*curr_literal) { - check_finalized_result(*curr_literal, results, num_results, - curr_result); - *curr_literal = 0; - } - - ok1(*curr_result < num_results); - ok1(results[*curr_result].type == BLOCK); - ok1(results[*curr_result].val == -result - 1); - (*curr_result)++; -} - -/* Start with buffer1 and sync to buffer2. */ -static void test_sync(const char *buffer1, size_t len1, - const char *buffer2, size_t len2, - size_t block_size, - const struct result results[], size_t num_results) -{ - struct crc_context *ctx; - size_t used, ret, i, curr_literal; - long result; - uint32_t crcs[num_blocks(len1, block_size)]; - - crc_of_blocks(buffer1, len1, block_size, 32, crcs); - - /* Normal method. */ - ctx = crc_context_new(block_size, 32, crcs, ARRAY_SIZE(crcs)); - - curr_literal = 0; - for (used = 0, i = 0; used < len2; used += ret) { - ret = crc_read_block(ctx, &result, buffer2+used, len2-used); - check_result(result, &curr_literal, results, num_results, &i); - } - - while ((result = crc_read_flush(ctx)) != 0) - check_result(result, &curr_literal, results, num_results, &i); - - check_finalized_result(curr_literal, results, num_results, &i); - - /* We must have achieved everything we expected. */ - ok1(i == num_results); - crc_context_free(ctx); - - /* Byte-at-a-time method. */ - ctx = crc_context_new(block_size, 32, crcs, ARRAY_SIZE(crcs)); - - curr_literal = 0; - for (used = 0, i = 0; used < len2; used += ret) { - ret = crc_read_block(ctx, &result, buffer2+used, 1); - - check_result(result, &curr_literal, results, num_results, &i); - } - - while ((result = crc_read_flush(ctx)) != 0) - check_result(result, &curr_literal, results, num_results, &i); - - check_finalized_result(curr_literal, results, num_results, &i); - - /* We must have achieved everything we expected. */ - ok1(i == num_results); - crc_context_free(ctx); -} - -int main(int argc, char *argv[]) -{ - char *buffer1, *buffer2; - unsigned int i; - uint32_t crcs1[12], crcs2[12]; - - plan_tests(1454); - - buffer1 = calloc(1024, 1); - buffer2 = calloc(1024, 1); - - /* Truncated end block test. */ - crcs1[11] = 0xdeadbeef; - crc_of_blocks(buffer1, 1024, 100, 32, crcs1); - ok1(crcs1[11] == 0xdeadbeef); - crc_of_blocks(buffer2, 1024, 100, 32, crcs2); - ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*11) == 0); - - /* Fill with non-zero pattern, retest. */ - for (i = 0; i < 1024; i++) - buffer1[i] = buffer2[i] = i + i/128; - - crcs1[11] = 0xdeadbeef; - crc_of_blocks(buffer1, 1024, 100, 32, crcs1); - ok1(crcs1[11] == 0xdeadbeef); - crc_of_blocks(buffer2, 1024, 100, 32, crcs2); - ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*11) == 0); - - /* Check that it correctly masks bits. */ - crc_of_blocks(buffer1, 1024, 128, 32, crcs1); - crc_of_blocks(buffer2, 1024, 128, 8, crcs2); - for (i = 0; i < 1024/128; i++) - ok1(crcs2[i] == (crcs1[i] & 0xFF)); - - /* Now test the "exact match" "round blocks" case. */ - { - struct result res[] = { - { BLOCK, 0 }, - { BLOCK, 1 }, - { BLOCK, 2 }, - { BLOCK, 3 }, - { BLOCK, 4 }, - { BLOCK, 5 }, - { BLOCK, 6 }, - { BLOCK, 7 } }; - test_sync(buffer1, 1024, buffer2, 1024, 128, - res, ARRAY_SIZE(res)); - } - - /* Now test the "exact match" with end block case. */ - { - struct result res[] = { - { BLOCK, 0 }, - { BLOCK, 1 }, - { BLOCK, 2 }, - { BLOCK, 3 }, - { BLOCK, 4 }, - { BLOCK, 5 }, - { BLOCK, 6 }, - { BLOCK, 7 }, - { BLOCK, 8 }, - { BLOCK, 9 }, - { BLOCK, 10 } }; - test_sync(buffer1, 1024, buffer2, 1024, 100, - res, ARRAY_SIZE(res)); - } - - /* Now test the "one byte append" "round blocks" case. */ - { - struct result res[] = { - { BLOCK, 0 }, - { BLOCK, 1 }, - { BLOCK, 2 }, - { BLOCK, 3 }, - { BLOCK, 4 }, - { BLOCK, 5 }, - { BLOCK, 6 }, - { LITERAL, 1 } }; - test_sync(buffer1, 1024-128, buffer2, 1024-127, 128, - res, ARRAY_SIZE(res)); - } - - /* Now test the "one byte append" with end block case. */ - { - struct result res[] = { - { BLOCK, 0 }, - { BLOCK, 1 }, - { BLOCK, 2 }, - { BLOCK, 3 }, - { BLOCK, 4 }, - { BLOCK, 5 }, - { BLOCK, 6 }, - { BLOCK, 7 }, - { BLOCK, 8 }, - { BLOCK, 9 }, - { BLOCK, 10 }, - { LITERAL, 1 } }; - test_sync(buffer1, 1023, buffer2, 1024, 100, - res, ARRAY_SIZE(res)); - } - - /* Now try changing one block at a time, check we get right results. */ - for (i = 0; i < 1024/128; i++) { - unsigned int j; - struct result res[8]; - - /* Mess with block. */ - memcpy(buffer2, buffer1, 1024); - buffer2[i * 128]++; - - for (j = 0; j < ARRAY_SIZE(res); j++) { - if (j == i) { - res[j].type = LITERAL; - res[j].val = 128; - } else { - res[j].type = BLOCK; - res[j].val = j; - } - } - - test_sync(buffer1, 1024, buffer2, 1024, 128, - res, ARRAY_SIZE(res)); - } - - /* Now try shrinking one block at a time, check we get right results. */ - for (i = 0; i < 1024/128; i++) { - unsigned int j; - struct result res[8]; - - /* Shrink block. */ - memcpy(buffer2, buffer1, i * 128 + 64); - memcpy(buffer2 + i * 128 + 64, buffer1 + i * 128 + 65, - 1024 - (i * 128 + 65)); - - for (j = 0; j < ARRAY_SIZE(res); j++) { - if (j == i) { - res[j].type = LITERAL; - res[j].val = 127; - } else { - res[j].type = BLOCK; - res[j].val = j; - } - } - - test_sync(buffer1, 1024, buffer2, 1023, 128, - res, ARRAY_SIZE(res)); - } - - /* Now try shrinking one block at a time, check we get right results. */ - for (i = 0; i < 1024/128; i++) { - unsigned int j; - struct result res[8]; - - /* Shrink block. */ - memcpy(buffer2, buffer1, i * 128 + 64); - memcpy(buffer2 + i * 128 + 64, buffer1 + i * 128 + 65, - 1024 - (i * 128 + 65)); - - for (j = 0; j < ARRAY_SIZE(res); j++) { - if (j == i) { - res[j].type = LITERAL; - res[j].val = 127; - } else { - res[j].type = BLOCK; - res[j].val = j; - } - } - - test_sync(buffer1, 1024, buffer2, 1023, 128, - res, ARRAY_SIZE(res)); - } - - return exit_status(); -} diff --git a/ccan/crcsync/test/run-crash.c b/ccan/crcsync/test/run-crash.c index c047cce2..7fb1df45 100644 --- a/ccan/crcsync/test/run-crash.c +++ b/ccan/crcsync/test/run-crash.c @@ -39,26 +39,30 @@ int main(int argc, char *argv[]) "pqr-a-very-long-test-that-differs-between-two-invokations-of-the-same-page-st" /* MATCH */ "uvwxy" "z ABC" "DEFGH" "IJKLM" "NOPQR" "STUVW" "XYZ 0" "12345" + "6789" /* NO MATCH */ - "6789ab"; + "ab"; int expected[] = { 4, -2, -3, 77, -5, -6, -7, -8, -9, -10, -11, -12, - 6 }; + -13, + 2 }; crc_info_t crc_info1; struct crc_context *crcctx; long result; size_t ndigested; size_t offset = 0; size_t len2 = strlen(data2); + size_t finalsize = strlen(data1) % BLOCKSIZE ?: BLOCKSIZE; int expected_i = 0; 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, 30, crc_info1.crcs, crc_info1.block_count, + finalsize); while ( offset < len2) { ndigested = crc_read_block(crcctx, &result, data2+offset, len2 - offset); diff --git a/ccan/crcsync/test/run.c b/ccan/crcsync/test/run.c new file mode 100644 index 00000000..5f821b6c --- /dev/null +++ b/ccan/crcsync/test/run.c @@ -0,0 +1,289 @@ +#include "crcsync/crcsync.h" +#include "../crcsync.c" +#include "tap/tap.h" +#include +#include +#include + +/* FIXME: ccanize. */ +#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) + +struct result { + enum { + LITERAL, BLOCK + } type; + /* Block number, or length of literal. */ + size_t val; +}; + +static inline size_t num_blocks(size_t len, size_t block_size) +{ + return (len + block_size - 1) / block_size; +} + +static void check_finalized_result(size_t curr_literal, + const struct result results[], + size_t num_results, + size_t *curr_result) +{ + if (curr_literal == 0) + return; + ok1(*curr_result < num_results); + ok1(results[*curr_result].type == LITERAL); + ok1(results[*curr_result].val == curr_literal); + (*curr_result)++; +} + +static void check_result(long result, + size_t *curr_literal, + const struct result results[], size_t num_results, + size_t *curr_result) +{ + /* We append multiple literals into one. */ + if (result >= 0) { + *curr_literal += result; + return; + } + + /* Check outstanding literals. */ + if (*curr_literal) { + check_finalized_result(*curr_literal, results, num_results, + curr_result); + *curr_literal = 0; + } + + ok1(*curr_result < num_results); + ok1(results[*curr_result].type == BLOCK); + ok1(results[*curr_result].val == -result - 1); + (*curr_result)++; +} + +/* Start with buffer1 and sync to buffer2. */ +static void test_sync(const char *buffer1, size_t len1, + const char *buffer2, size_t len2, + size_t block_size, + const struct result results[], size_t num_results) +{ + struct crc_context *ctx; + size_t used, ret, i, curr_literal, finalsize; + long result; + uint32_t crcs[num_blocks(len1, block_size)]; + + crc_of_blocks(buffer1, len1, block_size, 32, crcs); + + finalsize = len1 % block_size ?: block_size; + + /* Normal method. */ + ctx = crc_context_new(block_size, 32, crcs, ARRAY_SIZE(crcs), + finalsize); + + curr_literal = 0; + for (used = 0, i = 0; used < len2; used += ret) { + ret = crc_read_block(ctx, &result, buffer2+used, len2-used); + check_result(result, &curr_literal, results, num_results, &i); + } + + while ((result = crc_read_flush(ctx)) != 0) + check_result(result, &curr_literal, results, num_results, &i); + + check_finalized_result(curr_literal, results, num_results, &i); + + /* We must have achieved everything we expected. */ + ok1(i == num_results); + crc_context_free(ctx); + + /* Byte-at-a-time method. */ + ctx = crc_context_new(block_size, 32, crcs, ARRAY_SIZE(crcs), + finalsize); + + curr_literal = 0; + for (used = 0, i = 0; used < len2; used += ret) { + ret = crc_read_block(ctx, &result, buffer2+used, 1); + + check_result(result, &curr_literal, results, num_results, &i); + } + + while ((result = crc_read_flush(ctx)) != 0) + check_result(result, &curr_literal, results, num_results, &i); + + check_finalized_result(curr_literal, results, num_results, &i); + + /* We must have achieved everything we expected. */ + ok1(i == num_results); + crc_context_free(ctx); +} + +int main(int argc, char *argv[]) +{ + char *buffer1, *buffer2; + unsigned int i; + uint32_t crcs1[12], crcs2[12]; + + plan_tests(1454); + + buffer1 = calloc(1024, 1); + buffer2 = calloc(1024, 1); + + /* Truncated end block test. */ + crcs1[11] = 0xdeadbeef; + crc_of_blocks(buffer1, 1024, 100, 32, crcs1); + ok1(crcs1[11] == 0xdeadbeef); + crc_of_blocks(buffer2, 1024, 100, 32, crcs2); + ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*11) == 0); + + /* Fill with non-zero pattern, retest. */ + for (i = 0; i < 1024; i++) + buffer1[i] = buffer2[i] = i + i/128; + + crcs1[11] = 0xdeadbeef; + crc_of_blocks(buffer1, 1024, 100, 32, crcs1); + ok1(crcs1[11] == 0xdeadbeef); + crc_of_blocks(buffer2, 1024, 100, 32, crcs2); + ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*11) == 0); + + /* Check that it correctly masks bits. */ + crc_of_blocks(buffer1, 1024, 128, 32, crcs1); + crc_of_blocks(buffer2, 1024, 128, 8, crcs2); + for (i = 0; i < 1024/128; i++) + ok1(crcs2[i] == (crcs1[i] & 0xFF)); + + /* Now test the "exact match" "round blocks" case. */ + { + struct result res[] = { + { BLOCK, 0 }, + { BLOCK, 1 }, + { BLOCK, 2 }, + { BLOCK, 3 }, + { BLOCK, 4 }, + { BLOCK, 5 }, + { BLOCK, 6 }, + { BLOCK, 7 } }; + test_sync(buffer1, 1024, buffer2, 1024, 128, + res, ARRAY_SIZE(res)); + } + + /* Now test the "exact match" with end block case. */ + { + struct result res[] = { + { BLOCK, 0 }, + { BLOCK, 1 }, + { BLOCK, 2 }, + { BLOCK, 3 }, + { BLOCK, 4 }, + { BLOCK, 5 }, + { BLOCK, 6 }, + { BLOCK, 7 }, + { BLOCK, 8 }, + { BLOCK, 9 }, + { BLOCK, 10 } }; + test_sync(buffer1, 1024, buffer2, 1024, 100, + res, ARRAY_SIZE(res)); + } + + /* Now test the "one byte append" "round blocks" case. */ + { + struct result res[] = { + { BLOCK, 0 }, + { BLOCK, 1 }, + { BLOCK, 2 }, + { BLOCK, 3 }, + { BLOCK, 4 }, + { BLOCK, 5 }, + { BLOCK, 6 }, + { LITERAL, 1 } }; + test_sync(buffer1, 1024-128, buffer2, 1024-127, 128, + res, ARRAY_SIZE(res)); + } + + /* Now test the "one byte append" with end block case. */ + { + struct result res[] = { + { BLOCK, 0 }, + { BLOCK, 1 }, + { BLOCK, 2 }, + { BLOCK, 3 }, + { BLOCK, 4 }, + { BLOCK, 5 }, + { BLOCK, 6 }, + { BLOCK, 7 }, + { BLOCK, 8 }, + { BLOCK, 9 }, + { BLOCK, 10 }, + { LITERAL, 1 } }; + test_sync(buffer1, 1023, buffer2, 1024, 100, + res, ARRAY_SIZE(res)); + } + + /* Now try changing one block at a time, check we get right results. */ + for (i = 0; i < 1024/128; i++) { + unsigned int j; + struct result res[8]; + + /* Mess with block. */ + memcpy(buffer2, buffer1, 1024); + buffer2[i * 128]++; + + for (j = 0; j < ARRAY_SIZE(res); j++) { + if (j == i) { + res[j].type = LITERAL; + res[j].val = 128; + } else { + res[j].type = BLOCK; + res[j].val = j; + } + } + + test_sync(buffer1, 1024, buffer2, 1024, 128, + res, ARRAY_SIZE(res)); + } + + /* Now try shrinking one block at a time, check we get right results. */ + for (i = 0; i < 1024/128; i++) { + unsigned int j; + struct result res[8]; + + /* Shrink block. */ + memcpy(buffer2, buffer1, i * 128 + 64); + memcpy(buffer2 + i * 128 + 64, buffer1 + i * 128 + 65, + 1024 - (i * 128 + 65)); + + for (j = 0; j < ARRAY_SIZE(res); j++) { + if (j == i) { + res[j].type = LITERAL; + res[j].val = 127; + } else { + res[j].type = BLOCK; + res[j].val = j; + } + } + + test_sync(buffer1, 1024, buffer2, 1023, 128, + res, ARRAY_SIZE(res)); + } + + /* Now try shrinking one block at a time, check we get right results. */ + for (i = 0; i < 1024/128; i++) { + unsigned int j; + struct result res[8]; + + /* Shrink block. */ + memcpy(buffer2, buffer1, i * 128 + 64); + memcpy(buffer2 + i * 128 + 64, buffer1 + i * 128 + 65, + 1024 - (i * 128 + 65)); + + for (j = 0; j < ARRAY_SIZE(res); j++) { + if (j == i) { + res[j].type = LITERAL; + res[j].val = 127; + } else { + res[j].type = BLOCK; + res[j].val = j; + } + } + + test_sync(buffer1, 1024, buffer2, 1023, 128, + res, ARRAY_SIZE(res)); + } + + return exit_status(); +}