/src/wireshark/wsutil/bits_count_ones.h
Line | Count | Source |
1 | | /** @file |
2 | | * |
3 | | * Wireshark - Network traffic analyzer |
4 | | * By Gerald Combs <gerald@wireshark.org> |
5 | | * Copyright 1998 Gerald Combs |
6 | | * |
7 | | * SPDX-License-Identifier: GPL-2.0-or-later |
8 | | */ |
9 | | |
10 | | #ifndef __WSUTIL_BITS_COUNT_ONES_H__ |
11 | | #define __WSUTIL_BITS_COUNT_ONES_H__ |
12 | | |
13 | | #include <inttypes.h> |
14 | | |
15 | | /* |
16 | | * The variable-precision SWAR algorithm is an interesting way to count |
17 | | * the number of bits set in an integer: |
18 | | * |
19 | | * https://www.playingwithpointers.com/blog/swar.html |
20 | | * |
21 | | * See |
22 | | * |
23 | | * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=36041 |
24 | | * https://danluu.com/assembly-intrinsics/ |
25 | | * |
26 | | * for discussions of various forms of population-counting code on x86. |
27 | | * |
28 | | * See |
29 | | * |
30 | | * https://docs.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64 |
31 | | * |
32 | | * for MSVC's population count intrinsics. |
33 | | * |
34 | | * Note that not all x86 processors support the POPCOUNT instruction. |
35 | | * |
36 | | * Other CPUs may have population count instructions as well. |
37 | | */ |
38 | | |
39 | | /** |
40 | | * @brief Count the number of set bits (ones) in a 64-bit integer. |
41 | | * |
42 | | * Uses a branchless, bitwise population count algorithm to compute the number |
43 | | * of bits set to 1 in the input value. This is also known as Hamming weight. |
44 | | * |
45 | | * The implementation is based on the "SWAR" (SIMD Within A Register) technique, |
46 | | * which performs parallel bit counting using masks and shifts. |
47 | | * |
48 | | * @param x 64-bit unsigned integer to evaluate. |
49 | | * @return Number of bits set to 1. |
50 | | */ |
51 | | static inline int |
52 | | ws_count_ones(const uint64_t x) |
53 | 14.2k | { |
54 | 14.2k | uint64_t bits = x; |
55 | | |
56 | 14.2k | bits = bits - ((bits >> 1) & UINT64_C(0x5555555555555555)); |
57 | 14.2k | bits = (bits & UINT64_C(0x3333333333333333)) + ((bits >> 2) & UINT64_C(0x3333333333333333)); |
58 | 14.2k | bits = (bits + (bits >> 4)) & UINT64_C(0x0F0F0F0F0F0F0F0F); |
59 | | |
60 | | return (int)((bits * UINT64_C(0x0101010101010101)) >> 56); |
61 | 14.2k | } Line | Count | Source | 53 | 14.2k | { | 54 | 14.2k | uint64_t bits = x; | 55 | | | 56 | 14.2k | bits = bits - ((bits >> 1) & UINT64_C(0x5555555555555555)); | 57 | 14.2k | bits = (bits & UINT64_C(0x3333333333333333)) + ((bits >> 2) & UINT64_C(0x3333333333333333)); | 58 | 14.2k | bits = (bits + (bits >> 4)) & UINT64_C(0x0F0F0F0F0F0F0F0F); | 59 | | | 60 | | return (int)((bits * UINT64_C(0x0101010101010101)) >> 56); | 61 | 14.2k | } |
Unexecuted instantiation: ftype-ipv4.c:ws_count_ones Unexecuted instantiation: packet-dvb-s2-bb.c:ws_count_ones Unexecuted instantiation: packet-iso15765.c:ws_count_ones Unexecuted instantiation: packet-x11.c:ws_count_ones |
62 | | |
63 | | #endif /* __WSUTIL_BITS_COUNT_ONES_H__ */ |