47 lines
1.8 KiB
Plaintext
47 lines
1.8 KiB
Plaintext
# "VARIABLE-LENGTH QUANTITY"
|
|
# A VLQ is a variable-length encoding of a number into a sequence of octets,
|
|
# with the most-significant octet first, and with the most significant bit first in each octet.
|
|
# The first (left-most) bit in each octet is a continuation bit: all octets except the last have the left-most bit set.
|
|
# The bits of the original number are taken 7 at a time from the right to form the octets.
|
|
# Thus, if the number is between 0 and 127, it is represented exactly as one byte.
|
|
|
|
# Produce a stream of the base $b "digits" of the input number,
|
|
# least significant first, with a final 0
|
|
def digits($b):
|
|
def mod: . % $b;
|
|
def div: ((. - mod) / $b);
|
|
recurse( select(. > 0) | div) | mod ;
|
|
|
|
# 2 <= $b <= 36
|
|
def tobase($b):
|
|
def digit: "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[.:.+1];
|
|
if . == 0 then "0"
|
|
else [digits($b) | digit] | reverse[1:] | add
|
|
end;
|
|
|
|
# input: a decimal integer
|
|
# output: the corresponding variable-length quantity expressed as an array of strings of length 2,
|
|
# each representing an octet in hexadecimal notation, with most-significant octet first.
|
|
def vlq:
|
|
def lpad: if length == 2 then . else "0" + . end;
|
|
[digits(128) + 128] | reverse[1:] | .[-1] -=128 | map(tobase(16) | lpad);
|
|
|
|
# Input: a VLQ as produced by vlq/0
|
|
# Output: the corresponding decimal
|
|
def vlq2dec:
|
|
def x2d: # convert the character interpreted as a hex digit to a decimal
|
|
explode[0] as $x
|
|
| if $x < 65 then $x - 48 elif $x < 97 then $x - 55 else $x - 87 end;
|
|
map( ((.[0:1] | x2d) * 16) + (.[1:] | x2d) - 128)
|
|
| .[-1] += 128 # the most significant bit of the least significant octet
|
|
| reduce reverse[] as $x ({x: 0, m: 1}; .x += ($x * .m) | .m *= 128)
|
|
| .x ;
|
|
|
|
# The task
|
|
|
|
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
|
|
|
|
2097152, 2097151
|
|
| vlq as $vlq
|
|
| "\(lpad(8)) => \($vlq|join(",")|lpad(12)) => \($vlq | vlq2dec | lpad(8))"
|