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
Remember that in Scala there are two forms of the right shift operator. The >>
operator preserves the sign, while >>>
zeroes the leftmost bits.
The Scala exercises assume an SBT project scheme. The exercise solution source should be placed within the exercise directory/src/main/scala. The exercise unit tests can be found within the exercise directory/src/test/scala.
To run the tests simply run the command sbt test
in the exercise directory.
Please see the learning and installation pages if you need any help.
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.
import org.scalatest.{Matchers, FunSuite}
/** @version 1.1.0 */
class VariableLengthQuantityTest extends FunSuite with Matchers {
test("zero") {
VariableLengthQuantity.encode(List(0x0)) should be(List(0x0))
}
test("arbitrary single byte") {
pending
VariableLengthQuantity.encode(List(0x40)) should be(List(0x40))
}
test("largest single byte") {
pending
VariableLengthQuantity.encode(List(0x7F)) should be(List(0x7F))
}
test("smallest double byte") {
pending
VariableLengthQuantity.encode(List(0x80)) should be(List(0x81, 0x0))
}
test("arbitrary double byte") {
pending
VariableLengthQuantity.encode(List(0x2000)) should be(List(0xC0, 0x0))
}
test("largest double byte") {
pending
VariableLengthQuantity.encode(List(0x3FFF)) should be(List(0xFF, 0x7F))
}
test("smallest triple byte") {
pending
VariableLengthQuantity.encode(List(0x4000)) should be(List(0x81, 0x80, 0x0))
}
test("arbitrary triple byte") {
pending
VariableLengthQuantity.encode(List(0x100000)) should be(
List(0xC0, 0x80, 0x0))
}
test("largest triple byte") {
pending
VariableLengthQuantity.encode(List(0x1FFFFF)) should be(
List(0xFF, 0xFF, 0x7F))
}
test("smallest quadruple byte") {
pending
VariableLengthQuantity.encode(List(0x200000)) should be(
List(0x81, 0x80, 0x80, 0x0))
}
test("arbitrary quadruple byte") {
pending
VariableLengthQuantity.encode(List(0x8000000)) should be(
List(0xC0, 0x80, 0x80, 0x0))
}
test("largest quadruple byte") {
pending
VariableLengthQuantity.encode(List(0xFFFFFFF)) should be(
List(0xFF, 0xFF, 0xFF, 0x7F))
}
test("smallest quintuple byte") {
pending
VariableLengthQuantity.encode(List(0x10000000)) should be(
List(0x81, 0x80, 0x80, 0x80, 0x0))
}
test("arbitrary quintuple byte") {
pending
VariableLengthQuantity.encode(List(0xFF000000)) should be(
List(0x8F, 0xF8, 0x80, 0x80, 0x0))
}
test("maximum 32-bit integer input") {
pending
VariableLengthQuantity.encode(List(0xFFFFFFFF)) should be(
List(0x8F, 0xFF, 0xFF, 0xFF, 0x7F))
}
test("two single-byte values") {
pending
VariableLengthQuantity.encode(List(0x40, 0x7F)) should be(List(0x40, 0x7F))
}
test("two multi-byte values") {
pending
VariableLengthQuantity.encode(List(0x4000, 0x123456)) should be(
List(0x81, 0x80, 0x0, 0xC8, 0xE8, 0x56))
}
test("many multi-byte values") {
pending
VariableLengthQuantity.encode(
List(0x2000, 0x123456, 0xFFFFFFF, 0x0, 0x3FFF, 0x4000)) should be(
List(0xC0, 0x0, 0xC8, 0xE8, 0x56, 0xFF, 0xFF, 0xFF, 0x7F, 0x0, 0xFF, 0x7F,
0x81, 0x80, 0x0))
}
test("one byte") {
pending
VariableLengthQuantity.decode(List(0x7F)) should be(Right(List(0x7F)))
}
test("two bytes") {
pending
VariableLengthQuantity.decode(List(0xC0, 0x0)) should be(
Right(List(0x2000)))
}
test("three bytes") {
pending
VariableLengthQuantity.decode(List(0xFF, 0xFF, 0x7F)) should be(
Right(List(0x1FFFFF)))
}
test("four bytes") {
pending
VariableLengthQuantity.decode(List(0x81, 0x80, 0x80, 0x0)) should be(
Right(List(0x200000)))
}
test("maximum 32-bit integer") {
pending
VariableLengthQuantity.decode(List(0x8F, 0xFF, 0xFF, 0xFF, 0x7F)) should be(
Right(List(0xFFFFFFFF)))
}
test("incomplete sequence causes error") {
pending
VariableLengthQuantity.decode(List(0xFF)).isLeft should be(true)
}
test("incomplete sequence causes error, even if value is zero") {
pending
VariableLengthQuantity.decode(List(0x80)).isLeft should be(true)
}
test("multiple values") {
pending
VariableLengthQuantity.decode(
List(0xC0, 0x0, 0xC8, 0xE8, 0x56, 0xFF, 0xFF, 0xFF, 0x7F, 0x0, 0xFF, 0x7F,
0x81, 0x80, 0x0)) should be(
Right(List(0x2000, 0x123456, 0xFFFFFFF, 0x0, 0x3FFF, 0x4000)))
}
}
object VariableLengthQuantity {
def encode(input: List[Int]) : List[BigInt] = input.flatMap(encodeSingle)
private def encodeSingle(n: Int) = {
val byteRange = (0 until (n.toBinaryString.length / 7.0).ceil.toInt).toList
val m = if (n < 0) 0x100000000L + BigInt(n) else BigInt(n)
byteRange.map(k => {(m/(1<<7*k) % 128) + (if (k > 0) 128 else 0)}).reverse
}
private def split(input: List[Int], lists: List[List[Int]], current : List[Int]) :List[List[Int]]= {
input match {
case Nil => lists
case x :: y if x < 128 => split(y, lists :+ (current :+ x), List())
case x :: y => split(y, lists, current :+ x)
}
}
def decode(input: List[Int]) : Either[List[Int], List[Int]] = {
if (input.last > 127)
Left(List())
else
Right((split(input, List(), List()).map(decodeValue)))
}
private def decodeValue(input: List[Int]) = {
input.map(x => {x % 128}).foldLeft(0)((acc,x) => (acc<<7) + x)
}
}
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,113 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