package fse

import (
	
	
)

const (
	tablelogAbsoluteMax = 15
)

// Decompress a block of data.
// You can provide a scratch buffer to avoid allocations.
// If nil is provided a temporary one will be allocated.
// It is possible, but by no way guaranteed that corrupt data will
// return an error.
// It is up to the caller to verify integrity of the returned data.
// Use a predefined Scratch to set maximum acceptable output size.
func ( []byte,  *Scratch) ([]byte, error) {
	,  := .prepare()
	if  != nil {
		return nil, 
	}
	.Out = .Out[:0]
	 = .readNCount()
	if  != nil {
		return nil, 
	}
	 = .buildDtable()
	if  != nil {
		return nil, 
	}
	 = .decompress()
	if  != nil {
		return nil, 
	}

	return .Out, nil
}

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

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

	for  > 1 {
		if  {
			 := 
			for ( & 0xFFFF) == 0xFFFF {
				 += 24
				if .off < -5 {
					.advance(2)
					 = .Uint32() >> 
				} else {
					 >>= 16
					 += 16
				}
			}
			for ( & 3) == 3 {
				 += 3
				 >>= 2
				 += 2
			}
			 += uint16( & 3)
			 += 2
			if  > maxSymbolValue {
				return errors.New("maxSymbolValue too small")
			}
			for  <  {
				.norm[&0xff] = 0
				++
			}

			if .off <= -7 || .off+int(>>3) <= -4 {
				.advance( >> 3)
				 &= 7
				 = .Uint32() >> 
			} else {
				 >>= 2
			}
		}

		 := (2*() - 1) - ()
		var  int32

		if (int32() & ( - 1)) <  {
			 = int32() & ( - 1)
			 +=  - 1
		} else {
			 = int32() & (2* - 1)
			if  >=  {
				 -= 
			}
			 += 
		}

		-- // extra accuracy
		if  < 0 {
			// -1 means +1
			 += 
			 -= 
		} else {
			 -= 
			 += 
		}
		.norm[&0xff] = int16()
		++
		 =  == 0
		for  <  {
			--
			 >>= 1
		}
		if .off <= -7 || .off+int(>>3) <= -4 {
			.advance( >> 3)
			 &= 7
		} 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 nil
}

// 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.
type decSymbol struct {
	newState uint16
	symbol   uint8
	nbBits   uint8
}

// allocDtable will allocate decoding tables if they are not big enough.
func ( *Scratch) () {
	 := 1 << .actualTableLog
	if cap(.decTable) <  {
		.decTable = make([]decSymbol, )
	}
	.decTable = .decTable[:]

	if cap(.ct.tableSymbol) < 256 {
		.ct.tableSymbol = make([]byte, 256)
	}
	.ct.tableSymbol = .ct.tableSymbol[:256]

	if cap(.ct.stateTable) < 256 {
		.ct.stateTable = make([]uint16, 256)
	}
	.ct.stateTable = .ct.stateTable[:256]
}

// buildDtable will build the decoding table.
func ( *Scratch) () error {
	 := uint32(1 << .actualTableLog)
	 :=  - 1
	.allocDtable()
	 := .ct.stateTable[:256]

	// Init, lay down lowprob symbols
	.zeroBits = false
	{
		 := int16(1 << (.actualTableLog - 1))
		for ,  := range .norm[:.symbolLen] {
			if  == -1 {
				.decTable[].symbol = uint8()
				--
				[] = 1
			} else {
				if  >=  {
					.zeroBits = true
				}
				[] = uint16()
			}
		}
	}
	// Spread symbols
	{
		 :=  - 1
		 := tableStep()
		 := uint32(0)
		for ,  := range .norm[:.symbolLen] {
			for  := 0;  < int(); ++ {
				.decTable[].symbol = uint8()
				 = ( + ) & 
				for  >  {
					// lowprob area
					 = ( + ) & 
				}
			}
		}
		if  != 0 {
			// position must reach all cells once, otherwise normalizedCounter is incorrect
			return errors.New("corrupted input (position != 0)")
		}
	}

	// Build Decoding table
	{
		 := uint16(1 << .actualTableLog)
		for ,  := range .decTable {
			 := .symbol
			 := []
			[] =  + 1
			 := .actualTableLog - byte(highBits(uint32()))
			.decTable[].nbBits = 
			 := ( << ) - 
			if  >=  {
				return fmt.Errorf("newState (%d) outside table size (%d)", , )
			}
			if  == uint16() &&  == 0 {
				// Seems weird that this is possible with nbits > 0.
				return fmt.Errorf("newState (%d) == oldState (%d) and no bits", , )
			}
			.decTable[].newState = 
		}
	}
	return nil
}

// decompress will decompress the bitstream.
// If the buffer is over-read an error is returned.
func ( *Scratch) () error {
	 := &.bits
	if  := .init(.br.unread());  != nil {
		return 
	}

	var ,  decoder
	// Initialize and decode first state and symbol.
	.init(, .decTable, .actualTableLog)
	.init(, .decTable, .actualTableLog)

	// Use temp table to avoid bound checks/append penalty.
	var  = .ct.tableSymbol[:256]
	var  uint8

	// Main part
	if !.zeroBits {
		for .off >= 8 {
			.fillFast()
			[+0] = .nextFast()
			[+1] = .nextFast()
			.fillFast()
			[+2] = .nextFast()
			[+3] = .nextFast()
			 += 4
			// When off is 0, we have overflowed and should write.
			if  == 0 {
				.Out = append(.Out, ...)
				if len(.Out) >= .DecompressLimit {
					return fmt.Errorf("output size (%d) > DecompressLimit (%d)", len(.Out), .DecompressLimit)
				}
			}
		}
	} else {
		for .off >= 8 {
			.fillFast()
			[+0] = .next()
			[+1] = .next()
			.fillFast()
			[+2] = .next()
			[+3] = .next()
			 += 4
			if  == 0 {
				.Out = append(.Out, ...)
				// When off is 0, we have overflowed and should write.
				if len(.Out) >= .DecompressLimit {
					return fmt.Errorf("output size (%d) > DecompressLimit (%d)", len(.Out), .DecompressLimit)
				}
			}
		}
	}
	.Out = append(.Out, [:]...)

	// Final bits, a bit more expensive check
	for {
		if .finished() {
			.Out = append(.Out, .final(), .final())
			break
		}
		.fill()
		.Out = append(.Out, .next())
		if .finished() {
			.Out = append(.Out, .final(), .final())
			break
		}
		.Out = append(.Out, .next())
		if len(.Out) >= .DecompressLimit {
			return fmt.Errorf("output size (%d) > DecompressLimit (%d)", len(.Out), .DecompressLimit)
		}
	}
	return .close()
}

// decoder keeps track of the current state and updates it from the bitstream.
type decoder struct {
	state uint16
	br    *bitReader
	dt    []decSymbol
}

// init will initialize the decoder and read the first state from the stream.
func ( *decoder) ( *bitReader,  []decSymbol,  uint8) {
	.dt = 
	.br = 
	.state = .getBits()
}

// next returns the next symbol and sets the next state.
// At least tablelog bits must be available in the bit reader.
func ( *decoder) () uint8 {
	 := &.dt[.state]
	 := .br.getBits(.nbBits)
	.state = .newState + 
	return .symbol
}

// finished returns true if all bits have been read from the bitstream
// and the next state would require reading bits from the input.
func ( *decoder) () bool {
	return .br.finished() && .dt[.state].nbBits > 0
}

// final returns the current state symbol without decoding the next.
func ( *decoder) () uint8 {
	return .dt[.state].symbol
}

// nextFast returns the next symbol and sets the next state.
// This can only be used if no symbols are 0 bits.
// At least tablelog bits must be available in the bit reader.
func ( *decoder) () uint8 {
	 := .dt[.state]
	 := .br.getBitsFast(.nbBits)
	.state = .newState + 
	return .symbol
}