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[..];
70 fn case00_alloc_only(_bytes: &mut [u8]) {}
72 fn case01_black_box_read_each_byte(bytes: &mut [u8]) {
78 fn case02_lookup_table(bytes: &mut [u8]) {
80 *byte = ASCII_UPPERCASE_MAP[*byte as usize]
84 fn case03_branch_and_subtract(bytes: &mut [u8]) {
86 *byte = if b'a' <= *byte && *byte <= b'z' {
94 fn case04_branch_and_mask(bytes: &mut [u8]) {
96 *byte = if b'a' <= *byte && *byte <= b'z' {
104 fn case05_branchless(bytes: &mut [u8]) {
106 *byte = branchless_to_ascii_upper_case(*byte)
110 fn case06_libcore(bytes: &mut [u8]) {
111 bytes.make_ascii_uppercase()
114 fn case07_fake_simd_u32(bytes: &mut [u8]) {
115 // SAFETY: transmuting a sequence of `u8` to `u32` is always fine
116 let (before, aligned, after) = unsafe {
117 bytes.align_to_mut::<u32>()
120 *byte = branchless_to_ascii_upper_case(*byte)
122 for word in aligned {
123 // FIXME: this is incorrect for some byte values:
124 // addition within a byte can carry/overflow into the next byte.
125 // Test case: b"\xFFz "
128 word.wrapping_add(0x1f1f1f1f) &
129 !word.wrapping_add(0x05050505) &
135 *byte = branchless_to_ascii_upper_case(*byte)
139 fn case08_fake_simd_u64(bytes: &mut [u8]) {
140 // SAFETY: transmuting a sequence of `u8` to `u64` is always fine
141 let (before, aligned, after) = unsafe {
142 bytes.align_to_mut::<u64>()
145 *byte = branchless_to_ascii_upper_case(*byte)
147 for word in aligned {
148 // FIXME: like above, this is incorrect for some byte values.
151 word.wrapping_add(0x1f1f1f1f_1f1f1f1f) &
152 !word.wrapping_add(0x05050505_05050505) &
158 *byte = branchless_to_ascii_upper_case(*byte)
162 fn case09_mask_mult_bool_branchy_lookup_table(bytes: &mut [u8]) {
163 fn is_ascii_lowercase(b: u8) -> bool {
164 if b >= 0x80 { return false }
165 match ASCII_CHARACTER_CLASS[b as usize] {
171 *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
175 fn case10_mask_mult_bool_lookup_table(bytes: &mut [u8]) {
176 fn is_ascii_lowercase(b: u8) -> bool {
177 match ASCII_CHARACTER_CLASS[b as usize] {
183 *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
187 fn case11_mask_mult_bool_match_range(bytes: &mut [u8]) {
188 fn is_ascii_lowercase(b: u8) -> bool {
195 *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
199 fn case12_mask_shifted_bool_match_range(bytes: &mut [u8]) {
200 fn is_ascii_lowercase(b: u8) -> bool {
207 *byte &= !((is_ascii_lowercase(*byte) as u8) << 5)
211 fn case13_subtract_shifted_bool_match_range(bytes: &mut [u8]) {
212 fn is_ascii_lowercase(b: u8) -> bool {
219 *byte -= (is_ascii_lowercase(*byte) as u8) << 5
223 fn case14_subtract_multiplied_bool_match_range(bytes: &mut [u8]) {
224 fn is_ascii_lowercase(b: u8) -> bool {
231 *byte -= (b'a' - b'A') * is_ascii_lowercase(*byte) as u8
241 is_ascii_alphanumeric,
244 is_ascii_punctuation,
250 macro_rules! repeat {
252 concat!($s, $s, $s, $s, $s, $s, $s, $s, $s, $s)
256 const SHORT: &str = "Alice's";
257 const MEDIUM: &str = "Alice's Adventures in Wonderland";
258 const LONG: &str = repeat!(
260 La Guida di Bragia, a Ballad Opera for the Marionette Theatre (around 1850)
261 Alice's Adventures in Wonderland (1865)
262 Phantasmagoria and Other Poems (1869)
263 Through the Looking-Glass, and What Alice Found There
264 (includes "Jabberwocky" and "The Walrus and the Carpenter") (1871)
265 The Hunting of the Snark (1876)
266 Rhyme? And Reason? (1883) – shares some contents with the 1869 collection,
267 including the long poem "Phantasmagoria"
268 A Tangled Tale (1885)
269 Sylvie and Bruno (1889)
270 Sylvie and Bruno Concluded (1893)
271 Pillow Problems (1893)
272 What the Tortoise Said to Achilles (1895)
273 Three Sunsets and Other Poems (1898)
274 The Manlet (1903)[106]
279 const ASCII_UPPERCASE_MAP: [u8; 256] = [
280 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
281 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
282 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
283 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
284 b' ', b'!', b'"', b'#', b'$', b'%', b'&', b'\'',
285 b'(', b')', b'*', b'+', b',', b'-', b'.', b'/',
286 b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7',
287 b'8', b'9', b':', b';', b'<', b'=', b'>', b'?',
288 b'@', b'A', b'B', b'C', b'D', b'E', b'F', b'G',
289 b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
290 b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
291 b'X', b'Y', b'Z', b'[', b'\\', b']', b'^', b'_',
294 b'A', b'B', b'C', b'D', b'E', b'F', b'G',
295 b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
296 b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
299 b'{', b'|', b'}', b'~', 0x7f,
300 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
301 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
302 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
303 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
304 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
305 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
306 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
307 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
308 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
309 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
310 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
311 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
312 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
313 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
314 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
315 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
318 enum AsciiCharacterClass {
320 Cw, // control whitespace
324 Lx, // lowercase hex digit
326 Ux, // uppercase hex digit
330 use self::AsciiCharacterClass::*;
333 static ASCII_CHARACTER_CLASS: [AsciiCharacterClass; 256] = [
334 // _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _a _b _c _d _e _f
335 C, C, C, C, C, C, C, C, C, Cw,Cw,C, Cw,Cw,C, C, // 0_
336 C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // 1_
337 W, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, // 2_
338 D, D, D, D, D, D, D, D, D, D, P, P, P, P, P, P, // 3_
339 P, Ux,Ux,Ux,Ux,Ux,Ux,U, U, U, U, U, U, U, U, U, // 4_
340 U, U, U, U, U, U, U, U, U, U, U, P, P, P, P, P, // 5_
341 P, Lx,Lx,Lx,Lx,Lx,Lx,L, L, L, L, L, L, L, L, L, // 6_
342 L, L, L, L, L, L, L, L, L, L, L, P, P, P, P, C, // 7_
343 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
344 N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
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,