hashsplit.py

   1 #!/usr/bin/env python
   2 import sys, subprocess
   3
   4 BLOBBITS = 14
   5 BLOBSIZE = 1 << (BLOBBITS-1)
   6 WINDOWBITS = 7
   7 WINDOWSIZE = 1 << (WINDOWBITS-1)
   8
   9 # FIXME: replace this with a not-stupid rolling checksum algorithm,
  10 # such as the one used in rsync (Adler32?)
  11 def stupidsum_add(old, drop, add):
  12     return (((old<<1) | ((old>>31)&0xffffffff)) & 0xffffffff) ^ drop ^ add
  13
  14
  15 def test_sums():
  16     sum = 0
  17     for i in range(WINDOWSIZE):
  18         sum = stupidsum_add(sum, 0, i%256)
  19     sum1 = sum
  20     for i in range(WINDOWSIZE*5):
  21         sum = stupidsum_add(sum, i%256, i%256)
  22     assert(sum == sum1)
  23     for i in range(WINDOWSIZE):
  24         sum = stupidsum_add(sum, i%256, 0)
  25     assert(sum == 0)
  26
  27
  28 class Buf:
  29     def __init__(self):
  30         self.list = []
  31         self.total = 0
  32
  33     def put(self, s):
  34         if s:
  35             self.list.append(s)
  36             self.total += len(s)
  37
  38     def get(self, count):
  39         count = count
  40         out = []
  41         while count > 0 and self.list:
  42             n = len(self.list[0])
  43             if count >= n:
  44                 out.append(self.list[0])
  45                 self.list = self.list[1:]
  46             else:
  47                 n = count
  48                 out.append(self.list[0][:n])
  49                 self.list[0] = self.list[0][n:]
  50             count -= n
  51             self.total -= n
  52         return ''.join(out)
  53
  54     def used(self):
  55         return self.total
  56
  57
  58 def splitbuf(buf):
  59     #return buf.get(BLOBSIZE)
  60     window = [0] * WINDOWSIZE
  61     sum = 0
  62     i = 0
  63     count = 0
  64     for ent in buf.list:
  65         for c in ent:
  66             count += 1
  67             b = ord(c)
  68             sum = stupidsum_add(sum, window[i], b)
  69             window[i] = b
  70             i = (i + 1) % WINDOWSIZE
  71             if (sum & (BLOBSIZE-1)) == ((~0) & (BLOBSIZE-1)):
  72                 return buf.get(count)
  73     return None
  74
  75
  76 def save_blob(blob):
  77     pipe = subprocess.Popen(['git', 'hash-object', '--stdin', '-w'],
  78                             stdin=subprocess.PIPE)
  79     pipe.stdin.write(blob)
  80     pipe.stdin.close()
  81     pipe.wait()
  82     pipe = None
  83
  84
  85 def do_main():
  86     ofs = 0
  87     buf = Buf()
  88     blob = 1
  89
  90     eof = 0
  91     while blob or not eof:
  92         if not eof and (buf.used() < BLOBSIZE*2 or not blob):
  93             bnew = sys.stdin.read(BLOBSIZE*4)
  94             if not len(bnew): eof = 1
  95             # print 'got %d, total %d' % (len(bnew), buf.used())
  96             buf.put(bnew)
  97
  98         blob = splitbuf(buf)
  99         if not blob and not eof:
 100             continue
 101         if eof and not blob:
 102             blob = buf.get(buf.used())
 103
 104         if blob:
 105             ofs += len(blob)
 106             sys.stderr.write('SPLIT @ %-8d size=%-8d (%d/%d)\n'
 107                              % (ofs, len(blob), BLOBSIZE, WINDOWSIZE))
 108             save_blob(blob)
 109
 110 assert(WINDOWSIZE >= 32)
 111 assert(BLOBSIZE >= 32)
 112 test_sums()
 113 do_main()