DOSBox-X
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines
src/gui/bitop.cpp
00001 
00002 #include <assert.h>
00003 
00004 #include "bitop.h"
00005 
00006 /* I don't know when this happened.... but suddenly Microsoft C++ doesn't like these constexpr tests or static_assert >:( */
00007 #if defined(_MSC_VER)
00008 # define DISABLE_SELF_TEST
00009 #endif
00010 
00011 namespace bitop {
00012 
00013 void self_test(void) {
00014 #ifdef DISABLE_SELF_TEST
00015 # pragma message ("bitop self-test disabled for your compiler")
00016 #else
00017     // DEBUG
00018     static_assert(bitcount2masklsb<0u>() == 0u, "whoops");
00019     static_assert(bitcount2masklsb<1u>() == 1u, "whoops");
00020     static_assert(bitcount2masklsb<2u>() == 3u, "whoops");
00021     static_assert(bitcount2masklsb<2u,1u>() == 6u, "whoops");
00022     static_assert(bitcount2masklsb<2u,uint8_t>() == 3u, "whoops");
00023     static_assert(bitcount2masklsb<2u,0u,uint8_t>() == 3u, "whoops");
00024     static_assert(bitcount2masklsb<2u,1u,uint8_t>() == 6u, "whoops");
00025     static_assert(bitcount2masklsb<type_bits()>() == allones(), "whoops");
00026     static_assert(allones<uint32_t>() == (uint32_t)0xFFFFFFFFUL, "whoops");
00027     static_assert(allzero<uint32_t>() == (uint32_t)0, "whoops");
00028     static_assert(allones<uint64_t>() == (uint64_t)0xFFFFFFFFFFFFFFFFULL, "whoops");
00029     static_assert(allzero<uint64_t>() == (uint64_t)0, "whoops");
00030     static_assert((~allones<uint32_t>()) == allzero<uint32_t>(), "whoops");
00031     static_assert((~allzero<uint32_t>()) == allones<uint32_t>(), "whoops");
00032     assert(type_bits<uint64_t>() == 64u);
00033     assert(type_bits<uint32_t>() == 32u);
00034     assert(type_bits<uint16_t>() == 16u);
00035     assert(type_bits<uint8_t>() == 8u);
00036     assert(bit2mask(0u) == 1u);
00037     assert(bit2mask(8u) == 256u);
00038     assert(bit2mask<8u>() == 256u);
00039     static_assert(bit2mask<9u>() == 512u, "whoops");
00040     static_assert(bit2mask<33u,uint64_t>() == (1ull << 33ull), "whoops");
00041     static_assert(bitlength<0u>() == 0u, "whoops");
00042     static_assert(bitlength<1u>() == 1u, "whoops");
00043     static_assert(bitlength<2u>() == 2u, "whoops");
00044     static_assert(bitlength<3u>() == 2u, "whoops");
00045     static_assert(bitlength<4u>() == 3u, "whoops");
00046     static_assert(bitlength<7u>() == 3u, "whoops");
00047     static_assert(bitlength<8u>() == 4u, "whoops");
00048     static_assert(bitlength<~0u>() == type_bits(), "whoops");
00049     static_assert(type_msb_mask<uint8_t>() == 0x80u, "whoops");
00050     static_assert(type_msb_mask<uint16_t>() == 0x8000u, "whoops");
00051     static_assert(type_msb_mask<uint32_t>() == 0x80000000ul, "whoops");
00052     static_assert(type_msb_mask<uint64_t>() == 0x8000000000000000ull, "whoops");
00053 
00054     static_assert(bitseqlengthlsb<0u>() == 0u, "whoops"); // 0
00055     static_assert(bitseqlengthlsb<1u>() == 1u, "whoops"); // 1
00056     static_assert(bitseqlengthlsb<2u>() == 0u, "whoops"); // 10
00057     static_assert(bitseqlengthlsb<3u>() == 2u, "whoops"); // 11
00058     static_assert(bitseqlengthlsb<4u>() == 0u, "whoops"); // 100
00059     static_assert(bitseqlengthlsb<5u>() == 1u, "whoops"); // 101
00060     static_assert(bitseqlengthlsb<6u>() == 0u, "whoops"); // 110
00061     static_assert(bitseqlengthlsb<7u>() == 3u, "whoops"); // 111
00062     static_assert(bitseqlengthlsb<8u>() == 0u, "whoops"); // 1000
00063     static_assert(bitseqlengthlsb<9u>() == 1u, "whoops"); // 1001
00064     static_assert(bitseqlengthlsb<10u>() == 0u, "whoops"); // 1010
00065     static_assert(bitseqlengthlsb<11u>() == 2u, "whoops"); // 1011
00066     static_assert(bitseqlengthlsb<12u>() == 0u, "whoops"); // 1100
00067     static_assert(bitseqlengthlsb<15u>() == 4u, "whoops"); // 1111
00068     static_assert(bitseqlengthlsb<23u>() == 3u, "whoops"); // 10111
00069     static_assert(bitseqlengthlsb<31u>() == 5u, "whoops"); // 11111
00070     static_assert(bitseqlengthlsb<~0u>() == type_bits(), "whoops");
00071 
00072     assert(bitlength(0u) == 0u);
00073     assert(bitlength(1u) == 1u);
00074     assert(bitlength(2u) == 2u);
00075     assert(bitlength(3u) == 2u);
00076     assert(bitlength(4u) == 3u);
00077     assert(bitlength(7u) == 3u);
00078     assert(bitlength(255u) == 8u);
00079     assert(bitlength(256u) == 9u);
00080     assert(bitlength(512u) == 10u);
00081     assert(bitlength(1024u) == 11u);
00082     assert(bitlength(32767u) == 15u);
00083     assert(bitlength(32768u) == 16u);
00084 
00085     assert(bitseqlengthlsb(0u) == 0u);
00086     assert(bitseqlengthlsb(1u) == 1u);
00087     assert(bitseqlengthlsb(2u) == 0u);
00088     assert(bitseqlengthlsb(3u) == 2u);
00089     assert(bitseqlengthlsb(4u) == 0u);
00090     assert(bitseqlengthlsb(5u) == 1u);
00091     assert(bitseqlengthlsb(6u) == 0u);
00092     assert(bitseqlengthlsb(7u) == 3u);
00093     assert(bitseqlengthlsb(255u) == 8u);
00094     assert(bitseqlengthlsb(256u) == 0u);
00095     assert(bitseqlengthlsb(512u) == 0u);
00096     assert(bitseqlengthlsb(1024u) == 0u);
00097     assert(bitseqlengthlsb(32767u) == 15u);
00098     assert(bitseqlengthlsb(32768u) == 0u);
00099 
00100     static_assert(bitcount2maskmsb<0u>() == 0u, "whoops");
00101     static_assert(bitcount2maskmsb<1u>() == (1u << (type_bits() - 1u)), "whoops");
00102     static_assert(bitcount2maskmsb<2u>() == (3u << (type_bits() - 2u)), "whoops");
00103     static_assert(bitcount2maskmsb<2u,1u>() == (3u << (type_bits() - 3u)), "whoops");
00104     static_assert(bitcount2maskmsb<2u,uint8_t>() == (3u << 6u), "whoops");
00105     static_assert(bitcount2maskmsb<2u,0u,uint8_t>() == (3u << 6u), "whoops");
00106     static_assert(bitcount2maskmsb<2u,1u,uint8_t>() == (3u << 5u), "whoops");
00107     static_assert(bitcount2maskmsb<type_bits()>() == allones(), "whoops");
00108 
00109     assert(bitcount2masklsb(0u) == 0u);
00110     assert(bitcount2masklsb(1u) == 1u);
00111     assert(bitcount2masklsb(2u) == 3u);
00112     assert(bitcount2masklsb(2u,1u) == 6u);
00113     assert(bitcount2masklsb<uint8_t>(2u) == 3u);
00114     assert(bitcount2masklsb<uint8_t>(2u,0u) == 3u);
00115     assert(bitcount2masklsb<uint8_t>(2u,1u) == 6u);
00116     assert(bitcount2masklsb(type_bits()) == allones());
00117 
00118     assert(bitcount2maskmsb(0u) == 0u);
00119     assert(bitcount2maskmsb(1u) == (1u << (type_bits() - 1u)));
00120     assert(bitcount2maskmsb(2u) == (3u << (type_bits() - 2u)));
00121     assert(bitcount2maskmsb(2u,1u) == (3u << (type_bits() - 3u)));
00122     assert(bitcount2maskmsb<uint8_t>(2u) == (3u << 6u));
00123     assert(bitcount2maskmsb<uint8_t>(2u,0u) == (3u << 6u));
00124     assert(bitcount2maskmsb<uint8_t>(2u,1u) == (3u << 5u));
00125     assert(bitcount2maskmsb(type_bits()) == allones());
00126 
00127     static_assert(ispowerof2(1u) == true, "whoops");
00128     static_assert(ispowerof2(2u) == true, "whoops");
00129     static_assert(ispowerof2(3u) == false, "whoops");
00130     static_assert(ispowerof2(4u) == true, "whoops");
00131     static_assert(ispowerof2(5u) == false, "whoops");
00132     static_assert(ispowerof2(6u) == false, "whoops");
00133     static_assert(ispowerof2(7u) == false, "whoops");
00134     static_assert(ispowerof2(8u) == true, "whoops");
00135     static_assert(ispowerof2(9u) == false, "whoops");
00136     static_assert(ispowerof2(10u) == false, "whoops");
00137     static_assert(ispowerof2(11u) == false, "whoops");
00138     static_assert(ispowerof2(255u) == false, "whoops");
00139     static_assert(ispowerof2(256u) == true, "whoops");
00140     static_assert(ispowerof2(257u) == false, "whoops");
00141     static_assert(ispowerof2(32767u) == false, "whoops");
00142     static_assert(ispowerof2(32768u) == true, "whoops");
00143     static_assert(ispowerof2(32769u) == false, "whoops");
00144 
00145     assert(ispowerof2(1u) == true);
00146     assert(ispowerof2(2u) == true);
00147     assert(ispowerof2(3u) == false);
00148     assert(ispowerof2(4u) == true);
00149     assert(ispowerof2(5u) == false);
00150     assert(ispowerof2(6u) == false);
00151     assert(ispowerof2(7u) == false);
00152     assert(ispowerof2(8u) == true);
00153     assert(ispowerof2(9u) == false);
00154     assert(ispowerof2(10u) == false);
00155     assert(ispowerof2(11u) == false);
00156     assert(ispowerof2(255u) == false);
00157     assert(ispowerof2(256u) == true);
00158     assert(ispowerof2(257u) == false);
00159     assert(ispowerof2(32767u) == false);
00160     assert(ispowerof2(32768u) == true);
00161     assert(ispowerof2(32769u) == false);
00162 
00163     static_assert(log2<1u << 31>() == 31, "whoops");
00164     static_assert(log2<1u << 16>() == 16, "whoops");
00165     static_assert(log2<1u << 8>() == 8, "whoops");
00166     static_assert(log2<1u << 4>() == 4, "whoops");
00167     static_assert(log2<1u << 3>() == 3, "whoops");
00168     static_assert(log2<1u << 2>() == 2, "whoops");
00169     static_assert(log2<1u << 1>() == 1, "whoops");
00170     static_assert(log2<1u << 0>() == 0, "whoops");
00171     static_assert(log2<256u>() == 8, "whoops");
00172     static_assert(log2<128u>() == 7, "whoops");
00173     static_assert(log2<16u>() == 4, "whoops");
00174     static_assert(log2<1u>() == 0, "whoops");
00175     static_assert(log2<0u>() == ~0u, "whoops");
00176 
00177                                                     /* 3210 bit position */
00178                                                     /* ---- */
00179     static_assert(log2<9u>() == 3, "whoops");       /* 1001 */
00180     static_assert(log2<7u>() == 2, "whoops");       /*  111 */
00181     static_assert(log2<5u>() == 2, "whoops");       /*  101 */
00182     static_assert(log2<3u>() == 1, "whoops");       /*   11 */
00183     static_assert(log2<2u>() == 1, "whoops");       /*   10 */
00184 
00185     if (sizeof(unsigned long long) >= 8) { /* we're assuming unsigned long long is at least 64 bits here */
00186     static_assert(log2<unsigned long long,1ull << 63ull>() == 63, "whoops");
00187     static_assert(log2<unsigned long long,1ull << 48ull>() == 48, "whoops");
00188     }
00189     static_assert(log2<unsigned long long,1ull << 31ull>() == 31, "whoops");
00190     static_assert(log2<unsigned long long,1ull << 16ull>() == 16, "whoops");
00191     static_assert(log2<unsigned long long,1ull << 8ull>() == 8, "whoops");
00192     static_assert(log2<unsigned long long,1ull << 4ull>() == 4, "whoops");
00193     static_assert(log2<unsigned long long,1ull << 3ull>() == 3, "whoops");
00194     static_assert(log2<unsigned long long,1ull << 2ull>() == 2, "whoops");
00195     static_assert(log2<unsigned long long,1ull << 1ull>() == 1, "whoops");
00196     static_assert(log2<unsigned long long,1ull << 0ull>() == 0, "whoops");
00197     static_assert(log2<unsigned long long,256ull>() == 8, "whoops");
00198     static_assert(log2<unsigned long long,128ull>() == 7, "whoops");
00199     static_assert(log2<unsigned long long,16ull>() == 4, "whoops");
00200     static_assert(log2<unsigned long long,1ull>() == 0, "whoops");
00201     static_assert(log2<unsigned long long,0ull>() == ~0u, "whoops");
00202 
00203     assert(log2(1u << 31) == 31);
00204     assert(log2(1u << 16) == 16);
00205     assert(log2(1u << 8) == 8);
00206     assert(log2(1u << 4) == 4);
00207     assert(log2(1u << 3) == 3);
00208     assert(log2(1u << 2) == 2);
00209     assert(log2(1u << 1) == 1);
00210     assert(log2(1u << 0) == 0);
00211     assert(log2(256u) == 8);
00212     assert(log2(128u) == 7);
00213     assert(log2(16u) == 4);
00214     assert(log2(1u) == 0);
00215     assert(log2(0u) == ~0u);
00216 
00217                                     /* 3210 bit position */
00218                                     /* ---- */
00219     assert(log2(9u) == 3);          /* 1001 */
00220     assert(log2(7u) == 2);          /*  111 */
00221     assert(log2(5u) == 2);          /*  101 */
00222     assert(log2(3u) == 1);          /*   11 */
00223     assert(log2(2u) == 1);          /*   10 */
00224 
00225     if (sizeof(unsigned long long) >= 8) { /* we're assuming unsigned long long is at least 64 bits here */
00226     assert(log2<unsigned long long>(1ull << 63ull) == 63);
00227     assert(log2<unsigned long long>(1ull << 48ull) == 48);
00228     }
00229     assert(log2<unsigned long long>(1ull << 31ull) == 31);
00230     assert(log2<unsigned long long>(1ull << 16ull) == 16);
00231     assert(log2<unsigned long long>(1ull << 8ull) == 8);
00232     assert(log2<unsigned long long>(1ull << 4ull) == 4);
00233     assert(log2<unsigned long long>(1ull << 3ull) == 3);
00234     assert(log2<unsigned long long>(1ull << 2ull) == 2);
00235     assert(log2<unsigned long long>(1ull << 1ull) == 1);
00236     assert(log2<unsigned long long>(1ull << 0ull) == 0);
00237     assert(log2<unsigned long long>(256ull) == 8);
00238     assert(log2<unsigned long long>(128ull) == 7);
00239     assert(log2<unsigned long long>(16ull) == 4);
00240     assert(log2<unsigned long long>(1ull) == 0);
00241     assert(log2<unsigned long long>(0ull) == ~0u);
00242 
00243     static_assert(invert<unsigned int>(0) == ~0u, "whoops");
00244     static_assert(invert<unsigned int>(1) == ~1u, "whoops");
00245     static_assert(invert<unsigned long>(0) == ~0ul, "whoops");
00246     static_assert(invert<unsigned long>(1) == ~1ul, "whoops");
00247     static_assert(invert<unsigned long long>(0) == ~0ull, "whoops");
00248     static_assert(invert<unsigned long long>(1) == ~1ull, "whoops");
00249 
00250     assert(invert<unsigned int>(0) == ~0u);
00251     assert(invert<unsigned int>(1) == ~1u);
00252     assert(invert<unsigned long>(0) == ~0ul);
00253     assert(invert<unsigned long>(1) == ~1ul);
00254     assert(invert<unsigned long long>(0) == ~0ull);
00255     assert(invert<unsigned long long>(1) == ~1ull);
00256 
00257     assert(bitseqlengthandpos(0)   == bitseqlengthandpos_ret_t(0,0));
00258     assert(bitseqlengthandpos(1)   == bitseqlengthandpos_ret_t(0,1));
00259     assert(bitseqlengthandpos(3)   == bitseqlengthandpos_ret_t(0,2));
00260     assert(bitseqlengthandpos(7)   == bitseqlengthandpos_ret_t(0,3));
00261     assert(bitseqlengthandpos(15)  == bitseqlengthandpos_ret_t(0,4));
00262     assert(bitseqlengthandpos(31)  == bitseqlengthandpos_ret_t(0,5));
00263     assert(bitseqlengthandpos(63)  == bitseqlengthandpos_ret_t(0,6));
00264     assert(bitseqlengthandpos(127) == bitseqlengthandpos_ret_t(0,7));
00265     assert(bitseqlengthandpos(255) == bitseqlengthandpos_ret_t(0,8));
00266 
00267     assert(bitseqlengthandpos(1)   == bitseqlengthandpos_ret_t(0,1));
00268     assert(bitseqlengthandpos(2)   == bitseqlengthandpos_ret_t(1,1));
00269     assert(bitseqlengthandpos(4)   == bitseqlengthandpos_ret_t(2,1));
00270     assert(bitseqlengthandpos(8)   == bitseqlengthandpos_ret_t(3,1));
00271     assert(bitseqlengthandpos(16)  == bitseqlengthandpos_ret_t(4,1));
00272     assert(bitseqlengthandpos(32)  == bitseqlengthandpos_ret_t(5,1));
00273     assert(bitseqlengthandpos(64)  == bitseqlengthandpos_ret_t(6,1));
00274     assert(bitseqlengthandpos(128) == bitseqlengthandpos_ret_t(7,1));
00275     assert(bitseqlengthandpos(256) == bitseqlengthandpos_ret_t(8,1));
00276 
00277     assert(bitseqlengthandpos(2)   == bitseqlengthandpos_ret_t(1,1));
00278     assert(bitseqlengthandpos(6)   == bitseqlengthandpos_ret_t(1,2));
00279     assert(bitseqlengthandpos(14)  == bitseqlengthandpos_ret_t(1,3));
00280     assert(bitseqlengthandpos(30)  == bitseqlengthandpos_ret_t(1,4));
00281     assert(bitseqlengthandpos(62)  == bitseqlengthandpos_ret_t(1,5));
00282     assert(bitseqlengthandpos(126) == bitseqlengthandpos_ret_t(1,6));
00283     assert(bitseqlengthandpos(254) == bitseqlengthandpos_ret_t(1,7));
00284     assert(bitseqlengthandpos(510) == bitseqlengthandpos_ret_t(1,8));
00285 
00286     assert(bitseqlengthandpos(4)   == bitseqlengthandpos_ret_t(2,1));
00287     assert(bitseqlengthandpos(12)  == bitseqlengthandpos_ret_t(2,2));
00288     assert(bitseqlengthandpos(28)  == bitseqlengthandpos_ret_t(2,3));
00289     assert(bitseqlengthandpos(60)  == bitseqlengthandpos_ret_t(2,4));
00290     assert(bitseqlengthandpos(124) == bitseqlengthandpos_ret_t(2,5));
00291     assert(bitseqlengthandpos(252) == bitseqlengthandpos_ret_t(2,6));
00292     assert(bitseqlengthandpos(508) == bitseqlengthandpos_ret_t(2,7));
00293     assert(bitseqlengthandpos(1020)== bitseqlengthandpos_ret_t(2,8));
00294 #endif
00295 }
00296 
00297 }
00298