Compiler Explorer

Source code

fn u32_into_nib_le(x: u32) -> [u8; 8] {
	let [b0, b1, b2, b3] = x.to_le_bytes();
	[
		b0 & 0x0f,
		(b0 >> 4) & 0x0f,
		b1 & 0x0f,
		(b1 >> 4) & 0x0f,
		b2 & 0x0f,
		(b2 >> 4) & 0x0f,
		b3 & 0x0f,
		(b3 >> 4) & 0x0f,
	]
}

pub fn u32_sum_nibs_ref(x: u32) -> u32 {
	IntoIterator::into_iter(u32_into_nib_le(x))
		.map(|x| x as u32)
		.sum()
}

// this implementation is just a truncated popcnt/count_ones.
// it's truncated in that we skip horizontal summing the bits and
// half-nibbles and just dive right into horizontal summing the
// nibbles.
//
// visually:
//
//   x  AAAA BBBB CCCC DDDD EEEE FFFF GGGG HHHH
//   y  000A BABA 000C DCDC 000E FEFE 000G HGHG  (1.)
//   z  0000 0000 00AB CDAB 0000 0000 00EF GHEF  (2.)
//   w  0000 0000 0000 0000 0000 0000 0ABC DEFG  (3.)
//
// (1.) note that any horizontal sum AAAA + BBBB will fill at most
//      _5_ bits. (log2(16 + 16) == 5)
// (2.) each will fill at most _6_ bits. (log2(32 + 32) == 6)
// (3.) the result will fill at most _7_ bits. (log2(64 + 64) == 7)
pub fn u32_sum_nibs_simple(x: u32) -> u32 {
    const NIBS_0246: u32 = 0x0f0f_0f0f;
    const NIBS_0145: u32 = 0x00ff_00ff;
    const NIBS_0123: u32 = 0x0000_ffff;

// like taking each individual byte and replacing it with the sum
	// of its hi and lo nibbles.
    let y = (x & NIBS_0246) + ((x >> 4) & NIBS_0246);
	// for each individual half-word, replace it with the sum of its
	// hi and lo bytes.
	let z = (y & NIBS_0145) + ((y >> 8) & NIBS_0145);
	// our result is then the sum of the remaining hi and lo
	// half-words!
    let w = (z & NIBS_0123) + ((z >> 16) & NIBS_0123);

w
}

pub fn u32_sum_nibs(x: u32) -> u32 {
	const NIBS_0246: u32 = 0x0f0f_0f0f;
	
    let y = (x & NIBS_0246) + ((x >> 4) & NIBS_0246);
	
	y.wrapping_mul(0x0101_0101) >> 24
}