You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

base64-vlq.js 4.6KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
  1. /* -*- Mode: js; js-indent-level: 2; -*- */
  2. /*
  3. * Copyright 2011 Mozilla Foundation and contributors
  4. * Licensed under the New BSD license. See LICENSE or:
  5. * http://opensource.org/licenses/BSD-3-Clause
  6. *
  7. * Based on the Base 64 VLQ implementation in Closure Compiler:
  8. * https://code.google.com/p/closure-compiler/source/browse/trunk/src/com/google/debugging/sourcemap/Base64VLQ.java
  9. *
  10. * Copyright 2011 The Closure Compiler Authors. All rights reserved.
  11. * Redistribution and use in source and binary forms, with or without
  12. * modification, are permitted provided that the following conditions are
  13. * met:
  14. *
  15. * * Redistributions of source code must retain the above copyright
  16. * notice, this list of conditions and the following disclaimer.
  17. * * Redistributions in binary form must reproduce the above
  18. * copyright notice, this list of conditions and the following
  19. * disclaimer in the documentation and/or other materials provided
  20. * with the distribution.
  21. * * Neither the name of Google Inc. nor the names of its
  22. * contributors may be used to endorse or promote products derived
  23. * from this software without specific prior written permission.
  24. *
  25. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29. * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31. * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32. * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33. * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36. */
  37. var base64 = require('./base64');
  38. // A single base 64 digit can contain 6 bits of data. For the base 64 variable
  39. // length quantities we use in the source map spec, the first bit is the sign,
  40. // the next four bits are the actual value, and the 6th bit is the
  41. // continuation bit. The continuation bit tells us whether there are more
  42. // digits in this value following this digit.
  43. //
  44. // Continuation
  45. // | Sign
  46. // | |
  47. // V V
  48. // 101011
  49. var VLQ_BASE_SHIFT = 5;
  50. // binary: 100000
  51. var VLQ_BASE = 1 << VLQ_BASE_SHIFT;
  52. // binary: 011111
  53. var VLQ_BASE_MASK = VLQ_BASE - 1;
  54. // binary: 100000
  55. var VLQ_CONTINUATION_BIT = VLQ_BASE;
  56. /**
  57. * Converts from a two-complement value to a value where the sign bit is
  58. * placed in the least significant bit. For example, as decimals:
  59. * 1 becomes 2 (10 binary), -1 becomes 3 (11 binary)
  60. * 2 becomes 4 (100 binary), -2 becomes 5 (101 binary)
  61. */
  62. function toVLQSigned(aValue) {
  63. return aValue < 0
  64. ? ((-aValue) << 1) + 1
  65. : (aValue << 1) + 0;
  66. }
  67. /**
  68. * Converts to a two-complement value from a value where the sign bit is
  69. * placed in the least significant bit. For example, as decimals:
  70. * 2 (10 binary) becomes 1, 3 (11 binary) becomes -1
  71. * 4 (100 binary) becomes 2, 5 (101 binary) becomes -2
  72. */
  73. function fromVLQSigned(aValue) {
  74. var isNegative = (aValue & 1) === 1;
  75. var shifted = aValue >> 1;
  76. return isNegative
  77. ? -shifted
  78. : shifted;
  79. }
  80. /**
  81. * Returns the base 64 VLQ encoded value.
  82. */
  83. exports.encode = function base64VLQ_encode(aValue) {
  84. var encoded = "";
  85. var digit;
  86. var vlq = toVLQSigned(aValue);
  87. do {
  88. digit = vlq & VLQ_BASE_MASK;
  89. vlq >>>= VLQ_BASE_SHIFT;
  90. if (vlq > 0) {
  91. // There are still more digits in this value, so we must make sure the
  92. // continuation bit is marked.
  93. digit |= VLQ_CONTINUATION_BIT;
  94. }
  95. encoded += base64.encode(digit);
  96. } while (vlq > 0);
  97. return encoded;
  98. };
  99. /**
  100. * Decodes the next base 64 VLQ value from the given string and returns the
  101. * value and the rest of the string via the out parameter.
  102. */
  103. exports.decode = function base64VLQ_decode(aStr, aIndex, aOutParam) {
  104. var strLen = aStr.length;
  105. var result = 0;
  106. var shift = 0;
  107. var continuation, digit;
  108. do {
  109. if (aIndex >= strLen) {
  110. throw new Error("Expected more digits in base 64 VLQ value.");
  111. }
  112. digit = base64.decode(aStr.charCodeAt(aIndex++));
  113. if (digit === -1) {
  114. throw new Error("Invalid base64 digit: " + aStr.charAt(aIndex - 1));
  115. }
  116. continuation = !!(digit & VLQ_CONTINUATION_BIT);
  117. digit &= VLQ_BASE_MASK;
  118. result = result + (digit << shift);
  119. shift += VLQ_BASE_SHIFT;
  120. } while (continuation);
  121. aOutParam.value = fromVLQSigned(result);
  122. aOutParam.rest = aIndex;
  123. };