00001
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #ifndef LIBECC_BITS_H
00029 #define LIBECC_BITS_H
00030
00031 #ifndef LIBECC_DEBUG_H
00032 #error "You need to include the appropriate debug.h in the source file, before including this header file."
00033 #endif
00034
00035 #include <libecc/config.h>
00036 #include <iosfwd>
00037 #include <cstddef>
00038 #include <cstring>
00039 #include <string>
00040 #include <inttypes.h>
00041 #include <cassert>
00042 #ifdef CWDEBUG
00043 #include "debug.h"
00044 #include <libcwd/cwprint.h>
00045 #endif
00046 #define LIBECC_TRACK_EXPR_TEMPORARIES (ECC_DEBUG && 1)
00047 #if LIBECC_TRACK_EXPR_TEMPORARIES
00048 #include <set>
00049 #endif
00050
00051 #if defined(__i386__) && defined(HAVE_NASM)
00052
00053 extern "C" int libecc_shift_xorassign(unsigned long* bitset1, unsigned long const* bitset2, int lsb, int msb, int shift);
00054 extern "C" int libecc_shiftwindow_xorassign(unsigned long* bitset1, unsigned long const* bitset2, int lsb, int msb, int shift);
00055 #endif
00056
00057 namespacelibecc {
00058
00068 typedef unsigned long bitset_digit_t;
00069
00071 static unsigned int const bitset_digit_bits = sizeof(bitset_digit_t) * 8;
00072
00074 #if ECC_BITS == 32
00075 static unsigned int const bitset_digit_bits_log2 = 5;
00076 #elif ECC_BITS == 64
00077 #warning 64 bit code has not been tested. This warning will remain here until you mail me.
00078 static unsigned int const bitset_digit_bits_log2 = 6;
00079 #elif ECC_BITS == 128
00080 #warning 128 bit code has not been tested. This warning will remain here until you mail me.
00081 static unsigned int const bitset_digit_bits_log2 = 7;
00082 #endif
00083
00084
00085 template<unsigned int n, bool inverted>
00086 classbitset_invertible;
00087
00097 template<unsigned int n>
00098 structbitset_base {
00099 public:
00100
00101 static size_t const offsetof_vector = 0;
00102
00103 public:
00107 static unsigned int const number_of_bits = n;
00108
00110 static unsigned int const digits = (n - 1) / bitset_digit_bits + 1;
00111
00112
00113 static unsigned int const number_of_valid_bits = bitset_digit_bits - (digits * bitset_digit_bits - n);
00114
00116 static bitset_digit_t const valid_bits =
00117 ((static_cast<bitset_digit_t>(1) << (number_of_valid_bits - 1)) << 1) - 1;
00118
00120 static bool const has_excess_bits = ((digits * bitset_digit_bits) != n);
00121
00122 protected:
00129
00130 bitset_digit_t vector[digits];
00131
00132
00133 template<unsigned int n1, bool i1, unsigned int n2, bool i2>
00134 friend bool operator==(bitset_invertible<n1, i1> const&, bitset_invertible<n2, i2> const&);
00135
00136 template<unsigned int n1, bool i1, unsigned int n2, bool i2>
00137 friend bool operator!=(bitset_invertible<n1, i1> const&, bitset_invertible<n2, i2> const&);
00138
00139 public:
00140
00141 bitset_digit_t& rawdigit(unsigned int d) { return this->vector[d]; }
00142 bitset_digit_t const* digits_ptr(void) const{ return this->vector; }
00143 bitset_digit_t* digits_ptr(void) { return this->vector; }
00144 uint32_t digit32(unsigned int d32) const
00145 {
00146 if (sizeof(bitset_digit_t) == 4)
00147 return this->vector[d32];
00148 else
00149 {
00150 unsigned int d = d32 / (sizeof(bitset_digit_t) / 4);
00151 unsigned int r = d32 % (sizeof(bitset_digit_t) / 4);
00152 return (this->vector[d] >> (r * 32)) & 0xffffffff;
00153 }
00154 }
00155 };
00156
00157 #ifndef HIDE_FROM_DOXYGEN
00158 namespaceOperator {
00159
00160 #ifdef __i386__
00161
00162
00163
00164
00165
00166
00167
00168 #define LIBECC_INVERT "xorl $-1,%%eax\n\t"
00169 #define LIBECC_NOTHING ""
00170
00171 #define LIBECC_ASMLOOP(destination, source, count, OPCODE, OPTIONAL_INVERT) \
00172 do { \
00173 int __d0, __d1, __d2; \
00174 __asm__ __volatile__ ( \
00175 "\n1:\n\t" \
00176 "movl (%5,%%ecx,4),%%eax\n\t" \
00177 OPTIONAL_INVERT \
00178 OPCODE " %%eax,(%4,%%ecx,4)\n\t" \
00179 "decl %%ecx\n\t" \
00180 "jnz 1b" \
00181 : "=c" (__d0), "=&r" (__d1), "=&r" (__d2) \
00182 : "0" (count), \
00183 "1" ((destination) - 1), \
00184 "2" ((source) - 1) \
00185 : "%eax", "memory" \
00186 ); \
00187 } while(0)
00188
00189 #define LIBECC_ASMLOOP_BODY(OPCODE, destination, source, count, inverted) \
00190 do { \
00191 if (inverted) \
00192 LIBECC_ASMLOOP(destination, source, count, OPCODE, LIBECC_INVERT); \
00193 else \
00194 LIBECC_ASMLOOP(destination, source, count, OPCODE, LIBECC_NOTHING); \
00195 } while(0)
00196
00197 #define LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, OPTIONAL_INVERT1, OPCODE2, OPTIONAL_INVERT3) \
00198 do { \
00199 int __d0, __d1, __d2, __d3; \
00200 __asm__ __volatile__ ( \
00201 "\n1:\n\t" \
00202 "movl (%6,%%ecx,4),%%eax\n\t" \
00203 OPTIONAL_INVERT1 \
00204 OPCODE2 " (%7,%%ecx,4),%%eax\n\t" \
00205 OPTIONAL_INVERT3 \
00206 OPCODE " %%eax,(%5,%%ecx,4)\n\t" \
00207 "decl %%ecx\n\t" \
00208 "jnz 1b" \
00209 : "=c" (__d0), "=&r" (__d1), "=&r" (__d2), "=&r" (__d3) \
00210 : "0" (count), \
00211 "1" ((destination) - 1), \
00212 "2" ((source1) - 1), \
00213 "3" ((source2) - 1) \
00214 : "%eax", "memory" \
00215 ); \
00216 } while(0)
00217
00218 #define LIBECC_ASMLOOP2_BODY(OPCODE, OPERATOR, inverted1, inverted2, destination, source1, source2, count) \
00219 do { \
00220 if (OPERATOR::id == libecc::Operator::bitsetAND::id) \
00221 { \
00222 if (inverted1 && inverted2) \
00223 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "orl", LIBECC_INVERT); \
00224 else if (inverted1) \
00225 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_INVERT, "andl", LIBECC_NOTHING); \
00226 else if (inverted2) \
00227 LIBECC_ASMLOOP2(destination, source2, source1, count, OPCODE, LIBECC_INVERT, "andl", LIBECC_NOTHING); \
00228 else \
00229 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "andl", LIBECC_NOTHING); \
00230 } \
00231 else if (OPERATOR::id == libecc::Operator::bitsetOR::id) \
00232 { \
00233 if (inverted1 && inverted2) \
00234 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "andl", LIBECC_INVERT); \
00235 else if (inverted1) \
00236 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_INVERT, "orl", LIBECC_NOTHING); \
00237 else if (inverted2) \
00238 LIBECC_ASMLOOP2(destination, source2, source1, count, OPCODE, LIBECC_INVERT, "orl", LIBECC_NOTHING); \
00239 else \
00240 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "orl", LIBECC_NOTHING); \
00241 } \
00242 else if (OPERATOR::id == libecc::Operator::bitsetXOR::id) \
00243 { \
00244 if (inverted1 == inverted2) \
00245 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "xorl", LIBECC_NOTHING); \
00246 else \
00247 LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "xorl", LIBECC_INVERT); \
00248 } \
00249 } while(0)
00250
00251 #define LIBECC_INLINE_ASMLOOP(ID, destination, source, count, inverted) \
00252 do { \
00253 if (ID == libecc::Operator::bitsetAssign::id) \
00254 { \
00255 LIBECC_ASMLOOP_BODY("movl", destination, source, count, inverted); \
00256 } \
00257 else if (ID == libecc::Operator::bitsetANDAssign::id) \
00258 { \
00259 LIBECC_ASMLOOP_BODY("andl", destination, source, count, inverted); \
00260 } \
00261 else if (ID == libecc::Operator::bitsetORAssign::id) \
00262 { \
00263 LIBECC_ASMLOOP_BODY("orl", destination, source, count, inverted); \
00264 } \
00265 else if (ID == libecc::Operator::bitsetXORAssign::id) \
00266 { \
00267 LIBECC_ASMLOOP_BODY("xorl", destination, source, count, inverted); \
00268 } \
00269 } while(0)
00270
00271 #define LIBECC_INLINE_ASMLOOP2(ID, OPERATOR, inverted1, inverted2, destination, source1, source2, count) \
00272 do { \
00273 if (ID == libecc::Operator::bitsetAssign::id) \
00274 { \
00275 LIBECC_ASMLOOP2_BODY("movl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
00276 } \
00277 else if (ID == libecc::Operator::bitsetANDAssign::id) \
00278 { \
00279 LIBECC_ASMLOOP2_BODY("andl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
00280 } \
00281 else if (ID == libecc::Operator::bitsetORAssign::id) \
00282 { \
00283 LIBECC_ASMLOOP2_BODY("orl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
00284 } \
00285 else if (ID == libecc::Operator::bitsetXORAssign::id) \
00286 { \
00287 LIBECC_ASMLOOP2_BODY("xorl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
00288 } \
00289 } while(0)
00290
00291 #define LIBECC_ASMSHIFTRIGHT0(OP1) \
00292 __asm__ __volatile__ ( \
00293 "movl 4(%%esi),%%edx\n\t" \
00294 "shrl $1,%%edx\n\t" \
00295 OP1 \
00296 "movl %%edx,4(%%edi)" \
00297 : "=&S" (ptr1), \
00298 "=&D" (ptr2) \
00299 : "0" (&this->vector[initial - count]), \
00300 "1" (&result.vector[initial - count]) \
00301 : "%eax", "%edx", "memory", "cc" \
00302 )
00303
00304 #if 0 // NOT faster.
00305 #define LIBECC_OP1_SOURCE "(%%esi)"
00306 #define LIBECC_OP2_SOURCE "(%%esi)"
00307 #define LIBECC_OP1_DESTINATION "(%%edi)"
00308 #define LIBECC_OP2_DESTINATION "(%%edi)"
00309 #define LIBECC_WORKREG "%%eax"
00310 #define LIBECC_CLOBBER "%eax"
00311 #define LIBECC_INIT "std\n\t"
00312 #define LIBECC_LOAD1 "lodsl\n\t"
00313 #define LIBECC_SHIFT "shrl $1," LIBECC_WORKREG "\n\t"
00314 #define LIBECC_STORE1 "stosl\n\t"
00315 #define LIBECC_LOAD2 "lodsl\n\t"
00316 #define LIBECC_ROTATE "rcrl $1," LIBECC_WORKREG "\n\t"
00317 #define LIBECC_STORE2 "stosl\n\t"
00318 #define LIBECC_DEINIT "cld\n\t"
00319 #define LIBECC_RIGHT_PRESERVE_CF(OPERAND) "setc %%edx\n\t" OPERAND "\n\tbt $0,%%edx\n\t"
00320 #define LIBECC_PRESERVE_CF_CLOBBER LIBECC_CLOBBER,"%edx"
00321 #define LIBECC_INITIAL_ESI &this->vector[initial]
00322 #define LIBECC_INITIAL_EDI &result.vector[initial]
00323 #else
00324 #define LIBECC_OP1_SOURCE "4(%%esi,%%ecx,4)"
00325 #define LIBECC_OP2_SOURCE "(%%esi,%%ecx,4)"
00326 #define LIBECC_OP1_DESTINATION "4(%%edi,%%ecx,4)"
00327 #define LIBECC_OP2_DESTINATION "(%%edi,%%ecx,4)"
00328 #define LIBECC_WORKREG "%%edx"
00329 #define LIBECC_CLOBBER "%edx"
00330 #define LIBECC_INIT
00331 #define LIBECC_LOAD1 "movl " LIBECC_OP1_SOURCE "," LIBECC_WORKREG "\n\t"
00332 #define LIBECC_SHIFT "shrl $1," LIBECC_WORKREG "\n\t"
00333 #define LIBECC_STORE1 "movl " LIBECC_WORKREG "," LIBECC_OP1_DESTINATION "\n\t"
00334 #define LIBECC_LOAD2 "movl " LIBECC_OP2_SOURCE "," LIBECC_WORKREG "\n\t"
00335 #define LIBECC_ROTATE "rcrl $1," LIBECC_WORKREG "\n\t"
00336 #define LIBECC_STORE2 "movl " LIBECC_WORKREG "," LIBECC_OP2_DESTINATION "\n\t"
00337 #define LIBECC_DEINIT
00338 #define LIBECC_RIGHT_PRESERVE_CF(OPERAND) "lahf\n\t" OPERAND "\n\tsahf\n\t"
00339 #define LIBECC_PRESERVE_CF_CLOBBER LIBECC_CLOBBER,"%eax"
00340 #define LIBECC_INITIAL_ESI &this->vector[initial - count]
00341 #define LIBECC_INITIAL_EDI &result.vector[initial - count]
00342 #endif
00343
00344 #define LIBECC_ASMSHIFTRIGHT1(OP1, OP2, CLOBBER) \
00345 __asm__ __volatile__ ( \
00346 LIBECC_INIT \
00347 LIBECC_LOAD1 \
00348 LIBECC_SHIFT \
00349 OP1 \
00350 LIBECC_STORE1 \
00351 "1:\n\t" \
00352 LIBECC_LOAD2 \
00353 LIBECC_ROTATE \
00354 OP2 \
00355 LIBECC_STORE2 \
00356 "decl %%ecx\n\t" \
00357 "jnz 1b\n\t" \
00358 LIBECC_DEINIT \
00359 : "=&S" (ptr1), \
00360 "=&D" (ptr2), \
00361 "=&c" (c) \
00362 : "0" (LIBECC_INITIAL_ESI), \
00363 "1" (LIBECC_INITIAL_EDI), \
00364 "2" (count - 1) \
00365 : "memory", "cc", CLOBBER \
00366 )
00367
00368 #define LIBECC_ASMSHIFTLEFT(OP1, OP2, FINISH) \
00369 __asm__ __volatile__ ( \
00370 "movl -4(%%esi),%%edx\n\t" \
00371 "shll $1,%%edx\n\t" \
00372 OP1 \
00373 "movl %%edx,-4(%%edi)\n\t" \
00374 "jecxz 2f\n" \
00375 "1:\n\t" \
00376 "movl (%%esi),%%edx\n\t" \
00377 "rcll $1,%%edx\n\t" \
00378 OP2 \
00379 "movl %%edx,(%%edi)\n\t" \
00380 "leal 4(%%esi),%%esi\n\t" \
00381 "leal 4(%%edi),%%edi\n\t" \
00382 "decl %%ecx\n\t" \
00383 "jnz 1b\n" \
00384 "2:\n\t" \
00385 FINISH \
00386 : "=&S" (ptr1), \
00387 "=&D" (ptr2), \
00388 "=&c" (c) \
00389 : "0" (&this->vector[initial + 1]), \
00390 "1" (&result.vector[initial + 1]), \
00391 "2" (count - 1), \
00392 "i" (bitset_base<n>::valid_bits) \
00393 : "%eax", "%edx", "memory", "cc" \
00394 )
00395
00396 #define LIBECC_ASMSHIFTLEFT_FINISH(OP) \
00397 "movl (%%esi),%%edx\n\t" \
00398 "rcll $1,%%edx\n\t" \
00399 "andl %6,%%edx\n\t" \
00400 OP \
00401 "movl %%edx,(%%edi)"
00402
00403 #define LIBECC_LEFT_PRESERVE_CF(OPERAND) "lahf\n\t" OPERAND "\n\tsahf\n\t"
00404
00405 #endif // __i386__
00406
00407
00408
00409
00410 structbitsetAND {
00411 static int const id = 1;
00412 static inline bitset_digit_t exec(bitset_digit_t digit1, bitset_digit_t digit2) { return digit1 & digit2; }
00413 template<bool inverted1, bool inverted2>
00414 structexecbool {
00415 static bool const value = inverted1 && inverted2;
00416 };
00417 };
00418
00419
00420 structbitsetOR {
00421 static int const id = 2;
00422 static inline bitset_digit_t exec(bitset_digit_t digit1, bitset_digit_t digit2) { return digit1 | digit2; }
00423 template<bool inverted1, bool inverted2>
00424 structexecbool {
00425 static bool const value = inverted1 || inverted2;
00426 };
00427 };
00428
00429
00430 structbitsetXOR {
00431 static int const id = 3;
00432 static inline bitset_digit_t exec(bitset_digit_t digit1, bitset_digit_t digit2) { return digit1 ^ digit2; }
00433 template<bool inverted1, bool inverted2>
00434 structexecbool {
00435 static bool const value = (inverted1 != inverted2);
00436 };
00437 };
00438
00439
00440 structbitsetAssign {
00441 static int const id = 1;
00442 static bool const sets_excess_bits = true;
00443 static bool const with_zero_sets_zero = true;
00444 static bool const with_ones_sets_ones = true;
00445 static bool const with_ones_inverts = false;
00446 static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out = in; }
00447 };
00448
00449
00450 structbitsetANDAssign {
00451 static int const id = 2;
00452 static bool const sets_excess_bits = false;
00453 static bool const with_zero_sets_zero = true;
00454 static bool const with_ones_sets_ones = false;
00455 static bool const with_ones_inverts = false;
00456 static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out &= in; }
00457 };
00458
00459
00460 structbitsetORAssign {
00461 static int const id = 3;
00462 static bool const sets_excess_bits = true;
00463 static bool const with_zero_sets_zero = false;
00464 static bool const with_ones_sets_ones = true;
00465 static bool const with_ones_inverts = false;
00466 static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out |= in; }
00467 };
00468
00469
00470 structbitsetXORAssign {
00471 static int const id = 4;
00472 static bool const sets_excess_bits = true;
00473 static bool const with_zero_sets_zero = false;
00474 static bool const with_ones_sets_ones = false;
00475 static bool const with_ones_inverts = true;
00476 static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out ^= in; }
00477 };
00478
00479 #if LIBECC_TRACK_EXPR_TEMPORARIES
00480 extern std::multiset<void const*> bitsetExpression_bitset_invertible_pointers;
00481 #endif
00482
00483 template<unsigned int n, bool inverted1, bool inverted2, typename OP>
00484 structbitsetExpression
00485 {
00486 bitset_invertible<n, inverted1> const& first;
00487 bitset_invertible<n, inverted2> const& second;
00488 OP op;
00489
00490 bitsetExpression(bitset_invertible<n, inverted1> const& arg1, bitset_invertible<n, inverted2> const& arg2) :
00491 first(arg1), second(arg2)
00492 {
00493
00494
00495
00496
00497 #if LIBECC_TRACK_EXPR_TEMPORARIES
00498 bitsetExpression_bitset_invertible_pointers.insert(&arg1);
00499 bitsetExpression_bitset_invertible_pointers.insert(&arg2);
00500 LibEccDout(dc::notice, "Constructed a bitsetExpression with arguments " <<
00501 (void const*)&first << " and " << (void const*)&second);
00502 #endif
00503 }
00504 #if LIBECC_TRACK_EXPR_TEMPORARIES
00505 ~bitsetExpression();
00506 #endif
00507 };
00508
00509 #if LIBECC_TRACK_EXPR_TEMPORARIES
00510 template<unsigned int n, bool inverted1, bool inverted2, typename OP>
00511 bitsetExpression<n, inverted1, inverted2, OP>::~bitsetExpression()
00512 {
00513 bitsetExpression_bitset_invertible_pointers.erase(bitsetExpression_bitset_invertible_pointers.find(&first));
00514 bitsetExpression_bitset_invertible_pointers.erase(bitsetExpression_bitset_invertible_pointers.find(&second));
00515 LibEccDout(dc::notice, "Destructed bitsetExpression with arguments " <<
00516 (void const*)&first << " and " << (void const*)&second);
00517 }
00518 #endif
00519
00520 }
00521 #endif // HIDE_FROM_DOXYGEN
00522
00540 template<unsigned int n, bool inverted>
00541 classbitset_invertible : public bitset_base<n> {
00542 public:
00543
00544 bitset_invertible(void);
00545 template<typename Expression>
00546 explicit bitset_invertible<n, inverted>(Expression const&);
00547
00548 #if LIBECC_TRACK_EXPR_TEMPORARIES
00549 ~bitset_invertible();
00550 #endif
00551
00552 protected:
00553 template<typename OP, unsigned int x, bool invertedx>
00554 void assign(bitset_invertible<x, invertedx> const&, OP);
00555 template<typename OP1, unsigned int x, bool inverted1, bool inverted2, typename OP2>
00556 void assign(Operator::bitsetExpression<x, inverted1, inverted2, OP2> const&, OP1);
00557
00558 private:
00559 template<unsigned int m, bool i>
00560 friend classbitset_invertible;
00561 template<unsigned int m, int DIRECTION>
00562 friend classbitset_iterator;
00563
00564 public:
00566 void base2_print_on(std::ostream& os) const;
00567
00569 bitset_digit_t digit(unsigned int d) const{ assert(!inverted); return inverted ? ~this->vector[d] : this->vector[d]; }
00570 };
00571
00572 #if LIBECC_TRACK_EXPR_TEMPORARIES
00573 template<unsigned int n, bool inverted>
00574 bitset_invertible<n, inverted>::~bitset_invertible()
00575 {
00576 LibEccDout(dc::notice, "Destructing bitset_invertible at " << (void*)this);
00577 if (Operator::bitsetExpression_bitset_invertible_pointers.find(this) !=
00578 Operator::bitsetExpression_bitset_invertible_pointers.end())
00579 LibEccDoutFatal(dc::core, "This object is still in use by a bitsetExpression!");
00580 }
00581 #endif
00582
00594 template<unsigned int n, bool inverted>
00595 void
00596 bitset_invertible<n, inverted>::base2_print_on(std::ostream& os) const
00597 {
00598
00599 for (int d = bitset_base<n>::digits - 1; d >= 0; --d)
00600 for (bitset_digit_t mask = (~static_cast<bitset_digit_t>(0) >> 1) + 1; mask != 0; mask >>= 1)
00601 if (d != bitset_base<n>::digits - 1 || (mask & bitset_base<n>::valid_bits))
00602 if ((this->digit(d) & mask) == inverted)
00603 os << '0';
00604 else
00605 os << '1';
00606 }
00607
00608
00609 template<unsigned int n, bool inverted>
00610 inline
00611 bitset_invertible<n, inverted>::bitset_invertible(void)
00612 {
00613 if (bitset_base<n>::has_excess_bits)
00614 this->vector[bitset_base<n>::digits - 1] = 0;
00615 }
00616
00617
00618 template<unsigned int n, bool inverted>
00619 template<typename Expression>
00620 inline
00621 bitset_invertible<n, inverted>::bitset_invertible(Expression const& expr)
00622 {
00623 this->assign(expr, Operator::bitsetAssign());
00624 }
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641 template<unsigned int n, bool inverted>
00642 template<typename ASSIGNMENT_OPERATOR, unsigned int x, bool inverted_argument>
00643 inline void
00644 bitset_invertible<n, inverted>::assign(bitset_invertible<x, inverted_argument> const& bits, ASSIGNMENT_OPERATOR)
00645 {
00646
00647 if (bitset_base<n>::digits > bitset_base<x>::digits)
00648 {
00649 if (!inverted_argument)
00650 {
00651
00652 if (ASSIGNMENT_OPERATOR::with_zero_sets_zero)
00653 {
00654 #ifdef __i386__
00655 int __d0, __d1;
00656 __asm__ __volatile__ (
00657 "std; rep; stosl"
00658 : "=m" (this->vector[bitset_base<n>::digits - 1]), "=&c" (__d0), "=&D" (__d1)
00659 : "a" (0), "1" (bitset_base<n>::digits - bitset_base<x>::digits), "2" (&this->vector[bitset_base<n>::digits - 1])
00660 : "memory"
00661 );
00662 #else
00663 unsigned int count = bitset_base<n>::digits - bitset_base<x>::digits;
00664 do { this->vector[count + bitset_base<x>::digits - 1] = 0; } while (--count);
00665 #endif
00666 }
00667 }
00668 else
00669 {
00670
00671 if (ASSIGNMENT_OPERATOR::with_ones_sets_ones)
00672 {
00673 #ifdef __i386__
00674 int __d0, __d1;
00675 __asm__ __volatile__ (
00676 "movl %6,4(%%edi); std; rep; stosl"
00677 : "=m" (this->vector[bitset_base<n>::digits - 2]), "=&c" (__d0), "=&D" (__d1)
00678 : "a" (-1), "1" (bitset_base<n>::digits - bitset_base<x>::digits - 1), "2" (&this->vector[bitset_base<n>::digits - 2]), "i" (bitset_base<n>::valid_bits)
00679 : "memory"
00680 );
00681 #else
00682 this->vector[bitset_base<n>::digits - 1] = bitset_base<n>::valid_bits;
00683 unsigned int count = bitset_base<n>::digits - bitset_base<x>::digits;
00684 while(--count) { this->vector[count + bitset_base<x>::digits - 1] = ~static_cast<bitset_digit_t>(0); }
00685 #endif
00686 }
00687
00688 if (ASSIGNMENT_OPERATOR::with_ones_inverts)
00689 {
00690 #ifdef __i386__
00691 int __d0, __d1;
00692 __asm__ __volatile__ (
00693 "xorl %5,(%2)\n\t"
00694 "jecxz 2f\n\t"
00695 "subl %6,%2\n"
00696 "1:\n\t"
00697 "xorl $-1,(%2,%%ecx,4)\n\t"
00698 "decl %%ecx\n\t"
00699 "jnz 1b\n"
00700 "2:"
00701 : "=m" (this->vector[bitset_base<n>::digits - 1]), "=&c" (__d0), "=&r" (__d1)
00702 : "1" (bitset_base<n>::digits - bitset_base<x>::digits - 1), "2" (&this->vector[bitset_base<n>::digits - 1]),
00703 "i" (bitset_base<n>::valid_bits), "i" ((bitset_base<n>::digits - bitset_base<x>::digits) * 4)
00704 : "memory", "cc"
00705 );
00706 #else
00707 this->vector[bitset_base<n>::digits - 1] ^= bitset_base<n>::valid_bits;
00708 unsigned int count = bitset_base<n>::digits - bitset_base<x>::digits;
00709 while(--count) { this->vector[count + bitset_base<x>::digits - 1] ^= ~static_cast<bitset_digit_t>(0); }
00710 #endif
00711 }
00712 }
00713 }
00714
00715
00716 #ifdef __i386__
00717 LIBECC_INLINE_ASMLOOP(ASSIGNMENT_OPERATOR::id,
00718 this->vector, bits.digits_ptr(),
00719 ((bitset_base<n>::digits > bitset_base<x>::digits) ? bitset_base<x>::digits : bitset_base<n>::digits),
00720 inverted_argument);
00721 #else
00722 unsigned int d;
00723 if (bitset_base<n>::digits > bitset_base<x>::digits)
00724 d = bitset_base<x>::digits - 1;
00725 else
00726 d = bitset_base<n>::digits - 1;
00727 ASSIGNMENT_OPERATOR::exec(this->vector[d], inverted_argument ? ~*(bits.digits_ptr() + d) : bits.digit(d));
00728 while(d) { --d; ASSIGNMENT_OPERATOR::exec(this->vector[d], inverted_argument ? ~*(bits.digits_ptr() + d) : bits.digit(d)); }
00729 #endif
00730
00731
00732 if (((!inverted_argument && x > n) ||
00733 (inverted_argument && bitset_base<n>::digits <= bitset_base<x>::digits)) &&
00734 bitset_base<n>::has_excess_bits && ASSIGNMENT_OPERATOR::sets_excess_bits)
00735 this->vector[bitset_base<n>::digits - 1] &= bitset_base<n>::valid_bits;
00736 }
00737
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780
00781
00782
00783
00784
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794 template<unsigned int n, bool inverted>
00795 template<typename ASSIGNMENT_OPERATOR, unsigned int x, bool inverted1, bool inverted2, typename OPERATOR>
00796 inline void
00797 bitset_invertible<n, inverted>::assign(Operator::bitsetExpression<x, inverted1, inverted2, OPERATOR> const& expr, ASSIGNMENT_OPERATOR)
00798 {
00799 static bool const argument_has_leading_ones = OPERATOR::template execbool<inverted1, inverted2>::value;
00800
00801
00802 if (bitset_base<n>::digits > bitset_base<x>::digits)
00803 {
00804 if (!argument_has_leading_ones)
00805 {
00806
00807 if (ASSIGNMENT_OPERATOR::with_zero_sets_zero)
00808 {
00809 #ifdef __i386__
00810 int __d0, __d1;
00811 __asm__ __volatile__ (
00812 "std; rep; stosl"
00813 : "=m" (this->vector[bitset_base<n>::digits - 1]), "=&c" (__d0), "=&D" (__d1)
00814 : "a" (0), "1" (bitset_base<n>::digits - bitset_base<x>::digits), "2" (&this->vector[bitset_base<n>::digits - 1])
00815 : "memory"
00816 );
00817 #else
00818 unsigned int count = bitset_base<n>::digits - bitset_base<x>::digits;
00819 do { this->vector[count + bitset_base<x>::digits - 1] = 0; } while (--count);
00820 #endif
00821 }
00822 }
00823 else
00824 {
00825
00826 if (ASSIGNMENT_OPERATOR::with_ones_sets_ones)
00827 {
00828 #ifdef __i386__
00829 int __d0, __d1;
00830 __asm__ __volatile__ (
00831 "movl %6,4(%%edi); std; rep; stosl"
00832 : "=m" (this->vector[bitset_base<n>::digits - 2]), "=&c" (__d0), "=&D" (__d1)
00833 : "a" (-1), "1" (bitset_base<n>::digits - bitset_base<x>::digits - 1), "2" (&this->vector[bitset_base<n>::digits - 2]), "i" (bitset_base<n>::valid_bits)
00834 : "memory"
00835 );
00836 #else
00837 this->vector[bitset_base<n>::digits - 1] = bitset_base<n>::valid_bits;
00838 unsigned int count = bitset_base<n>::digits - bitset_base<x>::digits;
00839 while(--count) { this->vector[count + bitset_base<x>::digits - 1] = ~static_cast<bitset_digit_t>(0); }
00840 #endif
00841 }
00842
00843 if (ASSIGNMENT_OPERATOR::with_ones_inverts)
00844 {
00845 #ifdef __i386__
00846 int __d0, __d1;
00847 __asm__ __volatile__ (
00848 "xorl %5,(%2)\n\t"
00849 "jecxz 2f\n\t"
00850 "subl %6,%2\n"
00851 "1:\n\t"
00852 "xorl $-1,(%2,%%ecx,4)\n\t"
00853 "decl %%ecx\n\t"
00854 "jnz 1b\n"
00855 "2:"
00856 : "=m" (this->vector[bitset_base<n>::digits - 1]), "=&c" (__d0), "=&r" (__d1)
00857 : "1" (bitset_base<n>::digits - bitset_base<x>::digits - 1), "2" (&this->vector[bitset_base<n>::digits - 1]),
00858 "i" (bitset_base<n>::valid_bits), "i" ((bitset_base<n>::digits - bitset_base<x>::digits) * 4)
00859 : "memory", "cc"
00860 );
00861 #else
00862 this->vector[bitset_base<n>::digits - 1] ^= bitset_base<n>::valid_bits;
00863 unsigned int count = bitset_base<n>::digits - bitset_base<x>::digits;
00864 while(--count) { this->vector[count + bitset_base<x>::digits - 1] ^= ~static_cast<bitset_digit_t>(0); }
00865 #endif
00866 }
00867 }
00868 }
00869
00870
00871 #ifdef __i386__
00872 LIBECC_INLINE_ASMLOOP2(ASSIGNMENT_OPERATOR::id, OPERATOR, inverted1, inverted2,
00873 this->vector, expr.first.digits_ptr(), expr.second.digits_ptr(),
00874 ((bitset_base<n>::digits > bitset_base<x>::digits) ? bitset_base<x>::digits : bitset_base<n>::digits));
00875 #else
00876 unsigned int d;
00877 if (bitset_base<n>::digits < bitset_base<x>::digits)
00878 d = bitset_base<n>::digits - 1;
00879 else
00880 d = bitset_base<x>::digits - 1;
00881 for(;;)
00882 {
00883 ASSIGNMENT_OPERATOR::exec(this->vector[d],
00884 OPERATOR::exec(inverted1 ? ~*(expr.first.digits_ptr() + d) : expr.first.digit(d),
00885 inverted2 ? ~*(expr.second.digits_ptr() + d) : expr.second.digit(d)));
00886 if (!d)
00887 break;
00888 --d;
00889 }
00890 #endif
00891
00892
00893 if (((!argument_has_leading_ones && x > n) ||
00894 (argument_has_leading_ones && bitset_base<n>::digits <= bitset_base<x>::digits)) &&
00895 bitset_base<n>::has_excess_bits && ASSIGNMENT_OPERATOR::sets_excess_bits)
00896 this->vector[bitset_base<n>::digits - 1] &= bitset_base<n>::valid_bits;
00897 }
00898
00925 template<unsigned int n, bool inverted>
00926 inline bitset_invertible<n, !inverted> const&
00927 operator~(bitset_invertible<n, inverted> const& bits)
00928 {
00929 return *reinterpret_cast<bitset_invertible<n, !inverted> const*>(&bits);
00930 }
00931
00932
00933
00934
00935
00945 classbitset_index {
00946 #if defined(__i386__) || defined(LIBECC_DOXYGEN)
00947 protected:
00948 int M_index;
00949
00950 public:
00951
00952 int get_index(void) const;
00953
00954 #else
00955 protected:
00956 int M_digit;
00957 bitset_digit_t M_mask;
00958
00959 public:
00960
00961 int get_digit(void) const;
00962 bitset_digit_t get_mask(void) const;
00963 #endif
00964
00965 public:
00966
00967 friend bool operator==(bitset_index const& i1, bitset_index const& i2);
00968 friend bool operator!=(bitset_index const& i1, bitset_index const& i2);
00969
00970 protected:
00971
00972 void left(void);
00973 void right(void);
00974
00975
00976 void left(int n);
00977 void right(int n);
00978 friend int subtract(bitset_index const& i1, bitset_index const& i2);
00979
00980 protected:
00981
00982 bitset_index(void);
00983 bitset_index(bitset_index const& index);
00984 bitset_index(int bit);
00985
00986 public:
00987 friend std::ostream& operator<<(std::ostream& os, bitset_index const& i);
00988 };
00989
00990 #if defined(__i386__) || defined(LIBECC_DOXYGEN)
00991
00995 inline int
00996 bitset_index::get_index(void) const
00997 {
00998 return M_index;
00999 }
01000
01001 #else // !defined(__i386__)
01002
01003
01004 inline int
01005 bitset_index::get_digit(void) const
01006 {
01007 return M_digit;
01008 }
01009
01010
01011 inline bitset_digit_t
01012 bitset_index::get_mask(void) const
01013 {
01014 return M_mask;
01015 }
01016
01017 #if 0
01018 #include <strings.h>
01019 inline int
01020 bitset_index::get_index(void) const
01021 {
01022 return M_digit * bitset_digit_bits + ::ffs(M_mask) - 1;
01023 }
01024 #endif
01025
01026 #endif // !defined(__i386__)
01027
01031 inline bool
01032 operator==(bitset_index const& i1, bitset_index const& i2)
01033 {
01034 #ifdef __i386__
01035 return (i1.M_index == i2.M_index);
01036 #else
01037 return (i1.M_digit == i2.M_digit && i1.M_mask == i2.M_mask);
01038 #endif
01039 }
01040
01044 inline bool
01045 operator!=(bitset_index const& i1, bitset_index const& i2)
01046 {
01047 #ifdef __i386__
01048 return (i1.M_index != i2.M_index);
01049 #else
01050 return (i1.M_digit != i2.M_digit || i1.M_mask != i2.M_mask);
01051 #endif
01052 }
01053
01057 inline
01058 bitset_index::bitset_index(void)
01059 {
01060 }
01061
01065 inline
01066 bitset_index::bitset_index(bitset_index const& index) :
01067 #ifdef __i386__
01068 M_index(index.M_index)
01069 #else
01070 M_digit(index.M_digit), M_mask(index.M_mask)
01071 #endif
01072 {
01073 }
01074
01081 inline
01082 bitset_index::bitset_index(int bit) :
01083 #ifdef __i386__
01084 M_index(bit)
01085 #else
01086
01087 M_digit(bit >> bitset_digit_bits_log2),
01088 M_mask(static_cast<bitset_digit_t>(1) << ((unsigned int)bit & (bitset_digit_bits - 1)))
01089 #endif
01090 {
01091 }
01092
01096 inline void
01097 bitset_index::left(void)
01098 {
01099 #ifdef __i386__
01100 ++M_index;
01101 #else
01102 if ((M_mask <<= 1) == 0)
01103 {
01104 ++M_digit;
01105 M_mask = 1;
01106 }
01107 #endif
01108 }
01109
01113 inline void
01114 bitset_index::right(void)
01115 {
01116 #ifdef __i386__
01117 --M_index;
01118 #else
01119 if ((M_mask >>= 1) == 0)
01120 {
01121 --M_digit;
01122 M_mask = static_cast<bitset_digit_t>(1) << (bitset_digit_bits - 1);
01123 }
01124 #endif
01125 }
01126
01130 inline void
01131 bitset_index::left(int n)
01132 {
01133 #ifdef __i386__
01134 M_index += n;
01135 #else
01136 int const digit_shift = n >> bitset_digit_bits_log2;
01137 int const mask_shift = n & (bitset_digit_bits - 1);
01138 M_digit += digit_shift;
01139 if (mask_shift)
01140 {
01141 bitset_digit_t new_mask = M_mask << mask_shift;
01142 if (new_mask == 0)
01143 {
01144 ++M_digit;
01145 new_mask = M_mask >> (bitset_digit_bits - mask_shift);
01146 }
01147 M_mask = new_mask;
01148 }
01149 #endif
01150 }
01151
01155 inline void
01156 bitset_index::right(int n)
01157 {
01158 #ifdef __i386__
01159 M_index -= n;
01160 #else
01161 int const digit_shift = n >> bitset_digit_bits_log2;
01162 int const mask_shift = n & (bitset_digit_bits - 1);
01163 M_digit -= digit_shift;
01164 if (mask_shift)
01165 {
01166 bitset_digit_t new_mask = M_mask >> mask_shift;
01167 if (new_mask == 0)
01168 {
01169 --M_digit;
01170 new_mask = M_mask << (bitset_digit_bits - mask_shift);
01171 }
01172 M_mask = new_mask;
01173 }
01174 #endif
01175 }
01176
01177 enum {
01178 forwards_iterating,
01179 backwards_iterating
01180 };
01181
01182
01183 template<int DIRECTION> classbitset_index_iterator;
01184 template<int DIRECTION> bool operator<(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);
01185 template<int DIRECTION> bool operator>(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);
01186 template<int DIRECTION> bool operator<=(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);
01187 template<int DIRECTION> bool operator>=(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);
01188
01197 template<int DIRECTION>
01198 classbitset_index_iterator : public bitset_index {
01199 public:
01200
01201 friend bool operator< <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);
01202 friend bool operator> <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);
01203 friend bool operator<= <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);
01204 friend bool operator>= <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);
01205
01206 public:
01207
01208 void increment(void);
01209 void decrement(void);
01210
01211
01212 void increment(int n);
01213 void decrement(int n);
01214
01215 friend int operator-(bitset_index const& i1, bitset_index const& i2);
01216
01217 public:
01218
01219 bitset_index_iterator(void);
01220 bitset_index_iterator(bitset_index_iterator const& index);
01221 bitset_index_iterator(int bit);
01222 };
01223
01227 template<int DIRECTION>
01228 inline
01229 bitset_index_iterator<DIRECTION>::bitset_index_iterator(void)
01230 {
01231 }
01232
01236 template<int DIRECTION>
01237 inline
01238 bitset_index_iterator<DIRECTION>::bitset_index_iterator(bitset_index_iterator<DIRECTION> const& index) :
01239 bitset_index(index)
01240 {
01241 }
01242
01249 template<int DIRECTION>
01250 inline
01251 bitset_index_iterator<DIRECTION>::bitset_index_iterator(int bit) : bitset_index(bit)
01252 {
01253 }
01254
01258 template<int DIRECTION>
01259 inline bool
01260 operator<(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
01261 {
01262 #ifdef __i386__
01263 if (DIRECTION == forwards_iterating)
01264 return (i1.M_index < i2.M_index);
01265 else
01266 return (i1.M_index > i2.M_index);
01267 #else
01268 if (DIRECTION == forwards_iterating)
01269 return (i1.M_digit < i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask < i2.M_mask));
01270 else
01271 return (i1.M_digit > i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask > i2.M_mask));
01272 #endif
01273 }
01274
01278 template<int DIRECTION>
01279 inline bool
01280 operator>(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
01281 {
01282 #ifdef __i386__
01283 if (DIRECTION == forwards_iterating)
01284 return (i1.M_index > i2.M_index);
01285 else
01286 return (i1.M_index < i2.M_index);
01287 #else
01288 if (DIRECTION == forwards_iterating)
01289 return (i1.M_digit > i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask > i2.M_mask));
01290 else
01291 return (i1.M_digit < i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask < i2.M_mask));
01292 #endif
01293 }
01294
01298 template<int DIRECTION>
01299 inline bool
01300 operator<=(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
01301 {
01302 #ifdef __i386__
01303 if (DIRECTION == forwards_iterating)
01304 return (i1.M_index <= i2.M_index);
01305 else
01306 return (i1.M_index >= i2.M_index);
01307 #else
01308 if (DIRECTION == forwards_iterating)
01309 return (i1.M_digit <= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask <= i2.M_mask));
01310 else
01311 return (i1.M_digit >= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask >= i2.M_mask));
01312 #endif
01313 }
01314
01318 template<int DIRECTION>
01319 inline bool
01320 operator>=(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
01321 {
01322 #ifdef __i386__
01323 if (DIRECTION == forwards_iterating)
01324 return (i1.M_index >= i2.M_index);
01325 else
01326 return (i1.M_index <= i2.M_index);
01327 #else
01328 if (DIRECTION == forwards_iterating)
01329 return (i1.M_digit >= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask >= i2.M_mask));
01330 else
01331 return (i1.M_digit <= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask <= i2.M_mask));
01332 #endif
01333 }
01334
01338 template<int DIRECTION>
01339 inline void
01340 bitset_index_iterator<DIRECTION>::increment(void)
01341 {
01342 if (DIRECTION == forwards_iterating)
01343 left();
01344 else
01345 right();
01346 }
01347
01351 template<int DIRECTION>
01352 inline void
01353 bitset_index_iterator<DIRECTION>::decrement(void)
01354 {
01355 if (DIRECTION == forwards_iterating)
01356 right();
01357 else
01358 left();
01359 }
01360
01364 template<int DIRECTION>
01365 inline void
01366 bitset_index_iterator<DIRECTION>::increment(int n)
01367 {
01368 if (DIRECTION == forwards_iterating)
01369 left(n);
01370 else
01371 right(n);
01372 }
01373
01377 template<int DIRECTION>
01378 inline void
01379 bitset_index_iterator<DIRECTION>::decrement(int n)
01380 {
01381 if (DIRECTION == forwards_iterating)
01382 right(n);
01383 else
01384 left(n);
01385 }
01386
01387 template<int DIRECTION>
01388 inline int
01389 operator-(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
01390 {
01391 return (DIRECTION == forwards_iterating) ? subtract(i1, i2) : subtract(i2, i1);
01392 }
01393
01394
01395 template<unsigned int n, int DIRECTION> classbitset_iterator;
01396 template<unsigned int n, int DIRECTION> bitset_iterator<n, DIRECTION> operator+(bitset_iterator<n, DIRECTION> const&, int);
01397 template<unsigned int n, int DIRECTION> bitset_iterator<n, DIRECTION> operator+(int, bitset_iterator<n, DIRECTION> const&);
01398 template<unsigned int n, int DIRECTION> bitset_iterator<n, DIRECTION> operator-(bitset_iterator<n, DIRECTION> const&, int);
01399 template<unsigned int n, int DIRECTION> bitset_iterator<n, DIRECTION> operator-(int, bitset_iterator<n, DIRECTION> const&);
01400
01410 template<unsigned int n, int DIRECTION>
01411 classbitset_iterator : public bitset_index_iterator<DIRECTION>,
01412 public std::iterator<std::random_access_iterator_tag, bitset_digit_t,
01413 int, bitset_digit_t*, bitset_digit_t&> {
01414 protected:
01415 bitset_invertible<n, false> const* M_bitset_ptr;
01416 public:
01417
01418 bitset_iterator(void);
01419
01420
01421 bitset_iterator(bitset_iterator const& iter);
01422 bitset_iterator& operator=(bitset_iterator const& iter);
01423 bitset_iterator& operator=(bitset_index_iterator<DIRECTION> const& index);
01424
01425
01426 bitset_digit_t operator*() const;
01427
01428
01429
01430 bitset_iterator& operator++();
01431 bitset_iterator operator++(int);
01432 bitset_iterator& operator--();
01433 bitset_iterator operator--(int);
01434
01435
01436
01437 bitset_iterator& operator+=(int n);
01438 friend bitset_iterator operator+ <>(bitset_iterator const& i, int n);
01439 friend bitset_iterator operator+ <>(int n, bitset_iterator const& i);
01440 bitset_iterator& operator-=(int n);
01441 friend bitset_iterator operator- <>(bitset_iterator const& i, int n);
01442 friend bitset_iterator operator- <>(int n, bitset_iterator const& i);
01443 bitset_digit_t operator[](int n) const;
01444
01445
01446
01447 bitset_iterator(bitset_invertible<n, false> const* bitset_ptr, int bit);
01448 void find1(void);
01449
01450 #ifndef __i386__
01451 private:
01452 void find1_forward(void);
01453 void find1_backward(void);
01454 #endif
01455 };
01456
01457 #ifndef __i386__
01458 template<unsigned int n, int DIRECTION>
01459 void
01460 bitset_iterator<n, DIRECTION>::find1_forward(void)
01461 {
01462 if (this->M_digit < (int)bitset_base<n>::digits - 1 || (this->M_mask & bitset_base<n>::valid_bits))
01463 {
01464 register bitset_digit_t mask = this->M_mask;
01465 while(!(M_bitset_ptr->digit(this->M_digit) & mask))
01466 {
01467 if ((mask <<= 1))
01468 continue;
01469 mask = 1;
01470 while(++(this->M_digit) < (int)bitset_base<n>::digits)
01471 if (M_bitset_ptr->digit(this->M_digit))
01472 break;
01473 if (this->M_digit == (int)bitset_base<n>::digits)
01474 {
01475 this->M_digit = (n >> bitset_digit_bits_log2);
01476 mask = static_cast<bitset_digit_t>(1) << (n & (bitset_digit_bits - 1));
01477 break;
01478 }
01479 }
01480 this->M_mask = mask;
01481 }
01482 }
01483
01484 template<unsigned int n, int DIRECTION>
01485 void
01486 bitset_iterator<n, DIRECTION>::find1_backward(void)
01487 {
01488 LibEccDout(dc::bitsetfind1, "Entering find1_backward with: " <<
01489 libcwd::cwprint_using(*M_bitset_ptr, &bitset_invertible<n, false>::base2_print_on));
01490 LibEccDout(dc::bitsetfind1, "Input: " << *this);
01491 if (this->M_digit >= 0)
01492 {
01493 register bitset_digit_t mask = this->M_mask;
01494 if (!(M_bitset_ptr->digit(this->M_digit) & (mask | (mask - 1))))
01495 {
01496 mask = 1 << (bitset_digit_bits - 1);
01497 do
01498 {
01499 if (--(this->M_digit) < 0)
01500 {
01501 this->M_mask = mask;
01502 return;
01503 }
01504 }
01505 while (!M_bitset_ptr->digit(this->M_digit));
01506 }
01507 while(!(M_bitset_ptr->digit(this->M_digit) & mask))
01508 mask >>= 1;
01509 this->M_mask = mask;
01510 }
01511 LibEccDout(dc::bitsetfind1|flush_cf, "Output: " << *this);
01512 }
01513 #endif
01514
01518 template<unsigned int n, int DIRECTION>
01519 inline void
01520 bitset_iterator<n, DIRECTION>::find1(void)
01521 {
01522 LibEccDout(dc::bitsetfind1, "Input: " << *this);
01523 LibEccDout(dc::bitsetfind1, "Entering find1 with: " <<
01524 libcwd::cwprint_using(*M_bitset_ptr, &bitset_invertible<n, false>::base2_print_on));
01525 #ifdef __i386__
01526 int bit_index, digit, ptr;
01527 if (DIRECTION == backwards_iterating)
01528 {
01529 __asm__ __volatile__ (
01530
01531
01532
01533
01534
01535
01536 "movl %%eax,%%ecx\n\t"
01537
01538 "sarl $5,%%eax\n\t"
01539
01540 "andl $31,%%ecx\n\t"
01541
01542 "js 1f\n\t"
01543
01544
01545
01546 "movl 4(%%edi),%2\n\t"
01547
01548
01549 "xorl $31,%%ecx\n\t"
01550
01551 "shll %%cl,%2\n\t"
01552
01553
01554
01555 "orl %2,%2\n\t"
01556
01557 "jz 5f\n\t"
01558
01559
01560 "bsrl %2,%2\n\t"
01561
01562
01563 "sall $5,%%eax\n\t"
01564
01565 "subl %%ecx,%2\n\t"
01566
01567 "addl %2,%%eax\n\t"
01568
01569
01570 "jmp 1f\n\t"
01571 ".align 16\n"
01572 "7:\n\t"
01573 "movl (%%edi),%2\n\t"
01574 "subl $4,%%edi\n\t"
01575 "testl %2,%2\n\t"
01576 "jnz 6f\n\t"
01577 "5:\n\t"
01578 "decl %%eax\n\t"
01579
01580 "jns 7b\n"
01581 "4:\n\t"
01582
01583 "movl $-1,%%eax\n\t"
01584
01585
01586 "jmp 1f\n"
01587
01588 "6:\n\t"
01589 "bsrl %2,%2\n\t"
01590
01591 "sall $5,%%eax\n\t"
01592 "addl %2,%%eax\n"
01593 "1:"
01594
01595 : "=a" (this->M_index), "=&c" (bit_index), "=r" (digit), "=&D" (ptr)
01596 : "0" (this->M_index), "3" (M_bitset_ptr->digits_ptr() - 1 + (this->M_index >> 5))
01597 : "cc"
01598 );
01599 }
01600 else
01601 {
01602 __asm__ __volatile__ (
01603
01604
01605
01606
01607
01608
01609 "cmpl %6,%%eax\n\t"
01610 "jge 1f\n\t"
01611
01612 "movl %%eax,%%ecx\n\t"
01613
01614 "sarl $5,%%eax\n\t"
01615
01616 "andl $31,%%ecx\n\t"
01617
01618
01619
01620 "movl -4(%%edi),%2\n\t"
01621
01622
01623 "shrl %%cl,%2\n\t"
01624
01625
01626
01627 "orl %2,%2\n\t"
01628
01629 "jz 5f\n\t"
01630
01631
01632 "bsfl %2,%2\n\t"
01633
01634
01635 "sall $5,%%eax\n\t"
01636
01637 "addl %%ecx,%2\n\t"
01638
01639 "addl %2,%%eax\n\t"
01640
01641
01642 "jmp 1f\n\t"
01643 ".align 16\n"
01644 "7:\n\t"
01645 "movl (%%edi),%2\n\t"
01646 "addl $4,%%edi\n\t"
01647 "testl %2,%2\n\t"
01648 "jnz 6f\n\t"
01649 "5:\n\t"
01650 "incl %%eax\n\t"
01651 "cmpl %7, %%eax\n\t"
01652
01653 "jnz 7b\n"
01654 "4:\n\t"
01655
01656 "movl %6,%%eax\n\t"
01657
01658
01659 "jmp 1f\n"
01660
01661 "6:\n\t"
01662 "bsfl %2,%2\n\t"
01663
01664 "sall $5,%%eax\n\t"
01665 "addl %2,%%eax\n"
01666 "1:"
01667
01668 : "=a" (this->M_index), "=&c" (bit_index), "=r" (digit), "=&D" (ptr)
01669 : "0" (this->M_index), "3" (M_bitset_ptr->digits_ptr() + 1 + (this->M_index >> 5)),
01670 "i" (n), "i" (bitset_base<n>::digits)
01671 : "cc"
01672 );
01673 }
01674 #else
01675 if (DIRECTION == forwards_iterating)
01676 find1_forward();
01677 else
01678 find1_backward();
01679 #endif
01680 LibEccDout(dc::bitsetfind1|flush_cf, "Output: " << *this);
01681 return;
01682 }
01683
01684
01688 template<unsigned int n, int DIRECTION>
01689 inline
01690 bitset_iterator<n, DIRECTION>::bitset_iterator(void)
01691 {
01692 }
01693
01697 template<unsigned int n, int DIRECTION>
01698 inline
01699 bitset_iterator<n, DIRECTION>::bitset_iterator(bitset_invertible<n, false> const* bitset_ptr, int bit) :
01700 bitset_index_iterator<DIRECTION>(bit), M_bitset_ptr(bitset_ptr)
01701 {
01702 }
01703
01707 template<unsigned int n, int DIRECTION>
01708 inline
01709 bitset_iterator<n, DIRECTION>::bitset_iterator(bitset_iterator const& iter) :
01710 bitset_index_iterator<DIRECTION>(iter), M_bitset_ptr(iter.M_bitset_ptr)
01711 {
01712 }
01713
01717 template<unsigned int n, int DIRECTION>
01718 inline bitset_iterator<n, DIRECTION>&
01719 bitset_iterator<n, DIRECTION>::operator=(bitset_iterator<n, DIRECTION> const& iter)
01720 {
01721 #ifdef __i386__
01722 this->M_index = iter.M_index;
01723 #else
01724 this->M_digit = iter.M_digit;
01725 this->M_mask = iter.M_mask;
01726 #endif
01727 M_bitset_ptr = iter.M_bitset_ptr;
01728 return *this;
01729 }
01730
01731 template<unsigned int n, int DIRECTION>
01732 inline bitset_iterator<n, DIRECTION>&
01733 bitset_iterator<n, DIRECTION>::operator=(bitset_index_iterator<DIRECTION> const& index)
01734 {
01735 #ifdef __i386__
01736 this->M_index = index.get_index();
01737 #else
01738 this->M_digit = index.get_digit();
01739 this->M_mask = index.get_mask();
01740 #endif
01741 return *this;
01742 }
01743
01747 template<unsigned int n, int DIRECTION>
01748 inline bitset_iterator<n, DIRECTION>&
01749 bitset_iterator<n, DIRECTION>::operator++()
01750 {
01751 this->increment();
01752 return *this;
01753 }
01754
01758 template<unsigned int n, int DIRECTION>
01759 inline bitset_iterator<n, DIRECTION>
01760 bitset_iterator<n, DIRECTION>::operator++(int)
01761 {
01762 bitset_iterator prev(*this);
01763 this->increment();
01764 return prev;
01765 }
01766
01770 template<unsigned int n, int DIRECTION>
01771 inline bitset_iterator<n, DIRECTION>&
01772 bitset_iterator<n, DIRECTION>::operator--()
01773 {
01774 this->decrement();
01775 return *this;
01776 }
01777
01781 template<unsigned int n, int DIRECTION>
01782 inline bitset_iterator<n, DIRECTION>
01783 bitset_iterator<n, DIRECTION>::operator--(int)
01784 {
01785 bitset_iterator prev(*this);
01786 this->decrement();
01787 return prev;
01788 }
01789
01796 template<unsigned int n, int DIRECTION>
01797 inline bitset_digit_t
01798 bitset_iterator<n, DIRECTION>::operator*() const
01799 {
01800 #ifdef __i386__
01801 register unsigned int digit = this->M_index;
01802 register bitset_digit_t mask = 1;
01803 register unsigned short shift = this->M_index & (ECC_BITS - 1);
01804 digit >>= bitset_digit_bits_log2;
01805 mask <<= shift;
01806 return (M_bitset_ptr->digit(digit) & mask);
01807 #else
01808 return (M_bitset_ptr->digit(this->M_digit) & this->M_mask);
01809 #endif
01810 }
01811
01815 template<unsigned int n, int DIRECTION>
01816 inline bitset_iterator<n, DIRECTION>&
01817 bitset_iterator<n, DIRECTION>::operator+=(int d)
01818 {
01819 this->increment(d);
01820 return *this;
01821 }
01822
01826 template<unsigned int n, int DIRECTION>
01827 inline bitset_iterator<n, DIRECTION>&
01828 bitset_iterator<n, DIRECTION>::operator-=(int d)
01829 {
01830 this->decrement(d);
01831 return *this;
01832 }
01833
01837 template<unsigned int n, int DIRECTION>
01838 inline bitset_iterator<n, DIRECTION>
01839 operator+(bitset_iterator<n, DIRECTION> const& i, int d)
01840 {
01841 bitset_iterator<n, DIRECTION> result(i);
01842 return result += d;
01843 }
01844
01848 template<unsigned int n, int DIRECTION>
01849 inline bitset_iterator<n, DIRECTION>
01850 operator+(int d, bitset_iterator<n, DIRECTION> const& i)
01851 {
01852 bitset_iterator<n, DIRECTION> result(i);
01853 return result += d;
01854 }
01855
01859 template<unsigned int n, int DIRECTION>
01860 inline bitset_iterator<n, DIRECTION>
01861 operator-(bitset_iterator<n, DIRECTION> const& i, int d)
01862 {
01863 bitset_iterator<n, DIRECTION> result(i);
01864 return result -= d;
01865 }
01866
01870 template<unsigned int n, int DIRECTION>
01871 inline bitset_iterator<n, DIRECTION>
01872 operator-(int d, bitset_iterator<n, DIRECTION> const& i)
01873 {
01874 bitset_iterator<n, DIRECTION> result(i);
01875 return result -= d;
01876 }
01877
01881 template<unsigned int n, int DIRECTION>
01882 inline bitset_digit_t
01883 bitset_iterator<n, DIRECTION>::operator[](int d) const
01884 {
01885 return *(*this + d);
01886 }
01887
01888
01895 template<unsigned int n>
01896 classbitset : public bitset_invertible<n, false> {
01897 public:
01898
01899 bitset(void);
01900 bitset(std::string const&);
01901 explicit bitset(bitset_digit_t low_bits);
01902
01903
01909 bitset(bitset_digit_t const (&v)[bitset_base<n>::digits])
01910 {
01911 #if ECC_DEBUG
01912 assert( (v[bitset_base<n>::digits - 1] & ~bitset_base<n>::valid_bits) == 0 );
01913 #endif
01914 std::memcpy(this->vector, v, sizeof(this->vector));
01915 }
01916
01917
01918 template<unsigned int m, bool inverted>
01919 bitset(bitset_invertible<m, inverted> const&);
01920 template<unsigned int m, bool i1, bool i2, typename OP>
01921 bitset(Operator::bitsetExpression<m, i1, i2, OP> const& expr);
01922
01923
01924 bitset& operator=(bitset const&);
01925 template<typename Expression>
01926 bitset& operator=(Expression const&);
01927
01928
01929 template<typename Expression>
01930 bitset& operator&=(Expression const&);
01931 template<typename Expression>
01932 bitset& operator|=(Expression const&);
01933 template<typename Expression>
01934 bitset& operator^=(Expression const&);
01935
01936 public:
01937
01938 template<unsigned int shift, class DIRECTION, class OPERATION>
01939 void shift_op(bitset& result) const;
01940
01941
01942 bitset& operator<<=(unsigned int shift);
01943 bitset& operator>>=(unsigned int shift);
01944
01945
01946 template<unsigned int shift, class DIRECTION>
01947 void rotate(bitset& result) const;
01948
01949
01950 bool test(size_t n) const;
01951 bool odd(void) const;
01952 void set(size_t n);
01953 void clear(size_t n);
01954 void flip(size_t n);
01955
01956
01957 bool test(bitset_index const& index) const;
01958 void set(bitset_index const& index);
01959 void clear(bitset_index const& index);
01960 void flip(bitset_index const& index);
01961
01962
01963 template<unsigned int pos>
01964 bool test(void) const;
01965 template<unsigned int pos>
01966 void set(void);
01967 template<unsigned int pos>
01968 void clear(void);
01969 template<unsigned int pos>
01970 void flip(void);
01971
01972
01973 bitset& reset(void);
01974 void setall(void);
01975 bool any(void) const;
01976
01977 public:
01978
01980 typedef bitset_iterator<n, forwards_iterating> const_iterator;
01982 typedef bitset_iterator<n, backwards_iterating> const_reverse_iterator;
01984 const_iterator begin(void) const{ return const_iterator(this, 0); }
01986 const_iterator end(void) const{ return const_iterator(this, n); }
01988 const_reverse_iterator rbegin(void) const{ return const_reverse_iterator(this, n - 1); }
01990 const_reverse_iterator rend(void) const{ return const_reverse_iterator(this, -1); }
01991
01992 template<unsigned int m>
01993 void xor_with_zero_padded(bitset<m> const& bitset, int lsb, int msb, int shift);
01994 };
01995
02012 template<unsigned int n>
02013 template<unsigned int m>
02014 #if defined(__i386__) && defined(HAVE_NASM)
02015 inline
02016 #endif
02017 void
02018 bitset<n>::xor_with_zero_padded(bitset<m> const& bitset, int lsb, int msb, int shift)
02019 {
02020 #if defined(__i386__) && defined(HAVE_NASM)
02021 libecc_shift_xorassign(this->vector, bitset.digits_ptr(), lsb, msb, shift);
02022 #else
02023 int digit1 = lsb >> bitset_digit_bits_log2;
02024 int digit2 = msb >> bitset_digit_bits_log2;
02025 bitset_digit_t d1 = 0;
02026 if (shift < 0)
02027 {
02028 unsigned int bitshift = (-shift) & (bitset_digit_bits - 1);
02029 unsigned int digitshift = (-shift) >> bitset_digit_bits_log2;
02030 if (bitshift == 0)
02031 {
02032 for (int digit = digit2; digit >= digit1; --digit)
02033 {
02034 bitset_digit_t d2 = bitset.digit(digit);
02035 this->vector[digit - digitshift] ^= d2;
02036 d1 = d2;
02037 }
02038 }
02039 else
02040 {
02041 for (int digit = digit2; digit >= digit1; --digit)
02042 {
02043 bitset_digit_t d2 = bitset.digit(digit);
02044 this->vector[digit - digitshift] ^= (d2 >> bitshift) | (d1 << (32 - bitshift));
02045 d1 = d2;
02046 }
02047 this->vector[digit1 - 1 - digitshift] ^= (d1 << (32 - bitshift));
02048 }
02049 }
02050 else if (shift > 0)
02051 {
02052 unsigned int bitshift = shift & (bitset_digit_bits - 1);
02053 unsigned int digitshift = shift >> bitset_digit_bits_log2;
02054 if (bitshift == 0)
02055 {
02056 for (int digit = digit1; digit <= digit2; ++digit)
02057 {
02058 bitset_digit_t d2 = bitset.digit(digit);
02059 this->vector[digit + digitshift] ^= d2;
02060 d1 = d2;
02061 }
02062 }
02063 else
02064 {
02065 for (int digit = digit1; digit <= digit2; ++digit)
02066 {
02067 bitset_digit_t d2 = bitset.digit(digit);
02068 this->vector[digit + digitshift] ^= (d2 << bitshift) | (d1 >> (32 - bitshift));
02069 d1 = d2;
02070 }
02071 this->vector[digit2 + 1 + digitshift] ^= (d1 >> (32 - bitshift));
02072 }
02073 }
02074 else
02075 {
02076 for (int digit = digit1; digit <= digit2; ++digit)
02077 this->vector[digit] ^= bitset.digit(digit);
02078 }
02079 #endif
02080 }
02081
02085 template<unsigned int n>
02086 inline
02087 bitset<n>::bitset(void)
02088 {
02089 }
02090
02096 template<unsigned int n>
02097 inline
02098 bitset<n>::bitset(bitset_digit_t low_bits)
02099 {
02100 #if ECC_DEBUG
02101 assert( bitset_base<n>::digits > 1 || (low_bits & ~bitset_base<n>::valid_bits) == 0 );
02102 #endif
02103 std::memset(this->vector, 0, sizeof(this->vector));
02104 this->vector[0] = low_bits;
02105 }
02106
02110 template<unsigned int n>
02111 void
02112 bitset<n>::setall(void)
02113 {
02114 this->vector[bitset_base<n>::digits - 1] = bitset_base<n>::valid_bits;
02115 if (bitset_base<n>::digits > 1)
02116 {
02117 int d = bitset_base<n>::digits - 2;
02118 do { this->vector[d] = ~static_cast<bitset_digit_t>(0); } while(--d >= 0);
02119 }
02120 }
02121
02146 template<unsigned int n>
02147 template<typename Expression>
02148 inline
02149 bitset<n>& bitset<n>::operator=(Expression const& expr)
02150 {
02151 this->assign(expr, Operator::bitsetAssign());
02152 return *this;
02153 }
02154
02155
02156 template<unsigned int n>
02157 inline bitset<n>&
02158 bitset<n>::operator=(bitset const& expr)
02159 {
02160 this->assign(expr, Operator::bitsetAssign());
02161 return *this;
02162 }
02163
02180 template<unsigned int n>
02181 template<unsigned int m, bool inverted>
02182 inline bitset<n>::bitset(bitset_invertible<m, inverted> const& bits) : bitset_invertible<n, false>(bits)
02183 {
02184 }
02185
02191 template<unsigned int n>
02192 template<unsigned int m, bool i1, bool i2, typename OP>
02193 inline bitset<n>::bitset(Operator::bitsetExpression<m, i1, i2, OP> const& expr) : bitset_invertible<n, false>(expr)
02194 {
02195 }
02196
02208 template<unsigned int n1, bool inverted1, unsigned int n2, bool inverted2>
02209 bool operator==(bitset_invertible<n1, inverted1> const& bits1, bitset_invertible<n2, inverted2> const& bits2)
02210 {
02211 unsigned int d;
02212 if (bitset_invertible<n1, inverted1>::digits > bitset_invertible<n2, inverted2>::digits)
02213 {
02214 d = bitset_base<n1>::digits - 1;
02215 do
02216 {
02217 if (bits1.vector[d] != (inverted1 == inverted2 ? 0 : ~static_cast<bitset_digit_t>(0)))
02218 return false;
02219 }
02220 while (--d != bitset_base<n2>::digits - 1);
02221 }
02222 if (bitset_base<n2>::digits > bitset_base<n1>::digits)
02223 {
02224 d = bitset_base<n2>::digits - 1;
02225 do
02226 {
02227 if (bits2.vector[d] != (inverted1 == inverted2 ? 0 : ~static_cast<bitset_digit_t>(0)))
02228 return false;
02229 }
02230 while (--d != bitset_base<n1>::digits - 1);
02231 }
02232 if (bitset_base<n1>::digits > 1 && bitset_base<n2>::digits > 1)
02233 {
02234 if (bitset_base<n1>::digits == bitset_base<n2>::digits)
02235 d = bitset_base<n1>::digits - 1;
02236 do
02237 {
02238 if (inverted1 == inverted2)
02239 {
02240 if (bits1.vector[d] != bits2.vector[d])
02241 return false;
02242 }
02243 else
02244 {
02245 if (bits1.vector[d] != ~(bits2.vector[d]))
02246 return false;
02247 }
02248 }
02249 while(--d != 0);
02250 }
02251 if (inverted1 != inverted2)
02252 return (bits1.vector[0] == ~(bits2.vector[0]));
02253 return (bits1.vector[0] == bits2.vector[0]);
02254 }
02255
02261 template<unsigned int n1, bool inverted1, unsigned int n2, bool inverted2>
02262 inline bool
02263 operator!=(bitset_invertible<n1, inverted1> const& bits1, bitset_invertible<n2, inverted2> const& bits2)
02264 {
02265 return !(bits1 == bits2);
02266 }
02267
02272 template<unsigned int n>
02273 template<typename Expression>
02274 inline bitset<n>&
02275 bitset<n>::operator&=(Expression const& expr)
02276 {
02277 this->assign(expr, Operator::bitsetANDAssign());
02278 return *this;
02279 }
02280
02285 template<unsigned int n>
02286 template<typename Expression>
02287 inline bitset<n>&
02288 bitset<n>::operator|=(Expression const& expr)
02289 {
02290 this->assign(expr, Operator::bitsetORAssign());
02291 return *this;
02292 }
02293
02298 template<unsigned int n>
02299 template<typename Expression>
02300 inline bitset<n>&
02301 bitset<n>::operator^=(Expression const& expr)
02302 {
02303 this->assign(expr, Operator::bitsetXORAssign());
02304 return *this;
02305 }
02306
02311 template<unsigned int m, bool inverted1, bool inverted2>
02312 Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetAND>
02313 operator&(bitset_invertible<m, inverted1> const& arg1, bitset_invertible<m, inverted2> const& arg2)
02314 {
02315 return Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetAND>(arg1, arg2);
02316 }
02317
02322 template<unsigned int m, bool inverted1, bool inverted2>
02323 Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetOR>
02324 operator|(bitset_invertible<m, inverted1> const& arg1, bitset_invertible<m, inverted2> const& arg2)
02325 {
02326 return Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetOR>(arg1, arg2);
02327 }
02328
02333 template<unsigned int m, bool inverted1, bool inverted2>
02334 Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetXOR>
02335 operator^(bitset_invertible<m, inverted1> const& arg1, bitset_invertible<m, inverted2> const& arg2)
02336 {
02337 return Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetXOR>(arg1, arg2);
02338 }
02339
02343 structassign {
02344 static int const id = 1;
02345 static bool const __clear = true;
02346 static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
02347 static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
02348 };
02349
02353 structexor {
02354 static int const id = 2;
02355 static bool const __clear = false;
02356 static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 ^= digit2; }
02357 static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 ^= digit2; }
02358 };
02359
02360 #ifndef HIDE_FROM_DOXYGEN
02361 structrotate_phase1 {
02362 static int const id = 3;
02363 static bool const __clear = false;
02364 static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
02365 static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
02366 };
02367
02368 structrotate_phase2 {
02369 public:
02370 static int const id = 4;
02371 static bool const __clear = false;
02372 static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
02373 static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 |= digit2; }
02374 };
02375 #endif
02376
02387 template<unsigned int n>
02388 template<unsigned int shift, class DIRECTION, class OPERATION>
02389 void
02390 bitset<n>::shift_op(bitset& result) const
02391 {
02392 LibEccDout(dc::bitsetshift, "Entering shift_op<" << shift << ", " << libcwd::type_info_of<DIRECTION>().demangled_name() <<
02393 ", " << type_info_of<OPERATION>().demangled_name() << '>');
02394 LibEccDout(dc::bitsetshift|flush_cf, "Input : " << cwprint_using(*this, &bitset<n>::base2_print_on));
02395 if (shift == 1)
02396 {
02397
02398
02399
02400
02401
02402 static unsigned int const initial = DIRECTION::__left ? 0 : bitset_base<n>::digits - 1;
02403 static unsigned int const count = bitset_base<n>::digits - ((DIRECTION::__left && bitset_base<n>::has_excess_bits) ? 1 : 0);
02404 #ifdef __i386__
02405 if (count)
02406 {
02407 bitset_digit_t const volatile* ptr1;
02408 bitset_digit_t volatile* ptr2;
02409 int c;
02410 if (DIRECTION::__left)
02411 {
02412 if (OPERATION::id == libecc::exor::id)
02413 {
02414 if (bitset_base<n>::has_excess_bits)
02415 LIBECC_ASMSHIFTLEFT(
02416 LIBECC_LEFT_PRESERVE_CF("xorl -4(%%edi), %%edx"),
02417 LIBECC_LEFT_PRESERVE_CF("xorl (%%edi), %%edx"),
02418 LIBECC_ASMSHIFTLEFT_FINISH("xorl (%%edi),%%edx\n\t"));
02419 else
02420 LIBECC_ASMSHIFTLEFT(
02421 LIBECC_LEFT_PRESERVE_CF("xorl -4(%%edi), %%edx"),
02422 LIBECC_LEFT_PRESERVE_CF("xorl (%%edi), %%edx"), "");
02423 }
02424 else if (OPERATION::id == libecc::rotate_phase2::id)
02425 {
02426 if (bitset_base<n>::has_excess_bits)
02427 LIBECC_ASMSHIFTLEFT(
02428 LIBECC_LEFT_PRESERVE_CF("orl -4(%%edi), %%edx"), "", LIBECC_ASMSHIFTLEFT_FINISH(""));
02429 else
02430 LIBECC_ASMSHIFTLEFT(
02431 LIBECC_LEFT_PRESERVE_CF("orl -4(%%edi), %%edx"), "", "");
02432 }
02433 else
02434 {
02435 if (bitset_base<n>::has_excess_bits)
02436 LIBECC_ASMSHIFTLEFT("", "", LIBECC_ASMSHIFTLEFT_FINISH(""));
02437 else
02438 LIBECC_ASMSHIFTLEFT("", "", "");
02439 }
02440 }
02441 else if (count > 1)
02442 {
02443 if (OPERATION::id == libecc::exor::id)
02444 LIBECC_ASMSHIFTRIGHT1(
02445 LIBECC_RIGHT_PRESERVE_CF("xorl " LIBECC_OP1_DESTINATION "," LIBECC_WORKREG),
02446 LIBECC_RIGHT_PRESERVE_CF("xorl " LIBECC_OP2_DESTINATION "," LIBECC_WORKREG),
02447 LIBECC_PRESERVE_CF_CLOBBER);
02448 else if (OPERATION::id == libecc::rotate_phase2::id)
02449 LIBECC_ASMSHIFTRIGHT1(
02450 LIBECC_RIGHT_PRESERVE_CF("orl " LIBECC_OP1_DESTINATION "," LIBECC_WORKREG),
02451 "",
02452 LIBECC_PRESERVE_CF_CLOBBER);
02453 else
02454 LIBECC_ASMSHIFTRIGHT1(
02455 "",
02456 "",
02457 LIBECC_CLOBBER);
02458 }
02459 else
02460 {
02461 if (OPERATION::id == libecc::exor::id)
02462 LIBECC_ASMSHIFTRIGHT0("xorl 4(%%edi), %%edx\n\t");
02463 else if (OPERATION::id == libecc::rotate_phase2::id)
02464 LIBECC_ASMSHIFTRIGHT0("orl 4(%%edi), %%edx\n\t");
02465 else
02466 LIBECC_ASMSHIFTRIGHT0("");
02467 }
02468 }
02469 else if (DIRECTION::__left && bitset_base<n>::has_excess_bits)
02470 OPERATION::op(result.vector[0], ((this->vector[0] << 1) & bitset_base<n>::valid_bits));
02471 #else
02472 static unsigned int complement_shift = bitset_digit_bits - 1;
02473 static bitset_digit_t const mask1 = DIRECTION::__left ? (1 << complement_shift) : 1;
02474 static bitset_digit_t const mask2 = DIRECTION::__right ? (1 << complement_shift) : 1;
02475 bitset_digit_t const* ptr1 = &this->vector[initial];
02476 bitset_digit_t* ptr2 = &result.vector[initial];
02477 bool carry;
02478 if (count)
02479 {
02480 bitset_digit_t digit = *ptr1;
02481 carry = (digit & mask1);
02482 if (DIRECTION::__left)
02483 digit <<= 1;
02484 else
02485 digit >>= 1;
02486 OPERATION::mixed_op(*ptr2, digit);
02487 for (int c = count - 1; c; --c)
02488 {
02489 ptr1 -= DIRECTION::direction;
02490 ptr2 -= DIRECTION::direction;
02491 digit = *ptr1;
02492 if (carry)
02493 {
02494 carry = (digit & mask1);
02495 if (DIRECTION::__left)
02496 digit <<= 1;
02497 else
02498 digit >>= 1;
02499 digit |= mask2;
02500 }
02501 else
02502 {
02503 carry = (digit & mask1);
02504 if (DIRECTION::__left)
02505 digit <<= 1;
02506 else
02507 digit >>= 1;
02508 }
02509 OPERATION::op(*ptr2, digit);
02510 }
02511 }
02512 if (DIRECTION::__left && bitset_base<n>::has_excess_bits)
02513 {
02514 bitset_digit_t digit;
02515 if (count)
02516 digit = ptr1[-DIRECTION::direction];
02517 else
02518 digit = *ptr1;
02519 digit <<= 1;
02520 if (count && carry)
02521 digit |= mask2;
02522 if (count)
02523 OPERATION::op(ptr2[-DIRECTION::direction], (digit & bitset_base<n>::valid_bits));
02524 else
02525 OPERATION::op(*ptr2, (digit & bitset_base<n>::valid_bits));
02526 }
02527 #endif
02528 }
02529 else
02530 {
02531 static unsigned int const digit_shift = shift / bitset_digit_bits;
02532 static unsigned int const bit_shift = shift % bitset_digit_bits;
02533
02534 static unsigned int const zeroed_digits =
02535 DIRECTION::__left ? ((shift < n) ? digit_shift : bitset_base<n>::digits)
02536 : ((bitset_digit_bits - bitset_base<n>::number_of_valid_bits + shift) / bitset_digit_bits);
02537
02538 if (zeroed_digits < bitset_base<n>::digits)
02539 {
02540 static unsigned int const complement_shift = (bit_shift == 0) ? 0 : bitset_digit_bits - bit_shift;
02541 static unsigned int const initial_to = DIRECTION::__right ? 0 : bitset_base<n>::digits - 1;
02542 static unsigned int const initial_from = initial_to + DIRECTION::direction * digit_shift;
02543 static unsigned int const final_from = DIRECTION::__left ? 0 : bitset_base<n>::digits - 1;
02544
02545 register bitset_digit_t digit = this->vector[initial_from];
02546 if (initial_from != final_from)
02547 {
02548 register bitset_digit_t next_digit;
02549 unsigned int to = initial_to;
02550 unsigned int from = initial_from + DIRECTION::direction;
02551 if (from != final_from)
02552 do
02553 {
02554 next_digit = this->vector[from];
02555 if (bit_shift != 0)
02556 {
02557 if (DIRECTION::direction == -1)
02558 digit <<= bit_shift;
02559 else
02560 digit >>= bit_shift;
02561 digit |= DIRECTION::reverse_shift_copy(next_digit, complement_shift);
02562 }
02563 OPERATION::op(result.vector[to], digit);
02564 digit = next_digit;
02565 to += DIRECTION::direction;
02566 from += DIRECTION::direction;
02567 }
02568 while (from != final_from);
02569 if (DIRECTION::__left || bit_shift < bitset_base<n>::number_of_valid_bits || bit_shift != 0)
02570 next_digit = this->vector[final_from];
02571 if (bit_shift != 0)
02572 {
02573 if (DIRECTION::direction == -1)
02574 digit <<= bit_shift;
02575 else
02576 digit >>= bit_shift;
02577 digit |= DIRECTION::reverse_shift_copy(next_digit, complement_shift);
02578 }
02579 if (DIRECTION::__left || bit_shift < bitset_base<n>::number_of_valid_bits)
02580 {
02581 OPERATION::op(result.vector[final_from - DIRECTION::direction * (digit_shift + 1)], digit);
02582 digit = DIRECTION::shift_copy(next_digit, bit_shift);
02583 }
02584 }
02585 else
02586 {
02587 if (DIRECTION::direction == -1)
02588 digit <<= bit_shift;
02589 else
02590 digit >>= bit_shift;
02591 }
02592 static bool const have_mixed_digit = shift != 0 && (DIRECTION::__left ? shift : (n - shift)) % bitset_digit_bits != 0;
02593 static unsigned int const last_digit = (DIRECTION::__left ? shift : (n - 1 - shift)) / bitset_digit_bits;
02594 if (have_mixed_digit)
02595 OPERATION::mixed_op(result.vector[last_digit], digit);
02596 else
02597 OPERATION::op(result.vector[last_digit], digit);
02598 if (DIRECTION::__left && bitset_base<n>::has_excess_bits)
02599 result.vector[bitset_base<n>::digits - 1] &= bitset_base<n>::valid_bits;
02600 }
02601 if (OPERATION::__clear && zeroed_digits > 0)
02602 {
02603 static unsigned int const final_to = DIRECTION::__left ? 0 : bitset_base<n>::digits - 1;
02604 static unsigned int const initial_to = final_to - DIRECTION::direction * (zeroed_digits - 1);
02605 unsigned int to = initial_to;
02606 if (to != final_to)
02607 do
02608 {
02609 result.vector[to] = 0;
02610 to += DIRECTION::direction;
02611 }
02612 while(to != final_to);
02613 result.vector[to] = 0;
02614 }
02615 }
02616 LibEccDout(dc::bitsetshift|flush_cf, "Output: " << cwprint_using(result, &bitset<n>::base2_print_on));
02617 }
02618
02622 template<unsigned int n>
02623 bitset<n>&
02624 bitset<n>::operator<<=(unsigned int shift)
02625 {
02626 unsigned int const digit_shift = shift >> bitset_digit_bits_log2;
02627 unsigned int const bit_shift = shift & (bitset_digit_bits - 1);
02628 int digit1 = bitset_base<n>::digits - digit_shift - 2;
02629 bitset_digit_t d0 = (digit1 >= -1) ? this->vector[digit1 + 1] : 0;
02630 for (int digit_to = bitset_base<n>::digits - 1; digit_to >= 0; --digit_to)
02631 {
02632 bitset_digit_t d1 = (digit1 >= 0) ? this->vector[digit1] : 0;
02633 if (bit_shift == 0)
02634 this->vector[digit_to] = d0;
02635 else
02636 this->vector[digit_to] = (d0 << bit_shift) | (d1 >> (bitset_digit_bits - bit_shift));
02637 d0 = d1;
02638 --digit1;
02639 }
02640 if (bitset_base<n>::has_excess_bits)
02641 this->vector[bitset_base<n>::digits - 1] &= bitset_base<n>::valid_bits;
02642 return *this;
02643 }
02644
02648 template<unsigned int n>
02649 bitset<n>&
02650 bitset<n>::operator>>=(unsigned int shift)
02651 {
02652 unsigned int const digit_shift = shift >> bitset_digit_bits_log2;
02653 unsigned int const bit_shift = shift & (bitset_digit_bits - 1);
02654 unsigned int digit1 = digit_shift + 1;
02655 bitset_digit_t d0 = (digit1 <= bitset_base<n>::digits) ? this->vector[digit1 - 1] : 0;
02656 for (unsigned int digit_to = 0; digit_to < bitset_base<n>::digits; ++digit_to)
02657 {
02658 bitset_digit_t d1 = (digit1 < bitset_base<n>::digits) ? this->vector[digit1] : 0;
02659 if (bit_shift == 0)
02660 this->vector[digit_to] = d0;
02661 else
02662 this->vector[digit_to] = (d0 >> bit_shift) | (d1 << (bitset_digit_bits - bit_shift));
02663 d0 = d1;
02664 ++digit1;
02665 }
02666 return *this;
02667 }
02668
02685 template<unsigned int n>
02686 bitset<n>::bitset(std::string const& input)
02687 {
02688 reset();
02689 unsigned int d = 0;
02690 unsigned int u = 0;
02691
02692 for (std::string::const_reverse_iterator iter = input.rbegin(); iter != input.rend(); ++iter)
02693 {
02694 bitset_digit_t c = toupper(*iter);
02695 if (c == ' ')
02696 continue;
02697 if (c < '0')
02698 break;
02699 if (c <= '9')
02700 c -= '0';
02701 else
02702 {
02703 if (c > 'F')
02704 break;
02705 if (c >= 'A')
02706 c -= ('A' - 10);
02707 else
02708 break;
02709 }
02710 this->vector[d] |= c << u;
02711 if ((u += 4) == bitset_digit_bits)
02712 {
02713 u = 0;
02714 if (++d == bitset_base<n>::digits)
02715 break;
02716 }
02717 }
02718 if (bitset_base<n>::has_excess_bits)
02719 this->vector[bitset_base<n>::digits - 1] &= bitset_base<n>::valid_bits;
02720 }
02721
02725 template<unsigned int n>
02726 std::istream&
02727 operator>>(std::istream& is, bitset<n>& bitsetx)
02728 {
02729 std::string tmp;
02730 is >> tmp;
02731 bitsetx.bitset(tmp);
02732 return is;
02733 }
02734
02738 template<unsigned int n>
02739 std::ostream&
02740 operator<<(std::ostream& os, bitset<n> const& bits)
02741 {
02742
02743 os.fill('0');
02744 os << std::hex;
02745 for (int d = bitset<n>::digits - 1; d >= 0; --d)
02746 {
02747 os.width((d == bitset<n>::digits - 1 && bitset<n>::has_excess_bits) ?
02748 (((n % bitset_digit_bits) - 1) / 4 + 1) :
02749 (bitset_digit_bits / 4));
02750 os << bits.digit(d);
02751 if (d > 0)
02752 os << ' ';
02753 }
02754 os << std::dec;
02755 return os;
02756 }
02757
02761 template<unsigned int n>
02762 bitset<n>&
02763 bitset<n>::reset(void)
02764 {
02765 std::memset(this->vector, 0, sizeof(this->vector));
02766 return *this;
02767 }
02768
02772 template<unsigned int n>
02773 inline bool
02774 bitset<n>::test(size_t pos) const
02775 {
02776 #ifdef __i386__
02777 int result;
02778 __asm__ __volatile__ (
02779 "btl %2, %1\n\t"
02780 "sbbl %0, %0"
02781 : "=r" (result)
02782 : "m" ((*(bitset_digit_t volatile*)this->vector)), "Ir" (pos));
02783 return result;
02784 #else
02785 unsigned int d = pos / bitset_digit_bits;
02786 bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
02787 return (this->vector[d] & mask);
02788 #endif
02789 }
02790
02794 template<unsigned int n>
02795 template<unsigned int pos>
02796 inline bool
02797 bitset<n>::test(void) const
02798 {
02799 static unsigned int const d = pos / bitset_digit_bits;
02800 static bitset_digit_t const mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
02801 return (this->vector[d] & mask);
02802 }
02803
02807 template<unsigned int n>
02808 inline bool
02809 bitset<n>::test(bitset_index const& index) const
02810 {
02811 #ifdef __i386__
02812 return this->test(index.get_index());
02813 #else
02814 return (this->vector[index.get_digit()] & index.get_mask());
02815 #endif
02816 }
02817
02821 template<unsigned int n>
02822 inline void
02823 bitset<n>::set(size_t pos)
02824 {
02825 #ifdef __i386__
02826 __asm__ __volatile__ (
02827 "btsl %1, %0"
02828 : "=m" ((*(bitset_digit_t volatile*)this->vector))
02829 : "Ir" (pos));
02830
02831 #else
02832 unsigned int d = pos / bitset_digit_bits;
02833 bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
02834 this->vector[d] |= mask;
02835 #endif
02836 }
02837
02841 template<unsigned int n>
02842 inline void
02843 bitset<n>::set(bitset_index const& index)
02844 {
02845 #ifdef __i386__
02846 this->set(index.get_index());
02847 #else
02848 this->vector[index.get_digit()] |= index.get_mask();
02849 #endif
02850 }
02851
02855 template<unsigned int n>
02856 template<unsigned int pos>
02857 inline void
02858 bitset<n>::set(void)
02859 {
02860 static unsigned int const d = pos / bitset_digit_bits;
02861 static bitset_digit_t const mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
02862 this->vector[d] |= mask;
02863 }
02864
02868 template<unsigned int n>
02869 inline void
02870 bitset<n>::clear(size_t pos)
02871 {
02872 #ifdef __i386__
02873 __asm__ __volatile__ (
02874 "btrl %1, %0"
02875 : "=m" ((*(bitset_digit_t volatile*)this->vector))
02876 : "Ir" (pos)
02877 );
02878 #else
02879 unsigned int d = pos / bitset_digit_bits;
02880 bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
02881 this->vector[d] &= ~mask;
02882 #endif
02883 }
02884
02888 template<unsigned int n>
02889 inline void
02890 bitset<n>::clear(bitset_index const& index)
02891 {
02892 #ifdef __i386__
02893 this->clear(index.get_index());
02894 #else
02895 this->vector[index.get_digit()] &= ~(index.get_mask());
02896 #endif
02897 }
02898
02902 template<unsigned int n>
02903 template<unsigned int pos>
02904 inline void
02905 bitset<n>::clear(void)
02906 {
02907 static unsigned int const d = pos / bitset_digit_bits;
02908 static bitset_digit_t const mask = ~(static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits));
02909 this->vector[d] &= mask;
02910 }
02911
02915 template<unsigned int n>
02916 inline void
02917 bitset<n>::flip(size_t pos)
02918 {
02919 #ifdef __i386__
02920 __asm__ __volatile__ (
02921 "btcl %1, %0"
02922 : "=m" ((*(bitset_digit_t volatile*)this->vector))
02923 : "Ir" (pos)
02924 );
02925 #else
02926 unsigned int d = pos / bitset_digit_bits;
02927 bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
02928 this->vector[d] ^= mask;
02929 #endif
02930 }
02931
02935 template<unsigned int n>
02936 inline void
02937 bitset<n>::flip(bitset_index const& index)
02938 {
02939 #ifdef __i386__
02940 this->flip(index.get_index());
02941 #else
02942 this->vector[index.get_digit()] ^= index.get_mask();
02943 #endif
02944 }
02945
02949 template<unsigned int n>
02950 template<unsigned int pos>
02951 inline void
02952 bitset<n>::flip(void)
02953 {
02954 static unsigned int const d = pos / bitset_digit_bits;
02955 static bitset_digit_t const mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
02956 this->vector[d] ^= mask;
02957 }
02958
02962 template<unsigned int n>
02963 bool
02964 bitset<n>::any(void) const
02965 {
02966 unsigned int to = bitset_base<n>::digits - 1;
02967 if (bitset_base<n>::digits > 1)
02968 do
02969 {
02970 if (this->vector[to] != 0)
02971 return true;
02972 --to;
02973 }
02974 while(to != 0);
02975 return (this->vector[0] != 0);
02976 }
02977
02978 static bool const oddnumberofbits[] = {
02979 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
02980 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02981 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02982 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
02983 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02984 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
02985 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
02986 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02987 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02988 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
02989 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
02990 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02991 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
02992 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02993 true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
02994 false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false };
02995
02999 template<unsigned int n>
03000 bool
03001 bitset<n>::odd(void) const
03002 {
03003 unsigned int from = bitset_base<n>::digits - 1;
03004 bitset_digit_t sum = this->vector[0];
03005 if (bitset_base<n>::digits > 1)
03006 do
03007 {
03008 sum ^= this->vector[from];
03009 --from;
03010 }
03011 while(from != 0);
03012 bitset_digit_t ssum = sum;
03013 if (sizeof(bitset_digit_t) >= 2)
03014 {
03015 ssum >>= (bitset_digit_bits / 2);
03016 sum ^= ssum;
03017 }
03018 if (sizeof(bitset_digit_t) >= 4)
03019 {
03020 ssum = sum;
03021 ssum >>= (bitset_digit_bits / 4);
03022 sum ^= ssum;
03023 }
03024 if (sizeof(bitset_digit_t) >= 8)
03025 {
03026 ssum = sum;
03027 ssum >>= (bitset_digit_bits / 8);
03028 sum ^= ssum;
03029 }
03030 if (sizeof(bitset_digit_t) == 16)
03031 {
03032 ssum = sum;
03033 ssum >>= (bitset_digit_bits / 16);
03034 sum ^= ssum;
03035 }
03036 return oddnumberofbits[sum & 0xff];
03037 }
03038
03042 structleft {
03043 public:
03044 typedef structright inverse;
03045 static int const direction = -1;
03046 static bool const __left = true;
03047 static bool const __right = false;
03048 static inline bitset_digit_t shift_copy(bitset_digit_t digit, unsigned int shift) { return digit << shift; }
03049 static inline bitset_digit_t reverse_shift_copy(bitset_digit_t digit, unsigned int shift) { return digit >> shift; }
03050 };
03051
03055 structright {
03056 public:
03057 typedef structleft inverse;
03058 static int const direction = 1;
03059 static bool const __left = false;
03060 static bool const __right = true;
03061 static inline bitset_digit_t shift_copy(bitset_digit_t digit, unsigned int shift) { return digit >> shift; }
03062 static inline bitset_digit_t reverse_shift_copy(bitset_digit_t digit, unsigned int shift) { return digit << shift; }
03063 };
03064
03073 template<unsigned int n>
03074 template<unsigned int shift, class DIRECTION>
03075 void
03076 bitset<n>::rotate(bitset<n>& result) const
03077 {
03078 LibEccDout(dc::bitsetshift|flush_cf, "Entering bitset<" << n << ">::rotate<" << shift << ", " << type_info_of<DIRECTION>().demangled_name() << ">");
03079 LibEccDout(dc::bitsetshift|flush_cf, "Rotate input : " << cwprint_using(*this, &bitset<n>::base2_print_on));
03080 shift_op<shift % n, DIRECTION, rotate_phase1>(result);
03081 LibEccDout(dc::bitsetshift|flush_cf, "After phase1 : " << cwprint_using(result, &bitset<n>::base2_print_on));
03082 shift_op<n - (shift % n), typename DIRECTION::inverse, rotate_phase2>(result);
03083 LibEccDout(dc::bitsetshift|flush_cf, "After phase2 : " << cwprint_using(result, &bitset<n>::base2_print_on));
03084 LibEccDout(dc::bitsetshift|flush_cf, "Leaving bitset<" << n << ">::rotate<" << shift << ", " << type_info_of<DIRECTION>().demangled_name() << ">");
03085 }
03086
03087 }
03088
03089 #endif // LIBECC_BITS_H