Check-in [470d7e947b]
Overview
SHA1:470d7e947b552686794784b96cdb8dca2166b9e3
Date: 2015-01-04 12:24:08
User: spaskalev
Comment:encoding/mtf.Encoder now returns an io.Reader. This allows to encoding in place without allocating buffers.
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | folders | manifest
Tags And Properties
Context
2015-01-04
12:52
[6bd6e6d5c7] commands/mtf now uses fibonacci representation when encoding (user: spaskalev, tags: trunk)
12:24
[470d7e947b] encoding/mtf.Encoder now returns an io.Reader. This allows to encoding in place without allocating buffers. (user: spaskalev, tags: trunk)
2015-01-02
17:55
[783d0b7f51] update the copyright notice for 2015 (user: spaskalev, tags: trunk)
Changes

Modified src/0dev.org/commands/mtf/main.go from [8212c2eba2] to [a9b931eec8].

     1      1   package main
     2      2   
     3      3   import (
     4      4   	mtf "0dev.org/encoding/mtf"
     5      5   	iou "0dev.org/ioutil"
            6  +	"flag"
     6      7   	"fmt"
     7      8   	"io"
     8      9   	"os"
     9     10   )
    10     11   
    11     12   func main() {
           13  +	d := flag.Bool("d", false, "Use to toggle decode mode")
           14  +	flag.Parse()
           15  +
    12     16   	var code int
    13         -	switch {
    14         -	case len(os.Args) == 1:
    15         -		code = transform(os.Stdout, os.Stdin)
    16         -	case len(os.Args) == 2 && os.Args[1] == "-d":
    17         -		code = reverse(os.Stdout, os.Stdin)
    18         -	default:
    19         -		fmt.Fprintln(os.Stdout, "Usage: mtf [-d]")
           17  +	if *d {
           18  +		code = decode(os.Stdout, os.Stdin)
           19  +	} else {
           20  +		code = encode(os.Stdout, os.Stdin)
    20     21   	}
           22  +
    21     23   	os.Exit(code)
    22     24   }
    23     25   
    24     26   // Transforms the data according to the move-to-front algorithm
    25     27   // I/O is buffered for better performance
    26         -func transform(output io.Writer, input io.Reader) int {
           28  +func encode(output io.Writer, input io.Reader) int {
    27     29   	var (
    28     30   		err     error
    29         -		buffer  io.Writer = iou.SizedWriter(output, 4096)
    30         -		encoder io.Writer = mtf.Encoder(buffer)
           31  +		encoder io.Reader = mtf.Encoder(iou.SizedReader(input, 4096))
    31     32   	)
    32     33   
    33         -	_, err = io.Copy(encoder, input)
           34  +	_, err = io.Copy(output, encoder)
    34     35   	if err != nil {
    35     36   		fmt.Fprintln(os.Stderr, "Error while encoding.\n", err)
    36     37   		return 1
    37     38   	}
    38     39   
    39         -	// Flush the buffer
    40         -	_, err = buffer.Write(nil)
    41         -	if err != nil {
    42         -		fmt.Fprintln(os.Stderr, "Error while flushing output buffer.\n", err)
    43         -		return 1
    44         -	}
    45         -
    46     40   	return 0
    47     41   }
    48     42   
    49     43   // Reverses MTF`ed data and writes back the original bytes
    50     44   // I/O is buffered for better performance
    51         -func reverse(output io.Writer, input io.Reader) int {
           45  +func decode(output io.Writer, input io.Reader) int {
    52     46   	var (
    53     47   		err     error
    54     48   		decoder io.Reader = mtf.Decoder(iou.SizedReader(input, 4096))
    55     49   	)
    56     50   
    57     51   	_, err = io.Copy(output, decoder)
    58     52   	if err != nil {
    59     53   		fmt.Fprintln(os.Stderr, "Error while decoding.\n", err)
    60     54   		return 1
    61     55   	}
    62     56   
    63     57   	return 0
    64     58   }

Modified src/0dev.org/encoding/mtf/mtf.go from [f2ad12a795] to [cebf1719c8].

    25     25   	240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255,
    26     26   }
    27     27   
    28     28   type context struct {
    29     29   	table [256]byte
    30     30   }
    31     31   
    32         -// Returns an MTF encoder over the provided io.Writer
    33         -func Encoder(writer io.Writer) io.Writer {
    34         -	var enc encoder
    35         -	enc.table = initial
    36         -	enc.target = writer
    37         -	return &enc
    38         -}
    39         -
    40         -type encoder struct {
    41         -	context
    42         -	target io.Writer
    43         -}
    44         -
    45         -func (c *encoder) Write(data []byte) (int, error) {
    46         -	var (
    47         -		dataLength int    = len(data)
    48         -		buffer     []byte = make([]byte, dataLength)
    49         -	)
    50         -
    51         -	// io.Write must not modify the passed data in any way
    52         -	// TODO - check sync.Pool or a local free-list for amortizing buffers
    53         -	// TODO - use a buffer with a fixed max size to avoid OOM conditions
    54         -
    55         -	// Loop over the input data
           32  +// Encodes data in place
           33  +func (c *context) encode(data []byte) {
    56     34   	for index, value := range data {
    57     35   
    58     36   		// Shortcut for sequential, equal values
    59     37   		if c.table[0] == value {
    60         -			buffer[index] = 0
           38  +			data[index] = 0
    61     39   			continue
    62     40   		}
    63     41   
    64     42   		// Loop over the MTF table
    65     43   		for j := byte(1); j != 0; j++ {
    66     44   			if c.table[j] == value {
    67     45   				// Output the value
    68         -				buffer[index] = j
           46  +				data[index] = j
    69     47   
    70     48   				// Shift the table
    71     49   				copy(c.table[1:], c.table[:j])
    72     50   
    73     51   				// Restore the value in front and break
    74     52   				c.table[0] = value
    75     53   				break
    76     54   			}
    77     55   		}
    78     56   	}
           57  +}
           58  +
           59  +// Decode data in place
           60  +func (c *context) decode(data []byte) {
           61  +	for index, value := range data {
           62  +		position := value
           63  +
           64  +		// Shortcut for sequential, equal values
           65  +		if position == 0 {
           66  +			data[index] = c.table[0]
           67  +			continue
           68  +		}
           69  +
           70  +		// Output the value
           71  +		data[index] = c.table[position]
           72  +
           73  +		// Shift the table and restore the value in front
           74  +		copy(c.table[1:], c.table[:position])
           75  +		c.table[0] = data[index]
           76  +	}
           77  +}
           78  +
           79  +// Returns an MTF encoder over the provided io.Reader
           80  +func Encoder(reader io.Reader) io.Reader {
           81  +	var enc encoder
           82  +	enc.table = initial
           83  +	enc.source = reader
           84  +	return &enc
           85  +}
           86  +
           87  +type encoder struct {
           88  +	context
           89  +	source io.Reader
           90  +}
           91  +
           92  +// Read and encode data in place
           93  +func (c *encoder) Read(output []byte) (count int, err error) {
           94  +	count, err = c.source.Read(output)
           95  +	c.encode(output[:count])
    79     96   
    80         -	return c.target.Write(buffer)
           97  +	return count, err
    81     98   }
    82     99   
    83         -// Returns an MTF decoder over the provided io.Writer
          100  +// Returns an MTF decoder over the provided io.Reader
    84    101   func Decoder(reader io.Reader) io.Reader {
    85    102   	var dec decoder
    86    103   	dec.table = initial
    87    104   	dec.source = reader
    88    105   	return &dec
    89    106   }
    90    107   
    91    108   type decoder struct {
    92    109   	context
    93    110   	source io.Reader
    94    111   }
    95    112   
    96         -func (c *decoder) Read(output []byte) (int, error) {
    97         -	var (
    98         -		count    int
    99         -		err      error
   100         -		position byte
   101         -	)
   102         -
   103         -	// Read from the source and decode in place
          113  +// Read and decode data in place
          114  +func (c *decoder) Read(output []byte) (count int, err error) {
   104    115   	count, err = c.source.Read(output)
   105         -	for i := 0; i < count; i++ {
   106         -		position = output[i]
   107         -
   108         -		// Shortcut for sequential, equal values
   109         -		if position == 0 {
   110         -			output[i] = c.table[0]
   111         -			continue
   112         -		}
   113         -
   114         -		// Output the value
   115         -		output[i] = c.table[position]
   116         -
   117         -		// Shift the table and restore the value in front
   118         -		copy(c.table[1:], c.table[:position])
   119         -		c.table[0] = output[i]
   120         -	}
          116  +	c.decode(output[:count])
   121    117   
   122    118   	return count, err
   123    119   }

Modified src/0dev.org/encoding/mtf/mtf_test.go from [efb3f6ccdb] to [8e70ad85db].

     3      3   import (
     4      4   	diff "0dev.org/diff"
     5      5   	"bytes"
     6      6   	"io"
     7      7   	"testing"
     8      8   )
     9      9   
    10         -func TestEncoder(t *testing.T) {
           10  +func TestMTF(t *testing.T) {
    11     11   	var (
    12         -		input    []byte = []byte{1, 1, 0, 0}
    13         -		expected []byte = []byte{1, 0, 1, 0}
           12  +		data []byte = []byte{1, 1, 0, 0}
           13  +
           14  +		input   *bytes.Reader = bytes.NewReader(data)
           15  +		encoder io.Reader     = Encoder(input)
           16  +		decoder io.Reader     = Decoder(encoder)
           17  +
           18  +		output bytes.Buffer
           19  +	)
    14     20   
    15         -		buffer  bytes.Buffer
    16         -		encoder io.Writer = Encoder(&buffer)
    17         -	)
           21  +	io.Copy(&output, decoder)
           22  +	processed := output.Bytes()
    18     23   
    19         -	count, err := encoder.Write(input)
    20         -	if count != len(input) {
    21         -		t.Error("Unexpected write count from encoder", count)
    22         -	}
    23         -	if err != nil {
    24         -		t.Error("Unexpected write error from encoder", err)
    25         -	}
    26         -
    27         -	output := buffer.Bytes()
    28         -
    29         -	// Diff the output against the expected result
    30         -	delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output),
    31         -		EqualFunc: func(i, j int) bool { return expected[i] == output[j] }})
           24  +	delta := diff.Diff(diff.D{Len1: len(data), Len2: len(processed),
           25  +		EqualFunc: func(i, j int) bool { return data[i] == processed[j] }})
    32     26   	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
    33     27   		t.Error("Differences detected ", delta)
    34     28   	}
    35     29   }
    36     30   
    37         -func TestDecoder(t *testing.T) {
    38         -	var (
    39         -		input    []byte = []byte{1, 0, 1, 0}
    40         -		expected []byte = []byte{1, 1, 0, 0}
    41         -		output   []byte = make([]byte, 4)
           31  +// func TestEncoder(t *testing.T) {
           32  +// 	var (
           33  +// 		input    []byte = []byte{1, 1, 0, 0}
           34  +// 		expected []byte = []byte{1, 0, 1, 0}
           35  +
           36  +// 		buffer  bytes.Buffer
           37  +// 		encoder io.Writer = Encoder(&buffer)
           38  +// 	)
           39  +
           40  +// 	count, err := encoder.Write(input)
           41  +// 	if count != len(input) {
           42  +// 		t.Error("Unexpected write count from encoder", count)
           43  +// 	}
           44  +// 	if err != nil {
           45  +// 		t.Error("Unexpected write error from encoder", err)
           46  +// 	}
           47  +
           48  +// 	output := buffer.Bytes()
           49  +
           50  +// 	// Diff the output against the expected result
           51  +// 	delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output),
           52  +// 		EqualFunc: func(i, j int) bool { return expected[i] == output[j] }})
           53  +// 	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
           54  +// 		t.Error("Differences detected ", delta)
           55  +// 	}
           56  +// }
           57  +
           58  +// func TestDecoder(t *testing.T) {
           59  +// 	var (
           60  +// 		input    []byte = []byte{1, 0, 1, 0}
           61  +// 		expected []byte = []byte{1, 1, 0, 0}
           62  +// 		output   []byte = make([]byte, 4)
    42     63   
    43         -		reader  *bytes.Reader = bytes.NewReader(input)
    44         -		decoder io.Reader     = Decoder(reader)
    45         -	)
           64  +// 		reader  *bytes.Reader = bytes.NewReader(input)
           65  +// 		decoder io.Reader     = Decoder(reader)
           66  +// 	)
    46     67   
    47         -	count, err := decoder.Read(output)
    48         -	if count != len(output) {
    49         -		t.Error("Unexpected read count from decoder", count)
    50         -	}
    51         -	if err != nil {
    52         -		t.Error("Unexpected read error from decoder", err)
    53         -	}
           68  +// 	count, err := decoder.Read(output)
           69  +// 	if count != len(output) {
           70  +// 		t.Error("Unexpected read count from decoder", count)
           71  +// 	}
           72  +// 	if err != nil {
           73  +// 		t.Error("Unexpected read error from decoder", err)
           74  +// 	}
    54     75   
    55         -	// Diff the output against the expected result
    56         -	delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output),
    57         -		EqualFunc: func(i, j int) bool { return expected[i] == output[j] }})
    58         -	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
    59         -		t.Error("Differences detected ", delta)
    60         -	}
    61         -}
           76  +// 	// Diff the output against the expected result
           77  +// 	delta := diff.Diff(diff.D{Len1: len(expected), Len2: len(output),
           78  +// 		EqualFunc: func(i, j int) bool { return expected[i] == output[j] }})
           79  +// 	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
           80  +// 		t.Error("Differences detected ", delta)
           81  +// 	}
           82  +// }