3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ @Reinderien Done, I was trying out a new config for my editor, and I hadn't changed the defaults. \$\endgroup\$ – honeypot Jun 19 at 16:08
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Please consider asking a new question instead and feel free to add links back-and-forth. \$\endgroup\$ – Mast Jun 23 at 11:08
3
\$\begingroup\$
  • 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 = ....
    
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.