cmd/margin-cmd.py

   1 #!/usr/bin/env python
   2 import sys, struct, math
   3 from bup import options, git, _helpers
   4 from bup.helpers import *
   5
   6 POPULATION_OF_EARTH=6.7e9  # as of September, 2010
   7
   8 optspec = """
   9 bup margin
  10 --
  11 predict    Guess object offsets and report the maximum deviation
  12 ignore-midx  Don't use midx files; use only plain pack idx files.
  13 """
  14 o = options.Options(optspec)
  15 (opt, flags, extra) = o.parse(sys.argv[1:])
  16
  17 if extra:
  18     o.fatal("no arguments expected")
  19
  20 git.check_repo_or_die()
  21 git.ignore_midx = opt.ignore_midx
  22
  23 mi = git.PackIdxList(git.repo('objects/pack'))
  24
  25 def do_predict(ix):
  26     total = len(ix)
  27     maxdiff = 0
  28     for count,i in enumerate(ix):
  29         prefix = struct.unpack('!Q', i[:8])[0]
  30         expected = prefix * total / (1<<64)
  31         diff = count - expected
  32         maxdiff = max(maxdiff, abs(diff))
  33     print '%d of %d (%.3f%%) ' % (maxdiff, len(ix), maxdiff*100.0/len(ix))
  34     sys.stdout.flush()
  35     assert(count+1 == len(ix))
  36
  37 if opt.predict:
  38     if opt.ignore_midx:
  39         for pack in mi.packs:
  40             do_predict(pack)
  41     else:
  42         do_predict(mi)
  43 else:
  44     # default mode: find longest matching prefix
  45     last = '\0'*20
  46     longmatch = 0
  47     for i in mi:
  48         if i == last:
  49             continue
  50         #assert(str(i) >= last)
  51         pm = _helpers.bitmatch(last, i)
  52         longmatch = max(longmatch, pm)
  53         last = i
  54     print longmatch
  55     log('%d matching prefix bits\n' % longmatch)
  56     doublings = math.log(len(mi), 2)
  57     bpd = longmatch / doublings
  58     log('%.2f bits per doubling\n' % bpd)
  59     remain = 160 - longmatch
  60     rdoublings = remain / bpd
  61     log('%d bits (%.2f doublings) remaining\n' % (remain, rdoublings))
  62     larger = 2**rdoublings
  63     log('%g times larger is possible\n' % larger)
  64     perperson = larger/POPULATION_OF_EARTH
  65     log('\nEveryone on earth could have %d data sets like yours, all in one\n'
  66         'repository, and we would expect 1 object collision.\n'
  67         % int(perperson))