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