Bitmask.hpp

/*
   Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.

   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; version 2 of the License.

   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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
*/

#ifndef NDB_BITMASK_H
#define NDB_BITMASK_H

#include <ndb_global.h>

#ifdef HAVE__BITSCANFORWARD
#include <intrin.h>
#endif

class BitmaskImpl {
public:
  STATIC_CONST( NotFound = (unsigned)-1 );

  static bool get(unsigned size, const Uint32 data[], unsigned n);

  static void set(unsigned size, Uint32 data[], unsigned n, bool value);

  static void set(unsigned size, Uint32 data[], unsigned n);

  static void set(unsigned size, Uint32 data[]);

  static void setRange(unsigned size, Uint32 data[], unsigned start,
                       unsigned len);

  static void assign(unsigned size, Uint32 dst[], const Uint32 src[]);

  static void clear(unsigned size, Uint32 data[], unsigned n);

  static void clear(unsigned size, Uint32 data[]);

  static void clear_range(unsigned size, Uint32 data[], unsigned start, unsigned last);

  static Uint32 getWord(unsigned size, Uint32 data[], unsigned word_pos);
  static void setWord(unsigned size, Uint32 data[],
                      unsigned word_pos, Uint32 new_word);
  static bool isclear(unsigned size, const Uint32 data[]);

  static unsigned count(unsigned size, const Uint32 data[]);

  static unsigned ffs(Uint32 x);

  static unsigned find_first(unsigned size, const Uint32 data[]);

  static unsigned find_next(unsigned size, const Uint32 data[], unsigned n);

  static unsigned find(unsigned size, const Uint32 data[], unsigned n);

  static bool equal(unsigned size, const Uint32 data[], const Uint32 data2[]);

  static void bitOR(unsigned size, Uint32 data[], const Uint32 data2[]);

  static void bitAND(unsigned size, Uint32 data[], const Uint32 data2[]);

  static void bitANDC(unsigned size, Uint32 data[], const Uint32 data2[]);

  static void bitXOR(unsigned size, Uint32 data[], const Uint32 data2[]);

  static void bitXORC(unsigned size, Uint32 data[], const Uint32 data2[]);

  static void bitNOT(unsigned size, Uint32 data[]);

  static bool contains(unsigned size, Uint32 data[], const Uint32 data2[]);

  static bool overlaps(unsigned size, Uint32 data[], const Uint32 data2[]);

  static Uint32 getField(unsigned size, const Uint32 data[],
      unsigned pos, unsigned len);

  static void setField(unsigned size, Uint32 data[],
      unsigned pos, unsigned len, Uint32 val);


  static void getField(unsigned size, const Uint32 data[],
                       unsigned pos, unsigned len, Uint32 dst[]);
  
  static void setField(unsigned size, Uint32 data[],
                       unsigned pos, unsigned len, const Uint32 src[]);
  
  static void copyField(Uint32 dst[], unsigned destPos,
                        const Uint32 src[], unsigned srcPos, unsigned len);
  
  static char* getText(unsigned size, const Uint32 data[], char* buf);

  /* Fast bit counting (16 instructions on x86_64, gcc -O3). */
  static inline Uint32 count_bits(Uint32 x);

  static Uint32 toArray(Uint8* dst, Uint32 len,
                        unsigned size, const Uint32 data[]);
private:
  static void getFieldImpl(const Uint32 data[], unsigned, unsigned, Uint32 []);
  static void setFieldImpl(Uint32 data[], unsigned, unsigned, const Uint32 []);
};

inline bool
BitmaskImpl::get(unsigned size, const Uint32 data[], unsigned n)
{
  assert(n < (size << 5));
  return (data[n >> 5] & (1 << (n & 31))) != 0;
}

inline void
BitmaskImpl::set(unsigned size, Uint32 data[], unsigned n, bool value)
{
  value ? set(size, data, n) : clear(size, data, n);
}

inline void
BitmaskImpl::set(unsigned size, Uint32 data[], unsigned n)
{
  assert(n < (size << 5));
  data[n >> 5] |= (1 << (n & 31));
}

inline void
BitmaskImpl::set(unsigned size, Uint32 data[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] = ~0;
  }
}

inline void
BitmaskImpl::setRange(unsigned size, Uint32 data[],
                      unsigned start, unsigned len)
{
  Uint32 last = start + len - 1;
  Uint32 *ptr = data + (start >> 5);
  Uint32 *end =  data + (last >> 5);
  assert(start <= last);
  assert(last < (size << 5));
  
  Uint32 tmp_word = ~(Uint32)0 << (start & 31);

  if (ptr < end)
  {
    * ptr ++ |= tmp_word;
    
    for(; ptr < end; )
    {
      * ptr ++ = ~(Uint32)0;
    }
    
    tmp_word = ~(Uint32)0;
  }

  tmp_word &= ~(~(Uint32)0 << (last & 31));
  
  * ptr |= tmp_word;
}

inline void 
BitmaskImpl::assign(unsigned size, Uint32 dst[], const Uint32 src[])
{
  for (unsigned i = 0; i < size; i++) {
    dst[i] = src[i];
  }
}

inline void
BitmaskImpl::clear(unsigned size, Uint32 data[], unsigned n)
{
  assert(n < (size << 5));
  data[n >> 5] &= ~(1 << (n & 31));
}

inline void
BitmaskImpl::clear(unsigned size, Uint32 data[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] = 0;
  }
}

inline void
BitmaskImpl::clear_range(unsigned size, Uint32 data[], 
                         unsigned start, unsigned last)
{
  Uint32 *ptr = data + (start >> 5);
  Uint32 *end =  data + (last >> 5);
  assert(start <= last);
  assert(last < (size << 5));
  
  Uint32 tmp_word = ~(Uint32)0 << (start & 31);

  if (ptr < end)
  {
    * ptr ++ &= ~tmp_word;
    
    for(; ptr < end; )
    {
      * ptr ++ = 0;
    }
    
    tmp_word = ~(Uint32)0;
  }

  tmp_word &= ~(~(Uint32)0 << (last & 31));

  * ptr &= ~tmp_word;
}

inline
Uint32
BitmaskImpl::getWord(unsigned size, Uint32 data[], unsigned word_pos)
{
  return data[word_pos];
}

inline void
BitmaskImpl::setWord(unsigned size, Uint32 data[],
                     unsigned word_pos, Uint32 new_word)
{
  data[word_pos] = new_word;
  return;
}

inline bool
BitmaskImpl::isclear(unsigned size, const Uint32 data[])
{
  for (unsigned i = 0; i < size; i++) {
    if (data[i] != 0)
      return false;
  }
  return true;
}

inline unsigned
BitmaskImpl::count(unsigned size, const Uint32 data[])
{
  unsigned cnt = 0;
  for (unsigned i = 0; i < size; i++) {
    cnt += count_bits(data[i]);
  }
  return cnt;
}

inline
Uint32
BitmaskImpl::ffs(Uint32 x)
{
#if defined(__GNUC__) && (defined(__x86_64__) || defined (__i386__))
  asm("bsf %1,%0"
      : "=r" (x)
      : "rm" (x));
  return x;
#elif defined HAVE___BUILTIN_FFS

  return __builtin_ffs(x) - 1;
#elif defined HAVE__BITSCANFORWARD
  unsigned long r;
  unsigned char res = _BitScanForward(&r, (unsigned long)x);
  assert(res > 0);
  return (Uint32)r;
#elif defined HAVE_FFS
  return ::ffs(x) - 1;
#else
  int b = 0;
  if (!(x & 0xffff))
  {
    x >>= 16;
    b += 16;
  }
  if (!(x & 0xff))
  {
    x >>= 8;
    b += 8;
  }
  if (!(x & 0xf))
  {
    x >>= 4;
    b += 4;
  }
  if (!(x & 3))
  {
    x >>= 2;
    b += 2;
  }
  if (!(x & 1))
  {
    x >>= 1;
    b += 1;
  }
  return b;
#endif
}

inline unsigned
BitmaskImpl::find_first(unsigned size, const Uint32 data[])
{
  Uint32 n = 0;
  while (n < (size << 5))
  {
    Uint32 val = data[n >> 5];
    if (val)
    {
      return n + ffs(val);
    }
    n += 32;
  }
 return NotFound;
}

inline unsigned
BitmaskImpl::find_next(unsigned size, const Uint32 data[], unsigned n)
{
  Uint32 val = data[n >> 5];
  Uint32 b = n & 31;
  if (b)
  {
    val >>= b;
    if (val)
    {
      return n + ffs(val);
    }
    n += 32 - b;
  }

  while (n < (size << 5))
  {
    val = data[n >> 5];
    if (val)
    {
      return n + ffs(val);
    }
    n += 32;
  }
  return NotFound;
}

inline unsigned
BitmaskImpl::find(unsigned size, const Uint32 data[], unsigned n)
{
  return find_next(size, data, n);
}

inline bool
BitmaskImpl::equal(unsigned size, const Uint32 data[], const Uint32 data2[])
{
  for (unsigned i = 0; i < size; i++) {
    if (data[i] != data2[i])
      return false;
  }
  return true;
}

inline void
BitmaskImpl::bitOR(unsigned size, Uint32 data[], const Uint32 data2[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] |= data2[i];
  }
}

inline void
BitmaskImpl::bitAND(unsigned size, Uint32 data[], const Uint32 data2[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] &= data2[i];
  }
}

inline void
BitmaskImpl::bitANDC(unsigned size, Uint32 data[], const Uint32 data2[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] &= ~data2[i];
  }
}

inline void
BitmaskImpl::bitXOR(unsigned size, Uint32 data[], const Uint32 data2[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] ^= data2[i];
  }
}

inline void
BitmaskImpl::bitXORC(unsigned size, Uint32 data[], const Uint32 data2[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] ^= ~data2[i];
  }
}

inline void
BitmaskImpl::bitNOT(unsigned size, Uint32 data[])
{
  for (unsigned i = 0; i < size; i++) {
    data[i] = ~data[i];
  }
}

inline bool
BitmaskImpl::contains(unsigned size, Uint32 data[], const Uint32 data2[])
{
  for (unsigned int i = 0; i < size; i++)
    if ((data[i] & data2[i]) != data2[i])
      return false;
  return true;
}

inline bool
BitmaskImpl::overlaps(unsigned size, Uint32 data[], const Uint32 data2[])
{
  for (unsigned int i = 0; i < size; i++)
    if ((data[i] & data2[i]) != 0)
      return true;
  return false;
}

inline Uint32
BitmaskImpl::getField(unsigned size, const Uint32 data[],
    unsigned pos, unsigned len)
{
  Uint32 val = 0;
  for (unsigned i = 0; i < len; i++)
    val |= get(size, data, pos + i) << i;
  return val;
}

inline void
BitmaskImpl::setField(unsigned size, Uint32 data[],
    unsigned pos, unsigned len, Uint32 val)
{
  for (unsigned i = 0; i < len; i++)
    set(size, data, pos + i, val & (1 << i));
}

inline char *
BitmaskImpl::getText(unsigned size, const Uint32 data[], char* buf)
{
  char * org = buf;
  const char* const hex = "0123456789abcdef";
  for (int i = (size-1); i >= 0; i--) {
    Uint32 x = data[i];
    for (unsigned j = 0; j < 8; j++) {
      buf[7-j] = hex[x & 0xf];
      x >>= 4;
    }
    buf += 8;
  }
  *buf = 0;
  return org;
}

inline
Uint32
BitmaskImpl::count_bits(Uint32 x)
{
  x= x - ((x>>1) & 0x55555555);
  x= (x & 0x33333333) + ((x>>2) & 0x33333333);
  x= (x + (x>>4)) & 0x0f0f0f0f;
  x= (x*0x01010101) >> 24;
  return x;
}

inline
Uint32
BitmaskImpl::toArray(Uint8* dst, Uint32 len,
                     unsigned size, const Uint32 * data)
{
  assert(len >= size * 32);
  assert(32 * size <= 256); // Uint8
  Uint8 * save = dst;
  for (Uint32 i = 0; i<size; i++)
  {
    Uint32 val = * data++;
    Uint32 bit = 0;
    while (val)
    {
      if (val & (1 << bit))
      {
        * dst++ = 32 * i + bit;
        val &= ~(1U << bit);
      }
      bit ++;
    }
  }
  return (Uint32)(dst - save);
}

template <unsigned size>
struct BitmaskPOD {
public:
  struct Data {
    Uint32 data[size];
#if 0
    Data & operator=(const BitmaskPOD<size> & src) {
      src.copyto(size, data);
      return *this;
    }
#endif
  };
  
  Data rep;
public:
  STATIC_CONST( Size = size );
  STATIC_CONST( NotFound = BitmaskImpl::NotFound );
  STATIC_CONST( TextLength = size * 8 );

  Uint32 getSizeInWords() const { return Size;}

  unsigned max_size() const { return (size * 32) - 1; }

  void assign(const typename BitmaskPOD<size>::Data & src);

  static void assign(Uint32 dst[], const Uint32 src[]);
  static void assign(Uint32 dst[], const BitmaskPOD<size> & src);
  void assign(const BitmaskPOD<size> & src);

  void copyto(unsigned sz, Uint32 dst[]) const;
  
  void assign(unsigned sz, const Uint32 src[]);

  static bool get(const Uint32 data[], unsigned n);
  bool get(unsigned n) const;

  static void set(Uint32 data[], unsigned n, bool value);
  void set(unsigned n, bool value);

  static void set(Uint32 data[], unsigned n);
  void set(unsigned n);

  static void set(Uint32 data[]);
  void set();

  static void setRange(Uint32 data[], Uint32 pos, Uint32 len);
  void setRange(Uint32 pos, Uint32 len);

  static void clear(Uint32 data[], unsigned n);
  void clear(unsigned n);

  static void clear(Uint32 data[]);
  void clear();

  Uint32 getWord(unsigned word_pos);
  void setWord(unsigned word_pos, Uint32 new_word);
  
  static bool isclear(const Uint32 data[]);
  bool isclear() const;

  static unsigned count(const Uint32 data[]);
  unsigned count() const;

  static unsigned find_first(const Uint32 data[]);
  unsigned find_first() const;

  static unsigned find_next(const Uint32 data[], unsigned n);
  unsigned find_next(unsigned n) const;

  static unsigned find(const Uint32 data[], unsigned n);
  unsigned find(unsigned n) const;

  static bool equal(const Uint32 data[], const Uint32 data2[]);
  bool equal(const BitmaskPOD<size>& mask2) const;

  static void bitOR(Uint32 data[], const Uint32 data2[]);
  BitmaskPOD<size>& bitOR(const BitmaskPOD<size>& mask2);

  static void bitAND(Uint32 data[], const Uint32 data2[]);
  BitmaskPOD<size>& bitAND(const BitmaskPOD<size>& mask2);

  static void bitANDC(Uint32 data[], const Uint32 data2[]);
  BitmaskPOD<size>& bitANDC(const BitmaskPOD<size>& mask2);

  static void bitXOR(Uint32 data[], const Uint32 data2[]);
  BitmaskPOD<size>& bitXOR(const BitmaskPOD<size>& mask2);

  static void bitXORC(Uint32 data[], const Uint32 data2[]);
  BitmaskPOD<size>& bitXORC(const BitmaskPOD<size>& mask2);

  static void bitNOT(Uint32 data[]);
  BitmaskPOD<size>& bitNOT();

  static bool contains(Uint32 data[], const Uint32 data2[]);
  bool contains(BitmaskPOD<size> that);

  static bool overlaps(Uint32 data[], const Uint32 data2[]);
  bool overlaps(BitmaskPOD<size> that);

  static char* getText(const Uint32 data[], char* buf);
  char* getText(char* buf) const;

  static Uint32 toArray(Uint8 * dst, Uint32 len, const Uint32 data[]);
  Uint32 toArray(Uint8 * dst, Uint32 len) const;
};

template <unsigned size>
inline void
BitmaskPOD<size>::assign(Uint32 dst[], const Uint32 src[])
{
  BitmaskImpl::assign(size, dst, src);
}

template <unsigned size>
inline void
BitmaskPOD<size>::assign(Uint32 dst[], const BitmaskPOD<size> & src)
{
  BitmaskImpl::assign(size, dst, src.rep.data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::assign(const typename BitmaskPOD<size>::Data & src)
{
  BitmaskPOD<size>::assign(rep.data, src.data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::assign(const BitmaskPOD<size> & src)
{
  BitmaskPOD<size>::assign(rep.data, src.rep.data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::copyto(unsigned sz, Uint32 dst[]) const
{
  BitmaskImpl::assign(sz, dst, rep.data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::assign(unsigned sz, const Uint32 src[])
{
  BitmaskImpl::assign(sz, rep.data, src);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::get(const Uint32 data[], unsigned n)
{
  return BitmaskImpl::get(size, data, n);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::get(unsigned n) const
{
  return BitmaskPOD<size>::get(rep.data, n);
}

template <unsigned size>
inline void
BitmaskPOD<size>::set(Uint32 data[], unsigned n, bool value)
{
  BitmaskImpl::set(size, data, n, value);
}

template <unsigned size>
inline void
BitmaskPOD<size>::set(unsigned n, bool value)
{
  BitmaskPOD<size>::set(rep.data, n, value);
}

template <unsigned size>
inline void
BitmaskPOD<size>::set(Uint32 data[], unsigned n)
{
  BitmaskImpl::set(size, data, n);
}

template <unsigned size>
inline void
BitmaskPOD<size>::set(unsigned n)
{
  BitmaskPOD<size>::set(rep.data, n);
}

template <unsigned size>
inline void
BitmaskPOD<size>::set(Uint32 data[])
{
  BitmaskImpl::set(size, data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::set()
{
  BitmaskPOD<size>::set(rep.data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::setRange(Uint32 data[], Uint32 pos, Uint32 len)
{
  BitmaskImpl::setRange(size, data, pos, len);
}


template <unsigned size>
inline void
BitmaskPOD<size>::setRange(Uint32 pos, Uint32 len)
{
  BitmaskPOD<size>::setRange(rep.data, pos, len);
}

template <unsigned size>
inline void
BitmaskPOD<size>::clear(Uint32 data[], unsigned n)
{
  BitmaskImpl::clear(size, data, n);
}

template <unsigned size>
inline void
BitmaskPOD<size>::clear(unsigned n)
{
  BitmaskPOD<size>::clear(rep.data, n);
}

template <unsigned size>
inline void
BitmaskPOD<size>::clear(Uint32 data[])
{
  BitmaskImpl::clear(size, data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::clear()
{
  BitmaskPOD<size>::clear(rep.data);
}

template <unsigned size>
inline Uint32
BitmaskPOD<size>::getWord(unsigned word_pos)
{
  return BitmaskImpl::getWord(size, rep.data, word_pos);
}

template <unsigned size>
inline void
BitmaskPOD<size>::setWord(unsigned word_pos, Uint32 new_word)
{
  BitmaskImpl::setWord(size, rep.data, word_pos, new_word);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::isclear(const Uint32 data[])
{
  return BitmaskImpl::isclear(size, data);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::isclear() const
{
  return BitmaskPOD<size>::isclear(rep.data);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::count(const Uint32 data[])
{
  return BitmaskImpl::count(size, data);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::count() const
{
  return BitmaskPOD<size>::count(rep.data);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::find_first(const Uint32 data[])
{
  return BitmaskImpl::find_first(size, data);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::find_first() const
{
  return BitmaskPOD<size>::find_first(rep.data);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::find_next(const Uint32 data[], unsigned n)
{
  return BitmaskImpl::find_next(size, data, n);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::find_next(unsigned n) const
{
  return BitmaskPOD<size>::find_next(rep.data, n);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::find(const Uint32 data[], unsigned n)
{
  return find_next(data, n);
}

template <unsigned size>
inline unsigned
BitmaskPOD<size>::find(unsigned n) const
{
  return find_next(n);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::equal(const Uint32 data[], const Uint32 data2[])
{
  return BitmaskImpl::equal(size, data, data2);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::equal(const BitmaskPOD<size>& mask2) const
{
  return BitmaskPOD<size>::equal(rep.data, mask2.rep.data);
}

template <unsigned size>
inline void
BitmaskPOD<size>::bitOR(Uint32 data[], const Uint32 data2[])
{
  BitmaskImpl::bitOR(size,data, data2);
}

template <unsigned size>
inline BitmaskPOD<size>&
BitmaskPOD<size>::bitOR(const BitmaskPOD<size>& mask2)
{
  BitmaskPOD<size>::bitOR(rep.data, mask2.rep.data);
  return *this;
}

template <unsigned size>
inline void
BitmaskPOD<size>::bitAND(Uint32 data[], const Uint32 data2[])
{
  BitmaskImpl::bitAND(size,data, data2);
}

template <unsigned size>
inline BitmaskPOD<size>&
BitmaskPOD<size>::bitAND(const BitmaskPOD<size>& mask2)
{
  BitmaskPOD<size>::bitAND(rep.data, mask2.rep.data);
  return *this;
}

template <unsigned size>
inline void
BitmaskPOD<size>::bitANDC(Uint32 data[], const Uint32 data2[])
{
  BitmaskImpl::bitANDC(size,data, data2);
}

template <unsigned size>
inline BitmaskPOD<size>&
BitmaskPOD<size>::bitANDC(const BitmaskPOD<size>& mask2)
{
  BitmaskPOD<size>::bitANDC(rep.data, mask2.rep.data);
  return *this;
}

template <unsigned size>
inline void
BitmaskPOD<size>::bitXOR(Uint32 data[], const Uint32 data2[])
{
  BitmaskImpl::bitXOR(size,data, data2);
}

template <unsigned size>
inline BitmaskPOD<size>&
BitmaskPOD<size>::bitXOR(const BitmaskPOD<size>& mask2)
{
  BitmaskPOD<size>::bitXOR(rep.data, mask2.rep.data);
  return *this;
}

template <unsigned size>
inline void
BitmaskPOD<size>::bitXORC(Uint32 data[], const Uint32 data2[])
{
  BitmaskImpl::bitXORC(size,data, data2);
}

template <unsigned size>
inline BitmaskPOD<size>&
BitmaskPOD<size>::bitXORC(const BitmaskPOD<size>& mask2)
{
  BitmaskPOD<size>::bitXORC(rep.data, mask2.rep.data);
  return *this;
}

template <unsigned size>
inline void
BitmaskPOD<size>::bitNOT(Uint32 data[])
{
  BitmaskImpl::bitNOT(size,data);
}

template <unsigned size>
inline BitmaskPOD<size>&
BitmaskPOD<size>::bitNOT()
{
  BitmaskPOD<size>::bitNOT(rep.data);
  return *this;
}

template <unsigned size>
inline char *
BitmaskPOD<size>::getText(const Uint32 data[], char* buf)
{
  return BitmaskImpl::getText(size, data, buf);
}

template <unsigned size>
inline char *
BitmaskPOD<size>::getText(char* buf) const
{
  return BitmaskPOD<size>::getText(rep.data, buf);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::contains(Uint32 data[], const Uint32 data2[])
{
  return BitmaskImpl::contains(size, data, data2);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::contains(BitmaskPOD<size> that)
{
  return BitmaskPOD<size>::contains(this->rep.data, that.rep.data);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::overlaps(Uint32 data[], const Uint32 data2[])
{
  return BitmaskImpl::overlaps(size, data, data2);
}

template <unsigned size>
inline bool
BitmaskPOD<size>::overlaps(BitmaskPOD<size> that)
{
  return BitmaskPOD<size>::overlaps(this->rep.data, that.rep.data);
}

template <unsigned size>
inline
Uint32
BitmaskPOD<size>::toArray(Uint8* dst, Uint32 len, const Uint32 data[])
{
  return BitmaskImpl::toArray(dst, len, size, data);
}

template <unsigned size>
inline
Uint32
BitmaskPOD<size>::toArray(Uint8* dst, Uint32 len) const
{
  return BitmaskImpl::toArray(dst, len, size, this->rep.data);
}

template <unsigned size>
class Bitmask : public BitmaskPOD<size> {
public:
  Bitmask() { this->clear();}

  template<unsigned sz2> Bitmask& operator=(const Bitmask<sz2>& src){
    if (size >= sz2)
    {
      for (unsigned i = 0; i < sz2; i++) 
      {
        this->rep.data[i] = src.rep.data[i];
      }
    }
    else
    {
      assert(src.find(32*size+1) == BitmaskImpl::NotFound);
      for (unsigned i = 0; i < size; i++) 
      {
        this->rep.data[i] = src.rep.data[i];
      }
    }
    return * this;
  }

  template<unsigned sz2> Bitmask& operator=(const BitmaskPOD<sz2>& src){
    if (size >= sz2)
    {
      for (unsigned i = 0; i < sz2; i++) 
      {
        this->rep.data[i] = src.rep.data[i];
      }
    }
    else
    {
      assert(src.find(32*size+1) == BitmaskImpl::NotFound);
      for (unsigned i = 0; i < size; i++) 
      {
        this->rep.data[i] = src.rep.data[i];
      }
    }
    return * this;
  }
};

inline void
BitmaskImpl::getField(unsigned size, const Uint32 src[],
                      unsigned pos, unsigned len, Uint32 dst[])
{
  assert(pos + len <= (size << 5));
  assert (len != 0);
  if (len == 0)
    return;

  src += (pos >> 5);
  Uint32 offset = pos & 31;
  * dst = (* src >> offset) & (len >= 32 ? ~0 : (1 << len) - 1);
  
  if(offset + len <= 32)
  {
    return;
  }
  Uint32 used = (32 - offset);
  assert(len > used);
  getFieldImpl(src+1, used & 31, len-used, dst+(used >> 5));
}

inline void
BitmaskImpl::setField(unsigned size, Uint32 dst[],
                      unsigned pos, unsigned len, const Uint32 src[])
{
  assert(pos + len <= (size << 5));
  assert(len != 0);
  if (len == 0)
    return;

  dst += (pos >> 5);
  Uint32 offset = pos & 31;
  Uint32 mask = (len >= 32 ? ~0 : (1 << len) - 1) << offset;
  
  * dst = (* dst & ~mask) | ((*src << offset) & mask);
  
  if(offset + len <= 32)
  {
    return;
  }
  Uint32 used = (32 - offset);
  assert(len > used);
  setFieldImpl(dst+1, used & 31, len-used, src+(used >> 5));
}

/* Three way min utiltiy for copyField below */
inline unsigned minLength(unsigned a, unsigned b, unsigned c)
{
  return (a < b ? 
          (a < c ? a : c) : 
          (b < c ? b : c ));
}

inline void
BitmaskImpl::copyField(Uint32 _dst[], unsigned dstPos,
                       const Uint32 _src[], unsigned srcPos, unsigned len)
{
  /* Algorithm
   * While (len > 0)
   *  - Find the longest bit length we can copy from one 32-bit word
   *    to another (which is the miniumum of remaining length, 
   *    space in current src word and space in current dest word)
   *  - Extract that many bits from src, and shift them to the correct
   *    position to insert into dest
   *  - Mask out the to-be-written words from dest (and any irrelevant 
   *    words in src) and or them together
   *  - Move onto next chunk
   */
  while (len > 0)
  {
    const Uint32* src= _src + (srcPos >> 5);
    Uint32* dst= _dst + (dstPos >> 5);
    unsigned srcOffset= srcPos & 31;
    unsigned dstOffset= dstPos & 31;
    unsigned srcBitsInWord= 32 - srcOffset; 
    unsigned dstBitsInWord= 32 - dstOffset;
    
    /* How many bits can we copy at once? */
    unsigned bits= minLength(dstBitsInWord, srcBitsInWord, len);
    
    /* Create mask for affected bits in dest */
    Uint32 destMask= (~(Uint32)0 >> (32-bits) << dstOffset);
    
    /* Grab source data and shift to dest offset */
    Uint32 data= ((*src) >> srcOffset) << dstOffset;
    
    /* Mask out affected bits in dest and irrelevant bits in source
     * and combine
     */
    *dst= (*dst  & ~destMask) | (data & destMask);
    
    srcPos+= bits;
    dstPos+= bits;
    len-= bits;
  }
  
  return;
}

#endif