1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // Original implementation taken from rust-memchr
12 // Copyright 2015 Andrew Gallant, bluss and Nicolas Koch
16 /// A safe interface to `memchr`.
18 /// Returns the index corresponding to the first occurrence of `needle` in
19 /// `haystack`, or `None` if one is not found.
21 /// memchr reduces to super-optimized machine code at around an order of
22 /// magnitude faster than `haystack.iter().position(|&b| b == needle)`.
27 /// This shows how to find the first position of a byte in a byte string.
30 /// use memchr::memchr;
32 /// let haystack = b"the quick brown fox";
33 /// assert_eq!(memchr(b'k', haystack), Some(8));
35 pub fn memchr(needle: u8, haystack: &[u8]) -> Option<usize> {
37 #[cfg(not(target_os = "windows"))]
38 fn memchr_specific(needle: u8, haystack: &[u8]) -> Option<usize> {
43 haystack.as_ptr() as *const libc::c_void,
44 needle as libc::c_int,
45 haystack.len() as libc::size_t)
50 Some(p as usize - (haystack.as_ptr() as usize))
54 // use fallback on windows, since it's faster
55 #[cfg(target_os = "windows")]
56 fn memchr_specific(needle: u8, haystack: &[u8]) -> Option<usize> {
57 fallback::memchr(needle, haystack)
60 memchr_specific(needle, haystack)
63 /// A safe interface to `memrchr`.
65 /// Returns the index corresponding to the last occurrence of `needle` in
66 /// `haystack`, or `None` if one is not found.
70 /// This shows how to find the last position of a byte in a byte string.
73 /// use memchr::memrchr;
75 /// let haystack = b"the quick brown fox";
76 /// assert_eq!(memrchr(b'o', haystack), Some(17));
78 pub fn memrchr(needle: u8, haystack: &[u8]) -> Option<usize> {
80 #[cfg(target_os = "linux")]
81 fn memrchr_specific(needle: u8, haystack: &[u8]) -> Option<usize> {
84 // GNU's memrchr() will - unlike memchr() - error if haystack is empty.
85 if haystack.is_empty() {return None}
88 haystack.as_ptr() as *const libc::c_void,
89 needle as libc::c_int,
90 haystack.len() as libc::size_t)
95 Some(p as usize - (haystack.as_ptr() as usize))
99 #[cfg(not(target_os = "linux"))]
100 fn memrchr_specific(needle: u8, haystack: &[u8]) -> Option<usize> {
101 fallback::memrchr(needle, haystack)
104 memrchr_specific(needle, haystack)
112 const LO_U64: u64 = 0x0101010101010101;
113 const HI_U64: u64 = 0x8080808080808080;
116 const LO_USIZE: usize = LO_U64 as usize;
117 const HI_USIZE: usize = HI_U64 as usize;
119 /// Return `true` if `x` contains any zero byte.
121 /// From *Matters Computational*, J. Arndt
123 /// "The idea is to subtract one from each of the bytes and then look for
124 /// bytes where the borrow propagated all the way to the most significant
127 fn contains_zero_byte(x: usize) -> bool {
128 x.wrapping_sub(LO_USIZE) & !x & HI_USIZE != 0
131 #[cfg(target_pointer_width = "32")]
133 fn repeat_byte(b: u8) -> usize {
134 let mut rep = (b as usize) << 8 | b as usize;
135 rep = rep << 16 | rep;
139 #[cfg(target_pointer_width = "64")]
141 fn repeat_byte(b: u8) -> usize {
142 let mut rep = (b as usize) << 8 | b as usize;
143 rep = rep << 16 | rep;
144 rep = rep << 32 | rep;
148 /// Return the first index matching the byte `a` in `text`.
149 pub fn memchr(x: u8, text: &[u8]) -> Option<usize> {
150 // Scan for a single byte value by reading two `usize` words at a time.
152 // Split `text` in three parts
153 // - unaligned initial part, before the first word aligned address in text
154 // - body, scan by 2 words at a time
155 // - the last remaining part, < 2 word size
156 let len = text.len();
157 let ptr = text.as_ptr();
158 let usize_bytes = mem::size_of::<usize>();
160 // search up to an aligned boundary
161 let align = (ptr as usize) & (usize_bytes- 1);
164 offset = cmp::min(usize_bytes - align, len);
165 if let Some(index) = text[..offset].iter().position(|elt| *elt == x) {
172 // search the body of the text
173 let repeated_x = repeat_byte(x);
175 if len >= 2 * usize_bytes {
176 while offset <= len - 2 * usize_bytes {
178 let u = *(ptr.offset(offset as isize) as *const usize);
179 let v = *(ptr.offset((offset + usize_bytes) as isize) as *const usize);
181 // break if there is a matching byte
182 let zu = contains_zero_byte(u ^ repeated_x);
183 let zv = contains_zero_byte(v ^ repeated_x);
188 offset += usize_bytes * 2;
192 // find the byte after the point the body loop stopped
193 text[offset..].iter().position(|elt| *elt == x).map(|i| offset + i)
196 /// Return the last index matching the byte `a` in `text`.
197 pub fn memrchr(x: u8, text: &[u8]) -> Option<usize> {
198 // Scan for a single byte value by reading two `usize` words at a time.
200 // Split `text` in three parts
201 // - unaligned tail, after the last word aligned address in text
202 // - body, scan by 2 words at a time
203 // - the first remaining bytes, < 2 word size
204 let len = text.len();
205 let ptr = text.as_ptr();
206 let usize_bytes = mem::size_of::<usize>();
208 // search to an aligned boundary
209 let end_align = (ptr as usize + len) & (usize_bytes - 1);
212 offset = len - cmp::min(usize_bytes - end_align, len);
213 if let Some(index) = text[offset..].iter().rposition(|elt| *elt == x) {
214 return Some(offset + index);
220 // search the body of the text
221 let repeated_x = repeat_byte(x);
223 while offset >= 2 * usize_bytes {
225 let u = *(ptr.offset(offset as isize - 2 * usize_bytes as isize) as *const usize);
226 let v = *(ptr.offset(offset as isize - usize_bytes as isize) as *const usize);
228 // break if there is a matching byte
229 let zu = contains_zero_byte(u ^ repeated_x);
230 let zv = contains_zero_byte(v ^ repeated_x);
235 offset -= 2 * usize_bytes;
238 // find the byte before the point the body loop stopped
239 text[..offset].iter().rposition(|elt| *elt == x)
242 // test fallback implementations on all plattforms
245 assert_eq!(Some(0), memchr(b'a', b"a"));
250 assert_eq!(Some(0), memchr(b'a', b"aaaa"));
255 assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
260 assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
264 fn matches_past_nul() {
265 assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
269 fn no_match_empty() {
270 assert_eq!(None, memchr(b'a', b""));
275 assert_eq!(None, memchr(b'a', b"xyz"));
279 fn matches_one_reversed() {
280 assert_eq!(Some(0), memrchr(b'a', b"a"));
284 fn matches_begin_reversed() {
285 assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
289 fn matches_end_reversed() {
290 assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
294 fn matches_nul_reversed() {
295 assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
299 fn matches_past_nul_reversed() {
300 assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
304 fn no_match_empty_reversed() {
305 assert_eq!(None, memrchr(b'a', b""));
309 fn no_match_reversed() {
310 assert_eq!(None, memrchr(b'a', b"xyz"));
316 // test the implementations for the current plattform
317 use super::{memchr, memrchr};
321 assert_eq!(Some(0), memchr(b'a', b"a"));
326 assert_eq!(Some(0), memchr(b'a', b"aaaa"));
331 assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
336 assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
340 fn matches_past_nul() {
341 assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
345 fn no_match_empty() {
346 assert_eq!(None, memchr(b'a', b""));
351 assert_eq!(None, memchr(b'a', b"xyz"));
355 fn matches_one_reversed() {
356 assert_eq!(Some(0), memrchr(b'a', b"a"));
360 fn matches_begin_reversed() {
361 assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
365 fn matches_end_reversed() {
366 assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
370 fn matches_nul_reversed() {
371 assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
375 fn matches_past_nul_reversed() {
376 assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
380 fn no_match_empty_reversed() {
381 assert_eq!(None, memrchr(b'a', b""));
385 fn no_match_reversed() {
386 assert_eq!(None, memrchr(b'a', b"xyz"));