bits.js 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145
  1. // Copyright 2012 The Obvious Corporation.
  2. /*
  3. * bits: Bitwise buffer utilities. The utilities here treat a buffer
  4. * as a little-endian bigint, so the lowest-order bit is bit #0 of
  5. * `buffer[0]`, and the highest-order bit is bit #7 of
  6. * `buffer[buffer.length - 1]`.
  7. */
  8. /*
  9. * Modules used
  10. */
  11. "use strict";
  12. /*
  13. * Exported bindings
  14. */
  15. /**
  16. * Extracts the given number of bits from the buffer at the indicated
  17. * index, returning a simple number as the result. If bits are requested
  18. * that aren't covered by the buffer, the `defaultBit` is used as their
  19. * value.
  20. *
  21. * The `bitLength` must be no more than 32. The `defaultBit` if not
  22. * specified is taken to be `0`.
  23. */
  24. export function extract(buffer, bitIndex, bitLength, defaultBit) {
  25. if (bitLength < 0 || bitLength > 32) {
  26. throw new Error("Bad value for bitLength.");
  27. }
  28. if (defaultBit === undefined) {
  29. defaultBit = 0;
  30. } else if (defaultBit !== 0 && defaultBit !== 1) {
  31. throw new Error("Bad value for defaultBit.");
  32. }
  33. var defaultByte = defaultBit * 0xff;
  34. var result = 0; // All starts are inclusive. The {endByte, endBit} pair is exclusive, but
  35. // if endBit !== 0, then endByte is inclusive.
  36. var lastBit = bitIndex + bitLength;
  37. var startByte = Math.floor(bitIndex / 8);
  38. var startBit = bitIndex % 8;
  39. var endByte = Math.floor(lastBit / 8);
  40. var endBit = lastBit % 8;
  41. if (endBit !== 0) {
  42. // `(1 << endBit) - 1` is the mask of all bits up to but not including
  43. // the endBit.
  44. result = get(endByte) & (1 << endBit) - 1;
  45. }
  46. while (endByte > startByte) {
  47. endByte--;
  48. result = result << 8 | get(endByte);
  49. }
  50. result >>>= startBit;
  51. return result;
  52. function get(index) {
  53. var result = buffer[index];
  54. return result === undefined ? defaultByte : result;
  55. }
  56. }
  57. /**
  58. * Injects the given bits into the given buffer at the given index. Any
  59. * bits in the value beyond the length to set are ignored.
  60. */
  61. export function inject(buffer, bitIndex, bitLength, value) {
  62. if (bitLength < 0 || bitLength > 32) {
  63. throw new Error("Bad value for bitLength.");
  64. }
  65. var lastByte = Math.floor((bitIndex + bitLength - 1) / 8);
  66. if (bitIndex < 0 || lastByte >= buffer.length) {
  67. throw new Error("Index out of range.");
  68. } // Just keeping it simple, until / unless profiling shows that this
  69. // is a problem.
  70. var atByte = Math.floor(bitIndex / 8);
  71. var atBit = bitIndex % 8;
  72. while (bitLength > 0) {
  73. if (value & 1) {
  74. buffer[atByte] |= 1 << atBit;
  75. } else {
  76. buffer[atByte] &= ~(1 << atBit);
  77. }
  78. value >>= 1;
  79. bitLength--;
  80. atBit = (atBit + 1) % 8;
  81. if (atBit === 0) {
  82. atByte++;
  83. }
  84. }
  85. }
  86. /**
  87. * Gets the sign bit of the given buffer.
  88. */
  89. export function getSign(buffer) {
  90. return buffer[buffer.length - 1] >>> 7;
  91. }
  92. /**
  93. * Gets the zero-based bit number of the highest-order bit with the
  94. * given value in the given buffer.
  95. *
  96. * If the buffer consists entirely of the other bit value, then this returns
  97. * `-1`.
  98. */
  99. export function highOrder(bit, buffer) {
  100. var length = buffer.length;
  101. var fullyWrongByte = (bit ^ 1) * 0xff; // the other-bit extended to a full byte
  102. while (length > 0 && buffer[length - 1] === fullyWrongByte) {
  103. length--;
  104. }
  105. if (length === 0) {
  106. // Degenerate case. The buffer consists entirely of ~bit.
  107. return -1;
  108. }
  109. var byteToCheck = buffer[length - 1];
  110. var result = length * 8 - 1;
  111. for (var i = 7; i > 0; i--) {
  112. if ((byteToCheck >> i & 1) === bit) {
  113. break;
  114. }
  115. result--;
  116. }
  117. return result;
  118. }