...
Run Format

Source file src/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	package strings
     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 string) 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 string) 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 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 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 && 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 && s[i-n:i] == sep {
    91				return i - n
    92			}
    93		}
    94		return -1
    95	}
    96	

View as plain text