package brotli

import 

/* Copyright 2013 Google Inc. All Rights Reserved.

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

func initialEntropyCodesLiteral( []byte,  uint,  uint,  uint,  []histogramLiteral) {
	var  uint32 = 7
	var  uint =  / 
	var  uint
	clearHistogramsLiteral(, )
	for  = 0;  < ; ++ {
		var  uint =  *  / 
		if  != 0 {
			 += uint(myRand(&) % uint32())
		}

		if + >=  {
			 =  -  - 1
		}

		histogramAddVectorLiteral(&[], [:], )
	}
}

func randomSampleLiteral( *uint32,  []byte,  uint,  uint,  *histogramLiteral) {
	var  uint = 0
	if  >=  {
		 = 
	} else {
		 = uint(myRand() % uint32(-+1))
	}

	histogramAddVectorLiteral(, [:], )
}

func refineEntropyCodesLiteral( []byte,  uint,  uint,  uint,  []histogramLiteral) {
	var  uint = kIterMulForRefining*/ + kMinItersForRefining
	var  uint32 = 7
	var  uint
	 = (( +  - 1) / ) * 
	for  = 0;  < ; ++ {
		var  histogramLiteral
		histogramClearLiteral(&)
		randomSampleLiteral(&, , , , &)
		histogramAddHistogramLiteral(&[%], &)
	}
}

/* Assigns a block id from the range [0, num_histograms) to each data element
   in data[0..length) and fills in block_id[0..length) with the assigned values.
   Returns the number of blocks, i.e. one plus the number of block switches. */
func findBlocksLiteral( []byte,  uint,  float64,  uint,  []histogramLiteral,  []float64,  []float64,  []byte,  []byte) uint {
	var  uint = histogramDataSizeLiteral()
	var  uint = ( + 7) >> 3
	var  uint = 1
	var  uint
	var  uint
	assert( <= 256)
	if  <= 1 {
		for  = 0;  < ; ++ {
			[] = 0
		}

		return 1
	}

	for  := 0;  < int(*); ++ {
		[] = 0
	}
	for  = 0;  < ; ++ {
		[] = fastLog2(uint(uint32([].total_count_)))
	}

	for  = ;  != 0; {
		--
		for  = 0;  < ; ++ {
			[*+] = [] - bitCost(uint([].data_[]))
		}
	}

	for  := 0;  < int(); ++ {
		[] = 0
	}
	for  := 0;  < int(*); ++ {
		[] = 0
	}

	/* After each iteration of this loop, cost[k] will contain the difference
	   between the minimum cost of arriving at the current byte position using
	   entropy code k, and the minimum cost of arriving at the current byte
	   position. This difference is capped at the block switch cost, and if it
	   reaches block switch cost, it means that when we trace back from the last
	   position, we need to switch here. */
	for  = 0;  < ; ++ {
		var  uint = 
		var  uint =  * 
		var  uint = uint([]) * 
		var  float64 = 1e99
		var  float64 = 
		var  uint
		for  = 0;  < ; ++ {
			/* We are coding the symbol in data[byte_ix] with entropy code k. */
			[] += [+]

			if [] <  {
				 = []
				[] = byte()
			}
		}

		/* More blocks for the beginning. */
		if  < 2000 {
			 *= 0.77 + 0.07*float64()/2000
		}

		for  = 0;  < ; ++ {
			[] -= 
			if [] >=  {
				var  byte = byte(1 << ( & 7))
				[] = 
				assert(>>3 < )
				[+(>>3)] |= 
				/* Trace back from the last position and switch at the marked places. */
			}
		}
	}
	{
		var  uint =  - 1
		var  uint =  * 
		var  byte = []
		for  > 0 {
			var  byte = byte(1 << ( & 7))
			assert(uint()>>3 < )
			--
			 -= 
			if [+uint(>>3)]& != 0 {
				if  != [] {
					 = []
					++
				}
			}

			[] = 
		}
	}

	return 
}

var remapBlockIdsLiteral_kInvalidId uint16 = 256

func remapBlockIdsLiteral( []byte,  uint,  []uint16,  uint) uint {
	var  uint16 = 0
	var  uint
	for  = 0;  < ; ++ {
		[] = remapBlockIdsLiteral_kInvalidId
	}

	for  = 0;  < ; ++ {
		assert(uint([]) < )
		if [[]] == remapBlockIdsLiteral_kInvalidId {
			[[]] = 
			++
		}
	}

	for  = 0;  < ; ++ {
		[] = byte([[]])
		assert(uint([]) < )
	}

	assert(uint() <= )
	return uint()
}

func buildBlockHistogramsLiteral( []byte,  uint,  []byte,  uint,  []histogramLiteral) {
	var  uint
	clearHistogramsLiteral(, )
	for  = 0;  < ; ++ {
		histogramAddLiteral(&[[]], uint([]))
	}
}

var clusterBlocksLiteral_kInvalidIndex uint32 = math.MaxUint32

func clusterBlocksLiteral( []byte,  uint,  uint,  []byte,  *blockSplit) {
	var  []uint32 = make([]uint32, )
	var  []uint32 = make([]uint32, )
	var  uint = clustersPerBatch * ( + histogramsPerBatch - 1) / histogramsPerBatch
	var  uint = 0
	var  uint = 
	var  []histogramLiteral = make([]histogramLiteral, )
	var  uint = 0
	var  uint = 
	var  []uint32 = make([]uint32, )
	var  uint = 0
	var  []histogramLiteral = make([]histogramLiteral, brotli_min_size_t(, histogramsPerBatch))
	var  uint = histogramsPerBatch * histogramsPerBatch / 2
	var  uint =  + 1
	var  []histogramPair = make([]histogramPair, )
	var  uint = 0
	var  []uint32
	var  uint
	var  []uint32
	var  uint
	var  = [histogramsPerBatch]uint32{0}
	var  = [histogramsPerBatch]uint32{0}
	var  = [histogramsPerBatch]uint32{0}
	var  = [histogramsPerBatch]uint32{0}

	for  := 0;  < int(); ++ {
		[] = 0
	}
	{
		var  uint = 0
		for  = 0;  < ; ++ {
			assert( < )
			[]++
			if +1 ==  || [] != [+1] {
				++
			}
		}

		assert( == )
	}

	for  = 0;  < ;  += histogramsPerBatch {
		var  uint = brotli_min_size_t(-, histogramsPerBatch)
		var  uint
		var  uint
		for  = 0;  < ; ++ {
			var  uint
			histogramClearLiteral(&[])
			for  = 0; uint32() < [+]; ++ {
				histogramAddLiteral(&[], uint([]))
				++
			}

			[].bit_cost_ = populationCostLiteral(&[])
			[] = uint32()
			[] = uint32()
			[] = 1
		}

		 = histogramCombineLiteral(, [:], [:], [:], []histogramPair(), , , histogramsPerBatch, )
		if  < ( + ) {
			var  uint
			if  == 0 {
				 =  + 
			} else {
				 = 
			}
			var  []histogramLiteral
			for  < ( + ) {
				 *= 2
			}
			 = make([]histogramLiteral, )
			if  != 0 {
				copy(, [:])
			}

			 = 
			 = 
		}

		brotli_ensure_capacity_uint32_t(&, &, +)
		for  = 0;  < ; ++ {
			[] = [[]]
			++
			[] = [[]]
			++
			[[]] = uint32()
		}

		for  = 0;  < ; ++ {
			[+] = uint32() + [[]]
		}

		 += 
		assert( == )
		assert( == )
	}

	 = nil

	 = brotli_min_size_t(64*, (/2)*)
	if  < +1 {
		 = nil
		 = make([]histogramPair, ( + 1))
	}

	 = make([]uint32, )
	for  = 0;  < ; ++ {
		[] = uint32()
	}

	 = histogramCombineLiteral(, , , , , , , maxNumberOfBlockTypes, )
	 = nil
	 = nil

	 = make([]uint32, )
	for  = 0;  < ; ++ {
		[] = clusterBlocksLiteral_kInvalidIndex
	}
	 = 0
	{
		var  uint32 = 0
		for  = 0;  < ; ++ {
			var  histogramLiteral
			var  uint
			var  uint32
			var  float64
			histogramClearLiteral(&)
			for  = 0; uint32() < []; ++ {
				histogramAddLiteral(&, uint([]))
				++
			}

			if  == 0 {
				 = [0]
			} else {
				 = [-1]
			}
			 = histogramBitCostDistanceLiteral(&, &[])
			for  = 0;  < ; ++ {
				var  float64 = histogramBitCostDistanceLiteral(&, &[[]])
				if  <  {
					 = 
					 = []
				}
			}

			[] = 
			if [] == clusterBlocksLiteral_kInvalidIndex {
				[] = 
				++
			}
		}
	}

	 = nil
	 = nil
	brotli_ensure_capacity_uint8_t(&.types, &.types_alloc_size, )
	brotli_ensure_capacity_uint32_t(&.lengths, &.lengths_alloc_size, )
	{
		var  uint32 = 0
		var  uint = 0
		var  byte = 0
		for  = 0;  < ; ++ {
			 += []
			if +1 ==  || [] != [+1] {
				var  byte = byte([[]])
				.types[] = 
				.lengths[] = 
				 = brotli_max_uint8_t(, )
				 = 0
				++
			}
		}

		.num_blocks = 
		.num_types = uint() + 1
	}

	 = nil
	 = nil
	 = nil
}

func splitByteVectorLiteral( []byte,  uint,  uint,  uint,  uint,  float64,  *encoderParams,  *blockSplit) {
	var  uint = histogramDataSizeLiteral()
	var  uint = / + 1
	var  []histogramLiteral
	if  >  {
		 = 
	}

	if  == 0 {
		.num_types = 1
		return
	} else if  < kMinLengthForBlockSplitting {
		brotli_ensure_capacity_uint8_t(&.types, &.types_alloc_size, .num_blocks+1)
		brotli_ensure_capacity_uint32_t(&.lengths, &.lengths_alloc_size, .num_blocks+1)
		.num_types = 1
		.types[.num_blocks] = 0
		.lengths[.num_blocks] = uint32()
		.num_blocks++
		return
	}

	 = make([]histogramLiteral, )

	/* Find good entropy codes. */
	initialEntropyCodesLiteral(, , , , )

	refineEntropyCodesLiteral(, , , , )
	{
		var  []byte = make([]byte, )
		var  uint = 0
		var  uint = ( + 7) >> 3
		var  []float64 = make([]float64, ( * ))
		var  []float64 = make([]float64, )
		var  []byte = make([]byte, ( * ))
		var  []uint16 = make([]uint16, )
		var  uint
		if .quality < hqZopflificationQuality {
			 = 3
		} else {
			 = 10
		}
		/* Find a good path through literals with the good entropy codes. */

		var  uint
		for  = 0;  < ; ++ {
			 = findBlocksLiteral(, , , , , , , , )
			 = remapBlockIdsLiteral(, , , )
			buildBlockHistogramsLiteral(, , , , )
		}

		 = nil
		 = nil
		 = nil
		 = nil
		 = nil
		clusterBlocksLiteral(, , , , )
		 = nil
	}
}