package brotli

import 

/* Copyright 2016 Google Inc. All Rights Reserved.

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

func (*hashForgetfulChain) () uint {
	return 4
}

func (*hashForgetfulChain) () uint {
	return 4
}

/* HashBytes is the function that chooses the bucket to place the address in.*/
func ( *hashForgetfulChain) ( []byte) uint {
	var  uint32 = binary.LittleEndian.Uint32() * kHashMul32

	/* The higher bits contain more mixture from the multiplication,
	   so we take our results from there. */
	return uint( >> (32 - .bucketBits))
}

type slot struct {
	delta uint16
	next  uint16
}

/* A (forgetful) hash table to the data seen by the compressor, to
   help create backward references to previous data.

   Hashes are stored in chains which are bucketed to groups. Group of chains
   share a storage "bank". When more than "bank size" chain nodes are added,
   oldest nodes are replaced; this way several chains may share a tail. */
type hashForgetfulChain struct {
	hasherCommon

	bucketBits              uint
	numBanks                uint
	bankBits                uint
	numLastDistancesToCheck int

	addr          []uint32
	head          []uint16
	tiny_hash     [65536]byte
	banks         [][]slot
	free_slot_idx []uint16
	max_hops      uint
}

func ( *hashForgetfulChain) ( *encoderParams) {
	var  uint
	if .quality > 6 {
		 = 7
	} else {
		 = 8
	}
	.max_hops =  << uint(.quality-4)

	 := 1 << .bankBits
	 := 1 << .bucketBits

	.addr = make([]uint32, )
	.head = make([]uint16, )
	.banks = make([][]slot, .numBanks)
	for  := range .banks {
		.banks[] = make([]slot, )
	}
	.free_slot_idx = make([]uint16, .numBanks)
}

func ( *hashForgetfulChain) ( bool,  uint,  []byte) {
	var  uint = (1 << .bucketBits) >> 6
	/* Partial preparation is 100 times slower (per socket). */
	if  &&  <=  {
		var  uint
		for  = 0;  < ; ++ {
			var  uint = .HashBytes([:])

			/* See InitEmpty comment. */
			.addr[] = 0xCCCCCCCC

			.head[] = 0xCCCC
		}
	} else {
		/* Fill |addr| array with 0xCCCCCCCC value. Because of wrapping, position
		   processed by hasher never reaches 3GB + 64M; this makes all new chains
		   to be terminated after the first node. */
		for  := range .addr {
			.addr[] = 0xCCCCCCCC
		}

		for  := range .head {
			.head[] = 0
		}
	}

	.tiny_hash = [65536]byte{}
	for  := range .free_slot_idx {
		.free_slot_idx[] = 0
	}
}

/* Look at 4 bytes at &data[ix & mask]. Compute a hash from these, and prepend
   node to corresponding chain; also update tiny_hash for current position. */
func ( *hashForgetfulChain) ( []byte,  uint,  uint) {
	var  uint = .HashBytes([&:])
	var  uint =  & (.numBanks - 1)
	 := uint(.free_slot_idx[]) & ((1 << .bankBits) - 1)
	.free_slot_idx[]++
	var  uint =  - uint(.addr[])
	.tiny_hash[uint16()] = byte()
	if  > 0xFFFF {
		 = 0xFFFF
	}
	.banks[][].delta = uint16()
	.banks[][].next = .head[]
	.addr[] = uint32()
	.head[] = uint16()
}

func ( *hashForgetfulChain) ( []byte,  uint,  uint,  uint) {
	var  uint
	for  = ;  < ; ++ {
		.Store(, , )
	}
}

func ( *hashForgetfulChain) ( uint,  uint,  []byte,  uint) {
	if  >= .HashTypeLength()-1 &&  >= 3 {
		/* Prepare the hashes for three last bytes of the last write.
		   These could not be calculated before, since they require knowledge
		   of both the previous and the current block. */
		.Store(, , -3)
		.Store(, , -2)
		.Store(, , -1)
	}
}

func ( *hashForgetfulChain) ( []int) {
	prepareDistanceCache(, .numLastDistancesToCheck)
}

/* Find a longest backward match of &data[cur_ix] up to the length of
   max_length and stores the position cur_ix in the hash table.

   REQUIRES: PrepareDistanceCachehashForgetfulChain must be invoked for current distance cache
             values; if this method is invoked repeatedly with the same distance
             cache values, it is enough to invoke PrepareDistanceCachehashForgetfulChain once.

   Does not look for matches longer than max_length.
   Does not look for matches further away than max_backward.
   Writes the best match into |out|.
   |out|->score is updated only if a better match is found. */
func ( *hashForgetfulChain) ( *encoderDictionary,  []byte,  uint,  []int,  uint,  uint,  uint,  uint,  uint,  *hasherSearchResult) {
	var  uint =  & 
	var  uint = .score
	var  uint = .score
	var  uint = .len
	var  uint = .HashBytes([:])
	var  byte = byte()
	/* Don't accept a short copy from far away. */
	.len = 0

	.len_code_delta = 0

	/* Try last distance first. */
	for  := 0;  < .numLastDistancesToCheck; ++ {
		var  uint = uint([])
		var  uint = ( - )

		/* For distance code 0 we want to consider 2-byte matches. */
		if  > 0 && .tiny_hash[uint16()] !=  {
			continue
		}
		if  >=  ||  >  {
			continue
		}

		 &= 
		{
			var  uint = findMatchLengthWithLimit([:], [:], )
			if  >= 2 {
				var  uint = backwardReferenceScoreUsingLastDistance(uint())
				if  <  {
					if  != 0 {
						 -= backwardReferencePenaltyUsingLastDistance(uint())
					}
					if  <  {
						 = 
						 = uint()
						.len = 
						.distance = 
						.score = 
					}
				}
			}
		}
	}
	{
		var  uint =  & (.numBanks - 1)
		var  uint = 0
		var  uint = .max_hops
		var  uint =  - uint(.addr[])
		var  uint = uint(.head[])
		for {
			 := 
			--
			if  == 0 {
				break
			}
			var  uint
			var  uint = 
			 += 
			if  >  {
				break
			}
			 = ( - ) & 
			 = uint(.banks[][].next)
			 = uint(.banks[][].delta)
			if + >  || + >  || [+] != [+] {
				continue
			}
			{
				var  uint = findMatchLengthWithLimit([:], [:], )
				if  >= 4 {
					/* Comparing for >= 3 does not change the semantics, but just saves
					   for a few unnecessary binary logarithms in backward reference
					   score, since we are not interested in such short matches. */
					var  uint = backwardReferenceScore(uint(), )
					if  <  {
						 = 
						 = uint()
						.len = 
						.distance = 
						.score = 
					}
				}
			}
		}

		.Store(, , )
	}

	if .score ==  {
		searchInStaticDictionary(, , [:], , +, , , false)
	}
}