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