libecc/bitset.h

Go to the documentation of this file.

//
//
// This file is part of the libecc package.
// Copyright (C) 2002, by
//
// Carlo Wood, Run on IRC <carlo@alinoe.com>
// RSA-1024 0x624ACAD5 1997-01-26                    Sign & Encrypt
// Fingerprint16 = 32 EC A7 B6 AC DB 65 A6  F6 F6 55 DD 1C DC FF 61
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

#ifndef LIBECC_BITS_H
#define LIBECC_BITS_H

#ifndef LIBECC_DEBUG_H
#error "You need to include the appropriate debug.h in the source file, before including this header file."
#endif

#include <libecc/config.h>
#include <iosfwd>
#include <cstddef>
#include <cstring>
#include <string>
#include <inttypes.h>
#include <cassert>
#include <endian.h>
#ifdef CWDEBUG
#include "debug.h"
#include <libcwd/cwprint.h>
#endif
#define LIBECC_TRACK_EXPR_TEMPORARIES (ECC_DEBUG && 1)
#if LIBECC_TRACK_EXPR_TEMPORARIES
#include <set>
#endif

#if defined(__i386__) && defined(HAVE_NASM)
// Assembly code, defined in window.s.
extern "C" int libecc_shift_xorassign(unsigned long* bitset1, unsigned long const* bitset2, int lsb, int msb, int shift);
extern "C" int libecc_shiftwindow_xorassign(unsigned long* bitset1, unsigned long const* bitset2, int lsb, int msb, int shift);
#endif

namespacelibecc {

typedef unsigned long bitset_digit_t;

static unsigned int const bitset_digit_bits = sizeof(bitset_digit_t) * 8;

#if ECC_BITS == 32
static unsigned int const bitset_digit_bits_log2 = 5;
#elif ECC_BITS == 64
static unsigned int const bitset_digit_bits_log2 = 6;
#elif ECC_BITS == 128
#warning 128 bit code has not been tested.  This warning will remain here until you mail me.
static unsigned int const bitset_digit_bits_log2 = 7;
#endif

//------------------------------------------------------------------------------------------------------------------
// Iterators
//

classbitset_index {
#if defined(__i386__) || defined(LIBECC_DOXYGEN)
  protected:
    int M_index;                        

  public:
    // Accessors.
    int get_index(void) const;

#else
  protected:
    int M_digit;                        
    bitset_digit_t M_mask;              

  public:
    // Accessors.
    int get_digit(void) const;
    bitset_digit_t get_mask(void) const;

    // Used in polynomial.h
    int get_index(void) const;
#endif

  public:
    // Equality Comparable.
    friend bool operator==(bitset_index const& i1, bitset_index const& i2);
    friend bool operator!=(bitset_index const& i1, bitset_index const& i2);

  protected:
    // Bidirectional.
    void left(void);
    void right(void);

    // Random access.
    void left(int n);
    void right(int n);
    friend int subtract(bitset_index const& i1, bitset_index const& i2);

  protected:
    // Constructors.
    bitset_index(void);
    bitset_index(bitset_index const& index);
    bitset_index(int bit);

  public:
    friend std::ostream& operator<<(std::ostream& os, bitset_index const& i);
};

#if defined(__i386__) || defined(LIBECC_DOXYGEN)

inline int
bitset_index::get_index(void) const
{
  return M_index;
}

#else // !defined(__i386__)

// Accessor for the current digit index.
inline int
bitset_index::get_digit(void) const
{
  return M_digit;
}

// Accessor for the current digit mask.
inline bitset_digit_t
bitset_index::get_mask(void) const
{ 
  return M_mask;
}

#include <strings.h>   // Needed for ffsl.
inline int
bitset_index::get_index(void) const
{
  return M_digit * bitset_digit_bits + ::ffsl(M_mask) - 1;
}

#endif // !defined(__i386__)

inline bool
operator==(bitset_index const& i1, bitset_index const& i2)
{
#ifdef __i386__
  return (i1.M_index == i2.M_index);
#else
  return (i1.M_digit == i2.M_digit && i1.M_mask == i2.M_mask);
#endif
}

inline bool
operator!=(bitset_index const& i1, bitset_index const& i2)
{
#ifdef __i386__
  return (i1.M_index != i2.M_index);
#else
  return (i1.M_digit != i2.M_digit || i1.M_mask != i2.M_mask);
#endif
}

inline
bitset_index::bitset_index(void)
{
}

inline
bitset_index::bitset_index(bitset_index const& index) :
#ifdef __i386__
    M_index(index.M_index)
#else
    M_digit(index.M_digit), M_mask(index.M_mask)
#endif
{ 
}

inline
bitset_index::bitset_index(int bit) :
#ifdef __i386__
    M_index(bit)
#else
    // If bit == -1 then M_digit should become -1 and M_mask 0x80000000.
    M_digit(bit >> bitset_digit_bits_log2),
    M_mask(static_cast<bitset_digit_t>(1) << ((unsigned int)bit & (bitset_digit_bits - 1)))
#endif
{
}

inline void
bitset_index::left(void)
{
#ifdef __i386__
  ++M_index;
#else
  if ((M_mask <<= 1) == 0)
  {
    ++M_digit;
    M_mask = 1;
  }
#endif
}

inline void
bitset_index::right(void)
{
#ifdef __i386__
  --M_index;
#else
  if ((M_mask >>= 1) == 0)
  {
    --M_digit;
    M_mask = static_cast<bitset_digit_t>(1) << (bitset_digit_bits - 1);
  }
#endif
}

inline void
bitset_index::left(int n)
{
#ifdef __i386__
  M_index += n;
#else
  int const digit_shift = n >> bitset_digit_bits_log2;
  int const mask_shift = n & (bitset_digit_bits - 1);
  M_digit += digit_shift;
  if (mask_shift)
  {
    bitset_digit_t new_mask = M_mask << mask_shift;
    if (new_mask == 0)
    {
      ++M_digit;
      new_mask = M_mask >> (bitset_digit_bits - mask_shift);
    }
    M_mask = new_mask;
  }
#endif
}

inline void
bitset_index::right(int n)
{
#ifdef __i386__
  M_index -= n;
#else
  int const digit_shift = n >> bitset_digit_bits_log2;
  int const mask_shift = n & (bitset_digit_bits - 1);
  M_digit -= digit_shift;
  if (mask_shift)
  {
    bitset_digit_t new_mask = M_mask >> mask_shift;
    if (new_mask == 0)
    {
      --M_digit;
      new_mask = M_mask << (bitset_digit_bits - mask_shift);
    }
    M_mask = new_mask;
  }
#endif
}

enum {
  forwards_iterating,
  backwards_iterating
};

// Forward declarations.
template<int DIRECTION> classbitset_index_iterator;
template<int DIRECTION> bool operator<(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);
template<int DIRECTION> bool operator>(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);
template<int DIRECTION> bool operator<=(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);
template<int DIRECTION> bool operator>=(bitset_index_iterator<DIRECTION> const&, bitset_index_iterator<DIRECTION> const&);

template<int DIRECTION>
  classbitset_index_iterator : public bitset_index {
    public:
      // LessThan Comparable.
      friend bool operator< <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);
      friend bool operator> <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);
      friend bool operator<= <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);
      friend bool operator>= <>(bitset_index_iterator const& i1, bitset_index_iterator const& i2);

    public:
      // Bidirectional.
      void increment(void);
      void decrement(void);

      // Random access.
      void increment(int n);
      void decrement(int n);

      friend int operator-(bitset_index const& i1, bitset_index const& i2);

    public:
      // Constructors.
      bitset_index_iterator(void);
      bitset_index_iterator(bitset_index_iterator const& index);
      bitset_index_iterator(int bit);
  };

template<int DIRECTION>
  inline
  bitset_index_iterator<DIRECTION>::bitset_index_iterator(void)
  {
  }

template<int DIRECTION>
  inline
  bitset_index_iterator<DIRECTION>::bitset_index_iterator(bitset_index_iterator<DIRECTION> const& index) :
      bitset_index(index)
  { 
  }

template<int DIRECTION>
  inline
  bitset_index_iterator<DIRECTION>::bitset_index_iterator(int bit) : bitset_index(bit)
  {
  }

template<int DIRECTION>
  inline bool
  operator<(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
  {
#ifdef __i386__
    if (DIRECTION == forwards_iterating)
      return (i1.M_index < i2.M_index);
    else
      return (i1.M_index > i2.M_index);
#else
    if (DIRECTION == forwards_iterating)
      return (i1.M_digit < i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask < i2.M_mask));
    else
      return (i1.M_digit > i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask > i2.M_mask));
#endif
  }

template<int DIRECTION>
  inline bool
  operator>(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
  {
#ifdef __i386__
    if (DIRECTION == forwards_iterating)
      return (i1.M_index > i2.M_index);
    else
      return (i1.M_index < i2.M_index);
#else
    if (DIRECTION == forwards_iterating)
      return (i1.M_digit > i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask > i2.M_mask));
    else
      return (i1.M_digit < i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask < i2.M_mask));
#endif
  }

template<int DIRECTION>
  inline bool
  operator<=(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
  {
#ifdef __i386__
    if (DIRECTION == forwards_iterating)
      return (i1.M_index <= i2.M_index);
    else
      return (i1.M_index >= i2.M_index);
#else
    if (DIRECTION == forwards_iterating)
      return (i1.M_digit <= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask <= i2.M_mask));
    else
      return (i1.M_digit >= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask >= i2.M_mask));
#endif
  }

template<int DIRECTION>
  inline bool
  operator>=(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
  {
#ifdef __i386__
    if (DIRECTION == forwards_iterating)
      return (i1.M_index >= i2.M_index);
    else
      return (i1.M_index <= i2.M_index);
#else
    if (DIRECTION == forwards_iterating)
      return (i1.M_digit >= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask >= i2.M_mask));
    else
      return (i1.M_digit <= i2.M_digit || (i1.M_digit == i2.M_digit && i1.M_mask <= i2.M_mask));
#endif
  }

template<int DIRECTION>
  inline void
  bitset_index_iterator<DIRECTION>::increment(void)
  {
    if (DIRECTION == forwards_iterating)
      left();
    else
      right();
  }

template<int DIRECTION>
  inline void
  bitset_index_iterator<DIRECTION>::decrement(void)
  {
    if (DIRECTION == forwards_iterating)
      right();
    else
      left();
  }

template<int DIRECTION>
  inline void
  bitset_index_iterator<DIRECTION>::increment(int n)
  {
    if (DIRECTION == forwards_iterating)
      left(n);
    else
      right(n);
  }

template<int DIRECTION>
  inline void
  bitset_index_iterator<DIRECTION>::decrement(int n)
  {
    if (DIRECTION == forwards_iterating)
      right(n);
    else
      left(n);
  }

template<int DIRECTION>
  inline int
  operator-(bitset_index_iterator<DIRECTION> const& i1, bitset_index_iterator<DIRECTION> const& i2)
  {
    return (DIRECTION == forwards_iterating) ? subtract(i1, i2) : subtract(i2, i1);
  }

// Forward declarations.
template<unsigned int N, int DIRECTION> classbitset_iterator;
template<unsigned int N, int DIRECTION> bitset_iterator<N, DIRECTION> operator+(bitset_iterator<N, DIRECTION> const&, int);
template<unsigned int N, int DIRECTION> bitset_iterator<N, DIRECTION> operator+(int, bitset_iterator<N, DIRECTION> const&);
template<unsigned int N, int DIRECTION> bitset_iterator<N, DIRECTION> operator-(bitset_iterator<N, DIRECTION> const&, int);
template<unsigned int N, int DIRECTION> bitset_iterator<N, DIRECTION> operator-(int, bitset_iterator<N, DIRECTION> const&);
template<unsigned int N> structbitset_base;
template<unsigned int N, bool inverted> classbitset_invertible;

template<unsigned int N, int DIRECTION>
  classbitset_iterator : public bitset_index_iterator<DIRECTION>,
                          public std::iterator<std::random_access_iterator_tag, bitset_digit_t,
                                               int, bitset_digit_t*, bitset_digit_t&> {
    protected:
      bitset_base<N> const* M_bitset_ptr;

    public:
      // Default Constructible
      bitset_iterator(void);

      // Assignable
      bitset_iterator(bitset_iterator const& iter);
      bitset_iterator& operator=(bitset_iterator const& iter);
      bitset_iterator& operator=(bitset_index_iterator<DIRECTION> const& index);

      // Dereferencable
      bitset_digit_t operator*() const;

      // Bi-directional iterator
      //
      bitset_iterator& operator++();
      bitset_iterator operator++(int);
      bitset_iterator& operator--();
      bitset_iterator operator--(int);

      // Random Access Iterator
      //
      bitset_iterator& operator+=(int n);
      friend bitset_iterator operator+ <>(bitset_iterator const& i, int n);
      friend bitset_iterator operator+ <>(int n, bitset_iterator const& i);
      bitset_iterator& operator-=(int n);
      friend bitset_iterator operator- <>(bitset_iterator const& i, int n);
      friend bitset_iterator operator- <>(int n, bitset_iterator const& i);
      bitset_digit_t operator[](int n) const;

      // Special
      //
      bitset_iterator(bitset_base<N> const* bitset_ptr, int bit);
      void find1(void);

#ifndef __i386__
    private:
      void find1_forward(void);
      void find1_backward(void);
#endif
  };

template<unsigned int N>
  structbitset_base {
    public:
      // Fix this if you add members in front of vector.
      static size_t const offsetof_vector = 0; //sizeof(bitset_digit_t);

    public:
      static unsigned int const number_of_bits = N;

      static unsigned int const digits = (N == 0) ? 0 : ((N - 1) / bitset_digit_bits + 1);

      // ! The number of valid bits in the most significant digit.
      static unsigned int const number_of_valid_bits = bitset_digit_bits - (digits * bitset_digit_bits - N);

      static bitset_digit_t const valid_bits = ((static_cast<bitset_digit_t>(1) << (number_of_valid_bits - 1)) << 1) - 1;

      static bool const has_excess_bits = ((digits * bitset_digit_bits) != N);

    protected:
      //bitset_digit_t empty_space1;
      bitset_digit_t vector[digits];
      //bitset_digit_t empty_space2;

      template<unsigned int n1, bool i1, unsigned int n2, bool i2>
        friend bool operator==(bitset_invertible<n1, i1> const&, bitset_invertible<n2, i2> const&);

      template<unsigned int n1, bool i1, unsigned int n2, bool i2>
        friend bool operator!=(bitset_invertible<n1, i1> const&, bitset_invertible<n2, i2> const&);

    public:
      // Digit representation
      bitset_digit_t& rawdigit(unsigned int d) { return this->vector[d]; }
      bitset_digit_t rawdigit(unsigned int d) const{ return this->vector[d]; }
      bitset_digit_t* digits_ptr(void) { return this->vector; }
      bitset_digit_t const* digits_ptr(void) const{ return this->vector; }
      uint32_t digit32(unsigned int d32) const
     {
        if (sizeof(bitset_digit_t) == 4)
          return this->vector[d32];
        else
        {
          unsigned int d = d32 / (sizeof(bitset_digit_t) / 4);
          unsigned int r = d32 % (sizeof(bitset_digit_t) / 4);
#if __BYTE_ORDER == __LITTLE_ENDIAN
          return (this->vector[d] >> (r * 32));
#elif __BYTE_ORDER == __BIG_ENDIAN
          return (this->vector[d] >> (bitset_digit_bits - 32 - (r * 32)));
#endif
        }
      }

    public:
      // Iterator stuff.
      typedef bitset_iterator<N, forwards_iterating> const_iterator;
      typedef bitset_iterator<N, backwards_iterating> const_reverse_iterator;
      const_iterator begin(void) const{ return const_iterator(this, 0); }
      const_iterator end(void) const{ return const_iterator(this, N); }
      const_reverse_iterator rbegin(void) const{ return const_reverse_iterator(this, N - 1); }
      const_reverse_iterator rend(void) const{ return const_reverse_iterator(this, -1); }

      template<unsigned int m>
        void xor_with_zero_padded(bitset_base<m> const& bitset, int lsb, int msb, int shift);

      // Slower functions for shifting an arbitrary distance.
      void operator<<=(unsigned int shift);
      void operator>>=(unsigned int shift);

      // Single bit operations
      bool test(size_t n) const;                                        // Return true if bit `n' is set.
      bool odd(void) const;                                             // Return true if the vector has an odd number of bits set.
      void set(size_t n);                                               // Set bit `n'.
      void clear(size_t n);                                             // Clear bit `n'.
      void flip(size_t n);                                              // Toggle bit `n'.

      // Single bit operations using iterators.
      bool test(bitset_index const& index) const;                       // Return true if bit refered to by `index' is set.
      void set(bitset_index const& index);                              // Set bit refered to by `index'.
      void clear(bitset_index const& index);                            // Clear bit refered to by `index'.
      void flip(bitset_index const& index);                             // Toggle bit refered to by `index'.

      // Single bit operations at a constant position
      template<unsigned int pos>
        bool test(void) const;                                          // Return true if bit `pos' is set.
      template<unsigned int pos>
        void set(void);                                                 // Set bit `pos'.
      template<unsigned int pos>
        void clear(void);                                               // Clear bit `pos'.
      template<unsigned int pos>
        void flip(void);                                                // Toggle bit `pos'.

      // Other functions
      void reset(void);
      void setall(void);
      bool any(void) const;
  };

template<unsigned int N>
  template<unsigned int m>
#if defined(__i386__) && defined(HAVE_NASM)
  inline
#endif
  void
  bitset_base<N>::xor_with_zero_padded(bitset_base<m> const& bitset, int lsb, int msb, int shift)
  {
#if defined(__i386__) && defined(HAVE_NASM)
    libecc_shift_xorassign(this->vector, bitset.digits_ptr(), lsb, msb, shift);
#else
    int digit1 = lsb >> bitset_digit_bits_log2;
    int digit2 = msb >> bitset_digit_bits_log2;
    bitset_digit_t d1 = 0;
    // We can't use bitset.digit() because we need access to negative indexes.
    bitset_digit_t const* const digits_ptr = bitset.digits_ptr();
    if (shift < 0)
    {
      int bitshift = (-shift) & (bitset_digit_bits - 1);
      int digitshift = (-shift) >> bitset_digit_bits_log2;
      if (bitshift == 0)
      {
        for (int digit = digit2; digit >= digit1; --digit)
        {
          bitset_digit_t d2 = digits_ptr[digit];
          this->vector[digit - digitshift] ^= d2;
        }
      }
      else
      {
        for (int digit = digit2; digit >= digit1; --digit)
        {
          bitset_digit_t d2 = digits_ptr[digit];
          this->vector[digit - digitshift] ^= (d2 >> bitshift) | (d1 << (bitset_digit_bits - bitshift));
          d1 = d2;
        }
        this->vector[digit1 - 1 - digitshift] ^= (d1 << (bitset_digit_bits - bitshift));
      }
    }
    else if (shift > 0)
    {
      int bitshift = shift & (bitset_digit_bits - 1);
      int digitshift = shift >> bitset_digit_bits_log2;
      if (bitshift == 0)
      {
        for (int digit = digit1; digit <= digit2; ++digit)
        {
          bitset_digit_t d2 = digits_ptr[digit];
          this->vector[digit + digitshift] ^= d2;
          d1 = d2;
        }
      }
      else
      {
        for (int digit = digit1; digit <= digit2; ++digit)
        {
          bitset_digit_t d2 = digits_ptr[digit];
          this->vector[digit + digitshift] ^= (d2 << bitshift) | (d1 >> (bitset_digit_bits - bitshift));
          d1 = d2;
        }
        this->vector[digit2 + 1 + digitshift] ^= (d1 >> (bitset_digit_bits - bitshift));
      }
    }
    else
    {
      for (int digit = digit1; digit <= digit2; ++digit)
        this->vector[digit] ^= digits_ptr[digit];
    }
#endif
  }

#ifndef HIDE_FROM_DOXYGEN
namespaceOperator {

#ifdef __i386__

//
// Due to heavily broken inlining heuristics of gcc,
// we are forced to use macros to do the assembly
// inlining.  There is no alternative, I tried everything.
//

#define LIBECC_INVERT "xorl $-1,%%eax\n\t"
#define LIBECC_NOTHING ""

#define LIBECC_ASMLOOP(destination, source, count, OPCODE, OPTIONAL_INVERT)     \
  do {                                                  \
    int __d0, __d1, __d2;                               \
    __asm__ __volatile__ (                              \
      "\n1:\n\t"                                        \
        "movl (%5,%%ecx,4),%%eax\n\t"                   \
        OPTIONAL_INVERT                                 \
        OPCODE " %%eax,(%4,%%ecx,4)\n\t"                \
        "decl %%ecx\n\t"                                \
        "jnz 1b"                                        \
        : "=c" (__d0), "=&r" (__d1), "=&r" (__d2)       \
        : "0" (count),                                  \
          "1" ((destination) - 1),                      \
          "2" ((source) - 1)                            \
        : "%eax", "memory"                              \
    );                                                  \
  } while(0)

#define LIBECC_ASMLOOP_BODY(OPCODE, destination, source, count, inverted) \
  do { \
    if (inverted) \
      LIBECC_ASMLOOP(destination, source, count, OPCODE, LIBECC_INVERT); \
    else \
      LIBECC_ASMLOOP(destination, source, count, OPCODE, LIBECC_NOTHING); \
  } while(0)

#define LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, OPTIONAL_INVERT1, OPCODE2, OPTIONAL_INVERT3)              \
  do {                                                          \
    int __d0, __d1, __d2, __d3;                                 \
    __asm__ __volatile__ (                                      \
      "\n1:\n\t"                                                \
        "movl (%6,%%ecx,4),%%eax\n\t"                           \
        OPTIONAL_INVERT1                                        \
        OPCODE2 " (%7,%%ecx,4),%%eax\n\t"                       \
        OPTIONAL_INVERT3                                        \
        OPCODE " %%eax,(%5,%%ecx,4)\n\t"                        \
        "decl %%ecx\n\t"                                        \
        "jnz 1b"                                                \
        : "=c" (__d0), "=&r" (__d1), "=&r" (__d2), "=&r" (__d3) \
        : "0" (count),                                          \
          "1" ((destination) - 1),                              \
          "2" ((source1) - 1),                                  \
          "3" ((source2) - 1)                                   \
        : "%eax", "memory"                                      \
    );                                                          \
  } while(0)

#define LIBECC_ASMLOOP2_BODY(OPCODE, OPERATOR, inverted1, inverted2, destination, source1, source2, count) \
  do { \
    if (OPERATOR::id == libecc::Operator::bitsetAND::id) \
    { \
      if (inverted1 && inverted2) \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "orl", LIBECC_INVERT); \
      else if (inverted1) \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_INVERT, "andl", LIBECC_NOTHING); \
      else if (inverted2) \
        LIBECC_ASMLOOP2(destination, source2, source1, count, OPCODE, LIBECC_INVERT, "andl", LIBECC_NOTHING); \
      else \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "andl", LIBECC_NOTHING); \
    } \
    else if (OPERATOR::id == libecc::Operator::bitsetOR::id) \
    { \
      if (inverted1 && inverted2) \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "andl", LIBECC_INVERT); \
      else if (inverted1) \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_INVERT, "orl", LIBECC_NOTHING); \
      else if (inverted2) \
        LIBECC_ASMLOOP2(destination, source2, source1, count, OPCODE, LIBECC_INVERT, "orl", LIBECC_NOTHING); \
      else \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "orl", LIBECC_NOTHING); \
    } \
    else if (OPERATOR::id == libecc::Operator::bitsetXOR::id) \
    { \
      if (inverted1 == inverted2) \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "xorl", LIBECC_NOTHING); \
      else \
        LIBECC_ASMLOOP2(destination, source1, source2, count, OPCODE, LIBECC_NOTHING, "xorl", LIBECC_INVERT); \
    } \
  } while(0)

#define LIBECC_INLINE_ASMLOOP(ID, destination, source, count, inverted) \
    do { \
      if (ID == libecc::Operator::bitsetAssign::id) \
      { \
        LIBECC_ASMLOOP_BODY("movl", destination, source, count, inverted); \
      } \
      else if (ID == libecc::Operator::bitsetANDAssign::id) \
      { \
        LIBECC_ASMLOOP_BODY("andl", destination, source, count, inverted); \
      } \
      else if (ID == libecc::Operator::bitsetORAssign::id) \
      { \
        LIBECC_ASMLOOP_BODY("orl", destination, source, count, inverted); \
      } \
      else if (ID == libecc::Operator::bitsetXORAssign::id) \
      { \
        LIBECC_ASMLOOP_BODY("xorl", destination, source, count, inverted); \
      } \
    } while(0)

#define LIBECC_INLINE_ASMLOOP2(ID, OPERATOR, inverted1, inverted2, destination, source1, source2, count) \
    do { \
      if (ID == libecc::Operator::bitsetAssign::id) \
      { \
        LIBECC_ASMLOOP2_BODY("movl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
      } \
      else if (ID == libecc::Operator::bitsetANDAssign::id) \
      { \
        LIBECC_ASMLOOP2_BODY("andl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
      } \
      else if (ID == libecc::Operator::bitsetORAssign::id) \
      { \
        LIBECC_ASMLOOP2_BODY("orl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
      } \
      else if (ID == libecc::Operator::bitsetXORAssign::id) \
      { \
        LIBECC_ASMLOOP2_BODY("xorl", OPERATOR, inverted1, inverted2, destination, source1, source2, count); \
      } \
    } while(0)

#define LIBECC_ASMSHIFTRIGHT0(OP1)                      \
              __asm__ __volatile__ (                    \
                  "movl 4(%%esi),%%edx\n\t"             \
                  "shrl $1,%%edx\n\t"                   \
                  OP1                                   \
                  "movl %%edx,4(%%edi)"                 \
                : "=&S" (ptr1),                         \
                  "=&D" (ptr2)                          \
                : "0" (&this->vector[initial - count]), \
                  "1" (&result.vector[initial - count]) \
                : "%eax", "%edx", "memory", "cc"        \
              )

#if 0   // NOT faster.
#define LIBECC_OP1_SOURCE "(%%esi)"
#define LIBECC_OP2_SOURCE "(%%esi)"
#define LIBECC_OP1_DESTINATION "(%%edi)"
#define LIBECC_OP2_DESTINATION "(%%edi)"
#define LIBECC_WORKREG "%%eax"
#define LIBECC_CLOBBER "%eax"
#define LIBECC_INIT "std\n\t"
#define LIBECC_LOAD1 "lodsl\n\t"
#define LIBECC_SHIFT "shrl $1," LIBECC_WORKREG "\n\t"
#define LIBECC_STORE1 "stosl\n\t"
#define LIBECC_LOAD2 "lodsl\n\t"
#define LIBECC_ROTATE "rcrl $1," LIBECC_WORKREG "\n\t"
#define LIBECC_STORE2 "stosl\n\t"
#define LIBECC_DEINIT "cld\n\t"
#define LIBECC_RIGHT_PRESERVE_CF(OPERAND) "setc %%edx\n\t" OPERAND "\n\tbt $0,%%edx\n\t"
#define LIBECC_PRESERVE_CF_CLOBBER LIBECC_CLOBBER,"%edx"
#define LIBECC_INITIAL_ESI &this->vector[initial]
#define LIBECC_INITIAL_EDI &result.vector[initial]
#else
#define LIBECC_OP1_SOURCE "4(%%esi,%%ecx,4)"
#define LIBECC_OP2_SOURCE "(%%esi,%%ecx,4)"
#define LIBECC_OP1_DESTINATION "4(%%edi,%%ecx,4)"
#define LIBECC_OP2_DESTINATION "(%%edi,%%ecx,4)"
#define LIBECC_WORKREG "%%edx"
#define LIBECC_CLOBBER "%edx"
#define LIBECC_INIT
#define LIBECC_LOAD1 "movl " LIBECC_OP1_SOURCE "," LIBECC_WORKREG "\n\t"
#define LIBECC_SHIFT "shrl $1," LIBECC_WORKREG "\n\t"
#define LIBECC_STORE1 "movl " LIBECC_WORKREG "," LIBECC_OP1_DESTINATION "\n\t"
#define LIBECC_LOAD2 "movl " LIBECC_OP2_SOURCE "," LIBECC_WORKREG "\n\t"
#define LIBECC_ROTATE "rcrl $1," LIBECC_WORKREG "\n\t"
#define LIBECC_STORE2 "movl " LIBECC_WORKREG "," LIBECC_OP2_DESTINATION "\n\t"
#define LIBECC_DEINIT
#define LIBECC_RIGHT_PRESERVE_CF(OPERAND) "lahf\n\t" OPERAND "\n\tsahf\n\t"
#define LIBECC_PRESERVE_CF_CLOBBER LIBECC_CLOBBER,"%eax"
#define LIBECC_INITIAL_ESI &this->vector[initial - count]
#define LIBECC_INITIAL_EDI &result.vector[initial - count]
#endif

#define LIBECC_ASMSHIFTRIGHT1(OP1, OP2, CLOBBER)        \
              __asm__ __volatile__ (                    \
                  LIBECC_INIT                           \
                  LIBECC_LOAD1                          \
                  LIBECC_SHIFT                          \
                  OP1                                   \
                  LIBECC_STORE1                         \
                "1:\n\t"                                \
                  LIBECC_LOAD2                          \
                  LIBECC_ROTATE                         \
                  OP2                                   \
                  LIBECC_STORE2                         \
                  "decl %%ecx\n\t"                      \
                  "jnz 1b\n\t"                          \
                  LIBECC_DEINIT                         \
                : "=&S" (ptr1),                         \
                  "=&D" (ptr2),                         \
                  "=&c" (c)                             \
                : "0" (LIBECC_INITIAL_ESI),             \
                  "1" (LIBECC_INITIAL_EDI),             \
                  "2" (count - 1)                       \
                : "memory", "cc", CLOBBER               \
              )

#define LIBECC_ASMSHIFTLEFT(OP1, OP2, FINISH)           \
              __asm__ __volatile__ (                    \
                  "movl -4(%%esi),%%edx\n\t"            \
                  "shll $1,%%edx\n\t"                   \
                  OP1                                   \
                  "movl %%edx,-4(%%edi)\n\t"            \
                  "jecxz 2f\n"                          \
                "1:\n\t"                                \
                  "movl (%%esi),%%edx\n\t"              \
                  "rcll $1,%%edx\n\t"                   \
                  OP2                                   \
                  "movl %%edx,(%%edi)\n\t"              \
                  "leal 4(%%esi),%%esi\n\t"             \
                  "leal 4(%%edi),%%edi\n\t"             \
                  "decl %%ecx\n\t"                      \
                  "jnz 1b\n"                            \
                "2:\n\t"                                \
                  FINISH                                \
                : "=&S" (ptr1),                         \
                  "=&D" (ptr2),                         \
                  "=&c" (c)                             \
                : "0" (&this->vector[initial + 1]),     \
                  "1" (&result.vector[initial + 1]),    \
                  "2" (count - 1),                      \
                  "n" (bitset_base<N>::valid_bits)      \
                : "%eax", "%edx", "memory", "cc"        \
              )

#define LIBECC_ASMSHIFTLEFT_FINISH(OP)                  \
                  "movl (%%esi),%%edx\n\t"              \
                  "rcll $1,%%edx\n\t"                   \
                  "andl %6,%%edx\n\t"                   \
                  OP                                    \
                  "movl %%edx,(%%edi)"

#define LIBECC_LEFT_PRESERVE_CF(OPERAND) "lahf\n\t" OPERAND "\n\tsahf\n\t"

#endif // __i386__

// Functors.

// Functor for '&'.
structbitsetAND {
  static int const id = 1;
  static inline bitset_digit_t exec(bitset_digit_t digit1, bitset_digit_t digit2) { return digit1 & digit2; }
  template<bool inverted1, bool inverted2>
   structexecbool {
     static bool const value = inverted1 && inverted2;
   };
};

// Functor for '|'.
structbitsetOR {
  static int const id = 2;
  static inline bitset_digit_t exec(bitset_digit_t digit1, bitset_digit_t digit2) { return digit1 | digit2; }
  template<bool inverted1, bool inverted2>
   structexecbool {
     static bool const value = inverted1 || inverted2;
   };
};

// Functor for '^'.
structbitsetXOR {
  static int const id = 3;
  static inline bitset_digit_t exec(bitset_digit_t digit1, bitset_digit_t digit2) { return digit1 ^ digit2; }
  template<bool inverted1, bool inverted2>
   structexecbool {
     static bool const value = (inverted1 != inverted2);
   };
};

// Functor for '='.
structbitsetAssign {
  static int const id = 1;
  static bool const sets_excess_bits = true;
  static bool const with_zero_sets_zero = true;
  static bool const with_ones_sets_ones = true;
  static bool const with_ones_inverts = false;
  static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out = in; }
};

// Functor for '&='.
structbitsetANDAssign {
  static int const id = 2;
  static bool const sets_excess_bits = false;
  static bool const with_zero_sets_zero = true;
  static bool const with_ones_sets_ones = false;
  static bool const with_ones_inverts = false;
  static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out &= in; }
};

// Functor for '|='.
structbitsetORAssign {
  static int const id = 3;
  static bool const sets_excess_bits = true;
  static bool const with_zero_sets_zero = false;
  static bool const with_ones_sets_ones = true;
  static bool const with_ones_inverts = false;
  static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out |= in; }
};

// Functor for '^='.
structbitsetXORAssign {
  static int const id = 4;
  static bool const sets_excess_bits = true;
  static bool const with_zero_sets_zero = false;
  static bool const with_ones_sets_ones = false;
  static bool const with_ones_inverts = true;
  static inline void exec(bitset_digit_t& out, bitset_digit_t in) { out ^= in; }
};

#if LIBECC_TRACK_EXPR_TEMPORARIES
extern std::multiset<void const*> bitsetExpression_bitset_invertible_pointers;
#endif

template<unsigned int N, bool inverted1, bool inverted2, typename OP>
  structbitsetExpression
  {
    bitset_invertible<N, inverted1> const& first;
    bitset_invertible<N, inverted2> const& second;
    OP op;

    bitsetExpression(bitset_invertible<N, inverted1> const& arg1, bitset_invertible<N, inverted2> const& arg2) :
        first(arg1), second(arg2)
    {
      // I found a problem with a destructed temporary that was still in use.
      // It seems that the pointer to this destructed temporary is stored in
      // this object.  The following code is added in order to debug this
      // problem.
#if LIBECC_TRACK_EXPR_TEMPORARIES
      bitsetExpression_bitset_invertible_pointers.insert(&arg1);
      bitsetExpression_bitset_invertible_pointers.insert(&arg2);
      LibEccDout(dc::notice, "Constructed a bitsetExpression with arguments " <<
          (void const*)&first << " and " << (void const*)&second);
#endif
    }
#if LIBECC_TRACK_EXPR_TEMPORARIES
    ~bitsetExpression();
#endif
  };

#if LIBECC_TRACK_EXPR_TEMPORARIES
template<unsigned int N, bool inverted1, bool inverted2, typename OP>
  bitsetExpression<N, inverted1, inverted2, OP>::~bitsetExpression()
  {
    bitsetExpression_bitset_invertible_pointers.erase(bitsetExpression_bitset_invertible_pointers.find(&first));
    bitsetExpression_bitset_invertible_pointers.erase(bitsetExpression_bitset_invertible_pointers.find(&second));
    LibEccDout(dc::notice, "Destructed bitsetExpression with arguments " <<
        (void const*)&first << " and " << (void const*)&second);
  }
#endif

} // namespace Operator
#endif // HIDE_FROM_DOXYGEN

template<unsigned int N, bool inverted>
  classbitset_invertible : public bitset_base<N> {
    public:
      // Constructors
      bitset_invertible(void);
      template<typename Expression>
        explicit bitset_invertible(Expression const&);

#if LIBECC_TRACK_EXPR_TEMPORARIES
      ~bitset_invertible();
#endif

    protected:
      template<typename OP, unsigned int x, bool invertedx>
        void assign(bitset_invertible<x, invertedx> const&, OP);
      template<typename OP1, unsigned int x, bool inverted1, bool inverted2, typename OP2>
        void assign(Operator::bitsetExpression<x, inverted1, inverted2, OP2> const&, OP1);

    private:
      template<unsigned int m, bool i>
        friend classbitset_invertible;

    public:
      void base2_print_on(std::ostream& os) const;

      bitset_digit_t digit(unsigned int d) const{ return inverted ? ~this->vector[d] : this->vector[d]; }
  };

#if LIBECC_TRACK_EXPR_TEMPORARIES
template<unsigned int N, bool inverted>
  bitset_invertible<N, inverted>::~bitset_invertible()
  {
    LibEccDout(dc::notice, "Destructing bitset_invertible at " << (void*)this);
    if (Operator::bitsetExpression_bitset_invertible_pointers.find(this) !=
        Operator::bitsetExpression_bitset_invertible_pointers.end())
      LibEccDoutFatal(dc::core, "This object is still in use by a bitsetExpression!");
  }
#endif

template<unsigned int N, bool inverted>
  void
  bitset_invertible<N, inverted>::base2_print_on(std::ostream& os) const
 {
    // Binary representation
    for (int d = bitset_base<N>::digits - 1; d >= 0; --d)
      for (bitset_digit_t mask = (~static_cast<bitset_digit_t>(0) >> 1) + 1; mask != 0; mask >>= 1)
        if (d != bitset_base<N>::digits - 1 || (mask & bitset_base<N>::valid_bits))
        {
          if ((this->digit(d) & mask) == inverted)
            os << '0';
          else
            os << '1';
        }
  }

// Default constructor.
template<unsigned int N, bool inverted>
  inline
  bitset_invertible<N, inverted>::bitset_invertible(void)
  {
    if (bitset_base<N>::has_excess_bits)
      this->vector[bitset_base<N>::digits - 1] = 0;                     // Reset the excess bits!
  }

// Copy constructor.
template<unsigned int N, bool inverted>
  template<typename Expression>
    inline
    bitset_invertible<N, inverted>::bitset_invertible(Expression const& expr)
    {
      this->assign(expr, Operator::bitsetAssign());
    }

//
// Assignment function.
// This function handles:
//
// a = b;
// a = ~b;
// a &= b;
// a &= ~b;
// a |= b;
// a |= ~b;
// a ^= b;
// a ^= ~b;
//
// ASSIGNMENT_OPERATOR is one of bitsetAssign, bitsetANDAssign, bitsetORAssign or bitsetXORAssign.
//
template<unsigned int N, bool inverted>
  template<typename ASSIGNMENT_OPERATOR, unsigned int x, bool inverted_argument>
    inline void
    bitset_invertible<N, inverted>::assign(bitset_invertible<x, inverted_argument> const& bits, ASSIGNMENT_OPERATOR)
    {
      // Handle excess digits.
      if (bitset_base<N>::digits > bitset_base<x>::digits)
      {
        if (!inverted_argument)
        {
          // Fill excess digits with 0's when needed.
          if (ASSIGNMENT_OPERATOR::with_zero_sets_zero)
            std::memset(&this->vector[bitset_base<x>::digits], 0, (bitset_base<N>::digits - bitset_base<x>::digits) * sizeof(bitset_digit_t));
        }
        else
        {
          // Fill excess digits with 1's when needed.
          if (ASSIGNMENT_OPERATOR::with_ones_sets_ones)
          {
            unsigned int const count = bitset_base<N>::digits - bitset_base<x>::digits - 1;
            if (count)
              std::memset(&this->vector[bitset_base<x>::digits], 0xff, count * sizeof(bitset_digit_t));
            this->vector[bitset_base<N>::digits - 1] = bitset_base<N>::valid_bits;
          }
          // Or invert them.
          if (ASSIGNMENT_OPERATOR::with_ones_inverts)
          {
#ifdef __i386__
            int __d0, __d1;
            __asm__ __volatile__ (
                "xorl %4,(%1)\n\t"
                "jecxz 2f\n\t"
                "subl %5,%1\n"
        "1:\n\t"
                "xorl $-1,(%1,%%ecx,4)\n\t"
                "decl %%ecx\n\t"
                "jnz 1b\n"
        "2:"
                : "=&c" (__d0), "=&r" (__d1)
                : "0" (bitset_base<N>::digits - bitset_base<x>::digits - 1), "1" (&this->vector[bitset_base<N>::digits - 1]),
                  "n" (bitset_base<N>::valid_bits), "n" ((bitset_base<N>::digits - bitset_base<x>::digits) * 4)
                : "memory", "cc"
            );
#else
            this->vector[bitset_base<N>::digits - 1] ^= bitset_base<N>::valid_bits;
            unsigned int count = bitset_base<N>::digits - bitset_base<x>::digits;
            while(--count) { this->vector[count + bitset_base<x>::digits - 1] ^= ~static_cast<bitset_digit_t>(0); }
#endif
          }
        }
      }

      // Handle other digits.
#ifdef __i386__
      LIBECC_INLINE_ASMLOOP(ASSIGNMENT_OPERATOR::id,
          this->vector, bits.digits_ptr(),
          ((bitset_base<N>::digits > bitset_base<x>::digits) ? bitset_base<x>::digits : bitset_base<N>::digits),
          inverted_argument);
#else
      unsigned int d;
      if (bitset_base<N>::digits > bitset_base<x>::digits)
        d = bitset_base<x>::digits - 1;
      else
        d = bitset_base<N>::digits - 1;
      ASSIGNMENT_OPERATOR::exec(this->vector[d], inverted_argument ? ~bits.rawdigit(d) : bits.rawdigit(d));
      while(d) { --d; ASSIGNMENT_OPERATOR::exec(this->vector[d], inverted_argument ? ~bits.rawdigit(d) : bits.rawdigit(d)); }
#endif

      // Reset excess bits if needed.
      if (((!inverted_argument && x > N) ||
            (inverted_argument && bitset_base<N>::digits <= bitset_base<x>::digits)) &&
          bitset_base<N>::has_excess_bits && ASSIGNMENT_OPERATOR::sets_excess_bits)
        this->vector[bitset_base<N>::digits - 1] &= bitset_base<N>::valid_bits;
    }

//
// Assignment function for expressions.
// This function handles:
//
// a = b & c;
// a = b & ~c;
// a = ~b & c;
// a = ~b & ~b;
// a = b | c;
// a = b | ~c;
// a = ~b | c;
// a = ~b | ~b;
// a = b ^ c;
// a = b ^ ~c;
// a = ~b ^ c;
// a = ~b ^ ~b;
// a &= b & c;
// a &= b & ~c;
// a &= ~b & c;
// a &= ~b & ~b;
// a &= b | c;
// a &= b | ~c;
// a &= ~b | c;
// a &= ~b | ~b;
// a &= b ^ c;
// a &= b ^ ~c;
// a &= ~b ^ c;
// a &= ~b ^ ~b;
// a |= b & c;
// a |= b & ~c;
// a |= ~b & c;
// a |= ~b & ~b;
// a |= b | c;
// a |= b | ~c;
// a |= ~b | c;
// a |= ~b | ~b;
// a |= b ^ c;
// a |= b ^ ~c;
// a |= ~b ^ c;
// a |= ~b ^ ~b;
// a ^= b & c;
// a ^= b & ~c;
// a ^= ~b & c;
// a ^= ~b & ~b;
// a ^= b | c;
// a ^= b | ~c;
// a ^= ~b | c;
// a ^= ~b | ~b;
// a ^= b ^ c;
// a ^= b ^ ~c;
// a ^= ~b ^ c;
// a ^= ~b ^ ~b;
//
// ASSIGNMENT_OPERATOR is one of bitsetAssign, bitsetANDAssign, bitsetORAssign or bitsetXORAssign.
// OPERATOR is one of bitsetAND, bitsetOR or bitsetXOR.
//
template<unsigned int N, bool inverted>
  template<typename ASSIGNMENT_OPERATOR, unsigned int x, bool inverted1, bool inverted2, typename OPERATOR>
    inline void
    bitset_invertible<N, inverted>::assign(Operator::bitsetExpression<x, inverted1, inverted2, OPERATOR> const& expr, ASSIGNMENT_OPERATOR)
    {
      static bool const argument_has_leading_ones = OPERATOR::template execbool<inverted1, inverted2>::value;

      // Handle excess digits.
      if (bitset_base<N>::digits > bitset_base<x>::digits)
      {
        if (!argument_has_leading_ones)
        {
          // Fill excess digits with 0's when needed.
          if (ASSIGNMENT_OPERATOR::with_zero_sets_zero)
            std::memset(&this->vector[bitset_base<x>::digits], 0, (bitset_base<N>::digits - bitset_base<x>::digits) * sizeof(bitset_digit_t));
        }
        else
        {
          // Fill excess digits with 1's when needed.
          if (ASSIGNMENT_OPERATOR::with_ones_sets_ones)
          {
            unsigned int const count = bitset_base<N>::digits - bitset_base<x>::digits - 1;
            if (count)
              std::memset(&this->vector[bitset_base<x>::digits], 0xff, count * sizeof(bitset_digit_t));
            this->vector[bitset_base<N>::digits - 1] = bitset_base<N>::valid_bits;
          }
          // Or invert them.
          if (ASSIGNMENT_OPERATOR::with_ones_inverts)
          {
#ifdef __i386__
            int __d0, __d1;
            __asm__ __volatile__ (
                "xorl %4,(%1)\n\t"
                "jecxz 2f\n\t"
                "subl %5,%1\n"
        "1:\n\t"
                "xorl $-1,(%1,%%ecx,4)\n\t"
                "decl %%ecx\n\t"
                "jnz 1b\n"
        "2:"
                : "=&c" (__d0), "=&r" (__d1)
                : "0" (bitset_base<N>::digits - bitset_base<x>::digits - 1), "1" (&this->vector[bitset_base<N>::digits - 1]),
                  "n" (bitset_base<N>::valid_bits), "n" ((bitset_base<N>::digits - bitset_base<x>::digits) * 4)
                : "memory", "cc"
            );
#else
            this->vector[bitset_base<N>::digits - 1] ^= bitset_base<N>::valid_bits;
            unsigned int count = bitset_base<N>::digits - bitset_base<x>::digits;
            while(--count) { this->vector[count + bitset_base<x>::digits - 1] ^= ~static_cast<bitset_digit_t>(0); }
#endif
          }
        }
      }

      // Handle other digits.
#ifdef __i386__
      LIBECC_INLINE_ASMLOOP2(ASSIGNMENT_OPERATOR::id, OPERATOR, inverted1, inverted2,
          this->vector, expr.first.digits_ptr(), expr.second.digits_ptr(),
          ((bitset_base<N>::digits > bitset_base<x>::digits) ? bitset_base<x>::digits : bitset_base<N>::digits));
#else
      unsigned int d;
      if (bitset_base<N>::digits < bitset_base<x>::digits)
        d = bitset_base<N>::digits - 1;
      else
        d = bitset_base<x>::digits - 1;
      for(;;)
      {
        ASSIGNMENT_OPERATOR::exec(this->vector[d],
            OPERATOR::exec(inverted1 ? ~expr.first.rawdigit(d) : expr.first.rawdigit(d),
                           inverted2 ? ~expr.second.rawdigit(d) : expr.second.rawdigit(d)));
        if (!d)
          break;
        --d;
      }
#endif

      // Reset excess bits if needed.
      if (((!argument_has_leading_ones && x > N) ||
            (argument_has_leading_ones && bitset_base<N>::digits <= bitset_base<x>::digits)) &&
          bitset_base<N>::has_excess_bits && ASSIGNMENT_OPERATOR::sets_excess_bits)
        this->vector[bitset_base<N>::digits - 1] &= bitset_base<N>::valid_bits;
    }

template<unsigned int N, bool inverted>
  inline bitset_invertible<N, !inverted> const&
  operator~(bitset_invertible<N, inverted> const& bits)
  {
    return *reinterpret_cast<bitset_invertible<N, !inverted> const*>(&bits);
  }

#ifndef __i386__
template<unsigned int N, int DIRECTION>
  void
  bitset_iterator<N, DIRECTION>::find1_forward(void)
  {
    if (this->M_digit < (int)bitset_base<N>::digits - 1 || (this->M_mask & bitset_base<N>::valid_bits))
    {
      register bitset_digit_t mask = this->M_mask;
      while(!(M_bitset_ptr->rawdigit(this->M_digit) & mask)) 
      {
        if ((mask <<= 1))
          continue;
        mask = 1;
        while(++(this->M_digit) < (int)bitset_base<N>::digits)
          if (M_bitset_ptr->rawdigit(this->M_digit))
            break;
        if (this->M_digit == (int)bitset_base<N>::digits)
        {
          this->M_digit = (N >> bitset_digit_bits_log2);
          mask = static_cast<bitset_digit_t>(1) << (N & (bitset_digit_bits - 1));
          break;
        }
      }
      this->M_mask = mask;
    }
  }

template<unsigned int N, int DIRECTION>
  void
  bitset_iterator<N, DIRECTION>::find1_backward(void)
  {
    LibEccDout(dc::bitsetfind1, "Entering find1_backward with: " << 
        libcwd::cwprint_using(*static_cast<bitset_invertible<N, false> const*>(M_bitset_ptr), &bitset_invertible<N, false>::base2_print_on));
    LibEccDout(dc::bitsetfind1, "Input: " << *this);
    if (this->M_digit >= 0)
    {
      register bitset_digit_t mask = this->M_mask;
      if (!(M_bitset_ptr->rawdigit(this->M_digit) & (mask | (mask - 1))))
      {
        mask = static_cast<bitset_digit_t>(1) << (bitset_digit_bits - 1);
        do
        {
          if (--(this->M_digit) < 0)
          {
            this->M_mask = mask;
            return;
          }
        }
        while (!M_bitset_ptr->rawdigit(this->M_digit));
      }
      while(!(M_bitset_ptr->rawdigit(this->M_digit) & mask)) 
        mask >>= 1;
      this->M_mask = mask;
    }
    LibEccDout(dc::bitsetfind1|flush_cf, "Output: " << *this);
  }
#endif

template<unsigned int N, int DIRECTION>
  inline void
  bitset_iterator<N, DIRECTION>::find1(void)
  {
    LibEccDout(dc::bitsetfind1, "Input: " << *this);
    LibEccDout(dc::bitsetfind1, "Entering find1 with: " << 
        libcwd::cwprint_using(*static_cast<bitset_invertible<N, false> const*>(M_bitset_ptr), &bitset_invertible<N, false>::base2_print_on));
#ifdef __i386__
    int bit_index, digit, ptr;
    if (DIRECTION == backwards_iterating)
    {
      __asm__ __volatile__ (
          // %eax: M_index (input) and work variable.
          // %ecx: bit_index (work variable).
          // %edi: &M_bitset_ptr->rawdigit(M_index/32 - 1) (input) and ptr (work variable).
          // %2  : digit (work variable).

          // Make a copy of M_index into %ecx, last time we used M_index.
          "movl %%eax,%%ecx\n\t"
          // Set %eax to its correct value by deviding it by 32.
          "sarl $5,%%eax\n\t"
          // Set bit_index to its correct value by taking the modulo 32 of it.
          "andl $31,%%ecx\n\t"
          // If M_index is -1, do nothing.
          "js 1f\n\t"
          // Copy the most significant digit, the digit with the
          // bit at which we will start the search, into %2.
          // digit = M_bitset_ptr->rawdigit(%eax)
          "movl 4(%%edi),%2\n\t"
          // Shift this digit left until the first bit comes at position 31.
          // bit_index = 31 - bit_index
          "xorl $31,%%ecx\n\t"
          // digit <<= bit_index
          "shll %%cl,%2\n\t"
          // See http://fatphil.org/x86/pentopt/19.html, chapter 19.3 for why we need the orl.
          // This is not needed for the athlon for that reason, but we also need this orl
          // for the case that %cl equals zero in which case the ZF is cleared!
          "orl %2,%2\n\t"                       
          // If there is no bit set in the current digit, goto digit_search.
          "jz 5f\n\t"
          // Search for the (next) most significant bit set.
          // This is slow on i[345]86: 11 + 2*N cycles; only generates 2 uops on a pentium though.
          "bsrl %2,%2\n\t"
          // Correct M_index to point to this bit.
          // %eax <<= 5
          "sall $5,%%eax\n\t"
          // %2 -= bit_index
          "subl %%ecx,%2\n\t"
          // M_index = %eax + %2
          "addl %2,%%eax\n\t"
          // Done.
          // goto exit
          "jmp 1f\n\t"
          ".align 16\n"
       "7:\n\t"                         // Main loop.
          "movl (%%edi),%2\n\t"
          "subl $4,%%edi\n\t"
          "testl %2,%2\n\t"
          "jnz 6f\n\t"
       "5:\n\t"                         // digit_search:
          "decl %%eax\n\t"
          // Repeat main loop.
          "jns 7b\n"    
       "4:\n\t"                         // reached_end:
          // No set bit found at all.  Set M_index to -1.
          "movl $-1,%%eax\n\t"
          // Done.
          // goto exit
          "jmp 1f\n"
          // Search for the most significant bit set in this digit.
       "6:\n\t"
          "bsrl %2,%2\n\t"
          // Correct M_index to point to this bit.
          "sall $5,%%eax\n\t"
          "addl %2,%%eax\n"
       "1:"                             // exit:

          : "=a" (this->M_index), "=&c" (bit_index), "=r" (digit), "=&D" (ptr)
          : "0" (this->M_index), "3" (M_bitset_ptr->digits_ptr() - 1 + (this->M_index >> 5))
          : "cc"
      );
    }
    else
    {
      __asm__ __volatile__ (
          // %eax: M_index (input) and work variable.
          // %ecx: bit_index (work variable).
          // %edi: &M_bitset_ptr->rawdigit(M_index/32 + 1) (input) and ptr (work variable).
          // %2  : digit (work variable).

          // if (M_index >= N) then goto exit
          "cmpl %6,%%eax\n\t"
          "jge 1f\n\t"
          // Make a copy of M_index into %ecx, last time we used M_index.
          "movl %%eax,%%ecx\n\t"
          // Set %eax to its correct value by deviding it by 32.
          "sarl $5,%%eax\n\t"
          // Set bit_index to its correct value by taking the modulo 32 of it.
          "andl $31,%%ecx\n\t"
          // Copy the least significant digit, the digit with the
          // bit at which we will start the search, into %2.
          // digit = M_bitset_ptr->rawdigit(%eax)
          "movl -4(%%edi),%2\n\t"
          // Shift this digit right until the first bit comes at position 0.
          // digit >>= bit_index
          "shrl %%cl,%2\n\t"
          // See http://fatphil.org/x86/pentopt/19.html, chapter 19.3 for why we need the orl.
          // This is not needed for the athlon for that reason, but we also need this orl
          // for the case that %cl equals zero in which case the ZF is cleared!
          "orl %2,%2\n\t"                       
          // If there is no bit set in the current digit, goto digit_search.
          "jz 5f\n\t"
          // Search for the (next) most significant bit set.
          // This is slow on i[345]86: 11 + 2*N cycles; only generates 2 uops on a pentium though.
          "bsfl %2,%2\n\t"
          // Correct M_index to point to this bit.
          // %eax <<= 5
          "sall $5,%%eax\n\t"
          // %2 -= bit_index
          "addl %%ecx,%2\n\t"
          // M_index = %eax + %2
          "addl %2,%%eax\n\t"
          // Done.
          // goto exit
          "jmp 1f\n\t"
          ".align 16\n"
       "7:\n\t"                         // Main loop.
          "movl (%%edi),%2\n\t"
          "addl $4,%%edi\n\t"
          "testl %2,%2\n\t"
          "jnz 6f\n\t"
       "5:\n\t"                         // digit_search:
          "incl %%eax\n\t"
          "cmpl %7, %%eax\n\t"
          // Repeat main loop.
          "jnz 7b\n"            
       "4:\n\t"                         // reached_end:
          // No set bit found at all.  Set M_index to N.
          "movl %6,%%eax\n\t"
          // Done.
          // goto exit
          "jmp 1f\n"
          // Search for the least significant bit set in this digit.
       "6:\n\t"
          "bsfl %2,%2\n\t"
          // Correct M_index to point to this bit.
          "sall $5,%%eax\n\t"
          "addl %2,%%eax\n"
       "1:"                             // exit:

          : "=a" (this->M_index), "=&c" (bit_index), "=r" (digit), "=&D" (ptr)
          : "0" (this->M_index), "3" (M_bitset_ptr->digits_ptr() + 1 + (this->M_index >> 5)),
            "n" (N), "n" (bitset_base<N>::digits)
          : "cc"
      );
    }
#else
    if (DIRECTION == forwards_iterating)
      find1_forward();
    else
      find1_backward();
#endif
    LibEccDout(dc::bitsetfind1|flush_cf, "Output: " << *this);
    return;
  }


template<unsigned int N, int DIRECTION>
  inline
  bitset_iterator<N, DIRECTION>::bitset_iterator(void)
  {
  }

template<unsigned int N, int DIRECTION>
  inline
  bitset_iterator<N, DIRECTION>::bitset_iterator(bitset_base<N> const* bitset_ptr, int bit) :
      bitset_index_iterator<DIRECTION>(bit), M_bitset_ptr(bitset_ptr)
  {
  }

template<unsigned int N, int DIRECTION>
  inline
  bitset_iterator<N, DIRECTION>::bitset_iterator(bitset_iterator const& iter) :
      bitset_index_iterator<DIRECTION>(iter), M_bitset_ptr(iter.M_bitset_ptr)
  {
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>&
  bitset_iterator<N, DIRECTION>::operator=(bitset_iterator<N, DIRECTION> const& iter)
  {
#ifdef __i386__
    this->M_index = iter.M_index;
#else
    this->M_digit = iter.M_digit;
    this->M_mask = iter.M_mask;
#endif
    M_bitset_ptr = iter.M_bitset_ptr;
    return *this;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>&
  bitset_iterator<N, DIRECTION>::operator=(bitset_index_iterator<DIRECTION> const& index)
  {
#ifdef __i386__
    this->M_index = index.get_index();
#else
    this->M_digit = index.get_digit();
    this->M_mask = index.get_mask();
#endif
    return *this;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>&
  bitset_iterator<N, DIRECTION>::operator++()
  {
    this->increment();
    return *this;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>
  bitset_iterator<N, DIRECTION>::operator++(int)
  {
    bitset_iterator prev(*this);
    this->increment();
    return prev;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>&
  bitset_iterator<N, DIRECTION>::operator--()
  {
    this->decrement();
    return *this;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>
  bitset_iterator<N, DIRECTION>::operator--(int)
  {
    bitset_iterator prev(*this);
    this->decrement();
    return prev;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_digit_t
  bitset_iterator<N, DIRECTION>::operator*() const
 {
#ifdef __i386__
    register unsigned int digit = this->M_index;
    register bitset_digit_t mask = 1;
    register unsigned short shift = this->M_index & (ECC_BITS - 1);
    digit >>= bitset_digit_bits_log2;
    mask <<= shift;
    return (M_bitset_ptr->rawdigit(digit) & mask);
#else
    return (M_bitset_ptr->rawdigit(this->M_digit) & this->M_mask);
#endif
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>&
  bitset_iterator<N, DIRECTION>::operator+=(int d)
  {
    this->increment(d);
    return *this;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>&
  bitset_iterator<N, DIRECTION>::operator-=(int d)
  {
    this->decrement(d);
    return *this;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>
  operator+(bitset_iterator<N, DIRECTION> const& i, int d)
  {
    bitset_iterator<N, DIRECTION> result(i);
    return result += d;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>
  operator+(int d, bitset_iterator<N, DIRECTION> const& i)
  {
    bitset_iterator<N, DIRECTION> result(i);
    return result += d;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>
  operator-(bitset_iterator<N, DIRECTION> const& i, int d)
  {
    bitset_iterator<N, DIRECTION> result(i);
    return result -= d;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_iterator<N, DIRECTION>
  operator-(int d, bitset_iterator<N, DIRECTION> const& i)
  {
    bitset_iterator<N, DIRECTION> result(i);
    return result -= d;
  }

template<unsigned int N, int DIRECTION>
  inline bitset_digit_t
  bitset_iterator<N, DIRECTION>::operator[](int d) const
 {
    return *(*this + d);
  }

//--------------------------------------------------------------------------------------------------------------------------
template<unsigned int N>
  classbitset : public bitset_invertible<N, false> {
    public:
      // Constructors.
      bitset(void);
      bitset(std::string const&);
      explicit bitset(bitset_digit_t low_bits);
      // This definition must be here, inside the template class declaration because
      // otherwise the compiler (2.95 - 3.1) barfs.
      bitset(bitset_digit_t const (&v)[bitset_base<N>::digits])
      {
#if ECC_DEBUG
        assert( (v[bitset_base<N>::digits - 1] & ~bitset_base<N>::valid_bits) == 0 );
#endif
        std::memcpy(this->vector, v, sizeof(this->vector));
      }

      // Copy constructors.
      template<unsigned int m, bool inverted>
        bitset(bitset_invertible<m, inverted> const&);
      template<unsigned int m, bool i1, bool i2, typename OP>
        bitset(Operator::bitsetExpression<m, i1, i2, OP> const& expr);

      // Assignment operators.
      bitset& operator=(bitset const&);
      template<typename Expression>
        bitset& operator=(Expression const&);

      // Perform AND, OR, XOR operations
      template<typename Expression>
        bitset& operator&=(Expression const&);
      template<typename Expression>
        bitset& operator|=(Expression const&);
      template<typename Expression>
        bitset& operator^=(Expression const&);

    public:
      // Shift bitset left or right and perform operation with result.
      template<unsigned int shift, class DIRECTION, class OPERATION>
        void shift_op(bitset& result) const;

      bitset& operator<<=(unsigned int shift) { this->bitset_base<N>::operator<<=(shift); return *this; }
      bitset& operator>>=(unsigned int shift) { this->bitset_base<N>::operator>>=(shift); return *this; }

      // Rotate left or right
      template<unsigned int shift, class DIRECTION>                     // Return a copy rotated `shift' bits in `DIRECTION'.
        void rotate(bitset& result) const;
  };

template<unsigned int N>
  inline
  bitset<N>::bitset(void)
  {
  }

template<unsigned int N>
  inline
  bitset<N>::bitset(bitset_digit_t low_bits)
  {
#if ECC_DEBUG
    assert( bitset_base<N>::digits > 1 || (low_bits & ~bitset_base<N>::valid_bits) == 0 );
#endif
    std::memset(this->vector, 0, sizeof(this->vector));
    this->vector[0] = low_bits;
  }

template<unsigned int N>
  void
  bitset_base<N>::setall(void)
  {
    this->vector[bitset_base<N>::digits - 1] = bitset_base<N>::valid_bits;
    if (bitset_base<N>::digits > 1)
    {
      int d = bitset_base<N>::digits - 2;
      do { this->vector[d] = ~static_cast<bitset_digit_t>(0); } while(--d >= 0);
    }
  }

template<unsigned int N>
  template<typename Expression>
    inline
    bitset<N>& bitset<N>::operator=(Expression const& expr)
    {
      this->assign(expr, Operator::bitsetAssign());
      return *this;
    }

// Special case, need to define this or else we'd get a default assignment operator.
template<unsigned int N>
  inline bitset<N>&
  bitset<N>::operator=(bitset const& expr)
  {
    this->assign(expr, Operator::bitsetAssign());
    return *this;
  }

template<unsigned int N>
  template<unsigned int m, bool inverted>
    inline bitset<N>::bitset(bitset_invertible<m, inverted> const& bits) : bitset_invertible<N, false>(bits)
    {
    }

template<unsigned int N>
  template<unsigned int m, bool i1, bool i2, typename OP>
    inline bitset<N>::bitset(Operator::bitsetExpression<m, i1, i2, OP> const& expr) : bitset_invertible<N, false>(expr)
    {
    }

template<unsigned int n1, bool inverted1, unsigned int n2, bool inverted2>
  bool operator==(bitset_invertible<n1, inverted1> const& bits1, bitset_invertible<n2, inverted2> const& bits2)
  {
    unsigned int d;
    if (bitset_invertible<n1, inverted1>::digits > bitset_invertible<n2, inverted2>::digits)
    {
      d = bitset_base<n1>::digits - 1;
      do
      {
        if (bits1.vector[d] != (inverted1 == inverted2 ? 0 : ~static_cast<bitset_digit_t>(0)))
          return false;
      }
      while (--d != bitset_base<n2>::digits - 1);
    }
    if (bitset_base<n2>::digits > bitset_base<n1>::digits)
    {
      d = bitset_base<n2>::digits - 1;
      do
      {
        if (bits2.vector[d] != (inverted1 == inverted2 ? 0 : ~static_cast<bitset_digit_t>(0)))
          return false;
      }
      while (--d != bitset_base<n1>::digits - 1);
    }
    if (bitset_base<n1>::digits > 1 && bitset_base<n2>::digits > 1)
    {
      if (bitset_base<n1>::digits == bitset_base<n2>::digits)
        d = bitset_base<n1>::digits - 1;
      do
      {
        if (inverted1 == inverted2)
        {
          if (bits1.vector[d] != bits2.vector[d])
            return false;
        }
        else
        {
          if (bits1.vector[d] != ~(bits2.vector[d]))
            return false;
        }
      }
      while(--d != 0);
    }
    if (inverted1 != inverted2)
      return (bits1.vector[0] == ~(bits2.vector[0]));
    return (bits1.vector[0] == bits2.vector[0]);
  }

template<unsigned int n1, bool inverted1, unsigned int n2, bool inverted2>
  inline bool
  operator!=(bitset_invertible<n1, inverted1> const& bits1, bitset_invertible<n2, inverted2> const& bits2)
  {
    return !(bits1 == bits2);
  }

template<unsigned int N>
  template<typename Expression>
    inline bitset<N>&
    bitset<N>::operator&=(Expression const& expr)
    {
      this->assign(expr, Operator::bitsetANDAssign());
      return *this;
    }

template<unsigned int N>
  template<typename Expression>
    inline bitset<N>&
    bitset<N>::operator|=(Expression const& expr)
    {
      this->assign(expr, Operator::bitsetORAssign());
      return *this;
    }

template<unsigned int N>
  template<typename Expression>
    inline bitset<N>&
    bitset<N>::operator^=(Expression const& expr)
    {
      this->assign(expr, Operator::bitsetXORAssign());
      return *this;
    }

template<unsigned int m, bool inverted1, bool inverted2>
  Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetAND>
  operator&(bitset_invertible<m, inverted1> const& arg1, bitset_invertible<m, inverted2> const& arg2)
    {
      return Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetAND>(arg1, arg2);
    }

template<unsigned int m, bool inverted1, bool inverted2>
  Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetOR>
  operator|(bitset_invertible<m, inverted1> const& arg1, bitset_invertible<m, inverted2> const& arg2)
    {
      return Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetOR>(arg1, arg2);
    }

template<unsigned int m, bool inverted1, bool inverted2>
  Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetXOR>
  operator^(bitset_invertible<m, inverted1> const& arg1, bitset_invertible<m, inverted2> const& arg2)
    {
      return Operator::bitsetExpression<m, inverted1, inverted2, Operator::bitsetXOR>(arg1, arg2);
    }

structassign {
  static int const id = 1;
  static bool const __clear = true;
  static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
  static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
};

structexor {
  static int const id = 2;
  static bool const __clear = false;
  static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 ^= digit2; }
  static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 ^= digit2; }
};

#ifndef HIDE_FROM_DOXYGEN
structrotate_phase1 {
  static int const id = 3;
  static bool const __clear = false;
  static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
  static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
};

structrotate_phase2 {
public:
  static int const id = 4;
  static bool const __clear = false;
  static inline void op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 = digit2; }
  static inline void mixed_op(bitset_digit_t& digit1, bitset_digit_t digit2) { digit1 |= digit2; }
};
#endif

template<unsigned int N>
  template<unsigned int shift, class DIRECTION, class OPERATION>
    void
    bitset<N>::shift_op(bitset& result) const
   {
      LibEccDout(dc::bitsetshift, "Entering shift_op<" << shift << ", " << libcwd::type_info_of<DIRECTION>().demangled_name() <<
          ", " << type_info_of<OPERATION>().demangled_name() << '>');
      LibEccDout(dc::bitsetshift|flush_cf, "Input : " << cwprint_using(*this, &bitset<N>::base2_print_on));
      if (shift == 1)
      {
        // Specialization for shift == 1.
        // digit_shift = 0
        // bit_shift = 1
        // zeroed_digits = 0 (likely and if not - then assumed).
        // Here we scan in the opposite direction of when shift > 1.
        static unsigned int const initial = DIRECTION::__left ? 0 : bitset_base<N>::digits - 1;
        static unsigned int const count = bitset_base<N>::digits - ((DIRECTION::__left && bitset_base<N>::has_excess_bits) ? 1 : 0);
#ifdef __i386__
        if (count)
        {
          bitset_digit_t const volatile* ptr1;
          bitset_digit_t volatile* ptr2;
          int c;
          if (DIRECTION::__left)
          {
            if (OPERATION::id == libecc::exor::id)
            {
              if (bitset_base<N>::has_excess_bits)
                LIBECC_ASMSHIFTLEFT(
                    LIBECC_LEFT_PRESERVE_CF("xorl -4(%%edi), %%edx"),
                    LIBECC_LEFT_PRESERVE_CF("xorl (%%edi), %%edx"),
                    LIBECC_ASMSHIFTLEFT_FINISH("xorl (%%edi),%%edx\n\t"));
              else
                LIBECC_ASMSHIFTLEFT(
                    LIBECC_LEFT_PRESERVE_CF("xorl -4(%%edi), %%edx"),
                    LIBECC_LEFT_PRESERVE_CF("xorl (%%edi), %%edx"), "");
            }
            else if (OPERATION::id == libecc::rotate_phase2::id)
            {
              if (bitset_base<N>::has_excess_bits)
                LIBECC_ASMSHIFTLEFT(
                    LIBECC_LEFT_PRESERVE_CF("orl -4(%%edi), %%edx"), "", LIBECC_ASMSHIFTLEFT_FINISH(""));
              else
                LIBECC_ASMSHIFTLEFT(
                    LIBECC_LEFT_PRESERVE_CF("orl -4(%%edi), %%edx"), "", "");
            }
            else
            {
              if (bitset_base<N>::has_excess_bits)
                LIBECC_ASMSHIFTLEFT("", "", LIBECC_ASMSHIFTLEFT_FINISH(""));
              else
                LIBECC_ASMSHIFTLEFT("", "", "");
            }
          }
          else if (count > 1)
          {
            if (OPERATION::id == libecc::exor::id)
              LIBECC_ASMSHIFTRIGHT1(
                  LIBECC_RIGHT_PRESERVE_CF("xorl " LIBECC_OP1_DESTINATION "," LIBECC_WORKREG),
                  LIBECC_RIGHT_PRESERVE_CF("xorl " LIBECC_OP2_DESTINATION "," LIBECC_WORKREG),
                  LIBECC_PRESERVE_CF_CLOBBER);
            else if (OPERATION::id == libecc::rotate_phase2::id)
              LIBECC_ASMSHIFTRIGHT1(
                  LIBECC_RIGHT_PRESERVE_CF("orl " LIBECC_OP1_DESTINATION "," LIBECC_WORKREG),
                  "",
                  LIBECC_PRESERVE_CF_CLOBBER);
            else
              LIBECC_ASMSHIFTRIGHT1(
                  "",
                  "",
                  LIBECC_CLOBBER);
          }
          else
          {
            if (OPERATION::id == libecc::exor::id)
              LIBECC_ASMSHIFTRIGHT0("xorl 4(%%edi), %%edx\n\t");
            else if (OPERATION::id == libecc::rotate_phase2::id)
              LIBECC_ASMSHIFTRIGHT0("orl 4(%%edi), %%edx\n\t");
            else
              LIBECC_ASMSHIFTRIGHT0("");
          }
        }
        else if (DIRECTION::__left && bitset_base<N>::has_excess_bits)
          OPERATION::op(result.vector[0], ((this->vector[0] << 1) & bitset_base<N>::valid_bits));
#else
        static unsigned int complement_shift = bitset_digit_bits - 1;
        static bitset_digit_t const mask1 = DIRECTION::__left ? (static_cast<bitset_digit_t>(1) << complement_shift) : static_cast<bitset_digit_t>(1);
        static bitset_digit_t const mask2 = DIRECTION::__right ? (static_cast<bitset_digit_t>(1) << complement_shift) : static_cast<bitset_digit_t>(1);
        bitset_digit_t const* ptr1 = &this->vector[initial];
        bitset_digit_t* ptr2 = &result.vector[initial];
        bool carry;
        if (count)
        {
          bitset_digit_t digit = *ptr1;
          carry = (digit & mask1);
          if (DIRECTION::__left)
            digit <<= 1;
          else
            digit >>= 1;
          OPERATION::mixed_op(*ptr2, digit);
          for (int c = count - 1; c; --c)
          {
            ptr1 -= DIRECTION::direction;
            ptr2 -= DIRECTION::direction;
            digit = *ptr1;
            if (carry)
            {
              carry = (digit & mask1);
              if (DIRECTION::__left)
                digit <<= 1;
              else
                digit >>= 1;
              digit |= mask2;
            }
            else
            {
              carry = (digit & mask1);
              if (DIRECTION::__left)
                digit <<= 1;
              else
                digit >>= 1;
            }
            OPERATION::op(*ptr2, digit);
          }
        }
        if (DIRECTION::__left && bitset_base<N>::has_excess_bits)
        {
          bitset_digit_t digit;
          if (count)
            digit = ptr1[-DIRECTION::direction];
          else
            digit = *ptr1;
          digit <<= 1;
          if (count && carry)
            digit |= mask2;
          if (count)
            OPERATION::op(ptr2[-DIRECTION::direction], (digit & bitset_base<N>::valid_bits));
          else
            OPERATION::op(*ptr2, (digit & bitset_base<N>::valid_bits));
        }
#endif
      }
      else
      {
        static unsigned int const digit_shift = shift / bitset_digit_bits;
        static unsigned int const bit_shift = shift % bitset_digit_bits;

        static unsigned int const zeroed_digits =
          DIRECTION::__left ? ((shift < N) ? digit_shift : bitset_base<N>::digits)
                            : ((bitset_digit_bits - bitset_base<N>::number_of_valid_bits + shift) / bitset_digit_bits);

        if (zeroed_digits < bitset_base<N>::digits)
        {
          static unsigned int const complement_shift = (bit_shift == 0) ? 0 : bitset_digit_bits - bit_shift;
          static unsigned int const initial_to = DIRECTION::__right ? 0 : bitset_base<N>::digits - 1;
          static unsigned int const initial_from = initial_to + DIRECTION::direction * digit_shift;
          static unsigned int const final_from = DIRECTION::__left ? 0 : bitset_base<N>::digits - 1;

          register bitset_digit_t digit = this->vector[initial_from];
          if (initial_from != final_from)
          {
            register bitset_digit_t next_digit;
            unsigned int to = initial_to;
            unsigned int from = initial_from + DIRECTION::direction;
            if (from != final_from)
              do
              {
                next_digit = this->vector[from];
                if (bit_shift != 0)
                {
                  if (DIRECTION::direction == -1)
                    digit <<= bit_shift;
                  else
                    digit >>= bit_shift;
                  digit |= DIRECTION::reverse_shift_copy(next_digit, complement_shift);
                }
                OPERATION::op(result.vector[to], digit);
                digit = next_digit;
                to += DIRECTION::direction;
                from += DIRECTION::direction;
              }
              while (from != final_from);
            if (DIRECTION::__left || bit_shift < bitset_base<N>::number_of_valid_bits || bit_shift != 0)
              next_digit = this->vector[final_from];
            if (bit_shift != 0)
            {
              if (DIRECTION::direction == -1)
                digit <<= bit_shift;
              else
                digit >>= bit_shift;
              digit |= DIRECTION::reverse_shift_copy(next_digit, complement_shift);
            }
            if (DIRECTION::__left || bit_shift < bitset_base<N>::number_of_valid_bits)
            {
              OPERATION::op(result.vector[final_from - DIRECTION::direction * (digit_shift + 1)], digit);
              digit = DIRECTION::shift_copy(next_digit, bit_shift);
            }
          }
          else
          {
            if (DIRECTION::direction == -1)
              digit <<= bit_shift;
            else
              digit >>= bit_shift;
          }
          static bool const have_mixed_digit = shift != 0 && (DIRECTION::__left ? shift : (N - shift)) % bitset_digit_bits != 0;
          static unsigned int const last_digit = (DIRECTION::__left ? shift : (N - 1 - shift)) / bitset_digit_bits;
          if (have_mixed_digit)
            OPERATION::mixed_op(result.vector[last_digit], digit);
          else
            OPERATION::op(result.vector[last_digit], digit);
          if (DIRECTION::__left && bitset_base<N>::has_excess_bits)
            result.vector[bitset_base<N>::digits - 1] &= bitset_base<N>::valid_bits;
        }
        if (OPERATION::__clear && zeroed_digits > 0)
        {
          static unsigned int const final_to = DIRECTION::__left ? 0 : bitset_base<N>::digits - 1;
          static unsigned int const initial_to = final_to - DIRECTION::direction * (zeroed_digits - 1);
          unsigned int to = initial_to;
          if (to != final_to)
            do
            {
              result.vector[to] = 0;
              to += DIRECTION::direction;
            }
            while(to != final_to);
          result.vector[to] = 0;
        }
      }
      LibEccDout(dc::bitsetshift|flush_cf, "Output: " << cwprint_using(result, &bitset<N>::base2_print_on));
    }

template<unsigned int N>
  void
  bitset_base<N>::operator<<=(unsigned int shift)
  {
    unsigned int const digit_shift = shift >> bitset_digit_bits_log2;
    unsigned int const bit_shift = shift & (bitset_digit_bits - 1);
    int digit1 = bitset_base<N>::digits - digit_shift - 2;
    bitset_digit_t d0 = (digit1 >= -1) ? this->vector[digit1 + 1] : 0;
    for (int digit_to = bitset_base<N>::digits - 1; digit_to >= 0; --digit_to)
    {
      bitset_digit_t d1 = (digit1 >= 0) ? this->vector[digit1] : 0;
      if (bit_shift == 0)
        this->vector[digit_to] = d0;
      else
        this->vector[digit_to] = (d0 << bit_shift) | (d1 >> (bitset_digit_bits - bit_shift));
      d0 = d1;
      --digit1;
    }
    if (bitset_base<N>::has_excess_bits)
      this->vector[bitset_base<N>::digits - 1] &= bitset_base<N>::valid_bits;           // Reset possibly set excess bits.
  }

template<unsigned int N>
  void
  bitset_base<N>::operator>>=(unsigned int shift)
  {
    unsigned int const digit_shift = shift >> bitset_digit_bits_log2;
    unsigned int const bit_shift = shift & (bitset_digit_bits - 1);
    unsigned int digit1 = digit_shift + 1;
    bitset_digit_t d0 = (digit1 <= bitset_base<N>::digits) ? this->vector[digit1 - 1] : 0;
    for (unsigned int digit_to = 0; digit_to < bitset_base<N>::digits; ++digit_to)
    {
      bitset_digit_t d1 = (digit1 < bitset_base<N>::digits) ? this->vector[digit1] : 0;
      if (bit_shift == 0)
        this->vector[digit_to] = d0;
      else
        this->vector[digit_to] = (d0 >> bit_shift) | (d1 << (bitset_digit_bits - bit_shift));
      d0 = d1;
      ++digit1;
    }
  }

template<unsigned int N>
  bitset<N>::bitset(std::string const& input)
  {
    this->reset();                                      // Reset internal digits to zero.
    unsigned int d = 0;                                 // Current index of internal digit.
    unsigned int u = 0;                                 // Current bit-shift of input digit relative to internal digit.

    for (std::string::const_reverse_iterator iter = input.rbegin(); iter != input.rend(); ++iter)       // Read right to left.
    {
      bitset_digit_t c = toupper(*iter);                // Get next hexadecimal input character.
      if (c == ' ')                                     // Skip spaces.
        continue;
      if (c < '0')                                      // Terminate reading when not a hexadecimal character.
        break;
      if (c <= '9')
        c -= '0';                                       // Set c to the value that the input character represents.
      else
      {
        if (c > 'F')
          break;
        if (c >= 'A')
          c -= ('A' - 10);
        else
          break;
      }
      this->vector[d] |= c << u;                        // Set internal bits.
      if ((u += 4) == bitset_digit_bits)                // Update bit/digit 'pointers'.
      {
        u = 0;
        if (++d == bitset_base<N>::digits)              // Terminate reading when bitset is full.
          break;
      }
    }
    if (bitset_base<N>::has_excess_bits)
      this->vector[bitset_base<N>::digits - 1] &= bitset_base<N>::valid_bits;   // Reset possibly set excess bits.
  }

template<unsigned int N>
  std::istream&
  operator>>(std::istream& is, bitset<N>& bitsetx)
  {
    std::string tmp;
    is >> tmp;
    bitsetx.bitset(tmp);
    return is;
  }

template<unsigned int N>
  std::ostream&
  operator<<(std::ostream& os, bitset<N> const& bits)
  {
    // Hexadecimal representation
    os.fill('0');
    os << std::hex;
    for (int d = bitset<N>::digits - 1; d >= 0; --d)
    {
      os.width((d == bitset<N>::digits - 1 && bitset<N>::has_excess_bits) ?
          (((N % bitset_digit_bits) - 1) / 4 + 1) :
          (bitset_digit_bits / 4));
      os << bits.digit(d);
      if (d > 0)
        os << ' ';
    }
    os << std::dec;
    return os;
  }

template<unsigned int N>
  void
  bitset_base<N>::reset(void)
  {
    std::memset(this->vector, 0, sizeof(this->vector));
  }

template<unsigned int N>
  inline bool
  bitset_base<N>::test(size_t pos) const
 {
#ifdef __i386__
    int result;
    __asm__ __volatile__ (
        "btl %2, %1\n\t"
        "sbbl %0, %0"
        : "=r" (result)
        : "m" ((*(bitset_digit_t volatile*)this->vector)), "Ir" (pos)
        : "cc");
    return result;
#else
    unsigned int d = pos / bitset_digit_bits;
    bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
    return (this->vector[d] & mask);
#endif
  }

template<unsigned int N>
  template<unsigned int pos>
    inline bool
    bitset_base<N>::test(void) const
   {
      static unsigned int const d = pos / bitset_digit_bits;
      static bitset_digit_t const mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
      return (this->vector[d] & mask);
    }

template<unsigned int N>
  inline bool
  bitset_base<N>::test(bitset_index const& index) const
 {
#ifdef __i386__
    return this->test(index.get_index());
#else
    return (this->vector[index.get_digit()] & index.get_mask());
#endif
  }

template<unsigned int N>
  inline void
  bitset_base<N>::set(size_t pos)
  {
#ifdef __i386__
    __asm__ __volatile__ (
        "btsl %1, %0"
        : "=m" ((*(bitset_digit_t volatile*)this->vector))
        : "Ir" (pos)
        : "cc");

#else
    unsigned int d = pos / bitset_digit_bits;
    bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
    this->vector[d] |= mask;
#endif
  }

template<unsigned int N>
  inline void
  bitset_base<N>::set(bitset_index const& index)
  {
#ifdef __i386__
    this->set(index.get_index());
#else
    this->vector[index.get_digit()] |= index.get_mask();
#endif
  }

template<unsigned int N>
  template<unsigned int pos>
    inline void
    bitset_base<N>::set(void)
    {
      static unsigned int const d = pos / bitset_digit_bits;
      static bitset_digit_t const mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
      this->vector[d] |= mask;
    }

template<unsigned int N>
  inline void
  bitset_base<N>::clear(size_t pos)
  {
#ifdef __i386__
    __asm__ __volatile__ (
        "btrl %1, %0"
        : "=m" ((*(bitset_digit_t volatile*)this->vector))
        : "Ir" (pos)
        : "cc"
    );
#else
    unsigned int d = pos / bitset_digit_bits;
    bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
    this->vector[d] &= ~mask;
#endif
  }

template<unsigned int N>
  inline void
  bitset_base<N>::clear(bitset_index const& index)
  {
#ifdef __i386__
    this->clear(index.get_index());
#else
    this->vector[index.get_digit()] &= ~(index.get_mask());
#endif
  }

template<unsigned int N>
  template<unsigned int pos>
    inline void
    bitset_base<N>::clear(void)
    {
      static unsigned int const d = pos / bitset_digit_bits;
      static bitset_digit_t const mask = ~(static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits));
      this->vector[d] &= mask;
    }

template<unsigned int N>
  inline void
  bitset_base<N>::flip(size_t pos)
  {
#ifdef __i386__
    __asm__ __volatile__ (
        "btcl %1, %0"
        : "=m" ((*(bitset_digit_t volatile*)this->vector))
        : "Ir" (pos)
        : "cc"
    );
#else
    unsigned int d = pos / bitset_digit_bits;
    bitset_digit_t mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
    this->vector[d] ^= mask;
#endif
  }

template<unsigned int N>
  inline void
  bitset_base<N>::flip(bitset_index const& index)
  {
#ifdef __i386__
    this->flip(index.get_index());
#else
    this->vector[index.get_digit()] ^= index.get_mask();
#endif
  }

template<unsigned int N>
  template<unsigned int pos>
    inline void
    bitset_base<N>::flip(void)
    {
      static unsigned int const d = pos / bitset_digit_bits;
      static bitset_digit_t const mask = static_cast<bitset_digit_t>(1) << (pos % bitset_digit_bits);
      this->vector[d] ^= mask;
    }

template<unsigned int N>
  bool
  bitset_base<N>::any(void) const
 {
    unsigned int to = bitset_base<N>::digits - 1;
    if (bitset_base<N>::digits > 1)
      do
      {
        if (this->vector[to] != 0)
          return true;
        --to;
      }
      while(to != 0);
    return (this->vector[0] != 0);
  }

static bool const oddnumberofbits[] = {
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  true, false, false, true, false, true, true, false, false, true, true, false, true, false, false, true,
  false, true, true, false, true, false, false, true, true, false, false, true, false, true, true, false };

template<unsigned int N>
  bool
  bitset_base<N>::odd(void) const
 {
    unsigned int from = bitset_base<N>::digits - 1;
    bitset_digit_t sum = this->vector[0];
    if (bitset_base<N>::digits > 1)
      do
      {
        sum ^= this->vector[from];
        --from;
      }
      while(from != 0);
    bitset_digit_t ssum = sum;
    if (sizeof(bitset_digit_t) >= 2)
    {
      ssum >>= (bitset_digit_bits / 2);
      sum ^= ssum;
    }
    if (sizeof(bitset_digit_t) >= 4)
    {
      ssum = sum;
      ssum >>= (bitset_digit_bits / 4);
      sum ^= ssum;
    }
    if (sizeof(bitset_digit_t) >= 8)
    {
      ssum = sum;
      ssum >>= (bitset_digit_bits / 8);
      sum ^= ssum;
    }
    if (sizeof(bitset_digit_t) == 16)
    {
      ssum = sum;
      ssum >>= (bitset_digit_bits / 16);
      sum ^= ssum;
    }
    return oddnumberofbits[sum & 0xff];
  }

structleft {
public:
  typedef structright inverse;
  static int const direction = -1;
  static bool const __left = true;
  static bool const __right = false;
  static inline bitset_digit_t shift_copy(bitset_digit_t digit, unsigned int shift) { return digit << shift; }
  static inline bitset_digit_t reverse_shift_copy(bitset_digit_t digit, unsigned int shift) { return digit >> shift; }
};

structright {
public:
  typedef structleft inverse;
  static int const direction = 1;
  static bool const __left = false;
  static bool const __right = true;
  static inline bitset_digit_t shift_copy(bitset_digit_t digit, unsigned int shift) { return digit >> shift; }
  static inline bitset_digit_t reverse_shift_copy(bitset_digit_t digit, unsigned int shift) { return digit << shift; }
};

template<unsigned int N>
  template<unsigned int shift, class DIRECTION>
    void
    bitset<N>::rotate(bitset<N>& result) const
   {
      LibEccDout(dc::bitsetshift|flush_cf, "Entering bitset<" << N << ">::rotate<" << shift << ", " << type_info_of<DIRECTION>().demangled_name() << ">");
      LibEccDout(dc::bitsetshift|flush_cf, "Rotate input : " << cwprint_using(*this, &bitset<N>::base2_print_on));
      shift_op<shift % N, DIRECTION, rotate_phase1>(result);
      LibEccDout(dc::bitsetshift|flush_cf, "After phase1 : " << cwprint_using(result, &bitset<N>::base2_print_on));
      shift_op<N - (shift % N), typename DIRECTION::inverse, rotate_phase2>(result);
      LibEccDout(dc::bitsetshift|flush_cf, "After phase2 : " << cwprint_using(result, &bitset<N>::base2_print_on));
      LibEccDout(dc::bitsetshift|flush_cf, "Leaving bitset<" << N << ">::rotate<" << shift << ", " << type_info_of<DIRECTION>().demangled_name() << ">");
    }

} // namespace libecc

#endif // LIBECC_BITS_H