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