qsieve

qsieve Mercurial Source Tree


Root/src/myBitString_generic.H

#ifndef MYBITSTRING_HEADER_
#define MYBITSTRING_HEADER_
 
/*! @file
 * @brief
 * generic implementation of an array class of bits (in dense representation)
 */
 
 
#include <new>
using std::nothrow;
 
#include "utils.H"
 
 
class myBitString
{
private:
  template <class Tuint> class CmyBitMask
   {
    public:
     inline const Tuint operator[] (const unsigned int i) const
      {
        return static_cast<Tuint>(1)<<i;
      }
    };
  static const CmyBitMask<unsigned int> bitmask;
protected:
  int size;
  unsigned int *data;
  inline void resize(int newsize)
    {
      if (newsize < size) return;
      //cerr << "Resize " << size << " to " << newsize << endl;
      unsigned int *olddata = data;
      data = new(nothrow) unsigned int[newsize];
      if (!data)
    {
      cerr << "myBitString.resize(" << newsize << ") out of memory" << endl;
      exit(1);
    }
      for (int i=0; i<size; i++) data[i] = olddata[i];
      for (int i=size; i< newsize; i++) data[i]=0;
      size=newsize;
      if (olddata) delete [] olddata;
    }
public:
  inline void optisize(void)
    {
      int i=size-1;
      while (i>=0 && data[i]==0) i--;
      if (i==size-1) return; // nothing to do...
 
      if (size<128)
       {
         // to avoid heap pollution for small sizes, simply decrease
         // the size without reallocating any heap memory
#ifdef VERBOSE
         cout << "MyBitString::Optisize, no reallocate " << size << " to " << i+1 << endl;
#endif
         size=i+1; return;
       }
 
#ifdef VERBOSE
      cout << "MyBitString::Optisize, reallocate" << size << " to " << i+1 << endl;
#endif
      if (i<0) { delete [] data; data=NULL; size=0; return; } // now empty
 
      size=i+1; // new size
      unsigned int *olddata = data;
      data = new(nothrow) unsigned int[size];
      if (!data)
    {
      cerr << "myBitString.optisize(" << size << ") out of memory" << endl;
      exit(1);
    }
      for (; i>=0; --i) data[i] = olddata[i];
      if (olddata) delete [] olddata;
    }
 
  inline myBitString(void) : size(0), data(NULL) { }
  inline ~myBitString(void)
    {
      if (data) delete [] data;
      data=NULL;
      size=0;
    }
  inline myBitString(const myBitString &rhs) : size(rhs.size), data(NULL)
   {
     data = new(nothrow) unsigned int[size];
     if (!data)
       {
         cerr << "myBitString.operator=(" << size << ") out of memory" << endl;
         exit(1);
       }
     for (int i=size-1; i>=0; --i) data[i] = rhs.data[i];
   }
  inline myBitString& operator= (const myBitString &rhs)
   {
     if (data) delete [] data;
     size=rhs.size;
     data = new(nothrow) unsigned int[size];
     if (!data)
       {
         cerr << "myBitString.operator=(" << size << ") out of memory" << endl;
         exit(1);
       }
     for (int i=size-1; i>=0; --i) data[i] = rhs.data[i];
     return *this;
   }
  inline int count(const bool b = true) const
    {
      int i;
      int z=0;
      if (!b) return -1;
      for (i=0; i<size; i++)
    {
      register unsigned int h = data[i];
      while (h)
        {
          if (h&1) z++;
          h>>=1;
        }
    }
      return z;
    }
  inline int first(const bool b = true) const
    {
      if (b)
    {
      int j=0;
      for (int i=0; i<size; i++)
        {
          register unsigned int h = data[i];
          while (h)
        {
          if (h&1)
            {
              //cerr << "first(1)=" << 8*sizeof(unsigned int)*i+j << endl;
              return 8*sizeof(unsigned int)*i+j;
            }
          h>>=1;
          j++;
        }
        }
      //cerr << "first(1)=-1" << endl;
      return -1;
    }
      else
    {
      cerr << "myBitString.first(0) not implemented" << endl;
      exit(1);
    }
    }
  inline int next(int pos, const bool b = true) const
    {
      int i,j;
      if (pos<0) return first(b);
      pos++;
      if (b)
    {
      i=pos/(8*sizeof(unsigned int));
      j=pos%(8*sizeof(unsigned int));
      if (i>=size) return -1;
      register unsigned int h = data[i];
      h>>=j;
      if (h)
        {
          while (!(h&1))
        {
          h>>=1;
          pos++;
        }
          return pos;
        }
      else
        {
          j = 0;
          for (i++;i<size; i++)
        {
          h = data[i];
          while (h)
            {
              if (h&1) return 8*sizeof(unsigned int)*i+j;
              h>>=1;
              j++;
            }
        }
        }
      return -1;
    }
      else
    {
      cerr << "myBitString.next(0) not implemented" << endl;
      exit(1);
    }
    }
  inline int last(const bool b = true) const
    {
      int i;
 
      if (b)
    {
      int j = 8*sizeof(unsigned int)-1;
      for (i=size-1; i>=0; i--)
        {
          //cerr << "i=" << i << endl;
          register unsigned int h = data[i];
          while (h)
        {
          if (h& bitmask[8*sizeof(unsigned int)-1])
            {
              //cerr << "last(1)=" << 8*sizeof(unsigned int)*i+j << endl;
              return 8*sizeof(unsigned int)*i+j;
            }
          h<<=1;
          j--;
        }
        }
      //cerr << "last(1)=-1"<<endl;
      return -1;
    }
      else
    {
      cerr << "myBitString.last(0) not implemented" << endl;
      exit(1);
    }
    }
  inline int prev(int pos, const bool b = true) const
    {
      int i,j;
 
      if (pos>size*8*static_cast<int>(sizeof(unsigned int))) return last(b);
      if (pos<=0) return -1;
      pos--;
      if (b)
    {
      i=pos/(8*sizeof(unsigned int));
      j=pos%(8*sizeof(unsigned int));
      register unsigned int h = data[i];
      h<<=8*sizeof(unsigned int)-j-1;
      if (h)
        {
          while (!(h&bitmask[8*sizeof(unsigned int)-1]))
        {
          h<<=1;
          pos--;
        }
          return pos;
        }
      else
        {
          j = 8*sizeof(unsigned int)-1;
          for (i--;i>=0; i--)
        {
          h = data[i];
          while (h)
            {
              if (h&bitmask[8*sizeof(unsigned int)-1])
            return 8*sizeof(unsigned int)*i+j;
              h<<=1;
              j--;
            }
        }
        }
      return -1;
    }
      else
    {
      cerr << "myBitString.prev(0) not implemented" << endl;
      exit(1);
    }
    }
  inline void invert(const int pos)
    {
      //cerr << "invert("<<pos<<")"<<endl;
      int i=pos/(8*sizeof(unsigned int));
      int j=pos%(8*sizeof(unsigned int));
 
      if (i>=size) resize(i+1);
 
      data[i] ^= bitmask[j];
    }
  inline bool test_and_invert(const int pos)
    {
      //cerr << "test_and_invert("<<pos<<")"<<endl;
      int i=pos/(8*sizeof(unsigned int));
      int j=pos%(8*sizeof(unsigned int));
      if (i>=size) resize(i+1);
      const bool ret = (data[i] & bitmask[j]);
      data[i] ^= bitmask[j];
      return ret;
    }
  inline bool test(const int pos) const
    {
      int i=pos/(8*sizeof(unsigned int));
      int j=pos%(8*sizeof(unsigned int));
 
      if (i>=size) return false;
      //cerr << "test("<<pos<<")=" << (data[i] & bitmask[j]) << endl;
      return (data[i] & bitmask[j]);
    }
  inline void set(const int pos, const bool b = true)
    {
      //cerr << "set("<<pos<< "," << b << ")" << endl;
      int i=pos/(8*sizeof(unsigned int));
      int j=pos%(8*sizeof(unsigned int));
 
      if (i>=size)
       {
    if (b)
      resize(i+1);
    else
      return;
       }
      if (b)
    data[i] |= bitmask[j];
      else
    data[i] &= ~bitmask[j];
    }
  inline void _xor(const myBitString &s)
    {
      if (s.size>size)
    {
      //cerr << "myBitString.xor calls resize" << endl;
      resize (s.size);
    }
      for (int i=0; i<s.size; i++)
    data[i] ^= s.data[i];
    }
  inline const myBitString& operator ^= (const myBitString &s)
    {
      _xor(s); return *this;  
    }
 
  inline void _and(const myBitString &s1, const myBitString &s2)
  // der eigene Bitstring wird durch s1&s2 (komponentenweise) überschrieben
    {
      int i = MIN(s1.size,s2.size)-1;
      if (i>=size) // <-> i+1>size
    {
          // CAUTION:  (this == &s1 || this == &s2) -> BOOM!!
          // But since (this == &s1 || this == &s2) also
          // implies MIN(s1.size,s2.size)-1 < size, we can safely
          // destroy the array...
          if (data) delete [] data; // alten Vektor löschen
          size=i+1;
          data = new unsigned int[size];
      // Initialisieren der Bits  des neuen Vektors nicht notwendig (geschieht ja gleich durch das and)
    }
      else
       {
         register int j=size-1;
         while (j>i) data[j--]=0; // überschüssige Bits im Resultat löschen
       }
      for (; i>=0; --i)
    data[i] = s1.data[i] & s2.data[i];
    }
 
  template<typename T> void test_and_add_carry(const myBitString &s2, T &CarryVec) const
  // temporäre (komponentenweise) AND-Verknüpfung den eigenen Bitstrings
  // mit s2; den Vektor CarryVector an den korrespondierenden gesetzten
  // Positionen inkrementieren.
    {
      const int s = MIN(size,s2.size);
      const int Bits = 8*sizeof(unsigned int);
      for (int i=0; i<s; ++i)
       {
         register unsigned int h = data[i] & s2.data[i];
         register int j=0;
         while (h)
          {
            if (h&0xff)
             {
               CarryVec[Bits*i+j  ]+=h&1;
               CarryVec[Bits*i+j+1]+=(h>>1)&1;
               CarryVec[Bits*i+j+2]+=(h>>2)&1;
               CarryVec[Bits*i+j+3]+=(h>>3)&1;
               CarryVec[Bits*i+j+4]+=(h>>4)&1;
               CarryVec[Bits*i+j+5]+=(h>>5)&1;
               CarryVec[Bits*i+j+6]+=(h>>6)&1;
               CarryVec[Bits*i+j+7]+=(h>>7)&1;
             }
            h>>=8;
            j+=8;
          }
       }
    }
 
};
 
#endif
Source at commit b0b32840dfbc created 11 years 9 months ago.
By Nathan Adams, compile issues

Archive Download this file

Branches

Tags

Page rendered in 0.79414s using 11 queries.