source file: /home/buildslave/tahoe/edgy/build/src/allmydata/util/base32.py
file stats: 155 lines, 155 executed: 100.0% covered
coverage versus previous test: 0 lines added, 0 lines removed
1. # from the Python Standard Library
2. import string
3.
4. from assertutil import precondition
5.
6. z_base_32_alphabet = "ybndrfg8ejkmcpqxot1uwisza345h769" # Zooko's choice, rationale in "DESIGN" doc
7. rfc3548_alphabet = "abcdefghijklmnopqrstuvwxyz234567" # RFC3548 standard used by Gnutella, Content-Addressable Web, THEX, Bitzi, Web-Calculus...
8. chars = rfc3548_alphabet
9.
10. vals = ''.join(map(chr, range(32)))
11. c2vtranstable = string.maketrans(chars, vals)
12. v2ctranstable = string.maketrans(vals, chars)
13. identitytranstable = string.maketrans('', '')
14.
15. def _get_trailing_chars_without_lsbs(N, d):
16. """
17. @return: a list of chars that can legitimately appear in the last place when the least significant N bits are ignored.
18. """
19. s = []
20. if N < 4:
21. s.extend(_get_trailing_chars_without_lsbs(N+1, d=d))
22. i = 0
23. while i < len(chars):
24. if not d.has_key(i):
25. d[i] = None
26. s.append(chars[i])
27. i = i + 2**N
28. return s
29.
30. def get_trailing_chars_without_lsbs(N):
31. precondition((N >= 0) and (N < 5), "N is required to be > 0 and < len(chars).", N=N)
32. if N == 0:
33. return chars
34. d = {}
35. return ''.join(_get_trailing_chars_without_lsbs(N, d=d))
36.
37. BASE32CHAR = '['+get_trailing_chars_without_lsbs(0)+']'
38. BASE32CHAR_4bits = '['+get_trailing_chars_without_lsbs(1)+']'
39. BASE32CHAR_3bits = '['+get_trailing_chars_without_lsbs(2)+']'
40. BASE32CHAR_2bits = '['+get_trailing_chars_without_lsbs(3)+']'
41. BASE32CHAR_1bits = '['+get_trailing_chars_without_lsbs(4)+']'
42. BASE32STR_1byte = BASE32CHAR+BASE32CHAR_3bits
43. BASE32STR_2bytes = BASE32CHAR+'{3}'+BASE32CHAR_1bits
44. BASE32STR_3bytes = BASE32CHAR+'{4}'+BASE32CHAR_4bits
45. BASE32STR_4bytes = BASE32CHAR+'{6}'+BASE32CHAR_2bits
46. BASE32STR_anybytes = '((?:%s{8})*' % (BASE32CHAR,) + "(?:|%s|%s|%s|%s))" % (BASE32STR_1byte, BASE32STR_2bytes, BASE32STR_3bytes, BASE32STR_4bytes)
47.
48. def b2a(os):
49. """
50. @param os the data to be encoded (a string)
51.
52. @return the contents of os in base-32 encoded form
53. """
54. return b2a_l(os, len(os)*8)
55.
56. def b2a_or_none(os):
57. if os is not None:
58. return b2a(os)
59.
60. def b2a_l(os, lengthinbits):
61. """
62. @param os the data to be encoded (a string)
63. @param lengthinbits the number of bits of data in os to be encoded
64.
65. b2a_l() will generate a base-32 encoded string big enough to encode lengthinbits bits. So for
66. example if os is 2 bytes long and lengthinbits is 15, then b2a_l() will generate a 3-character-
67. long base-32 encoded string (since 3 quintets is sufficient to encode 15 bits). If os is
68. 2 bytes long and lengthinbits is 16 (or None), then b2a_l() will generate a 4-character string.
69. Note that b2a_l() does not mask off unused least-significant bits, so for example if os is
70. 2 bytes long and lengthinbits is 15, then you must ensure that the unused least-significant bit
71. of os is a zero bit or you will get the wrong result. This precondition is tested by assertions
72. if assertions are enabled.
73.
74. Warning: if you generate a base-32 encoded string with b2a_l(), and then someone else tries to
75. decode it by calling a2b() instead of a2b_l(), then they will (probably) get a different
76. string than the one you encoded! So only use b2a_l() when you are sure that the encoding and
77. decoding sides know exactly which lengthinbits to use. If you do not have a way for the
78. encoder and the decoder to agree upon the lengthinbits, then it is best to use b2a() and
79. a2b(). The only drawback to using b2a() over b2a_l() is that when you have a number of
80. bits to encode that is not a multiple of 8, b2a() can sometimes generate a base-32 encoded
81. string that is one or two characters longer than necessary.
82.
83. @return the contents of os in base-32 encoded form
84. """
85. precondition(isinstance(lengthinbits, (int, long,)), "lengthinbits is required to be an integer.", lengthinbits=lengthinbits)
86. precondition((lengthinbits+7)/8 == len(os), "lengthinbits is required to specify a number of bits storable in exactly len(os) octets.", lengthinbits=lengthinbits, lenos=len(os))
87.
88. os = map(ord, os)
89.
90. numquintets = (lengthinbits+4)/5
91. numoctetsofdata = (lengthinbits+7)/8
92. # print "numoctetsofdata: %s, len(os): %s, lengthinbits: %s, numquintets: %s" % (numoctetsofdata, len(os), lengthinbits, numquintets,)
93. # strip trailing octets that won't be used
94. del os[numoctetsofdata:]
95. # zero out any unused bits in the final octet
96. if lengthinbits % 8 != 0:
97. os[-1] = os[-1] >> (8-(lengthinbits % 8))
98. os[-1] = os[-1] << (8-(lengthinbits % 8))
99. # append zero octets for padding if needed
100. numoctetsneeded = (numquintets*5+7)/8 + 1
101. os.extend([0]*(numoctetsneeded-len(os)))
102.
103. quintets = []
104. cutoff = 256
105. num = os[0]
106. i = 0
107. while len(quintets) < numquintets:
108. i = i + 1
109. assert len(os) > i, "len(os): %s, i: %s, len(quintets): %s, numquintets: %s, lengthinbits: %s, numoctetsofdata: %s, numoctetsneeded: %s, os: %s" % (len(os), i, len(quintets), numquintets, lengthinbits, numoctetsofdata, numoctetsneeded, os,)
110. num = num * 256
111. num = num + os[i]
112. if cutoff == 1:
113. cutoff = 256
114. continue
115. cutoff = cutoff * 8
116. quintet = num / cutoff
117. quintets.append(quintet)
118. num = num - (quintet * cutoff)
119.
120. cutoff = cutoff / 32
121. quintet = num / cutoff
122. quintets.append(quintet)
123. num = num - (quintet * cutoff)
124.
125. if len(quintets) > numquintets:
126. assert len(quintets) == (numquintets+1), "len(quintets): %s, numquintets: %s, quintets: %s" % (len(quintets), numquintets, quintets,)
127. quintets = quintets[:numquintets]
128. res = string.translate(string.join(map(chr, quintets), ''), v2ctranstable)
129. assert could_be_base32_encoded_l(res, lengthinbits), "lengthinbits: %s, res: %s" % (lengthinbits, res,)
130. return res
131.
132. # b2a() uses the minimal number of quintets sufficient to encode the binary
133. # input. It just so happens that the relation is like this (everything is
134. # modulo 40 bits).
135. # num_qs = NUM_OS_TO_NUM_QS[num_os]
136. NUM_OS_TO_NUM_QS=(0, 2, 4, 5, 7,)
137.
138. # num_os = NUM_QS_TO_NUM_OS[num_qs], but if not NUM_QS_LEGIT[num_qs] then
139. # there is *no* number of octets which would have resulted in this number of
140. # quintets, so either the encoded string has been mangled (truncated) or else
141. # you were supposed to decode it with a2b_l() (which means you were supposed
142. # to know the actual length of the encoded data).
143.
144. NUM_QS_TO_NUM_OS=(0, 1, 1, 2, 2, 3, 3, 4)
145. NUM_QS_LEGIT=(1, 0, 1, 0, 1, 1, 0, 1,)
146. NUM_QS_TO_NUM_BITS=tuple(map(lambda x: x*8, NUM_QS_TO_NUM_OS))
147.
148. # A fast way to determine whether a given string *could* be base-32 encoded data, assuming that the
149. # original data had 8K bits for a positive integer K.
150. # The boolean value of s8[len(s)%8][ord(s[-1])], where s is the possibly base-32 encoded string
151. # tells whether the final character is reasonable.
152. def add_check_array(cs, sfmap):
153. checka=[0] * 256
154. for c in cs:
155. checka[ord(c)] = 1
156. sfmap.append(tuple(checka))
157.
158. def init_s8():
159. s8 = []
160. add_check_array(chars, s8)
161. for lenmod8 in (1, 2, 3, 4, 5, 6, 7,):
162. if NUM_QS_LEGIT[lenmod8]:
163. add_check_array(get_trailing_chars_without_lsbs(4-(NUM_QS_TO_NUM_BITS[lenmod8]%5)), s8)
164. else:
165. add_check_array('', s8)
166. return tuple(s8)
167. s8 = init_s8()
168.
169. # A somewhat fast way to determine whether a given string *could* be base-32 encoded data, given a
170. # lengthinbits.
171. # The boolean value of s5[lengthinbits%5][ord(s[-1])], where s is the possibly base-32 encoded
172. # string tells whether the final character is reasonable.
173. def init_s5():
174. s5 = []
175. add_check_array(get_trailing_chars_without_lsbs(0), s5)
176. for lenmod5 in [1,2,3,4]:
177. add_check_array(get_trailing_chars_without_lsbs(5-lenmod5), s5)
178. return tuple(s5)
179. s5 = init_s5()
180.
181. def could_be_base32_encoded(s, s8=s8, tr=string.translate, identitytranstable=identitytranstable, chars=chars):
182. precondition(isinstance(s, str), s)
183. if s == '':
184. return True
185. return s8[len(s)%8][ord(s[-1])] and not tr(s, identitytranstable, chars)
186.
187. def could_be_base32_encoded_l(s, lengthinbits, s5=s5, tr=string.translate, identitytranstable=identitytranstable, chars=chars):
188. precondition(isinstance(s, str), s)
189. if s == '':
190. return True
191. assert lengthinbits%5 < len(s5), lengthinbits
192. assert ord(s[-1]) < s5[lengthinbits%5]
193. return (((lengthinbits+4)/5) == len(s)) and s5[lengthinbits%5][ord(s[-1])] and not string.translate(s, identitytranstable, chars)
194.
195. def num_octets_that_encode_to_this_many_quintets(numqs):
196. # Here is a computation that conveniently expresses this:
197. return (numqs*5+3)/8
198.
199. def a2b(cs):
200. """
201. @param cs the base-32 encoded data (a string)
202. """
203. precondition(could_be_base32_encoded(cs), "cs is required to be possibly base32 encoded data.", cs=cs)
204. precondition(isinstance(cs, str), cs)
205.
206. return a2b_l(cs, num_octets_that_encode_to_this_many_quintets(len(cs))*8)
207.
208. def a2b_l(cs, lengthinbits):
209. """
210. @param lengthinbits the number of bits of data in encoded into cs
211.
212. a2b_l() will return a result big enough to hold lengthinbits bits. So for example if cs is
213. 4 characters long (encoding at least 15 and up to 20 bits) and lengthinbits is 16, then a2b_l()
214. will return a string of length 2 (since 2 bytes is sufficient to store 16 bits). If cs is 4
215. characters long and lengthinbits is 20, then a2b_l() will return a string of length 3 (since
216. 3 bytes is sufficient to store 20 bits). Note that b2a_l() does not mask off unused least-
217. significant bits, so for example if cs is 4 characters long and lengthinbits is 17, then you
218. must ensure that all three of the unused least-significant bits of cs are zero bits or you will
219. get the wrong result. This precondition is tested by assertions if assertions are enabled.
220. (Generally you just require the encoder to ensure this consistency property between the least
221. significant zero bits and value of lengthinbits, and reject strings that have a length-in-bits
222. which isn't a multiple of 8 and yet don't have trailing zero bits, as improperly encoded.)
223.
224. Please see the warning in the docstring of b2a_l() regarding the use of b2a() versus b2a_l().
225.
226. @return the data encoded in cs
227. """
228. precondition(could_be_base32_encoded_l(cs, lengthinbits), "cs is required to be possibly base32 encoded data.", cs=cs, lengthinbits=lengthinbits)
229. precondition(isinstance(cs, str), cs)
230. if cs == '':
231. return ''
232.
233. qs = map(ord, string.translate(cs, c2vtranstable))
234.
235. numoctets = (lengthinbits+7)/8
236. numquintetsofdata = (lengthinbits+4)/5
237. # strip trailing quintets that won't be used
238. del qs[numquintetsofdata:]
239. # zero out any unused bits in the final quintet
240. if lengthinbits % 5 != 0:
241. qs[-1] = qs[-1] >> (5-(lengthinbits % 5))
242. qs[-1] = qs[-1] << (5-(lengthinbits % 5))
243. # append zero quintets for padding if needed
244. numquintetsneeded = (numoctets*8+4)/5
245. qs.extend([0]*(numquintetsneeded-len(qs)))
246.
247. octets = []
248. pos = 2048
249. num = qs[0] * pos
250. readybits = 5
251. i = 1
252. while len(octets) < numoctets:
253. while pos > 256:
254. pos = pos / 32
255. num = num + (qs[i] * pos)
256. i = i + 1
257. octet = num / 256
258. octets.append(octet)
259. num = num - (octet * 256)
260. num = num * 256
261. pos = pos * 256
262. assert len(octets) == numoctets, "len(octets): %s, numoctets: %s, octets: %s" % (len(octets), numoctets, octets,)
263. res = ''.join(map(chr, octets))
264. precondition(b2a_l(res, lengthinbits) == cs, "cs is required to be the canonical base-32 encoding of some data.", b2a(res), res=res, cs=cs)
265. return res