hashsplit.c

   1 #include <stdio.h>
   2 #include <stdint.h>
   3 #include <assert.h>
   4 #include <memory.h>
   5
   6 #define BLOBBITS (14)
   7 #define BLOBSIZE (1<<(BLOBBITS-1))
   8 #define WINDOWBITS (7)
   9 #define WINDOWSIZE (1<<(WINDOWBITS-1))
  10
  11
  12 // FIXME: replace this with a not-stupid rolling checksum algorithm,
  13 // such as the one used in rsync (Adler32?)
  14 static uint32_t stupidsum_add(uint32_t old, uint8_t drop, uint8_t add)
  15 {
  16     return ((old<<1) | (old>>31)) ^ drop ^ add;
  17 }
  18
  19
  20 static void test_sums()
  21 {
  22     uint32_t sum = 0;
  23     int i;
  24
  25     for (i = 0; i < WINDOWSIZE; i++)
  26         sum = stupidsum_add(sum, 0, i%256);
  27     uint32_t sum1 = sum;
  28
  29     for (i = 0; i < WINDOWSIZE*2; i++)
  30         sum = stupidsum_add(sum, i%256, i%256);
  31     assert(sum1 == sum);
  32
  33     for (i = 0; i < WINDOWSIZE; i++)
  34         sum = stupidsum_add(sum, i%256, 0);
  35     assert(sum == 0);
  36 }
  37
  38
  39 int main()
  40 {
  41     assert(WINDOWSIZE >= 32);
  42     assert(BLOBSIZE >= 32);
  43     test_sums();
  44
  45     uint8_t buf[WINDOWSIZE];
  46     uint32_t sum = 0;
  47     int i = 0, count = 0, last_count = 0, c;
  48     FILE *pipe = NULL;
  49
  50     memset(buf, 0, sizeof(buf));
  51
  52     // FIXME: read more than one byte at a time.  This is absurdly slow.
  53     while ((c = fgetc(stdin)) != EOF)
  54     {
  55         sum = stupidsum_add(sum, buf[i], c);
  56         buf[i] = c;
  57
  58         if (0)
  59         {
  60             int j;
  61             fprintf(stderr, "[%5X] %08X  '", i, sum);
  62             for (j = i+1; j < i+1+WINDOWSIZE; j++)
  63             {
  64                 int d = buf[j % WINDOWSIZE];
  65                 fputc((d >= 32 && d <= 126) ? d : '.', stderr);
  66             }
  67             fprintf(stderr, "'\n");
  68         }
  69
  70         i = (i + 1) % WINDOWSIZE;
  71         count++;
  72
  73         if (!pipe)
  74             pipe = popen("git hash-object --stdin -w", "w");
  75
  76         // FIXME: write more than one byte at a time.  This is absurdly
  77         // slow.
  78         fputc(c, pipe);
  79
  80         if ((sum & (BLOBSIZE-1)) == ((~0) & (BLOBSIZE-1)))
  81         {
  82             fprintf(stderr, "SPLIT @ %-8d size=%-8d (%d/%d)\n",
  83                     count, count - last_count, BLOBSIZE, WINDOWSIZE);
  84             last_count = count;
  85             i = 0;
  86             memset(buf, 0, sizeof(buf));
  87             sum = 0;
  88             if (pipe)
  89             {
  90                 fflush(stderr);
  91                 pclose(pipe);
  92                 pipe = NULL;
  93             }
  94         }
  95     }
  96
  97     if (pipe)
  98         pclose(pipe);
  99
 100     return 0;
 101 }