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 import "internal/cpu"
  10
  11 //go:noescape
  12
  13 // indexShortStr returns the index of the first instance of c in s, or -1 if c is not present in s.
  14 // indexShortStr requires 2 <= len(c) <= shortStringLen
  15 func indexShortStr(s, c string) int  // ../runtime/asm_amd64.s
  16 func countByte(s string, c byte) int // ../runtime/asm_amd64.s
  17
  18 var shortStringLen int
  19
  20 func init() {
  21         if cpu.X86.HasAVX2 {
  22                 shortStringLen = 63
  23         } else {
  24                 shortStringLen = 31
  25         }
  26 }
  27
  28 // Index returns the index of the first instance of substr in s, or -1 if substr is not present in s.
  29 func Index(s, substr string) int {
  30         n := len(substr)
  31         switch {
  32         case n == 0:
  33                 return 0
  34         case n == 1:
  35                 return IndexByte(s, substr[0])
  36         case n == len(s):
  37                 if substr == s {
  38                         return 0
  39                 }
  40                 return -1
  41         case n > len(s):
  42                 return -1
  43         case n <= shortStringLen:
  44                 // Use brute force when s and substr both are small
  45                 if len(s) <= 64 {
  46                         return indexShortStr(s, substr)
  47                 }
  48                 c := substr[0]
  49                 i := 0
  50                 t := s[:len(s)-n+1]
  51                 fails := 0
  52                 for i < len(t) {
  53                         if t[i] != c {
  54                                 // IndexByte skips 16/32 bytes per iteration,
  55                                 // so it's faster than indexShortStr.
  56                                 o := IndexByte(t[i:], c)
  57                                 if o < 0 {
  58                                         return -1
  59                                 }
  60                                 i += o
  61                         }
  62                         if s[i:i+n] == substr {
  63                                 return i
  64                         }
  65                         fails++
  66                         i++
  67                         // Switch to indexShortStr when IndexByte produces too many false positives.
  68                         // Too many means more that 1 error per 8 characters.
  69                         // Allow some errors in the beginning.
  70                         if fails > (i+16)/8 {
  71                                 r := indexShortStr(s[i:], substr)
  72                                 if r >= 0 {
  73                                         return r + i
  74                                 }
  75                                 return -1
  76                         }
  77                 }
  78                 return -1
  79         }
  80         // Rabin-Karp search
  81         hashss, pow := hashStr(substr)
  82         var h uint32
  83         for i := 0; i < n; i++ {
  84                 h = h*primeRK + uint32(s[i])
  85         }
  86         if h == hashss && s[:n] == substr {
  87                 return 0
  88         }
  89         for i := n; i < len(s); {
  90                 h *= primeRK
  91                 h += uint32(s[i])
  92                 h -= pow * uint32(s[i-n])
  93                 i++
  94                 if h == hashss && s[i-n:i] == substr {
  95                         return i - n
  96                 }
  97         }
  98         return -1
  99 }
 100
 101 // Count counts the number of non-overlapping instances of substr in s.
 102 // If substr is an empty string, Count returns 1 + the number of Unicode code points in s.
 103 func Count(s, substr string) int {
 104         if len(substr) == 1 && cpu.X86.HasPOPCNT {
 105                 return countByte(s, byte(substr[0]))
 106         }
 107         return countGeneric(s, substr)
 108 }