3 // Lower-case ASCII 'a' is the first byte that has its highest bit set
4 // after wrap-adding 0x1F:
6 // b'a' + 0x1F == 0x80 == 0b1000_0000
7 // b'z' + 0x1F == 0x98 == 0b1001_1000
9 // Lower-case ASCII 'z' is the last byte that has its highest bit unset
10 // after wrap-adding 0x05:
12 // b'a' + 0x05 == 0x66 == 0b0110_0110
13 // b'z' + 0x05 == 0x7F == 0b0111_1111
15 // … except for 0xFB to 0xFF, but those are in the range of bytes
16 // that have the highest bit unset again after adding 0x1F.
18 // So `(byte + 0x1f) & !(byte + 5)` has its highest bit set
19 // iff `byte` is a lower-case ASCII letter.
21 // Lower-case ASCII letters all have the 0x20 bit set.
22 // (Two positions right of 0x80, the highest bit.)
23 // Unsetting that bit produces the same letter, in upper-case.
26 fn branchless_to_ascii_upper_case(byte: u8) -> u8 {
27 byte & !((byte.wrapping_add(0x1f) & !byte.wrapping_add(0x05) & 0x80) >> 2)
30 macro_rules! benches {
31 ($( fn $name: ident($arg: ident: &mut [u8]) $body: block )+ @iter $( $is_: ident, )+) => {
33 $( fn $name($arg: &mut [u8]) $body )+
34 $( fn $is_(bytes: &mut [u8]) { bytes.iter().all(u8::$is_) } )+
38 (@$( fn $name: ident($arg: ident: &mut [u8]) $body: block )+) => {
39 benches!(mod short SHORT $($name $arg $body)+);
40 benches!(mod medium MEDIUM $($name $arg $body)+);
41 benches!(mod long LONG $($name $arg $body)+);
44 (mod $mod_name: ident $input: ident $($name: ident $arg: ident $body: block)+) => {
50 fn $name(bencher: &mut Bencher) {
51 bencher.bytes = $input.len() as u64;
53 let mut vec = $input.as_bytes().to_vec();
55 let $arg = &mut vec[..];
69 const ASCII_CASE_MASK: u8 = 0b0010_0000;
72 fn case00_alloc_only(_bytes: &mut [u8]) {}
74 fn case01_black_box_read_each_byte(bytes: &mut [u8]) {
80 fn case02_lookup_table(bytes: &mut [u8]) {
82 *byte = ASCII_UPPERCASE_MAP[*byte as usize]
86 fn case03_branch_and_subtract(bytes: &mut [u8]) {
88 *byte = if b'a' <= *byte && *byte <= b'z' {
96 fn case04_branch_and_mask(bytes: &mut [u8]) {
98 *byte = if b'a' <= *byte && *byte <= b'z' {
106 fn case05_branchless(bytes: &mut [u8]) {
108 *byte = branchless_to_ascii_upper_case(*byte)
112 fn case06_libcore(bytes: &mut [u8]) {
113 bytes.make_ascii_uppercase()
116 fn case07_fake_simd_u32(bytes: &mut [u8]) {
117 // SAFETY: transmuting a sequence of `u8` to `u32` is always fine
118 let (before, aligned, after) = unsafe {
119 bytes.align_to_mut::<u32>()
122 *byte = branchless_to_ascii_upper_case(*byte)
124 for word in aligned {
125 // FIXME: this is incorrect for some byte values:
126 // addition within a byte can carry/overflow into the next byte.
127 // Test case: b"\xFFz "
130 word.wrapping_add(0x1f1f1f1f) &
131 !word.wrapping_add(0x05050505) &
137 *byte = branchless_to_ascii_upper_case(*byte)
141 fn case08_fake_simd_u64(bytes: &mut [u8]) {
142 // SAFETY: transmuting a sequence of `u8` to `u64` is always fine
143 let (before, aligned, after) = unsafe {
144 bytes.align_to_mut::<u64>()
147 *byte = branchless_to_ascii_upper_case(*byte)
149 for word in aligned {
150 // FIXME: like above, this is incorrect for some byte values.
153 word.wrapping_add(0x1f1f1f1f_1f1f1f1f) &
154 !word.wrapping_add(0x05050505_05050505) &
160 *byte = branchless_to_ascii_upper_case(*byte)
164 fn case09_mask_mult_bool_branchy_lookup_table(bytes: &mut [u8]) {
165 fn is_ascii_lowercase(b: u8) -> bool {
166 if b >= 0x80 { return false }
167 match ASCII_CHARACTER_CLASS[b as usize] {
173 *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
177 fn case10_mask_mult_bool_lookup_table(bytes: &mut [u8]) {
178 fn is_ascii_lowercase(b: u8) -> bool {
179 match ASCII_CHARACTER_CLASS[b as usize] {
185 *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
189 fn case11_mask_mult_bool_match_range(bytes: &mut [u8]) {
190 fn is_ascii_lowercase(b: u8) -> bool {
197 *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
201 fn case12_mask_shifted_bool_match_range(bytes: &mut [u8]) {
202 fn is_ascii_lowercase(b: u8) -> bool {
209 *byte &= !((is_ascii_lowercase(*byte) as u8) * ASCII_CASE_MASK)
213 fn case13_subtract_shifted_bool_match_range(bytes: &mut [u8]) {
214 fn is_ascii_lowercase(b: u8) -> bool {
221 *byte -= (is_ascii_lowercase(*byte) as u8) * ASCII_CASE_MASK
225 fn case14_subtract_multiplied_bool_match_range(bytes: &mut [u8]) {
226 fn is_ascii_lowercase(b: u8) -> bool {
233 *byte -= (b'a' - b'A') * is_ascii_lowercase(*byte) as u8
243 is_ascii_alphanumeric,
246 is_ascii_punctuation,
252 macro_rules! repeat {
254 concat!($s, $s, $s, $s, $s, $s, $s, $s, $s, $s)
258 const SHORT: &str = "Alice's";
259 const MEDIUM: &str = "Alice's Adventures in Wonderland";
260 const LONG: &str = repeat!(
262 La Guida di Bragia, a Ballad Opera for the Marionette Theatre (around 1850)
263 Alice's Adventures in Wonderland (1865)
264 Phantasmagoria and Other Poems (1869)
265 Through the Looking-Glass, and What Alice Found There
266 (includes "Jabberwocky" and "The Walrus and the Carpenter") (1871)
267 The Hunting of the Snark (1876)
268 Rhyme? And Reason? (1883) – shares some contents with the 1869 collection,
269 including the long poem "Phantasmagoria"
270 A Tangled Tale (1885)
271 Sylvie and Bruno (1889)
272 Sylvie and Bruno Concluded (1893)
273 Pillow Problems (1893)
274 What the Tortoise Said to Achilles (1895)
275 Three Sunsets and Other Poems (1898)
276 The Manlet (1903)[106]
281 const ASCII_UPPERCASE_MAP: [u8; 256] = [
282 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
283 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
284 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
285 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
286 b' ', b'!', b'"', b'#', b'$', b'%', b'&', b'\'',
287 b'(', b')', b'*', b'+', b',', b'-', b'.', b'/',
288 b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7',
289 b'8', b'9', b':', b';', b'<', b'=', b'>', b'?',
290 b'@', b'A', b'B', b'C', b'D', b'E', b'F', b'G',
291 b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
292 b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
293 b'X', b'Y', b'Z', b'[', b'\\', b']', b'^', b'_',
296 b'A', b'B', b'C', b'D', b'E', b'F', b'G',
297 b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
298 b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
301 b'{', b'|', b'}', b'~', 0x7f,
302 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
303 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
304 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
305 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
306 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
307 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
308 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
309 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
310 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
311 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
312 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
313 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
314 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
315 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
316 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
317 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
320 enum AsciiCharacterClass {
322 Cw, // control whitespace
326 Lx, // lowercase hex digit
328 Ux, // uppercase hex digit
332 use self::AsciiCharacterClass::*;
335 static ASCII_CHARACTER_CLASS: [AsciiCharacterClass; 256] = [
336 // _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _a _b _c _d _e _f
337 C, C, C, C, C, C, C, C, C, Cw,Cw,C, Cw,Cw,C, C, // 0_
338 C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // 1_
339 W, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, // 2_
340 D, D, D, D, D, D, D, D, D, D, P, P, P, P, P, P, // 3_
341 P, Ux,Ux,Ux,Ux,Ux,Ux,U, U, U, U, U, U, U, U, U, // 4_
342 U, U, U, U, U, U, U, U, U, U, U, P, P, P, P, P, // 5_
343 P, Lx,Lx,Lx,Lx,Lx,Lx,L, L, L, L, L, L, L, L, L, // 6_
344 L, L, L, L, L, L, L, L, L, L, L, P, P, P, P, C, // 7_
345 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
346 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
347 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
348 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
349 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
350 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
351 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
352 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,