crcsync change: better detection of final block.
authorRusty Russell <rusty@rustcorp.com.au>
Sat, 4 Apr 2009 11:35:46 +0000 (22:05 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Sat, 4 Apr 2009 11:35:46 +0000 (22:05 +1030)
ccan/crcsync/crcsync.c
ccan/crcsync/crcsync.h
ccan/crcsync/test/api.c [deleted file]
ccan/crcsync/test/run-crash.c
ccan/crcsync/test/run.c [new file with mode: 0644]

index 2301bc103c1fce4952dbb14cd88057416d62339c..459010a760f7e826b7a3780e8ef6491a1ee5213f 100644 (file)
@@ -2,6 +2,7 @@
 #include <ccan/crc/crc.h>
 #include <string.h>
 #include <assert.h>
+#include <stdbool.h>
 
 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;
 }
 
index 8ea33457b32b88fc7bf704d946fdb3ecad6bcc38..4b25562bbb793d6f1bd9b193d785a963eca5aaf6 100644 (file)
@@ -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 (file)
index 2f07cb6..0000000
+++ /dev/null
@@ -1,284 +0,0 @@
-#include "crcsync/crcsync.h"
-#include "tap/tap.h"
-#include <stdlib.h>
-#include <stdbool.h>
-#include <string.h>
-
-/* 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();
-}
index c047cce28c0d7d8f26f0d0a5874def9a8b06a2e4..7fb1df4554ffd5754ff3d5214defbcbf9ad9828f 100644 (file)
@@ -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 (file)
index 0000000..5f821b6
--- /dev/null
@@ -0,0 +1,289 @@
+#include "crcsync/crcsync.h"
+#include "../crcsync.c"
+#include "tap/tap.h"
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+
+/* 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();
+}