Implement variable length quantity encoding and decoding.
The goal of this exercise is to implement VLQ encoding/decoding.
In short, the goal of this encoding is to encode integer values in a way that would save bytes. Only the first 7 bits of each byte is significant (right-justified; sort of like an ASCII byte). So, if you have a 32-bit value, you have to unpack it into a series of 7-bit bytes. Of course, you will have a variable number of bytes depending upon your integer. To indicate which is the last byte of the series, you leave bit #7 clear. In all of the preceding bytes, you set bit #7.
So, if an integer is between 0-127
, it can be represented as one byte.
Although VLQ can deal with numbers of arbitrary sizes, for this exercise we will restrict ourselves to only numbers that fit in a 32-bit unsigned integer.
Here are examples of integers as 32-bit values, and the variable length quantities that they translate to:
NUMBER VARIABLE QUANTITY
00000000 00
00000040 40
0000007F 7F
00000080 81 00
00002000 C0 00
00003FFF FF 7F
00004000 81 80 00
00100000 C0 80 00
001FFFFF FF FF 7F
00200000 81 80 80 00
08000000 C0 80 80 00
0FFFFFFF FF FF FF 7F
To run the tests, run the command busted
from within the exercise directory.
For more detailed information about the Lua track, including how to get help if you're having trouble, please visit the exercism.io Lua language page.
A poor Splice developer having to implement MIDI encoding/decoding. https://splice.com
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
local vlq = require 'variable-length-quantity'
describe('variable-length-quantity', function()
it('should decode single bytes', function()
assert.are.same({ 0x00 }, vlq.decode({ 0x00 }))
assert.are.same({ 0x40 }, vlq.decode({ 0x40 }))
assert.are.same({ 0x7f }, vlq.decode({ 0x7f }))
end)
it('should decode double bytes', function()
assert.are.same({ 0x80 }, vlq.decode({ 0x81, 0x00 }))
assert.are.same({ 0x2000 }, vlq.decode({ 0xc0, 0x00 }))
assert.are.same({ 0x3fff }, vlq.decode({ 0xff, 0x7f }))
end)
it('should decode triple bytes', function()
assert.are.same({ 0x4000 }, vlq.decode({ 0x81, 0x80, 0x00 }))
assert.are.same({ 0x100000 }, vlq.decode({ 0xc0, 0x80, 0x00 }))
assert.are.same({ 0x1fffff }, vlq.decode({ 0xff, 0xff, 0x7f }))
end)
it('should decode quadruple bytes', function()
assert.are.same({ 0x200000 }, vlq.decode({ 0x81, 0x80, 0x80, 0x00 }))
assert.are.same({ 0x08000000 }, vlq.decode({ 0xc0, 0x80, 0x80, 0x00 }))
assert.are.same({ 0x0fffffff }, vlq.decode({ 0xff, 0xff, 0xff, 0x7f }))
end)
it('should decode multiple values', function()
assert.are.same(
{ 0x2000, 0x123456, 0x0fffffff, 0x00, 0x3fff, 0x4000 },
vlq.decode({ 0xc0, 0x00, 0xc8, 0xe8, 0x56, 0xff, 0xff, 0xff, 0x7f, 0x00, 0xff, 0x7f, 0x81, 0x80, 0x00 })
)
end)
it('should encode single bytes', function()
assert.are.same({ 0x00 }, vlq.encode({ 0x00 }))
assert.are.same({ 0x40 }, vlq.encode({ 0x40 }))
assert.are.same({ 0x7f }, vlq.encode({ 0x7f }))
end)
it('should encode double bytes', function()
assert.are.same({ 0x81, 0x00 }, vlq.encode({ 0x80 }))
assert.are.same({ 0xc0, 0x00 }, vlq.encode({ 0x2000 }))
assert.are.same({ 0xff, 0x7f }, vlq.encode({ 0x3fff }))
end)
it('should encode triple bytes', function()
assert.are.same({ 0x81, 0x80, 0x00 }, vlq.encode({ 0x4000 }))
assert.are.same({ 0xc0, 0x80, 0x00 }, vlq.encode({ 0x100000 }))
assert.are.same({ 0xff, 0xff, 0x7f }, vlq.encode({ 0x1fffff }))
end)
it('should encode quadruple bytes', function()
assert.are.same({ 0x81, 0x80, 0x80, 0x00 }, vlq.encode({ 0x200000 }))
assert.are.same({ 0xc0, 0x80, 0x80, 0x00 }, vlq.encode({ 0x08000000 }))
assert.are.same({ 0xff, 0xff, 0xff, 0x7f }, vlq.encode({ 0x0fffffff }))
end)
it('should encode multiple values', function()
assert.are.same({ 0x40, 0x7f }, vlq.encode({ 0x40, 0x7f }))
assert.are.same({ 0x81, 0x80, 0x00, 0xc8, 0xe8, 0x56 }, vlq.encode({ 0x4000, 0x123456 }))
assert.are.same(
{ 0xc0, 0x00, 0xc8, 0xe8, 0x56, 0xff, 0xff, 0xff, 0x7f, 0x00, 0xff, 0x7f, 0x81, 0x80, 0x00 },
vlq.encode({ 0x2000, 0x123456, 0x0fffffff, 0x00, 0x3fff, 0x4000 })
)
end)
it('should raise an error when decoding an incomplete byte sequence', function()
assert.has.error(function()
vlq.decode({ 0x81, 0x00, 0x80 })
end, 'incomplete byte sequence')
end)
end)
local base = 2^7
local function decode_worker(data, decoded)
local next_stream_following = data//base
table.insert(decoded, data%base)
if next_stream_following == 1 then return false
else return true end
end
local function decode(input)
local output = {}
local decoded = {}
local end_of_stream
for i=1, #input do
end_of_stream = decode_worker(input[i], decoded)
if end_of_stream then
local decoded_value = 0
for j=0, #decoded-1 do
decoded_value = decoded_value + decoded[#decoded -j]*base^j
end
table.insert(output, decoded_value) decoded = {}
end
end
if end_of_stream ~= true then error('incomplete byte sequence') end
return output
end
local function encode_worker(input, ith, output)
if ith == 1 then table.insert(output, input%base)
else table.insert(output, (input%base + base)) end
local next_input = input//base
if next_input >= 1 then encode_worker(next_input, ith+1, output) end
end
local function encode(input)
local output = {}
for i=1, #input do
local encoded = {}
encode_worker(input[i], 1, encoded)
for j=#encoded, 1, -1 do
table.insert(output, encoded[j])
end
end
return output
end
return {
encode = encode,
decode = decode
}
A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.
Here are some questions to help you reflect on this solution and learn the most from it.
Level up your programming skills with 3,449 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors. Exercism is 100% free forever.
Sign up Learn More
Community comments