C: Implementing array of nibbles

Question

I am trying to stuff 16 unsigned values into 8 bytes (64 bit), and access them using an array-like syntax.
Every entry in the "array" will be one nibble - 4 bit long. (The values I plan to store are never bigger than 15).

My first attempt was this:

int main(int argc, char* argv[]) {

    union nibbles_array {
        uint64_t as_long;

        struct inner_array {
            unsigned entry0  : 4;
            unsigned entry1  : 4;
            unsigned entry2  : 4;
            unsigned entry3  : 4;
            unsigned entry4  : 4;
            unsigned entry5  : 4;
            unsigned entry6  : 4;
            unsigned entry7  : 4;
            unsigned entry8  : 4;
            unsigned entry9  : 4;
            unsigned entry10 : 4;
            unsigned entry11 : 4;
            unsigned entry12 : 4;
            unsigned entry13 : 4;
            unsigned entry14 : 4;
            unsigned entry15 : 4;
        } as_array;     
    } array;

    array.as_long = 0x0123456789abcdef;

    printf("%d \n", array.as_array.entry0);
    printf("%d \n", array.as_array.entry1);
    printf("%d \n", array.as_array.entry2);
    printf("%d \n", array.as_array.entry3);
    printf("%d \n", array.as_array.entry4);

    return 0;
}

Two problems arises from this implementation: the first is that the values are stored in reverse order. I can, of course, assign the values in reverse order to get the desired result: array.as_long = 0xfedcba9876543210, but I want this code to be portable, and not endianness-dependent. The second is that I can't access the nibbles with an index, in an array-like syntax.

The second attempt was this:

int main(int argc, char* argv[]) {

    uint64_t pseudo_array = 0x0123456789abcdef;

    #define Array(i) (unsigned)((pseudo_array & (0xfUL << i)) >> i)

    int i;
    for (i = 0; i < 16; ++i) {
        printf("%d ", Array(i));
    }

    printf("\n");

    return 0;
}

The above can solve the second problem (array-like syntax); now I can access "elements" with index, but the problem of endianness remains, plus this produces wrong output:

15 7 11 13 14 15 7 11 13 6 3 9 12 14 15 7

Why is the above produces this output?
Can you please suggest implementation that will both allow me to access the "array" by index and will solve the endianness problem?

What makes you think your second attempt still has an endianness problem? — John Bollinger, Dec 08 '15 at 19:52
You need to multiply `i` by 4 when using it as a nibble shift amount (shift amounts are in bits). Also, you can eliminate a shift by simply shifting `pseudo_array` right by `4*i` first, then masking (you could even cast before masking). — Tom Karzes, Dec 08 '15 at 19:53
@Codor, it seems reasonable to assume that the `uint64_t` used is the one defined by the standard header `stdint.h`. — John Bollinger, Dec 08 '15 at 19:55
Just use an array of `uint8_t` to store the nibbles. Sure it wastes a little space, but is the space savings really worth the trouble. Also, you could store two nibbles in each `uint8_t`, if space really is that important. — user3386109, Dec 08 '15 at 19:58
@JohnBollinger is right, it is the one defined in the standard. Sorry for not mentioning that. — so.very.tired, Dec 08 '15 at 20:33

chqrlie · Accepted Answer · 2015-12-08T21:02:46.727

2

Your first attempt definitely has portability issues: the mapping between bitfields and actual bits in memory is not defined in the Standard. It is not exactly an endianness issue, and you cannot have an array like syntax either.

Your second attempt is much more portable. The issue is not endianness either, but your own conception of what is the n-th element of the array. The macro is erroneous because you do not shift by the correct number of bits: i must be multiplied by 4. I would suggest this macro to fit your understanding:

#define Array(a, i)  ((unsigned)(((a) >> (60 - 4 * (i))) & 0xf))

edited Dec 08 '15 at 21:02

answered Dec 08 '15 at 19:52

chqrlie

131,814
10
121
189

"The issue is not endianness either, but your own conception of what is the n-th element of the array." Exactly right. I guess this confused me. Thank you for your solution, this will work for me. – so.very.tired Dec 08 '15 at 20:35

score 1 · Answer 2 · answered Dec 08 '15 at 20:02

1

The undesired output is caused by the fact that the macro is defined in the wrong way; you mean to shift nibble-wise, not bit-wise. The desired behaviour can be achieved by defining the macro as follows.

#define Array(i) (unsigned)((pseudo_array & ((uint64_t)0x0f << (4*i))) >> (4*i))

answered Dec 08 '15 at 20:02

Codor

17,447
9
29
56

1

Be careful to parenthesize `i` in the macro expansion. – chqrlie Dec 08 '15 at 21:09

score 0 · Answer 3 · answered Dec 08 '15 at 19:54

Instead of storing the "vector" as bitfields, could use a dynamically allocated array, and a set of functions for accessing individual "indexes" of your array as well as functions to set or get larger parts of the "array" using larger types (like e.g. uint64_t).

Something like the following API

// The "na" prefix stands for Nibble Array

struct nibble_array
{
    uint8_t *data;  // The actual "array" of nibbles
    size_t   size;  // Current size of "array" (number of elements)
};

// Create an array containing a number of elements
struct nibble_array *na_create(const size_t elements);

// Get a value from specified index in array
int na_get(const struct nibble_array *array, const size_t index);

// Set a specified index in the array to a value
void na_set(struct nibble_aray *array, const size_t index, const int value);

// Get the number of elements (nibbles) in the array
size_t na_size(const struct nibble_array *array);

// Set a larger part of the array to some values
void na_set64(struct nibble_array *array, size_t start_index, const uint64_t value);

You don't have to provide the definition of the nibble_array structure if you want the data to be private (read about opaque pointers).

score 0 · Answer 4 · answered Dec 08 '15 at 20:07

How about something like this:

#include <stdio>

int main(int argc, char* argv[]) {

    unsigned char array[8] = { 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF };

    #define Array(i) (i%2 ? (array[i/2] & 0x0F) : ((array[i/2] & 0xF0) >> 4))

    int i;
    for (i = 0; i < 16; ++i) {
        printf("%d ", Array(i));
    }

    printf("\n");
    return 0;
}

drognisep · Answer 5 · 2015-12-08T20:20:27.750

0

I believe @chqrlie is correct concerning endianness issues, but I think it would be easier to just use an array.

uint8_t ary[20]; /* 40 nibbles */
#define getnibblelen(ary) (sizeof(ary) * 2) /* works because it's an ARRAY of uint8_t, wouldn't work if you're passing the array to a function. */
#define getnibble(ary, idx) (idx % 2 ? /* if odd */ ary[idx/2] & 0xf0 >> 4 : /* if even */ ary[idx/2] & 0x0f)
#define setnibble(ary, idx, val) (idx % 2 ? ary[idx/2] = (ary[idx/2] & 0x0f) | ((val & 0x0f) << 4) : ary[idx/2] = (ary[idx/2] & 0xf0) | (val & 0x0f))

edited Dec 08 '15 at 20:20

answered Dec 08 '15 at 20:10

drognisep

579
1
7
16

I don't have 40 nibbles to spend... I only have 16. – so.very.tired Dec 08 '15 at 20:32
1

The macro arguments must be parenthesized in the expansion. Evaluating them more than once should be avoided as it is error prone. If you cannot achieve that, use inline functions. – chqrlie Dec 08 '15 at 21:16
@so.very.tired: 40 was an arbitrary choice, change that to an 8 byte array. – drognisep Dec 09 '15 at 00:06

C: Implementing array of nibbles

5 Answers5