src/libcore/slice/memchr.rs

   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.
   4 //
   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.
  10 //
  11 // Original implementation taken from rust-memchr
  12 // Copyright 2015 Andrew Gallant, bluss and Nicolas Koch
  13
  14 use cmp;
  15 use mem;
  16
  17 const LO_U64: u64 = 0x0101010101010101;
  18 const HI_U64: u64 = 0x8080808080808080;
  19
  20 // use truncation
  21 const LO_USIZE: usize = LO_U64 as usize;
  22 const HI_USIZE: usize = HI_U64 as usize;
  23
  24 /// Return `true` if `x` contains any zero byte.
  25 ///
  26 /// From *Matters Computational*, J. Arndt
  27 ///
  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
  30 /// bit."
  31 #[inline]
  32 fn contains_zero_byte(x: usize) -> bool {
  33     x.wrapping_sub(LO_USIZE) & !x & HI_USIZE != 0
  34 }
  35
  36 #[cfg(target_pointer_width = "16")]
  37 #[inline]
  38 fn repeat_byte(b: u8) -> usize {
  39     (b as usize) << 8 | b as usize
  40 }
  41
  42 #[cfg(not(target_pointer_width = "16"))]
  43 #[inline]
  44 fn repeat_byte(b: u8) -> usize {
  45     (b as usize) * (::usize::MAX / 255)
  46 }
  47
  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.
  51     //
  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
  56     let len = text.len();
  57     let ptr = text.as_ptr();
  58     let usize_bytes = mem::size_of::<usize>();
  59
  60     // search up to an aligned boundary
  61     let mut offset = ptr.align_offset(usize_bytes);
  62     if offset > 0 {
  63         offset = cmp::min(offset, len);
  64         if let Some(index) = text[..offset].iter().position(|elt| *elt == x) {
  65             return Some(index);
  66         }
  67     }
  68
  69     // search the body of the text
  70     let repeated_x = repeat_byte(x);
  71
  72     if len >= 2 * usize_bytes {
  73         while offset <= len - 2 * usize_bytes {
  74             unsafe {
  75                 let u = *(ptr.offset(offset as isize) as *const usize);
  76                 let v = *(ptr.offset((offset + usize_bytes) as isize) as *const usize);
  77
  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);
  81                 if zu || zv {
  82                     break;
  83                 }
  84             }
  85             offset += usize_bytes * 2;
  86         }
  87     }
  88
  89     // find the byte after the point the body loop stopped
  90     text[offset..].iter().position(|elt| *elt == x).map(|i| offset + i)
  91 }
  92
  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.
  96     //
  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();
 103     let usize_bytes = mem::size_of::<usize>();
 104
 105     // search to an aligned boundary
 106     let end_align = (ptr as usize + len) & (usize_bytes - 1);
 107     let mut offset;
 108     if end_align > 0 {
 109         offset = if end_align >= len { 0 } else { len - end_align };
 110         if let Some(index) = text[offset..].iter().rposition(|elt| *elt == x) {
 111             return Some(offset + index);
 112         }
 113     } else {
 114         offset = len;
 115     }
 116
 117     // search the body of the text
 118     let repeated_x = repeat_byte(x);
 119
 120     while offset >= 2 * usize_bytes {
 121         unsafe {
 122             let u = *(ptr.offset(offset as isize - 2 * usize_bytes as isize) as *const usize);
 123             let v = *(ptr.offset(offset as isize - usize_bytes as isize) as *const usize);
 124
 125             // break if there is a matching byte
 126             let zu = contains_zero_byte(u ^ repeated_x);
 127             let zv = contains_zero_byte(v ^ repeated_x);
 128             if zu || zv {
 129                 break;
 130             }
 131         }
 132         offset -= 2 * usize_bytes;
 133     }
 134
 135     // find the byte before the point the body loop stopped
 136     text[..offset].iter().rposition(|elt| *elt == x)
 137 }
 138
 139 // test fallback implementations on all platforms
 140 #[test]
 141 fn matches_one() {
 142     assert_eq!(Some(0), memchr(b'a', b"a"));
 143 }
 144
 145 #[test]
 146 fn matches_begin() {
 147     assert_eq!(Some(0), memchr(b'a', b"aaaa"));
 148 }
 149
 150 #[test]
 151 fn matches_end() {
 152     assert_eq!(Some(4), memchr(b'z', b"aaaaz"));
 153 }
 154
 155 #[test]
 156 fn matches_nul() {
 157     assert_eq!(Some(4), memchr(b'\x00', b"aaaa\x00"));
 158 }
 159
 160 #[test]
 161 fn matches_past_nul() {
 162     assert_eq!(Some(5), memchr(b'z', b"aaaa\x00z"));
 163 }
 164
 165 #[test]
 166 fn no_match_empty() {
 167     assert_eq!(None, memchr(b'a', b""));
 168 }
 169
 170 #[test]
 171 fn no_match() {
 172     assert_eq!(None, memchr(b'a', b"xyz"));
 173 }
 174
 175 #[test]
 176 fn matches_one_reversed() {
 177     assert_eq!(Some(0), memrchr(b'a', b"a"));
 178 }
 179
 180 #[test]
 181 fn matches_begin_reversed() {
 182     assert_eq!(Some(3), memrchr(b'a', b"aaaa"));
 183 }
 184
 185 #[test]
 186 fn matches_end_reversed() {
 187     assert_eq!(Some(0), memrchr(b'z', b"zaaaa"));
 188 }
 189
 190 #[test]
 191 fn matches_nul_reversed() {
 192     assert_eq!(Some(4), memrchr(b'\x00', b"aaaa\x00"));
 193 }
 194
 195 #[test]
 196 fn matches_past_nul_reversed() {
 197     assert_eq!(Some(0), memrchr(b'z', b"z\x00aaaa"));
 198 }
 199
 200 #[test]
 201 fn no_match_empty_reversed() {
 202     assert_eq!(None, memrchr(b'a', b""));
 203 }
 204
 205 #[test]
 206 fn no_match_reversed() {
 207     assert_eq!(None, memrchr(b'a', b"xyz"));
 208 }
 209
 210 #[test]
 211 fn each_alignment_reversed() {
 212     let mut data = [1u8; 64];
 213     let needle = 2;
 214     let pos = 40;
 215     data[pos] = needle;
 216     for start in 0..16 {
 217         assert_eq!(Some(pos - start), memrchr(needle, &data[start..]));
 218     }
 219 }