Index: src/0dev.org/commands/mtf/main.go ================================================================== --- src/0dev.org/commands/mtf/main.go +++ src/0dev.org/commands/mtf/main.go @@ -1,56 +1,50 @@ package main import ( mtf "0dev.org/encoding/mtf" iou "0dev.org/ioutil" + "flag" "fmt" "io" "os" ) func main() { - var code int - switch { - case len(os.Args) == 1: - code = transform(os.Stdout, os.Stdin) - case len(os.Args) == 2 && os.Args[1] == "-d": - code = reverse(os.Stdout, os.Stdin) - default: - fmt.Fprintln(os.Stdout, "Usage: mtf [-d]") - } + d := flag.Bool("d", false, "Use to toggle decode mode") + flag.Parse() + + var code int + if *d { + code = decode(os.Stdout, os.Stdin) + } else { + code = encode(os.Stdout, os.Stdin) + } + os.Exit(code) } // Transforms the data according to the move-to-front algorithm // I/O is buffered for better performance -func transform(output io.Writer, input io.Reader) int { +func encode(output io.Writer, input io.Reader) int { var ( err error - buffer io.Writer = iou.SizedWriter(output, 4096) - encoder io.Writer = mtf.Encoder(buffer) + encoder io.Reader = mtf.Encoder(iou.SizedReader(input, 4096)) ) - _, err = io.Copy(encoder, input) + _, err = io.Copy(output, encoder) if err != nil { fmt.Fprintln(os.Stderr, "Error while encoding.\n", err) return 1 } - // Flush the buffer - _, err = buffer.Write(nil) - if err != nil { - fmt.Fprintln(os.Stderr, "Error while flushing output buffer.\n", err) - return 1 - } - return 0 } // Reverses MTF`ed data and writes back the original bytes // I/O is buffered for better performance -func reverse(output io.Writer, input io.Reader) int { +func decode(output io.Writer, input io.Reader) int { var ( err error decoder io.Reader = mtf.Decoder(iou.SizedReader(input, 4096)) ) Index: src/0dev.org/encoding/mtf/mtf.go ================================================================== --- src/0dev.org/encoding/mtf/mtf.go +++ src/0dev.org/encoding/mtf/mtf.go @@ -27,47 +27,25 @@ 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 +// Encodes data in place +func (c *context) encode(data []byte) { for index, value := range data { // Shortcut for sequential, equal values if c.table[0] == value { - buffer[index] = 0 + data[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 + data[index] = j // Shift the table copy(c.table[1:], c.table[:j]) // Restore the value in front and break @@ -74,15 +52,54 @@ c.table[0] = value break } } } +} + +// Decode data in place +func (c *context) decode(data []byte) { + for index, value := range data { + position := value + + // Shortcut for sequential, equal values + if position == 0 { + data[index] = c.table[0] + continue + } + + // Output the value + data[index] = c.table[position] + + // Shift the table and restore the value in front + copy(c.table[1:], c.table[:position]) + c.table[0] = data[index] + } +} + +// Returns an MTF encoder over the provided io.Reader +func Encoder(reader io.Reader) io.Reader { + var enc encoder + enc.table = initial + enc.source = reader + return &enc +} + +type encoder struct { + context + source io.Reader +} + +// Read and encode data in place +func (c *encoder) Read(output []byte) (count int, err error) { + count, err = c.source.Read(output) + c.encode(output[:count]) - return c.target.Write(buffer) + return count, err } -// Returns an MTF decoder over the provided io.Writer +// Returns an MTF decoder over the provided io.Reader func Decoder(reader io.Reader) io.Reader { var dec decoder dec.table = initial dec.source = reader return &dec @@ -91,33 +108,12 @@ 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 +// Read and decode data in place +func (c *decoder) Read(output []byte) (count int, err error) { 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] - } + c.decode(output[:count]) return count, err } 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 @@ -5,57 +5,78 @@ "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) - } -} +func TestMTF(t *testing.T) { + var ( + data []byte = []byte{1, 1, 0, 0} + + input *bytes.Reader = bytes.NewReader(data) + encoder io.Reader = Encoder(input) + decoder io.Reader = Decoder(encoder) + + output bytes.Buffer + ) + + io.Copy(&output, decoder) + processed := output.Bytes() + + delta := diff.Diff(diff.D{Len1: len(data), Len2: len(processed), + EqualFunc: func(i, j int) bool { return data[i] == processed[j] }}) + if len(delta.Added) > 0 || len(delta.Removed) > 0 { + t.Error("Differences detected ", delta) + } +} + +// 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) +// } +// }