common.py 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
  1. # -*- coding: utf-8 -*-
  2. #
  3. # Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
  4. #
  5. # Licensed under the Apache License, Version 2.0 (the "License");
  6. # you may not use this file except in compliance with the License.
  7. # You may obtain a copy of the License at
  8. #
  9. # https://www.apache.org/licenses/LICENSE-2.0
  10. #
  11. # Unless required by applicable law or agreed to in writing, software
  12. # distributed under the License is distributed on an "AS IS" BASIS,
  13. # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. # See the License for the specific language governing permissions and
  15. # limitations under the License.
  16. """Common functionality shared by several modules."""
  17. def bit_size(num):
  18. """
  19. Number of bits needed to represent a integer excluding any prefix
  20. 0 bits.
  21. As per definition from https://wiki.python.org/moin/BitManipulation and
  22. to match the behavior of the Python 3 API.
  23. Usage::
  24. >>> bit_size(1023)
  25. 10
  26. >>> bit_size(1024)
  27. 11
  28. >>> bit_size(1025)
  29. 11
  30. :param num:
  31. Integer value. If num is 0, returns 0. Only the absolute value of the
  32. number is considered. Therefore, signed integers will be abs(num)
  33. before the number's bit length is determined.
  34. :returns:
  35. Returns the number of bits in the integer.
  36. """
  37. if num == 0:
  38. return 0
  39. if num < 0:
  40. num = -num
  41. # Make sure this is an int and not a float.
  42. num & 1
  43. hex_num = "%x" % num
  44. return ((len(hex_num) - 1) * 4) + {
  45. '0': 0, '1': 1, '2': 2, '3': 2,
  46. '4': 3, '5': 3, '6': 3, '7': 3,
  47. '8': 4, '9': 4, 'a': 4, 'b': 4,
  48. 'c': 4, 'd': 4, 'e': 4, 'f': 4,
  49. }[hex_num[0]]
  50. def _bit_size(number):
  51. """
  52. Returns the number of bits required to hold a specific long number.
  53. """
  54. if number < 0:
  55. raise ValueError('Only nonnegative numbers possible: %s' % number)
  56. if number == 0:
  57. return 0
  58. # This works, even with very large numbers. When using math.log(number, 2),
  59. # you'll get rounding errors and it'll fail.
  60. bits = 0
  61. while number:
  62. bits += 1
  63. number >>= 1
  64. return bits
  65. def byte_size(number):
  66. """
  67. Returns the number of bytes required to hold a specific long number.
  68. The number of bytes is rounded up.
  69. Usage::
  70. >>> byte_size(1 << 1023)
  71. 128
  72. >>> byte_size((1 << 1024) - 1)
  73. 128
  74. >>> byte_size(1 << 1024)
  75. 129
  76. :param number:
  77. An unsigned integer
  78. :returns:
  79. The number of bytes required to hold a specific long number.
  80. """
  81. quanta, mod = divmod(bit_size(number), 8)
  82. if mod or number == 0:
  83. quanta += 1
  84. return quanta
  85. # return int(math.ceil(bit_size(number) / 8.0))
  86. def extended_gcd(a, b):
  87. """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
  88. """
  89. # r = gcd(a,b) i = multiplicitive inverse of a mod b
  90. # or j = multiplicitive inverse of b mod a
  91. # Neg return values for i or j are made positive mod b or a respectively
  92. # Iterateive Version is faster and uses much less stack space
  93. x = 0
  94. y = 1
  95. lx = 1
  96. ly = 0
  97. oa = a # Remember original a/b to remove
  98. ob = b # negative values from return results
  99. while b != 0:
  100. q = a // b
  101. (a, b) = (b, a % b)
  102. (x, lx) = ((lx - (q * x)), x)
  103. (y, ly) = ((ly - (q * y)), y)
  104. if lx < 0:
  105. lx += ob # If neg wrap modulo orignal b
  106. if ly < 0:
  107. ly += oa # If neg wrap modulo orignal a
  108. return a, lx, ly # Return only positive values
  109. def inverse(x, n):
  110. """Returns x^-1 (mod n)
  111. >>> inverse(7, 4)
  112. 3
  113. >>> (inverse(143, 4) * 143) % 4
  114. 1
  115. """
  116. (divider, inv, _) = extended_gcd(x, n)
  117. if divider != 1:
  118. raise ValueError("x (%d) and n (%d) are not relatively prime" % (x, n))
  119. return inv
  120. def crt(a_values, modulo_values):
  121. """Chinese Remainder Theorem.
  122. Calculates x such that x = a[i] (mod m[i]) for each i.
  123. :param a_values: the a-values of the above equation
  124. :param modulo_values: the m-values of the above equation
  125. :returns: x such that x = a[i] (mod m[i]) for each i
  126. >>> crt([2, 3], [3, 5])
  127. 8
  128. >>> crt([2, 3, 2], [3, 5, 7])
  129. 23
  130. >>> crt([2, 3, 0], [7, 11, 15])
  131. 135
  132. """
  133. m = 1
  134. x = 0
  135. for modulo in modulo_values:
  136. m *= modulo
  137. for (m_i, a_i) in zip(modulo_values, a_values):
  138. M_i = m // m_i
  139. inv = inverse(M_i, m_i)
  140. x = (x + a_i * M_i * inv) % m
  141. return x
  142. if __name__ == '__main__':
  143. import doctest
  144. doctest.testmod()