Source: bitArray.js

  1. /** @fileOverview Arrays of bits, encoded as arrays of Numbers.
  2. *
  3. * @author Emily Stark
  4. * @author Mike Hamburg
  5. * @author Dan Boneh
  6. */
  7. /**
  8. * Arrays of bits, encoded as arrays of Numbers.
  9. * @namespace
  10. * @description
  11. * <p>
  12. * These objects are the currency accepted by SJCL's crypto functions.
  13. * </p>
  14. *
  15. * <p>
  16. * Most of our crypto primitives operate on arrays of 4-byte words internally,
  17. * but many of them can take arguments that are not a multiple of 4 bytes.
  18. * This library encodes arrays of bits (whose size need not be a multiple of 8
  19. * bits) as arrays of 32-bit words. The bits are packed, big-endian, into an
  20. * array of words, 32 bits at a time. Since the words are double-precision
  21. * floating point numbers, they fit some extra data. We use this (in a private,
  22. * possibly-changing manner) to encode the number of bits actually present
  23. * in the last word of the array.
  24. * </p>
  25. *
  26. * <p>
  27. * Because bitwise ops clear this out-of-band data, these arrays can be passed
  28. * to ciphers like AES which want arrays of words.
  29. * </p>
  30. */
  31. sjcl.bitArray = {
  32. /**
  33. * Array slices in units of bits.
  34. * @param {bitArray} a The array to slice.
  35. * @param {Number} bstart The offset to the start of the slice, in bits.
  36. * @param {Number} bend The offset to the end of the slice, in bits. If this is undefined,
  37. * slice until the end of the array.
  38. * @return {bitArray} The requested slice.
  39. */
  40. bitSlice: function (a, bstart, bend) {
  41. a = sjcl.bitArray._shiftRight(a.slice(bstart/32), 32 - (bstart & 31)).slice(1);
  42. return (bend === undefined) ? a : sjcl.bitArray.clamp(a, bend-bstart);
  43. },
  44. /**
  45. * Extract a number packed into a bit array.
  46. * @param {bitArray} a The array to slice.
  47. * @param {Number} bstart The offset to the start of the slice, in bits.
  48. * @param {Number} blength The length of the number to extract.
  49. * @return {Number} The requested slice.
  50. */
  51. extract: function(a, bstart, blength) {
  52. // FIXME: this Math.floor is not necessary at all, but for some reason
  53. // seems to suppress a bug in the Chromium JIT.
  54. var x, sh = Math.floor((-bstart-blength) & 31);
  55. if ((bstart + blength - 1 ^ bstart) & -32) {
  56. // it crosses a boundary
  57. x = (a[bstart/32|0] << (32 - sh)) ^ (a[bstart/32+1|0] >>> sh);
  58. } else {
  59. // within a single word
  60. x = a[bstart/32|0] >>> sh;
  61. }
  62. return x & ((1<<blength) - 1);
  63. },
  64. /**
  65. * Concatenate two bit arrays.
  66. * @param {bitArray} a1 The first array.
  67. * @param {bitArray} a2 The second array.
  68. * @return {bitArray} The concatenation of a1 and a2.
  69. */
  70. concat: function (a1, a2) {
  71. if (a1.length === 0 || a2.length === 0) {
  72. return a1.concat(a2);
  73. }
  74. var last = a1[a1.length-1], shift = sjcl.bitArray.getPartial(last);
  75. if (shift === 32) {
  76. return a1.concat(a2);
  77. } else {
  78. return sjcl.bitArray._shiftRight(a2, shift, last|0, a1.slice(0,a1.length-1));
  79. }
  80. },
  81. /**
  82. * Find the length of an array of bits.
  83. * @param {bitArray} a The array.
  84. * @return {Number} The length of a, in bits.
  85. */
  86. bitLength: function (a) {
  87. var l = a.length, x;
  88. if (l === 0) { return 0; }
  89. x = a[l - 1];
  90. return (l-1) * 32 + sjcl.bitArray.getPartial(x);
  91. },
  92. /**
  93. * Truncate an array.
  94. * @param {bitArray} a The array.
  95. * @param {Number} len The length to truncate to, in bits.
  96. * @return {bitArray} A new array, truncated to len bits.
  97. */
  98. clamp: function (a, len) {
  99. if (a.length * 32 < len) { return a; }
  100. a = a.slice(0, Math.ceil(len / 32));
  101. var l = a.length;
  102. len = len & 31;
  103. if (l > 0 && len) {
  104. a[l-1] = sjcl.bitArray.partial(len, a[l-1] & 0x80000000 >> (len-1), 1);
  105. }
  106. return a;
  107. },
  108. /**
  109. * Make a partial word for a bit array.
  110. * @param {Number} len The number of bits in the word.
  111. * @param {Number} x The bits.
  112. * @param {Number} [_end=0] Pass 1 if x has already been shifted to the high side.
  113. * @return {Number} The partial word.
  114. */
  115. partial: function (len, x, _end) {
  116. if (len === 32) { return x; }
  117. return (_end ? x|0 : x << (32-len)) + len * 0x10000000000;
  118. },
  119. /**
  120. * Get the number of bits used by a partial word.
  121. * @param {Number} x The partial word.
  122. * @return {Number} The number of bits used by the partial word.
  123. */
  124. getPartial: function (x) {
  125. return Math.round(x/0x10000000000) || 32;
  126. },
  127. /**
  128. * Compare two arrays for equality in a predictable amount of time.
  129. * @param {bitArray} a The first array.
  130. * @param {bitArray} b The second array.
  131. * @return {boolean} true if a == b; false otherwise.
  132. */
  133. equal: function (a, b) {
  134. if (sjcl.bitArray.bitLength(a) !== sjcl.bitArray.bitLength(b)) {
  135. return false;
  136. }
  137. var x = 0, i;
  138. for (i=0; i<a.length; i++) {
  139. x |= a[i]^b[i];
  140. }
  141. return (x === 0);
  142. },
  143. /** Shift an array right.
  144. * @param {bitArray} a The array to shift.
  145. * @param {Number} shift The number of bits to shift.
  146. * @param {Number} [carry=0] A byte to carry in
  147. * @param {bitArray} [out=[]] An array to prepend to the output.
  148. * @private
  149. */
  150. _shiftRight: function (a, shift, carry, out) {
  151. var i, last2=0, shift2;
  152. if (out === undefined) { out = []; }
  153. for (; shift >= 32; shift -= 32) {
  154. out.push(carry);
  155. carry = 0;
  156. }
  157. if (shift === 0) {
  158. return out.concat(a);
  159. }
  160. for (i=0; i<a.length; i++) {
  161. out.push(carry | a[i]>>>shift);
  162. carry = a[i] << (32-shift);
  163. }
  164. last2 = a.length ? a[a.length-1] : 0;
  165. shift2 = sjcl.bitArray.getPartial(last2);
  166. out.push(sjcl.bitArray.partial(shift+shift2 & 31, (shift + shift2 > 32) ? carry : out.pop(),1));
  167. return out;
  168. },
  169. /** xor a block of 4 words together.
  170. * @private
  171. */
  172. _xor4: function(x,y) {
  173. return [x[0]^y[0],x[1]^y[1],x[2]^y[2],x[3]^y[3]];
  174. },
  175. /** byteswap a word array inplace.
  176. * (does not handle partial words)
  177. * @param {sjcl.bitArray} a word array
  178. * @return {sjcl.bitArray} byteswapped array
  179. */
  180. byteswapM: function(a) {
  181. var i, v, m = 0xff00;
  182. for (i = 0; i < a.length; ++i) {
  183. v = a[i];
  184. a[i] = (v >>> 24) | ((v >>> 8) & m) | ((v & m) << 8) | (v << 24);
  185. }
  186. return a;
  187. }
  188. };