#!/usr/bin/python
from __future__ import division
import math
UINT64_MAX = (1 << 64) -1

def OldByteSize(uint64):
  """Returns the bytes required to serialize a single varint.
  uint64 must be unsigned.
  """
  if uint64 > UINT64_MAX:
    raise  ValueError #message.EncodeError('Value out of range: %d' % uint64)
  bytes = 1
  while uint64 > 0x7f:
    bytes += 1
    uint64 >>= 7
  return bytes

def NewByteSize(uint64):
  """Returns the number of bytes required to serialize a single varint
  using boundary value comparisons. (unrolled loop optimization -WPierce)
  uint64 must be unsigned.
  """
  if uint64 < (1<< 7): return 1
  if uint64 < (1<<14): return 2
  if uint64 < (1<<21): return 3
  if uint64 < (1<<28): return 4
  if uint64 < (1<<35): return 5
  if uint64 < (1<<42): return 6
  if uint64 < (1<<49): return 7
  if uint64 < (1<<56): return 8
  if uint64 < (1<<63): return 9
  if uint64 > UINT64_MAX:
    raise ValueError
  return 10


def NewByteSize_LOG(uint64):
  """Returns size in bytes required to serialize a single varint
  using alternate calculation that requires no looping.
  """
  if uint64 > UINT64_MAX:
    raise ValueError
  if uint64 < 1:
    uint64 = 1
  uint64 += 1
  size = math.ceil(math.log(uint64,  2) / 7)
  return size

if __name__ == '__main__':
  import timeit
  repeat=4*1000*1000
  print "Testing speed using %d iterations" % (repeat)

  def compare(val, note=""):
    s1 = OldByteSize(val)
    s2 = NewByteSize(val)
    assert (s1 == s2) # ensure new method agrees with old method
    print "Value %d uses (old:%d == new:%d) bytes to encode" % (val,  s1,  s2), note
    x=timeit.Timer(stmt='s=OldByteSize(%d)' % (val),  setup='from __main__ import OldByteSize').timeit(repeat)
    y=timeit.Timer(stmt='s=NewByteSize(%d)' % (val),  setup='from __main__ import NewByteSize').timeit(repeat)
    print "  Old method takes:", x, "    New method takes:", y, "seconds"
    speedup = x/y
    verdict = "THE SAME"
    if speedup > 1:
      verdict = "FASTER"
    if speedup < 1:
      verdict = "SLOWER"
    print "> New method is %.1fx the old method speed.  New method is %s." % (speedup, verdict)
    print

  # test boundary values for validity coverage
  compare(UINT64_MAX, "(UINT64_MAX)")
  compare(UINT64_MAX-1, "(UINT64_MAX-1)")
  for shift in range(10):
    for offset in (-1, 0, 1):
      i = (1<<(shift*7)) + offset
      compare(i, note="(bit-shift is %d, offset is %d)" % (shift*7, offset))

print "Test done!"