bitVector.h

/*
 * Copyright © 2017 - 2020 Stefan Kebekus <stefan.kebekus@math.uni-freiburg.de>
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 */
 
 
#ifndef bitVECTOR
#define bitVECTOR 1
 
 
#include <QByteArray>
#include <QString>
 
class bitVector
{
 public:
  bitVector();
  
  explicit bitVector(int numBits);
  
  explicit bitVector(QByteArray data);
  
  inline quint8 getBit(int index) const {
    return (content[index/8] >> (7-index%8)) & 0x01;
  }
  
  inline void setBit(int index, quint8 bit) {
    quint32 byteIndex = index/8;
    if (bit) 
      content[byteIndex] = content[byteIndex] |  (0b00000001 << (7-index%8));
    else
      content[byteIndex] = content[byteIndex] & ~(0b00000001 << (7-index%8));
  }
 
  inline int size() const {
    return _size;
  }
 
  void resize(int newSize);
  
  class miniBitVector {
  public:
    quint8 numBits;
    
    quint32 value;
    
    inline quint8 getBit(int index) const {
      return (value >> (numBits-1-index)) & 0x01;
    }
  };
  
  bool startsWith(const miniBitVector &mbv, int index=0) const;
 
  inline void append(const miniBitVector &mbv) {
    // If contents array is too small, expand its size
    if (_size+32 > content.size()*8)
      content.resize(2*content.size()+1000);
    
    quint32 value = mbv.value;
    for(int i=0; i<mbv.numBits; i++) {
      bool bit = value & 0x01;
      value = value >> 1;
      setBit(_size+mbv.numBits-1-i, bit);
    }
    
    _size += mbv.numBits;
  }
 
  operator QByteArray();
  
  operator QString() const;
  
  static inline quint8 getBit(const quint8 *ptr, int index) {
    return (ptr[index/8] >> (7-index%8)) & 0x01;
  }
 
  static inline void setBit(quint8 *ptr, int index, quint8 bit) {
    quint32 byteIndex = index/8;
    if (bit) 
      ptr[byteIndex] = ptr[byteIndex] |  (0b00000001 << (7-index%8));
    else
      ptr[byteIndex] = ptr[byteIndex] & ~(0b00000001 << (7-index%8));
  }
  
  static inline void fill(quint8 *ptr, int startIndex, int numBits, quint8 bit) {
    quint32 endIndex = startIndex+numBits;
    quint32 index=startIndex;
    while(index < endIndex) {
      
      if (index%8 == 0) {
       uintptr_t currentBytePtr = (uintptr_t)(ptr+index/8);
       
       if ((currentBytePtr%8 == 0) && (index+64<endIndex)) {
         *((quint64 *)currentBytePtr) = (bit == 0) ? 0x0000000000000000 : 0xFFFFFFFFFFFFFFFF;
         index += 64;
         continue;
       }
       
       if ((currentBytePtr%4 == 0) && (index+32<endIndex)) {
         *((quint32 *)currentBytePtr) = (bit == 0) ? 0x00000000 : 0xFFFFFFFF;
         index += 32;
         continue;
       }
       
       if ((currentBytePtr%2 == 0) && (index+16<endIndex)) {
         // cppcheck-suppress unreadVariable
         *((quint16 *)currentBytePtr) = (bit == 0) ? 0x0000 : 0xFFFF;
         index += 16;
         continue;
       }
       
       if (index+8<endIndex) {
         ptr[index/8] = (bit == 0) ? 0x00 : 0xFF;
         index += 8;
         continue;
       }
      } // endif: index is on byte boundary
      
      bitVector::setBit(ptr, index, bit);
      index++;
    }
  }
 
  static inline int findEndOfRun(const quint8 *ptr, int startIndex, int endIndex, quint8 runValue) {
    int index=startIndex;
    
    while(index < endIndex) {
 
      if (index%8 == 0) {
       uintptr_t currentBytePtr = (uintptr_t)(ptr+index/8);
 
       // Handle 8-byte words efficiently
       if ((currentBytePtr%8 == 0) && (endIndex-index >= 64)) {
         if (runValue == 0) {
           if ( *((quint64 *)currentBytePtr) == 0) {
             index += 64;
             continue;
           }
         } else {
           if ( *((quint64 *)currentBytePtr) == 0xFFFFFFFFFFFFFFFF) {
             index += 64;
             continue;
           }
         }
       }
       
       // Handle 4-byte words efficiently
       if ((currentBytePtr%4 == 0) && (endIndex-index >= 32)) {
         if (runValue == 0) {
           if ( *((quint32 *)currentBytePtr) == 0) {
             index += 32;
             continue;
           }
         } else {
           if ( *((quint32 *)currentBytePtr) == 0xFFFFFFFF) {
             index += 32;
             continue;
           }
         }
       }
      
       // Handle 2-byte words efficiently
       if ((currentBytePtr%2 == 0) && (endIndex-index >= 16)) {
         if (runValue == 0) {
           if ( *((quint16 *)currentBytePtr) == 0) {
             index += 16;
           continue;
           }
         } else {
           if ( *((quint16 *)currentBytePtr) == 0xFFFF) {
             index += 16;
             continue;
           }
         }
       }
      
       // Handle 1-byte words efficiently
       if (endIndex-index >= 8) {
         if (runValue == 0) {
           if (ptr[index/8] == 0) {
             index += 8;
             continue;
           }
         } else {
           if (ptr[index/8] == 0xFF) {
             index += 8;
             continue;
           }
         }
       }
      } // endif: index is on byte boundary
      
      if (bitVector::getBit(ptr, index) != runValue)
       return index;
      index++;
    }
    
    return endIndex;
  }
  
 private:
  int _size;
  
  QByteArray content;
};
 
#endif