...
Run Format

Source file src/bytes/bytes_amd64.go

     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	

View as plain text