libgo/go/strings/strings_amd64.go

   1 // Copyright 2015 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 // +build ignore
   6
   7 package strings
   8
   9 //go:noescape
  10
  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 string) int // ../runtime/asm_$GOARCH.s
  14 func supportAVX2() bool             // ../runtime/asm_$GOARCH.s
  15
  16 var shortStringLen int
  17
  18 func init() {
  19         if supportAVX2() {
  20                 shortStringLen = 63
  21         } else {
  22                 shortStringLen = 31
  23         }
  24 }
  25
  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 string) int {
  28         n := len(sep)
  29         switch {
  30         case n == 0:
  31                 return 0
  32         case n == 1:
  33                 return IndexByte(s, sep[0])
  34         case n == len(s):
  35                 if sep == s {
  36                         return 0
  37                 }
  38                 return -1
  39         case n > len(s):
  40                 return -1
  41         case n <= shortStringLen:
  42                 // Use brute force when s and sep both are small
  43                 if len(s) <= 64 {
  44                         return indexShortStr(s, sep)
  45                 }
  46                 c := sep[0]
  47                 i := 0
  48                 t := s[:len(s)-n+1]
  49                 fails := 0
  50                 for i < len(t) {
  51                         if t[i] != c {
  52                                 // IndexByte skips 16/32 bytes per iteration,
  53                                 // so it's faster than indexShortStr.
  54                                 o := IndexByte(t[i:], c)
  55                                 if o < 0 {
  56                                         return -1
  57                                 }
  58                                 i += o
  59                         }
  60                         if s[i:i+n] == sep {
  61                                 return i
  62                         }
  63                         fails++
  64                         i++
  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.
  68                         if fails > (i+16)/8 {
  69                                 r := indexShortStr(s[i:], sep)
  70                                 if r >= 0 {
  71                                         return r + i
  72                                 }
  73                                 return -1
  74                         }
  75                 }
  76                 return -1
  77         }
  78         // Rabin-Karp search
  79         hashsep, pow := hashStr(sep)
  80         var h uint32
  81         for i := 0; i < n; i++ {
  82                 h = h*primeRK + uint32(s[i])
  83         }
  84         if h == hashsep && s[:n] == sep {
  85                 return 0
  86         }
  87         for i := n; i < len(s); {
  88                 h *= primeRK
  89                 h += uint32(s[i])
  90                 h -= pow * uint32(s[i-n])
  91                 i++
  92                 if h == hashsep && s[i-n:i] == sep {
  93                         return i - n
  94                 }
  95         }
  96         return -1
  97 }