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
17 const LO_U64: u64 = 0x0101010101010101;
18 const HI_U64: u64 = 0x8080808080808080;
21 const LO_USIZE: usize = LO_U64 as usize;
22 const HI_USIZE: usize = HI_U64 as usize;
24 /// Return `true` if `x` contains any zero byte.
26 /// From *Matters Computational*, J. Arndt
28 /// "The idea is to subtract one from each of the bytes and then look for
29 /// bytes where the borrow propagated all the way to the most significant
32 fn contains_zero_byte(x: usize) -> bool {
33 x.wrapping_sub(LO_USIZE) & !x & HI_USIZE != 0
36 #[cfg(target_pointer_width = "16")]
38 fn repeat_byte(b: u8) -> usize {
39 (b as usize) << 8 | b as usize
42 #[cfg(not(target_pointer_width = "16"))]
44 fn repeat_byte(b: u8) -> usize {
45 (b as usize) * (::usize::MAX / 255)
48 /// Return the first index matching the byte `x` in `text`.
49 pub fn memchr(x: u8, text: &[u8]) -> Option<usize> {
50 // Scan for a single byte value by reading two `usize` words at a time.
52 // Split `text` in three parts
53 // - unaligned initial part, before the first word aligned address in text
54 // - body, scan by 2 words at a time
55 // - the last remaining part, < 2 word size
57 let ptr = text.as_ptr();
58 let usize_bytes = mem::size_of::<usize>();
60 // search up to an aligned boundary
61 let mut offset = ptr.align_offset(usize_bytes);
63 offset = cmp::min(offset, len);
64 if let Some(index) = text[..offset].iter().position(|elt| *elt == x) {
69 // search the body of the text
70 let repeated_x = repeat_byte(x);
72 if len >= 2 * usize_bytes {
73 while offset <= len - 2 * usize_bytes {
75 let u = *(ptr.offset(offset as isize) as *const usize);
76 let v = *(ptr.offset((offset + usize_bytes) as isize) as *const usize);
78 // break if there is a matching byte
79 let zu = contains_zero_byte(u ^ repeated_x);
80 let zv = contains_zero_byte(v ^ repeated_x);
85 offset += usize_bytes * 2;
89 // find the byte after the point the body loop stopped
90 text[offset..].iter().position(|elt| *elt == x).map(|i| offset + i)
93 /// Return the last index matching the byte `x` in `text`.
94 pub fn memrchr(x: u8, text: &[u8]) -> Option<usize> {
95 // Scan for a single byte value by reading two `usize` words at a time.
97 // Split `text` in three parts
98 // - unaligned tail, after the last word aligned address in text
99 // - body, scan by 2 words at a time
100 // - the first remaining bytes, < 2 word size
101 let len = text.len();
102 let ptr = text.as_ptr();
105 let (min_aligned_offset, max_aligned_offset) = {
106 // We call this just to obtain the length of the prefix and suffix.
107 // In the middle we always process two chunks at once.
108 let (prefix, _, suffix) = unsafe { text.align_to::<(Chunk, Chunk)>() };
109 (prefix.len(), len - suffix.len())
112 let mut offset = max_aligned_offset;
113 if let Some(index) = text[offset..].iter().rposition(|elt| *elt == x) {
114 return Some(offset + index);
117 // search the body of the text, make sure we don't cross min_aligned_offset.
118 // offset is always aligned, so just testing `>` is sufficient and avoids possible
120 let repeated_x = repeat_byte(x);
121 let chunk_bytes = mem::size_of::<Chunk>();
123 while offset > min_aligned_offset {
125 let u = *(ptr.offset(offset as isize - 2 * chunk_bytes as isize) as *const Chunk);
126 let v = *(ptr.offset(offset as isize - chunk_bytes as isize) as *const Chunk);
128 // break if there is a matching byte
129 let zu = contains_zero_byte(u ^ repeated_x);
130 let zv = contains_zero_byte(v ^ repeated_x);
135 offset -= 2 * chunk_bytes;
138 // find the byte before the point the body loop stopped
139 text[..offset].iter().rposition(|elt| *elt == x)