// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package bytealg

import (
	
	
)

// Offsets into internal/cpu records for use in assembly.
const (
	offsetX86HasSSE42  = unsafe.Offsetof(cpu.X86.HasSSE42)
	offsetX86HasAVX2   = unsafe.Offsetof(cpu.X86.HasAVX2)
	offsetX86HasPOPCNT = unsafe.Offsetof(cpu.X86.HasPOPCNT)

	offsetS390xHasVX = unsafe.Offsetof(cpu.S390X.HasVX)

	offsetPPC64HasPOWER9 = unsafe.Offsetof(cpu.PPC64.IsPOWER9)
)

// MaxLen is the maximum length of the string to be searched for (argument b) in Index.
// If MaxLen is not 0, make sure MaxLen >= 4.
var MaxLen int

// FIXME: the logic of HashStrBytes, HashStrRevBytes, IndexRabinKarpBytes and HashStr, HashStrRev,
// IndexRabinKarp are exactly the same, except that the types are different. Can we eliminate
// three of them without causing allocation?

// PrimeRK is the prime base used in Rabin-Karp algorithm.
const PrimeRK = 16777619

// HashStrBytes returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func ( []byte) (uint32, uint32) {
	 := uint32(0)
	for  := 0;  < len(); ++ {
		 = *PrimeRK + uint32([])
	}
	var ,  uint32 = 1, PrimeRK
	for  := len();  > 0;  >>= 1 {
		if &1 != 0 {
			 *= 
		}
		 *= 
	}
	return , 
}

// HashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func ( string) (uint32, uint32) {
	 := uint32(0)
	for  := 0;  < len(); ++ {
		 = *PrimeRK + uint32([])
	}
	var ,  uint32 = 1, PrimeRK
	for  := len();  > 0;  >>= 1 {
		if &1 != 0 {
			 *= 
		}
		 *= 
	}
	return , 
}

// HashStrRevBytes returns the hash of the reverse of sep and the
// appropriate multiplicative factor for use in Rabin-Karp algorithm.
func ( []byte) (uint32, uint32) {
	 := uint32(0)
	for  := len() - 1;  >= 0; -- {
		 = *PrimeRK + uint32([])
	}
	var ,  uint32 = 1, PrimeRK
	for  := len();  > 0;  >>= 1 {
		if &1 != 0 {
			 *= 
		}
		 *= 
	}
	return , 
}

// HashStrRev returns the hash of the reverse of sep and the
// appropriate multiplicative factor for use in Rabin-Karp algorithm.
func ( string) (uint32, uint32) {
	 := uint32(0)
	for  := len() - 1;  >= 0; -- {
		 = *PrimeRK + uint32([])
	}
	var ,  uint32 = 1, PrimeRK
	for  := len();  > 0;  >>= 1 {
		if &1 != 0 {
			 *= 
		}
		 *= 
	}
	return , 
}

// IndexRabinKarpBytes uses the Rabin-Karp search algorithm to return the index of the
// first occurrence of substr in s, or -1 if not present.
func (,  []byte) int {
	// Rabin-Karp search
	,  := HashStrBytes()
	 := len()
	var  uint32
	for  := 0;  < ; ++ {
		 = *PrimeRK + uint32([])
	}
	if  ==  && Equal([:], ) {
		return 0
	}
	for  := ;  < len(); {
		 *= PrimeRK
		 += uint32([])
		 -=  * uint32([-])
		++
		if  ==  && Equal([-:], ) {
			return  - 
		}
	}
	return -1
}

// IndexRabinKarp uses the Rabin-Karp search algorithm to return the index of the
// first occurrence of substr in s, or -1 if not present.
func (,  string) int {
	// Rabin-Karp search
	,  := HashStr()
	 := len()
	var  uint32
	for  := 0;  < ; ++ {
		 = *PrimeRK + uint32([])
	}
	if  ==  && [:] ==  {
		return 0
	}
	for  := ;  < len(); {
		 *= PrimeRK
		 += uint32([])
		 -=  * uint32([-])
		++
		if  ==  && [-:] ==  {
			return  - 
		}
	}
	return -1
}

// MakeNoZero makes a slice of length and capacity n without zeroing the bytes.
// It is the caller's responsibility to ensure uninitialized bytes
// do not leak to the end user.
func ( int) []byte