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