1 // Copyright 2016 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.
11 // indexShortStr returns the index of the first instance of c in s, or -1 if c is not present in s.
12 // indexShortStr requires 2 <= len(c) <= shortStringLen
13 func indexShortStr(s
, c
[]byte) int // ../runtime/asm_$GOARCH.s
14 func supportAVX2() bool // ../runtime/asm_$GOARCH.s
16 var shortStringLen
int
26 // Index returns the index of the first instance of sep in s, or -1 if sep is not present in s.
27 func Index(s
, sep
[]byte) int {
33 return IndexByte(s
, sep
[0])
41 case n
<= shortStringLen
:
42 // Use brute force when s and sep both are small
44 return indexShortStr(s
, sep
)
52 // IndexByte skips 16/32 bytes per iteration,
53 // so it's faster than indexShortStr.
54 o
:= IndexByte(t
[i
:], c
)
60 if Equal(s
[i
:i
+n
], sep
) {
65 // Switch to indexShortStr when IndexByte produces too many false positives.
66 // Too many means more that 1 error per 8 characters.
67 // Allow some errors in the beginning.
69 r
:= indexShortStr(s
[i
:], sep
)
79 hashsep
, pow
:= hashStr(sep
)
81 for i
:= 0; i
< n
; i
++ {
82 h
= h
*primeRK
+ uint32(s
[i
])
84 if h
== hashsep
&& Equal(s
[:n
], sep
) {
87 for i
:= n
; i
< len(s
); {
90 h
-= pow
* uint32(s
[i
-n
])
92 if h
== hashsep
&& Equal(s
[i
-n
:i
], sep
) {
99 // primeRK is the prime base used in Rabin-Karp algorithm.
100 const primeRK
= 16777619
102 // hashStr returns the hash and the appropriate multiplicative
103 // factor for use in Rabin-Karp algorithm.
104 func hashStr(sep
[]byte) (uint32, uint32) {
106 for i
:= 0; i
< len(sep
); i
++ {
107 hash
= hash
*primeRK
+ uint32(sep
[i
])
109 var pow
, sq
uint32 = 1, primeRK
110 for i
:= len(sep
); i
> 0; i
>>= 1 {