pub fn altmap_size(words: usize) -> usize {
assert!(
words.is_multiple_of(16),
"altmap_size: words ({words}) must be a multiple of 16"
);
words * 2
}
pub fn to_altmap(src: &[u16], dst: &mut [u8]) {
let n = src.len();
assert!(
n.is_multiple_of(16),
"to_altmap: src length ({n}) must be a multiple of 16"
);
assert_eq!(
dst.len(),
n * 2,
"to_altmap: dst must be {} bytes, got {}",
n * 2,
dst.len()
);
#[cfg(target_arch = "x86_64")]
if std::is_x86_feature_detected!("sse2") {
unsafe { to_altmap_sse2(src, dst) };
return;
}
to_altmap_scalar(src, dst);
}
pub fn from_altmap(src: &[u8], dst: &mut [u16]) {
let n = dst.len();
assert!(
n.is_multiple_of(16),
"from_altmap: dst length ({n}) must be a multiple of 16"
);
assert_eq!(
src.len(),
n * 2,
"from_altmap: src must be {} bytes, got {}",
n * 2,
src.len()
);
from_altmap_scalar(src, dst);
}
fn to_altmap_scalar(src: &[u16], dst: &mut [u8]) {
let n = src.len();
let plane_bytes = n / 8;
for (g, chunk) in src.as_chunks::<16>().0.iter().enumerate() {
let byte_off = g * 2; for k in 0u32..16 {
let mut bits: u16 = 0;
for (i, &w) in chunk.iter().enumerate() {
if (w >> k) & 1 == 1 {
bits |= 1 << i;
}
}
let off = k as usize * plane_bytes + byte_off;
dst[off..off + 2].copy_from_slice(&bits.to_le_bytes());
}
}
}
fn from_altmap_scalar(src: &[u8], dst: &mut [u16]) {
let n = dst.len();
let plane_bytes = n / 8;
for g in 0..n / 16 {
let byte_off = g * 2;
for i in 0..16usize {
let mut word: u16 = 0;
for k in 0..16u32 {
let off = k as usize * plane_bytes + byte_off;
let bits = u16::from_le_bytes([src[off], src[off + 1]]);
if (bits >> i) & 1 == 1 {
word |= 1 << k;
}
}
dst[g * 16 + i] = word;
}
}
}
#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "sse2")]
unsafe fn to_altmap_sse2(src: &[u16], dst: &mut [u8]) {
#[allow(unused_imports)]
use std::arch::x86_64::*;
let n = src.len();
let plane_bytes = n / 8;
let masks: [__m128i; 8] = std::array::from_fn(|k| _mm_set1_epi8((1u8 << k) as i8));
let lo_mask = _mm_set1_epi16(0x00FF_u16 as i16);
for (g, chunk) in src.as_chunks::<16>().0.iter().enumerate() {
let byte_off = g * 2;
let ptr = chunk.as_ptr();
let v0 = _mm_loadu_si128(ptr as *const __m128i);
let v1 = _mm_loadu_si128(ptr.add(8) as *const __m128i);
let lo = _mm_packus_epi16(_mm_and_si128(v0, lo_mask), _mm_and_si128(v1, lo_mask));
let hi = _mm_packus_epi16(_mm_srli_epi16(v0, 8), _mm_srli_epi16(v1, 8));
for (k, &m) in masks.iter().enumerate() {
let lo_bits = _mm_movemask_epi8(_mm_cmpeq_epi8(_mm_and_si128(lo, m), m)) as u16;
let off_lo = k * plane_bytes + byte_off;
let lo_bytes = lo_bits.to_le_bytes();
dst[off_lo] = lo_bytes[0];
dst[off_lo + 1] = lo_bytes[1];
let hi_bits = _mm_movemask_epi8(_mm_cmpeq_epi8(_mm_and_si128(hi, m), m)) as u16;
let off_hi = (k + 8) * plane_bytes + byte_off;
let hi_bytes = hi_bits.to_le_bytes();
dst[off_hi] = hi_bytes[0];
dst[off_hi + 1] = hi_bytes[1];
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn round_trip(words: &[u16]) {
let n = words.len();
let mut altmap = vec![0u8; altmap_size(n)];
let mut recovered = vec![0u16; n];
to_altmap(words, &mut altmap);
from_altmap(&altmap, &mut recovered);
assert_eq!(recovered, words, "round-trip failed for {} words", n);
}
#[test]
fn round_trip_all_zeros() {
round_trip(&[0u16; 16]);
round_trip(&[0u16; 64]);
}
#[test]
fn round_trip_all_ones() {
round_trip(&[0xFFFF_u16; 16]);
round_trip(&[0xFFFF_u16; 256]);
}
#[test]
fn round_trip_single_bit_words() {
let words: Vec<u16> = (0..64).map(|i| 1u16 << (i % 16)).collect();
round_trip(&words);
}
#[test]
fn round_trip_incrementing() {
let words: Vec<u16> = (0..256).map(|i| i as u16).collect();
round_trip(&words);
}
#[test]
fn round_trip_random_512_words() {
let mut lcg: u64 = 0xDEAD_BEEF_1234_5678;
let words: Vec<u16> = (0..512)
.map(|_| {
lcg = lcg
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(lcg >> 48) as u16
})
.collect();
round_trip(&words);
}
#[test]
#[allow(unreachable_code)]
fn scalar_and_simd_produce_identical_output() {
#[cfg(not(target_arch = "x86_64"))]
return;
let mut lcg: u64 = 0xCAFEBABE_DEADBEEF;
let words: Vec<u16> = (0..256)
.map(|_| {
lcg = lcg
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(lcg >> 48) as u16
})
.collect();
let mut out_scalar = vec![0u8; altmap_size(words.len())];
let mut out_simd = vec![0u8; altmap_size(words.len())];
to_altmap_scalar(&words, &mut out_scalar);
to_altmap(&words, &mut out_simd);
assert_eq!(out_scalar, out_simd, "scalar and SIMD outputs differ");
}
#[test]
fn plane_layout_is_correct() {
let words: Vec<u16> = (0..16).map(|i| 1u16 << i).collect();
let mut altmap = vec![0u8; altmap_size(words.len())];
to_altmap(&words, &mut altmap);
let plane_bytes = words.len() / 8; for k in 0..16usize {
let off = k * plane_bytes;
let bits = u16::from_le_bytes([altmap[off], altmap[off + 1]]);
assert_eq!(
bits,
1 << k,
"plane {k}: expected {:#06x}, got {:#06x}",
1u16 << k,
bits
);
}
}
}