src/lib/bits.h

	bits.h revision d6e496a8bdb887a49112250e781f219d91fee117
02c335c23bf5fa225a467c19f2c063fb0dc7b8c3Timo Sirainen#ifndef BITS_H
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainen#define BITS_H
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainen
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainen#define UINT64_SUM_OVERFLOWS(a, b) \
afb7901ecb5d5566d4cf19be969654946fbaad4bTimo Sirainen    (a > (uint64_t)-1 - b)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainen#define BIT(n) (1u << (n))
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen
994bb1a8a80da664083691d41dd9aec5d6fba2bfTimo Sirainensize_t nearest_power(size_t num) ATTR_CONST;
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainen
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainen/* Returns TRUE if 2^x=num, i.e. if num has only a single bit set to 1. */
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainenstatic inline bool ATTR_CONST
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainenbits_is_power_of_two(uint64_t num)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen{
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainen    return num > 0 && (num & (num - 1)) == 0;
39afc7584d935b2dc7332c21966a7b20da03f1ecTimo Sirainen}
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainen
b66412da78711db8423288847ecfb08469609a03Timo Sirainen#if __GNUC__ > 2
b66412da78711db8423288847ecfb08469609a03Timo Sirainenstatic inline unsigned int ATTR_CONST
df02611c44e9432e7961223bf9bfa3fb233b1789Timo Sirainenbits_required32(uint32_t num)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen{
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    return num == 0 ? 0 : 32 - __builtin_clz(num);
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen}
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenstatic inline unsigned int ATTR_CONST
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenbits_required8(uint8_t num)   { return bits_required32(num); }
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen
39afc7584d935b2dc7332c21966a7b20da03f1ecTimo Sirainenstatic inline unsigned int ATTR_CONST
39afc7584d935b2dc7332c21966a7b20da03f1ecTimo Sirainenbits_required16(uint16_t num) { return bits_required32(num); }
39afc7584d935b2dc7332c21966a7b20da03f1ecTimo Sirainen
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenstatic inline unsigned int ATTR_CONST
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenbits_required64(uint64_t num)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen{
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    return num == 0 ? 0 : 64 - __builtin_clzll(num);
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen}
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen#else
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenunsigned int bits_required8(uint8_t num) ATTR_CONST;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenstatic inline
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainenunsigned int bits_required16(uint16_t num)
d6cc34b076dced6ebf8af47d72c8242357288312Timo Sirainen{
4babe70b863c71ea330cbf32ac0b71876f4f9137Timo Sirainen    return (num <= 0xff) ? bits_required8(num)
4babe70b863c71ea330cbf32ac0b71876f4f9137Timo Sirainen        : 8 + bits_required8(num >> 8);
4babe70b863c71ea330cbf32ac0b71876f4f9137Timo Sirainen}
4babe70b863c71ea330cbf32ac0b71876f4f9137Timo Sirainenstatic inline
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenunsigned int bits_required32(uint32_t num)
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen{
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen    return (num <= 0xffff) ? bits_required16(num)
d6cc34b076dced6ebf8af47d72c8242357288312Timo Sirainen        : 16 + bits_required16(num >> 16);
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen}
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenstatic inline
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenunsigned int bits_required64(uint64_t num)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen{
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    return (num <= 0xffffffff) ? bits_required32(num)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen        : 32 + bits_required32(num >> 32);
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen}
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen#endif
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen
39afc7584d935b2dc7332c21966a7b20da03f1ecTimo Sirainen/* These functions look too big to be inline, but in almost all expected
39afc7584d935b2dc7332c21966a7b20da03f1ecTimo Sirainen   uses, 'fracbits' will be a compile-time constant, and most of the
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen   expressions will simplify greatly.
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen*/
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen/* Perform a piecewise-linear approximation to a log2, with fracbits "fractional" bits.
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen   Best explained with examples:
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen   With 2 fractional bits splitting each power of 2 into 4 bands:
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen     00,   01,   10,   11 ->   00,   01,   10,   11 (small corner cases)
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainen    100,  101,  110,  111 ->  100,  101,  110,  111 ([4-8) split into 4 bands)
d6cc34b076dced6ebf8af47d72c8242357288312Timo Sirainen   1000, 1001, 1010, 1011 -> 1000, 1000, 1001, 1001 ([8-15) split ...
4babe70b863c71ea330cbf32ac0b71876f4f9137Timo Sirainen   1100, 1101, 1110, 1111 -> 1010, 1010, 1011, 1011  ... into 4 bands)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen   [16..31) -> 11bb
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen   [32..63) -> 100bb
3320f4770d1f6c2cdd10f3c4ca5a324beb335339Timo Sirainen   [64..127) -> 101bb
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen   [128..255) -> 110bb
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen   e.g. 236 = 11101100 -> ((8-2)<<2 == 11000) + (111.....>> 5 == 111) - 100 == 11011
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen */
b66412da78711db8423288847ecfb08469609a03Timo Sirainenstatic inline unsigned int ATTR_CONST
b66412da78711db8423288847ecfb08469609a03Timo Sirainenbits_fraclog(unsigned int val, unsigned int fracbits)
b66412da78711db8423288847ecfb08469609a03Timo Sirainen{
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    unsigned bits = bits_required32(val);
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    if (bits <= fracbits + 1)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen        return val;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainen    unsigned int bandnum = bits - fracbits;
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainen    unsigned int bandstart = bandnum << fracbits;
afb7901ecb5d5566d4cf19be969654946fbaad4bTimo Sirainen    unsigned int fracoffsbad = val >> (bandnum - 1); /* has leading 1 still */
d6cc34b076dced6ebf8af47d72c8242357288312Timo Sirainen    unsigned int bucket = bandstart + fracoffsbad - BIT(fracbits);
d6cc34b076dced6ebf8af47d72c8242357288312Timo Sirainen    return bucket;
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainen}
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenstatic inline unsigned int ATTR_CONST
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenbits_fraclog_bucket_start(unsigned int bucket, unsigned int fracbits)
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainen{
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    unsigned int bandnum = bucket >> fracbits;
b58fbcc79c40f867eccae98548fcd25a16823433Timo Sirainen    if (bandnum <= 1)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen        return bucket;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    if (fracbits == 0)
b66412da78711db8423288847ecfb08469609a03Timo Sirainen        return BIT(bucket - 1);
b66412da78711db8423288847ecfb08469609a03Timo Sirainen    unsigned int fracoffs = bucket & (BIT(fracbits)-1);
b039dabf4c53f72454e795930e7643b6e0e625f9Timo Sirainen    unsigned int fracoffs1 = BIT(fracbits) + fracoffs;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    unsigned int bandstart = fracoffs1 << (bandnum - 1);
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    return bandstart;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen}
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenstatic inline unsigned int ATTR_CONST
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainenbits_fraclog_bucket_end(unsigned int bucket, unsigned int fracbits)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen{
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    unsigned int bandnum = bucket >> fracbits;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    if (bandnum <= 1)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen        return bucket;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    if (fracbits == 0)
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen        return BIT(bucket - 1) * 2 - 1;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    unsigned int fracoffs = bucket & (BIT(fracbits)-1);
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    unsigned int nextfracoffs1 = 1 + BIT(fracbits) + fracoffs;
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    unsigned int nextbandstart = nextfracoffs1 << (bandnum - 1);
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen    return nextbandstart - 1;
b66412da78711db8423288847ecfb08469609a03Timo Sirainen}
b66412da78711db8423288847ecfb08469609a03Timo Sirainen/* UNSAFE: multiple use of parameter (but expecting a constant in reality).
b66412da78711db8423288847ecfb08469609a03Timo Sirainen   But a macro as it's most likely to be used to declare an array size.
b66412da78711db8423288847ecfb08469609a03Timo Sirainen*/
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen#define BITS_FRACLOG_BUCKETS(bits) ((33u - (bits)) << (bits))
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen#endif
cb1fd563e6000153d1be76fd8722a096bd144b77Timo Sirainen