lib: bits - add circular rotation functions

lib: optimize nearest_power Instead of looping over each bit of a size_t, we can use a closed form expression.

lib/bits.h: Fix compiling with gcc 3.0 .. 3.3 According to gcc's online manuals, 3.4 is the first version with __builtin_clzll

lib: Add bits_is_power_of_two()

lib: Fixed bits_required64() with 32bit systems. Broken by 84f697c5e30565823619abaaeb57164c789d4b66.

lib: bits - GCC (and clang) provide bit-twiddle intrinsics, use them Signed-off-by: Phil Carmody <phil@dovecot.fi>

lib: bits - new fractional log-like helper For stats gathering, where the data can have a wide range of values, you don't necessarily need the same granularity along the full range of values. For example, 1ms and 11ms latencies are very different, but 1.001s and 1.011s latencies are not worth distinguishing. Something logarithmic seems more apt. Simply looking at power-of-2 sized bands (e.g. doing log2(n)), however, is too granular, so these new helpers let you specify how fine to (linearly) subdivide each of those bands. 1 fractional bit splits each power of 2 band into 2 halves. 2 fractional bits splits each power of 2 band into 4 quarters, and so on. 0 fractional bits is just log2(). Exact identification of percentiles is impossible, but it was anyway, as you simply cannot store all the data required to calculate them. However, a mere 896 buckets will permit you to have 32 bands per power of 2, 5 fracional bits. The above example would have buckets such as 2.432s-2.496s, and 55.3s-56.3s. Assuming smooth distribution lets you calculate percentiles more accurately, just assume within each bucket is a trapezial distribution. This holds even if the distribution is multi-modal, which it will be. However, maths required. Signed-off-by: Phil Carmody <phil@dovecot.fi>

lib: Removed unnecessary includes from bits.h All of them are already in lib.h, and bits.h gets included from lib.h. This also solves a compiling problem for systems where stdint.h doesn't exist.

lib: bits - improve bits_required to recurse downwards, not sideways Ooops. Signed-off-by: Phil Carmody <phil@dovecot.fi>

lib: bits - Add macro for '1 << i' It's used all over the place. It feels weird not having access to such a macro. Signed-off-by: Phil Carmody <phil@dovecot.fi>

lib: Added UINT64_SUM_OVERFLOWS() Maybe the unit tests are kind of unnecessary since the macro is so simple, but at least it's now a well tested simple macro :)

lib: bit twiddles bits_requiredXX() gives the number of bits required to store an unsigned integer. Here, XX is 8, 16, 32, 64, reperesenting the size of the operand. It belongs in the same file as nearest_power(), which makes most sense in a separate bit twiddles file. Universal enough to stay in lib.h by inclusion. Signed-off-by: Phil Carmody <phil@dovecot.fi>