Array-like data structure for fixed sized types with non-machine-word sizes

Question

I am writing an array-like data structure for types other than 8 16 32 64 – the usual type sizes.

Ideally, my interface is the following for addressing the array.

void setindex(uint8_t *array, size_t width, size_t index, uint64_t value);
uint64_t getindex(uint8_t *array, size_t width, size_t index);

This is basically an array of unsigned integers of size width. A uint8_t value would contain 4 elements for width=2, at max. This should hold no more metadata than that. So in theory, it should work with any blob of allocated memory. Bound-checks should be done by the caller.

I have the following code, packed as a very small header library:

#include <cstdio>
#include <iostream>
#include <bitset>
#include <cassert>

using namespace std;

uint64_t getindex(uint64_t *A, size_t width, size_t index)
{
    uint64_t mask, mask1, mask2, ret, shift;
    uint64_t size, d, m;

    size = sizeof A[0] * 8;
    mask = (1 << width) - 1;
    shift = index * width;

    // Any decent compiler does this in one instruction
    d = (index + 1) * width / size;
    m = (index + 1) * width % size;

    if (!d) {
        ret = (*A & (mask << (shift))) >> shift;
    } else {
        mask1 = (1 << m) - 1;
        mask2 = (1 << (width - m)) - 1;

        ret = (A[d] & mask1) << (width - m) | (A[d - 1] & (mask2 << (size - (width - m)))) >> (size - (width - m));
    }

    return ret;
}

uint64_t setindex(uint64_t *A, size_t width, size_t index, uint64_t value)
{
    uint64_t mask, mask1, mask2, shift;
    uint64_t size, d, m;

    assert(value < (1 << width));

    size = sizeof A[0] * 8;

    mask = (1 << width) - 1;

    shift = index * width;

    // Any decent compiler does this in one instruction
    d = (index + 1) * width / size;
    m = (index + 1) * width % size;

    if (!d) {
        A[0] = (A[0] & ~(mask << (shift))) | (value << shift);

    } else {
        mask1 = (1 << m) - 1;
        mask2 = (1 << (width - m)) - 1;

        A[d] = (A[d] & ~mask1) | (((mask1 << (width - m)) & value) >> (width - m));
        A[d - 1] = A[d - 1] & ~(mask2 << size - m) | ((mask2 & value) << (size - (width - m)));
    }

    return value;
}

I come from C, so the code may be very C-like, as I don't fully know most of the C++ features well.

Can this be simplified and made more robust? The above code may have problems with bit shifting and undefined behavior. I have the feeling that this problem is very well suited for fors and divmods algorithms, like those used to construct gcd. But in my implementation, I did not manage to do that. Are there existing libraries I can better use?

Answer 1

• using namespace std; is a bad practice.

• The code is plain C. You have two options:

  1. Admit this fact, change your #includes to the C-style, and declare your functions as extern "C". This way they are callable from both C and C++ code.

  2. Make a class, and overload operator[](std::size_t) and operator[](std::size_t) const. The width shall be a class member. Much more C++ish.

• An A parameter to getindex should be const-qualified.

• Declare variables as close to use as possible. E.g. instead of

        uint64_t mask1;
        ....
        if () {
            ....
        } else {
            mask1 = ....;
        }
  

  do

        ....
        if () {
        } else {
            uint64_t mask2 = ....