package brotli

import (
	
)

/* Copyright 2014 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Algorithms for distributing the literals and commands of a metablock between
   block types and contexts. */

type metaBlockSplit struct {
	literal_split             blockSplit
	command_split             blockSplit
	distance_split            blockSplit
	literal_context_map       []uint32
	literal_context_map_size  uint
	distance_context_map      []uint32
	distance_context_map_size uint
	literal_histograms        []histogramLiteral
	literal_histograms_size   uint
	command_histograms        []histogramCommand
	command_histograms_size   uint
	distance_histograms       []histogramDistance
	distance_histograms_size  uint
}

var metaBlockPool sync.Pool

func getMetaBlockSplit() *metaBlockSplit {
	,  := metaBlockPool.Get().(*metaBlockSplit)

	if  == nil {
		 = &metaBlockSplit{}
	} else {
		initBlockSplit(&.literal_split)
		initBlockSplit(&.command_split)
		initBlockSplit(&.distance_split)
		.literal_context_map = .literal_context_map[:0]
		.literal_context_map_size = 0
		.distance_context_map = .distance_context_map[:0]
		.distance_context_map_size = 0
		.literal_histograms = .literal_histograms[:0]
		.command_histograms = .command_histograms[:0]
		.distance_histograms = .distance_histograms[:0]
	}
	return 
}

func freeMetaBlockSplit( *metaBlockSplit) {
	metaBlockPool.Put()
}

func initDistanceParams( *encoderParams,  uint32,  uint32) {
	var  *distanceParams = &.dist
	var  uint32
	var  uint32

	.distance_postfix_bits = 
	.num_direct_distance_codes = 

	 = uint32(distanceAlphabetSize(uint(), uint(), maxDistanceBits))
	 =  + (1 << (maxDistanceBits +  + 2)) - (1 << ( + 2))

	if .large_window {
		var  = [maxNpostfix + 1]uint32{0, 4, 12, 28}
		var  uint32 = 1 << 
		 = uint32(distanceAlphabetSize(uint(), uint(), largeMaxDistanceBits))

		/* The maximum distance is set so that no distance symbol used can encode
		   a distance larger than BROTLI_MAX_ALLOWED_DISTANCE with all
		   its extra bits set. */
		if  < [] {
			 = maxAllowedDistance - ([] - )
		} else if  >= []+ {
			 = (3 << 29) - 4 + ( - [])
		} else {
			 = maxAllowedDistance
		}
	}

	.alphabet_size = 
	.max_distance = uint()
}

func recomputeDistancePrefixes( []command,  *distanceParams,  *distanceParams) {
	if .distance_postfix_bits == .distance_postfix_bits && .num_direct_distance_codes == .num_direct_distance_codes {
		return
	}

	for  := range  {
		var  *command = &[]
		if commandCopyLen() != 0 && .cmd_prefix_ >= 128 {
			prefixEncodeCopyDistance(uint(commandRestoreDistanceCode(, )), uint(.num_direct_distance_codes), uint(.distance_postfix_bits), &.dist_prefix_, &.dist_extra_)
		}
	}
}

func computeDistanceCost( []command,  *distanceParams,  *distanceParams,  *float64) bool {
	var  bool = false
	var  uint16
	var  uint32
	var  float64 = 0.0
	var  histogramDistance
	histogramClearDistance(&)

	if .distance_postfix_bits == .distance_postfix_bits && .num_direct_distance_codes == .num_direct_distance_codes {
		 = true
	}

	for  := range  {
		 := &[]
		if commandCopyLen() != 0 && .cmd_prefix_ >= 128 {
			if  {
				 = .dist_prefix_
			} else {
				var  uint32 = commandRestoreDistanceCode(, )
				if  > uint32(.max_distance) {
					return false
				}

				prefixEncodeCopyDistance(uint(), uint(.num_direct_distance_codes), uint(.distance_postfix_bits), &, &)
			}

			histogramAddDistance(&, uint()&0x3FF)
			 += float64( >> 10)
		}
	}

	* = populationCostDistance(&) + 
	return true
}

var buildMetaBlock_kMaxNumberOfHistograms uint = 256

func buildMetaBlock( []byte,  uint,  uint,  *encoderParams,  byte,  byte,  []command,  int,  *metaBlockSplit) {
	var  []histogramDistance
	var  []histogramLiteral
	var  []int = nil
	var  uint
	var  uint
	var  uint
	var  uint = 1
	var  uint32
	var  uint32 = 0
	var  bool = true
	var  float64 = 1e99
	var  encoderParams = *
	/* Histogram ids need to fit in one byte. */

	var  encoderParams = *

	for  = 0;  <= maxNpostfix; ++ {
		for ;  < 16; ++ {
			var  uint32 =  << 
			var  bool
			var  float64
			initDistanceParams(&, , )
			if  == .dist.distance_postfix_bits &&  == .dist.num_direct_distance_codes {
				 = false
			}

			 = !computeDistanceCost(, &.dist, &.dist, &)
			if  || ( > ) {
				break
			}

			 = 
			.dist = .dist
		}

		if  > 0 {
			--
		}
		 /= 2
	}

	if  {
		var  float64
		computeDistanceCost(, &.dist, &.dist, &)
		if  <  {
			/* NB: currently unused; uncomment when more param tuning is added. */
			/* best_dist_cost = dist_cost; */
			.dist = .dist
		}
	}

	recomputeDistancePrefixes(, &.dist, &.dist)

	splitBlock(, , , , , &.literal_split, &.command_split, &.distance_split)

	if !.disable_literal_context_modeling {
		 = 1 << literalContextBits
		 = make([]int, (.literal_split.num_types))
		for  = 0;  < .literal_split.num_types; ++ {
			[] = 
		}
	}

	 = .literal_split.num_types * 
	 = make([]histogramLiteral, )
	clearHistogramsLiteral(, )

	 = .distance_split.num_types << distanceContextBits
	 = make([]histogramDistance, )
	clearHistogramsDistance(, )

	.command_histograms_size = .command_split.num_types
	if cap(.command_histograms) < int(.command_histograms_size) {
		.command_histograms = make([]histogramCommand, (.command_histograms_size))
	} else {
		.command_histograms = .command_histograms[:.command_histograms_size]
	}
	clearHistogramsCommand(.command_histograms, .command_histograms_size)

	buildHistogramsWithContext(, &.literal_split, &.command_split, &.distance_split, , , , , , , , .command_histograms, )
	 = nil

	.literal_context_map_size = .literal_split.num_types << literalContextBits
	if cap(.literal_context_map) < int(.literal_context_map_size) {
		.literal_context_map = make([]uint32, (.literal_context_map_size))
	} else {
		.literal_context_map = .literal_context_map[:.literal_context_map_size]
	}

	.literal_histograms_size = .literal_context_map_size
	if cap(.literal_histograms) < int(.literal_histograms_size) {
		.literal_histograms = make([]histogramLiteral, (.literal_histograms_size))
	} else {
		.literal_histograms = .literal_histograms[:.literal_histograms_size]
	}

	clusterHistogramsLiteral(, , buildMetaBlock_kMaxNumberOfHistograms, .literal_histograms, &.literal_histograms_size, .literal_context_map)
	 = nil

	if .disable_literal_context_modeling {
		/* Distribute assignment to all contexts. */
		for  = .literal_split.num_types;  != 0; {
			var  uint = 0
			--
			for ;  < 1<<literalContextBits; ++ {
				.literal_context_map[(<<literalContextBits)+] = .literal_context_map[]
			}
		}
	}

	.distance_context_map_size = .distance_split.num_types << distanceContextBits
	if cap(.distance_context_map) < int(.distance_context_map_size) {
		.distance_context_map = make([]uint32, (.distance_context_map_size))
	} else {
		.distance_context_map = .distance_context_map[:.distance_context_map_size]
	}

	.distance_histograms_size = .distance_context_map_size
	if cap(.distance_histograms) < int(.distance_histograms_size) {
		.distance_histograms = make([]histogramDistance, (.distance_histograms_size))
	} else {
		.distance_histograms = .distance_histograms[:.distance_histograms_size]
	}

	clusterHistogramsDistance(, .distance_context_map_size, buildMetaBlock_kMaxNumberOfHistograms, .distance_histograms, &.distance_histograms_size, .distance_context_map)
	 = nil
}

const maxStaticContexts = 13

/* Greedy block splitter for one block category (literal, command or distance).
   Gathers histograms for all context buckets. */
type contextBlockSplitter struct {
	alphabet_size_     uint
	num_contexts_      uint
	max_block_types_   uint
	min_block_size_    uint
	split_threshold_   float64
	num_blocks_        uint
	split_             *blockSplit
	histograms_        []histogramLiteral
	histograms_size_   *uint
	target_block_size_ uint
	block_size_        uint
	curr_histogram_ix_ uint
	last_histogram_ix_ [2]uint
	last_entropy_      [2 * maxStaticContexts]float64
	merge_last_count_  uint
}

func initContextBlockSplitter( *contextBlockSplitter,  uint,  uint,  uint,  float64,  uint,  *blockSplit,  *[]histogramLiteral,  *uint) {
	var  uint = / + 1
	var  uint
	assert( <= maxStaticContexts)

	.alphabet_size_ = 
	.num_contexts_ = 
	.max_block_types_ = maxNumberOfBlockTypes / 
	.min_block_size_ = 
	.split_threshold_ = 
	.num_blocks_ = 0
	.split_ = 
	.histograms_size_ = 
	.target_block_size_ = 
	.block_size_ = 0
	.curr_histogram_ix_ = 0
	.merge_last_count_ = 0

	/* We have to allocate one more histogram than the maximum number of block
	   types for the current histogram when the meta-block is too big. */
	 = brotli_min_size_t(, .max_block_types_+1)

	brotli_ensure_capacity_uint8_t(&.types, &.types_alloc_size, )
	brotli_ensure_capacity_uint32_t(&.lengths, &.lengths_alloc_size, )
	.num_blocks = 
	* =  * 
	if  == nil || cap(*) < int(*) {
		* = make([]histogramLiteral, (*))
	} else {
		* = (*)[:*]
	}
	.histograms_ = *

	/* Clear only current histogram. */
	clearHistogramsLiteral(.histograms_[0:], )

	.last_histogram_ix_[1] = 0
	.last_histogram_ix_[0] = .last_histogram_ix_[1]
}

/* Does either of three things:
   (1) emits the current block with a new block type;
   (2) emits the current block with the type of the second last block;
   (3) merges the current block with the last block. */
func contextBlockSplitterFinishBlock( *contextBlockSplitter,  bool) {
	var  *blockSplit = .split_
	var  uint = .num_contexts_
	var  []float64 = .last_entropy_[:]
	var  []histogramLiteral = .histograms_

	if .block_size_ < .min_block_size_ {
		.block_size_ = .min_block_size_
	}

	if .num_blocks_ == 0 {
		var  uint

		/* Create first block. */
		.lengths[0] = uint32(.block_size_)

		.types[0] = 0

		for  = 0;  < ; ++ {
			[] = bitsEntropy([].data_[:], .alphabet_size_)
			[+] = []
		}

		.num_blocks_++
		.num_types++
		.curr_histogram_ix_ += 
		if .curr_histogram_ix_ < *.histograms_size_ {
			clearHistogramsLiteral(.histograms_[.curr_histogram_ix_:], .num_contexts_)
		}

		.block_size_ = 0
	} else if .block_size_ > 0 {
		var  [maxStaticContexts]float64
		var  []histogramLiteral = make([]histogramLiteral, (2 * ))
		var  [2 * maxStaticContexts]float64
		var  = [2]float64{0.0}
		/* Try merging the set of histograms for the current block type with the
		   respective set of histograms for the last and second last block types.
		   Decide over the split based on the total reduction of entropy across
		   all contexts. */

		var  uint
		for  = 0;  < ; ++ {
			var  uint = .curr_histogram_ix_ + 
			var  uint
			[] = bitsEntropy([].data_[:], .alphabet_size_)
			for  = 0;  < 2; ++ {
				var  uint = * + 
				var  uint = .last_histogram_ix_[] + 
				[] = []
				histogramAddHistogramLiteral(&[], &[])
				[] = bitsEntropy([].data_[0:], .alphabet_size_)
				[] += [] - [] - []
			}
		}

		if .num_types < .max_block_types_ && [0] > .split_threshold_ && [1] > .split_threshold_ {
			/* Create new block. */
			.lengths[.num_blocks_] = uint32(.block_size_)

			.types[.num_blocks_] = byte(.num_types)
			.last_histogram_ix_[1] = .last_histogram_ix_[0]
			.last_histogram_ix_[0] = .num_types * 
			for  = 0;  < ; ++ {
				[+] = []
				[] = []
			}

			.num_blocks_++
			.num_types++
			.curr_histogram_ix_ += 
			if .curr_histogram_ix_ < *.histograms_size_ {
				clearHistogramsLiteral(.histograms_[.curr_histogram_ix_:], .num_contexts_)
			}

			.block_size_ = 0
			.merge_last_count_ = 0
			.target_block_size_ = .min_block_size_
		} else if [1] < [0]-20.0 {
			.lengths[.num_blocks_] = uint32(.block_size_)
			.types[.num_blocks_] = .types[.num_blocks_-2]
			/* Combine this block with second last block. */

			var  uint = .last_histogram_ix_[0]
			.last_histogram_ix_[0] = .last_histogram_ix_[1]
			.last_histogram_ix_[1] = 
			for  = 0;  < ; ++ {
				[.last_histogram_ix_[0]+] = [+]
				[+] = []
				[] = [+]
				histogramClearLiteral(&[.curr_histogram_ix_+])
			}

			.num_blocks_++
			.block_size_ = 0
			.merge_last_count_ = 0
			.target_block_size_ = .min_block_size_
		} else {
			/* Combine this block with last block. */
			.lengths[.num_blocks_-1] += uint32(.block_size_)

			for  = 0;  < ; ++ {
				[.last_histogram_ix_[0]+] = []
				[] = []
				if .num_types == 1 {
					[+] = []
				}

				histogramClearLiteral(&[.curr_histogram_ix_+])
			}

			.block_size_ = 0
			.merge_last_count_++
			if .merge_last_count_ > 1 {
				.target_block_size_ += .min_block_size_
			}
		}

		 = nil
	}

	if  {
		*.histograms_size_ = .num_types * 
		.num_blocks = .num_blocks_
	}
}

/* Adds the next symbol to the current block type and context. When the
   current block reaches the target size, decides on merging the block. */
func contextBlockSplitterAddSymbol( *contextBlockSplitter,  uint,  uint) {
	histogramAddLiteral(&.histograms_[.curr_histogram_ix_+], )
	.block_size_++
	if .block_size_ == .target_block_size_ {
		contextBlockSplitterFinishBlock(, false) /* is_final = */
	}
}

func mapStaticContexts( uint,  []uint32,  *metaBlockSplit) {
	var  uint
	.literal_context_map_size = .literal_split.num_types << literalContextBits
	if cap(.literal_context_map) < int(.literal_context_map_size) {
		.literal_context_map = make([]uint32, (.literal_context_map_size))
	} else {
		.literal_context_map = .literal_context_map[:.literal_context_map_size]
	}

	for  = 0;  < .literal_split.num_types; ++ {
		var  uint32 = uint32( * )
		var  uint
		for  = 0;  < 1<<literalContextBits; ++ {
			.literal_context_map[(<<literalContextBits)+] =  + []
		}
	}
}

func buildMetaBlockGreedyInternal( []byte,  uint,  uint,  byte,  byte,  contextLUT,  uint,  []uint32,  []command,  *metaBlockSplit) {
	var  struct {
		 blockSplitterLiteral
		   contextBlockSplitter
	}
	var  blockSplitterCommand
	var  blockSplitterDistance
	var  uint = 0
	for  := range  {
		 += uint([].insert_len_)
	}

	if  == 1 {
		initBlockSplitterLiteral(&., 256, 512, 400.0, , &.literal_split, &.literal_histograms, &.literal_histograms_size)
	} else {
		initContextBlockSplitter(&., 256, , 512, 400.0, , &.literal_split, &.literal_histograms, &.literal_histograms_size)
	}

	initBlockSplitterCommand(&, numCommandSymbols, 1024, 500.0, uint(len()), &.command_split, &.command_histograms, &.command_histograms_size)
	initBlockSplitterDistance(&, 64, 512, 100.0, uint(len()), &.distance_split, &.distance_histograms, &.distance_histograms_size)

	for ,  := range  {
		var  uint
		blockSplitterAddSymbolCommand(&, uint(.cmd_prefix_))
		for  = uint(.insert_len_);  != 0; -- {
			var  byte = [&]
			if  == 1 {
				blockSplitterAddSymbolLiteral(&., uint())
			} else {
				var  uint = uint(getContext(, , ))
				contextBlockSplitterAddSymbol(&., uint(), uint([]))
			}

			 = 
			 = 
			++
		}

		 += uint(commandCopyLen(&))
		if commandCopyLen(&) != 0 {
			 = [(-2)&]
			 = [(-1)&]
			if .cmd_prefix_ >= 128 {
				blockSplitterAddSymbolDistance(&, uint(.dist_prefix_)&0x3FF)
			}
		}
	}

	if  == 1 {
		blockSplitterFinishBlockLiteral(&., true) /* is_final = */
	} else {
		contextBlockSplitterFinishBlock(&., true) /* is_final = */
	}

	blockSplitterFinishBlockCommand(&, true)   /* is_final = */
	blockSplitterFinishBlockDistance(&, true) /* is_final = */

	if  > 1 {
		mapStaticContexts(, , )
	}
}

func buildMetaBlockGreedy( []byte,  uint,  uint,  byte,  byte,  contextLUT,  uint,  []uint32,  []command,  *metaBlockSplit) {
	if  == 1 {
		buildMetaBlockGreedyInternal(, , , , , , 1, nil, , )
	} else {
		buildMetaBlockGreedyInternal(, , , , , , , , , )
	}
}

func optimizeHistograms( uint32,  *metaBlockSplit) {
	var  [numCommandSymbols]byte
	var  uint
	for  = 0;  < .literal_histograms_size; ++ {
		optimizeHuffmanCountsForRLE(256, .literal_histograms[].data_[:], [:])
	}

	for  = 0;  < .command_histograms_size; ++ {
		optimizeHuffmanCountsForRLE(numCommandSymbols, .command_histograms[].data_[:], [:])
	}

	for  = 0;  < .distance_histograms_size; ++ {
		optimizeHuffmanCountsForRLE(uint(), .distance_histograms[].data_[:], [:])
	}
}