library/core/src/str/validations.rs

   1 //! Operations related to UTF-8 validation.
   2
   3 use crate::mem;
   4
   5 use super::Utf8Error;
   6
   7 /// Returns the initial codepoint accumulator for the first byte.
   8 /// The first byte is special, only want bottom 5 bits for width 2, 4 bits
   9 /// for width 3, and 3 bits for width 4.
  10 #[inline]
  11 const fn utf8_first_byte(byte: u8, width: u32) -> u32 {
  12     (byte & (0x7F >> width)) as u32
  13 }
  14
  15 /// Returns the value of `ch` updated with continuation byte `byte`.
  16 #[inline]
  17 const fn utf8_acc_cont_byte(ch: u32, byte: u8) -> u32 {
  18     (ch << 6) | (byte & CONT_MASK) as u32
  19 }
  20
  21 /// Checks whether the byte is a UTF-8 continuation byte (i.e., starts with the
  22 /// bits `10`).
  23 #[inline]
  24 pub(super) const fn utf8_is_cont_byte(byte: u8) -> bool {
  25     (byte as i8) < -64
  26 }
  27
  28 /// Reads the next code point out of a byte iterator (assuming a
  29 /// UTF-8-like encoding).
  30 ///
  31 /// # Safety
  32 ///
  33 /// `bytes` must produce a valid UTF-8-like (UTF-8 or WTF-8) string
  34 #[unstable(feature = "str_internals", issue = "none")]
  35 #[inline]
  36 pub unsafe fn next_code_point<'a, I: Iterator<Item = &'a u8>>(bytes: &mut I) -> Option<u32> {
  37     // Decode UTF-8
  38     let x = *bytes.next()?;
  39     if x < 128 {
  40         return Some(x as u32);
  41     }
  42
  43     // Multibyte case follows
  44     // Decode from a byte combination out of: [[[x y] z] w]
  45     // NOTE: Performance is sensitive to the exact formulation here
  46     let init = utf8_first_byte(x, 2);
  47     // SAFETY: `bytes` produces an UTF-8-like string,
  48     // so the iterator must produce a value here.
  49     let y = unsafe { *bytes.next().unwrap_unchecked() };
  50     let mut ch = utf8_acc_cont_byte(init, y);
  51     if x >= 0xE0 {
  52         // [[x y z] w] case
  53         // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
  54         // SAFETY: `bytes` produces an UTF-8-like string,
  55         // so the iterator must produce a value here.
  56         let z = unsafe { *bytes.next().unwrap_unchecked() };
  57         let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
  58         ch = init << 12 | y_z;
  59         if x >= 0xF0 {
  60             // [x y z w] case
  61             // use only the lower 3 bits of `init`
  62             // SAFETY: `bytes` produces an UTF-8-like string,
  63             // so the iterator must produce a value here.
  64             let w = unsafe { *bytes.next().unwrap_unchecked() };
  65             ch = (init & 7) << 18 | utf8_acc_cont_byte(y_z, w);
  66         }
  67     }
  68
  69     Some(ch)
  70 }
  71
  72 /// Reads the last code point out of a byte iterator (assuming a
  73 /// UTF-8-like encoding).
  74 ///
  75 /// # Safety
  76 ///
  77 /// `bytes` must produce a valid UTF-8-like (UTF-8 or WTF-8) string
  78 #[inline]
  79 pub(super) unsafe fn next_code_point_reverse<'a, I>(bytes: &mut I) -> Option<u32>
  80 where
  81     I: DoubleEndedIterator<Item = &'a u8>,
  82 {
  83     // Decode UTF-8
  84     let w = match *bytes.next_back()? {
  85         next_byte if next_byte < 128 => return Some(next_byte as u32),
  86         back_byte => back_byte,
  87     };
  88
  89     // Multibyte case follows
  90     // Decode from a byte combination out of: [x [y [z w]]]
  91     let mut ch;
  92     // SAFETY: `bytes` produces an UTF-8-like string,
  93     // so the iterator must produce a value here.
  94     let z = unsafe { *bytes.next_back().unwrap_unchecked() };
  95     ch = utf8_first_byte(z, 2);
  96     if utf8_is_cont_byte(z) {
  97         // SAFETY: `bytes` produces an UTF-8-like string,
  98         // so the iterator must produce a value here.
  99         let y = unsafe { *bytes.next_back().unwrap_unchecked() };
 100         ch = utf8_first_byte(y, 3);
 101         if utf8_is_cont_byte(y) {
 102             // SAFETY: `bytes` produces an UTF-8-like string,
 103             // so the iterator must produce a value here.
 104             let x = unsafe { *bytes.next_back().unwrap_unchecked() };
 105             ch = utf8_first_byte(x, 4);
 106             ch = utf8_acc_cont_byte(ch, y);
 107         }
 108         ch = utf8_acc_cont_byte(ch, z);
 109     }
 110     ch = utf8_acc_cont_byte(ch, w);
 111
 112     Some(ch)
 113 }
 114
 115 const NONASCII_MASK: usize = usize::repeat_u8(0x80);
 116
 117 /// Returns `true` if any byte in the word `x` is nonascii (>= 128).
 118 #[inline]
 119 const fn contains_nonascii(x: usize) -> bool {
 120     (x & NONASCII_MASK) != 0
 121 }
 122
 123 /// Walks through `v` checking that it's a valid UTF-8 sequence,
 124 /// returning `Ok(())` in that case, or, if it is invalid, `Err(err)`.
 125 #[inline(always)]
 126 #[rustc_const_unstable(feature = "str_internals", issue = "none")]
 127 pub(super) const fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
 128     let mut index = 0;
 129     let len = v.len();
 130
 131     let usize_bytes = mem::size_of::<usize>();
 132     let ascii_block_size = 2 * usize_bytes;
 133     let blocks_end = if len >= ascii_block_size { len - ascii_block_size + 1 } else { 0 };
 134     let align = v.as_ptr().align_offset(usize_bytes);
 135
 136     while index < len {
 137         let old_offset = index;
 138         macro_rules! err {
 139             ($error_len: expr) => {
 140                 return Err(Utf8Error { valid_up_to: old_offset, error_len: $error_len })
 141             };
 142         }
 143
 144         macro_rules! next {
 145             () => {{
 146                 index += 1;
 147                 // we needed data, but there was none: error!
 148                 if index >= len {
 149                     err!(None)
 150                 }
 151                 v[index]
 152             }};
 153         }
 154
 155         let first = v[index];
 156         if first >= 128 {
 157             let w = utf8_char_width(first);
 158             // 2-byte encoding is for codepoints  \u{0080} to  \u{07ff}
 159             //        first  C2 80        last DF BF
 160             // 3-byte encoding is for codepoints  \u{0800} to  \u{ffff}
 161             //        first  E0 A0 80     last EF BF BF
 162             //   excluding surrogates codepoints  \u{d800} to  \u{dfff}
 163             //               ED A0 80 to       ED BF BF
 164             // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
 165             //        first  F0 90 80 80  last F4 8F BF BF
 166             //
 167             // Use the UTF-8 syntax from the RFC
 168             //
 169             // https://tools.ietf.org/html/rfc3629
 170             // UTF8-1      = %x00-7F
 171             // UTF8-2      = %xC2-DF UTF8-tail
 172             // UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
 173             //               %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
 174             // UTF8-4      = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
 175             //               %xF4 %x80-8F 2( UTF8-tail )
 176             match w {
 177                 2 => {
 178                     if next!() as i8 >= -64 {
 179                         err!(Some(1))
 180                     }
 181                 }
 182                 3 => {
 183                     match (first, next!()) {
 184                         (0xE0, 0xA0..=0xBF)
 185                         | (0xE1..=0xEC, 0x80..=0xBF)
 186                         | (0xED, 0x80..=0x9F)
 187                         | (0xEE..=0xEF, 0x80..=0xBF) => {}
 188                         _ => err!(Some(1)),
 189                     }
 190                     if next!() as i8 >= -64 {
 191                         err!(Some(2))
 192                     }
 193                 }
 194                 4 => {
 195                     match (first, next!()) {
 196                         (0xF0, 0x90..=0xBF) | (0xF1..=0xF3, 0x80..=0xBF) | (0xF4, 0x80..=0x8F) => {}
 197                         _ => err!(Some(1)),
 198                     }
 199                     if next!() as i8 >= -64 {
 200                         err!(Some(2))
 201                     }
 202                     if next!() as i8 >= -64 {
 203                         err!(Some(3))
 204                     }
 205                 }
 206                 _ => err!(Some(1)),
 207             }
 208             index += 1;
 209         } else {
 210             // Ascii case, try to skip forward quickly.
 211             // When the pointer is aligned, read 2 words of data per iteration
 212             // until we find a word containing a non-ascii byte.
 213             if align != usize::MAX && align.wrapping_sub(index) % usize_bytes == 0 {
 214                 let ptr = v.as_ptr();
 215                 while index < blocks_end {
 216                     // SAFETY: since `align - index` and `ascii_block_size` are
 217                     // multiples of `usize_bytes`, `block = ptr.add(index)` is
 218                     // always aligned with a `usize` so it's safe to dereference
 219                     // both `block` and `block.offset(1)`.
 220                     unsafe {
 221                         let block = ptr.add(index) as *const usize;
 222                         // break if there is a nonascii byte
 223                         let zu = contains_nonascii(*block);
 224                         let zv = contains_nonascii(*block.offset(1));
 225                         if zu || zv {
 226                             break;
 227                         }
 228                     }
 229                     index += ascii_block_size;
 230                 }
 231                 // step from the point where the wordwise loop stopped
 232                 while index < len && v[index] < 128 {
 233                     index += 1;
 234                 }
 235             } else {
 236                 index += 1;
 237             }
 238         }
 239     }
 240
 241     Ok(())
 242 }
 243
 244 // https://tools.ietf.org/html/rfc3629
 245 const UTF8_CHAR_WIDTH: &[u8; 256] = &[
 246     // 1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
 247     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 0
 248     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 1
 249     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 2
 250     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 3
 251     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 4
 252     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 5
 253     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 6
 254     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 7
 255     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 8
 256     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 9
 257     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // A
 258     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // B
 259     0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // C
 260     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // D
 261     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, // E
 262     4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // F
 263 ];
 264
 265 /// Given a first byte, determines how many bytes are in this UTF-8 character.
 266 #[unstable(feature = "str_internals", issue = "none")]
 267 #[must_use]
 268 #[inline]
 269 pub const fn utf8_char_width(b: u8) -> usize {
 270     UTF8_CHAR_WIDTH[b as usize] as usize
 271 }
 272
 273 /// Mask of the value bits of a continuation byte.
 274 const CONT_MASK: u8 = 0b0011_1111;