package matchfinder

import (
	
	
	
	
)

// Bargain3 is a MatchFinder that attempts to find the encoding with the lowest
// "bit cost", using 3 hash lengths (5, 8, and 12).
type Bargain3 struct {
	MaxDistance int

	// Skip is whether to look for matches at every other byte instead of every
	// byte (to increase speed but decrease compression).
	Skip bool

	history []byte
	table5  [1 << 17]tableEntry
	table8  [1 << 18]tableEntry
	table12 [1 << 19]tableEntry

	// holding onto buffers to reduce allocations:

	arrivals []arrival
	matches  []Match
}

func ( *Bargain3) () {
	.table5 = [len(.table5)]tableEntry{}
	.table8 = [len(.table8)]tableEntry{}
	.table12 = [len(.table12)]tableEntry{}
	.history = .history[:0]
}

func ( *Bargain3) ( []Match,  []byte) []Match {
	if .MaxDistance == 0 {
		.MaxDistance = 1 << 16
	}

	var  [256]uint32
	for ,  := range  {
		[]++
	}
	var  [256]float32
	for ,  := range  {
		 := max(math.Log2(float64(len())/float64()), 1)
		[] = float32()
	}

	// Each element in arrivals corresponds to the position just after
	// the corresponding byte in src.
	 := .arrivals
	if len() < len() {
		 = make([]arrival, len())
		.arrivals = 
	} else {
		 = [:len()]
		for  := range  {
			[] = arrival{}
		}
	}

	if len(.history) > .MaxDistance*2 {
		 := len(.history) - .MaxDistance
		copy(.history, .history[:])
		.history = .history[:.MaxDistance]

		for  := range .table5 {
			 := .table5[].offset
			 -= int32()
			if  < 0 {
				.table5[] = tableEntry{}
			} else {
				.table5[].offset = 
			}
		}
		for  := range .table8 {
			 := .table8[].offset
			 -= int32()
			if  < 0 {
				.table8[] = tableEntry{}
			} else {
				.table8[].offset = 
			}
		}
		for  := range .table12 {
			 := .table12[].offset
			 -= int32()
			if  < 0 {
				.table12[] = tableEntry{}
			} else {
				.table12[].offset = 
			}
		}
	}

	 := len(.history)
	.history = append(.history, ...)
	 = .history

	 := func( absoluteMatch,  int,  bool) {
		var  float32
		if .Start >  {
			 = [.Start--1].cost
		}
		 := float32(bits.Len(uint()))
		var  float32
		if ! {
			 = float32(bits.Len(uint(.Start - .Match)))
		}
		 :=  + baseMatchCost +  + 
		for  := .End;  >= .Start+3; -- {
			 := &[--1]
			if .cost > 0 && .cost <=  {
				break
			}
			* = arrival{
				length:   uint32( - .Start),
				distance: uint32(.Start - .Match),
				cost:     ,
			}
		}
	}

	var  int

	for  := ;  < len(); ++ {
		var  arrival
		if  >  {
			 = [--1]
		}

		 := 0
		if .distance == 0 {
			 = int(.length)
		}
		 := 0
		if  != 0 && - >  {
			 = int([--1-].distance)
		}

		 := [[]]
		 := &[-]
		if .cost == 0 || .cost+ < .cost {
			* = arrival{
				cost:   .cost + ,
				length: uint32( + 1),
			}
		}

		if  > len()-12 {
			// There's no room to check hashes.
			continue
		}

		 := binary.LittleEndian.Uint64([:])
		 := binary.LittleEndian.Uint32([+8:])
		 := .hash5()
		 := .hash8()
		 := .hash12(, )
		 := .table5[]
		 := .table8[]
		 := .table12[]

		 := tableEntry{offset: int32(), val: uint32()}
		.table5[] = 
		.table8[] = 
		.table12[] = 

		// Look for a repeat match, unless there is no previous distance, or a match at
		// that distance has already been found.
		if  != 0 &&  != int([--1+4].distance) {
			 :=  - 
			if  >= 0 && binary.LittleEndian.Uint32([:]) == uint32() {
				// We have a repeat of the previous match distance.
				 := extendMatch2(, , , )
				(, , true)
			}
		}

		if .Skip {
			if %2 != 0 {
				continue
			}
		}

		 := [--1+1].distance == 0

		if  > 0 ||  >=  ||  {
			if int(.offset) <  && -int(.offset) < .MaxDistance && uint32() == .val &&
				binary.LittleEndian.Uint32([.offset:]) == uint32() {
				 := extendMatch2(, , int(.offset), )
				 :=  - .Start
				if  == 0 {
					(, , false)
				} else {
					// The match was extended backwards. Add it with and without the extra.
					(, max(-, 0), false)
					.Start += 
					.Match += 
					(, , false)
				}
				 = max(, .Start+1, .End-6)
			}

			if int(.offset) <  && -int(.offset) < .MaxDistance && uint32() == .val &&
				binary.LittleEndian.Uint32([.offset:]) == uint32() {
				 := extendMatch2(, , int(.offset), )
				 :=  - .Start
				if  == 0 {
					(, , false)
				} else {
					// The match was extended backwards. Add it with and without the extra.
					(, max(-, 0), false)
					.Start += 
					.Match += 
					(, , false)
				}
				 = max(, .Start+1, .End-6)
			}

			if int(.offset) <  && -int(.offset) < .MaxDistance && uint32() == .val &&
				binary.LittleEndian.Uint32([.offset:]) == uint32() {
				 := extendMatch2(, , int(.offset), )
				 :=  - .Start
				if  == 0 {
					(, , false)
				} else {
					// The match was extended backwards. Add it with and without the extra.
					(, max(-, 0), false)
					.Start += 
					.Match += 
					(, , false)
				}
				 = max(, .Start+1, .End-6)
			}
		}
	}

	// We've found the shortest path; now walk it backward and store the matches.
	 := .matches[:0]
	 := len() - 1
	for  >= 0 {
		 := []
		if .distance > 0 {
			 = append(, Match{
				Length:   int(.length),
				Distance: int(.distance),
			})
			 -= int(.length)
		} else {
			if len() == 0 {
				 = append(, Match{})
			}
			[len()-1].Unmatched = int(.length)
			 -= int(.length)
		}
	}
	.matches = 

	slices.Reverse()

	return append(, ...)
}

func ( *Bargain3) ( uint64) uint32 {
	return uint32((( << 24) * 889523592379) >> (64 - 17))
}

func ( *Bargain3) ( uint64) uint32 {
	return uint32(( * 0xcf1bbcdcb7a56463) >> (64 - 18))
}

func ( *Bargain3) ( uint64,  uint32) uint32 {
	return uint32((*0xcf1bbcdcb7a56463 + uint64()*(2654435761<<32)) >> (64 - 19))
}