cmd/margin-cmd.py

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