Documentation
¶
Overview ¶
Package simd provides SIMD-accelerated byte searching and validation primitives for the Fiber ecosystem: multi-needle scans, character-class scans, paired-byte scans, substring search, and ASCII validation.
Acceleration comes in two tiers. The scan kernels — Memchr2, Memchr3, MemchrPair, MemchrDigit, MemchrWord, MemchrNotWord, IsASCII, FirstNonASCII, and CountNonASCII — dispatch to AVX2 assembly on amd64 CPUs (for inputs of MinLen+ bytes) and fall back to portable SWAR loops built on the swar package everywhere else. The kernels consume four 32-byte vectors per iteration. The first-match scans and IsASCII combine the per-vector masks, so a 128-byte block costs one mask extraction and one branch, and the scans that report a position then re-extract the four masks in address order to locate the hit. CountNonASCII is the exception: a count cannot be recovered from a combined mask, so it extracts and population-counts all four (and, unlike the others, gates on POPCNT as well as AVX2). Memmem prefilters 128+ byte haystacks on amd64 — needles of 2-6 bytes containing two distinct values through the MemchrPair kernel, longer or single-valued needles through a single rare-byte bytes.IndexByte scan — and delegates to bytes.Index for shorter haystacks or without AVX2. MemchrInTable/MemchrNotInTable are plain scalar loops on every architecture, since an arbitrary 256-entry membership test has no cheap vector form. Accelerated reports whether the AVX2 tier is active. Single-byte search is deliberately absent: bytes.IndexByte is already vector-accelerated by the Go runtime on all major architectures.
Unlike the top-level utils helpers, this package operates on []byte only — it is the raw engine underneath the generic helpers. Callers holding a string can use the top-level generic functions instead of converting.
Adapted from the coregex project, https://github.com/coregx/coregex (package simd), Copyright (c) 2025 Andrey Kolkov and contributors, MIT License. See the LICENSE file in this directory for the full text.
Index ¶
- Constants
- func Accelerated() bool
- func ByteRank(b byte) byte
- func CountNonASCII(data []byte) int
- func FirstNonASCII(data []byte) int
- func IsASCII(data []byte) bool
- func Memchr2(haystack []byte, needle1, needle2 byte) int
- func Memchr3(haystack []byte, needle1, needle2, needle3 byte) int
- func MemchrDigit(haystack []byte) int
- func MemchrDigitAt(haystack []byte, at int) int
- func MemchrInTable(haystack []byte, table *[256]bool) int
- func MemchrNotInTable(haystack []byte, table *[256]bool) int
- func MemchrNotWord(haystack []byte) int
- func MemchrPair(haystack []byte, byte1, byte2 byte, offset int) int
- func MemchrWord(haystack []byte) int
- func Memmem(haystack, needle []byte) int
- type RareByteInfo
Constants ¶
const MinLen = 32
MinLen is the input length from which the AVX2 kernels engage on amd64: they consume whole 32-byte vectors, and below one vector their setup cost outweighs the win, so shorter inputs take the SWAR fallbacks. Callers that route between their own word loops and this package (as the top-level utils helpers do) should gate on this constant rather than hard-coding 32, so a retune here propagates everywhere.
Variables ¶
This section is empty.
Functions ¶
func Accelerated ¶
func Accelerated() bool
Accelerated reports whether the AVX2 assembly kernels are in use on this CPU. When false, all functions use portable fallback implementations.
func ByteRank ¶
ByteRank returns the empirical frequency rank of b. Lower values indicate rarer bytes, which are better anchors for search prefilters; SelectRareBytes and Memmem rank needle bytes with it.
func CountNonASCII ¶
CountNonASCII returns the number of bytes >= 0x80 in data.
On amd64 with AVX2 and inputs of MinLen+ bytes it turns each 32-byte vector into a high-bit mask and adds its population count; elsewhere it counts SWAR-word-wise with a popcount per word.
func FirstNonASCII ¶
FirstNonASCII returns the index of the first byte >= 0x80 in data, or -1 if data is all ASCII. Use it to find where UTF-8 sequences begin.
It reads the same signal as IsASCII — a non-ASCII byte is exactly a byte with its high bit set — so on amd64 with AVX2 and inputs of MinLen+ bytes it also tests 128 bytes per VPMOVMSKB, keeping the four vectors live so the hit path can pinpoint the byte; elsewhere it falls back to SWAR words.
func IsASCII ¶
IsASCII reports whether every byte in data is ASCII (< 0x80). An empty slice is trivially ASCII.
On amd64 with AVX2 and inputs of MinLen+ bytes it ORs four 32-byte vectors and tests all 128 bytes with a single VPMOVMSKB; elsewhere it uses a SWAR loop over 8-byte words.
func Memchr2 ¶
Memchr2 returns the index of the first occurrence in haystack of either needle1 or needle2, or -1 if neither is present. Both needles are checked in the same pass, so it costs the same as a single-byte scan.
There is deliberately no single-needle Memchr: use bytes.IndexByte, which the Go runtime already accelerates on all major architectures.
func Memchr3 ¶
Memchr3 returns the index of the first occurrence in haystack of needle1, needle2, or needle3, or -1 if none is present. All three needles are checked in the same pass.
func MemchrDigit ¶
MemchrDigit returns the index of the first ASCII digit '0'..'9' in haystack, or -1 if no digit is present. Only ASCII digits match; Unicode digit characters do not.
On amd64 with AVX2 the range check runs on 32 bytes per vector, four vectors per iteration, which is useful for locating numeric fields (ports, lengths, IP octets) in request data.
func MemchrDigitAt ¶
MemchrDigitAt is MemchrDigit(haystack[at:]) with the result translated back to an absolute index in haystack. It returns -1 when no digit is found or when at is out of bounds.
func MemchrInTable ¶
MemchrInTable returns the index of the first byte b of haystack with table[b] true, or -1 if none matches or table is nil.
This is a plain scalar table scan on every architecture — an arbitrary 256-entry membership test has no cheap SIMD or SWAR form — so unlike the rest of this package it carries no acceleration. For the \w class specifically, MemchrWord is much faster.
func MemchrNotInTable ¶
MemchrNotInTable is the complement of MemchrInTable: it returns the index of the first byte b with table[b] false, or -1 if every byte is in the table or table is nil. Like MemchrInTable it is a plain scalar loop on every architecture.
func MemchrNotWord ¶
MemchrNotWord is the complement of MemchrWord: it returns the index of the first byte that is NOT a word character, or -1 if every byte is one.
func MemchrPair ¶
MemchrPair returns the first index i such that haystack[i] == byte1 and haystack[i+offset] == byte2, or -1 if no such position exists. offset must be >= 0; a negative offset returns -1.
Requiring two bytes at a fixed distance makes the scan far more selective than a single-byte search, which is what makes it a good substring prefilter: false candidates need both bytes at exactly the right distance. Memmem uses it for short needles.
func MemchrWord ¶
MemchrWord returns the index of the first word character — 'A'..'Z', 'a'..'z', '0'..'9', or '_' (the regex \w class) — in haystack, or -1 if none is present.
func Memmem ¶
Memmem returns the index of the first occurrence of needle in haystack, or -1 if needle is not present. An empty needle matches at index 0, mirroring bytes.Index.
On amd64 with AVX2 and haystacks of 128+ bytes it prefilters with the needle's rarest bytes (per ByteRank) and verifies only the candidate positions, which typically beats bytes.Index by a wide margin on large inputs: needles of 2-6 bytes containing two distinct byte values are scanned for their two rarest values at the exact relative distance, while longer or single-valued needles are scanned for the single rarest byte. In all other cases it delegates to bytes.Index directly, and the prefilter itself falls back to bytes.Index after a bounded number of failed candidate verifications, so the worst case stays within a constant of the stdlib's O(n+m).
Types ¶
type RareByteInfo ¶
type RareByteInfo struct {
// Byte1 is the rarest byte found in the needle.
Byte1 byte
// Byte2 is the rarest byte with a value different from Byte1, when the
// needle has one; otherwise it equals Byte1.
Byte2 byte
// Index1 is the position of Byte1's first occurrence in the needle.
Index1 int
// Index2 is the position of Byte2's first occurrence in the needle.
Index2 int
}
RareByteInfo describes the two rarest bytes of a needle, as selected by SelectRareBytes. When the needle contains at least two distinct byte values, Byte2 always differs from Byte1; only for empty, single-byte, or all-identical needles do Byte2/Index2 equal Byte1/Index1.
func SelectRareBytes ¶
func SelectRareBytes(needle []byte) RareByteInfo
SelectRareBytes returns the two rarest bytes of needle according to ByteRank, preferring distinct byte values: whenever the needle contains two distinct values, Byte2 is the rarest byte different from Byte1, so duplicated occurrences of the rarest byte never crowd out a usable second anchor. Memmem feeds the result to MemchrPair to build a highly selective substring prefilter; it is exported so downstream code can build its own prefilters the same way.
Source Files