bytealg.go

     1  // Copyright 2018 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 bytealg
     6  
     7  import (
     8  	"internal/cpu"
     9  	"unsafe"
    10  )
    11  
    12  // Offsets into internal/cpu records for use in assembly.
    13  const (
    14  	offsetX86HasSSE42  = unsafe.Offsetof(cpu.X86.HasSSE42)
    15  	offsetX86HasAVX2   = unsafe.Offsetof(cpu.X86.HasAVX2)
    16  	offsetX86HasPOPCNT = unsafe.Offsetof(cpu.X86.HasPOPCNT)
    17  
    18  	offsetS390xHasVX = unsafe.Offsetof(cpu.S390X.HasVX)
    19  
    20  	offsetPPC64HasPOWER9 = unsafe.Offsetof(cpu.PPC64.IsPOWER9)
    21  )
    22  
    23  // MaxLen is the maximum length of the string to be searched for (argument b) in Index.
    24  // If MaxLen is not 0, make sure MaxLen >= 4.
    25  var MaxLen int
    26  
    27  // PrimeRK is the prime base used in Rabin-Karp algorithm.
    28  const PrimeRK = 16777619
    29  
    30  // HashStr returns the hash and the appropriate multiplicative
    31  // factor for use in Rabin-Karp algorithm.
    32  func HashStr[T string | []byte](sep T) (uint32, uint32) {
    33  	hash := uint32(0)
    34  	for i := 0; i < len(sep); i++ {
    35  		hash = hash*PrimeRK + uint32(sep[i])
    36  	}
    37  	var pow, sq uint32 = 1, PrimeRK
    38  	for i := len(sep); i > 0; i >>= 1 {
    39  		if i&1 != 0 {
    40  			pow *= sq
    41  		}
    42  		sq *= sq
    43  	}
    44  	return hash, pow
    45  }
    46  
    47  // HashStrRev returns the hash of the reverse of sep and the
    48  // appropriate multiplicative factor for use in Rabin-Karp algorithm.
    49  func HashStrRev[T string | []byte](sep T) (uint32, uint32) {
    50  	hash := uint32(0)
    51  	for i := len(sep) - 1; i >= 0; i-- {
    52  		hash = hash*PrimeRK + uint32(sep[i])
    53  	}
    54  	var pow, sq uint32 = 1, PrimeRK
    55  	for i := len(sep); i > 0; i >>= 1 {
    56  		if i&1 != 0 {
    57  			pow *= sq
    58  		}
    59  		sq *= sq
    60  	}
    61  	return hash, pow
    62  }
    63  
    64  // IndexRabinKarp uses the Rabin-Karp search algorithm to return the index of the
    65  // first occurrence of sep in s, or -1 if not present.
    66  func IndexRabinKarp[T string | []byte](s, sep T) int {
    67  	// Rabin-Karp search
    68  	hashss, pow := HashStr(sep)
    69  	n := len(sep)
    70  	var h uint32
    71  	for i := 0; i < n; i++ {
    72  		h = h*PrimeRK + uint32(s[i])
    73  	}
    74  	if h == hashss && string(s[:n]) == string(sep) {
    75  		return 0
    76  	}
    77  	for i := n; i < len(s); {
    78  		h *= PrimeRK
    79  		h += uint32(s[i])
    80  		h -= pow * uint32(s[i-n])
    81  		i++
    82  		if h == hashss && string(s[i-n:i]) == string(sep) {
    83  			return i - n
    84  		}
    85  	}
    86  	return -1
    87  }
    88  
    89  // LastIndexRabinKarp uses the Rabin-Karp search algorithm to return the last index of the
    90  // occurrence of sep in s, or -1 if not present.
    91  func LastIndexRabinKarp[T string | []byte](s, sep T) int {
    92  	// Rabin-Karp search from the end of the string
    93  	hashss, pow := HashStrRev(sep)
    94  	n := len(sep)
    95  	last := len(s) - n
    96  	var h uint32
    97  	for i := len(s) - 1; i >= last; i-- {
    98  		h = h*PrimeRK + uint32(s[i])
    99  	}
   100  	if h == hashss && string(s[last:]) == string(sep) {
   101  		return last
   102  	}
   103  	for i := last - 1; i >= 0; i-- {
   104  		h *= PrimeRK
   105  		h += uint32(s[i])
   106  		h -= pow * uint32(s[i+n])
   107  		if h == hashss && string(s[i:i+n]) == string(sep) {
   108  			return i
   109  		}
   110  	}
   111  	return -1
   112  }
   113  
   114  // MakeNoZero makes a slice of length n and capacity of at least n Bytes
   115  // without zeroing the bytes (including the bytes between len and cap).
   116  // It is the caller's responsibility to ensure uninitialized bytes
   117  // do not leak to the end user.
   118  func MakeNoZero(n int) []byte
   119
View as plain text