ccore/src/BitArray.c

#include "core/BitArray.h"

#include <assert.h>
#include <stdio.h>
#include <string.h>

#include "core/Utility.h"

static u64 roundUpDivide(u64 a, u64 b) {
    return a / b + ((a % b) != 0);
}

#define U64_BITS 64
#define DIVIDE_BITS 6

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

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

static size_t getArrayLength(size_t length, size_t bits) {
    return roundUpDivide(length * bits, U64_BITS);
}

void coreCopyBitArray(CoreBitArray* a, const CoreBitArray* other) {
    if(a == other) {
        return;
    }
    coreResizeBitArray(a, other->length, other->bits);
    size_t length = a->length;
    for(size_t i = 0; i < length; i++) {
        coreBitArraySet(a, i, coreBitArrayGet(other, i));
    }
}

void coreMoveBitArray(CoreBitArray* a, CoreBitArray* other) {
    if(a == other) {
        return;
    }
    coreSwapBitArray(a, other);
    coreDestroyBitArray(other);
}

void coreDestroyBitArray(CoreBitArray* a) {
    coreFree(a->data);
    *a = CORE_BIT_ARRAY;
}

CoreBitArray* coreBitArraySet(CoreBitArray* a, size_t index, u64 value) {
    assert(a->data != nullptr);
    assert(index < a->length);
    setBits(a->data, index, a->bits, value);
    return a;
}

u64 coreBitArrayGet(const CoreBitArray* a, size_t index) {
    assert(a->data != nullptr);
    assert(index < a->length);
    return readBits(a->data, index, a->bits);
}

size_t coreBitArrayBytes(const CoreBitArray* a) {
    if(a->length <= 0 || a->bits <= 0) {
        return 0;
    }
    return getArrayLength(a->length, a->bits) * sizeof(u64);
}

i64 coreBitArraySelect(const CoreBitArray* a, size_t index) {
    if(index <= 0) {
        return -1;
    }
    u64 found = 0;
    size_t end = getArrayLength(a->length, a->bits);
    for(size_t i = 0; i < end; i++) {
        u64 ones = corePopCount(a->data[i]);
        found += ones;
        if(found >= index) {
            found -= ones;
            u64 c = i * U64_BITS - 1;
            u64 d = a->data[i];
            while(found < index) {
                found += d & 1;
                d >>= 1;
                c++;
            }
            return (i64)c;
        }
    }
    return -1;
}

void coreResizeBitArray(CoreBitArray* a, size_t newLength, size_t newBits) {
    if(newLength == 0 || newBits == 0) {
        coreDestroyBitArray(a);
        return;
    } else if(newBits > 64) {
        newBits = 64;
    }
    size_t arrayLength = getArrayLength(newLength, newBits);
    u64* newData = coreAllocate(sizeof(u64) * arrayLength);
    memset(newData, 0, arrayLength * sizeof(u64));

    size_t end = coreMinSize(a->length, newLength);
    for(size_t i = 0; i < end; i++) {
        setBits(newData, i, newBits, coreBitArrayGet(a, i));
    }
    for(size_t i = end; i < newLength; i++) {
        setBits(newData, i, newBits, 0);
    }
    coreFree(a->data);
    a->data = newData;
    a->length = newLength & 0xFFFFFFFFFFFFFF;
    a->bits = newBits & 0xFF;
}

void coreFillBitArray(CoreBitArray* a, u64 value) {
    size_t length = a->length;
    for(size_t i = 0; i < length; i++) {
        coreBitArraySet(a, i, value);
    }
}

size_t coreToStringBitArray(const CoreBitArray* a, char* buffer, size_t n) {
    size_t w = 0;
    coreStringAddI(&w, &buffer, &n, snprintf(buffer, n, "["));
    size_t length = a->length;
    if(length > 0) {
        length--;
        for(size_t i = 0; i < length; i++) {
            coreStringAddI(&w, &buffer, &n,
                           snprintf(buffer, n, "%lu, ", coreBitArrayGet(a, i)));
        }
        coreStringAddI(&w, &buffer, &n,
                       snprintf(buffer, n, "%lu", coreBitArrayGet(a, length)));
    }
    coreStringAddI(&w, &buffer, &n, snprintf(buffer, n, "]"));
    return w;
}

void coreSwapBitArray(CoreBitArray* a, CoreBitArray* b) {
    CoreBitArray tmp = *a;
    *a = *b;
    *b = tmp;
}