// Package predictor implements the predictor compression/decompression algorithm // as specified by RFC1978 - PPP Predictor Compression Protocol package predictor import ( "io" ) type context struct { table [1 << 16]byte buffer [1 << 3]byte input []byte hash uint16 } // 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 = ctx.buffer[:0] // 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 { 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 ... 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) 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] 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 } type reader func([]byte) (int, error) func (r reader) Read(output []byte) (int, error) { return r(output) } // TODO - document func Decompressor(wrapped io.Reader) io.Reader { var ctx context ctx.input = ctx.buffer[:0] return reader(func(output []byte) (int, error) { var ( err error flags byte readCount int ) // Sanity check for space to read into if len(output) == 0 { return 0, nil } // Check whether we have leftover data in the buffer if len(ctx.input) > 0 { readCount = copy(output, ctx.input) ctx.input = ctx.input[readCount:] return readCount, nil } // 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 ctx.input = ctx.buffer[:1] readCount, err = wrapped.Read(ctx.input) if readCount == 0 || err != nil { return readCount, err } 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.input[i] = ctx.table[ctx.hash] } else { readCount, err = wrapped.Read(ctx.input[i:(i + 1)]) if err == io.EOF { break } if err != nil { return readCount, err } if readCount == 0 { // treat as EoF break } ctx.table[ctx.hash] = ctx.input[i] } ctx.hash = (ctx.hash << 4) ^ uint16(ctx.input[i]) } readCount = copy(output, ctx.input[:i]) // Place any remaining bytes in the buffer if uint(readCount) < i { ctx.input = ctx.input[readCount:i] } else { ctx.input = ctx.buffer[:0] } return readCount, nil }) }