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