lib/bup/bupsplit.c

   1 /*
   2  * Copyright 2011 Avery Pennarun. All rights reserved.
   3  *
   4  * (This license applies to bupsplit.c and bupsplit.h only.)
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are
   8  * met:
   9  *
  10  *    1. Redistributions of source code must retain the above copyright
  11  *       notice, this list of conditions and the following disclaimer.
  12  *
  13  *    2. Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY AVERY PENNARUN AND CONTRIBUTORS ``AS
  19  * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  21  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
  22  * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  23  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  24  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  27  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  29  * OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31 #include "bupsplit.h"
  32 #include <stdint.h>
  33 #include <memory.h>
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36
  37 // According to librsync/rollsum.h:
  38 // "We should make this something other than zero to improve the
  39 // checksum algorithm: tridge suggests a prime number."
  40 // apenwarr: I unscientifically tried 0 and 7919, and they both ended up
  41 // slightly worse than the librsync value of 31 for my arbitrary test data.
  42 #define ROLLSUM_CHAR_OFFSET 31
  43
  44 typedef struct {
  45     unsigned s1, s2;
  46     uint8_t window[BUP_WINDOWSIZE];
  47     int wofs;
  48 } Rollsum;
  49
  50
  51 // These formulas are based on rollsum.h in the librsync project.
  52 static void rollsum_add(Rollsum *r, uint8_t drop, uint8_t add)
  53 {
  54     r->s1 += add - drop;
  55     r->s2 += r->s1 - (BUP_WINDOWSIZE * (drop + ROLLSUM_CHAR_OFFSET));
  56 }
  57
  58
  59 static void rollsum_init(Rollsum *r)
  60 {
  61     r->s1 = BUP_WINDOWSIZE * ROLLSUM_CHAR_OFFSET;
  62     r->s2 = BUP_WINDOWSIZE * (BUP_WINDOWSIZE-1) * ROLLSUM_CHAR_OFFSET;
  63     r->wofs = 0;
  64     memset(r->window, 0, BUP_WINDOWSIZE);
  65 }
  66
  67
  68 // For some reason, gcc 4.3 (at least) optimizes badly if find_ofs()
  69 // is static and rollsum_roll is an inline function.  Let's use a macro
  70 // here instead to help out the optimizer.
  71 #define rollsum_roll(r, ch) do { \
  72     rollsum_add((r), (r)->window[(r)->wofs], (ch)); \
  73     (r)->window[(r)->wofs] = (ch); \
  74     (r)->wofs = ((r)->wofs + 1) % BUP_WINDOWSIZE; \
  75 } while (0)
  76
  77
  78 static uint32_t rollsum_digest(Rollsum *r)
  79 {
  80     return (r->s1 << 16) | (r->s2 & 0xffff);
  81 }
  82
  83
  84 static uint32_t rollsum_sum(uint8_t *buf, size_t ofs, size_t len)
  85 {
  86     size_t count;
  87     Rollsum r;
  88     rollsum_init(&r);
  89     for (count = ofs; count < len; count++)
  90         rollsum_roll(&r, buf[count]);
  91     return rollsum_digest(&r);
  92 }
  93
  94
  95 int bupsplit_find_ofs(const unsigned char *buf, int len, int *bits)
  96 {
  97     Rollsum r;
  98     int count;
  99
 100     rollsum_init(&r);
 101     for (count = 0; count < len; count++)
 102     {
 103         rollsum_roll(&r, buf[count]);
 104         if ((r.s2 & (BUP_BLOBSIZE-1)) == ((~0) & (BUP_BLOBSIZE-1)))
 105         {
 106             if (bits)
 107             {
 108                 unsigned rsum = rollsum_digest(&r);
 109                 rsum >>= BUP_BLOBBITS;
 110                 for (*bits = BUP_BLOBBITS; (rsum >>= 1) & 1; (*bits)++)
 111                     ;
 112             }
 113             return count+1;
 114         }
 115     }
 116     return 0;
 117 }
 118
 119
 120 #ifndef BUP_NO_SELFTEST
 121 #define BUP_SELFTEST_SIZE 100000
 122
 123 int bupsplit_selftest()
 124 {
 125     uint8_t *buf = malloc(BUP_SELFTEST_SIZE);
 126     uint32_t sum1a, sum1b, sum2a, sum2b, sum3a, sum3b;
 127     unsigned count;
 128
 129     srandom(1);
 130     for (count = 0; count < BUP_SELFTEST_SIZE; count++)
 131         buf[count] = random();
 132
 133     sum1a = rollsum_sum(buf, 0, BUP_SELFTEST_SIZE);
 134     sum1b = rollsum_sum(buf, 1, BUP_SELFTEST_SIZE);
 135     sum2a = rollsum_sum(buf, BUP_SELFTEST_SIZE - BUP_WINDOWSIZE*5/2,
 136                         BUP_SELFTEST_SIZE - BUP_WINDOWSIZE);
 137     sum2b = rollsum_sum(buf, 0, BUP_SELFTEST_SIZE - BUP_WINDOWSIZE);
 138     sum3a = rollsum_sum(buf, 0, BUP_WINDOWSIZE+3);
 139     sum3b = rollsum_sum(buf, 3, BUP_WINDOWSIZE+3);
 140
 141     fprintf(stderr, "sum1a = 0x%08x\n", sum1a);
 142     fprintf(stderr, "sum1b = 0x%08x\n", sum1b);
 143     fprintf(stderr, "sum2a = 0x%08x\n", sum2a);
 144     fprintf(stderr, "sum2b = 0x%08x\n", sum2b);
 145     fprintf(stderr, "sum3a = 0x%08x\n", sum3a);
 146     fprintf(stderr, "sum3b = 0x%08x\n", sum3b);
 147
 148     free(buf);
 149     return sum1a!=sum1b || sum2a!=sum2b || sum3a!=sum3b;
 150 }
 151
 152 #endif // !BUP_NO_SELFTEST