gaming-core/data/BitArray.cpp

#include "data/BitArray.h"

#include "math/Math.h"

static int roundUpDivide(int a, int b) {
    if(a % b == 0) {
        return a / b;
    }
    return a / b + 1;
}

static constexpr int INT_BITS = sizeof(int) * 8;
static constexpr int DIVIDE_BITS = Math::roundUpLog2(INT_BITS);

static int readBits(const int* data, int index, int bits) {
    int dataIndexA = (index * bits) >> DIVIDE_BITS;
    int dataIndexB = ((index + 1) * bits) >> DIVIDE_BITS;
    int shifts = (index * bits) & (INT_BITS - 1);
    if(dataIndexA == dataIndexB) {
        return (data[dataIndexA] >> shifts) & ((1 << bits) - 1);
    }
    int bitsInA = INT_BITS - shifts;
    int r = (data[dataIndexA] >> shifts) & ((1 << bitsInA) - 1);
    r |= (data[dataIndexB] & ((1 << (bits - bitsInA)) - 1)) << bitsInA;
    return r;
}

static void setBits(int* data, int index, int bits, int value) {
    int mask = (1 << bits) - 1;
    value &= mask;
    int dataIndexA = (index * bits) >> DIVIDE_BITS;
    int dataIndexB = ((index + 1) * bits) >> DIVIDE_BITS;
    int shifts = (index * bits) & (INT_BITS - 1);
    data[dataIndexA] &= ~(mask << shifts);
    data[dataIndexA] |= (value << shifts);
    if(dataIndexA != dataIndexB) {
        int leftBits = bits - (INT_BITS - shifts);
        data[dataIndexB] &= ~((1 << leftBits) - 1);
        data[dataIndexB] |= (value >> (INT_BITS - shifts));
    }
}

static int getArrayLength(int length, int bits) {
    return roundUpDivide(length * bits, sizeof(int) * 8);
}

BitArray::BitArray() : length(0), bits(0), data(nullptr) {
}

static int* allocate(int length, int bits) {
    int l = getArrayLength(length, bits);
    int* a = new int[l];
    memset(a, 0, static_cast<size_t>(l) * sizeof(int));
    return a;
}

BitArray::BitArray(int length_, int bits_)
    : length(length_), bits(bits_), data(nullptr) {
    if(length > 0 && bits > 0) {
        data = allocate(length, bits);
    }
}

BitArray::BitArray(const BitArray& other) : BitArray(other.length, other.bits) {
    for(int i = 0; i < length; i++) {
        set(i, other.get(i));
    }
}

BitArray::BitArray(BitArray&& other) : BitArray() {
    swap(other);
}

BitArray::~BitArray() {
    delete[] data;
}

BitArray& BitArray::operator=(BitArray other) {
    swap(other);
    return *this;
}

BitArray& BitArray::set(int index, int value) {
    setBits(data, index, bits, value);
    return *this;
}

int BitArray::get(int index) const {
    return readBits(data, index, bits);
}

int BitArray::getLength() const {
    return length;
}

int BitArray::getBits() const {
    return bits;
}

int BitArray::getInternalByteSize() const {
    if(bits <= 0 || length <= 0) {
        return 0;
    }
    return getArrayLength(length, bits) * static_cast<int>(sizeof(int));
}

int BitArray::select(int index) const {
    if(index <= 0) {
        return -1;
    }
    int found = 0;
    int end = getArrayLength(length, bits);
    for(int i = 0; i < end; i++) {
        int ones = __builtin_popcount(static_cast<unsigned int>(data[i]));
        found += ones;
        if(found >= index) {
            found -= ones;
            int a = i * 32 - 1;
            int d = data[i];
            while(found < index) {
                found += d & 1;
                d >>= 1;
                a++;
            }
            return a;
        }
    }
    return -1;
}

void BitArray::fill(int value) {
    for(int i = 0; i < length; i++) {
        set(i, value);
    }
}

void BitArray::resize(int newLength, int newBits) {
    int* newData = allocate(newLength, newBits);
    int end = Math::min(length, newLength);
    for(int i = 0; i < end; i++) {
        setBits(newData, i, newBits, get(i));
    }
    for(int i = end; i < newLength; i++) {
        setBits(newData, i, newBits, 0);
    }
    delete[] data;
    data = newData;
    bits = newBits;
    length = newLength;
}

void BitArray::swap(BitArray& other) {
    std::swap(length, other.length);
    std::swap(bits, other.bits);
    std::swap(data, other.data);
}