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