1 use memchr::{memchr, memchr2, memchr3, memrchr, memrchr2, memrchr3};
2 mod scalar;
3
4 #[inline]
build_table(byteset: &[u8]) -> [u8; 256]5 fn build_table(byteset: &[u8]) -> [u8; 256] {
6 let mut table = [0u8; 256];
7 for &b in byteset {
8 table[b as usize] = 1;
9 }
10 table
11 }
12
13 #[inline]
find(haystack: &[u8], byteset: &[u8]) -> Option<usize>14 pub(crate) fn find(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
15 match byteset.len() {
16 0 => return None,
17 1 => memchr(byteset[0], haystack),
18 2 => memchr2(byteset[0], byteset[1], haystack),
19 3 => memchr3(byteset[0], byteset[1], byteset[2], haystack),
20 _ => {
21 let table = build_table(byteset);
22 scalar::forward_search_bytes(haystack, |b| table[b as usize] != 0)
23 }
24 }
25 }
26
27 #[inline]
rfind(haystack: &[u8], byteset: &[u8]) -> Option<usize>28 pub(crate) fn rfind(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
29 match byteset.len() {
30 0 => return None,
31 1 => memrchr(byteset[0], haystack),
32 2 => memrchr2(byteset[0], byteset[1], haystack),
33 3 => memrchr3(byteset[0], byteset[1], byteset[2], haystack),
34 _ => {
35 let table = build_table(byteset);
36 scalar::reverse_search_bytes(haystack, |b| table[b as usize] != 0)
37 }
38 }
39 }
40
41 #[inline]
find_not(haystack: &[u8], byteset: &[u8]) -> Option<usize>42 pub(crate) fn find_not(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
43 if haystack.is_empty() {
44 return None;
45 }
46 match byteset.len() {
47 0 => return Some(0),
48 1 => scalar::inv_memchr(byteset[0], haystack),
49 2 => scalar::forward_search_bytes(haystack, |b| {
50 b != byteset[0] && b != byteset[1]
51 }),
52 3 => scalar::forward_search_bytes(haystack, |b| {
53 b != byteset[0] && b != byteset[1] && b != byteset[2]
54 }),
55 _ => {
56 let table = build_table(byteset);
57 scalar::forward_search_bytes(haystack, |b| table[b as usize] == 0)
58 }
59 }
60 }
61 #[inline]
rfind_not(haystack: &[u8], byteset: &[u8]) -> Option<usize>62 pub(crate) fn rfind_not(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
63 if haystack.is_empty() {
64 return None;
65 }
66 match byteset.len() {
67 0 => return Some(haystack.len() - 1),
68 1 => scalar::inv_memrchr(byteset[0], haystack),
69 2 => scalar::reverse_search_bytes(haystack, |b| {
70 b != byteset[0] && b != byteset[1]
71 }),
72 3 => scalar::reverse_search_bytes(haystack, |b| {
73 b != byteset[0] && b != byteset[1] && b != byteset[2]
74 }),
75 _ => {
76 let table = build_table(byteset);
77 scalar::reverse_search_bytes(haystack, |b| table[b as usize] == 0)
78 }
79 }
80 }
81
82 #[cfg(test)]
83 mod tests {
84 quickcheck::quickcheck! {
85 fn qc_byteset_forward_matches_naive(
86 haystack: Vec<u8>,
87 needles: Vec<u8>
88 ) -> bool {
89 super::find(&haystack, &needles)
90 == haystack.iter().position(|b| needles.contains(b))
91 }
92 fn qc_byteset_backwards_matches_naive(
93 haystack: Vec<u8>,
94 needles: Vec<u8>
95 ) -> bool {
96 super::rfind(&haystack, &needles)
97 == haystack.iter().rposition(|b| needles.contains(b))
98 }
99 fn qc_byteset_forward_not_matches_naive(
100 haystack: Vec<u8>,
101 needles: Vec<u8>
102 ) -> bool {
103 super::find_not(&haystack, &needles)
104 == haystack.iter().position(|b| !needles.contains(b))
105 }
106 fn qc_byteset_backwards_not_matches_naive(
107 haystack: Vec<u8>,
108 needles: Vec<u8>
109 ) -> bool {
110 super::rfind_not(&haystack, &needles)
111 == haystack.iter().rposition(|b| !needles.contains(b))
112 }
113 }
114 }
115