Check-in [10013ae789]
Overview
Comment:Removed goto from predictor's compressor, added more tests that invoke both compress/decompress
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 10013ae7898828f7bcb015ad656fd2ee55b28c1c
User & Date: spaskalev on 2014-12-16 16:04:52
Other Links: manifest | tags
Context
2014-12-16
22:56
Reworked the compressor's buffering code, switched to table testing, add step testing for the compressor. Code coverage at 88.3% check-in: 1847f77062 user: spaskalev tags: trunk
16:04
Removed goto from predictor's compressor, added more tests that invoke both compress/decompress check-in: 10013ae789 user: spaskalev tags: trunk
04:03
Fixed issues with both compressor and decompressor, added more tests check-in: b838653282 user: spaskalev tags: trunk
Changes

Modified src/0dev.org/predictor/predictor.go from [f0ba5a860c] to [0cc123a3c6].

32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
		)

		// Force a flush if we are called with no data to write
		if len(data) == 0 {
			if len(ctx.input) == 0 {
				return nil
			}
			data = ctx.input

			// We can't have more than 7 bytes in the buffer so this is safe
			blockSize = len(ctx.input)
			goto write
		}

		// Check if there are pending bytes in the buffer
		if len(data) < blockSize || bufferLength > 0 {
			// Check whether we have enough bytes for a complete block
			if len(data) > 8-bufferLength {
				// Fill the buffer ...







<
<

|
<







32
33
34
35
36
37
38


39
40

41
42
43
44
45
46
47
		)

		// Force a flush if we are called with no data to write
		if len(data) == 0 {
			if len(ctx.input) == 0 {
				return nil
			}


			// We can't have more than 7 bytes in the buffer so this is safe
			data, blockSize, bufferLength = ctx.input, len(ctx.input), 0

		}

		// Check if there are pending bytes in the buffer
		if len(data) < blockSize || bufferLength > 0 {
			// Check whether we have enough bytes for a complete block
			if len(data) > 8-bufferLength {
				// Fill the buffer ...
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
			} else {
				// Add the insufficient data to the buffer and return
				ctx.input = append(ctx.input, data...)
				return nil
			}
		}

	write:
		var buf []byte = make([]byte, 1, blockSize+1)

		var blocks int = len(data) / blockSize
		if blocks == 0 {
			blocks++
		}

		for block := 0; block < blocks; block++ {
			for i := 0; i < blockSize; i++ {
				var current byte = data[(block*blockSize)+i]
				if ctx.table[ctx.hash] == current {
					// Guess was right - don't output
					buf[0] |= 1 << uint(i)
				} else {
					// Guess was wrong, output char
					ctx.table[ctx.hash] = current
					buf = append(buf, current)
				}
				ctx.hash = (ctx.hash << 4) ^ uint16(current)
			}

			_, err = writer.Write(buf)
			if err != nil {
				return err
			}

			// Reset the flags and buffer for the next iteration
			buf[0] ^= buf[0]







<

<
<
<
<
<
<
|












>







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
			} else {
				// Add the insufficient data to the buffer and return
				ctx.input = append(ctx.input, data...)
				return nil
			}
		}


		var buf []byte = make([]byte, 1, blockSize+1)






		for block := 0; block < len(data)/blockSize; block++ {
			for i := 0; i < blockSize; i++ {
				var current byte = data[(block*blockSize)+i]
				if ctx.table[ctx.hash] == current {
					// Guess was right - don't output
					buf[0] |= 1 << uint(i)
				} else {
					// Guess was wrong, output char
					ctx.table[ctx.hash] = current
					buf = append(buf, current)
				}
				ctx.hash = (ctx.hash << 4) ^ uint16(current)
			}

			_, err = writer.Write(buf)
			if err != nil {
				return err
			}

			// Reset the flags and buffer for the next iteration
			buf[0] ^= buf[0]

Modified src/0dev.org/predictor/predictor_test.go from [0cbbd433d4] to [717a9810a3].

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

import (
	diff "0dev.org/diff"
	"bytes"

	"io/ioutil"
	"testing"
)

// Sample input from RFC1978 - PPP Predictor Compression Protocol
var input = []byte{0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x42, 0x41, 0x42, 0x41, 0x42, 0x41, 0x0a,
	0x42, 0x41, 0x42, 0x41, 0x42, 0x41, 0x42, 0x0a,
	0x78, 0x78, 0x78, 0x78, 0x78, 0x78, 0x78, 0x0a}

// Sample output from RFC1978 - PPP Predictor Compression Protocol
var output = []byte{0x60, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a, 0x60,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x0a, 0x6f, 0x41,
	0x0a, 0x6f, 0x41, 0x0a, 0x41, 0x42, 0x41, 0x42,
	0x41, 0x42, 0x0a, 0x60, 0x42, 0x41, 0x42, 0x41,
	0x42, 0x0a, 0x60, 0x78, 0x78, 0x78, 0x78, 0x78, 0x0a}

func TestCompressor(t *testing.T) {
	var (
		buf bytes.Buffer
		err error
	)

	out := Compressor(&buf)
	err = out(input)





>




















|







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

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

// Sample input from RFC1978 - PPP Predictor Compression Protocol
var input = []byte{0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a,
	0x41, 0x42, 0x41, 0x42, 0x41, 0x42, 0x41, 0x0a,
	0x42, 0x41, 0x42, 0x41, 0x42, 0x41, 0x42, 0x0a,
	0x78, 0x78, 0x78, 0x78, 0x78, 0x78, 0x78, 0x0a}

// Sample output from RFC1978 - PPP Predictor Compression Protocol
var output = []byte{0x60, 0x41, 0x41, 0x41, 0x41, 0x41, 0x0a, 0x60,
	0x41, 0x41, 0x41, 0x41, 0x41, 0x0a, 0x6f, 0x41,
	0x0a, 0x6f, 0x41, 0x0a, 0x41, 0x42, 0x41, 0x42,
	0x41, 0x42, 0x0a, 0x60, 0x42, 0x41, 0x42, 0x41,
	0x42, 0x0a, 0x60, 0x78, 0x78, 0x78, 0x78, 0x78, 0x0a}

func TestCompressorSample(t *testing.T) {
	var (
		buf bytes.Buffer
		err error
	)

	out := Compressor(&buf)
	err = out(input)
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



	delta := diff.Diff(diff.D{len(result), len(output), func(i, j int) bool { return result[i] == output[j] }})

	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
		t.Error("Unexpected compressed output", delta)
	}
}

func TestDecompressor(t *testing.T) {
	in := Decompressor(bytes.NewReader(output))
	result, err := ioutil.ReadAll(in)
	if err != nil {
		t.Error("Unexpected error while decompressing", err)
	}

	delta := diff.Diff(diff.D{len(result), len(input),
		func(i, j int) bool { return result[i] == input[j] }})

	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
		t.Error("Unexpected decompressed output", delta)
	}
}

func TestPartial(t *testing.T) {

	var (






























		input []byte = []byte{0, 1, 2, 3, 4, 5, 6}








		buf   bytes.Buffer
		err   error
	)


	out := Compressor(&buf)
	err = out(input)
	if err != nil {
		t.Error(err)
	}


	err = out(nil)
	if err != nil {
		t.Error(err)
	}


	compressed := buf.Bytes()
	decompressed, err := ioutil.ReadAll(Decompressor(bytes.NewReader(compressed)))





	delta := diff.Diff(diff.D{len(input), len(decompressed),
		func(i, j int) bool { return input[i] == decompressed[j] }})


	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
		t.Error("Unexpected decompressed output", delta)
		t.Errorf("%#x", input)
		t.Errorf("%#x", decompressed)
	}
}










|














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


>
|
|

|


>
|

|


>


>
>
|
>
>



>

|
<
|

|
>
>
>
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

140
141
142
143
144
145
	delta := diff.Diff(diff.D{len(result), len(output), func(i, j int) bool { return result[i] == output[j] }})

	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
		t.Error("Unexpected compressed output", delta)
	}
}

func TestDecompressorSample(t *testing.T) {
	in := Decompressor(bytes.NewReader(output))
	result, err := ioutil.ReadAll(in)
	if err != nil {
		t.Error("Unexpected error while decompressing", err)
	}

	delta := diff.Diff(diff.D{len(result), len(input),
		func(i, j int) bool { return result[i] == input[j] }})

	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
		t.Error("Unexpected decompressed output", delta)
	}
}

func TestEmptyCycle(t *testing.T) {
	var input []byte = []byte{}

	if err := cycle(input); err != nil {
		t.Error(err)
	}
}

func TestPartialCycle(t *testing.T) {
	var input []byte = []byte{0, 1, 2, 3}

	if err := cycle(input); err != nil {
		t.Error(err)
	}
}

func TestBlockCycle(t *testing.T) {
	var input []byte = []byte{0, 1, 2, 3, 4, 5, 6, 7}

	if err := cycle(input); err != nil {
		t.Error(err)
	}
}

func TestBlockPartialCycle(t *testing.T) {
	var input []byte = []byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

	if err := cycle(input); err != nil {
		t.Error(err)
	}
}

func TestDualBlockCycle(t *testing.T) {
	var input []byte = []byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

	if err := cycle(input); err != nil {
		t.Error(err)
	}
}

func cycle(input []byte) error {
	var (
		buf bytes.Buffer
		err error
	)

	// Create a compressor and write the given data
	compressor := Compressor(&buf)
	err = compressor(input)
	if err != nil {
		return err
	}

	// Flush the compressor
	err = compressor(nil)
	if err != nil {
		return err
	}

	// Attempt to decompress the data
	compressed := buf.Bytes()
	decompressed, err := ioutil.ReadAll(Decompressor(bytes.NewReader(compressed)))
	if err != nil {
		return err
	}

	// Diff the result against the initial input
	delta := diff.Diff(diff.D{len(input), len(decompressed),
		func(i, j int) bool { return input[i] == decompressed[j] }})

	// Return a well-formated error if any differences are found
	if len(delta.Added) > 0 || len(delta.Removed) > 0 {
		return fmt.Errorf("Unexpected decompressed output %v\ninput:  %#x\noutput: %#x\n",

			delta, input, decompressed)
	}

	// All is good :)
	return nil
}