Avatar of 4d47
0
1
Genius
0
0

4d47's solution

to Variable Length Quantity in the PHP Track

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

Running the tests

  1. Go to the root of your PHP exercise directory, which is <EXERCISM_WORKSPACE>/php. To find the Exercism workspace run

     % exercism debug | grep Workspace
    
  2. Get PHPUnit if you don't have it already.

     % wget --no-check-certificate https://phar.phpunit.de/phpunit.phar
     % chmod +x phpunit.phar
    
  3. Execute the tests:

     % ./phpunit.phar variable-length-quantity/variable-length-quantity_test.php
    

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.

variable-length-quantity_test.php

<?php

require_once 'variable-length-quantity.php';

class VariableLengthQuantityTest extends PHPUnit\Framework\TestCase
{
    public function testItEncodesSingleBytes()
    {
        $this->assertEquals([0x00], vlq_encode([0x00]));
        $this->assertEquals([0x40], vlq_encode([0x40]));
        $this->assertEquals([0x7f], vlq_encode([0x7f]));
    }

    public function testItEncodesDoubleBytes()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x81, 0x00], vlq_encode([0x80]));
        $this->assertEquals([0xc0, 0x00], vlq_encode([0x2000]));
        $this->assertEquals([0xff, 0x7f], vlq_encode([0x3fff]));
    }

    public function testItEncodesTripleBytes()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x81, 0x80, 0x00], vlq_encode([0x4000]));
        $this->assertEquals([0xc0, 0x80, 0x00], vlq_encode([0x100000]));
        $this->assertEquals([0xff, 0xff, 0x7f], vlq_encode([0x1fffff]));
    }

    public function testItEncodesQuadrupleBytes()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x81, 0x80, 0x80, 0x00], vlq_encode([0x200000]));
        $this->assertEquals([0xc0, 0x80, 0x80, 0x00], vlq_encode([0x8000000]));
        $this->assertEquals([0xff, 0xff, 0xff, 0x7f], vlq_encode([0xfffffff]));
    }

    public function testItEncodesMultipleValues()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x00, 0x00], vlq_encode([0x00, 0x00]));
        $this->assertEquals([0x40, 0x7f], vlq_encode([0x40, 0x7f]));
        $this->assertEquals([0x81, 0x80, 0x00, 0xc8, 0xe8, 0x56], vlq_encode([0x4000, 0x123456]));
        $this->assertEquals([
                0xc0, 0x00, 0xc8, 0xe8, 0x56,
                0xff, 0xff, 0xff, 0x7f, 0x00,
                0xff, 0x7f, 0x81, 0x80, 0x00,
        ], vlq_encode(
            [0x2000, 0x123456, 0x0fffffff, 0x00, 0x3fff, 0x4000]
        ));
    }

    public function testItDecodesFromSyngleBytes()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x00], vlq_decode([0x00]));
        $this->assertEquals([0x40], vlq_decode([0x40]));
        $this->assertEquals([0x7f], vlq_decode([0x7f]));
    }

    public function testItDecodesDoubleBytes()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x80], vlq_decode([0x81, 0x00]));
        $this->assertEquals([0x2000], vlq_decode([0xc0, 0x00]));
        $this->assertEquals([0x3fff], vlq_decode([0xff, 0x7f]));
    }

    public function testItDecodesTripleBytes()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x4000], vlq_decode([0x81, 0x80, 0x00]));
        $this->assertEquals([0x100000], vlq_decode([0xc0, 0x80, 0x00]));
        $this->assertEquals([0x1FFFFF], vlq_decode([0xff, 0xff, 0x7f]));
    }

    public function testItDecodesQuadrupleBytes()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x200000], vlq_decode([0x81, 0x80, 0x80, 0x00]));
        $this->assertEquals([0x8000000], vlq_decode([0xc0, 0x80, 0x80, 0x00]));
        $this->assertEquals([0xFFFFFFF], vlq_decode([0xff, 0xff, 0xff, 0x7f]));
    }

    public function testItDecodesMultipleValues()
    {
        $this->markTestSkipped();

        $this->assertEquals([0x00, 0x00], vlq_decode([0x00, 0x00]));
        $this->assertEquals([0x40, 0x7f], vlq_decode([0x40, 0x7f]));
        $this->assertEquals([0x4000, 0x123456], vlq_decode([0x81, 0x80, 0x00, 0xc8, 0xe8, 0x56]));
        $this->assertEquals(
            [0x2000, 0x123456, 0x0fffffff, 0x00, 0x3fff, 0x4000],
            vlq_decode([
                0xc0, 0x00, 0xc8, 0xe8, 0x56,
                0xff, 0xff, 0xff, 0x7f, 0x00,
                0xff, 0x7f, 0x81, 0x80, 0x00,
            ])
        );
    }

    public function testIncompleteByteSequence()
    {
        $this->markTestSkipped();

        $this->expectException(InvalidArgumentException::class);

        vlq_decode([0xff]);
    }

    public function testOverflow()
    {
        $this->markTestSkipped();

        $this->expectException(OverflowException::class);

        vlq_decode([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f]);
    }

    public function testChainedDecodeEncodeGivesOriginalBytes()
    {
        $this->markTestSkipped();

        $bytes = [
            0xc0, 0x00, 0xc8, 0xe8, 0x56,
            0xff, 0xff, 0xff, 0x7f, 0x00,
            0xff, 0x7f, 0x81, 0x80, 0x00,
        ];

        $this->assertTrue($bytes === vlq_encode(vlq_decode($bytes)));
    }

    public function testChainedEncodeDecodeGivesOriginalIntegers()
    {
        $this->markTestSkipped();

        $integers = [0x2000, 0x123456, 0x0fffffff, 0x00, 0x3fff, 0x4000];

        $this->assertEquals($integers, vlq_decode(vlq_encode($integers)));
    }
}
<?php

function vlq_encode(array $nums): array
{
    return array_merge(...array_map('encode', $nums));
}

function vlq_decode(array $octets): array
{
    $word = [];
    $nums = [];
    foreach ($octets as $octet) {
        $word[] = $octet;
        if (!($octet & 128)) {
            $nums[] = decode($word);
            $word = [];
        }
    }
    if ($word) {
        throw new InvalidArgumentException('Incomplete byte sequence');
    }
    return $nums;
}

function encode(int $n): array
{
    $octets = [];
    do {
        [$n, $remainder] = divmod($n, 128);
        if ($octets) {
            $remainder |= 128;
        }
        array_unshift($octets, $remainder);
    } while ($n > 0);
    return $octets;
}

function decode(array $octets): int
{
    $value = 0;
    foreach (array_reverse($octets) as $i => $octet) {
        if ($octet & 128) {
            $octet ^= 128;
        }
        $value += $octet * 128 ** $i;
        if (is_float($value)) {
            // http://php.net/manual/en/language.types.integer.php#language.types.integer.overflow
            throw new OverflowException();
        }
    }
    return $value;
}

function divmod(int $dividend, int $divisor): array
{
    return [intdiv($dividend, $divisor), $dividend % $divisor];
}

What can you learn from this solution?

A huge amount can be learnt 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 I could read more about to develop my understanding?