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

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 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 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?

• @Reinderien Done, I was trying out a new config for my editor, and I hadn't changed the defaults. – honeypot Jun 19 at 16:08

• 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 {

      ....