// Copyright 2019+ Klaus Post. All rights reserved.
// License information can be found in the LICENSE file.
// Based on work by Yann Collet, released under BSD License.

package zstd

import (
	
	
	
	
)

const (
	tablelogAbsoluteMax = 9
)

const (
	/*!MEMORY_USAGE :
	 *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
	 *  Increasing memory usage improves compression ratio
	 *  Reduced memory usage can improve speed, due to cache effect
	 *  Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
	maxMemoryUsage = tablelogAbsoluteMax + 2

	maxTableLog    = maxMemoryUsage - 2
	maxTablesize   = 1 << maxTableLog
	maxTableMask   = (1 << maxTableLog) - 1
	minTablelog    = 5
	maxSymbolValue = 255
)

// fseDecoder provides temporary storage for compression and decompression.
type fseDecoder struct {
	dt             [maxTablesize]decSymbol // Decompression table.
	symbolLen      uint16                  // Length of active part of the symbol table.
	actualTableLog uint8                   // Selected tablelog.
	maxBits        uint8                   // Maximum number of additional bits

	// used for table creation to avoid allocations.
	stateTable [256]uint16
	norm       [maxSymbolValue + 1]int16
	preDefined bool
}

// tableStep returns the next table index.
func ( uint32) uint32 {
	return ( >> 1) + ( >> 3) + 3
}

// readNCount will read the symbol distribution so decoding tables can be constructed.
func ( *fseDecoder) ( *byteReader,  uint16) error {
	var (
		   uint16
		 bool
	)
	if .remain() < 4 {
		return errors.New("input too small")
	}
	 := .Uint32NC()
	 := uint(( & 0xF) + minTablelog) // extract tableLog
	if  > tablelogAbsoluteMax {
		println("Invalid tablelog:", )
		return errors.New("tableLog too large")
	}
	 >>= 4
	 := uint(4)

	.actualTableLog = uint8()
	 := int32((1 << ) + 1)
	 := int32(1 << )
	 := int32(0)
	++

	for  > 1 &&  <=  {
		if  {
			//println("prev0")
			 := 
			for ( & 0xFFFF) == 0xFFFF {
				//println("24 x 0")
				 += 24
				if  := .remain();  > 5 {
					.advance(2)
					// The check above should make sure we can read 32 bits
					 = .Uint32NC() >> 
				} else {
					// end of bit stream
					 >>= 16
					 += 16
				}
			}
			//printf("bitstream: %d, 0b%b", bitStream&3, bitStream)
			for ( & 3) == 3 {
				 += 3
				 >>= 2
				 += 2
			}
			 += uint16( & 3)
			 += 2

			if  > maxSymbolValue {
				return errors.New("maxSymbolValue too small")
			}
			//println("inserting ", n0-charnum, "zeroes from idx", charnum, "ending before", n0)
			for  <  {
				.norm[uint8()] = 0
				++
			}

			if  := .remain();  >= 7 || -int(>>3) >= 4 {
				.advance( >> 3)
				 &= 7
				// The check above should make sure we can read 32 bits
				 = .Uint32NC() >> 
			} else {
				 >>= 2
			}
		}

		 := (2* - 1) - 
		var  int32

		if int32()&(-1) <  {
			 = int32() & ( - 1)
			if debugAsserts &&  < 1 {
				panic("nbBits underflow")
			}
			 +=  - 1
		} else {
			 = int32() & (2* - 1)
			if  >=  {
				 -= 
			}
			 += 
		}

		// extra accuracy
		--
		if  < 0 {
			// -1 means +1
			 += 
			 -= 
		} else {
			 -= 
			 += 
		}
		.norm[&0xff] = int16()
		++
		 =  == 0
		for  <  {
			--
			 >>= 1
		}

		if  := .remain();  >= 7 || -int(>>3) >= 4 {
			.advance( >> 3)
			 &= 7
			// The check above should make sure we can read 32 bits
			 = .Uint32NC() >> ( & 31)
		} else {
			 -= (uint)(8 * (len(.b) - 4 - .off))
			.off = len(.b) - 4
			 = .Uint32() >> ( & 31)
		}
	}
	.symbolLen = 
	if .symbolLen <= 1 {
		return fmt.Errorf("symbolLen (%d) too small", .symbolLen)
	}
	if .symbolLen > maxSymbolValue+1 {
		return fmt.Errorf("symbolLen (%d) too big", .symbolLen)
	}
	if  != 1 {
		return fmt.Errorf("corruption detected (remaining %d != 1)", )
	}
	if  > 32 {
		return fmt.Errorf("corruption detected (bitCount %d > 32)", )
	}
	if  != 1<<.actualTableLog {
		return fmt.Errorf("corruption detected (total %d != %d)", , 1<<.actualTableLog)
	}
	.advance(( + 7) >> 3)
	return .buildDtable()
}

func ( *fseDecoder) ( io.Reader) {
	 := func( error) {
		if  != nil {
			panic()
		}
	}
	// 	dt             [maxTablesize]decSymbol // Decompression table.
	//	symbolLen      uint16                  // Length of active part of the symbol table.
	//	actualTableLog uint8                   // Selected tablelog.
	//	maxBits        uint8                   // Maximum number of additional bits
	//	// used for table creation to avoid allocations.
	//	stateTable [256]uint16
	//	norm       [maxSymbolValue + 1]int16
	//	preDefined bool
	(binary.Read(, binary.LittleEndian, &.dt))
	(binary.Read(, binary.LittleEndian, &.symbolLen))
	(binary.Read(, binary.LittleEndian, &.actualTableLog))
	(binary.Read(, binary.LittleEndian, &.maxBits))
	(binary.Read(, binary.LittleEndian, &.stateTable))
	(binary.Read(, binary.LittleEndian, &.norm))
	(binary.Read(, binary.LittleEndian, &.preDefined))
}

// decSymbol contains information about a state entry,
// Including the state offset base, the output symbol and
// the number of bits to read for the low part of the destination state.
// Using a composite uint64 is faster than a struct with separate members.
type decSymbol uint64

func (,  uint8,  uint16,  uint32) decSymbol {
	return decSymbol() | (decSymbol() << 8) | (decSymbol() << 16) | (decSymbol() << 32)
}

func ( decSymbol) () uint8 {
	return uint8()
}

func ( decSymbol) () uint8 {
	return uint8( >> 8)
}

func ( decSymbol) () uint16 {
	return uint16( >> 16)
}

func ( decSymbol) () int {
	return int( >> 32)
}

func ( *decSymbol) ( uint8) {
	const  = 0xffffffffffffff00
	* = (* & ) | decSymbol()
}

func ( *decSymbol) ( uint8) {
	const  = 0xffffffffffff00ff
	* = (* & ) | (decSymbol() << 8)
}

func ( *decSymbol) ( uint16) {
	const  = 0xffffffff0000ffff
	* = (* & ) | decSymbol()<<16
}

func ( *decSymbol) ( uint8,  uint32) {
	const  = 0xffff00ff
	* = (* & ) | (decSymbol() << 8) | (decSymbol() << 32)
}

// decSymbolValue returns the transformed decSymbol for the given symbol.
func ( uint8,  []baseOffset) (decSymbol, error) {
	if int() >= len() {
		return 0, fmt.Errorf("rle symbol %d >= max %d", , len())
	}
	 := []
	return newDecSymbol(0, .addBits, 0, .baseLine), nil
}

// setRLE will set the decoder til RLE mode.
func ( *fseDecoder) ( decSymbol) {
	.actualTableLog = 0
	.maxBits = .addBits()
	.dt[0] = 
}

// transform will transform the decoder table into a table usable for
// decoding without having to apply the transformation while decoding.
// The state will contain the base value and the number of bits to read.
func ( *fseDecoder) ( []baseOffset) error {
	 := uint16(1 << .actualTableLog)
	.maxBits = 0
	for ,  := range .dt[:] {
		 := .addBits()
		if int() >= len() {
			return fmt.Errorf("invalid decoding table entry %d, symbol %d >= max (%d)", , .addBits(), len())
		}
		 := []
		if .addBits > .maxBits {
			.maxBits = .addBits
		}
		.setExt(.addBits, .baseLine)
		.dt[] = 
	}
	return nil
}

type fseState struct {
	dt    []decSymbol
	state decSymbol
}

// Initialize and decodeAsync first state and symbol.
func ( *fseState) ( *bitReader,  uint8,  []decSymbol) {
	.dt = 
	.fill()
	.state = [.getBits()]
}

// final returns the current state symbol without decoding the next.
func ( decSymbol) () (int, uint8) {
	return .baselineInt(), .addBits()
}