// Copyright 2009 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 flate

import (
	"io";
	"math";
	"os";
)

const (
	NoCompression		= 0;
	BestSpeed		= 1;
	fastCompression		= 3;
	BestCompression		= 9;
	DefaultCompression	= -1;
	logMaxOffsetSize	= 15;	// Standard DEFLATE
	wideLogMaxOffsetSize	= 22;	// Wide DEFLATE
	minMatchLength		= 3;	// The smallest match that the deflater looks for
	maxMatchLength		= 258;	// The longest match for the deflater
	minOffsetSize		= 1;	// The shortest offset that makes any sence

	// The maximum number of tokens we put into a single flat block, just too
	// stop things from getting too large.
	maxFlateBlockTokens	= 1 << 14;
	maxStoreBlockSize	= 65535;
	hashBits		= 15;
	hashSize		= 1 << hashBits;
	hashMask		= (1 << hashBits) - 1;
	hashShift		= (hashBits + minMatchLength - 1) / minMatchLength;
)

type syncPipeReader struct {
	*io.PipeReader;
	closeChan	chan bool;
}

func (sr *syncPipeReader) CloseWithError(err os.Error) os.Error {
	retErr := sr.PipeReader.CloseWithError(err);
	sr.closeChan <- true;	// finish writer close
	return retErr;
}

type syncPipeWriter struct {
	*io.PipeWriter;
	closeChan	chan bool;
}

type compressionLevel struct {
	good, lazy, nice, chain, fastSkipHashing int;
}

var levels = []compressionLevel{
	compressionLevel{},	// 0
	// For levels 1-3 we don't bother trying with lazy matches
	compressionLevel{3, 0, 8, 4, 4},
	compressionLevel{3, 0, 16, 8, 5},
	compressionLevel{3, 0, 32, 32, 6},
	// Levels 4-9 use increasingly more lazy matching
	// and increasingly stringent conditions for "good enough".
	compressionLevel{4, 4, 16, 16, math.MaxInt32},
	compressionLevel{8, 16, 32, 32, math.MaxInt32},
	compressionLevel{8, 16, 128, 128, math.MaxInt32},
	compressionLevel{8, 32, 128, 256, math.MaxInt32},
	compressionLevel{32, 128, 258, 1024, math.MaxInt32},
	compressionLevel{32, 258, 258, 4096, math.MaxInt32},
}

func (sw *syncPipeWriter) Close() os.Error {
	err := sw.PipeWriter.Close();
	<-sw.closeChan;	// wait for reader close
	return err;
}

func syncPipe() (*syncPipeReader, *syncPipeWriter) {
	r, w := io.Pipe();
	sr := &syncPipeReader{r, make(chan bool, 1)};
	sw := &syncPipeWriter{w, sr.closeChan};
	return sr, sw;
}

type deflater struct {
	level		int;
	logWindowSize	uint;
	w		*huffmanBitWriter;
	r		io.Reader;
	// (1 << logWindowSize) - 1.
	windowMask	int;

	// hashHead[hashValue] contains the largest inputIndex with the specified hash value
	hashHead	[]int;

	// If hashHead[hashValue] is within the current window, then
	// hashPrev[hashHead[hashValue] & windowMask] contains the previous index
	// with the same hash value.
	hashPrev	[]int;

	// If we find a match of length >= niceMatch, then we don't bother searching
	// any further.
	niceMatch	int;

	// If we find a match of length >= goodMatch, we only do a half-hearted
	// effort at doing lazy matching starting at the next character
	goodMatch	int;

	// The maximum number of chains we look at when finding a match
	maxChainLength	int;

	// The sliding window we use for matching
	window	[]byte;

	// The index just past the last valid character
	windowEnd	int;

	// index in "window" at which current block starts
	blockStart	int;
}

func (d *deflater) flush() os.Error {
	d.w.flush();
	return d.w.err;
}

func (d *deflater) fillWindow(index int) (int, os.Error) {
	wSize := d.windowMask + 1;
	if index >= wSize+wSize-(minMatchLength+maxMatchLength) {
		// shift the window by wSize
		copy(d.window, d.window[wSize:2*wSize]);
		index -= wSize;
		d.windowEnd -= wSize;
		if d.blockStart >= wSize {
			d.blockStart -= wSize
		} else {
			d.blockStart = math.MaxInt32
		}
		for i, h := range d.hashHead {
			d.hashHead[i] = max(h-wSize, -1)
		}
		for i, h := range d.hashPrev {
			d.hashPrev[i] = max(h-wSize, -1)
		}
	}
	var count int;
	var err os.Error;
	count, err = io.ReadAtLeast(d.r, d.window[d.windowEnd:], 1);
	d.windowEnd += count;
	if err == os.EOF {
		return index, nil
	}
	return index, err;
}

func (d *deflater) writeBlock(tokens []token, index int, eof bool) os.Error {
	if index > 0 || eof {
		var window []byte;
		if d.blockStart <= index {
			window = d.window[d.blockStart:index]
		}
		d.blockStart = index;
		d.w.writeBlock(tokens, eof, window);
		return d.w.err;
	}
	return nil;
}

// Try to find a match starting at index whose length is greater than prevSize.
// We only look at chainCount possibilities before giving up.
func (d *deflater) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
	win := d.window[0 : pos+min(maxMatchLength, lookahead)];

	// We quit when we get a match that's at least nice long
	nice := min(d.niceMatch, len(win)-pos);

	// If we've got a match that's good enough, only look in 1/4 the chain.
	tries := d.maxChainLength;
	length = prevLength;
	if length >= d.goodMatch {
		tries >>= 2
	}

	w0 := win[pos];
	w1 := win[pos+1];
	wEnd := win[pos+length];
	minIndex := pos - (d.windowMask + 1);

	for i := prevHead; tries > 0; tries-- {
		if w0 == win[i] && w1 == win[i+1] && wEnd == win[i+length] {
			// The hash function ensures that if win[i] and win[i+1] match, win[i+2] matches

			n := 3;
			for pos+n < len(win) && win[i+n] == win[pos+n] {
				n++
			}
			if n > length && (n > 3 || pos-i <= 4096) {
				length = n;
				offset = pos - i;
				ok = true;
				if n >= nice {
					// The match is good enough that we don't try to find a better one.
					break
				}
				wEnd = win[pos+n];
			}
		}
		if i == minIndex {
			// hashPrev[i & windowMask] has already been overwritten, so stop now.
			break
		}
		if i = d.hashPrev[i&d.windowMask]; i < minIndex || i < 0 {
			break
		}
	}
	return;
}

func (d *deflater) writeStoredBlock(buf []byte) os.Error {
	if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
		return d.w.err
	}
	d.w.writeBytes(buf);
	return d.w.err;
}

func (d *deflater) storedDeflate() os.Error {
	buf := make([]byte, maxStoreBlockSize);
	for {
		n, err := d.r.Read(buf);
		if n > 0 {
			if err := d.writeStoredBlock(buf[0:n]); err != nil {
				return err
			}
		}
		if err != nil {
			if err == os.EOF {
				break
			}
			return err;
		}
	}
	return nil;
}

func (d *deflater) doDeflate() (err os.Error) {
	// init
	d.windowMask = 1<<d.logWindowSize - 1;
	d.hashHead = make([]int, hashSize);
	d.hashPrev = make([]int, 1<<d.logWindowSize);
	d.window = make([]byte, 2<<d.logWindowSize);
	fillInts(d.hashHead, -1);
	tokens := make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1);
	l := levels[d.level];
	d.goodMatch = l.good;
	d.niceMatch = l.nice;
	d.maxChainLength = l.chain;
	lazyMatch := l.lazy;
	length := minMatchLength - 1;
	offset := 0;
	byteAvailable := false;
	isFastDeflate := l.fastSkipHashing != 0;
	index := 0;
	// run
	if index, err = d.fillWindow(index); err != nil {
		return
	}
	maxOffset := d.windowMask + 1;	// (1 << logWindowSize);
	// only need to change when you refill the window
	windowEnd := d.windowEnd;
	maxInsertIndex := windowEnd - (minMatchLength - 1);
	ti := 0;

	hash := int(0);
	if index < maxInsertIndex {
		hash = int(d.window[index])<<hashShift + int(d.window[index+1])
	}
	chainHead := -1;
	for {
		if index > windowEnd {
			panic("index > windowEnd")
		}
		lookahead := windowEnd - index;
		if lookahead < minMatchLength+maxMatchLength {
			if index, err = d.fillWindow(index); err != nil {
				return
			}
			windowEnd = d.windowEnd;
			if index > windowEnd {
				panic("index > windowEnd")
			}
			maxInsertIndex = windowEnd - (minMatchLength - 1);
			lookahead = windowEnd - index;
			if lookahead == 0 {
				break
			}
		}
		if index < maxInsertIndex {
			// Update the hash
			hash = (hash<<hashShift + int(d.window[index+2])) & hashMask;
			chainHead = d.hashHead[hash];
			d.hashPrev[index&d.windowMask] = chainHead;
			d.hashHead[hash] = index;
		}
		prevLength := length;
		prevOffset := offset;
		minIndex := max(index-maxOffset, 0);
		length = minMatchLength - 1;
		offset = 0;

		if chainHead >= minIndex &&
			(isFastDeflate && lookahead > minMatchLength-1 ||
				!isFastDeflate && lookahead > prevLength && prevLength < lazyMatch) {
			if newLength, newOffset, ok := d.findMatch(index, chainHead, minMatchLength-1, lookahead); ok {
				length = newLength;
				offset = newOffset;
			}
		}
		if isFastDeflate && length >= minMatchLength ||
			!isFastDeflate && prevLength >= minMatchLength && length <= prevLength {
			// There was a match at the previous step, and the current match is
			// not better. Output the previous match.
			if isFastDeflate {
				tokens[ti] = matchToken(uint32(length-minMatchLength), uint32(offset-minOffsetSize))
			} else {
				tokens[ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize))
			}
			ti++;
			// Insert in the hash table all strings up to the end of the match.
			// index and index-1 are already inserted. If there is not enough
			// lookahead, the last two strings are not inserted into the hash
			// table.
			if length <= l.fastSkipHashing {
				var newIndex int;
				if isFastDeflate {
					newIndex = index + length
				} else {
					newIndex = prevLength - 1
				}
				for index++; index < newIndex; index++ {
					if index < maxInsertIndex {
						hash = (hash<<hashShift + int(d.window[index+2])) & hashMask;
						// Get previous value with the same hash.
						// Our chain should point to the previous value.
						d.hashPrev[index&d.windowMask] = d.hashHead[hash];
						// Set the head of the hash chain to us.
						d.hashHead[hash] = index;
					}
				}
				if !isFastDeflate {
					byteAvailable = false;
					length = minMatchLength - 1;
				}
			} else {
				// For matches this long, we don't bother inserting each individual
				// item into the table.
				index += length;
				hash = (int(d.window[index])<<hashShift + int(d.window[index+1]));
			}
			if ti == maxFlateBlockTokens {
				// The block includes the current character
				if err = d.writeBlock(tokens, index, false); err != nil {
					return
				}
				ti = 0;
			}
		} else {
			if isFastDeflate || byteAvailable {
				i := index - 1;
				if isFastDeflate {
					i = index
				}
				tokens[ti] = literalToken(uint32(d.window[i]) & 0xFF);
				ti++;
				if ti == maxFlateBlockTokens {
					if err = d.writeBlock(tokens, i+1, false); err != nil {
						return
					}
					ti = 0;
				}
			}
			index++;
			if !isFastDeflate {
				byteAvailable = true
			}
		}

	}
	if byteAvailable {
		// There is still one pending token that needs to be flushed
		tokens[ti] = literalToken(uint32(d.window[index-1]) & 0xFF);
		ti++;
	}

	if ti > 0 {
		if err = d.writeBlock(tokens[0:ti], index, false); err != nil {
			return
		}
	}
	return;
}

func (d *deflater) deflater(r io.Reader, w io.Writer, level int, logWindowSize uint) (err os.Error) {
	d.r = r;
	d.w = newHuffmanBitWriter(w);
	d.level = level;
	d.logWindowSize = logWindowSize;

	switch {
	case level == NoCompression:
		err = d.storedDeflate()
	case level == DefaultCompression:
		d.level = 6;
		fallthrough;
	case 1 <= level && level <= 9:
		err = d.doDeflate()
	default:
		return WrongValueError{"level", 0, 9, int32(level)}
	}

	if err != nil {
		return err
	}
	if d.w.writeStoredHeader(0, true); d.w.err != nil {
		return d.w.err
	}
	return d.flush();
}

func newDeflater(w io.Writer, level int, logWindowSize uint) io.WriteCloser {
	var d deflater;
	pr, pw := syncPipe();
	go func() {
		err := d.deflater(pr, w, level, logWindowSize);
		pr.CloseWithError(err);
	}();
	return pw;
}

func NewDeflater(w io.Writer, level int) io.WriteCloser {
	return newDeflater(w, level, logMaxOffsetSize)
}