_hashsplit.c

   1 #include <Python.h>
   2 #include <assert.h>
   3 #include <stdint.h>
   4
   5 #define BLOBBITS (14)
   6 #define BLOBSIZE (1<<(BLOBBITS-1))
   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)
  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             return count+1;
  33     }
  34     return 0;
  35 }
  36
  37
  38 static PyObject *splitbuf(PyObject *self, PyObject *args)
  39 {
  40     unsigned char *buf = NULL;
  41     int len = 0, out = 0;
  42
  43     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
  44         return NULL;
  45     out = find_ofs(buf, len);
  46     //return Py_BuildValue("i", len);//len>BLOBSIZE ? BLOBSIZE : len);
  47     return Py_BuildValue("i", out);
  48 }
  49
  50
  51 static PyObject *bitmatch(PyObject *self, PyObject *args)
  52 {
  53     unsigned char *buf1 = NULL, *buf2 = NULL;
  54     int len1 = 0, len2 = 0;
  55     int byte, bit;
  56
  57     if (!PyArg_ParseTuple(args, "t#t#", &buf1, &len1, &buf2, &len2))
  58         return NULL;
  59
  60     bit = 0;
  61     for (byte = 0; byte < len1 && byte < len2; byte++)
  62     {
  63         int b1 = buf1[byte], b2 = buf2[byte];
  64         if (b1 != b2)
  65         {
  66             for (bit = 0; bit < 8; bit++)
  67                 if ( (b1 & (0x80 >> bit)) != (b2 & (0x80 >> bit)) )
  68                     break;
  69             break;
  70         }
  71     }
  72
  73     return Py_BuildValue("i", byte*8 + bit);
  74 }
  75
  76
  77 static PyMethodDef hashsplit_methods[] = {
  78     { "splitbuf", splitbuf, METH_VARARGS,
  79         "Split a list of strings based on a rolling checksum." },
  80     { "bitmatch", bitmatch, METH_VARARGS,
  81         "Count the number of matching prefix bits between two strings." },
  82     { NULL, NULL, 0, NULL },  // sentinel
  83 };
  84
  85 PyMODINIT_FUNC init_hashsplit(void)
  86 {
  87     Py_InitModule("_hashsplit", hashsplit_methods);
  88 }