1/*
2 * Copyright (c) 2003-2005 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;

--- 164 unchanged lines hidden (view full) ---

173 if (!bits(val, 15,0)) { lsb += 16; val >>= 16; }
174 if (!bits(val, 7,0)) { lsb += 8; val >>= 8; }
175 if (!bits(val, 3,0)) { lsb += 4; val >>= 4; }
176 if (!bits(val, 1,0)) { lsb += 2; val >>= 2; }
177 if (!bits(val, 0,0)) { lsb += 1; }
178 return lsb;
179}
180
181/**
182 * Checks if a number is a power of two, or zero.
183 */
184template <class T>
185inline bool
186isPow2(T v) {
187 return (v & (v - 1)) == (T)0;
188}
189
190/**
191 * Returns the number of set ones in the provided value.
192 * PD algorithm from
193 * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
194 */
195inline int
196popCount(uint64_t val) {
197#ifndef __has_builtin
198 #define __has_builtin(foo) 0
199#endif
200#if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl))
201 return __builtin_popcountl(val);
202#else
203 const uint64_t m1 = 0x5555555555555555; // ..010101b
204 const uint64_t m2 = 0x3333333333333333; // ..110011b
205 const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // ..001111b
206 const uint64_t sum = 0x0101010101010101;
207
208 val -= (val >> 1) & m1; // 2 bits count -> 2 bits
209 val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits
210 val = (val + (val >> 4)) & m4; // 8 bits count -> 8 bits
211 return (val * sum) >> 56; // horizontal sum
212#endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl))
213}
214#endif // __BASE_BITFIELD_HH__