// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package lzw

import (
	
	
	
	
)

// A writer is a buffered, flushable writer.
type writer interface {
	io.ByteWriter
	Flush() error
}

const (
	// A code is a 12 bit value, stored as a uint32 when encoding to avoid
	// type conversions when shifting bits.
	maxCode     = 1<<12 - 1
	invalidCode = 1<<32 - 1
	// There are 1<<12 possible codes, which is an upper bound on the number of
	// valid hash table entries at any given point in time. tableSize is 4x that.
	tableSize = 4 * 1 << 12
	tableMask = tableSize - 1
	// A hash table entry is a uint32. Zero is an invalid entry since the
	// lower 12 bits of a valid entry must be a non-literal code.
	invalidEntry = 0
)

// Writer is an LZW compressor. It writes the compressed form of the data
// to an underlying writer (see [NewWriter]).
type Writer struct {
	// w is the writer that compressed bytes are written to.
	w writer
	// order, write, bits, nBits and width are the state for
	// converting a code stream into a byte stream.
	order Order
	write func(*Writer, uint32) error
	bits  uint32
	nBits uint
	width uint
	// litWidth is the width in bits of literal codes.
	litWidth uint
	// hi is the code implied by the next code emission.
	// overflow is the code at which hi overflows the code width.
	hi, overflow uint32
	// savedCode is the accumulated code at the end of the most recent Write
	// call. It is equal to invalidCode if there was no such call.
	savedCode uint32
	// err is the first error encountered during writing. Closing the writer
	// will make any future Write calls return errClosed
	err error
	// table is the hash table from 20-bit keys to 12-bit values. Each table
	// entry contains key<<12|val and collisions resolve by linear probing.
	// The keys consist of a 12-bit code prefix and an 8-bit byte suffix.
	// The values are a 12-bit code.
	table [tableSize]uint32
}

// writeLSB writes the code c for "Least Significant Bits first" data.
func ( *Writer) ( uint32) error {
	.bits |=  << .nBits
	.nBits += .width
	for .nBits >= 8 {
		if  := .w.WriteByte(uint8(.bits));  != nil {
			return 
		}
		.bits >>= 8
		.nBits -= 8
	}
	return nil
}

// writeMSB writes the code c for "Most Significant Bits first" data.
func ( *Writer) ( uint32) error {
	.bits |=  << (32 - .width - .nBits)
	.nBits += .width
	for .nBits >= 8 {
		if  := .w.WriteByte(uint8(.bits >> 24));  != nil {
			return 
		}
		.bits <<= 8
		.nBits -= 8
	}
	return nil
}

// errOutOfCodes is an internal error that means that the writer has run out
// of unused codes and a clear code needs to be sent next.
var errOutOfCodes = errors.New("lzw: out of codes")

// incHi increments e.hi and checks for both overflow and running out of
// unused codes. In the latter case, incHi sends a clear code, resets the
// writer state and returns errOutOfCodes.
func ( *Writer) () error {
	.hi++
	if .hi == .overflow {
		.width++
		.overflow <<= 1
	}
	if .hi == maxCode {
		 := uint32(1) << .litWidth
		if  := .write(, );  != nil {
			return 
		}
		.width = .litWidth + 1
		.hi =  + 1
		.overflow =  << 1
		for  := range .table {
			.table[] = invalidEntry
		}
		return errOutOfCodes
	}
	return nil
}

// Write writes a compressed representation of p to w's underlying writer.
func ( *Writer) ( []byte) ( int,  error) {
	if .err != nil {
		return 0, .err
	}
	if len() == 0 {
		return 0, nil
	}
	if  := uint8(1<<.litWidth - 1);  != 0xff {
		for ,  := range  {
			if  >  {
				.err = errors.New("lzw: input byte too large for the litWidth")
				return 0, .err
			}
		}
	}
	 = len()
	 := .savedCode
	if  == invalidCode {
		// This is the first write; send a clear code.
		// https://www.w3.org/Graphics/GIF/spec-gif89a.txt Appendix F
		// "Variable-Length-Code LZW Compression" says that "Encoders should
		// output a Clear code as the first code of each image data stream".
		//
		// LZW compression isn't only used by GIF, but it's cheap to follow
		// that directive unconditionally.
		 := uint32(1) << .litWidth
		if  := .write(, );  != nil {
			return 0, 
		}
		// After the starting clear code, the next code sent (for non-empty
		// input) is always a literal code.
		,  = uint32([0]), [1:]
	}
:
	for ,  := range  {
		 := uint32()
		 := <<8 | 
		// If there is a hash table hit for this key then we continue the loop
		// and do not emit a code yet.
		 := (>>12 ^ ) & tableMask
		for ,  := , .table[];  != invalidEntry; {
			if  == >>12 {
				 =  & maxCode
				continue 
			}
			 = ( + 1) & tableMask
			 = .table[]
		}
		// Otherwise, write the current code, and literal becomes the start of
		// the next emitted code.
		if .err = .write(, ); .err != nil {
			return 0, .err
		}
		 = 
		// Increment e.hi, the next implied code. If we run out of codes, reset
		// the writer state (including clearing the hash table) and continue.
		if  := .incHi();  != nil {
			if  == errOutOfCodes {
				continue
			}
			.err = 
			return 0, .err
		}
		// Otherwise, insert key -> e.hi into the map that e.table represents.
		for {
			if .table[] == invalidEntry {
				.table[] = ( << 12) | .hi
				break
			}
			 = ( + 1) & tableMask
		}
	}
	.savedCode = 
	return , nil
}

// Close closes the [Writer], flushing any pending output. It does not close
// w's underlying writer.
func ( *Writer) () error {
	if .err != nil {
		if .err == errClosed {
			return nil
		}
		return .err
	}
	// Make any future calls to Write return errClosed.
	.err = errClosed
	// Write the savedCode if valid.
	if .savedCode != invalidCode {
		if  := .write(, .savedCode);  != nil {
			return 
		}
		if  := .incHi();  != nil &&  != errOutOfCodes {
			return 
		}
	} else {
		// Write the starting clear code, as w.Write did not.
		 := uint32(1) << .litWidth
		if  := .write(, );  != nil {
			return 
		}
	}
	// Write the eof code.
	 := uint32(1)<<.litWidth + 1
	if  := .write(, );  != nil {
		return 
	}
	// Write the final bits.
	if .nBits > 0 {
		if .order == MSB {
			.bits >>= 24
		}
		if  := .w.WriteByte(uint8(.bits));  != nil {
			return 
		}
	}
	return .w.Flush()
}

// Reset clears the [Writer]'s state and allows it to be reused again
// as a new [Writer].
func ( *Writer) ( io.Writer,  Order,  int) {
	* = Writer{}
	.init(, , )
}

// NewWriter creates a new [io.WriteCloser].
// Writes to the returned [io.WriteCloser] are compressed and written to w.
// It is the caller's responsibility to call Close on the WriteCloser when
// finished writing.
// The number of bits to use for literal codes, litWidth, must be in the
// range [2,8] and is typically 8. Input bytes must be less than 1<<litWidth.
//
// It is guaranteed that the underlying type of the returned [io.WriteCloser]
// is a *[Writer].
func ( io.Writer,  Order,  int) io.WriteCloser {
	return newWriter(, , )
}

func newWriter( io.Writer,  Order,  int) *Writer {
	 := new(Writer)
	.init(, , )
	return 
}

func ( *Writer) ( io.Writer,  Order,  int) {
	switch  {
	case LSB:
		.write = (*Writer).writeLSB
	case MSB:
		.write = (*Writer).writeMSB
	default:
		.err = errors.New("lzw: unknown order")
		return
	}
	if  < 2 || 8 <  {
		.err = fmt.Errorf("lzw: litWidth %d out of range", )
		return
	}
	,  := .(writer)
	if ! &&  != nil {
		 = bufio.NewWriter()
	}
	.w = 
	 := uint()
	.order = 
	.width = 1 + 
	.litWidth = 
	.hi = 1<< + 1
	.overflow = 1 << ( + 1)
	.savedCode = invalidCode
}