Index: src/0dev.org/commands/mtf/main.go ================================================================== --- src/0dev.org/commands/mtf/main.go +++ src/0dev.org/commands/mtf/main.go @@ -1,10 +1,10 @@ package main import ( + mtf "0dev.org/encoding/mtf" iou "0dev.org/ioutil" - mtf "0dev.org/mtf" "fmt" "io" "os" ) Index: src/0dev.org/encoding/fibonacci/fib.go ================================================================== --- src/0dev.org/encoding/fibonacci/fib.go +++ src/0dev.org/encoding/fibonacci/fib.go @@ -13,10 +13,11 @@ import ( "io" ) +// Alias type with methods for encoding and decoding integers type Numbers []uint64 var ( // Used for encoding and decoding byte values bytesCodec = New(14) @@ -77,11 +78,12 @@ length++ } return result + f[length] - 1, length + 1 } -func Writer(target io.Writer) io.Writer { +// Returns a fibonacci encoder over the provided io.Writer +func Encoder(target io.Writer) io.Writer { var enc encoder enc.target = target return &enc } @@ -89,10 +91,11 @@ target io.Writer remaining byte length byte } +// Implements io.Writer func (e *encoder) Write(input []byte) (int, error) { var ( total int err error ) @@ -153,11 +156,12 @@ total++ } return total, err } -func Reader(source io.Reader) io.Reader { +// Returns a fibonacci decoder over the provided io.Reader +func Decoder(source io.Reader) io.Reader { var dec decoder dec.source = source return &dec } @@ -165,10 +169,11 @@ source io.Reader buffer uint64 at byte } +// Implements io.Reader func (d *decoder) Read(output []byte) (int, error) { var ( total int err error ) Index: src/0dev.org/encoding/fibonacci/fib_test.go ================================================================== --- src/0dev.org/encoding/fibonacci/fib_test.go +++ src/0dev.org/encoding/fibonacci/fib_test.go @@ -38,11 +38,11 @@ } func TestWriterReader(t *testing.T) { var ( buf bytes.Buffer - w io.Writer = Writer(&buf) + w io.Writer = Encoder(&buf) input []byte = make([]byte, 256) fib Numbers = New(16) ) for i := uint64(0); i < 256; i++ { @@ -81,11 +81,11 @@ output = output[len(vs):] } var ( in *bytes.Reader = bytes.NewReader(buf.Bytes()) - r io.Reader = Reader(in) + r io.Reader = Decoder(in) out bytes.Buffer ) io.Copy(&out, r) decoded := out.Bytes() ADDED src/0dev.org/encoding/mtf/mtf.go Index: src/0dev.org/encoding/mtf/mtf.go ================================================================== --- src/0dev.org/encoding/mtf/mtf.go +++ src/0dev.org/encoding/mtf/mtf.go @@ -0,0 +1,123 @@ +// Package mtf provides a move-to-front encoder and decoder implementations +package mtf + +import ( + "io" +) + +// A static table with the initial condition for the mtf algorithm +var initial [256]byte = [...]byte{ + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, + 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, + 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, + 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, + 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, + 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, + 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, + 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, + 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, + 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, + 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, + 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, + 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, + 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, + 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, + 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, +} + +type context struct { + table [256]byte +} + +// Returns an MTF encoder over the provided io.Writer +func Encoder(writer io.Writer) io.Writer { + var enc encoder + enc.table = initial + enc.target = writer + return &enc +} + +type encoder struct { + context + target io.Writer +} + +func (c *encoder) Write(data []byte) (int, error) { + var ( + dataLength int = len(data) + buffer []byte = make([]byte, dataLength) + ) + + // io.Write must not modify the passed data in any way + // TODO - check sync.Pool or a local free-list for amortizing buffers + // TODO - use a buffer with a fixed max size to avoid OOM conditions + + // Loop over the input data + for index, value := range data { + + // Shortcut for sequential, equal values + if c.table[0] == value { + buffer[index] = 0 + continue + } + + // Loop over the MTF table + for j := byte(1); j != 0; j++ { + if c.table[j] == value { + // Output the value + buffer[index] = j + + // Shift the table + copy(c.table[1:], c.table[:j]) + + // Restore the value in front and break + c.table[0] = value + break + } + } + } + + return c.target.Write(buffer) +} + +// Returns an MTF decoder over the provided io.Writer +func Decoder(reader io.Reader) io.Reader { + var dec decoder + dec.table = initial + dec.source = reader + return &dec +} + +type decoder struct { + context + source io.Reader +} + +func (c *decoder) Read(output []byte) (int, error) { + var ( + count int + err error + position byte + ) + + // Read from the source and decode in place + count, err = c.source.Read(output) + for i := 0; i < count; i++ { + position = output[i] + + // Shortcut for sequential, equal values + if position == 0 { + output[i] = c.table[0] + continue + } + + // Output the value + output[i] = c.table[position] + + // Shift the table and restore the value in front + copy(c.table[1:], c.table[:position]) + c.table[0] = output[i] + } + + return count, err +} ADDED src/0dev.org/encoding/mtf/mtf_test.go Index: src/0dev.org/encoding/mtf/mtf_test.go ================================================================== --- src/0dev.org/encoding/mtf/mtf_test.go +++ src/0dev.org/encoding/mtf/mtf_test.go @@ -0,0 +1,61 @@ +package mtf + +import ( + diff "0dev.org/diff" + "bytes" + "io" + "testing" +) + +func TestEncoder(t *testing.T) { + var ( + input []byte = []byte{1, 1, 0, 0} + expected []byte = []byte{1, 0, 1, 0} + + buffer bytes.Buffer + encoder io.Writer = Encoder(&buffer) + ) + + count, err := encoder.Write(input) + if count != len(input) { + t.Error("Unexpected write count from encoder", count) + } + if err != nil { + t.Error("Unexpected write error from encoder", err) + } + + output := buffer.Bytes() + + // Diff the output against the expected result + delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output), + EqualFunc: func(i, j int) bool { return expected[i] == output[j] }}) + if len(delta.Added) > 0 || len(delta.Removed) > 0 { + t.Error("Differences detected ", delta) + } +} + +func TestDecoder(t *testing.T) { + var ( + input []byte = []byte{1, 0, 1, 0} + expected []byte = []byte{1, 1, 0, 0} + output []byte = make([]byte, 4) + + reader *bytes.Reader = bytes.NewReader(input) + decoder io.Reader = Decoder(reader) + ) + + count, err := decoder.Read(output) + if count != len(output) { + t.Error("Unexpected read count from decoder", count) + } + if err != nil { + t.Error("Unexpected read error from decoder", err) + } + + // Diff the output against the expected result + delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output), + EqualFunc: func(i, j int) bool { return expected[i] == output[j] }}) + if len(delta.Added) > 0 || len(delta.Removed) > 0 { + t.Error("Differences detected ", delta) + } +} DELETED src/0dev.org/mtf/mtf.go Index: src/0dev.org/mtf/mtf.go ================================================================== --- src/0dev.org/mtf/mtf.go +++ src/0dev.org/mtf/mtf.go @@ -1,123 +0,0 @@ -// Package mtf provides a move-to-front encoder and decoder implementations -package mtf - -import ( - "io" -) - -// A static table with the initial condition for the mtf algorithm -var initial [256]byte = [...]byte{ - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, - 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, - 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, - 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, - 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, - 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, - 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, - 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, - 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, - 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, - 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, - 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, - 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, - 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, - 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, - 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, -} - -type context struct { - table [256]byte -} - -// Returns an MTF encoder over the provided io.Writer -func Encoder(writer io.Writer) io.Writer { - var enc encoder - enc.table = initial - enc.target = writer - return &enc -} - -type encoder struct { - context - target io.Writer -} - -func (c *encoder) Write(data []byte) (int, error) { - var ( - dataLength int = len(data) - buffer []byte = make([]byte, dataLength) - ) - - // io.Write must not modify the passed data in any way - // TODO - check sync.Pool or a local free-list for amortizing buffers - // TODO - use a buffer with a fixed max size to avoid OOM conditions - - // Loop over the input data - for index, value := range data { - - // Shortcut for sequential, equal values - if c.table[0] == value { - buffer[index] = 0 - continue - } - - // Loop over the MTF table - for j := byte(1); j != 0; j++ { - if c.table[j] == value { - // Output the value - buffer[index] = j - - // Shift the table - copy(c.table[1:], c.table[:j]) - - // Restore the value in front and break - c.table[0] = value - break - } - } - } - - return c.target.Write(buffer) -} - -// Returns an MTF decoder over the provided io.Writer -func Decoder(reader io.Reader) io.Reader { - var dec decoder - dec.table = initial - dec.source = reader - return &dec -} - -type decoder struct { - context - source io.Reader -} - -func (c *decoder) Read(output []byte) (int, error) { - var ( - count int - err error - position byte - ) - - // Read from the source and decode in place - count, err = c.source.Read(output) - for i := 0; i < count; i++ { - position = output[i] - - // Shortcut for sequential, equal values - if position == 0 { - output[i] = c.table[0] - continue - } - - // Output the value - output[i] = c.table[position] - - // Shift the table and restore the value in front - copy(c.table[1:], c.table[:position]) - c.table[0] = output[i] - } - - return count, err -} DELETED src/0dev.org/mtf/mtf_test.go Index: src/0dev.org/mtf/mtf_test.go ================================================================== --- src/0dev.org/mtf/mtf_test.go +++ src/0dev.org/mtf/mtf_test.go @@ -1,61 +0,0 @@ -package mtf - -import ( - diff "0dev.org/diff" - "bytes" - "io" - "testing" -) - -func TestEncoder(t *testing.T) { - var ( - input []byte = []byte{1, 1, 0, 0} - expected []byte = []byte{1, 0, 1, 0} - - buffer bytes.Buffer - encoder io.Writer = Encoder(&buffer) - ) - - count, err := encoder.Write(input) - if count != len(input) { - t.Error("Unexpected write count from encoder", count) - } - if err != nil { - t.Error("Unexpected write error from encoder", err) - } - - output := buffer.Bytes() - - // Diff the output against the expected result - delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output), - EqualFunc: func(i, j int) bool { return expected[i] == output[j] }}) - if len(delta.Added) > 0 || len(delta.Removed) > 0 { - t.Error("Differences detected ", delta) - } -} - -func TestDecoder(t *testing.T) { - var ( - input []byte = []byte{1, 0, 1, 0} - expected []byte = []byte{1, 1, 0, 0} - output []byte = make([]byte, 4) - - reader *bytes.Reader = bytes.NewReader(input) - decoder io.Reader = Decoder(reader) - ) - - count, err := decoder.Read(output) - if count != len(output) { - t.Error("Unexpected read count from decoder", count) - } - if err != nil { - t.Error("Unexpected read error from decoder", err) - } - - // Diff the output against the expected result - delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output), - EqualFunc: func(i, j int) bool { return expected[i] == output[j] }}) - if len(delta.Added) > 0 || len(delta.Removed) > 0 { - t.Error("Differences detected ", delta) - } -}