| 1 |
/*! |
| 2 |
This library provides heavily optimized routines for string search primitives. |
| 3 |
|
| 4 |
# Overview |
| 5 |
|
| 6 |
This section gives a brief high level overview of what this crate offers. |
| 7 |
|
| 8 |
* The top-level module provides routines for searching for 1, 2 or 3 bytes |
| 9 |
in the forward or reverse direction. When searching for more than one byte, |
| 10 |
positions are considered a match if the byte at that position matches any |
| 11 |
of the bytes. |
| 12 |
* The [`memmem`] sub-module provides forward and reverse substring search |
| 13 |
routines. |
| 14 |
|
| 15 |
In all such cases, routines operate on `&[u8]` without regard to encoding. This |
| 16 |
is exactly what you want when searching either UTF-8 or arbitrary bytes. |
| 17 |
|
| 18 |
# Example: using `memchr` |
| 19 |
|
| 20 |
This example shows how to use `memchr` to find the first occurrence of `z` in |
| 21 |
a haystack: |
| 22 |
|
| 23 |
``` |
| 24 |
use memchr::memchr; |
| 25 |
|
| 26 |
let haystack = b"foo bar baz quuz"; |
| 27 |
assert_eq!(Some(10), memchr(b'z', haystack)); |
| 28 |
``` |
| 29 |
|
| 30 |
# Example: matching one of three possible bytes |
| 31 |
|
| 32 |
This examples shows how to use `memrchr3` to find occurrences of `a`, `b` or |
| 33 |
`c`, starting at the end of the haystack. |
| 34 |
|
| 35 |
``` |
| 36 |
use memchr::memchr3_iter; |
| 37 |
|
| 38 |
let haystack = b"xyzaxyzbxyzc"; |
| 39 |
|
| 40 |
let mut it = memchr3_iter(b'a', b'b', b'c', haystack).rev(); |
| 41 |
assert_eq!(Some(11), it.next()); |
| 42 |
assert_eq!(Some(7), it.next()); |
| 43 |
assert_eq!(Some(3), it.next()); |
| 44 |
assert_eq!(None, it.next()); |
| 45 |
``` |
| 46 |
|
| 47 |
# Example: iterating over substring matches |
| 48 |
|
| 49 |
This example shows how to use the [`memmem`] sub-module to find occurrences of |
| 50 |
a substring in a haystack. |
| 51 |
|
| 52 |
``` |
| 53 |
use memchr::memmem; |
| 54 |
|
| 55 |
let haystack = b"foo bar foo baz foo"; |
| 56 |
|
| 57 |
let mut it = memmem::find_iter(haystack, "foo"); |
| 58 |
assert_eq!(Some(0), it.next()); |
| 59 |
assert_eq!(Some(8), it.next()); |
| 60 |
assert_eq!(Some(16), it.next()); |
| 61 |
assert_eq!(None, it.next()); |
| 62 |
``` |
| 63 |
|
| 64 |
# Example: repeating a search for the same needle |
| 65 |
|
| 66 |
It may be possible for the overhead of constructing a substring searcher to be |
| 67 |
measurable in some workloads. In cases where the same needle is used to search |
| 68 |
many haystacks, it is possible to do construction once and thus to avoid it for |
| 69 |
subsequent searches. This can be done with a [`memmem::Finder`]: |
| 70 |
|
| 71 |
``` |
| 72 |
use memchr::memmem; |
| 73 |
|
| 74 |
let finder = memmem::Finder::new("foo"); |
| 75 |
|
| 76 |
assert_eq!(Some(4), finder.find(b"baz foo quux")); |
| 77 |
assert_eq!(None, finder.find(b"quux baz bar")); |
| 78 |
``` |
| 79 |
|
| 80 |
# Why use this crate? |
| 81 |
|
| 82 |
At first glance, the APIs provided by this crate might seem weird. Why provide |
| 83 |
a dedicated routine like `memchr` for something that could be implemented |
| 84 |
clearly and trivially in one line: |
| 85 |
|
| 86 |
``` |
| 87 |
fn memchr(needle: u8, haystack: &[u8]) -> Option<usize> { |
| 88 |
haystack.iter().position(|&b| b == needle) |
| 89 |
} |
| 90 |
``` |
| 91 |
|
| 92 |
Or similarly, why does this crate provide substring search routines when Rust's |
| 93 |
core library already provides them? |
| 94 |
|
| 95 |
``` |
| 96 |
fn search(haystack: &str, needle: &str) -> Option<usize> { |
| 97 |
haystack.find(needle) |
| 98 |
} |
| 99 |
``` |
| 100 |
|
| 101 |
The primary reason for both of them to exist is performance. When it comes to |
| 102 |
performance, at a high level at least, there are two primary ways to look at |
| 103 |
it: |
| 104 |
|
| 105 |
* **Throughput**: For this, think about it as, "given some very large haystack |
| 106 |
and a byte that never occurs in that haystack, how long does it take to |
| 107 |
search through it and determine that it, in fact, does not occur?" |
| 108 |
* **Latency**: For this, think about it as, "given a tiny haystack---just a |
| 109 |
few bytes---how long does it take to determine if a byte is in it?" |
| 110 |
|
| 111 |
The `memchr` routine in this crate has _slightly_ worse latency than the |
| 112 |
solution presented above, however, its throughput can easily be over an |
| 113 |
order of magnitude faster. This is a good general purpose trade off to make. |
| 114 |
You rarely lose, but often gain big. |
| 115 |
|
| 116 |
**NOTE:** The name `memchr` comes from the corresponding routine in `libc`. A |
| 117 |
key advantage of using this library is that its performance is not tied to its |
| 118 |
quality of implementation in the `libc` you happen to be using, which can vary |
| 119 |
greatly from platform to platform. |
| 120 |
|
| 121 |
But what about substring search? This one is a bit more complicated. The |
| 122 |
primary reason for its existence is still indeed performance, but it's also |
| 123 |
useful because Rust's core library doesn't actually expose any substring |
| 124 |
search routine on arbitrary bytes. The only substring search routine that |
| 125 |
exists works exclusively on valid UTF-8. |
| 126 |
|
| 127 |
So if you have valid UTF-8, is there a reason to use this over the standard |
| 128 |
library substring search routine? Yes. This routine is faster on almost every |
| 129 |
metric, including latency. The natural question then, is why isn't this |
| 130 |
implementation in the standard library, even if only for searching on UTF-8? |
| 131 |
The reason is that the implementation details for using SIMD in the standard |
| 132 |
library haven't quite been worked out yet. |
| 133 |
|
| 134 |
**NOTE:** Currently, only `x86_64`, `wasm32` and `aarch64` targets have vector |
| 135 |
accelerated implementations of `memchr` (and friends) and `memmem`. |
| 136 |
|
| 137 |
# Crate features |
| 138 |
|
| 139 |
* **std** - When enabled (the default), this will permit features specific to |
| 140 |
the standard library. Currently, the only thing used from the standard library |
| 141 |
is runtime SIMD CPU feature detection. This means that this feature must be |
| 142 |
enabled to get AVX2 accelerated routines on `x86_64` targets without enabling |
| 143 |
the `avx2` feature at compile time, for example. When `std` is not enabled, |
| 144 |
this crate will still attempt to use SSE2 accelerated routines on `x86_64`. It |
| 145 |
will also use AVX2 accelerated routines when the `avx2` feature is enabled at |
| 146 |
compile time. In general, enable this feature if you can. |
| 147 |
* **alloc** - When enabled (the default), APIs in this crate requiring some |
| 148 |
kind of allocation will become available. For example, the |
| 149 |
[`memmem::Finder::into_owned`](crate::memmem::Finder::into_owned) API and the |
| 150 |
[`arch::all::shiftor`](crate::arch::all::shiftor) substring search |
| 151 |
implementation. Otherwise, this crate is designed from the ground up to be |
| 152 |
usable in core-only contexts, so the `alloc` feature doesn't add much |
| 153 |
currently. Notably, disabling `std` but enabling `alloc` will **not** result |
| 154 |
in the use of AVX2 on `x86_64` targets unless the `avx2` feature is enabled |
| 155 |
at compile time. (With `std` enabled, AVX2 can be used even without the `avx2` |
| 156 |
feature enabled at compile time by way of runtime CPU feature detection.) |
| 157 |
* **logging** - When enabled (disabled by default), the `log` crate is used |
| 158 |
to emit log messages about what kinds of `memchr` and `memmem` algorithms |
| 159 |
are used. Namely, both `memchr` and `memmem` have a number of different |
| 160 |
implementation choices depending on the target and CPU, and the log messages |
| 161 |
can help show what specific implementations are being used. Generally, this is |
| 162 |
useful for debugging performance issues. |
| 163 |
* **libc** - **DEPRECATED**. Previously, this enabled the use of the target's |
| 164 |
`memchr` function from whatever `libc` was linked into the program. This |
| 165 |
feature is now a no-op because this crate's implementation of `memchr` should |
| 166 |
now be sufficiently fast on a number of platforms that `libc` should no longer |
| 167 |
be needed. (This feature is somewhat of a holdover from this crate's origins. |
| 168 |
Originally, this crate was literally just a safe wrapper function around the |
| 169 |
`memchr` function from `libc`.) |
| 170 |
*/ |
| 171 |
|
| 172 |
#![deny(missing_docs)] |
| 173 |
#![no_std] |
| 174 |
// It's just not worth trying to squash all dead code warnings. Pretty |
| 175 |
// unfortunate IMO. Not really sure how to fix this other than to either |
| 176 |
// live with it or sprinkle a whole mess of `cfg` annotations everywhere. |
| 177 |
#![cfg_attr( |
| 178 |
not(any( |
| 179 |
all(target_arch = "x86_64", target_feature = "sse2"), |
| 180 |
all(target_arch = "wasm32", target_feature = "simd128"), |
| 181 |
target_arch = "aarch64", |
| 182 |
)), |
| 183 |
allow(dead_code) |
| 184 |
)] |
| 185 |
// Same deal for miri. |
| 186 |
#![cfg_attr(miri, allow(dead_code, unused_macros))] |
| 187 |
|
| 188 |
// Supporting 8-bit (or others) would be fine. If you need it, please submit a |
| 189 |
// bug report at https://github.com/BurntSushi/memchr |
| 190 |
#[cfg(not(any( |
| 191 |
target_pointer_width = "16", |
| 192 |
target_pointer_width = "32", |
| 193 |
target_pointer_width = "64" |
| 194 |
)))] |
| 195 |
compile_error!("memchr currently not supported on non-{16,32,64}"); |
| 196 |
|
| 197 |
#[cfg(any(test, feature = "std"))] |
| 198 |
extern crate std; |
| 199 |
|
| 200 |
#[cfg(any(test, feature = "alloc"))] |
| 201 |
extern crate alloc; |
| 202 |
|
| 203 |
pub use crate::memchr::{ |
| 204 |
memchr, memchr2, memchr2_iter, memchr3, memchr3_iter, memchr_iter, |
| 205 |
memrchr, memrchr2, memrchr2_iter, memrchr3, memrchr3_iter, memrchr_iter, |
| 206 |
Memchr, Memchr2, Memchr3, |
| 207 |
}; |
| 208 |
|
| 209 |
#[macro_use] |
| 210 |
mod macros; |
| 211 |
|
| 212 |
#[cfg(test)] |
| 213 |
#[macro_use] |
| 214 |
mod tests; |
| 215 |
|
| 216 |
pub mod arch; |
| 217 |
mod cow; |
| 218 |
mod ext; |
| 219 |
mod memchr; |
| 220 |
pub mod memmem; |
| 221 |
mod vector; |