summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2018-09-23 22:48:32 +0200
committerDimitri Sokolyuk <demon@dim13.org>2018-09-23 22:48:32 +0200
commit5fd92e513024db6cdbb825c4e926e01eff6737e2 (patch)
tree3bae1e5987c47a2f89e5199af9ac026448080630
parent2551d7af4e75d863233c529a901375ef940ae98d (diff)
solve variable-length-quantity
-rw-r--r--go/variable-length-quantity/.solution.json1
-rw-r--r--go/variable-length-quantity/README.md56
-rw-r--r--go/variable-length-quantity/cases_test.go152
-rw-r--r--go/variable-length-quantity/variable_length_quantity.go59
-rw-r--r--go/variable-length-quantity/variable_length_quantity_test.go33
5 files changed, 301 insertions, 0 deletions
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)
+ }
+}