Avatar of pdmoore

pdmoore's solution

to Variable Length Quantity in the Java Track

Published at Apr 24 2020 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

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

Setup

Go through the setup instructions for Java to install the necessary dependencies:

https://exercism.io/tracks/java/installation

Running the tests

You can run all the tests for an exercise by entering the following in your terminal:

$ gradle test

Use gradlew.bat if you're on Windows

In the test suites all tests but the first have been skipped.

Once you get a test passing, you can enable the next one by removing the @Ignore("Remove to run test") annotation.

Source

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.

VariableLengthQuantityTest.java

import org.junit.Before;
import org.junit.Ignore;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.ExpectedException;

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.List;

public class VariableLengthQuantityTest {
    @Rule
    public ExpectedException expectedException = ExpectedException.none();

    private VariableLengthQuantity variableLengthQuantity;

    @Before
    public void setup() {
        variableLengthQuantity = new VariableLengthQuantity();
    }

    @Test
    public void testZero() {
        List<String> expected = Arrays.asList("0x0");
        List<Long> numbers = Arrays.asList(0x0L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testArbitrarySingleByte() {
        List<String> expected = Arrays.asList("0x40");
        List<Long> numbers = Arrays.asList(0x40L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testLargestSingleByte() {
        List<String> expected = Arrays.asList("0x7f");
        List<Long> numbers = Arrays.asList(0x7fL);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testSmallestDoubleByte() {
        List<String> expected = Arrays.asList("0x81", "0x0");
        List<Long> numbers = Arrays.asList(0x80L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testArbitraryDoubleByte() {
        List<String> expected = Arrays.asList("0xc0", "0x0");
        List<Long> numbers = Arrays.asList(0x2000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testLargestDoubleByte() {
        List<String> expected = Arrays.asList("0xff", "0x7f");
        List<Long> numbers = Arrays.asList(0x3fffL);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testSmallestTripleByte() {
        List<String> expected = Arrays.asList("0x81", "0x80", "0x0");
        List<Long> numbers = Arrays.asList(0x4000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testArbitraryTripleByte() {
        List<String> expected = Arrays.asList("0xc0", "0x80", "0x0");
        List<Long> numbers = Arrays.asList(0x100000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testLargestTripleByte() {
        List<String> expected = Arrays.asList("0xff", "0xff", "0x7f");
        List<Long> numbers = Arrays.asList(0x1fffffL);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testSmallestQuadrupleByte() {
        List<String> expected = Arrays.asList("0x81", "0x80", "0x80", "0x0");
        List<Long> numbers = Arrays.asList(0x200000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testArbitraryQuadrupleByte() {
        List<String> expected = Arrays.asList("0xc0", "0x80", "0x80", "0x0");
        List<Long> numbers = Arrays.asList(0x8000000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testLargestQuadrupleByte() {
        List<String> expected = Arrays.asList("0xff", "0xff", "0xff", "0x7f");
        List<Long> numbers = Arrays.asList(0xfffffffL);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testSmallestQuintupleByte() {
        List<String> expected = Arrays.asList("0x81", "0x80", "0x80", "0x80", "0x0");
        List<Long> numbers = Arrays.asList(0x10000000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testArbitraryQuintupleByte() {
        List<String> expected = Arrays.asList("0x8f", "0xf8", "0x80", "0x80", "0x0");
        List<Long> numbers = Arrays.asList(0xff000000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testMaximum32BitIntegerInput() {
        List<String> expected = Arrays.asList("0x8f", "0xff", "0xff", "0xff", "0x7f");
        List<Long> numbers = Arrays.asList(0xffffffffL);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testTwoSingleByteValues() {
        List<String> expected = Arrays.asList("0x40", "0x7f");
        List<Long> numbers = Arrays.asList(0x40L, 0x7fL);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testTwoMultiByteValues() {
        List<String> expected = Arrays.asList("0x81", "0x80", "0x0", "0xc8", "0xe8", "0x56");
        List<Long> numbers = Arrays.asList(0x4000L, 0x123456L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testManyMultiByteValues() {
        List<String> expected = Arrays.asList("0xc0", "0x0", "0xc8", "0xe8",
                                              "0x56", "0xff", "0xff", "0xff",
                                              "0x7f", "0x0", "0xff", "0x7f",
                                              "0x81", "0x80", "0x0");
        List<Long> numbers = Arrays.asList(0x2000L, 0x123456L, 0xfffffffL,
                                           0x0L, 0x3fffL, 0x4000L);

        assertEquals(expected, variableLengthQuantity.encode(numbers));
    }

    @Ignore("Remove to run test")
    @Test
    public void testDecodeOneByte() {
        List<String> expected = Arrays.asList("0x7f");
        List<Long> bytes = Arrays.asList(0x7fL);

        assertEquals(expected, variableLengthQuantity.decode(bytes));
    }

    @Ignore("Remove to run test")
    @Test
    public void testDecodeTwoBytes() {
        List<String> expected = Arrays.asList("0x2000");
        List<Long> bytes = Arrays.asList(0xc0L, 0x0L);

        assertEquals(expected, variableLengthQuantity.decode(bytes));
    }

    @Ignore("Remove to run test")
    @Test
    public void testDecodeThreeBytes() {
        List<String> expected = Arrays.asList("0x1fffff");
        List<Long> bytes = Arrays.asList(0xffL, 0xffL, 0x7fL);

        assertEquals(expected, variableLengthQuantity.decode(bytes));
    }

    @Ignore("Remove to run test")
    @Test
    public void testDecodeFourBytes() {
        List<String> expected = Arrays.asList("0x200000");
        List<Long> bytes = Arrays.asList(0x81L, 0x80L, 0x80L, 0x0L);

        assertEquals(expected, variableLengthQuantity.decode(bytes));
    }

    @Ignore("Remove to run test")
    @Test
    public void testDecodeMaximum32BitInteger() {
        List<String> expected = Arrays.asList("0xffffffff");
        List<Long> bytes = Arrays.asList(0x8fL, 0xffL, 0xffL, 0xffL, 0x7fL);

        assertEquals(expected, variableLengthQuantity.decode(bytes));
    }

    @Ignore("Remove to run test")
    @Test
    public void testCannotDecodeIncompleteSequence() {
        List<Long> bytes = Arrays.asList(0xffL);
        expectedException.expect(IllegalArgumentException.class);
        expectedException.expectMessage("Invalid variable-length quantity encoding");

        variableLengthQuantity.decode(bytes);
    }

    @Ignore("Remove to run test")
    @Test
    public void testCannotDecodeIncompleteSequenceEvenIfValueIsZero() {
        List<Long> bytes = Arrays.asList(0x80L);
        expectedException.expect(IllegalArgumentException.class);
        expectedException.expectMessage("Invalid variable-length quantity encoding");

        variableLengthQuantity.decode(bytes);
    }

    @Ignore("Remove to run test")
    @Test
    public void testDecodeMultipleBytes() {
        List<String> expected = Arrays.asList("0x2000", "0x123456",
                                              "0xfffffff", "0x0", "0x3fff",
                                              "0x4000");
        List<Long> bytes = Arrays.asList(0xc0L, 0x0L, 0xc8L, 0xe8L, 0x56L,
                                         0xffL, 0xffL, 0xffL, 0x7fL, 0x0L,
                                         0xffL, 0x7fL, 0x81L, 0x80L, 0x0L);

        assertEquals(expected, variableLengthQuantity.decode(bytes));
    }
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

class VariableLengthQuantity {

    private static final int VLQ_BYTE_LENGTH = 7;
    public static final long SET_BIT_7 = 128;
    public static final String HEX_PREFIX = "0x";
    public static final int LARGEST_7_BIT_NUMBER = 128;

    List<String> encode(List<Long> numbers) {
        return numbers.stream()
                .map(this::encodeSingleNumber)
                .flatMap(List::stream)
                .collect(Collectors.toList());
    }

    private List<String> encodeSingleNumber(Long number) {
        List<String> vlqBytes = new ArrayList<>();

        vlqBytes.add(convertLeftmostBitsToHex(getNext7BitsOf(number)));
        number >>= VLQ_BYTE_LENGTH;

        while (number > 0) {
            vlqBytes.add(convertLeftmostBitsToHex(SET_BIT_7 | (getNext7BitsOf(number))));
            number >>= VLQ_BYTE_LENGTH;
        }

        Collections.reverse(vlqBytes);
        return vlqBytes;
    }

    private long getNext7BitsOf(Long number) {
        return number & 0x7Fl;
    }

    private String convertLeftmostBitsToHex(long l) {
        return HEX_PREFIX + Long.toHexString(l);
    }

    List<String> decode(List<Long> seriesOfSevenBitBytes) {
        ArrayList<ArrayList<Long>> encodedVLQs = breakIntoEncodedVLQs(seriesOfSevenBitBytes);

        List<String> result = encodedVLQs.stream()
                .map(this::decodeSingleNumber)
                .collect(Collectors.toList());

        return result;
    }

    private ArrayList<ArrayList<Long>> breakIntoEncodedVLQs(List<Long> bytes) {
        ArrayList<ArrayList<Long>> allEncodedVLQs = new ArrayList<ArrayList<Long>>();

        ArrayList<Long> BytesInASingleVLQ = new ArrayList<>();
        for (int i = 0; i < bytes.size(); i++) {
            Long sevenBitByte = bytes.get(i);
            BytesInASingleVLQ.add(sevenBitByte);

            if (sevenBitByte < LARGEST_7_BIT_NUMBER) {
                allEncodedVLQs.add(BytesInASingleVLQ);
                BytesInASingleVLQ = new ArrayList<>();
            }
        }

        if (allEncodedVLQs.isEmpty()) {
            throw new IllegalArgumentException("Invalid variable-length quantity encoding");
        }
        return allEncodedVLQs;
    }

    private String decodeSingleNumber(List<Long> encodedVLQ) {
        // TODO - currently converts long->string->hex string
        return convertBitStringToHex(encodedVLQ.stream()
                .map(Long::toBinaryString).map(this::ensureExactly7BitLength).
                        collect(Collectors.joining()));
    }

    private String ensureExactly7BitLength(String bitString) {
        if (bitString.length() == 8) {
            bitString = bitString.substring(1);
        }

        return String.format("%1$7s", bitString).replace(' ', '0');
    }

    private String convertBitStringToHex(String bits) {
        return HEX_PREFIX + Long.toHexString(Long.parseUnsignedLong(bits, 2));
    }
}

Community comments

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

pdmoore's Reflection

Definitely spent more time on this than any other problem. Would like better symmetry between encode and decode topmost methods.