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. 4 5 package bytes 6 7 //go:noescape 8 9 // indexShortStr returns the index of the first instance of c in s, or -1 if c is not present in s. 10 // indexShortStr requires 2 <= len(c) <= shortStringLen 11 func indexShortStr(s, c []byte) int // ../runtime/asm_$GOARCH.s 12 func supportAVX2() bool // ../runtime/asm_$GOARCH.s 13 14 var shortStringLen int 15 16 func init() { 17 if supportAVX2() { 18 shortStringLen = 63 19 } else { 20 shortStringLen = 31 21 } 22 } 23 24 // Index returns the index of the first instance of sep in s, or -1 if sep is not present in s. 25 func Index(s, sep []byte) int { 26 n := len(sep) 27 switch { 28 case n == 0: 29 return 0 30 case n == 1: 31 return IndexByte(s, sep[0]) 32 case n == len(s): 33 if Equal(sep, s) { 34 return 0 35 } 36 return -1 37 case n > len(s): 38 return -1 39 case n <= shortStringLen: 40 // Use brute force when s and sep both are small 41 if len(s) <= 64 { 42 return indexShortStr(s, sep) 43 } 44 c := sep[0] 45 i := 0 46 t := s[:len(s)-n+1] 47 fails := 0 48 for i < len(t) { 49 if t[i] != c { 50 // IndexByte skips 16/32 bytes per iteration, 51 // so it's faster than indexShortStr. 52 o := IndexByte(t[i:], c) 53 if o < 0 { 54 return -1 55 } 56 i += o 57 } 58 if Equal(s[i:i+n], sep) { 59 return i 60 } 61 fails++ 62 i++ 63 // Switch to indexShortStr when IndexByte produces too many false positives. 64 // Too many means more that 1 error per 8 characters. 65 // Allow some errors in the beginning. 66 if fails > (i+16)/8 { 67 r := indexShortStr(s[i:], sep) 68 if r >= 0 { 69 return r + i 70 } 71 return -1 72 } 73 } 74 return -1 75 } 76 // Rabin-Karp search 77 hashsep, pow := hashStr(sep) 78 var h uint32 79 for i := 0; i < n; i++ { 80 h = h*primeRK + uint32(s[i]) 81 } 82 if h == hashsep && Equal(s[:n], sep) { 83 return 0 84 } 85 for i := n; i < len(s); { 86 h *= primeRK 87 h += uint32(s[i]) 88 h -= pow * uint32(s[i-n]) 89 i++ 90 if h == hashsep && Equal(s[i-n:i], sep) { 91 return i - n 92 } 93 } 94 return -1 95 } 96 97 // primeRK is the prime base used in Rabin-Karp algorithm. 98 const primeRK = 16777619 99 100 // hashStr returns the hash and the appropriate multiplicative 101 // factor for use in Rabin-Karp algorithm. 102 func hashStr(sep []byte) (uint32, uint32) { 103 hash := uint32(0) 104 for i := 0; i < len(sep); i++ { 105 hash = hash*primeRK + uint32(sep[i]) 106 } 107 var pow, sq uint32 = 1, primeRK 108 for i := len(sep); i > 0; i >>= 1 { 109 if i&1 != 0 { 110 pow *= sq 111 } 112 sq *= sq 113 } 114 return hash, pow 115 } 116
