1 /* ===-- popcountti2.c - Implement __popcountti2 ----------------------------===
3 * The LLVM Compiler Infrastructure
5 * This file is dual licensed under the MIT and the University of Illinois Open
6 * Source Licenses. See LICENSE.TXT for details.
8 * ===----------------------------------------------------------------------===
10 * This file implements __popcountti2 for the compiler_rt library.
12 * ===----------------------------------------------------------------------===
19 /* Returns: count of 1 bits */
22 __popcountti2(ti_int a
)
24 tu_int x3
= (tu_int
)a
;
25 x3
= x3
- ((x3
>> 1) & (((tu_int
)0x5555555555555555uLL
<< 64) |
26 0x5555555555555555uLL
));
27 /* Every 2 bits holds the sum of every pair of bits (64) */
28 x3
= ((x3
>> 2) & (((tu_int
)0x3333333333333333uLL
<< 64) | 0x3333333333333333uLL
))
29 + (x3
& (((tu_int
)0x3333333333333333uLL
<< 64) | 0x3333333333333333uLL
));
30 /* Every 4 bits holds the sum of every 4-set of bits (3 significant bits) (32) */
32 & (((tu_int
)0x0F0F0F0F0F0F0F0FuLL
<< 64) | 0x0F0F0F0F0F0F0F0FuLL
);
33 /* Every 8 bits holds the sum of every 8-set of bits (4 significant bits) (16) */
34 du_int x2
= (du_int
)(x3
+ (x3
>> 64));
35 /* Every 8 bits holds the sum of every 8-set of bits (5 significant bits) (8) */
36 su_int x
= (su_int
)(x2
+ (x2
>> 32));
37 /* Every 8 bits holds the sum of every 8-set of bits (6 significant bits) (4) */
39 /* Every 8 bits holds the sum of every 8-set of bits (7 significant bits) (2) */
40 /* Upper 16 bits are garbage */
41 return (x
+ (x
>> 8)) & 0xFF; /* (8 significant bits) */