1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
class SourceMap
# Support for encoding/decoding the variable length quantity format
# described in the spec at:
#
# https://docs.google.com/document/d/1U1RGAehQwRypUTovF1KRlpiOFze0b-_2gc6fAH0KY0k/edit
#
# This implementation is heavily based on https://github.com/mozilla/source-map
# Copyright 2009-2011, Mozilla Foundation and contributors, BSD
#
module VLQ
# A single base 64 digit can contain 6 bits of data. For the base 64 variable
# length quantities we use in the source map spec, the first bit is the sign,
# the next four bits are the actual value, and the 6th bit is the
# continuation bit. The continuation bit tells us whether there are more
# digits in this value following this digit.
#
# Continuation
# | Sign
# | |
# V V
# 101011
VLQ_BASE_SHIFT = 5;
# binary: 100000
VLQ_BASE = 1 << VLQ_BASE_SHIFT;
# binary: 011111
VLQ_BASE_MASK = VLQ_BASE - 1;
# binary: 100000
VLQ_CONTINUATION_BIT = VLQ_BASE;
BASE64_DIGITS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'.split('')
BASE64_VALUES = (0..64).inject({}){ |h, i| h.update BASE64_DIGITS[i] => i }
# Returns the base 64 VLQ encoded value.
def self.encode(int)
vlq = to_vlq_signed(int)
encoded = ""
begin
digit = vlq & VLQ_BASE_MASK
vlq >>= VLQ_BASE_SHIFT
digit |= VLQ_CONTINUATION_BIT if vlq > 0
encoded << base64_encode(digit)
end while vlq > 0
encoded
end
# Decodes the next base 64 VLQ value from the given string and returns the
# value and the rest of the string.
def self.decode(str)
vlq = 0
shift = 0
continue = true
chars = str.split('')
while continue
char = chars.shift or raise "Expected more digits in base 64 VLQ value."
digit = base64_decode(char)
continue = false if (digit & VLQ_CONTINUATION_BIT) == 0
digit &= VLQ_BASE_MASK
vlq += digit << shift
shift += VLQ_BASE_SHIFT
end
[from_vlq_signed(vlq), chars.join('')]
end
# Decode an array of variable length quantities from the given string and
# return them.
def self.decode_array(str)
output = []
while str != ''
int, str = decode(str)
output << int
end
output
end
protected
def self.base64_encode(int)
BASE64_DIGITS[int] or raise ArgumentError, "#{int} is not a valid base64 digit"
end
def self.base64_decode(char)
BASE64_VALUES[char] or raise ArgumentError, "#{char} is not a valid base64 digit"
end
# Converts from a two's-complement integer to an integer where the
# sign bit is placed in the least significant bit. For example, as decimals:
# 1 becomes 2 (10 binary), -1 becomes 3 (11 binary)
# 2 becomes 4 (100 binary), -2 becomes 5 (101 binary)
def self.to_vlq_signed(int)
if int < 0
((-int) << 1) + 1
else
int << 1
end
end
# Converts to a two's-complement value from a value where the sign bit is
# placed in the least significant bit. For example, as decimals:
#
# 2 (10 binary) becomes 1, 3 (11 binary) becomes -1
# 4 (100 binary) becomes 2, 5 (101 binary) becomes -2
def self.from_vlq_signed(vlq)
if vlq & 1 == 1
-(vlq >> 1)
else
vlq >> 1
end
end
end
end
|
