hashsplit.py

   1 #!/usr/bin/env python
   2 import sys, os, subprocess, errno, zlib
   3 from sha import sha
   4
   5 BLOBBITS = 14
   6 BLOBSIZE = 1 << (BLOBBITS-1)
   7 WINDOWBITS = 7
   8 WINDOWSIZE = 1 << (WINDOWBITS-1)
   9
  10
  11 def log(s):
  12     sys.stderr.write('%s\n' % s)
  13
  14
  15 # FIXME: replace this with a not-stupid rolling checksum algorithm,
  16 # such as the one used in rsync (Adler32?)
  17 def stupidsum_add(old, drop, add):
  18     return (((old<<1) | ((old>>31)&0xffffffff)) & 0xffffffff) ^ drop ^ add
  19
  20
  21 def test_sums():
  22     sum = 0
  23     for i in range(WINDOWSIZE):
  24         sum = stupidsum_add(sum, 0, i%256)
  25     sum1 = sum
  26     for i in range(WINDOWSIZE*5):
  27         sum = stupidsum_add(sum, i%256, i%256)
  28     assert(sum == sum1)
  29     for i in range(WINDOWSIZE):
  30         sum = stupidsum_add(sum, i%256, 0)
  31     assert(sum == 0)
  32
  33
  34 class Buf:
  35     def __init__(self):
  36         self.list = []
  37         self.total = 0
  38
  39     def put(self, s):
  40         if s:
  41             self.list.append(s)
  42             self.total += len(s)
  43
  44     def get(self, count):
  45         count = count
  46         out = []
  47         while count > 0 and self.list:
  48             n = len(self.list[0])
  49             if count >= n:
  50                 out.append(self.list[0])
  51                 self.list = self.list[1:]
  52             else:
  53                 n = count
  54                 out.append(self.list[0][:n])
  55                 self.list[0] = self.list[0][n:]
  56             count -= n
  57             self.total -= n
  58         return ''.join(out)
  59
  60     def used(self):
  61         return self.total
  62
  63
  64 def splitbuf(buf):
  65     #return buf.get(BLOBSIZE)
  66     window = [0] * WINDOWSIZE
  67     sum = 0
  68     i = 0
  69     count = 0
  70     for ent in buf.list:
  71         for c in ent:
  72             count += 1
  73             b = ord(c)
  74             sum = stupidsum_add(sum, window[i], b)
  75             window[i] = b
  76             i = (i + 1) % WINDOWSIZE
  77             if (sum & (BLOBSIZE-1)) == ((~0) & (BLOBSIZE-1)):
  78                 return buf.get(count)
  79     return None
  80
  81
  82 def save_blob(blob):
  83     header = 'blob %d\0' % len(blob)
  84     sum = sha(header)
  85     sum.update(blob)
  86     hex = sum.hexdigest()
  87     dir = '.git/objects/%s' % hex[0:2]
  88     fn = '%s/%s' % (dir, hex[2:])
  89     try:
  90         os.makedirs(dir)
  91     except OSError, e:
  92         if e.errno != errno.EEXIST:
  93             raise
  94     if not os.path.exists(fn):
  95         #log('creating %s' % fn)
  96         tfn = '%s.%d' % (fn, os.getpid())
  97         f = open(tfn, 'w')
  98         z = zlib.compressobj(1)
  99         f.write(z.compress(header))
 100         f.write(z.compress(blob))
 101         f.write(z.flush())
 102         f.close()
 103         os.rename(tfn, fn)
 104     else:
 105         #log('exists %s' % fn)
 106         pass
 107     print hex
 108     return hex
 109
 110
 111 def do_main():
 112     ofs = 0
 113     buf = Buf()
 114     blob = 1
 115
 116     eof = 0
 117     lv = 0
 118     while blob or not eof:
 119         if not eof and (buf.used() < BLOBSIZE*2 or not blob):
 120             bnew = sys.stdin.read(BLOBSIZE*4)
 121             if not len(bnew): eof = 1
 122             #log('got %d, total %d' % (len(bnew), buf.used()))
 123             buf.put(bnew)
 124
 125         blob = splitbuf(buf)
 126         if eof and not blob:
 127             blob = buf.get(buf.used())
 128         if not blob and buf.used() >= BLOBSIZE*8:
 129             blob = buf.get(BLOBSIZE*4)  # limit max blob size
 130         if not blob and not eof:
 131             continue
 132
 133         if blob:
 134             ofs += len(blob)
 135             #log('SPLIT @ %-8d size=%-8d (%d/%d)'
 136             #    % (ofs, len(blob), BLOBSIZE, WINDOWSIZE))
 137             save_blob(blob)
 138
 139         nv = (ofs + buf.used())/1000000
 140         if nv != lv:
 141             log(nv)
 142             lv = nv
 143
 144
 145 assert(WINDOWSIZE >= 32)
 146 assert(BLOBSIZE >= 32)
 147 test_sums()
 148 do_main()