Avatar of nathanchere

nathanchere's solution

to Variable Length Quantity in the C# Track

Published at Sep 12 2019 · 0 comments
Instructions
Test suite
Solution

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

Hints

This exercise requires you to use bitwise operations. For more information, see [this page] (https://msdn.microsoft.com/en-us/library/6a71f45d.aspx).

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit VariableLengthQuantity.cs

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

Source

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

VariableLengthQuantityTest.cs

// This file was auto-generated based on version 1.2.0 of the canonical data.

using System;
using Xunit;

public class VariableLengthQuantityTest
{
    [Fact]
    public void Zero()
    {
        var integers = new[] { 0x0u };
        var expected = new[] { 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Arbitrary_single_byte()
    {
        var integers = new[] { 0x40u };
        var expected = new[] { 0x40u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Largest_single_byte()
    {
        var integers = new[] { 0x7Fu };
        var expected = new[] { 0x7Fu };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Smallest_double_byte()
    {
        var integers = new[] { 0x80u };
        var expected = new[] { 0x81u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Arbitrary_double_byte()
    {
        var integers = new[] { 0x2000u };
        var expected = new[] { 0xC0u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Largest_double_byte()
    {
        var integers = new[] { 0x3FFFu };
        var expected = new[] { 0xFFu, 0x7Fu };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Smallest_triple_byte()
    {
        var integers = new[] { 0x4000u };
        var expected = new[] { 0x81u, 0x80u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Arbitrary_triple_byte()
    {
        var integers = new[] { 0x100000u };
        var expected = new[] { 0xC0u, 0x80u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Largest_triple_byte()
    {
        var integers = new[] { 0x1FFFFFu };
        var expected = new[] { 0xFFu, 0xFFu, 0x7Fu };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Smallest_quadruple_byte()
    {
        var integers = new[] { 0x200000u };
        var expected = new[] { 0x81u, 0x80u, 0x80u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Arbitrary_quadruple_byte()
    {
        var integers = new[] { 0x8000000u };
        var expected = new[] { 0xC0u, 0x80u, 0x80u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Largest_quadruple_byte()
    {
        var integers = new[] { 0xFFFFFFFu };
        var expected = new[] { 0xFFu, 0xFFu, 0xFFu, 0x7Fu };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Smallest_quintuple_byte()
    {
        var integers = new[] { 0x10000000u };
        var expected = new[] { 0x81u, 0x80u, 0x80u, 0x80u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Arbitrary_quintuple_byte()
    {
        var integers = new[] { 0xFF000000u };
        var expected = new[] { 0x8Fu, 0xF8u, 0x80u, 0x80u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Maximum_32_bit_integer_input()
    {
        var integers = new[] { 0xFFFFFFFFu };
        var expected = new[] { 0x8Fu, 0xFFu, 0xFFu, 0xFFu, 0x7Fu };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Two_single_byte_values()
    {
        var integers = new[] { 0x40u, 0x7Fu };
        var expected = new[] { 0x40u, 0x7Fu };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Two_multi_byte_values()
    {
        var integers = new[] { 0x4000u, 0x123456u };
        var expected = new[] { 0x81u, 0x80u, 0x0u, 0xC8u, 0xE8u, 0x56u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Many_multi_byte_values()
    {
        var integers = new[] { 0x2000u, 0x123456u, 0xFFFFFFFu, 0x0u, 0x3FFFu, 0x4000u };
        var expected = new[] { 0xC0u, 0x0u, 0xC8u, 0xE8u, 0x56u, 0xFFu, 0xFFu, 0xFFu, 0x7Fu, 0x0u, 0xFFu, 0x7Fu, 0x81u, 0x80u, 0x0u };
        Assert.Equal(expected, VariableLengthQuantity.Encode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void One_byte()
    {
        var integers = new[] { 0x7Fu };
        var expected = new[] { 0x7Fu };
        Assert.Equal(expected, VariableLengthQuantity.Decode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Two_bytes()
    {
        var integers = new[] { 0xC0u, 0x0u };
        var expected = new[] { 0x2000u };
        Assert.Equal(expected, VariableLengthQuantity.Decode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Three_bytes()
    {
        var integers = new[] { 0xFFu, 0xFFu, 0x7Fu };
        var expected = new[] { 0x1FFFFFu };
        Assert.Equal(expected, VariableLengthQuantity.Decode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Four_bytes()
    {
        var integers = new[] { 0x81u, 0x80u, 0x80u, 0x0u };
        var expected = new[] { 0x200000u };
        Assert.Equal(expected, VariableLengthQuantity.Decode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Maximum_32_bit_integer()
    {
        var integers = new[] { 0x8Fu, 0xFFu, 0xFFu, 0xFFu, 0x7Fu };
        var expected = new[] { 0xFFFFFFFFu };
        Assert.Equal(expected, VariableLengthQuantity.Decode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Incomplete_sequence_causes_error()
    {
        var integers = new[] { 0xFFu };
        Assert.Throws<InvalidOperationException>(() => VariableLengthQuantity.Decode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Incomplete_sequence_causes_error_even_if_value_is_zero()
    {
        var integers = new[] { 0x80u };
        Assert.Throws<InvalidOperationException>(() => VariableLengthQuantity.Decode(integers));
    }

    [Fact(Skip = "Remove to run test")]
    public void Multiple_values()
    {
        var integers = new[] { 0xC0u, 0x0u, 0xC8u, 0xE8u, 0x56u, 0xFFu, 0xFFu, 0xFFu, 0x7Fu, 0x0u, 0xFFu, 0x7Fu, 0x81u, 0x80u, 0x0u };
        var expected = new[] { 0x2000u, 0x123456u, 0xFFFFFFFu, 0x0u, 0x3FFFu, 0x4000u };
        Assert.Equal(expected, VariableLengthQuantity.Decode(integers));
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

public static class VariableLengthQuantity
{
    private const uint ContinuationMask = 0x80u;

    public static uint[] Encode(uint[] numbers) => numbers.SelectMany(number => EncodeNumber(number)).ToArray();
    public static uint[] Decode(uint[] bytes) => DecodeFragments(bytes).ToArray();

    private static uint GetFirst7Bits(uint number) => number & 0x7fu;
    private static bool HasContinuationBit(uint number) => (number & ContinuationMask) != 0;

    private static IEnumerable<uint> EncodeNumber(uint number)
    {
        var result = new List<uint> { GetFirst7Bits(number) };

        number >>= 7;

        while (number != 0)
        {
            result.Add(GetFirst7Bits(number) | ContinuationMask);
            number >>= 7;
        }

        return Enumerable.Reverse(result);
    }

    private static IEnumerable<uint> DecodeFragments(uint[] fragments)
    {
        if (HasContinuationBit(fragments.Last()))
        {
            throw new InvalidOperationException("Input is not a complete VLQ-encoded sequence");
        }

        var result = 0U;
        foreach (var fragment in fragments)
        {
            result = (result << 7) + GetFirst7Bits(fragment);

            if (!HasContinuationBit(fragment))
            {
                yield return result;
                result = 0;
            }
        }
    }
}

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?