Index: src/0dev.org/predictor/predictor.go
==================================================================
--- src/0dev.org/predictor/predictor.go
+++ src/0dev.org/predictor/predictor.go
@@ -17,11 +17,11 @@
//
// 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 = ctx.buffer[:]
+ ctx.input = ctx.buffer[:0]
// Forward declaration as it is required for recursion
var write func(data []byte) error
write = func(data []byte) error {
@@ -31,18 +31,22 @@
bufferLength int = len(ctx.input)
)
// 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 bufferLength > 0 && bufferLength < 8 {
-
+ if len(data) < blockSize || bufferLength > 0 {
// 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
@@ -70,11 +74,17 @@
}
}
write:
var buf []byte = make([]byte, 1, blockSize+1)
- for block := 0; block < len(data)/blockSize; block++ {
+
+ 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)
@@ -92,10 +102,19 @@
// Reset the flags and buffer for the next iteration
buf[0] ^= buf[0]
buf = buf[:1]
}
+
+ var remaining int = len(data) % blockSize
+ if remaining > 0 {
+ ctx.input = ctx.buffer[:remaining]
+ copy(ctx.input, data[len(data)-remaining:])
+ } else {
+ ctx.input = ctx.buffer[:0]
+ }
+
return nil
}
return write
}
@@ -105,15 +124,15 @@
func (r reader) Read(output []byte) (int, error) {
return r(output)
}
// TODO - document
-func Decompressor(reader io.Reader) reader {
+func Decompressor(wrapped io.Reader) io.Reader {
var ctx context
ctx.input = ctx.buffer[:0]
- return func(output []byte) (int, error) {
+ return reader(func(output []byte) (int, error) {
var (
err error
flags byte
readCount int
)
@@ -128,34 +147,31 @@
readCount = copy(output, ctx.input)
ctx.input = ctx.input[readCount:]
return readCount, nil
}
- // // The buffer will shrink as it empties, restore it if it is needed
- // if len(ctx.input) == 0 {
- // ctx.input = ctx.buffer[:1]
- // }
+ // This is single-iteration only but it is fine according to io.Reader's contract ?!
+ // TODO - read all bytes from a block based on the hamming weight of the flag
+ // and just shuffle them for predictions instead of bite-sized reads ;)
// Read the flags
- readCount, err = reader.Read(ctx.buffer[:1])
+ ctx.input = ctx.buffer[:1]
+ readCount, err = wrapped.Read(ctx.input)
if readCount == 0 || err != nil {
return readCount, err
}
- // This is single-iteration only but it is fine according to io.Reader's contract ?!
- // TODO - read all bytes from a block based on the hamming weight of the flag
- // and just shuffle them for predictions instead of bite-sized reads ;)
-
- flags = ctx.buffer[0]
+ flags = ctx.input[0]
+ ctx.input = ctx.buffer[:8]
var i uint = 0
for ; i < 8; i++ {
if flags&(1<<i) > 0 {
// Guess was right
- ctx.buffer[i] = ctx.table[ctx.hash]
+ ctx.input[i] = ctx.table[ctx.hash]
} else {
- readCount, err = reader.Read(ctx.buffer[i:(i + 1)])
+ readCount, err = wrapped.Read(ctx.input[i:(i + 1)])
if err == io.EOF {
break
}
@@ -165,21 +181,23 @@
if readCount == 0 { // treat as EoF
break
}
- ctx.table[ctx.hash] = ctx.buffer[i]
+ ctx.table[ctx.hash] = ctx.input[i]
}
- ctx.hash = (ctx.hash << 4) ^ uint16(ctx.buffer[i])
+ ctx.hash = (ctx.hash << 4) ^ uint16(ctx.input[i])
}
- readCount = copy(output, ctx.buffer[:i])
+ readCount = copy(output, ctx.input[:i])
// Place any remaining bytes in the buffer
if uint(readCount) < i {
- ctx.input = ctx.buffer[readCount:i]
+ ctx.input = ctx.input[readCount:i]
+ } else {
+ ctx.input = ctx.buffer[:0]
}
return readCount, nil
- }
+ })
}
Index: src/0dev.org/predictor/predictor_test.go
==================================================================
--- src/0dev.org/predictor/predictor_test.go
+++ src/0dev.org/predictor/predictor_test.go
@@ -5,35 +5,39 @@
"bytes"
"io/ioutil"
"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
+// 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)
if err != nil {
t.Error(err)
}
- err = out([]byte{})
+ err = out(nil)
if err != nil {
t.Error(err)
}
result := buf.Bytes()
@@ -40,16 +44,52 @@
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)
+ }
- data := bytes.NewBuffer(result)
- in := Decompressor(data)
+ compressed := buf.Bytes()
+ decompressed, err := ioutil.ReadAll(Decompressor(bytes.NewReader(compressed)))
- result, err = ioutil.ReadAll(in)
- delta = diff.Diff(diff.D{len(result), len(input), func(i, j int) bool { return result[i] == input[j] }})
+ 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 compressed output", delta)
+ t.Error("Unexpected decompressed output", delta)
+ t.Errorf("%#x", input)
+ t.Errorf("%#x", decompressed)
}
}