2
\$\begingroup\$

Apologies for the cryptic title, but the problem really is rather simple.

I have a 64 bit integer which I interpret as 16 4 bit nibbles, or a nibble array if you wish, and I needed generate a mask covering the nibbles which are zero, or the inverse.

I have already come up with a solution, but it seems to me that there has to be a better way.

uint64_t getNonZeroMask( uint64_t b )
{
    return ( ( ( b >> 2 | b ) >> 1 | ( b >> 2 | b ) ) & 0x1111111111111111 ) * 15;
}

The above is the most efficient I've found. I've tried numerous approaches, but they pretty much all use the same approach.

Just in case there should be any doubt what exactly I'm frying to do, a give value: ex.

0x010203456000abc0

Should give the mask:

0x0f0f0ffff000fff0

or the inverse.

What I have works, of course, but I do believe it can be done better, and I'd very much like to know how. Preferably it would only involve bitwise operations. Intrinsics from bmi and similar are okay, but I haven't found anything that seems useful. It may be that I'm entirely in the wrong, and this is indeed the way of doing it, in which case I'd very much like to know that too.

\$\endgroup\$
3
\$\begingroup\$

Intrinsics from bmi and similar are okay, but I haven't found anything that seems useful.

They're not very useful for this. pdep and pext let you do this in a different way, but it's not better (especially not on AMD Zen1), you shouldn't use this (but maybe it's interesting to think about):

uint64_t m = 0x1111111111111111;
uint64_t stacked = _pext_u64(b, m) | _pext_u64(b, m << 1) |
                   _pext_u64(b, m << 2) | _pext_u64(b, m << 3);
return _pdep_u64(stacked, m) * 15;

There is a slightly different way to write the original logic in a way that may be easier to read, of course that's subjective but it will be as a straight-line composition of common bitwise idioms, it shouldn't make any difference for a compiler. It's the same thing really, but instead of being a single expression it's linearized into discrete steps, which also creates the opportunity for in-line comments to explain the steps:

uint64_t getNonZeroMask( uint64_t b )
{
    // horizontal OR of nibbles in log(bits) steps
    b |= b >> 2;
    b |= b >> 1;
    // remove polluted bits, leaving the results in the lsb of every nibble
    b &= 0x1111111111111111;
    // spread single bit flags into full nibbles
    return b * 15;
}
\$\endgroup\$
2
\$\begingroup\$

This might be faster than your solution.

#include <stdio.h>

typedef struct __attribute__((__packed__)) {
    unsigned int N0 : 4;
    unsigned int N1 : 4;
    unsigned int N2 : 4;
    unsigned int N3 : 4;
    unsigned int N4 : 4;
    unsigned int N5 : 4;
    unsigned int N6 : 4;
    unsigned int N7 : 4;
    unsigned int N8 : 4;
    unsigned int N9 : 4;
    unsigned int NA : 4;
    unsigned int NB : 4;
    unsigned int NC : 4;
    unsigned int ND : 4;
    unsigned int NE : 4;
    unsigned int NF : 4;
} SIXTEENNIBBLES;

typedef union __attribute__((__packed__)) {
    unsigned long QWORD : 64;
    SIXTEENNIBBLES NIBBLE;
} QWONI; /* QWORD-NIBBLES */

QWONI createmask(QWONI qwoni) {
    QWONI mask;
    mask.QWORD = 0x0000000000000000;
    if(qwoni.NIBBLE.N0) mask.NIBBLE.N0 = 0xF;
    if(qwoni.NIBBLE.N1) mask.NIBBLE.N1 = 0xF;
    if(qwoni.NIBBLE.N2) mask.NIBBLE.N2 = 0xF;
    if(qwoni.NIBBLE.N3) mask.NIBBLE.N3 = 0xF;
    if(qwoni.NIBBLE.N4) mask.NIBBLE.N4 = 0xF;
    if(qwoni.NIBBLE.N5) mask.NIBBLE.N5 = 0xF;
    if(qwoni.NIBBLE.N6) mask.NIBBLE.N6 = 0xF;
    if(qwoni.NIBBLE.N7) mask.NIBBLE.N7 = 0xF;
    if(qwoni.NIBBLE.N8) mask.NIBBLE.N8 = 0xF;
    if(qwoni.NIBBLE.N9) mask.NIBBLE.N9 = 0xF;
    if(qwoni.NIBBLE.NA) mask.NIBBLE.NA = 0xF;
    if(qwoni.NIBBLE.NB) mask.NIBBLE.NB = 0xF;
    if(qwoni.NIBBLE.NC) mask.NIBBLE.NC = 0xF;
    if(qwoni.NIBBLE.ND) mask.NIBBLE.ND = 0xF;
    if(qwoni.NIBBLE.NE) mask.NIBBLE.NE = 0xF;
    if(qwoni.NIBBLE.NF) mask.NIBBLE.NF = 0xF;
    return mask;
}

int main(int argc, char *argv[]){
    QWONI mynibbles;
    mynibbles.QWORD = 0x010203456000abc0;
    
    printf("sizeof(mynibbles)           = %d\n", sizeof(mynibbles));
    printf("mynibbles.QWORD             = %llx\n", mynibbles.QWORD);
    printf("createmask(mynibbles).QWORD = %llx\n", createmask(mynibbles).QWORD);

    return 0;
}
\$\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.