package brotli

import 

type zopfliNode struct {
	length              uint32
	distance            uint32
	dcode_insert_length uint32
	u                   struct {
		cost     float32
		next     uint32
		shortcut uint32
	}
}

const maxEffectiveDistanceAlphabetSize = 544

const kInfinity float32 = 1.7e38 /* ~= 2 ^ 127 */

var kDistanceCacheIndex = []uint32{0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1}

var kDistanceCacheOffset = []int{0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3}

func initZopfliNodes( []zopfliNode,  uint) {
	var  zopfliNode
	var  uint
	.length = 1
	.distance = 0
	.dcode_insert_length = 0
	.u.cost = kInfinity
	for  = 0;  < ; ++ {
		[] = 
	}
}

func zopfliNodeCopyLength( *zopfliNode) uint32 {
	return .length & 0x1FFFFFF
}

func zopfliNodeLengthCode( *zopfliNode) uint32 {
	var  uint32 = .length >> 25
	return zopfliNodeCopyLength() + 9 - 
}

func zopfliNodeCopyDistance( *zopfliNode) uint32 {
	return .distance
}

func zopfliNodeDistanceCode( *zopfliNode) uint32 {
	var  uint32 = .dcode_insert_length >> 27
	if  == 0 {
		return zopfliNodeCopyDistance() + numDistanceShortCodes - 1
	} else {
		return  - 1
	}
}

func zopfliNodeCommandLength( *zopfliNode) uint32 {
	return zopfliNodeCopyLength() + (.dcode_insert_length & 0x7FFFFFF)
}

/* Histogram based cost model for zopflification. */
type zopfliCostModel struct {
	cost_cmd_               [numCommandSymbols]float32
	cost_dist_              []float32
	distance_histogram_size uint32
	literal_costs_          []float32
	min_cost_cmd_           float32
	num_bytes_              uint
}

func initZopfliCostModel( *zopfliCostModel,  *distanceParams,  uint) {
	var  uint32 = .alphabet_size
	if  > maxEffectiveDistanceAlphabetSize {
		 = maxEffectiveDistanceAlphabetSize
	}

	.num_bytes_ = 
	.literal_costs_ = make([]float32, ( + 2))
	.cost_dist_ = make([]float32, (.alphabet_size))
	.distance_histogram_size = 
}

func cleanupZopfliCostModel( *zopfliCostModel) {
	.literal_costs_ = nil
	.cost_dist_ = nil
}

func setCost( []uint32,  uint,  bool,  []float32) {
	var  uint = 0
	var  uint
	var  float32
	var  float32
	var  uint
	for  = 0;  < ; ++ {
		 += uint([])
	}

	 = float32(fastLog2())
	 = 
	if ! {
		for  = 0;  < ; ++ {
			if [] == 0 {
				++
			}
		}
	}

	 = float32(fastLog2()) + 2
	for  = 0;  < ; ++ {
		if [] == 0 {
			[] = 
			continue
		}

		/* Shannon bits for this symbol. */
		[] =  - float32(fastLog2(uint([])))

		/* Cannot be coded with less than 1 bit */
		if [] < 1 {
			[] = 1
		}
	}
}

func zopfliCostModelSetFromCommands( *zopfliCostModel,  uint,  []byte,  uint,  []command,  uint) {
	var  [numLiteralSymbols]uint32
	var  [numCommandSymbols]uint32
	var  [maxEffectiveDistanceAlphabetSize]uint32
	var  [numLiteralSymbols]float32
	var  uint =  - 
	var  float32 = kInfinity
	var  []float32 = .cost_cmd_[:]
	var  []float32

	 = [numLiteralSymbols]uint32{}
	 = [numCommandSymbols]uint32{}
	 = [maxEffectiveDistanceAlphabetSize]uint32{}

	for  := range  {
		var  uint = uint([].insert_len_)
		var  uint = uint(commandCopyLen(&[]))
		var  uint = uint([].dist_prefix_) & 0x3FF
		var  uint = uint([].cmd_prefix_)
		var  uint

		[]++
		if  >= 128 {
			[]++
		}

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

		 +=  + 
	}

	setCost([:], numLiteralSymbols, true, [:])
	setCost([:], numCommandSymbols, false, )
	setCost([:], uint(.distance_histogram_size), false, .cost_dist_)

	for  := 0;  < numCommandSymbols; ++ {
		 = brotli_min_float(, [])
	}

	.min_cost_cmd_ = 
	{
		 = .literal_costs_
		var  float32 = 0.0
		 := int(.num_bytes_)
		[0] = 0.0
		for  := 0;  < ; ++ {
			 += [[(+uint())&]]
			[+1] = [] + 
			 -= [+1] - []
		}
	}
}

func zopfliCostModelSetFromLiteralCosts( *zopfliCostModel,  uint,  []byte,  uint) {
	var  []float32 = .literal_costs_
	var  float32 = 0.0
	var  []float32 = .cost_dist_
	var  []float32 = .cost_cmd_[:]
	var  uint = .num_bytes_
	var  uint
	estimateBitCostsForLiterals(, , , , [1:])
	[0] = 0.0
	for  = 0;  < ; ++ {
		 += [+1]
		[+1] = [] + 
		 -= [+1] - []
	}

	for  = 0;  < numCommandSymbols; ++ {
		[] = float32(fastLog2(uint(11 + uint32())))
	}

	for  = 0; uint32() < .distance_histogram_size; ++ {
		[] = float32(fastLog2(uint(20 + uint32())))
	}

	.min_cost_cmd_ = float32(fastLog2(11))
}

func zopfliCostModelGetCommandCost( *zopfliCostModel,  uint16) float32 {
	return .cost_cmd_[]
}

func zopfliCostModelGetDistanceCost( *zopfliCostModel,  uint) float32 {
	return .cost_dist_[]
}

func zopfliCostModelGetLiteralCosts( *zopfliCostModel,  uint,  uint) float32 {
	return .literal_costs_[] - .literal_costs_[]
}

func zopfliCostModelGetMinCostCmd( *zopfliCostModel) float32 {
	return .min_cost_cmd_
}

/* REQUIRES: len >= 2, start_pos <= pos */
/* REQUIRES: cost < kInfinity, nodes[start_pos].cost < kInfinity */
/* Maintains the "ZopfliNode array invariant". */
func updateZopfliNode( []zopfliNode,  uint,  uint,  uint,  uint,  uint,  uint,  float32) {
	var  *zopfliNode = &[+]
	.length = uint32( | (+9-)<<25)
	.distance = uint32()
	.dcode_insert_length = uint32(<<27 | ( - ))
	.u.cost = 
}

type posData struct {
	pos            uint
	distance_cache [4]int
	costdiff       float32
	cost           float32
}

/* Maintains the smallest 8 cost difference together with their positions */
type startPosQueue struct {
	q_   [8]posData
	idx_ uint
}

func initStartPosQueue( *startPosQueue) {
	.idx_ = 0
}

func startPosQueueSize( *startPosQueue) uint {
	return brotli_min_size_t(.idx_, 8)
}

func startPosQueuePush( *startPosQueue,  *posData) {
	var  uint = ^(.idx_) & 7
	.idx_++
	var  uint = startPosQueueSize()
	var  uint
	var  []posData = .q_[:]
	[] = *

	/* Restore the sorted order. In the list of |len| items at most |len - 1|
	   adjacent element comparisons / swaps are required. */
	for  = 1;  < ; ++ {
		if [&7].costdiff > [(+1)&7].costdiff {
			var  posData = [&7]
			[&7] = [(+1)&7]
			[(+1)&7] = 
		}

		++
	}
}

func startPosQueueAt( *startPosQueue,  uint) *posData {
	return &.q_[(-.idx_)&7]
}

/* Returns the minimum possible copy length that can improve the cost of any */
/* future position. */
func computeMinimumCopyLength( float32,  []zopfliNode,  uint,  uint) uint {
	var  float32 = 
	var  uint = 2
	var  uint = 4
	/* Compute the minimum possible cost of reaching any future position. */

	var  uint = 10
	for + <=  && [+].u.cost <=  {
		/* We already reached (pos + len) with no more cost than the minimum
		   possible cost of reaching anything from this pos, so there is no point in
		   looking for lengths <= len. */
		++

		if  ==  {
			/* We reached the next copy length code bucket, so we add one more
			   extra bit to the minimum cost. */
			 += 1.0

			 += 
			 *= 2
		}
	}

	return uint()
}

/* REQUIRES: nodes[pos].cost < kInfinity
   REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */
func computeDistanceShortcut( uint,  uint,  uint,  uint,  []zopfliNode) uint32 {
	var  uint = uint(zopfliNodeCopyLength(&[]))
	var  uint = uint([].dcode_insert_length & 0x7FFFFFF)
	var  uint = uint(zopfliNodeCopyDistance(&[]))

	/* Since |block_start + pos| is the end position of the command, the copy part
	   starts from |block_start + pos - clen|. Distances that are greater than
	   this or greater than |max_backward_limit| + |gap| are static dictionary
	   references, and do not update the last distances.
	   Also distance code 0 (last distance) does not update the last distances. */
	if  == 0 {
		return 0
	} else if + <= ++ &&  <= + && zopfliNodeDistanceCode(&[]) > 0 {
		return uint32()
	} else {
		return [--].u.shortcut
	}
}

/* Fills in dist_cache[0..3] with the last four distances (as defined by
   Section 4. of the Spec) that would be used at (block_start + pos) if we
   used the shortest path of commands from block_start, computed from
   nodes[0..pos]. The last four distances at block_start are in
   starting_dist_cache[0..3].
   REQUIRES: nodes[pos].cost < kInfinity
   REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */
func computeDistanceCache( uint,  []int,  []zopfliNode,  []int) {
	var  int = 0
	var  uint = uint([].u.shortcut)
	for  < 4 &&  > 0 {
		var  uint = uint([].dcode_insert_length & 0x7FFFFFF)
		var  uint = uint(zopfliNodeCopyLength(&[]))
		var  uint = uint(zopfliNodeCopyDistance(&[]))
		[] = int()
		++

		/* Because of prerequisite, p >= clen + ilen >= 2. */
		 = uint([--].u.shortcut)
	}

	for ;  < 4; ++ {
		[] = [0]
		 = [1:]
	}
}

/* Maintains "ZopfliNode array invariant" and pushes node to the queue, if it
   is eligible. */
func evaluateNode( uint,  uint,  uint,  uint,  []int,  *zopfliCostModel,  *startPosQueue,  []zopfliNode) {
	/* Save cost, because ComputeDistanceCache invalidates it. */
	var  float32 = [].u.cost
	[].u.shortcut = computeDistanceShortcut(, , , , )
	if  <= zopfliCostModelGetLiteralCosts(, 0, ) {
		var  posData
		.pos = 
		.cost = 
		.costdiff =  - zopfliCostModelGetLiteralCosts(, 0, )
		computeDistanceCache(, , , .distance_cache[:])
		startPosQueuePush(, &)
	}
}

/* Returns longest copy length. */
func updateNodes( uint,  uint,  uint,  []byte,  uint,  *encoderParams,  uint,  []int,  uint,  []backwardMatch,  *zopfliCostModel,  *startPosQueue,  []zopfliNode) uint {
	var  uint =  + 
	var  uint =  & 
	var  uint = brotli_min_size_t(, )
	var  uint =  - 
	var  uint = maxZopfliLen()
	var  uint = maxZopfliCandidates()
	var  uint
	var  uint = 0
	var  uint
	var  uint = 0

	evaluateNode(, , , , , , , )
	{
		var  *posData = startPosQueueAt(, 0)
		var  float32 = (.cost + zopfliCostModelGetMinCostCmd() + zopfliCostModelGetLiteralCosts(, .pos, ))
		 = computeMinimumCopyLength(, , , )
	}

	/* Go over the command starting positions in order of increasing cost
	   difference. */
	for  = 0;  <  &&  < startPosQueueSize(); ++ {
		var  *posData = startPosQueueAt(, )
		var  uint = .pos
		var  uint16 = getInsertLengthCode( - )
		var  float32 = .costdiff
		var  float32 =  + float32(getInsertExtra()) + zopfliCostModelGetLiteralCosts(, 0, )
		var  uint =  - 1
		var  uint = 0
		/* Look for last distance matches using the distance cache from this
		   starting position. */
		for ;  < numDistanceShortCodes &&  < ; ++ {
			var  uint = uint(kDistanceCacheIndex[])
			var  uint = uint(.distance_cache[] + kDistanceCacheOffset[])
			var  uint =  - 
			var  uint = 0
			var  byte = [+]
			if + >  {
				break
			}

			if  > + {
				/* Word dictionary -> ignore. */
				continue
			}

			if  <=  {
				/* Regular backward reference. */
				if  >=  {
					continue
				}

				 &= 
				if + >  ||  != [+] {
					continue
				}

				 = findMatchLengthWithLimit([:], [:], )
			} else {
				continue
			}
			{
				var  float32 =  + zopfliCostModelGetDistanceCost(, )
				var  uint
				for  =  + 1;  <= ; ++ {
					var  uint16 = getCopyLengthCode()
					var  uint16 = combineLengthCodes(, ,  == 0)
					var  float32
					if  < 128 {
						 = 
					} else {
						 = 
					}
					var  float32 =  + float32(getCopyExtra()) + zopfliCostModelGetCommandCost(, )
					if  < [+].u.cost {
						updateZopfliNode(, , , , , , +1, )
						 = brotli_max_size_t(, )
					}

					 = 
				}
			}
		}

		/* At higher iterations look only for new last distance matches, since
		   looking only for new command start positions with the same distances
		   does not help much. */
		if  >= 2 {
			continue
		}
		{
			/* Loop through all possible copy lengths at this position. */
			var  uint = 
			for  = 0;  < ; ++ {
				var  backwardMatch = []
				var  uint = uint(.distance)
				var  bool = ( > +)
				var  uint =  + numDistanceShortCodes - 1
				var  uint16
				var  uint32
				var  uint32
				var  float32
				var  uint
				/* We already tried all possible last distance matches, so we can use
				   normal distance code here. */
				prefixEncodeCopyDistance(, uint(.dist.num_direct_distance_codes), uint(.dist.distance_postfix_bits), &, &)

				 = uint32() >> 10
				 =  + float32() + zopfliCostModelGetDistanceCost(, uint()&0x3FF)

				/* Try all copy lengths up until the maximum copy length corresponding
				   to this distance. If the distance refers to the static dictionary, or
				   the maximum length is long enough, try only one maximum length. */
				 = backwardMatchLength(&)

				if  <  && ( ||  > ) {
					 = 
				}

				for ;  <= ; ++ {
					var  uint
					if  {
						 = backwardMatchLengthCode(&)
					} else {
						 = 
					}
					var  uint16 = getCopyLengthCode()
					var  uint16 = combineLengthCodes(, , false)
					var  float32 =  + float32(getCopyExtra()) + zopfliCostModelGetCommandCost(, )
					if  < [+].u.cost {
						updateZopfliNode(, , , uint(), , , 0, )
						if  >  {
							 = 
						}
					}
				}
			}
		}
	}

	return 
}

func computeShortestPathFromNodes( uint,  []zopfliNode) uint {
	var  uint = 
	var  uint = 0
	for [].dcode_insert_length&0x7FFFFFF == 0 && [].length == 1 {
		--
	}
	[].u.next = math.MaxUint32
	for  != 0 {
		var  uint = uint(zopfliNodeCommandLength(&[]))
		 -= uint()
		[].u.next = uint32()
		++
	}

	return 
}

/* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */
func zopfliCreateCommands( uint,  uint,  []zopfliNode,  []int,  *uint,  *encoderParams,  *[]command,  *uint) {
	var  uint = maxBackwardLimit(.lgwin)
	var  uint = 0
	var  uint32 = [0].u.next
	var  uint
	var  uint = 0
	for  = 0;  != math.MaxUint32; ++ {
		var  *zopfliNode = &[uint32()+]
		var  uint = uint(zopfliNodeCopyLength())
		var  uint = uint(.dcode_insert_length & 0x7FFFFFF)
		 += 
		 = .u.next
		if  == 0 {
			 += *
			* = 0
		}
		{
			var  uint = uint(zopfliNodeCopyDistance())
			var  uint = uint(zopfliNodeLengthCode())
			var  uint = brotli_min_size_t(+, )
			var  bool = ( > +)
			var  uint = uint(zopfliNodeDistanceCode())
			* = append(*, makeCommand(&.dist, , , int()-int(), ))

			if ! &&  > 0 {
				[3] = [2]
				[2] = [1]
				[1] = [0]
				[0] = int()
			}
		}

		* += 
		 += 
	}

	* +=  - 
}

func zopfliIterate( uint,  uint,  []byte,  uint,  *encoderParams,  uint,  []int,  *zopfliCostModel,  []uint32,  []backwardMatch,  []zopfliNode) uint {
	var  uint = maxBackwardLimit(.lgwin)
	var  uint = maxZopfliLen()
	var  startPosQueue
	var  uint = 0
	var  uint
	[0].length = 0
	[0].u.cost = 0
	initStartPosQueue(&)
	for  = 0; +3 < ; ++ {
		var  uint = updateNodes(, , , , , , , , uint([]), [:], , &, )
		if  < longCopyQuickStep {
			 = 0
		}
		 += uint([])
		if [] == 1 && backwardMatchLength(&[-1]) >  {
			 = brotli_max_size_t(backwardMatchLength(&[-1]), )
		}

		if  > 1 {
			--
			for  != 0 {
				++
				if +3 >=  {
					break
				}
				evaluateNode(, , , , , , &, )
				 += uint([])
				--
			}
		}
	}

	return computeShortestPathFromNodes(, )
}

/* Computes the shortest path of commands from position to at most
   position + num_bytes.

   On return, path->size() is the number of commands found and path[i] is the
   length of the i-th command (copy length plus insert length).
   Note that the sum of the lengths of all commands can be less than num_bytes.

   On return, the nodes[0..num_bytes] array will have the following
   "ZopfliNode array invariant":
   For each i in [1..num_bytes], if nodes[i].cost < kInfinity, then
     (1) nodes[i].copy_length() >= 2
     (2) nodes[i].command_length() <= i and
     (3) nodes[i - nodes[i].command_length()].cost < kInfinity

 REQUIRES: nodes != nil and len(nodes) >= num_bytes + 1 */
func zopfliComputeShortestPath( uint,  uint,  []byte,  uint,  *encoderParams,  []int,  *h10,  []zopfliNode) uint {
	var  uint = maxBackwardLimit(.lgwin)
	var  uint = maxZopfliLen()
	var  zopfliCostModel
	var  startPosQueue
	var  [2 * (maxNumMatchesH10 + 64)]backwardMatch
	var  uint
	if  >= .StoreLookahead() {
		 =  +  - .StoreLookahead() + 1
	} else {
		 = 
	}
	var  uint
	var  uint = 0
	var  uint = 0
	[0].length = 0
	[0].u.cost = 0
	initZopfliCostModel(&, &.dist, )
	zopfliCostModelSetFromLiteralCosts(&, , , )
	initStartPosQueue(&)
	for  = 0; +.HashTypeLength()-1 < ; ++ {
		var  uint =  + 
		var  uint = brotli_min_size_t(, )
		var  uint
		var  uint
		 = findAllMatchesH10(, &.dictionary, , , , -, , , , [:])
		if  > 0 && backwardMatchLength(&[-1]) >  {
			[0] = [-1]
			 = 1
		}

		 = updateNodes(, , , , , , , , , [:], &, &, )
		if  < longCopyQuickStep {
			 = 0
		}
		if  == 1 && backwardMatchLength(&[0]) >  {
			 = brotli_max_size_t(backwardMatchLength(&[0]), )
		}

		if  > 1 {
			/* Add the tail of the copy to the hasher. */
			.StoreRange(, , +1, brotli_min_size_t(+, ))

			--
			for  != 0 {
				++
				if +.HashTypeLength()-1 >=  {
					break
				}
				evaluateNode(, , , , , &, &, )
				--
			}
		}
	}

	cleanupZopfliCostModel(&)
	return computeShortestPathFromNodes(, )
}

func createZopfliBackwardReferences( uint,  uint,  []byte,  uint,  *encoderParams,  *h10,  []int,  *uint,  *[]command,  *uint) {
	var  []zopfliNode
	 = make([]zopfliNode, ( + 1))
	initZopfliNodes(, +1)
	zopfliComputeShortestPath(, , , , , , , )
	zopfliCreateCommands(, , , , , , , )
	 = nil
}

func createHqZopfliBackwardReferences( uint,  uint,  []byte,  uint,  *encoderParams,  hasherHandle,  []int,  *uint,  *[]command,  *uint) {
	var  uint = maxBackwardLimit(.lgwin)
	var  []uint32 = make([]uint32, )
	var  uint = 4 * 
	var  uint
	if  >= .StoreLookahead() {
		 =  +  - .StoreLookahead() + 1
	} else {
		 = 
	}
	var  uint = 0
	var  uint
	var  uint
	var  uint
	var  [4]int
	var  int
	var  zopfliCostModel
	var  []zopfliNode
	var  []backwardMatch = make([]backwardMatch, )
	var  uint = 0
	var  uint = 0
	var  []backwardMatch
	for  = 0; +.HashTypeLength()-1 < ; ++ {
		var  uint =  + 
		var  uint = brotli_min_size_t(, )
		var  uint =  - 
		var  uint
		var  uint
		var  uint

		/* Ensure that we have enough free slots. */
		if  < +maxNumMatchesH10+ {
			var  uint = 
			if  == 0 {
				 =  + maxNumMatchesH10 + 
			}

			for  < +maxNumMatchesH10+ {
				 *= 2
			}

			 = make([]backwardMatch, )
			if  != 0 {
				copy(, [:])
			}

			 = 
			 = 
		}

		 = findAllMatchesH10(.(*h10), &.dictionary, , , , , , , , [+:])
		 =  + 
		for  = ; +1 < ; ++ {
			assert(backwardMatchLength(&[]) <= backwardMatchLength(&[+1]))
		}

		[] = uint32()
		if  > 0 {
			var  uint = backwardMatchLength(&[-1])
			if  > maxZopfliLenQuality11 {
				var  uint =  - 1
				[] = [-1]
				++
				[] = 1

				/* Add the tail of the copy to the hasher. */
				.StoreRange(, , +1, brotli_min_size_t(+, ))
				var  uint = 
				for  := 0;  < int(); ++ {
					[+1:][] = 0
				}
				 += 
			} else {
				 = 
			}
		}
	}

	 = *
	 = *
	copy([:], [:4])
	 = len(*)
	 = make([]zopfliNode, ( + 1))
	initZopfliCostModel(&, &.dist, )
	for  = 0;  < 2; ++ {
		initZopfliNodes(, +1)
		if  == 0 {
			zopfliCostModelSetFromLiteralCosts(&, , , )
		} else {
			zopfliCostModelSetFromCommands(&, , , , (*)[:], )
		}

		* = (*)[:]
		* = 
		* = 
		copy(, [:4])
		zopfliIterate(, , , , , , , &, , , )
		zopfliCreateCommands(, , , , , , , )
	}

	cleanupZopfliCostModel(&)
	 = nil
	 = nil
	 = nil
}