src/allmydata/util/base62.py

   1 #!/usr/bin/env python
   2
   3 # Copyright (c) 2002-2009 Zooko Wilcox-O'Hearn
   4 # mailto:zooko@zooko.com
   5 # Permission is hereby granted to any person obtaining a copy of this work to
   6 # deal in this work without restriction (including the rights to use, modify,
   7 # distribute, sublicense, and/or sell copies).
   8
   9 # from the Python Standard Library
  10 import string
  11
  12 from allmydata.util.mathutil import log_ceil, log_floor
  13
  14 chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  15
  16 BASE62CHAR = '[' + chars + ']'
  17
  18 vals = ''.join([chr(i) for i in range(62)])
  19 c2vtranstable = string.maketrans(chars, vals)
  20 v2ctranstable = string.maketrans(vals, chars)
  21 identitytranstable = string.maketrans(chars, chars)
  22
  23 def b2a(os):
  24     """
  25     @param os the data to be encoded (a string)
  26
  27     @return the contents of os in base-62 encoded form
  28     """
  29     cs = b2a_l(os, len(os)*8)
  30     assert num_octets_that_encode_to_this_many_chars(len(cs)) == len(os), "%s != %s, numchars: %s" % (num_octets_that_encode_to_this_many_chars(len(cs)), len(os), len(cs))
  31     return cs
  32
  33 def b2a_l(os, lengthinbits):
  34     """
  35     @param os the data to be encoded (a string)
  36     @param lengthinbits the number of bits of data in os to be encoded
  37
  38     b2a_l() will generate a base-62 encoded string big enough to encode
  39     lengthinbits bits.  So for example if os is 3 bytes long and lengthinbits is
  40     17, then b2a_l() will generate a 3-character- long base-62 encoded string
  41     (since 3 chars is sufficient to encode more than 2^17 values).  If os is 3
  42     bytes long and lengthinbits is 18 (or None), then b2a_l() will generate a
  43     4-character string (since 4 chars are required to hold 2^18 values).  Note
  44     that if os is 3 bytes long and lengthinbits is 17, the least significant 7
  45     bits of os are ignored.
  46
  47     Warning: if you generate a base-62 encoded string with b2a_l(), and then someone else tries to
  48     decode it by calling a2b() instead of  a2b_l(), then they will (potentially) get a different
  49     string than the one you encoded!  So use b2a_l() only when you are sure that the encoding and
  50     decoding sides know exactly which lengthinbits to use.  If you do not have a way for the
  51     encoder and the decoder to agree upon the lengthinbits, then it is best to use b2a() and
  52     a2b().  The only drawback to using b2a() over b2a_l() is that when you have a number of
  53     bits to encode that is not a multiple of 8, b2a() can sometimes generate a base-62 encoded
  54     string that is one or two characters longer than necessary.
  55
  56     @return the contents of os in base-62 encoded form
  57     """
  58     os = [ord(o) for o in reversed(os)] # treat os as big-endian -- and we want to process the least-significant o first
  59
  60     value = 0
  61     numvalues = 1 # the number of possible values that value could be
  62     for o in os:
  63         o *= numvalues
  64         value += o
  65         numvalues *= 256
  66
  67     chars = []
  68     while numvalues > 0:
  69         chars.append(value % 62)
  70         value //= 62
  71         numvalues //= 62
  72
  73     return string.translate(''.join([chr(c) for c in reversed(chars)]), v2ctranstable) # make it big-endian
  74
  75 def num_octets_that_encode_to_this_many_chars(numcs):
  76     return log_floor(62**numcs, 256)
  77
  78 def num_chars_that_this_many_octets_encode_to(numos):
  79     return log_ceil(256**numos, 62)
  80
  81 def a2b(cs):
  82     """
  83     @param cs the base-62 encoded data (a string)
  84     """
  85     return a2b_l(cs, num_octets_that_encode_to_this_many_chars(len(cs))*8)
  86
  87 def a2b_l(cs, lengthinbits):
  88     """
  89     @param lengthinbits the number of bits of data in encoded into cs
  90
  91     a2b_l() will return a result just big enough to hold lengthinbits bits.  So
  92     for example if cs is 2 characters long (encoding between 5 and 12 bits worth
  93     of data) and lengthinbits is 8, then a2b_l() will return a string of length
  94     1 (since 1 byte is sufficient to store 8 bits), but if lengthinbits is 9,
  95     then a2b_l() will return a string of length 2.
  96
  97     Please see the warning in the docstring of b2a_l() regarding the use of
  98     b2a() versus b2a_l().
  99
 100     @return the data encoded in cs
 101     """
 102     cs = [ord(c) for c in reversed(string.translate(cs, c2vtranstable))] # treat cs as big-endian -- and we want to process the least-significant c first
 103
 104     value = 0
 105     numvalues = 1 # the number of possible values that value could be
 106     for c in cs:
 107         c *= numvalues
 108         value += c
 109         numvalues *= 62
 110
 111     numvalues = 2**lengthinbits
 112     bytes = []
 113     while numvalues > 1:
 114         bytes.append(value % 256)
 115         value //= 256
 116         numvalues //= 256
 117
 118     return ''.join([chr(b) for b in reversed(bytes)]) # make it big-endian