• Home
Name
Date
Size
#Lines
LOC

..--

.github/workflows/07-Sep-2024-210193

bench/07-Sep-2024-589,044553,833

fuzz/07-Sep-2024-223175

scripts/07-Sep-2024-7540

src/07-Sep-2024-8,4845,505

.gitignoreD07-Sep-202494 1110

.ignoreD07-Sep-20249 21

BUILD.gnD07-Sep-20241 KiB3127

COPYINGD07-Sep-2024126 42

Cargo.tomlD07-Sep-20241.6 KiB5846

LICENSE-MITD07-Sep-20241.1 KiB2217

OAT.xmlD07-Sep-20244.2 KiB6813

README.OpenSourceD07-Sep-2024317 1111

README.mdD07-Sep-20244.4 KiB10877

UNLICENSED07-Sep-20241.2 KiB2520

build.rsD07-Sep-20242.7 KiB8960

rustfmt.tomlD07-Sep-202444 32

README.OpenSource

1 [
2   {
3     "Name": "memchr",
4     "License": "MIT",
5     "License File": "LICENSE-MIT",
6     "Version Number": "2.5.0",
7     "Owner": "fangting12@huawei.com",
8     "Upstream URL": "https://github.com/BurntSushi/memchr",
9     "Description": "A Rust library that provides support for searching for characters in memory."
10   }
11 ]

README.md

1 memchr
2 ======
3 This library provides heavily optimized routines for string search primitives.
4 
5 [![Build status](https://github.com/BurntSushi/memchr/workflows/ci/badge.svg)](https://github.com/BurntSushi/memchr/actions)
6 [![Crates.io](https://img.shields.io/crates/v/memchr.svg)](https://crates.io/crates/memchr)
7 
8 Dual-licensed under MIT or the [UNLICENSE](https://unlicense.org/).
9 
10 
11 ### Documentation
12 
13 [https://docs.rs/memchr](https://docs.rs/memchr)
14 
15 
16 ### Overview
17 
18 * The top-level module provides routines for searching for 1, 2 or 3 bytes
19   in the forward or reverse direction. When searching for more than one byte,
20   positions are considered a match if the byte at that position matches any
21   of the bytes.
22 * The `memmem` sub-module provides forward and reverse substring search
23   routines.
24 
25 In all such cases, routines operate on `&[u8]` without regard to encoding. This
26 is exactly what you want when searching either UTF-8 or arbitrary bytes.
27 
28 ### Compiling without the standard library
29 
30 memchr links to the standard library by default, but you can disable the
31 `std` feature if you want to use it in a `#![no_std]` crate:
32 
33 ```toml
34 [dependencies]
35 memchr = { version = "2", default-features = false }
36 ```
37 
38 On x86 platforms, when the `std` feature is disabled, the SSE2 accelerated
39 implementations will be used. When `std` is enabled, AVX accelerated
40 implementations will be used if the CPU is determined to support it at runtime.
41 
42 ### Using libc
43 
44 `memchr` is a routine that is part of libc, although this crate does not use
45 libc by default. Instead, it uses its own routines, which are either vectorized
46 or generic fallback routines. In general, these should be competitive with
47 what's in libc, although this has not been tested for all architectures. If
48 using `memchr` from libc is desirable and a vectorized routine is not otherwise
49 available in this crate, then enabling the `libc` feature will use libc's
50 version of `memchr`.
51 
52 The rest of the functions in this crate, e.g., `memchr2` or `memrchr3` and the
53 substring search routines, will always use the implementations in this crate.
54 One exception to this is `memrchr`, which is an extension in `libc` found on
55 Linux. On Linux, `memrchr` is used in precisely the same scenario as `memchr`,
56 as described above.
57 
58 
59 ### Minimum Rust version policy
60 
61 This crate's minimum supported `rustc` version is `1.41.1`.
62 
63 The current policy is that the minimum Rust version required to use this crate
64 can be increased in minor version updates. For example, if `crate 1.0` requires
65 Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust
66 1.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum
67 version of Rust.
68 
69 In general, this crate will be conservative with respect to the minimum
70 supported version of Rust.
71 
72 
73 ### Testing strategy
74 
75 Given the complexity of the code in this crate, along with the pervasive use
76 of `unsafe`, this crate has an extensive testing strategy. It combines multiple
77 approaches:
78 
79 * Hand-written tests.
80 * Exhaustive-style testing meant to exercise all possible branching and offset
81   calculations.
82 * Property based testing through [`quickcheck`](https://github.com/BurntSushi/quickcheck).
83 * Fuzz testing through [`cargo fuzz`](https://github.com/rust-fuzz/cargo-fuzz).
84 * A huge suite of benchmarks that are also run as tests. Benchmarks always
85   confirm that the expected result occurs.
86 
87 Improvements to the testing infrastructure are very welcome.
88 
89 
90 ### Algorithms used
91 
92 At time of writing, this crate's implementation of substring search actually
93 has a few different algorithms to choose from depending on the situation.
94 
95 * For very small haystacks,
96   [Rabin-Karp](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm)
97   is used to reduce latency. Rabin-Karp has very small overhead and can often
98   complete before other searchers have even been constructed.
99 * For small needles, a variant of the
100   ["Generic SIMD"](http://0x80.pl/articles/simd-strfind.html#algorithm-1-generic-simd)
101   algorithm is used. Instead of using the first and last bytes, a heuristic is
102   used to select bytes based on a background distribution of byte frequencies.
103 * In all other cases,
104   [Two-Way](https://en.wikipedia.org/wiki/Two-way_string-matching_algorithm)
105   is used. If possible, a prefilter based on the "Generic SIMD" algorithm
106   linked above is used to find candidates quickly. A dynamic heuristic is used
107   to detect if the prefilter is ineffective, and if so, disables it.
108