1// Copyright 2018 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bytealg
6
7import (
8	"internal/cpu"
9	"unsafe"
10)
11
12// Offsets into internal/cpu records for use in assembly.
13const (
14	offsetX86HasSSE42  = unsafe.Offsetof(cpu.X86.HasSSE42)
15	offsetX86HasAVX2   = unsafe.Offsetof(cpu.X86.HasAVX2)
16	offsetX86HasPOPCNT = unsafe.Offsetof(cpu.X86.HasPOPCNT)
17
18	offsetS390xHasVX = unsafe.Offsetof(cpu.S390X.HasVX)
19
20	offsetPPC64HasPOWER9 = unsafe.Offsetof(cpu.PPC64.IsPOWER9)
21)
22
23// MaxLen is the maximum length of the string to be searched for (argument b) in Index.
24// If MaxLen is not 0, make sure MaxLen >= 4.
25var MaxLen int
26
27// PrimeRK is the prime base used in Rabin-Karp algorithm.
28const PrimeRK = 16777619
29
30// HashStr returns the hash and the appropriate multiplicative
31// factor for use in Rabin-Karp algorithm.
32func HashStr[T string | []byte](sep T) (uint32, uint32) {
33	hash := uint32(0)
34	for i := 0; i < len(sep); i++ {
35		hash = hash*PrimeRK + uint32(sep[i])
36	}
37	var pow, sq uint32 = 1, PrimeRK
38	for i := len(sep); i > 0; i >>= 1 {
39		if i&1 != 0 {
40			pow *= sq
41		}
42		sq *= sq
43	}
44	return hash, pow
45}
46
47// HashStrRev returns the hash of the reverse of sep and the
48// appropriate multiplicative factor for use in Rabin-Karp algorithm.
49func HashStrRev[T string | []byte](sep T) (uint32, uint32) {
50	hash := uint32(0)
51	for i := len(sep) - 1; i >= 0; i-- {
52		hash = hash*PrimeRK + uint32(sep[i])
53	}
54	var pow, sq uint32 = 1, PrimeRK
55	for i := len(sep); i > 0; i >>= 1 {
56		if i&1 != 0 {
57			pow *= sq
58		}
59		sq *= sq
60	}
61	return hash, pow
62}
63
64// IndexRabinKarp uses the Rabin-Karp search algorithm to return the index of the
65// first occurrence of sep in s, or -1 if not present.
66func IndexRabinKarp[T string | []byte](s, sep T) int {
67	// Rabin-Karp search
68	hashss, pow := HashStr(sep)
69	n := len(sep)
70	var h uint32
71	for i := 0; i < n; i++ {
72		h = h*PrimeRK + uint32(s[i])
73	}
74	if h == hashss && string(s[:n]) == string(sep) {
75		return 0
76	}
77	for i := n; i < len(s); {
78		h *= PrimeRK
79		h += uint32(s[i])
80		h -= pow * uint32(s[i-n])
81		i++
82		if h == hashss && string(s[i-n:i]) == string(sep) {
83			return i - n
84		}
85	}
86	return -1
87}
88
89// LastIndexRabinKarp uses the Rabin-Karp search algorithm to return the last index of the
90// occurrence of sep in s, or -1 if not present.
91func LastIndexRabinKarp[T string | []byte](s, sep T) int {
92	// Rabin-Karp search from the end of the string
93	hashss, pow := HashStrRev(sep)
94	n := len(sep)
95	last := len(s) - n
96	var h uint32
97	for i := len(s) - 1; i >= last; i-- {
98		h = h*PrimeRK + uint32(s[i])
99	}
100	if h == hashss && string(s[last:]) == string(sep) {
101		return last
102	}
103	for i := last - 1; i >= 0; i-- {
104		h *= PrimeRK
105		h += uint32(s[i])
106		h -= pow * uint32(s[i+n])
107		if h == hashss && string(s[i:i+n]) == string(sep) {
108			return i
109		}
110	}
111	return -1
112}
113
114// MakeNoZero makes a slice of length n and capacity of at least n Bytes
115// without zeroing the bytes (including the bytes between len and cap).
116// It is the caller's responsibility to ensure uninitialized bytes
117// do not leak to the end user.
118func MakeNoZero(n int) []byte
119