1//! popcount - population count
2//! counts the number of 1 bits
3//! SWAR-Popcount: count bits of duos, aggregate to nibbles, and bytes inside
4//! x-bit register in parallel to sum up all bytes
5//! SWAR-Masks and factors can be defined as 2-adic fractions
6//! TAOCP: Combinational Algorithms, Bitwise Tricks And Techniques,
7//! subsubsection "Working with the rightmost bits" and "Sideways addition".
8
9const compiler_rt = @import("../compiler_rt.zig");
10const symbol = compiler_rt.symbol;
11
12comptime {
13 symbol(&__popcountsi2, "__popcountsi2");
14 symbol(&__popcountdi2, "__popcountdi2");
15 symbol(&__popcountti2, "__popcountti2");
16}
17
18pub fn __popcountsi2(a: i32) callconv(.c) i32 {
19 return popcountXi2(i32, a);
20}
21
22pub fn __popcountdi2(a: i64) callconv(.c) i32 {
23 return popcountXi2(i64, a);
24}
25
26pub fn __popcountti2(a: i128) callconv(.c) i32 {
27 return popcountXi2(i128, a);
28}
29
30inline fn popcountXi2(comptime ST: type, a: ST) i32 {
31 const UT = switch (ST) {
32 i32 => u32,
33 i64 => u64,
34 i128 => u128,
35 else => unreachable,
36 };
37 var x: UT = @bitCast(a);
38 x -= (x >> 1) & (~@as(UT, 0) / 3); // 0x55...55, aggregate duos
39 x = ((x >> 2) & (~@as(UT, 0) / 5)) // 0x33...33, aggregate nibbles
40 + (x & (~@as(UT, 0) / 5));
41 x += x >> 4;
42 x &= ~@as(UT, 0) / 17; // 0x0F...0F, aggregate bytes
43 // 8 most significant bits of x + (x<<8) + (x<<16) + ..
44 x *%= ~@as(UT, 0) / 255; // 0x01...01
45 x >>= (@bitSizeOf(ST) - 8);
46 return @intCast(x);
47}
48
49test {
50 _ = @import("popcountsi2_test.zig");
51 _ = @import("popcountdi2_test.zig");
52 _ = @import("popcountti2_test.zig");
53}