lib/bup/bupsplit.c

   1 #include "bupsplit.h"
   2 #include <assert.h>
   3 #include <stdint.h>
   4 #include <memory.h>
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7
   8 // According to librsync/rollsum.h:
   9 // "We should make this something other than zero to improve the
  10 // checksum algorithm: tridge suggests a prime number."
  11 // apenwarr: I unscientifically tried 0 and 7919, and they both ended up
  12 // slightly worse than the librsync value of 31 for my arbitrary test data.
  13 #define ROLLSUM_CHAR_OFFSET 31
  14
  15 typedef struct {
  16     unsigned s1, s2;
  17     uint8_t window[BUP_WINDOWSIZE];
  18     int wofs;
  19 } Rollsum;
  20
  21
  22 // These formulas are based on rollsum.h in the librsync project.
  23 static void rollsum_add(Rollsum *r, uint8_t drop, uint8_t add)
  24 {
  25     r->s1 += add - drop;
  26     r->s2 += r->s1 - (BUP_WINDOWSIZE * (drop + ROLLSUM_CHAR_OFFSET));
  27 }
  28
  29
  30 static void rollsum_init(Rollsum *r)
  31 {
  32     r->s1 = BUP_WINDOWSIZE * ROLLSUM_CHAR_OFFSET;
  33     r->s2 = BUP_WINDOWSIZE * (BUP_WINDOWSIZE-1) * ROLLSUM_CHAR_OFFSET;
  34     r->wofs = 0;
  35     memset(r->window, 0, BUP_WINDOWSIZE);
  36 }
  37
  38
  39 // For some reason, gcc 4.3 (at least) optimizes badly if find_ofs()
  40 // is static and rollsum_roll is an inline function.  Let's use a macro
  41 // here instead to help out the optimizer.
  42 #define rollsum_roll(r, ch) do { \
  43     rollsum_add((r), (r)->window[(r)->wofs], (ch)); \
  44     (r)->window[(r)->wofs] = (ch); \
  45     (r)->wofs = ((r)->wofs + 1) % BUP_WINDOWSIZE; \
  46 } while (0)
  47
  48
  49 static uint32_t rollsum_digest(Rollsum *r)
  50 {
  51     return (r->s1 << 16) | (r->s2 & 0xffff);
  52 }
  53
  54
  55 static uint32_t rollsum_sum(uint8_t *buf, size_t ofs, size_t len)
  56 {
  57     size_t count;
  58     Rollsum r;
  59     rollsum_init(&r);
  60     for (count = ofs; count < len; count++)
  61         rollsum_roll(&r, buf[count]);
  62     return rollsum_digest(&r);
  63 }
  64
  65
  66 int bupsplit_find_ofs(const unsigned char *buf, int len, int *bits)
  67 {
  68     Rollsum r;
  69     int count;
  70
  71     rollsum_init(&r);
  72     for (count = 0; count < len; count++)
  73     {
  74         rollsum_roll(&r, buf[count]);
  75         if ((r.s2 & (BUP_BLOBSIZE-1)) == ((~0) & (BUP_BLOBSIZE-1)))
  76         {
  77             if (bits)
  78             {
  79                 unsigned rsum = rollsum_digest(&r);
  80                 *bits = BUP_BLOBBITS;
  81                 rsum >>= BUP_BLOBBITS;
  82                 for (*bits = BUP_BLOBBITS; (rsum >>= 1) & 1; (*bits)++)
  83                     ;
  84             }
  85             return count+1;
  86         }
  87     }
  88     return 0;
  89 }
  90
  91
  92 #ifndef BUP_NO_SELFTEST
  93
  94 int bupsplit_selftest()
  95 {
  96     uint8_t buf[100000];
  97     uint32_t sum1a, sum1b, sum2a, sum2b, sum3a, sum3b;
  98     unsigned count;
  99
 100     srandom(1);
 101     for (count = 0; count < sizeof(buf); count++)
 102         buf[count] = random();
 103
 104     sum1a = rollsum_sum(buf, 0, sizeof(buf));
 105     sum1b = rollsum_sum(buf, 1, sizeof(buf));
 106     sum2a = rollsum_sum(buf, sizeof(buf) - BUP_WINDOWSIZE*5/2,
 107                         sizeof(buf) - BUP_WINDOWSIZE);
 108     sum2b = rollsum_sum(buf, 0, sizeof(buf) - BUP_WINDOWSIZE);
 109     sum3a = rollsum_sum(buf, 0, BUP_WINDOWSIZE+3);
 110     sum3b = rollsum_sum(buf, 3, BUP_WINDOWSIZE+3);
 111
 112     fprintf(stderr, "sum1a = 0x%08x\n", sum1a);
 113     fprintf(stderr, "sum1b = 0x%08x\n", sum1b);
 114     fprintf(stderr, "sum2a = 0x%08x\n", sum2a);
 115     fprintf(stderr, "sum2b = 0x%08x\n", sum2b);
 116     fprintf(stderr, "sum3a = 0x%08x\n", sum3a);
 117     fprintf(stderr, "sum3b = 0x%08x\n", sum3b);
 118
 119     return sum1a!=sum1b || sum2a!=sum2b || sum3a!=sum3b;
 120 }
 121
 122 #endif // !BUP_NO_SELFTEST