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 builtin = @import("builtin");
10const std = @import("std");
11const common = @import("common.zig");
12
13pub const panic = common.panic;
14
15comptime {
16    @export(&__popcountsi2, .{ .name = "__popcountsi2", .linkage = common.linkage, .visibility = common.visibility });
17    @export(&__popcountdi2, .{ .name = "__popcountdi2", .linkage = common.linkage, .visibility = common.visibility });
18    @export(&__popcountti2, .{ .name = "__popcountti2", .linkage = common.linkage, .visibility = common.visibility });
19}
20
21pub fn __popcountsi2(a: i32) callconv(.c) i32 {
22    return popcountXi2(i32, a);
23}
24
25pub fn __popcountdi2(a: i64) callconv(.c) i32 {
26    return popcountXi2(i64, a);
27}
28
29pub fn __popcountti2(a: i128) callconv(.c) i32 {
30    return popcountXi2(i128, a);
31}
32
33inline fn popcountXi2(comptime ST: type, a: ST) i32 {
34    const UT = switch (ST) {
35        i32 => u32,
36        i64 => u64,
37        i128 => u128,
38        else => unreachable,
39    };
40    var x: UT = @bitCast(a);
41    x -= (x >> 1) & (~@as(UT, 0) / 3); // 0x55...55, aggregate duos
42    x = ((x >> 2) & (~@as(UT, 0) / 5)) // 0x33...33, aggregate nibbles
43        + (x & (~@as(UT, 0) / 5));
44    x += x >> 4;
45    x &= ~@as(UT, 0) / 17; // 0x0F...0F, aggregate bytes
46    // 8 most significant bits of x + (x<<8) + (x<<16) + ..
47    x *%= ~@as(UT, 0) / 255; // 0x01...01
48    x >>= (@bitSizeOf(ST) - 8);
49    return @intCast(x);
50}
51
52test {
53    _ = @import("popcountsi2_test.zig");
54    _ = @import("popcountdi2_test.zig");
55    _ = @import("popcountti2_test.zig");
56}