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 initialEntropyCodesDistance( []uint16,  uint,  uint,  uint,  []histogramDistance) {
	var  uint32 = 7
	var  uint =  / 
	var  uint
	clearHistogramsDistance(, )
	for  = 0;  < ; ++ {
		var  uint =  *  / 
		if  != 0 {
			 += uint(myRand(&) % uint32())
		}

		if + >=  {
			 =  -  - 1
		}

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

func randomSampleDistance( *uint32,  []uint16,  uint,  uint,  *histogramDistance) {
	var  uint = 0
	if  >=  {
		 = 
	} else {
		 = uint(myRand() % uint32(-+1))
	}

	histogramAddVectorDistance(, [:], )
}

func refineEntropyCodesDistance( []uint16,  uint,  uint,  uint,  []histogramDistance) {
	var  uint = kIterMulForRefining*/ + kMinItersForRefining
	var  uint32 = 7
	var  uint
	 = (( +  - 1) / ) * 
	for  = 0;  < ; ++ {
		var  histogramDistance
		histogramClearDistance(&)
		randomSampleDistance(&, , , , &)
		histogramAddHistogramDistance(&[%], &)
	}
}

/* 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 findBlocksDistance( []uint16,  uint,  float64,  uint,  []histogramDistance,  []float64,  []float64,  []byte,  []byte) uint {
	var  uint = histogramDataSizeDistance()
	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 remapBlockIdsDistance_kInvalidId uint16 = 256

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

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

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

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

func buildBlockHistogramsDistance( []uint16,  uint,  []byte,  uint,  []histogramDistance) {
	var  uint
	clearHistogramsDistance(, )
	for  = 0;  < ; ++ {
		histogramAddDistance(&[[]], uint([]))
	}
}

var clusterBlocksDistance_kInvalidIndex uint32 = math.MaxUint32

func clusterBlocksDistance( []uint16,  uint,  uint,  []byte,  *blockSplit) {
	var  []uint32 = make([]uint32, )
	var  []uint32 = make([]uint32, )
	var  uint = clustersPerBatch * ( + histogramsPerBatch - 1) / histogramsPerBatch
	var  uint = 0
	var  uint = 
	var  []histogramDistance = make([]histogramDistance, )
	var  uint = 0
	var  uint = 
	var  []uint32 = make([]uint32, )
	var  uint = 0
	var  []histogramDistance = make([]histogramDistance, 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
			histogramClearDistance(&[])
			for  = 0; uint32() < [+]; ++ {
				histogramAddDistance(&[], uint([]))
				++
			}

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

		 = histogramCombineDistance(, [:], [:], [:], []histogramPair(), , , histogramsPerBatch, )
		if  < ( + ) {
			var  uint
			if  == 0 {
				 =  + 
			} else {
				 = 
			}
			var  []histogramDistance
			for  < ( + ) {
				 *= 2
			}
			 = make([]histogramDistance, )
			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()
	}

	 = histogramCombineDistance(, , , , , , , maxNumberOfBlockTypes, )
	 = nil
	 = nil

	 = make([]uint32, )
	for  = 0;  < ; ++ {
		[] = clusterBlocksDistance_kInvalidIndex
	}
	 = 0
	{
		var  uint32 = 0
		for  = 0;  < ; ++ {
			var  histogramDistance
			var  uint
			var  uint32
			var  float64
			histogramClearDistance(&)
			for  = 0; uint32() < []; ++ {
				histogramAddDistance(&, uint([]))
				++
			}

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

			[] = 
			if [] == clusterBlocksDistance_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 splitByteVectorDistance( []uint16,  uint,  uint,  uint,  uint,  float64,  *encoderParams,  *blockSplit) {
	var  uint = histogramDataSizeDistance()
	var  uint = / + 1
	var  []histogramDistance
	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([]histogramDistance, )

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

	refineEntropyCodesDistance(, , , , )
	{
		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;  < ; ++ {
			 = findBlocksDistance(, , , , , , , , )
			 = remapBlockIdsDistance(, , , )
			buildBlockHistogramsDistance(, , , , )
		}

		 = nil
		 = nil
		 = nil
		 = nil
		 = nil
		clusterBlocksDistance(, , , , )
		 = nil
	}
}