LZ77 compression.

// LZ77 over bytes. Each token is either one literal byte or a copy: go back `distance`
// bytes in what has already been written and copy `length` bytes from there.
export const MIN_MATCH = 3; // shorter copies cost more than the literals they replace
export const MAX_MATCH = 258; // DEFLATE's longest copy (RFC 1951)
export const MAX_WINDOW = 4096; // a teaching bound; DEFLATE looks back up to 32,768 bytes
export const MAX_INPUT = 4096;

export type Literal = { byte: number };
export type Copy = { distance: number; length: number };
export type Token = Literal | Copy;

export type Lz77ErrorCode = 'bad-window' | 'too-long' | 'bad-token';

export class Lz77Error extends Error {
	readonly code: Lz77ErrorCode;
	constructor(code: Lz77ErrorCode, message: string) {
		super(message);
		this.name = 'Lz77Error';
		this.code = code;
	}
}

export function encode(input: Uint8Array, window = MAX_WINDOW): Token[] {
	if (!Number.isInteger(window) || window < 1 || window > MAX_WINDOW)
		throw new Lz77Error('bad-window', `window must be 1 to ${MAX_WINDOW} bytes`);
	if (input.length > MAX_INPUT)
		throw new Lz77Error('too-long', `input is limited to ${MAX_INPUT} bytes`);
	const tokens: Token[] = [];
	let cursor = 0;
	while (cursor < input.length) {
		const longest = Math.min(MAX_MATCH, input.length - cursor);
		let best = 0;
		let bestDistance = 0;
		// Nearest first, and only a strictly longer match replaces the best: ties keep the nearest.
		for (let distance = 1; distance <= Math.min(window, cursor); distance++) {
			let length = 0;
			// The copy may run past the cursor. The decoder will have written those bytes by then.
			while (length < longest && input[cursor - distance + length] === input[cursor + length])
				length++;
			if (length > best) {
				best = length;
				bestDistance = distance;
				if (best === longest) break;
			}
		}
		if (best >= MIN_MATCH) {
			tokens.push({ distance: bestDistance, length: best });
			cursor += best;
		} else {
			tokens.push({ byte: input[cursor] });
			cursor += 1;
		}
	}
	return tokens;
}

export function decode(tokens: readonly Token[]): Uint8Array {
	const output: number[] = [];
	for (const token of tokens) {
		if ('byte' in token) {
			if (!Number.isInteger(token.byte) || token.byte < 0 || token.byte > 255)
				throw new Lz77Error('bad-token', 'a literal is one byte, 0 to 255');
			output.push(token.byte);
		} else {
			const { distance, length } = token;
			if (!Number.isInteger(distance) || distance < 1 || distance > output.length)
				throw new Lz77Error('bad-token', 'a copy can only point back into bytes already written');
			if (!Number.isInteger(length) || length < MIN_MATCH || length > MAX_MATCH)
				throw new Lz77Error('bad-token', `a copy is ${MIN_MATCH} to ${MAX_MATCH} bytes long`);
			// One byte at a time, so a copy can read bytes it wrote a moment ago.
			for (let i = 0; i < length; i++) output.push(output[output.length - distance]);
		}
		if (output.length > MAX_INPUT)
			throw new Lz77Error('too-long', `output is limited to ${MAX_INPUT} bytes`);
	}
	return Uint8Array.from(output);
}

// This lesson's own fixed-width format, not DEFLATE's: one flag bit, then 8 bits for a
// literal, or 15 bits of distance and 8 bits of length for a copy.
export const LITERAL_BITS = 9;
export const COPY_BITS = 24;

export function sizeInBits(tokens: readonly Token[]): number {
	return tokens.reduce((sum, token) => sum + ('byte' in token ? LITERAL_BITS : COPY_BITS), 0);
}

// LZ77 over bytes. Each token is either one literal byte or a copy: go back Distance
// bytes in what has already been written and copy Length bytes from there.
const (
	MinMatch  = 3    // shorter copies cost more than the literals they replace
	MaxMatch  = 258  // DEFLATE's longest copy (RFC 1951)
	MaxWindow = 4096 // a teaching bound; DEFLATE looks back up to 32,768 bytes
	MaxInput  = 4096
)

// Token is a literal when Length is 0, and a copy otherwise.
type Token struct {
	Byte     byte
	Distance int
	Length   int
}

func (t Token) IsCopy() bool { return t.Length > 0 }

type Lz77Error struct {
	Code    string // "bad-window", "too-long", or "bad-token"
	Message string
}

func (e *Lz77Error) Error() string { return e.Code + ": " + e.Message }

func Encode(input []byte, window int) ([]Token, error) {
	if window < 1 || window > MaxWindow {
		return nil, &Lz77Error{"bad-window", fmt.Sprintf("window must be 1 to %d bytes", MaxWindow)}
	}
	if len(input) > MaxInput {
		return nil, &Lz77Error{"too-long", fmt.Sprintf("input is limited to %d bytes", MaxInput)}
	}
	tokens := []Token{}
	cursor := 0
	for cursor < len(input) {
		longest := min(MaxMatch, len(input)-cursor)
		best, bestDistance := 0, 0
		// Nearest first, and only a strictly longer match replaces the best: ties keep the nearest.
		for distance := 1; distance <= min(window, cursor); distance++ {
			length := 0
			// The copy may run past the cursor. The decoder will have written those bytes by then.
			for length < longest && input[cursor-distance+length] == input[cursor+length] {
				length++
			}
			if length > best {
				best, bestDistance = length, distance
				if best == longest {
					break
				}
			}
		}
		if best >= MinMatch {
			tokens = append(tokens, Token{Distance: bestDistance, Length: best})
			cursor += best
		} else {
			tokens = append(tokens, Token{Byte: input[cursor]})
			cursor++
		}
	}
	return tokens, nil
}

func Decode(tokens []Token) ([]byte, error) {
	output := []byte{}
	for _, token := range tokens {
		if !token.IsCopy() {
			output = append(output, token.Byte)
		} else {
			if token.Distance < 1 || token.Distance > len(output) {
				return nil, &Lz77Error{"bad-token", "a copy can only point back into bytes already written"}
			}
			if token.Length < MinMatch || token.Length > MaxMatch {
				return nil, &Lz77Error{"bad-token", fmt.Sprintf("a copy is %d to %d bytes long", MinMatch, MaxMatch)}
			}
			// One byte at a time, so a copy can read bytes it wrote a moment ago.
			for i := 0; i < token.Length; i++ {
				output = append(output, output[len(output)-token.Distance])
			}
		}
		if len(output) > MaxInput {
			return nil, &Lz77Error{"too-long", fmt.Sprintf("output is limited to %d bytes", MaxInput)}
		}
	}
	return output, nil
}

// This lesson's own fixed-width format, not DEFLATE's: one flag bit, then 8 bits for a
// literal, or 15 bits of distance and 8 bits of length for a copy.
const (
	LiteralBits = 9
	CopyBits    = 24
)

func SizeInBits(tokens []Token) int {
	sum := 0
	for _, token := range tokens {
		if token.IsCopy() {
			sum += CopyBits
		} else {
			sum += LiteralBits
		}
	}
	return sum
}