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