From 5fd92e513024db6cdbb825c4e926e01eff6737e2 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sun, 23 Sep 2018 22:48:32 +0200 Subject: solve variable-length-quantity --- go/variable-length-quantity/.solution.json | 1 + go/variable-length-quantity/README.md | 56 ++++++++ go/variable-length-quantity/cases_test.go | 152 +++++++++++++++++++++ .../variable_length_quantity.go | 59 ++++++++ .../variable_length_quantity_test.go | 33 +++++ 5 files changed, 301 insertions(+) create mode 100644 go/variable-length-quantity/.solution.json create mode 100644 go/variable-length-quantity/README.md create mode 100644 go/variable-length-quantity/cases_test.go create mode 100644 go/variable-length-quantity/variable_length_quantity.go create mode 100644 go/variable-length-quantity/variable_length_quantity_test.go diff --git a/go/variable-length-quantity/.solution.json b/go/variable-length-quantity/.solution.json new file mode 100644 index 0000000..1085b09 --- /dev/null +++ b/go/variable-length-quantity/.solution.json @@ -0,0 +1 @@ +{"track":"go","exercise":"variable-length-quantity","id":"f6276ea385294e809d2c79a284cc2109","url":"https://exercism.io/my/solutions/f6276ea385294e809d2c79a284cc2109","handle":"dim13","is_requester":true,"auto_approve":false} \ No newline at end of file diff --git a/go/variable-length-quantity/README.md b/go/variable-length-quantity/README.md new file mode 100644 index 0000000..102efbd --- /dev/null +++ b/go/variable-length-quantity/README.md @@ -0,0 +1,56 @@ +# Variable Length Quantity + +Implement variable length quantity encoding and decoding. + +The goal of this exercise is to implement [VLQ](https://en.wikipedia.org/wiki/Variable-length_quantity) 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: + +```text + 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 + +To run the tests run the command `go test` from within the exercise directory. + +If the test suite contains benchmarks, you can run these with the `--bench` and `--benchmem` +flags: + + go test -v --bench . --benchmem + +Keep in mind that each reviewer will run benchmarks on a different machine, with +different specs, so the results from these benchmark tests may vary. + +## Further information + +For more detailed information about the Go track, including how to get help if +you're having trouble, please visit the exercism.io [Go language page](http://exercism.io/languages/go/about). + +## Source + +A poor Splice developer having to implement MIDI encoding/decoding. [https://splice.com](https://splice.com) + +## Submitting Incomplete Solutions +It's possible to submit an incomplete solution so you can see how others have completed the exercise. diff --git a/go/variable-length-quantity/cases_test.go b/go/variable-length-quantity/cases_test.go new file mode 100644 index 0000000..71d71a6 --- /dev/null +++ b/go/variable-length-quantity/cases_test.go @@ -0,0 +1,152 @@ +package variablelengthquantity + +// Source: exercism/problem-specifications +// Commit: 48dc5e6 variable-length-quantity: Apply new "input" policy +// Problem Specifications Version: 1.1.0 + +// Encode a series of integers, producing a series of bytes. +var encodeTestCases = []struct { + description string + input []uint32 + output []byte +}{ + { + "zero", + []uint32{0x0}, + []byte{0x0}, + }, + { + "arbitrary single byte", + []uint32{0x40}, + []byte{0x40}, + }, + { + "largest single byte", + []uint32{0x7f}, + []byte{0x7f}, + }, + { + "smallest double byte", + []uint32{0x80}, + []byte{0x81, 0x0}, + }, + { + "arbitrary double byte", + []uint32{0x2000}, + []byte{0xc0, 0x0}, + }, + { + "largest double byte", + []uint32{0x3fff}, + []byte{0xff, 0x7f}, + }, + { + "smallest triple byte", + []uint32{0x4000}, + []byte{0x81, 0x80, 0x0}, + }, + { + "arbitrary triple byte", + []uint32{0x100000}, + []byte{0xc0, 0x80, 0x0}, + }, + { + "largest triple byte", + []uint32{0x1fffff}, + []byte{0xff, 0xff, 0x7f}, + }, + { + "smallest quadruple byte", + []uint32{0x200000}, + []byte{0x81, 0x80, 0x80, 0x0}, + }, + { + "arbitrary quadruple byte", + []uint32{0x8000000}, + []byte{0xc0, 0x80, 0x80, 0x0}, + }, + { + "largest quadruple byte", + []uint32{0xfffffff}, + []byte{0xff, 0xff, 0xff, 0x7f}, + }, + { + "smallest quintuple byte", + []uint32{0x10000000}, + []byte{0x81, 0x80, 0x80, 0x80, 0x0}, + }, + { + "arbitrary quintuple byte", + []uint32{0xff000000}, + []byte{0x8f, 0xf8, 0x80, 0x80, 0x0}, + }, + { + "maximum 32-bit integer input", + []uint32{0xffffffff}, + []byte{0x8f, 0xff, 0xff, 0xff, 0x7f}, + }, + { + "two single-byte values", + []uint32{0x40, 0x7f}, + []byte{0x40, 0x7f}, + }, + { + "two multi-byte values", + []uint32{0x4000, 0x123456}, + []byte{0x81, 0x80, 0x0, 0xc8, 0xe8, 0x56}, + }, + { + "many multi-byte values", + []uint32{0x2000, 0x123456, 0xfffffff, 0x0, 0x3fff, 0x4000}, + []byte{0xc0, 0x0, 0xc8, 0xe8, 0x56, 0xff, 0xff, 0xff, 0x7f, 0x0, 0xff, 0x7f, 0x81, 0x80, 0x0}, + }, +} + +// Decode a series of bytes, producing a series of integers. +var decodeTestCases = []struct { + description string + input []byte + output []uint32 // nil slice indicates error expected. +}{ + + { + "one byte", + []byte{0x7f}, + []uint32{0x7f}, + }, + { + "two bytes", + []byte{0xc0, 0x0}, + []uint32{0x2000}, + }, + { + "three bytes", + []byte{0xff, 0xff, 0x7f}, + []uint32{0x1fffff}, + }, + { + "four bytes", + []byte{0x81, 0x80, 0x80, 0x0}, + []uint32{0x200000}, + }, + { + "maximum 32-bit integer", + []byte{0x8f, 0xff, 0xff, 0xff, 0x7f}, + []uint32{0xffffffff}, + }, + { + "incomplete sequence causes error", + []byte{0xff}, + []uint32(nil), + }, + { + "incomplete sequence causes error, even if value is zero", + []byte{0x80}, + []uint32(nil), + }, + { + "multiple values", + []byte{0xc0, 0x0, 0xc8, 0xe8, 0x56, 0xff, 0xff, 0xff, 0x7f, 0x0, 0xff, 0x7f, 0x81, 0x80, 0x0}, + []uint32{0x2000, 0x123456, 0xfffffff, 0x0, 0x3fff, 0x4000}, + }, +} diff --git a/go/variable-length-quantity/variable_length_quantity.go b/go/variable-length-quantity/variable_length_quantity.go new file mode 100644 index 0000000..9df99d9 --- /dev/null +++ b/go/variable-length-quantity/variable_length_quantity.go @@ -0,0 +1,59 @@ +package variablelengthquantity + +import ( + "bytes" + "io" +) + +func decodeVarint(r io.ByteReader) (uint32, error) { + var i uint32 + for { + b, err := r.ReadByte() + if err != nil { + return 0, err + } + i = (i << 7) | uint32(b&0x7f) + if b&0x80 == 0 { + return i, nil + } + } +} + +func DecodeVarint(b []byte) ([]uint32, error) { + var ret []uint32 + r := bytes.NewReader(b) + for r.Len() > 0 { + u, err := decodeVarint(r) + if err != nil { + return nil, err + } + ret = append(ret, u) + } + return ret, nil +} + +func encodeVarint(w io.ByteWriter, u uint32) { + if u == 0 { + w.WriteByte(0) + return + } + var l int + for i := u; i > 0; i >>= 7 { + l++ + } + for i := l - 1; i >= 0; i-- { + o := byte(u >> uint(i*7) & 0x7f) + if i != 0 { + o |= 0x80 + } + w.WriteByte(o) + } +} + +func EncodeVarint(u []uint32) []byte { + w := new(bytes.Buffer) + for _, v := range u { + encodeVarint(w, v) + } + return w.Bytes() +} diff --git a/go/variable-length-quantity/variable_length_quantity_test.go b/go/variable-length-quantity/variable_length_quantity_test.go new file mode 100644 index 0000000..537f5ac --- /dev/null +++ b/go/variable-length-quantity/variable_length_quantity_test.go @@ -0,0 +1,33 @@ +package variablelengthquantity + +import ( + "bytes" + "reflect" + "testing" +) + +func TestDecodeVarint(t *testing.T) { + for i, tc := range decodeTestCases { + o, err := DecodeVarint(tc.input) + if err != nil { + var _ error = err + if tc.output != nil { + t.Fatalf("FAIL: case %d | %s\nexpected %#v got error: %q\n", i, tc.description, tc.output, err) + } + } else if tc.output == nil { + t.Fatalf("FAIL: case %d | %s\nexpected error, got %#v\n", i, tc.description, o) + } else if !reflect.DeepEqual(o, tc.output) { + t.Fatalf("FAIL: case %d | %s\nexpected\t%#v\ngot\t\t%#v\n", i, tc.description, tc.output, o) + } + t.Logf("PASS: case %d | %s\n", i, tc.description) + } +} + +func TestEncodeVarint(t *testing.T) { + for i, tc := range encodeTestCases { + if encoded := EncodeVarint(tc.input); bytes.Compare(encoded, tc.output) != 0 { + t.Fatalf("FAIL: case %d | %s\nexpected\t%#v\ngot\t\t%#v\n", i, tc.description, tc.output, encoded) + } + t.Logf("PASS: case %d | %s\n", i, tc.description) + } +} -- cgit v1.2.3