- Commit
- 46ecec1b5d2e556691a8154018988c1ae2916d84
- Parent
- fac8f2af7c7d1fba3ffe9bd34343c6c0fa492ecd
- Author
- Pablo <pablo-pie@riseup.net>
- Date
[escape] Use AVX2 instead of SSE for SIMD escaping
Custum build of stapix for tikz.pablopie.xyz
[escape] Use AVX2 instead of SSE for SIMD escaping
1 files changed, 65 insertions, 54 deletions
| Status | Name | Changes | Insertions | Deletions |
| Modified | src/escape.rs | 2 files changed | 65 | 54 |
diff --git a/src/escape.rs b/src/escape.rs @@ -1,7 +1,8 @@ +#![allow(unsafe_op_in_unsafe_fn)] //! HTML Escaping //! //! Stolen from pulldown-cmark-escape -//! <https://github.com/pulldown-cmark/pulldown-cmark/> +//! <github.com/pulldown-cmark/pulldown-cmark/> use std::fmt::{self, Display}; @@ -23,9 +24,9 @@ pub struct Escaped<'a>(pub &'a str); impl Display for Escaped<'_> { #[cfg(target_arch = "x86_64")] fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - // the SIMD accelerated code uses the PSHUFB instruction, which is part - // of the SSSE3 instruction set - if is_x86_feature_detected!("ssse3") { + // the SIMD accelerated code uses PSHUFB with AVX2, which allows processing + // 32 bytes at a time + if is_x86_feature_detected!("avx2") { simd::fmt_escaped_html(self.0, f) } else { fmt_escaped_html_scalar(self.0, f) @@ -73,14 +74,14 @@ fn fmt_escaped_html_scalar( mod simd { use std::{arch::x86_64::*, mem, fmt}; - const VECTOR_SIZE: usize = mem::size_of::<__m128i>(); + const VECTOR_SIZE: usize = mem::size_of::<__m256i>(); #[inline] pub fn fmt_escaped_html(s: &str, f: &mut fmt::Formatter<'_>) -> fmt::Result { - // the strategy here is to walk s in chunks of VECTOR_SIZE (16) bytes at + // the strategy here is to walk s in chunks of VECTOR_SIZE (32) bytes at // a time: // - // 1. for each chunk, we compute a a bitmask indicating whether the + // 1. for each chunk, we compute a bitmask indicating whether the // corresponding byte is a HTML special byte // 2. for each bit set in this mask, we print the escaped character // accordingly, as well as the surrounding characters that don't need @@ -97,35 +98,16 @@ mod simd { let mut mark = 0; let mut offset = 0; - unsafe { - let upperbound = bytes.len() - VECTOR_SIZE; - while offset < upperbound { - let mut mask = compute_mask(bytes, offset); - - while mask != 0 { - let first_special = mask.trailing_zeros(); - let i = offset + first_special as usize; - let c = *bytes.get_unchecked(i) as usize; - - // here we know c = s[i] is a character that should be escaped, - // so it is safe to unwrap ESCAPE_TABLE[c] - let escape_seq = super::ESCAPE_TABLE[c].unwrap(); - f.write_str(s.get_unchecked(mark..i))?; - f.write_str(escape_seq)?; - - mark = i + 1; // all escaped characters are ASCII - mask ^= mask & -mask; - } - - offset += VECTOR_SIZE; - } - - // ====================================================================== - // final iteration: we align the read with the end of the slice - // and shift off the bytes at start we have already scanned - let mut mask = compute_mask(bytes, upperbound); - mask >>= offset - upperbound; - + #[inline] + unsafe fn process_mask( + mask: u32, + offset: usize, + mark: &mut usize, + s: &str, + bytes: &[u8], + f: &mut fmt::Formatter<'_>, + ) -> fmt::Result { + let mut mask = mask as i32; while mask != 0 { let first_special = mask.trailing_zeros(); let i = offset + first_special as usize; @@ -134,46 +116,75 @@ mod simd { // here we know c = s[i] is a character that should be escaped, // so it is safe to unwrap ESCAPE_TABLE[c] let escape_seq = super::ESCAPE_TABLE[c].unwrap(); - f.write_str(s.get_unchecked(mark..i))?; + // NOTE: str::get_unchecked operates on the level of raw bytes instead + // of unicode code points, so it is safe to call it like so + f.write_str(s.get_unchecked(*mark..i))?; f.write_str(escape_seq)?; - mark = i + 1; // all escaped characters are ASCII + *mark = i + 1; // all escaped characters are ASCII mask ^= mask & -mask; } + Ok(()) + } + + unsafe { + let upperbound = bytes.len() - VECTOR_SIZE; + while offset < upperbound { + let mask = compute_mask(bytes, offset); + process_mask(mask, offset, &mut mark, s, bytes, f)?; + + offset += VECTOR_SIZE; + } + + // ====================================================================== + // final iteration: we align the read with the end of the slice + // and shift off the bytes at start we have already scanned + let mut mask = compute_mask(bytes, upperbound); + mask >>= offset - upperbound; + process_mask(mask, offset, &mut mark, s, bytes, f)?; + // NOTE: str::get_unchecked operates on the level of raw bytes instead + // of unicode code points, so it is safe to call it like so f.write_str(s.get_unchecked(mark..)) } } #[inline] - #[target_feature(enable = "ssse3")] - /// Computes a byte mask at given offset in the byte buffer. Its first 16 + #[target_feature(enable = "avx2")] + /// Computes a byte mask at given offset in the byte buffer. Its first 32 /// (least significant) bits correspond to whether there is an HTML special /// byte at the first VECTOR_SIZE bytes `bytes[offset..]`. /// /// It is only safe to call this function when `bytes.len() >= offset + /// VECTOR_SIZE`. - unsafe fn compute_mask(bytes: &[u8], offset: usize) -> i32 { + unsafe fn compute_mask(bytes: &[u8], offset: usize) -> u32 { debug_assert!(bytes.len() >= offset + VECTOR_SIZE); const LOOKUP_TABLE: [u8; VECTOR_SIZE] = create_lookup(); const fn create_lookup() -> [u8; VECTOR_SIZE] { + const _: () = assert!(2 * 16 == VECTOR_SIZE); let mut table = [0; VECTOR_SIZE]; - table[(b'<' & 0x0f) as usize] = b'<'; - table[(b'>' & 0x0f) as usize] = b'>'; - table[(b'&' & 0x0f) as usize] = b'&'; - table[(b'"' & 0x0f) as usize] = b'"'; - table[(b'\'' & 0x0f) as usize] = b'\''; - table[0] = 0b01111111; + table[(b'<' & 0x0f) as usize] = b'<'; + table[(b'>' & 0x0f) as usize] = b'>'; + table[(b'&' & 0x0f) as usize] = b'&'; + table[(b'"' & 0x0f) as usize] = b'"'; + table[(b'\'' & 0x0f) as usize] = b'\''; + table[0] = 0b01111111; + table[(b'<' & 0x0f) as usize + 16] = b'<'; + table[(b'>' & 0x0f) as usize + 16] = b'>'; + table[(b'&' & 0x0f) as usize + 16] = b'&'; + table[(b'"' & 0x0f) as usize + 16] = b'"'; + table[(b'\'' & 0x0f) as usize + 16] = b'\''; + table[16] = 0b01111111; table } - let lookup_table = _mm_loadu_si128( - LOOKUP_TABLE.as_ptr() as *const __m128i + let lookup_table = _mm256_loadu_si256( + LOOKUP_TABLE.as_ptr() as *const __m256i ); - let raw_ptr = bytes.as_ptr().add(offset) as *const __m128i; - let vector = _mm_loadu_si128(raw_ptr); + let raw_ptr = bytes.as_ptr().add(offset) as *const __m256i; + let vector = _mm256_loadu_si256(raw_ptr); // mask the vector using the lookup table: // @@ -182,17 +193,17 @@ mod simd { // 2. bytes whose lower nibbles are nonzero and *not* special HTML // characters get mapped to 0 // 3. bytes whose lower nibbles are 0 get mapped to 0b01111111 - let masked = _mm_shuffle_epi8(lookup_table, vector); + let masked = _mm256_shuffle_epi8(lookup_table, vector); // compare the original vector to the masked one: // // 1. bytes that shared a lower nibble with an HTML special byte match // *only* if they are that special byte // 2. all other bytes will never match - let matches = _mm_cmpeq_epi8(masked, vector); + let matches = _mm256_cmpeq_epi8(masked, vector); // translate matches to a bitmask: every 1 corresponds to a HTML // special character and a 0 is a non-HTML byte - _mm_movemask_epi8(matches) + i32::cast_unsigned(_mm256_movemask_epi8(matches)) } }