lib/bup/_hashsplit.c

   1 #include <Python.h>
   2 #include <assert.h>
   3 #include <stdint.h>
   4
   5 #define BLOBBITS (13)
   6 #define BLOBSIZE (1<<BLOBBITS)
   7 #define WINDOWBITS (7)
   8 #define WINDOWSIZE (1<<(WINDOWBITS-1))
   9
  10
  11 // FIXME: replace this with a not-stupid rolling checksum algorithm,
  12 // such as the one used in rsync (Adler32?)
  13 static uint32_t stupidsum_add(uint32_t old, uint8_t drop, uint8_t add)
  14 {
  15     return ((old<<1) | (old>>31)) ^ drop ^ add;
  16 }
  17
  18
  19 static int find_ofs(const unsigned char *buf, int len, int *bits)
  20 {
  21     unsigned char window[WINDOWSIZE];
  22     uint32_t sum = 0;
  23     int i = 0, count;
  24     memset(window, 0, sizeof(window));
  25
  26     for (count = 0; count < len; count++)
  27     {
  28         sum = stupidsum_add(sum, window[i], buf[count]);
  29         window[i] = buf[count];
  30         i = (i + 1) % WINDOWSIZE;
  31         if ((sum & (BLOBSIZE-1)) == ((~0) & (BLOBSIZE-1)))
  32         {
  33             if (bits)
  34             {
  35                 *bits = BLOBBITS;
  36                 sum >>= BLOBBITS;
  37                 for (*bits = BLOBBITS; (sum >>= 1) & 1; (*bits)++)
  38                     ;
  39             }
  40             return count+1;
  41         }
  42     }
  43     return 0;
  44 }
  45
  46
  47 static PyObject *blobbits(PyObject *self, PyObject *args)
  48 {
  49     if (!PyArg_ParseTuple(args, ""))
  50         return NULL;
  51     return Py_BuildValue("i", BLOBBITS);
  52 }
  53
  54
  55 static PyObject *splitbuf(PyObject *self, PyObject *args)
  56 {
  57     unsigned char *buf = NULL;
  58     int len = 0, out = 0, bits = -1;
  59
  60     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
  61         return NULL;
  62     out = find_ofs(buf, len, &bits);
  63     return Py_BuildValue("ii", out, bits);
  64 }
  65
  66
  67 static PyObject *bitmatch(PyObject *self, PyObject *args)
  68 {
  69     unsigned char *buf1 = NULL, *buf2 = NULL;
  70     int len1 = 0, len2 = 0;
  71     int byte, bit;
  72
  73     if (!PyArg_ParseTuple(args, "t#t#", &buf1, &len1, &buf2, &len2))
  74         return NULL;
  75
  76     bit = 0;
  77     for (byte = 0; byte < len1 && byte < len2; byte++)
  78     {
  79         int b1 = buf1[byte], b2 = buf2[byte];
  80         if (b1 != b2)
  81         {
  82             for (bit = 0; bit < 8; bit++)
  83                 if ( (b1 & (0x80 >> bit)) != (b2 & (0x80 >> bit)) )
  84                     break;
  85             break;
  86         }
  87     }
  88
  89     return Py_BuildValue("i", byte*8 + bit);
  90 }
  91
  92
  93 // I would have made this a lower-level function that just fills in a buffer
  94 // with random values, and then written those values from python.  But that's
  95 // about 20% slower in my tests, and since we typically generate random
  96 // numbers for benchmarking other parts of bup, any slowness in generating
  97 // random bytes will make our benchmarks inaccurate.  Plus nobody wants
  98 // pseudorandom bytes much except for this anyway.
  99 static PyObject *write_random(PyObject *self, PyObject *args)
 100 {
 101     uint32_t buf[1024/4];
 102     int fd = -1, seed = 0;
 103     ssize_t ret;
 104     long long len = 0, kbytes = 0, written = 0;
 105
 106     if (!PyArg_ParseTuple(args, "iLi", &fd, &len, &seed))
 107         return NULL;
 108
 109     srandom(seed);
 110
 111     for (kbytes = 0; kbytes < len/1024; kbytes++)
 112     {
 113         int i;
 114         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 115             buf[i] = random();
 116         ret = write(fd, buf, sizeof(buf));
 117         if (ret < 0)
 118             ret = 0;
 119         written += ret;
 120         if (ret < sizeof(buf))
 121             break;
 122         if (kbytes/1024 > 0 && !(kbytes%1024))
 123             fprintf(stderr, "Random: %lld Mbytes\r", kbytes/1024);
 124     }
 125
 126     if (kbytes/1024 > 0)
 127         fprintf(stderr, "Random: %lld Mbytes, done.\n", kbytes/1024);
 128     return Py_BuildValue("L", written);
 129 }
 130
 131
 132 static PyMethodDef hashsplit_methods[] = {
 133     { "blobbits", blobbits, METH_VARARGS,
 134         "Return the number of bits in the rolling checksum." },
 135     { "splitbuf", splitbuf, METH_VARARGS,
 136         "Split a list of strings based on a rolling checksum." },
 137     { "bitmatch", bitmatch, METH_VARARGS,
 138         "Count the number of matching prefix bits between two strings." },
 139     { "write_random", write_random, METH_VARARGS,
 140         "Write random bytes to the given file descriptor" },
 141     { NULL, NULL, 0, NULL },  // sentinel
 142 };
 143
 144 PyMODINIT_FUNC init_hashsplit(void)
 145 {
 146     Py_InitModule("_hashsplit", hashsplit_methods);
 147 }