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

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

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

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