lib/bup/bupsplit.c

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