Decode a variable-length quantity

Question

A variable-length quantity (also referred to as VLQ or uintvar) is a way to encode up to a 28 bit integer value using only as many bytes as necessary. This was used in MIDI file format as a way to minimize the size of certain event data.

The way it works is fairly simple. As a big-endian series of bytes, the most significant bit (MSB) of each byte is a 1 to indicate that another VLQ byte follows. The remaining 7 bits of each byte make up the decoded value.

Example (from Wikipedia):

[ 0x86, 0xc3, 0x17 ] => 106903

Additional references: Wikipedia, Some Guy.

Challenge:

Given a variable-length quantity, convert it to it's integer value.

Input:

A list of one to four bytes or a 32-bit value type representing a valid VLQ of an integer.

Output:

The integer value of the VLQ input.

Rules and scoring:

• This is code-golf, so shortest answer in bytes for each language wins.
• Standard rules and default I/O rules apply.
• Loopholes forbidden (of course).
• Please provide link with a test for your code (TIO.run, etc).
• A clear explanation for your answer is highly recommended.
• Built-ins that handle this conversion are not banned, however not using them is a lot more interesting.

Test cases:

Input (VLQ)                   Output (int)

[                   0x00 ] => 0
[                   0x07 ] => 7
[                   0x7f ] => 127
[             0x81, 0x00 ] => 128
[             0xC0, 0x00 ] => 8192
[             0xff, 0x7f ] => 16383
[       0x81, 0x80, 0x00 ] => 16384
[       0x86, 0xc3, 0x17 ] => 106903
[       0xbd, 0x84, 0x40 ] => 1000000
[       0xff, 0xff, 0x7f ] => 2097151 
[ 0xC0, 0x80, 0x80, 0x00 ] => 134217728  
[ 0xFF, 0xFF, 0xFF, 0x7F ] => 268435455  

Note: you are not required to use hex literals to represent a byte as your input or output. You may use decimal literal ([ 129, 128, 0 ]), integer (0x80818000) or any other reasonable byte/octet representation if better suited to your platform. Format is flexible as long as it represents 1-4 byte/octets.

Golf away!

Answer 1

APL (dzaima/APL), 8 bytes

128(⊣⊥|)

Try it online!

How:

128(⊣⊥|) ⍝ Anonymous function
128   |  ⍝ Input modulo 128
    ⊣⊥   ⍝ Decoded from base 128

Answer 2

Pari/GP, 24 bytes

a->fromdigits(a%128,128)

Try it online!

Answer 3

Wolfram Language (Mathematica), 25 bytes

Fold[128#+#2&,#~Mod~128]&

Try it online!

Wolfram Language (Mathematica), 25 bytes

#~Mod~128~FromDigits~128&

Try it online!

Answer 4

J, 10 bytes

128#.128|]

Try it online!

Taking inspiration from J Salle's APL answer.

• 128|] Remainder of the input numbers divided by 128
• 128#. Interpreted as the digits of a base 128 number

Answer 5

Jelly, 6 bytes

%Ø⁷ḅØ⁷

Try it online!

Equivalent to alephalpha's Pari/GP answer.

Method: Given \$n\$, output \$n \mod 128\$, converted from base \$128\$ to decimal.

Answer 6

05AB1E, 6 bytes

žy%žyβ

Try it online!

ಠ_ಠ Why do both Jelly and 05AB1E have 2-byte constants for 128? _{^{Well... It's \$2^7\$. But surely those bytes could be used for something better, right?}}

Answer 7

Stax, 8 bytes

å→♂á╣>nt

Run and debug it

Algorithm:

• Convert each byte to fixed-width 7 bit array.
• Flatten bit arrays into one.
• Convert bit array back to number.

Answer 8

JavaScript (ES6), 29 bytes

-2 bytes thanks to @Shaggy

Takes input as an array of bytes.

a=>a.map(p=c=>p=p<<7|c&127)|p

Try it online!

Answer 9

APL+WIN, 22 bytes

Prompts for a vector of integers:

2⊥¯32↑,0 1↓⍉(8⍴2)⊤¯4↑⎕

Try it online! Courtesy of Dyalog Classic

Explanation:

¯4↑⎕ Pad the vector to 4 integers from the right.

⍉(8⍴2)⊤ Convert to a matrix of 8 bit values.

,0 1↓ drop the MSBs and flatten to a vector.

2⊥¯32↑ pad bit vector to 32 bits starting at LSB and convert back to integer.

Answer 10

Stax, 12 bytes

ü╫ôà¡k2Wù}a☺

Run and debug it at staxlang.xyz!

Unpacked (14 bytes) and explanation:

rk128%128i^#*+
r                 Reverse 'cuz big-endian
 k                Fold from the left using block:
  128%              Modulize by 128
      128i^#        Push 128 to the power of (one plus the iteration index)
            *       Multiply
             +      Add to the total
                  Implicit print

Stax has builtin base conversion, but it only works on strings. It almost works on lists of integers, though; the problem is in Stax's handling of 0.

A string is a list of integers. When you're using such a list as a string, any zeroes are automatically converted to 32 as a nice shorthand for spaces. Since the builtin |b for base conversion treats its operand as a string rather than as a raw list of integers, any case with a zero will fail.

10 bytes, fails on zeroes

Ç┘_A♥∙QZ►╣
{128%m128|b    Unpacked
{128%m         Modulize each by 128
      128|b    Convert from base 128

Run and debug it at staxlang.xyz!

Answer 11

Python 3, 58 49 bytes

-9 bytes thanks to @Chas and @ar4093

lambda x:int("".join(bin(a|128)[3:]for a in x),2)

Try it online!

or

lambda x:int("".join(f"{a%128:07b}"for a in x),2)

Try it online!

Input via list of integers.

Python's bin function adds "0b" to the beginning of the string, so those have to be taken off before they can be concatenated. It also doesn't keep leading zeros, so if there aren't any (aka the last byte) those have to be added back in. And if there is a leading one (aka all but the last byte) that must be removed as well. Thanks to @Chas for figuring out that by always setting the first bit, I can just remove the first three characters and be done.

Apparently (according to @ar4093) the format function allows not only not having the '0b' prefix, but also removing the first bit and padding to 7 characters all at the same time.

Answer 12

C (gcc), 48 bytes

Takes an integer in big-endian order as input, which is the same order as a byte array.

f(i,j){for(j=0;j|=i&127,i&128;j<<=7,i>>=8);i=j;}

Try it online!

C (gcc), 53 bytes

If a byte array is needed:

f(c,j)char*c;{for(j=0;j|=*c&127,*c++&128;j<<=7);c=j;}

Try it online!

Answer 13

MathGolf, 14 bytes

ê♣%hrx♣▬^mÅε*Σ

Input as integers.

Try it online.

I have the feeling this can be shorter.. It's a bit annoying that MathGolf has a 1-byte builtin for the constant 128, but no base-conversion (except for binary/hexadecimal).

Explanation:

ê              # Take the inputs as integer-array
 ♣%            # Take modulo-128 on each value in this array
   h           # Push the length of the array (without popping the array itself)
    r          # Pop and push a list in the range [0, length)
     x         # Reverse the array to (length, 0]
      ♣▬       # Take 128 to the power of each value in this array
        ^      # Zip the two lists together to create pairs
         mÅ    # Map each pair to (using the following two commands):
           ε*  #  Reduce by multiplication (so basically the product of the pair)
             Σ # After multiplying each pair, take the total sum
               # (after which the entire stack joined together is output implicitly)

Answer 14

Japt, 10 8 bytes

Takes input as an array of integers.

muIÑ ìIÑ

Try it or run all test cases (header in both converts from input format used in challenge)

Saved 2 bytes by taking inspiration from alephalpha's solution.

muIÑ ìIÑ     :Implicit input of integer array
m            :Map
 u           :  Modulo
  I          :    64
   Ñ         :    Multiply by 2
     ì       :Convert to decimal
      IÑ     :  From base 64*2

Answer 15

PHP, 42 bytes

foreach($argv as$a)$r=$r<<7|$a&127;echo$r;

Try it online! and verify all test cases.

Input via command line args, output to STDOUT.

Answer 16

Charcoal, 11 bytes

Ｉ↨﹪θ¹²⁸¦¹²⁸

Try it online! Link is to verbose version of code. Takes input as an array. Explanation:

   θ        Input array
  ﹪ ¹²⁸    Elementwise modulo 128
 ↨      ¹²⁸ Convert from base 128
Ｉ          Cast to string for implicit print

Answer 17

Python 2, 42 bytes

f=lambda a:a>[]and a[-1]%128+f(a[:-1])*128

Try it online!

Answer 18

Windows Batch, 76 bytes

:a
@set/ax="%1&127",y=y*128+x
@if %2. neq . @shift&goto:a
@echo %y%

Pass parameters prefixed with "0x" and space between (e.g. 0xC0 0x80 0x80 0x00).