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  
 38  var base64 = require('./base64');
 39  
 40  // A single base 64 digit can contain 6 bits of data. For the base 64 variable
 41  // length quantities we use in the source map spec, the first bit is the sign,
 42  // the next four bits are the actual value, and the 6th bit is the
 43  // continuation bit. The continuation bit tells us whether there are more
 44  // digits in this value following this digit.
 45  //
 46  //   Continuation
 47  //   |    Sign
 48  //   |    |
 49  //   V    V
 50  //   101011
 51  
 52  var VLQ_BASE_SHIFT = 5;
 53  
 54  // binary: 100000
 55  var VLQ_BASE = 1 << VLQ_BASE_SHIFT;
 56  
 57  // binary: 011111
 58  var VLQ_BASE_MASK = VLQ_BASE - 1;
 59  
 60  // binary: 100000
 61  var VLQ_CONTINUATION_BIT = VLQ_BASE;
 62  
 63  /**
 64   * Converts from a two-complement value to a value where the sign bit is
 65   * placed in the least significant bit.  For example, as decimals:
 66   *   1 becomes 2 (10 binary), -1 becomes 3 (11 binary)
 67   *   2 becomes 4 (100 binary), -2 becomes 5 (101 binary)
 68   */
 69  function toVLQSigned(aValue) {
 70    return aValue < 0
 71      ? ((-aValue) << 1) + 1
 72      : (aValue << 1) + 0;
 73  }
 74  
 75  /**
 76   * Converts to a two-complement value from a value where the sign bit is
 77   * placed in the least significant bit.  For example, as decimals:
 78   *   2 (10 binary) becomes 1, 3 (11 binary) becomes -1
 79   *   4 (100 binary) becomes 2, 5 (101 binary) becomes -2
 80   */
 81  function fromVLQSigned(aValue) {
 82    var isNegative = (aValue & 1) === 1;
 83    var shifted = aValue >> 1;
 84    return isNegative
 85      ? -shifted
 86      : shifted;
 87  }
 88  
 89  /**
 90   * Returns the base 64 VLQ encoded value.
 91   */
 92  exports.encode = function base64VLQ_encode(aValue) {
 93    var encoded = "";
 94    var digit;
 95  
 96    var vlq = toVLQSigned(aValue);
 97  
 98    do {
 99      digit = vlq & VLQ_BASE_MASK;
100      vlq >>>= VLQ_BASE_SHIFT;
101      if (vlq > 0) {
102        // There are still more digits in this value, so we must make sure the
103        // continuation bit is marked.
104        digit |= VLQ_CONTINUATION_BIT;
105      }
106      encoded += base64.encode(digit);
107    } while (vlq > 0);
108  
109    return encoded;
110  };
111  
112  /**
113   * Decodes the next base 64 VLQ value from the given string and returns the
114   * value and the rest of the string via the out parameter.
115   */
116  exports.decode = function base64VLQ_decode(aStr, aIndex, aOutParam) {
117    var strLen = aStr.length;
118    var result = 0;
119    var shift = 0;
120    var continuation, digit;
121  
122    do {
123      if (aIndex >= strLen) {
124        throw new Error("Expected more digits in base 64 VLQ value.");
125      }
126  
127      digit = base64.decode(aStr.charCodeAt(aIndex++));
128      if (digit === -1) {
129        throw new Error("Invalid base64 digit: " + aStr.charAt(aIndex - 1));
130      }
131  
132      continuation = !!(digit & VLQ_CONTINUATION_BIT);
133      digit &= VLQ_BASE_MASK;
134      result = result + (digit << shift);
135      shift += VLQ_BASE_SHIFT;
136    } while (continuation);
137  
138    aOutParam.value = fromVLQSigned(result);
139    aOutParam.rest = aIndex;
140  };