hashsplitmodule.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 PyObject *splitbuf(PyObject *self, PyObject *args)
  20 {
  21     char *buf = NULL;
  22     int len = 0, count;
  23
  24     if (!PyArg_ParseTuple(args, "et#", "utf-8", &buf, &len))
  25         return NULL;
  26
  27     {
  28         unsigned char window[WINDOWSIZE];
  29         uint32_t sum = 0;
  30         int i = 0;
  31         memset(window, 0, sizeof(window));
  32
  33         for (count = 0; count < len; count++)
  34         {
  35             sum = stupidsum_add(sum, window[i], buf[count]);
  36             window[i] = buf[count];
  37             i = (i + 1) % WINDOWSIZE;
  38             if ((sum & (BLOBSIZE-1)) == ((~0) & (BLOBSIZE-1)))
  39                 goto done;
  40         }
  41     }
  42
  43     count = -1;
  44 done:
  45     PyMem_Free(buf);
  46     return Py_BuildValue("i", count+1);
  47 }
  48
  49
  50 static PyMethodDef hashsplit_methods[] = {
  51     { "splitbuf", splitbuf, METH_VARARGS,
  52         "Split a list of strings based on a rolling checksum." },
  53     { NULL, NULL, 0, NULL },  // sentinel
  54 };
  55
  56 PyMODINIT_FUNC inithashsplit()
  57 {
  58     Py_InitModule("hashsplit", hashsplit_methods);
  59 }