lib/bup/cmd/margin.py

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