Check-in [67794bdf14]
Overview
Comment:Added diff.D struct; Added an RFC1978 Predictor compressor implementation and a test
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 67794bdf1483c0173b3b095a2b723e53fb25dc2d
User & Date: spaskalev on 2014-12-15 21:22:10
Other Links: manifest | tags
Context
2014-12-16
01:55
Added hamming weight lookup table for bytes in package bits. Added a PoC predictor decompressor implementation check-in: 60ca5b4b7b user: spaskalev tags: trunk
2014-12-15
21:22
Added diff.D struct; Added an RFC1978 Predictor compressor implementation and a test check-in: 67794bdf14 user: spaskalev tags: trunk
2014-12-14
20:41
Buffer stdout, use os.Args instead of flag check-in: 074a26f76b user: spaskalev tags: trunk
Changes

Modified src/0dev.org/diff/diff.go from [1f071ca8dd] to [00f91e1be6].

1
2


3
4
5
6
7
8
9
10

11
12
13
14
15
16
17


1
2
3
4
5
6
7
8
9

10
11
12
13
14
15
16
17
-
-
+
+







-
+







// Package diff provides a diff implementation
// for finite, indexable sequences with comparable elements
// Package diff provides a diff algorithm implementation
// for finite, indexable sequences with comparable elements.
package diff

import (
	bits "0dev.org/bits"
)

// Interface abstracts the required knowledge to perform a diff
// on any two comparable, fixed-length sequences
// on any two fixed-length sequences with comparable elements.
type Interface interface {
	// The sequences' lengths
	Len() (int, int)
	// True when the sequences' elements at those indices are equal
	Equal(int, int) bool
}

124
125
126
127
128
129
130
















124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146







+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
			}
		} else { // End of current of match
			inMatch = false // ... and reset the current one
		}
	}
	return
}

// A diff.Interface implementation with plugable Equal function
type D struct {
	Len1, Len2 int
	EqualFunc  func(i, j int) bool
}

// Required per diff.Interface
func (d D) Len() (int, int) {
	return d.Len1, d.Len2
}

// Required per diff.Interface
func (d D) Equal(i, j int) bool {
	return d.EqualFunc(i, j)
}

Added src/0dev.org/predictor/predictor.go version [d4a72555aa].





































































































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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
// Package predictor implements the predictor compression/decompression algorithm
// as specified by RFC1978 - PPP Predictor Compression Protocol
package predictor

import (
	"io"
)

type context struct {
	table [65536]byte
	hash  uint16
	input []byte
}

// Returns a closure over the provided writer that compresses data when called.
//
// It can buffer data as the predictor mandates 8-byte blocks with a header.
// A call with no data will force a flush.
func Compressor(writer io.Writer) func([]byte) error {
	var ctx context
	ctx.input = make([]byte, 8)

	// Forward declaration as it is required for recursion
	var write func(data []byte) error

	write = func(data []byte) error {
		var (
			err          error
			blockSize    int = 8
			bufferLength int = len(ctx.input)
		)

		// Force a flush if we are called with no data to write
		if len(data) == 0 {
			// 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 bufferLength > 0 && bufferLength < 8 {

			// Check whether we have enough bytes for a complete block
			if len(data) > 8-bufferLength {
				// Fill the buffer ...
				ctx.input = append(ctx.input, data[:8-bufferLength]...)
				// ... and recurse, calling ourselves with the full buffer
				err = write(ctx.input)
				if err != nil {
					return err
				}

				// Clear the buffer
				ctx.input = ctx.input[:0]

				// Handle remaining bytes, if any
				var remaining []byte = data[8-bufferLength:]
				if len(remaining) > 0 {
					// Recurse, calling ourselves with the rest of the bytes
					err = write(data[8-bufferLength:])
					if err != nil {
						return err
					}
				}
			} 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)
		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]
			buf = buf[:1]
		}
		return nil
	}

	return write
}

Added src/0dev.org/predictor/predictor_test.go version [f542b34031].













































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

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

func TestRFC(t *testing.T) {
	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}

	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}

	var buf bytes.Buffer
	var err error

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

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

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

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