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

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

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
package main

import (
	mtf "0dev.org/encoding/mtf"
	iou "0dev.org/ioutil"

	"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]")
	}

	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 {
	var (
		err     error
		buffer  io.Writer = iou.SizedWriter(output, 4096)
		encoder io.Writer = mtf.Encoder(buffer)
	)

	_, err = io.Copy(encoder, input)
	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 {
	var (
		err     error
		decoder io.Reader = mtf.Decoder(iou.SizedReader(input, 4096))
	)

	_, err = io.Copy(output, decoder)
	if err != nil {
		fmt.Fprintln(os.Stderr, "Error while decoding.\n", err)
		return 1
	}

	return 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
package main

import (
	mtf "0dev.org/encoding/mtf"
	iou "0dev.org/ioutil"
	"flag"
	"fmt"
	"io"
	"os"
)

func main() {
	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 encode(output io.Writer, input io.Reader) int {
	var (
		err     error

		encoder io.Reader = mtf.Encoder(iou.SizedReader(input, 4096))
	)

	_, err = io.Copy(output, encoder)
	if err != nil {
		fmt.Fprintln(os.Stderr, "Error while encoding.\n", err)
		return 1
	}








	return 0
}

// Reverses MTF`ed data and writes back the original bytes
// I/O is buffered for better performance
func decode(output io.Writer, input io.Reader) int {
	var (
		err     error
		decoder io.Reader = mtf.Decoder(iou.SizedReader(input, 4096))
	)

	_, err = io.Copy(output, decoder)
	if err != nil {
		fmt.Fprintln(os.Stderr, "Error while decoding.\n", err)
		return 1
	}

	return 0
}

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

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
	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
}







<
<
<
<
<
<
<
|
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<




|







|










|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|


>
>
>
>
>
>
>
>
>
>
>
>
>
|












>
|
<
<
<
<
<
<
<

<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<



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
	240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255,
}

type context struct {
	table [256]byte
}








// 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 {
			data[index] = 0
			continue
		}

		// Loop over the MTF table
		for j := byte(1); j != 0; j++ {
			if c.table[j] == value {
				// Output the value
				data[index] = j

				// Shift the table
				copy(c.table[1:], c.table[:j])

				// Restore the value in front and break
				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 count, err
}

// 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
}

type decoder struct {
	context
	source io.Reader
}

// Read and decode data in place
func (c *decoder) Read(output []byte) (count int, err error) {







	count, err = c.source.Read(output)


	c.decode(output[:count])














	return count, err
}

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

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


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)
	}
}











|

|
<

|
|
>
|
>
|
<
<
<
|
<
<
<
|
|

<
|
|





|
|
|
|
<

|
|
>
|
>
>
>
>
>
>
>

|
|
|
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
>
|
<
|
|
|
|
|
<
<
>
>
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
package mtf

import (
	diff "0dev.org/diff"
	"bytes"
	"io"
	"testing"
)

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)


// 	}
// }