DOSBox-X
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines
include/bitop.h
00001 
00002 #include <limits.h>
00003 #include <stdint.h>
00004 
00005 #include <utility>
00006 
00007 namespace bitop {
00008 
00009 /* Return the number of bits of the data type.
00010  *
00011  * The return value is sizeof() * CHAR_BIT. On most platforms today, CHAR_BIT == 8.
00012  * CHAR_BIT could be other values if this is compiled on older mainframe platforms where
00013  * a 'char' is less or more than 8 bits.
00014  *
00015  * @return Number of bits in data type T
00016  */
00017 template <typename T=unsigned int> static inline constexpr unsigned int type_bits(void) {
00018     return (unsigned int)sizeof(T) * (unsigned int)CHAR_BIT;
00019 }
00020 
00021 /* Return data type T with all bits 0
00022  *
00023  * The memory storage of such a value should show ALL bits set to 0.
00024  * 
00025  * On CPUs today that use signed 2's complement integers, it is expected that: allzero() - (T)1u == allones()
00026  * Subtracting 1 from all zeros should result in all ones.
00027  *
00028  * @return Type T with zero bits
00029  */
00030 template <typename T=unsigned int> static inline constexpr T allzero(void) {
00031     return (T)0;
00032 }
00033 
00034 /* Return data type T with all bits 1
00035  *
00036  * The memory storage of such a value should show ALL bits set to 1.
00037  * 
00038  * On CPUs today that use signed 2's complement integers, it is expected that: allones() + (T)1u == allzero()
00039  * Adding 1 to all ones should result in all zeros.
00040  * 
00041  * @return Type T with set bits
00042  */
00043 template <typename T=unsigned int> static inline constexpr T allones(void) {
00044     return (T)( ~((T)0) );
00045 }
00046 
00047 
00048 /* Return data type T with value inverted
00049  *
00050  * This is to avoid typecast messes when masking by the inverse of a constant
00051  * 
00052  * @return Type T with value inverted
00053  */
00054 template <typename T=unsigned int> static inline constexpr T invert(const T v) {
00055     return (T)( ~v );
00056 }
00057 
00058 
00059 /* private recursion function */
00060 template <typename T=unsigned int> static inline constexpr unsigned int _bitlength_recursion(const T v,const unsigned int bits) {
00061     return (v != allzero()) ? _bitlength_recursion(v >> (T)1u,bits + 1u) : bits;
00062 }
00063 
00064 /* Return minimum number of bits required to represent value 'v' in data type 'T'
00065  *
00066  * This function is declared constexpr so that the compiler can evaluate a constant value at compile
00067  * time and insert the result as constant into the code. Since constexpr cannot use if(), while() and
00068  * so on, recursion is used instead.
00069  *
00070  * @return Number of bits needed
00071  */
00072 template <typename T=unsigned int,const T v> static inline constexpr unsigned int bitlength(void) {
00073     return _bitlength_recursion<T>(v,0);
00074 }
00075 
00076 template <const unsigned int v> static inline constexpr unsigned int bitlength(void) {
00077     return bitlength<unsigned int,v>();
00078 }
00079 
00080 /* non-constant version for runtime use */
00081 template <typename T=unsigned int> static inline unsigned int bitlength(T v) {
00082     unsigned int c = 0;
00083 
00084     while ((v & 0xFFUL) == 0xFFUL) {
00085         v >>= (T)8UL;
00086         c += (T)8;
00087     }
00088     while (v != allzero<T>()) {
00089         v >>= (T)1UL;
00090         c++;
00091     }
00092 
00093     return c;
00094 }
00095 
00096 
00097 /* private recursion function */
00098 template <typename T=unsigned int> static inline constexpr unsigned int _bitseqlength_recursionlsb(const T v,const unsigned int bits) {
00099     return (v & 1u) ? _bitseqlength_recursionlsb<T>(v >> (T)1u,bits + 1u) : bits;
00100 }
00101 
00102 /* private common function */
00103 template <typename T=unsigned int> static inline void _bitseqlengthlsb_1(unsigned int &c,T &v) {
00104     while ((v & 0xFFUL) == 0xFFUL) {
00105         v >>= (T)8UL;
00106         c += (T)8;
00107     }
00108     while (v & 1u) {
00109         v >>= (T)1UL;
00110         c++;
00111     }
00112 }
00113 
00114 /* Return number of sequential 1 bits counting from LSB in value 'v' of type 'T'
00115  *
00116  * THis counts bits from the LSB upward until a zero bit is encountered.
00117  *
00118  * A constexpr version is provided for use at compile time and a non-constexpr
00119  * version is provided for use at runtime.
00120  *
00121  * @return Number of bits
00122  */
00123 template <typename T=unsigned int,const T v> static inline constexpr unsigned int bitseqlengthlsb(void) {
00124     return _bitseqlength_recursionlsb(v,0);
00125 }
00126 
00127 template <const unsigned int v> static inline constexpr unsigned int bitseqlengthlsb(void) {
00128     return bitseqlengthlsb<unsigned int,v>();
00129 }
00130 
00131 template <typename T=unsigned int> static inline unsigned int bitseqlengthlsb(T v) {
00132     unsigned int c = 0;
00133     _bitseqlengthlsb_1(/*&*/c,/*&*/v);
00134     return c;
00135 }
00136 
00137 
00138 /* Return binary mask of bit 'a'
00139  *
00140  * The returned bitmask should be usable to mask off bit 'a' and only bit 'a'.
00141  *
00142  * The function is constexpr to enable compile-time evaluation.
00143  *
00144  * @return Bitmask
00145  */
00146 template <const unsigned int a,typename T=unsigned int> static inline constexpr T bit2mask(void) {
00147     static_assert(a < type_bits<T>(), "bit2mask constexpr bit count too large for data type");
00148     return (T)1U << (T)a;
00149 }
00150 
00151 template <typename T=unsigned int> static inline constexpr T bit2mask(const unsigned int a) {
00152     return (T)1U << (T)a;
00153 }
00154 
00155 
00156 /* Return binary mask of MSB in type 'T'
00157  *
00158  * The returned bitmask should be usable to mask off the most significant bit of data type 'T'
00159  *
00160  * @return Bitmask
00161  */
00162 template <typename T=unsigned int> static inline constexpr T type_msb_mask(void) {
00163     return bit2mask<T>(type_bits<T>() - 1u);
00164 }
00165 
00166 
00167 /* Return binary mask of 'a' LSB bits starting at bit offset 'offset' in type 'T'
00168  *
00169  * The returned bitmask should be usable to mask off 'a' bits starting from the bottom (LSB) at bit 'offset'.
00170  *
00171  * Examples:    bitcount2masklsb<1,0>() = 0x00000001U           a=1 offset=0        bits 0 to 0
00172  *              bitcount2masklsb<4,0>() = 0x0000000FU           a=4 offset=0        bits 3 to 0
00173  *              bitcount2masklsb<16,0>() = 0x0000FFFFU          a=16 offset=0       bits 15 to 0
00174  *              bitcount2masklsb<4,4>() = 0x000000F0U           a=4 offset=4        bits 7 to 4
00175  *
00176  * @return Bitmask
00177  */
00178 template <const unsigned int a,const unsigned int offset,typename T=unsigned int> static inline constexpr T bitcount2masklsb(void) {
00179     /* NTS: special case for a == type_bits because shifting the size of a register OR LARGER is undefined.
00180      *      On Intel x86 processors, with 32-bit integers, x >> 32 == x >> 0 because only the low 5 bits are used 
00181      *      a % type_bits<T>() is there to keep a < type_bits<T> in case your C++11 compiler likes to trigger
00182      *      all static_assert<> clauses even if the ternary would not choose that path. */
00183     static_assert(a <= type_bits<T>(), "bitcount2masklsb constexpr bit count too large for data type");
00184     static_assert(offset < type_bits<T>(), "bitcount2masklsb constexpr offset count too large for data type");
00185     static_assert((a+offset) <= type_bits<T>(), "bitcount2masklsb constexpr bit count + offset count too large for data type");
00186     return ((a < type_bits<T>()) ? (bit2mask<a % type_bits<T>(),T>() - (T)1u) : allones<T>()) << (T)offset;
00187 }
00188 
00189 template <const unsigned int a,typename T=unsigned int> static inline constexpr T bitcount2masklsb(void) {
00190     return bitcount2masklsb<a,0u,T>();
00191 }
00192 
00193 template <typename T=unsigned int> static inline constexpr T bitcount2masklsb(const unsigned int a,const unsigned int offset=0) {
00194     /* NTS: special case for a == type_bits because shifting the size of a register OR LARGER is undefined.
00195      *      On Intel x86 processors, with 32-bit integers, x >> 32 == x >> 0 because only the low 5 bits are used */
00196     return ((a < type_bits<T>()) ? (bit2mask<T>(a) - (T)1u) : allones<T>()) << (T)offset;
00197 }
00198 
00199 
00200 /* Return binary mask of 'a' MSB bits starting at bit offset 'offset' in type 'T'
00201  *
00202  * The returned bitmask should be usable to mask off 'a' bits starting from the top (MSB) at bit 'offset'.
00203  *
00204  * Examples:    bitcount2maskmsb<1,0>() = 0x80000000U           a=1 offset=0        bits 31 to 31
00205  *              bitcount2maskmsb<4,0>() = 0xF0000000U           a=4 offset=0        bits 31 to 28
00206  *              bitcount2maskmsb<16,0>() = 0xFFFF0000U          a=16 offset=0       bits 31 to 16
00207  *              bitcount2maskmsb<4,4>() = 0x0F000000U           a=4 offset=4        bits 27 to 24
00208  *
00209  * @return Bitmask
00210  */
00211 template <const unsigned int a,const unsigned int offset,typename T=unsigned int> static inline constexpr T bitcount2maskmsb(void) {
00212     /* NTS: special case for a == type_bits because shifting the size of a register OR LARGER is undefined.
00213      *      On Intel x86 processors, with 32-bit integers, x >> 32 == x >> 0 because only the low 5 bits are used 
00214      *      a % type_bits<T>() is there to keep a < type_bits<T> in case your C++11 compiler likes to trigger
00215      *      all static_assert<> clauses even if the ternary would not choose that path. */
00216     static_assert(a <= type_bits<T>(), "bitcount2maskmsb constexpr bit count too large for data type");
00217     static_assert(offset < type_bits<T>(), "bitcount2maskmsb constexpr offset count too large for data type");
00218     static_assert((a+offset) <= type_bits<T>(), "bitcount2maskmsb constexpr bit count + offset count too large for data type");
00219     return ((a != (T)0) ? ((T)(allones<T>() << (T)(type_bits<T>() - a)) >> (T)offset) : allzero<T>());
00220 }
00221 
00222 template <const unsigned int a,typename T=unsigned int> static inline constexpr T bitcount2maskmsb(void) {
00223     return bitcount2maskmsb<a,0u,T>();
00224 }
00225 
00226 template <typename T=unsigned int> static inline constexpr T bitcount2maskmsb(const unsigned int a,const unsigned int offset=0) {
00227     /* NTS: special case for a == type_bits because shifting the size of a register OR LARGER is undefined.
00228      *      On Intel x86 processors, with 32-bit integers, x >> 32 == x >> 0 because only the low 5 bits are used */
00229     return ((a != (T)0) ? ((T)(allones<T>() << (T)(type_bits<T>() - a)) >> (T)offset) : allzero<T>());
00230 }
00231 
00232 
00233 /* Indicate whether 'a' is a power of 2.
00234  *
00235  * This code will NOT work correctly if a == 0, the result is to be considered undefined.
00236  * Note that in real mathematics, there is no value x for which 2 to the power of 'x' equals zero.
00237  * But you might be able to plug infinity into x to get really close to zero.
00238  *
00239  * The reason this works is that the binary value of an unsigned integer that holds a power of 2,
00240  * when the power is 0 <= x < (number of bits), is exactly one '1' bit surrounded by zeros.
00241  *
00242  * 2^0 == 1                     00000001
00243  * 2^1 == 2                     00000010
00244  * 2^2 == 4                     00000100
00245  * 2^3 == 8                     00001000
00246  * 2^4 == 16                    00010000
00247  * 2^5 == 32                    00100000
00248  * 2^6 == 64                    01000000
00249  * 2^7 == 128                   10000000
00250  * 
00251  * Subtracting 1 from the power of 2 changes bit 'x' to zero and all bits 0 to (x-1) to one.
00252  *
00253  * 2^0 - 1 == 0                 00000000        |       00000001            2^0 == 1
00254  * 2^1 - 1 == 1                 00000001        |       00000010            2^1 == 2
00255  * 2^2 - 1 == 3                 00000011        |       00000100            2^2 == 4
00256  * 2^3 - 1 == 7                 00000111        |       00001000            2^3 == 8
00257  * 2^4 - 1 == 15                00001111        |       00010000            2^4 == 16
00258  * 2^5 - 1 == 31                00011111        |       00100000            2^5 == 32
00259  * 2^6 - 1 == 63                00111111        |       01000000            2^6 == 64
00260  * 2^7 - 1 == 127               01111111        |       10000000            2^7 == 128
00261  *
00262  * Since subtracting 1 from 2^x changes the single bit to zero, ANDing (2^x) and (2^x - 1) should always
00263  * produce a zero value.
00264  *
00265  * No other integer value has this property.
00266  *
00267  * 6 & 5 == 110 & 101           00000100
00268  * 7 & 6 == 111 & 110           00000110
00269  * 8 & 7 == 1000 & 0111         00000000
00270  * 9 & 8 == 1001 & 1000         00001000
00271  * 10 & 9 == 1010 & 1001        00001000
00272  *
00273  * AND truth table:                                     +---------
00274  *                                                      |         --
00275  * OUTPUT = a AND b                             --------+           -
00276  *                                                      |            +-----         A ยท B
00277  * OUTPUT is '1' if both a and b are '1'        --------+           -
00278  *                                                      |         --
00279  *    0 1 <- a                                          +---------
00280  *   +----
00281  * 0 |0 0
00282  * 1 |0 1
00283  * ^
00284  * b
00285  *
00286  * For integer values, apply the AND operator to the same bit position from both integers for each bit across the width of the integer.
00287  *
00288  * @return Boolean true if 'a' is a power of 2 */
00289 template <typename T=unsigned int> static inline constexpr bool ispowerof2(const unsigned int a) {
00290     return (a & (a-(T)1u)) == 0;
00291 }
00292 
00293 
00294 /* Return log2(v), or the bit position of the highest '1' bit of value 'v'
00295  *
00296  * A value of '0' will return allones<unsigned int>() to indicate an invalid value.
00297  *
00298  * The constexpr templated version will trigger a static_assert if v == 0.
00299  *
00300  * log2(2^32 - 1) == 31                         2^32 - 1 = 0xFFFFFFFF
00301  * log2(2^31) == 31
00302  * log2(2^30) == 30
00303  * log2(2^16) == 16                             2^16 == 65536
00304  * log2(2^4) == 4                               2^4 == 16
00305  * log2(2^1) == 1                               2^1 == 2
00306  * log2(2^0) == 0                               2^0 == 1
00307  * log2(0) == ~0u (UINT_MAX or allones()) 
00308  *
00309  * @return Bitmask
00310  */
00311 
00312 /* private recursion function */
00313 template <typename T=unsigned int> static inline constexpr unsigned int _log2_recursion(const T v,const unsigned int bits) {
00314     /* NTS: The additional check against v == allzero() is needed to avoid an infinite recursion loop */
00315     return (v != allzero<T>()) ?
00316         (((v & type_msb_mask<T>()) == allzero<T>()) ? _log2_recursion(v << (T)1u,bits - 1u) : bits) :
00317         (~0u);
00318 }
00319 
00320 template <typename T=unsigned int,const T v> static inline constexpr unsigned int log2(void) {
00321     return _log2_recursion<T>(v,type_bits<T>() - 1u);
00322 }
00323 
00324 template <const unsigned int v> static inline constexpr unsigned int log2(void) {
00325     return log2<unsigned int,v>();
00326 }
00327 
00328 /* non-constant version for runtime use */
00329 template <typename T=unsigned int> static inline unsigned int log2(T v) {
00330     if (v != allzero<T>()) {
00331         unsigned int c = type_bits<T>() - 1u;
00332 
00333         while (!(v & type_msb_mask<T>())) {
00334             v <<= (T)1UL;
00335             c--;
00336         }
00337 
00338         return c;
00339     }
00340 
00341     return ~0u;
00342 }
00343 
00344 
00345 /* return type, pair */
00346 class bitseqlengthandpos_ret_t {
00347     public:
00348         bitseqlengthandpos_ret_t(const unsigned int _start,const unsigned int _length) : start(_start), length(_length) { }
00349     public:
00350         bool operator==(const bitseqlengthandpos_ret_t &n) const {
00351             return  (n.start == start) &&
00352                     (n.length == length);
00353         }
00354         bool empty(void) const {
00355             return  (start == 0u && length == 0u);
00356         }
00357     public:
00358         unsigned int    start, length;
00359 };
00360 
00361 /* return a pair struct representing start and length of a series of 1 bits */
00362 template <typename T=unsigned int> static inline bitseqlengthandpos_ret_t bitseqlengthandpos(T v) {
00363     if (v != bitop::allzero<T>()) {
00364         unsigned int start=0,length=0;
00365 
00366         /* count zeros */
00367         while ((v & (T)0xFFUL) == (T)0x00UL) {
00368             start += (T)8;
00369             v >>= (T)8UL;
00370         }
00371         while (!(v & (T)1u)) {
00372             start++;
00373             v >>= (T)1UL;
00374         }
00375 
00376         /* count ones */
00377         while ((v & (T)0xFFUL) == (T)0xFFUL) {
00378             length += (T)8;
00379             v >>= (T)8UL;
00380         }
00381         while (v & (T)1u) {
00382             length++;
00383             v >>= (T)1UL;
00384         }
00385 
00386         return bitseqlengthandpos_ret_t(start,length);
00387     }
00388 
00389     return bitseqlengthandpos_ret_t(0u,0u);
00390 }
00391 
00392 
00393 void self_test(void);
00394 
00395 }
00396