package brotli

import (
	
	
)

const maxHuffmanTreeSize = (2*numCommandSymbols + 1)

/* The maximum size of Huffman dictionary for distances assuming that
   NPOSTFIX = 0 and NDIRECT = 0. */
const maxSimpleDistanceAlphabetSize = 140

/* Represents the range of values belonging to a prefix code:
   [offset, offset + 2^nbits) */
type prefixCodeRange struct {
	offset uint32
	nbits  uint32
}

var kBlockLengthPrefixCode = [numBlockLenSymbols]prefixCodeRange{
	prefixCodeRange{1, 2},
	prefixCodeRange{5, 2},
	prefixCodeRange{9, 2},
	prefixCodeRange{13, 2},
	prefixCodeRange{17, 3},
	prefixCodeRange{25, 3},
	prefixCodeRange{33, 3},
	prefixCodeRange{41, 3},
	prefixCodeRange{49, 4},
	prefixCodeRange{65, 4},
	prefixCodeRange{81, 4},
	prefixCodeRange{97, 4},
	prefixCodeRange{113, 5},
	prefixCodeRange{145, 5},
	prefixCodeRange{177, 5},
	prefixCodeRange{209, 5},
	prefixCodeRange{241, 6},
	prefixCodeRange{305, 6},
	prefixCodeRange{369, 7},
	prefixCodeRange{497, 8},
	prefixCodeRange{753, 9},
	prefixCodeRange{1265, 10},
	prefixCodeRange{2289, 11},
	prefixCodeRange{4337, 12},
	prefixCodeRange{8433, 13},
	prefixCodeRange{16625, 24},
}

func blockLengthPrefixCode( uint32) uint32 {
	var  uint32
	if  >= 177 {
		if  >= 753 {
			 = 20
		} else {
			 = 14
		}
	} else if  >= 41 {
		 = 7
	} else {
		 = 0
	}
	for  < (numBlockLenSymbols-1) &&  >= kBlockLengthPrefixCode[+1].offset {
		++
	}
	return 
}

func getBlockLengthPrefixCode( uint32,  *uint,  *uint32,  *uint32) {
	* = uint(blockLengthPrefixCode(uint32()))
	* = kBlockLengthPrefixCode[*].nbits
	* =  - kBlockLengthPrefixCode[*].offset
}

type blockTypeCodeCalculator struct {
	last_type        uint
	second_last_type uint
}

func initBlockTypeCodeCalculator( *blockTypeCodeCalculator) {
	.last_type = 1
	.second_last_type = 0
}

func nextBlockTypeCode( *blockTypeCodeCalculator,  byte) uint {
	var  uint
	if uint() == .last_type+1 {
		 = 1
	} else if uint() == .second_last_type {
		 = 0
	} else {
		 = uint() + 2
	}
	.second_last_type = .last_type
	.last_type = uint()
	return 
}

/* |nibblesbits| represents the 2 bits to encode MNIBBLES (0-3)
   REQUIRES: length > 0
   REQUIRES: length <= (1 << 24) */
func encodeMlen( uint,  *uint64,  *uint,  *uint64) {
	var  uint
	if  == 1 {
		 = 1
	} else {
		 = uint(log2FloorNonZero(uint(uint32(-1)))) + 1
	}
	var  uint
	if  < 16 {
		 = 16
	} else {
		 = ( + 3)
	}
	var  uint =  / 4
	assert( > 0)
	assert( <= 1<<24)
	assert( <= 24)
	* = uint64() - 4
	* =  * 4
	* = uint64() - 1
}

func storeCommandExtra( *command,  *uint,  []byte) {
	var  uint32 = commandCopyLenCode()
	var  uint16 = getInsertLengthCode(uint(.insert_len_))
	var  uint16 = getCopyLengthCode(uint())
	var  uint32 = getInsertExtra()
	var  uint64 = uint64(.insert_len_) - uint64(getInsertBase())
	var  uint64 = uint64() - uint64(getCopyBase())
	var  uint64 = << | 
	writeBits(uint(+getCopyExtra()), , , )
}

/* Data structure that stores almost everything that is needed to encode each
   block switch command. */
type blockSplitCode struct {
	type_code_calculator blockTypeCodeCalculator
	type_depths          [maxBlockTypeSymbols]byte
	type_bits            [maxBlockTypeSymbols]uint16
	length_depths        [numBlockLenSymbols]byte
	length_bits          [numBlockLenSymbols]uint16
}

/* Stores a number between 0 and 255. */
func storeVarLenUint8( uint,  *uint,  []byte) {
	if  == 0 {
		writeBits(1, 0, , )
	} else {
		var  uint = uint(log2FloorNonZero())
		writeBits(1, 1, , )
		writeBits(3, uint64(), , )
		writeBits(, uint64()-(uint64(uint(1))<<), , )
	}
}

/* Stores the compressed meta-block header.
   REQUIRES: length > 0
   REQUIRES: length <= (1 << 24) */
func storeCompressedMetaBlockHeader( bool,  uint,  *uint,  []byte) {
	var  uint64
	var  uint
	var  uint64
	var  uint64
	if  {
		 = 1
	} else {
		 = 0
	}

	/* Write ISLAST bit. */
	writeBits(1, , , )

	/* Write ISEMPTY bit. */
	if  {
		writeBits(1, 0, , )
	}

	encodeMlen(, &, &, &)
	writeBits(2, , , )
	writeBits(, , , )

	if ! {
		/* Write ISUNCOMPRESSED bit. */
		writeBits(1, 0, , )
	}
}

/* Stores the uncompressed meta-block header.
   REQUIRES: length > 0
   REQUIRES: length <= (1 << 24) */
func storeUncompressedMetaBlockHeader( uint,  *uint,  []byte) {
	var  uint64
	var  uint
	var  uint64

	/* Write ISLAST bit.
	   Uncompressed block cannot be the last one, so set to 0. */
	writeBits(1, 0, , )

	encodeMlen(, &, &, &)
	writeBits(2, , , )
	writeBits(, , , )

	/* Write ISUNCOMPRESSED bit. */
	writeBits(1, 1, , )
}

var storeHuffmanTreeOfHuffmanTreeToBitMask_kStorageOrder = [codeLengthCodes]byte{1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15}

var storeHuffmanTreeOfHuffmanTreeToBitMask_kHuffmanBitLengthHuffmanCodeSymbols = [6]byte{0, 7, 3, 2, 1, 15}
var storeHuffmanTreeOfHuffmanTreeToBitMask_kHuffmanBitLengthHuffmanCodeBitLengths = [6]byte{2, 4, 3, 2, 2, 4}

func storeHuffmanTreeOfHuffmanTreeToBitMask( int,  []byte,  *uint,  []byte) {
	var  uint = 0
	var  uint = codeLengthCodes
	/* The bit lengths of the Huffman code over the code length alphabet
	   are compressed with the following static Huffman code:
	     Symbol   Code
	     ------   ----
	     0          00
	     1        1110
	     2         110
	     3          01
	     4          10
	     5        1111 */

	/* Throw away trailing zeros: */
	if  > 1 {
		for ;  > 0; -- {
			if [storeHuffmanTreeOfHuffmanTreeToBitMask_kStorageOrder[-1]] != 0 {
				break
			}
		}
	}

	if [storeHuffmanTreeOfHuffmanTreeToBitMask_kStorageOrder[0]] == 0 && [storeHuffmanTreeOfHuffmanTreeToBitMask_kStorageOrder[1]] == 0 {
		 = 2 /* skips two. */
		if [storeHuffmanTreeOfHuffmanTreeToBitMask_kStorageOrder[2]] == 0 {
			 = 3 /* skips three. */
		}
	}

	writeBits(2, uint64(), , )
	{
		var  uint
		for  = ;  < ; ++ {
			var  uint = uint([storeHuffmanTreeOfHuffmanTreeToBitMask_kStorageOrder[]])
			writeBits(uint(storeHuffmanTreeOfHuffmanTreeToBitMask_kHuffmanBitLengthHuffmanCodeBitLengths[]), uint64(storeHuffmanTreeOfHuffmanTreeToBitMask_kHuffmanBitLengthHuffmanCodeSymbols[]), , )
		}
	}
}

func storeHuffmanTreeToBitMask( uint,  []byte,  []byte,  []byte,  []uint16,  *uint,  []byte) {
	var  uint
	for  = 0;  < ; ++ {
		var  uint = uint([])
		writeBits(uint([]), uint64([]), , )

		/* Extra bits */
		switch  {
		case repeatPreviousCodeLength:
			writeBits(2, uint64([]), , )

		case repeatZeroCodeLength:
			writeBits(3, uint64([]), , )
		}
	}
}

func storeSimpleHuffmanTree( []byte,  []uint,  uint,  uint,  *uint,  []byte) {
	/* value of 1 indicates a simple Huffman code */
	writeBits(2, 1, , )

	writeBits(2, uint64()-1, , ) /* NSYM - 1 */
	{
		/* Sort */
		var  uint
		for  = 0;  < ; ++ {
			var  uint
			for  =  + 1;  < ; ++ {
				if [[]] < [[]] {
					var  uint = []
					[] = []
					[] = 
				}
			}
		}
	}

	if  == 2 {
		writeBits(, uint64([0]), , )
		writeBits(, uint64([1]), , )
	} else if  == 3 {
		writeBits(, uint64([0]), , )
		writeBits(, uint64([1]), , )
		writeBits(, uint64([2]), , )
	} else {
		writeBits(, uint64([0]), , )
		writeBits(, uint64([1]), , )
		writeBits(, uint64([2]), , )
		writeBits(, uint64([3]), , )

		/* tree-select */
		var  int
		if [[0]] == 1 {
			 = 1
		} else {
			 = 0
		}
		writeBits(1, uint64(), , )
	}
}

/* num = alphabet size
   depths = symbol depths */
func storeHuffmanTree( []byte,  uint,  []huffmanTree,  *uint,  []byte) {
	var  [numCommandSymbols]byte
	var  [numCommandSymbols]byte
	var  uint = 0
	var  = [codeLengthCodes]byte{0}
	var  [codeLengthCodes]uint16
	var  = [codeLengthCodes]uint32{0}
	var  uint
	var  int = 0
	/* Write the Huffman tree into the brotli-representation.
	   The command alphabet is the largest, so this allocation will fit all
	   alphabets. */

	var  uint = 0

	assert( <= numCommandSymbols)

	writeHuffmanTree(, , &, [:], [:])

	/* Calculate the statistics of the Huffman tree in brotli-representation. */
	for  = 0;  < ; ++ {
		[[]]++
	}

	for  = 0;  < codeLengthCodes; ++ {
		if [] != 0 {
			if  == 0 {
				 = 
				 = 1
			} else if  == 1 {
				 = 2
				break
			}
		}
	}

	/* Calculate another Huffman tree to use for compressing both the
	   earlier Huffman tree with. */
	createHuffmanTree([:], codeLengthCodes, 5, , [:])

	convertBitDepthsToSymbols([:], codeLengthCodes, [:])

	/* Now, we have all the data, let's start storing it */
	storeHuffmanTreeOfHuffmanTreeToBitMask(, [:], , )

	if  == 1 {
		[] = 0
	}

	/* Store the real Huffman tree now. */
	storeHuffmanTreeToBitMask(, [:], [:], [:], [:], , )
}

/* Builds a Huffman tree from histogram[0:length] into depth[0:length] and
   bits[0:length] and stores the encoded tree to the bit stream. */
func buildAndStoreHuffmanTree( []uint32,  uint,  uint,  []huffmanTree,  []byte,  []uint16,  *uint,  []byte) {
	var  uint = 0
	var  = [4]uint{0}
	var  uint
	var  uint = 0
	for  = 0;  < ; ++ {
		if [] != 0 {
			if  < 4 {
				[] = 
			} else if  > 4 {
				break
			}

			++
		}
	}
	{
		var  uint =  - 1
		for  != 0 {
			 >>= 1
			++
		}
	}

	if  <= 1 {
		writeBits(4, 1, , )
		writeBits(, uint64([0]), , )
		[[0]] = 0
		[[0]] = 0
		return
	}

	for  := 0;  < int(); ++ {
		[] = 0
	}
	createHuffmanTree(, , 15, , )
	convertBitDepthsToSymbols(, , )

	if  <= 4 {
		storeSimpleHuffmanTree(, [:], , , , )
	} else {
		storeHuffmanTree(, , , , )
	}
}

func sortHuffmanTree1( huffmanTree,  huffmanTree) bool {
	return .total_count_ < .total_count_
}

var huffmanTreePool sync.Pool

func buildAndStoreHuffmanTreeFast( []uint32,  uint,  uint,  []byte,  []uint16,  *uint,  []byte) {
	var  uint = 0
	var  = [4]uint{0}
	var  uint = 0
	var  uint = 
	for  != 0 {
		if [] != 0 {
			if  < 4 {
				[] = 
			}

			++
			 -= uint([])
		}

		++
	}

	if  <= 1 {
		writeBits(4, 1, , )
		writeBits(, uint64([0]), , )
		[[0]] = 0
		[[0]] = 0
		return
	}

	for  := 0;  < int(); ++ {
		[] = 0
	}
	{
		var  uint = 2* + 1
		,  := huffmanTreePool.Get().(*[]huffmanTree)
		if  == nil || cap(*) < int() {
			 := make([]huffmanTree, )
			 = &
		} else {
			* = (*)[:]
		}
		var  uint32
		for  = 1; ;  *= 2 {
			var  int = 0
			var  uint
			for  = ;  != 0; {
				--
				if [] != 0 {
					if [] >=  {
						initHuffmanTree(&(*)[:][0], [], -1, int16())
					} else {
						initHuffmanTree(&(*)[:][0], , -1, int16())
					}

					++
				}
			}
			{
				var  int = 
				/* Points to the next leaf node. */ /* Points to the next non-leaf node. */
				var  huffmanTree
				var  int = 0
				var  int =  + 1
				var  int

				sortHuffmanTreeItems(*, uint(), huffmanTreeComparator(sortHuffmanTree1))

				/* The nodes are:
				   [0, n): the sorted leaf nodes that we start with.
				   [n]: we add a sentinel here.
				   [n + 1, 2n): new parent nodes are added here, starting from
				                (n+1). These are naturally in ascending order.
				   [2n]: we add a sentinel at the end as well.
				   There will be (2n+1) elements at the end. */
				initHuffmanTree(&, math.MaxUint32, -1, -1)

				(*)[] = 
				++
				(*)[] = 
				++

				for  =  - 1;  > 0; -- {
					var  int
					var  int
					if (*)[].total_count_ <= (*)[].total_count_ {
						 = 
						++
					} else {
						 = 
						++
					}

					if (*)[].total_count_ <= (*)[].total_count_ {
						 = 
						++
					} else {
						 = 
						++
					}

					/* The sentinel node becomes the parent node. */
					(*)[-1].total_count_ = (*)[].total_count_ + (*)[].total_count_

					(*)[-1].index_left_ = int16()
					(*)[-1].index_right_or_value_ = int16()

					/* Add back the last sentinel node. */
					(*)[] = 
					++
				}

				if setDepth(2*-1, *, , 14) {
					/* We need to pack the Huffman tree in 14 bits. If this was not
					   successful, add fake entities to the lowest values and retry. */
					break
				}
			}
		}

		huffmanTreePool.Put()
	}

	convertBitDepthsToSymbols(, , )
	if  <= 4 {
		var  uint

		/* value of 1 indicates a simple Huffman code */
		writeBits(2, 1, , )

		writeBits(2, uint64()-1, , ) /* NSYM - 1 */

		/* Sort */
		for  = 0;  < ; ++ {
			var  uint
			for  =  + 1;  < ; ++ {
				if [[]] < [[]] {
					var  uint = []
					[] = []
					[] = 
				}
			}
		}

		if  == 2 {
			writeBits(, uint64([0]), , )
			writeBits(, uint64([1]), , )
		} else if  == 3 {
			writeBits(, uint64([0]), , )
			writeBits(, uint64([1]), , )
			writeBits(, uint64([2]), , )
		} else {
			writeBits(, uint64([0]), , )
			writeBits(, uint64([1]), , )
			writeBits(, uint64([2]), , )
			writeBits(, uint64([3]), , )

			/* tree-select */
			var  int
			if [[0]] == 1 {
				 = 1
			} else {
				 = 0
			}
			writeBits(1, uint64(), , )
		}
	} else {
		var  byte = 8
		var  uint

		/* Complex Huffman Tree */
		storeStaticCodeLengthCode(, )

		/* Actual RLE coding. */
		for  = 0;  < ; {
			var  byte = []
			var  uint = 1
			var  uint
			for  =  + 1;  <  && [] == ; ++ {
				++
			}

			 += 
			if  == 0 {
				writeBits(uint(kZeroRepsDepth[]), kZeroRepsBits[], , )
			} else {
				if  !=  {
					writeBits(uint(kCodeLengthDepth[]), uint64(kCodeLengthBits[]), , )
					--
				}

				if  < 3 {
					for  != 0 {
						--
						writeBits(uint(kCodeLengthDepth[]), uint64(kCodeLengthBits[]), , )
					}
				} else {
					 -= 3
					writeBits(uint(kNonZeroRepsDepth[]), kNonZeroRepsBits[], , )
				}

				 = 
			}
		}
	}
}

func indexOf( []byte,  uint,  byte) uint {
	var  uint = 0
	for ;  < ; ++ {
		if [] ==  {
			return 
		}
	}

	return 
}

func moveToFront( []byte,  uint) {
	var  byte = []
	var  uint
	for  = ;  != 0; -- {
		[] = [-1]
	}

	[0] = 
}

func moveToFrontTransform( []uint32,  uint,  []uint32) {
	var  uint
	var  [256]byte
	var  uint32
	if  == 0 {
		return
	}

	 = [0]
	for  = 1;  < ; ++ {
		if [] >  {
			 = []
		}
	}

	assert( < 256)
	for  = 0; uint32() <= ; ++ {
		[] = byte()
	}
	{
		var  uint = uint( + 1)
		for  = 0;  < ; ++ {
			var  uint = indexOf([:], , byte([]))
			assert( < )
			[] = uint32()
			moveToFront([:], )
		}
	}
}

/* Finds runs of zeros in v[0..in_size) and replaces them with a prefix code of
   the run length plus extra bits (lower 9 bits is the prefix code and the rest
   are the extra bits). Non-zero values in v[] are shifted by
   *max_length_prefix. Will not create prefix codes bigger than the initial
   value of *max_run_length_prefix. The prefix code of run length L is simply
   Log2Floor(L) and the number of extra bits is the same as the prefix code. */
func runLengthCodeZeros( uint,  []uint32,  *uint,  *uint32) {
	var  uint32 = 0
	var  uint
	var  uint32
	for  = 0;  < ; {
		var  uint32 = 0
		for ;  <  && [] != 0; ++ {
		}
		for ;  <  && [] == 0; ++ {
			++
		}

		 = brotli_max_uint32_t(, )
	}

	if  > 0 {
		 = log2FloorNonZero(uint())
	} else {
		 = 0
	}
	 = brotli_min_uint32_t(, *)
	* = 
	* = 0
	for  = 0;  < ; {
		assert(* <= )
		if [] != 0 {
			[*] = [] + *
			++
			(*)++
		} else {
			var  uint32 = 1
			var  uint
			for  =  + 1;  <  && [] == 0; ++ {
				++
			}

			 += uint()
			for  != 0 {
				if  < 2<< {
					var  uint32 = log2FloorNonZero(uint())
					var  uint32 =  - (1 << )
					[*] =  + ( << 9)
					(*)++
					break
				} else {
					var  uint32 = (1 << ) - 1
					[*] =  + ( << 9)
					 -= (2 << ) - 1
					(*)++
				}
			}
		}
	}
}

const symbolBits = 9

var encodeContextMap_kSymbolMask uint32 = (1 << symbolBits) - 1

func encodeContextMap( []uint32,  uint,  uint,  []huffmanTree,  *uint,  []byte) {
	var  uint
	var  []uint32
	var  uint32 = 6
	var  uint = 0
	var  [maxContextMapSymbols]uint32
	var  [maxContextMapSymbols]byte
	var  [maxContextMapSymbols]uint16

	storeVarLenUint8(-1, , )

	if  == 1 {
		return
	}

	 = make([]uint32, )
	moveToFrontTransform(, , )
	runLengthCodeZeros(, , &, &)
	 = [maxContextMapSymbols]uint32{}
	for  = 0;  < ; ++ {
		[[]&encodeContextMap_kSymbolMask]++
	}
	{
		var  bool = ( > 0)
		writeSingleBit(, , )
		if  {
			writeBits(4, uint64()-1, , )
		}
	}

	buildAndStoreHuffmanTree([:], uint(uint32()+), uint(uint32()+), , [:], [:], , )
	for  = 0;  < ; ++ {
		var  uint32 = [] & encodeContextMap_kSymbolMask
		var  uint32 = [] >> symbolBits
		writeBits(uint([]), uint64([]), , )
		if  > 0 &&  <=  {
			writeBits(uint(), uint64(), , )
		}
	}

	writeBits(1, 1, , ) /* use move-to-front */
	 = nil
}

/* Stores the block switch command with index block_ix to the bit stream. */
func storeBlockSwitch( *blockSplitCode,  uint32,  byte,  bool,  *uint,  []byte) {
	var  uint = nextBlockTypeCode(&.type_code_calculator, )
	var  uint
	var  uint32
	var  uint32
	if ! {
		writeBits(uint(.type_depths[]), uint64(.type_bits[]), , )
	}

	getBlockLengthPrefixCode(, &, &, &)

	writeBits(uint(.length_depths[]), uint64(.length_bits[]), , )
	writeBits(uint(), uint64(), , )
}

/* Builds a BlockSplitCode data structure from the block split given by the
   vector of block types and block lengths and stores it to the bit stream. */
func buildAndStoreBlockSplitCode( []byte,  []uint32,  uint,  uint,  []huffmanTree,  *blockSplitCode,  *uint,  []byte) {
	var  [maxBlockTypeSymbols]uint32
	var  [numBlockLenSymbols]uint32
	var  uint
	var  blockTypeCodeCalculator
	for  := 0;  < int(+2); ++ {
		[] = 0
	}
	 = [numBlockLenSymbols]uint32{}
	initBlockTypeCodeCalculator(&)
	for  = 0;  < ; ++ {
		var  uint = nextBlockTypeCode(&, [])
		if  != 0 {
			[]++
		}
		[blockLengthPrefixCode([])]++
	}

	storeVarLenUint8(-1, , )
	if  > 1 { /* TODO: else? could StoreBlockSwitch occur? */
		buildAndStoreHuffmanTree([0:], +2, +2, , .type_depths[0:], .type_bits[0:], , )
		buildAndStoreHuffmanTree([0:], numBlockLenSymbols, numBlockLenSymbols, , .length_depths[0:], .length_bits[0:], , )
		storeBlockSwitch(, [0], [0], true, , )
	}
}

/* Stores a context map where the histogram type is always the block type. */
func storeTrivialContextMap( uint,  uint,  []huffmanTree,  *uint,  []byte) {
	storeVarLenUint8(-1, , )
	if  > 1 {
		var  uint =  - 1
		var  uint = (1 << ) - 1
		var  uint =  + 
		var  [maxContextMapSymbols]uint32
		var  [maxContextMapSymbols]byte
		var  [maxContextMapSymbols]uint16
		var  uint
		for  := 0;  < int(); ++ {
			[] = 0
		}

		/* Write RLEMAX. */
		writeBits(1, 1, , )

		writeBits(4, uint64()-1, , )
		[] = uint32()
		[0] = 1
		for  = ;  < ; ++ {
			[] = 1
		}

		buildAndStoreHuffmanTree([:], , , , [:], [:], , )
		for  = 0;  < ; ++ {
			var  uint
			if  == 0 {
				 = 0
			} else {
				 =  +  - 1
			}
			var  uint = 
			writeBits(uint([]), uint64([]), , )
			writeBits(uint([]), uint64([]), , )
			writeBits(, uint64(), , )
		}

		/* Write IMTF (inverse-move-to-front) bit. */
		writeBits(1, 1, , )
	}
}

/* Manages the encoding of one block category (literal, command or distance). */
type blockEncoder struct {
	histogram_length_ uint
	num_block_types_  uint
	block_types_      []byte
	block_lengths_    []uint32
	num_blocks_       uint
	block_split_code_ blockSplitCode
	block_ix_         uint
	block_len_        uint
	entropy_ix_       uint
	depths_           []byte
	bits_             []uint16
}

var blockEncoderPool sync.Pool

func getBlockEncoder( uint,  uint,  []byte,  []uint32,  uint) *blockEncoder {
	,  := blockEncoderPool.Get().(*blockEncoder)

	if  != nil {
		.block_ix_ = 0
		.entropy_ix_ = 0
		.depths_ = .depths_[:0]
		.bits_ = .bits_[:0]
	} else {
		 = &blockEncoder{}
	}

	.histogram_length_ = 
	.num_block_types_ = 
	.block_types_ = 
	.block_lengths_ = 
	.num_blocks_ = 
	initBlockTypeCodeCalculator(&.block_split_code_.type_code_calculator)
	if  == 0 {
		.block_len_ = 0
	} else {
		.block_len_ = uint([0])
	}

	return 
}

func cleanupBlockEncoder( *blockEncoder) {
	blockEncoderPool.Put()
}

/* Creates entropy codes of block lengths and block types and stores them
   to the bit stream. */
func buildAndStoreBlockSwitchEntropyCodes( *blockEncoder,  []huffmanTree,  *uint,  []byte) {
	buildAndStoreBlockSplitCode(.block_types_, .block_lengths_, .num_blocks_, .num_block_types_, , &.block_split_code_, , )
}

/* Stores the next symbol with the entropy code of the current block type.
   Updates the block type and block length at block boundaries. */
func storeSymbol( *blockEncoder,  uint,  *uint,  []byte) {
	if .block_len_ == 0 {
		.block_ix_++
		var  uint = .block_ix_
		var  uint32 = .block_lengths_[]
		var  byte = .block_types_[]
		.block_len_ = uint()
		.entropy_ix_ = uint() * .histogram_length_
		storeBlockSwitch(&.block_split_code_, , , false, , )
	}

	.block_len_--
	{
		var  uint = .entropy_ix_ + 
		writeBits(uint(.depths_[]), uint64(.bits_[]), , )
	}
}

/* Stores the next symbol with the entropy code of the current block type and
   context value.
   Updates the block type and block length at block boundaries. */
func storeSymbolWithContext( *blockEncoder,  uint,  uint,  []uint32,  *uint,  []byte,  uint) {
	if .block_len_ == 0 {
		.block_ix_++
		var  uint = .block_ix_
		var  uint32 = .block_lengths_[]
		var  byte = .block_types_[]
		.block_len_ = uint()
		.entropy_ix_ = uint() << 
		storeBlockSwitch(&.block_split_code_, , , false, , )
	}

	.block_len_--
	{
		var  uint = uint([.entropy_ix_+])
		var  uint = *.histogram_length_ + 
		writeBits(uint(.depths_[]), uint64(.bits_[]), , )
	}
}

func buildAndStoreEntropyCodesLiteral( *blockEncoder,  []histogramLiteral,  uint,  uint,  []huffmanTree,  *uint,  []byte) {
	var  uint =  * .histogram_length_
	if cap(.depths_) < int() {
		.depths_ = make([]byte, )
	} else {
		.depths_ = .depths_[:]
	}
	if cap(.bits_) < int() {
		.bits_ = make([]uint16, )
	} else {
		.bits_ = .bits_[:]
	}
	{
		var  uint
		for  = 0;  < ; ++ {
			var  uint =  * .histogram_length_
			buildAndStoreHuffmanTree([].data_[0:], .histogram_length_, , , .depths_[:], .bits_[:], , )
		}
	}
}

func buildAndStoreEntropyCodesCommand( *blockEncoder,  []histogramCommand,  uint,  uint,  []huffmanTree,  *uint,  []byte) {
	var  uint =  * .histogram_length_
	if cap(.depths_) < int() {
		.depths_ = make([]byte, )
	} else {
		.depths_ = .depths_[:]
	}
	if cap(.bits_) < int() {
		.bits_ = make([]uint16, )
	} else {
		.bits_ = .bits_[:]
	}
	{
		var  uint
		for  = 0;  < ; ++ {
			var  uint =  * .histogram_length_
			buildAndStoreHuffmanTree([].data_[0:], .histogram_length_, , , .depths_[:], .bits_[:], , )
		}
	}
}

func buildAndStoreEntropyCodesDistance( *blockEncoder,  []histogramDistance,  uint,  uint,  []huffmanTree,  *uint,  []byte) {
	var  uint =  * .histogram_length_
	if cap(.depths_) < int() {
		.depths_ = make([]byte, )
	} else {
		.depths_ = .depths_[:]
	}
	if cap(.bits_) < int() {
		.bits_ = make([]uint16, )
	} else {
		.bits_ = .bits_[:]
	}
	{
		var  uint
		for  = 0;  < ; ++ {
			var  uint =  * .histogram_length_
			buildAndStoreHuffmanTree([].data_[0:], .histogram_length_, , , .depths_[:], .bits_[:], , )
		}
	}
}

func jumpToByteBoundary( *uint,  []byte) {
	* = (* + 7) &^ 7
	[*>>3] = 0
}

func storeMetaBlock( []byte,  uint,  uint,  uint,  byte,  byte,  bool,  *encoderParams,  int,  []command,  *metaBlockSplit,  *uint,  []byte) {
	var  uint = 
	var  uint
	var  uint32 = .dist.alphabet_size
	var  uint32 = 
	var  []huffmanTree
	var  contextLUT = getContextLUT()
	var  *distanceParams = &.dist
	if .large_window &&  > numHistogramDistanceSymbols {
		 = numHistogramDistanceSymbols
	}

	storeCompressedMetaBlockHeader(, , , )

	 = make([]huffmanTree, maxHuffmanTreeSize)
	 := getBlockEncoder(numLiteralSymbols, .literal_split.num_types, .literal_split.types, .literal_split.lengths, .literal_split.num_blocks)
	 := getBlockEncoder(numCommandSymbols, .command_split.num_types, .command_split.types, .command_split.lengths, .command_split.num_blocks)
	 := getBlockEncoder(uint(), .distance_split.num_types, .distance_split.types, .distance_split.lengths, .distance_split.num_blocks)

	buildAndStoreBlockSwitchEntropyCodes(, , , )
	buildAndStoreBlockSwitchEntropyCodes(, , , )
	buildAndStoreBlockSwitchEntropyCodes(, , , )

	writeBits(2, uint64(.distance_postfix_bits), , )
	writeBits(4, uint64(.num_direct_distance_codes)>>.distance_postfix_bits, , )
	for  = 0;  < .literal_split.num_types; ++ {
		writeBits(2, uint64(), , )
	}

	if .literal_context_map_size == 0 {
		storeTrivialContextMap(.literal_histograms_size, literalContextBits, , , )
	} else {
		encodeContextMap(.literal_context_map, .literal_context_map_size, .literal_histograms_size, , , )
	}

	if .distance_context_map_size == 0 {
		storeTrivialContextMap(.distance_histograms_size, distanceContextBits, , , )
	} else {
		encodeContextMap(.distance_context_map, .distance_context_map_size, .distance_histograms_size, , , )
	}

	buildAndStoreEntropyCodesLiteral(, .literal_histograms, .literal_histograms_size, numLiteralSymbols, , , )
	buildAndStoreEntropyCodesCommand(, .command_histograms, .command_histograms_size, numCommandSymbols, , , )
	buildAndStoreEntropyCodesDistance(, .distance_histograms, .distance_histograms_size, uint(), , , )
	 = nil

	for ,  := range  {
		var  uint = uint(.cmd_prefix_)
		storeSymbol(, , , )
		storeCommandExtra(&, , )
		if .literal_context_map_size == 0 {
			var  uint
			for  = uint(.insert_len_);  != 0; -- {
				storeSymbol(, uint([&]), , )
				++
			}
		} else {
			var  uint
			for  = uint(.insert_len_);  != 0; -- {
				var  uint = uint(getContext(, , ))
				var  byte = [&]
				storeSymbolWithContext(, uint(), , .literal_context_map, , , literalContextBits)
				 = 
				 = 
				++
			}
		}

		 += uint(commandCopyLen(&))
		if commandCopyLen(&) != 0 {
			 = [(-2)&]
			 = [(-1)&]
			if .cmd_prefix_ >= 128 {
				var  uint = uint(.dist_prefix_) & 0x3FF
				var  uint32 = uint32(.dist_prefix_) >> 10
				var  uint64 = uint64(.dist_extra_)
				if .distance_context_map_size == 0 {
					storeSymbol(, , , )
				} else {
					var  uint = uint(commandDistanceContext(&))
					storeSymbolWithContext(, , , .distance_context_map, , , distanceContextBits)
				}

				writeBits(uint(), , , )
			}
		}
	}

	cleanupBlockEncoder()
	cleanupBlockEncoder()
	cleanupBlockEncoder()
	if  {
		jumpToByteBoundary(, )
	}
}

func buildHistograms( []byte,  uint,  uint,  []command,  *histogramLiteral,  *histogramCommand,  *histogramDistance) {
	var  uint = 
	for ,  := range  {
		var  uint
		histogramAddCommand(, uint(.cmd_prefix_))
		for  = uint(.insert_len_);  != 0; -- {
			histogramAddLiteral(, uint([&]))
			++
		}

		 += uint(commandCopyLen(&))
		if commandCopyLen(&) != 0 && .cmd_prefix_ >= 128 {
			histogramAddDistance(, uint(.dist_prefix_)&0x3FF)
		}
	}
}

func storeDataWithHuffmanCodes( []byte,  uint,  uint,  []command,  []byte,  []uint16,  []byte,  []uint16,  []byte,  []uint16,  *uint,  []byte) {
	var  uint = 
	for ,  := range  {
		var  uint = uint(.cmd_prefix_)
		var  uint
		writeBits(uint([]), uint64([]), , )
		storeCommandExtra(&, , )
		for  = uint(.insert_len_);  != 0; -- {
			var  byte = [&]
			writeBits(uint([]), uint64([]), , )
			++
		}

		 += uint(commandCopyLen(&))
		if commandCopyLen(&) != 0 && .cmd_prefix_ >= 128 {
			var  uint = uint(.dist_prefix_) & 0x3FF
			var  uint32 = uint32(.dist_prefix_) >> 10
			var  uint32 = .dist_extra_
			writeBits(uint([]), uint64([]), , )
			writeBits(uint(), uint64(), , )
		}
	}
}

func storeMetaBlockTrivial( []byte,  uint,  uint,  uint,  bool,  *encoderParams,  []command,  *uint,  []byte) {
	var  histogramLiteral
	var  histogramCommand
	var  histogramDistance
	var  [numLiteralSymbols]byte
	var  [numLiteralSymbols]uint16
	var  [numCommandSymbols]byte
	var  [numCommandSymbols]uint16
	var  [maxSimpleDistanceAlphabetSize]byte
	var  [maxSimpleDistanceAlphabetSize]uint16
	var  []huffmanTree
	var  uint32 = .dist.alphabet_size

	storeCompressedMetaBlockHeader(, , , )

	histogramClearLiteral(&)
	histogramClearCommand(&)
	histogramClearDistance(&)

	buildHistograms(, , , , &, &, &)

	writeBits(13, 0, , )

	 = make([]huffmanTree, maxHuffmanTreeSize)
	buildAndStoreHuffmanTree(.data_[:], numLiteralSymbols, numLiteralSymbols, , [:], [:], , )
	buildAndStoreHuffmanTree(.data_[:], numCommandSymbols, numCommandSymbols, , [:], [:], , )
	buildAndStoreHuffmanTree(.data_[:], maxSimpleDistanceAlphabetSize, uint(), , [:], [:], , )
	 = nil
	storeDataWithHuffmanCodes(, , , , [:], [:], [:], [:], [:], [:], , )
	if  {
		jumpToByteBoundary(, )
	}
}

func storeMetaBlockFast( []byte,  uint,  uint,  uint,  bool,  *encoderParams,  []command,  *uint,  []byte) {
	var  uint32 = .dist.alphabet_size
	var  uint32 = log2FloorNonZero(uint(-1)) + 1

	storeCompressedMetaBlockHeader(, , , )

	writeBits(13, 0, , )

	if len() <= 128 {
		var  = [numLiteralSymbols]uint32{0}
		var  uint = 
		var  uint = 0
		var  [numLiteralSymbols]byte
		var  [numLiteralSymbols]uint16
		for ,  := range  {
			var  uint
			for  = uint(.insert_len_);  != 0; -- {
				[[&]]++
				++
			}

			 += uint(.insert_len_)
			 += uint(commandCopyLen(&))
		}

		buildAndStoreHuffmanTreeFast([:], , /* max_bits = */
			8, [:], [:], , )

		storeStaticCommandHuffmanTree(, )
		storeStaticDistanceHuffmanTree(, )
		storeDataWithHuffmanCodes(, , , , [:], [:], kStaticCommandCodeDepth[:], kStaticCommandCodeBits[:], kStaticDistanceCodeDepth[:], kStaticDistanceCodeBits[:], , )
	} else {
		var  histogramLiteral
		var  histogramCommand
		var  histogramDistance
		var  [numLiteralSymbols]byte
		var  [numLiteralSymbols]uint16
		var  [numCommandSymbols]byte
		var  [numCommandSymbols]uint16
		var  [maxSimpleDistanceAlphabetSize]byte
		var  [maxSimpleDistanceAlphabetSize]uint16
		histogramClearLiteral(&)
		histogramClearCommand(&)
		histogramClearDistance(&)
		buildHistograms(, , , , &, &, &)
		buildAndStoreHuffmanTreeFast(.data_[:], .total_count_, /* max_bits = */
			8, [:], [:], , )

		buildAndStoreHuffmanTreeFast(.data_[:], .total_count_, /* max_bits = */
			10, [:], [:], , )

		buildAndStoreHuffmanTreeFast(.data_[:], .total_count_, /* max_bits = */
			uint(), [:], [:], , )

		storeDataWithHuffmanCodes(, , , , [:], [:], [:], [:], [:], [:], , )
	}

	if  {
		jumpToByteBoundary(, )
	}
}

/* This is for storing uncompressed blocks (simple raw storage of
   bytes-as-bytes). */
func storeUncompressedMetaBlock( bool,  []byte,  uint,  uint,  uint,  *uint,  []byte) {
	var  uint =  & 
	storeUncompressedMetaBlockHeader(uint(), , )
	jumpToByteBoundary(, )

	if + > +1 {
		var  uint =  + 1 - 
		copy([*>>3:], [:][:])
		* +=  << 3
		 -= 
		 = 0
	}

	copy([*>>3:], [:][:])
	* += uint( << 3)

	/* We need to clear the next 4 bytes to continue to be
	   compatible with BrotliWriteBits. */
	writeBitsPrepareStorage(*, )

	/* Since the uncompressed block itself may not be the final block, add an
	   empty one after this. */
	if  {
		writeBits(1, 1, , ) /* islast */
		writeBits(1, 1, , ) /* isempty */
		jumpToByteBoundary(, )
	}
}