3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody#ifndef BITS_H
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody#define BITS_H
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen#define UINT64_SUM_OVERFLOWS(a, b) \
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen (a > (uint64_t)-1 - b)
cbc01fc844fa307e565cc81fd78536d7afca05a9Timo Sirainen
db10156822c596c5e953b0ce9b10fc3732030ba8Phil Carmody#define BIT(n) (1u << (n))
db10156822c596c5e953b0ce9b10fc3732030ba8Phil Carmody
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek/* Returns x, such that x is the smallest power of 2 >= num. */
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodysize_t nearest_power(size_t num) ATTR_CONST;
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen/* Returns TRUE if 2^x=num, i.e. if num has only a single bit set to 1. */
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainenstatic inline bool ATTR_CONST
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainenbits_is_power_of_two(uint64_t num)
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen{
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen return num > 0 && (num & (num - 1)) == 0;
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen}
d6e496a8bdb887a49112250e781f219d91fee117Timo Sirainen
33c05298ab11c13b409da265a6bf2f745196156fTimo Sirainen#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodystatic inline unsigned int ATTR_CONST
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodybits_required32(uint32_t num)
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody{
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody return num == 0 ? 0 : 32 - __builtin_clz(num);
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody}
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodystatic inline unsigned int ATTR_CONST
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodybits_required8(uint8_t num) { return bits_required32(num); }
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodystatic inline unsigned int ATTR_CONST
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodybits_required16(uint16_t num) { return bits_required32(num); }
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodystatic inline unsigned int ATTR_CONST
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmodybits_required64(uint64_t num)
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody{
9e9711ebed27c8efeece02d57cf91bb00f10015cTimo Sirainen return num == 0 ? 0 : 64 - __builtin_clzll(num);
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody}
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody#else
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodyunsigned int bits_required8(uint8_t num) ATTR_CONST;
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodystatic inline
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodyunsigned int bits_required16(uint16_t num)
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody{
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody return (num <= 0xff) ? bits_required8(num)
62684181bd6a426052af1e3e6c7ec73fb51eb7ffPhil Carmody : 8 + bits_required8(num >> 8);
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody}
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodystatic inline
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodyunsigned int bits_required32(uint32_t num)
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody{
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody return (num <= 0xffff) ? bits_required16(num)
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody : 16 + bits_required16(num >> 16);
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody}
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodystatic inline
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodyunsigned int bits_required64(uint64_t num)
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody{
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody return (num <= 0xffffffff) ? bits_required32(num)
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody : 32 + bits_required32(num >> 32);
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody}
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody#endif
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic inline uint64_t
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomibits_rotl64(uint64_t num, unsigned int count)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi count &= mask;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi return (num << count) | (num >> (-count & mask));
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic inline uint32_t
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomibits_rotl32(uint32_t num, unsigned int count)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi count &= mask;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi return (num << count) | (num >> (-count & mask));
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic inline uint64_t
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomibits_rotr64(uint64_t num, unsigned int count)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi count &= mask;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi return (num >> count) | (num << (-count & mask));
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomistatic inline uint32_t
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomibits_rotr32(uint32_t num, unsigned int count)
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi{
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi count &= mask;
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi return (num >> count) | (num << (-count & mask));
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi}
f1577719e3bed5fd814788642f165f1d3d699636Aki Tuomi
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody/* These functions look too big to be inline, but in almost all expected
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody uses, 'fracbits' will be a compile-time constant, and most of the
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody expressions will simplify greatly.
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody*/
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody/* Perform a piecewise-linear approximation to a log2, with fracbits "fractional" bits.
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody Best explained with examples:
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody With 2 fractional bits splitting each power of 2 into 4 bands:
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody 00, 01, 10, 11 -> 00, 01, 10, 11 (small corner cases)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody 100, 101, 110, 111 -> 100, 101, 110, 111 ([4-8) split into 4 bands)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody 1000, 1001, 1010, 1011 -> 1000, 1000, 1001, 1001 ([8-15) split ...
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody 1100, 1101, 1110, 1111 -> 1010, 1010, 1011, 1011 ... into 4 bands)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody [16..31) -> 11bb
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody [32..63) -> 100bb
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody [64..127) -> 101bb
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody [128..255) -> 110bb
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody e.g. 236 = 11101100 -> ((8-2)<<2 == 11000) + (111.....>> 5 == 111) - 100 == 11011
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody */
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmodystatic inline unsigned int ATTR_CONST
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmodybits_fraclog(unsigned int val, unsigned int fracbits)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody{
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned bits = bits_required32(val);
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody if (bits <= fracbits + 1)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return val;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int bandnum = bits - fracbits;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int bandstart = bandnum << fracbits;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int fracoffsbad = val >> (bandnum - 1); /* has leading 1 still */
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int bucket = bandstart + fracoffsbad - BIT(fracbits);
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return bucket;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody}
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmodystatic inline unsigned int ATTR_CONST
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmodybits_fraclog_bucket_start(unsigned int bucket, unsigned int fracbits)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody{
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int bandnum = bucket >> fracbits;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody if (bandnum <= 1)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return bucket;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody if (fracbits == 0)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return BIT(bucket - 1);
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int fracoffs = bucket & (BIT(fracbits)-1);
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int fracoffs1 = BIT(fracbits) + fracoffs;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int bandstart = fracoffs1 << (bandnum - 1);
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return bandstart;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody}
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmodystatic inline unsigned int ATTR_CONST
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmodybits_fraclog_bucket_end(unsigned int bucket, unsigned int fracbits)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody{
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int bandnum = bucket >> fracbits;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody if (bandnum <= 1)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return bucket;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody if (fracbits == 0)
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return BIT(bucket - 1) * 2 - 1;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int fracoffs = bucket & (BIT(fracbits)-1);
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int nextfracoffs1 = 1 + BIT(fracbits) + fracoffs;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody unsigned int nextbandstart = nextfracoffs1 << (bandnum - 1);
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody return nextbandstart - 1;
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody}
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody/* UNSAFE: multiple use of parameter (but expecting a constant in reality).
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody But a macro as it's most likely to be used to declare an array size.
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody*/
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody#define BITS_FRACLOG_BUCKETS(bits) ((33u - (bits)) << (bits))
bb0eabc25c8ec2ee98e31fb81274481cc8ed245ePhil Carmody
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody#endif