Avatar of tinnuir

tinnuir's solution

to Variable Length Quantity in the Scala Track

Published at Jun 01 2019 · 0 comments
Test suite

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:

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.

For more detailed info about the Scala track see the help page.


A poor Splice developer having to implement MIDI encoding/decoding. https://splice.com

Submitting Incomplete Solutions

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") {
    VariableLengthQuantity.encode(List(0x40)) should be(List(0x40))

  test("largest single byte") {
    VariableLengthQuantity.encode(List(0x7F)) should be(List(0x7F))

  test("smallest double byte") {
    VariableLengthQuantity.encode(List(0x80)) should be(List(0x81, 0x0))

  test("arbitrary double byte") {
    VariableLengthQuantity.encode(List(0x2000)) should be(List(0xC0, 0x0))

  test("largest double byte") {
    VariableLengthQuantity.encode(List(0x3FFF)) should be(List(0xFF, 0x7F))

  test("smallest triple byte") {
    VariableLengthQuantity.encode(List(0x4000)) should be(List(0x81, 0x80, 0x0))

  test("arbitrary triple byte") {
    VariableLengthQuantity.encode(List(0x100000)) should be(
      List(0xC0, 0x80, 0x0))

  test("largest triple byte") {
    VariableLengthQuantity.encode(List(0x1FFFFF)) should be(
      List(0xFF, 0xFF, 0x7F))

  test("smallest quadruple byte") {
    VariableLengthQuantity.encode(List(0x200000)) should be(
      List(0x81, 0x80, 0x80, 0x0))

  test("arbitrary quadruple byte") {
    VariableLengthQuantity.encode(List(0x8000000)) should be(
      List(0xC0, 0x80, 0x80, 0x0))

  test("largest quadruple byte") {
    VariableLengthQuantity.encode(List(0xFFFFFFF)) should be(
      List(0xFF, 0xFF, 0xFF, 0x7F))

  test("smallest quintuple byte") {
    VariableLengthQuantity.encode(List(0x10000000)) should be(
      List(0x81, 0x80, 0x80, 0x80, 0x0))

  test("arbitrary quintuple byte") {
    VariableLengthQuantity.encode(List(0xFF000000)) should be(
      List(0x8F, 0xF8, 0x80, 0x80, 0x0))

  test("maximum 32-bit integer input") {
    VariableLengthQuantity.encode(List(0xFFFFFFFF)) should be(
      List(0x8F, 0xFF, 0xFF, 0xFF, 0x7F))

  test("two single-byte values") {
    VariableLengthQuantity.encode(List(0x40, 0x7F)) should be(List(0x40, 0x7F))

  test("two multi-byte values") {
    VariableLengthQuantity.encode(List(0x4000, 0x123456)) should be(
      List(0x81, 0x80, 0x0, 0xC8, 0xE8, 0x56))

  test("many multi-byte values") {
      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") {
    VariableLengthQuantity.decode(List(0x7F)) should be(Right(List(0x7F)))

  test("two bytes") {
    VariableLengthQuantity.decode(List(0xC0, 0x0)) should be(

  test("three bytes") {
    VariableLengthQuantity.decode(List(0xFF, 0xFF, 0x7F)) should be(

  test("four bytes") {
    VariableLengthQuantity.decode(List(0x81, 0x80, 0x80, 0x0)) should be(

  test("maximum 32-bit integer") {
    VariableLengthQuantity.decode(List(0x8F, 0xFF, 0xFF, 0xFF, 0x7F)) should be(

  test("incomplete sequence causes error") {
    VariableLengthQuantity.decode(List(0xFF)).isLeft should be(true)

  test("incomplete sequence causes error, even if value is zero") {
    VariableLengthQuantity.decode(List(0x80)).isLeft should be(true)

  test("multiple values") {
      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)))
import DecodingError.DecodingError

import scala.annotation.tailrec

object DecodingError extends Enumeration {
  type DecodingError = Value
  val IncompleteNumber: Value = Value

object VariableLengthQuantity {
  private val ChunkMask = 0x7f
  private val ChunkSize = 7
  private val MostSignificantBit = 0x80

  private def bytes(n: Int): List[Int] = {
    def helper(remaining: Int, result: List[Int]): List[Int] =
      if (remaining == 0) result
      else helper(remaining >>> ChunkSize, (remaining & ChunkMask) :: result)
    helper(n >>> ChunkSize, List(n & ChunkMask))

  private def encodeNumber(n: Int): List[Int] = (bytes(n).reverse: @unchecked) match {
    case b :: bs => (b :: bs.map(_ | MostSignificantBit)).reverse

  private def extractNumbers(values: List[Int]): List[List[Int]] =
    values.foldRight(List[List[Int]]())((v, a) =>
      if ((v & MostSignificantBit) == 0) List(v) :: a else (v :: a.head) :: a.tail

  private def decodeNumber(values: List[Int]): Int = (values.reverse: @unchecked) match {
    case b :: bs => (b :: bs.map(_ & ~MostSignificantBit)).foldRight(0)((x, a) => (a << ChunkSize) | x)

  def encode(values: List[Int]): List[Int] = values.flatMap(encodeNumber)

  def decode(values: List[Int]): Either[DecodingError, List[Int]] =
    if ((values.lastOption.getOrElse(0) & MostSignificantBit) != 0) Left(DecodingError.IncompleteNumber)
    else Right(extractNumbers(values).map(decodeNumber))

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

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.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?