The Shed
Check-in [470d7e947b]
Login
HomeTimelineFilesBranchesTagsTicketsWiki
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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

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






+






+
+
+

-
+
-
-
-
-
+
+
+
-
-

+





-
+


-
-
+


-
+





-
-
-
-
-
-
-





-
+








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
	switch {
	if *d {
	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)
		code = decode(os.Stdout, os.Stdin)
	} else {
		code = encode(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 {
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))
	)

	_, err = io.Copy(output, decoder)
	if err != nil {
︙

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

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
}

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

// Encodes data in place
type encoder struct {
	context
	target io.Writer
}

func (c *context) encode(data []byte) {
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
			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
				c.table[0] = value
				break
			}
		}
	}

	return c.target.Write(buffer)
}

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

type decoder struct {
	context
	source io.Reader
}

// Read and decode data in place
func (c *decoder) Read(output []byte) (int, error) {
func (c *decoder) Read(output []byte) (count int, err 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]

	c.decode(output[:count])
		// 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
}

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



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 TestEncoder(t *testing.T) {
func TestMTF(t *testing.T) {
	var (
		input    []byte = []byte{1, 1, 0, 0}
		data []byte = []byte{1, 1, 0, 0}
		expected []byte = []byte{1, 0, 1, 0}

		buffer  bytes.Buffer
		encoder io.Writer = Encoder(&buffer)
	)

		input   *bytes.Reader = bytes.NewReader(data)
		encoder io.Reader     = Encoder(input)
		decoder io.Reader     = Decoder(encoder)

		output bytes.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()
	io.Copy(&output, decoder)
	processed := output.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] }})
	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 TestDecoder(t *testing.T) {
	var (
		input    []byte = []byte{1, 0, 1, 0}
		expected []byte = []byte{1, 1, 0, 0}
// func TestEncoder(t *testing.T) {
// 	var (
// 		input    []byte = []byte{1, 1, 0, 0}
// 		expected []byte = []byte{1, 0, 1, 0}
		output   []byte = make([]byte, 4)

		reader  *bytes.Reader = bytes.NewReader(input)
		decoder io.Reader     = Decoder(reader)
	)
// 		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)
// 	}

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

Powered by Fossil · RSS