Masking out unwanted bits from array of uint64_t

Question

I have an array of 8 uint64_t (512 bits). I also receive 2 numbers as function parameters. Let them be 54 and 133. I need to mask out every bit with position (zero based) lower then 54 or higher then 133 .

What is the most cost efficient way to do that?

It would be easy to do so with one uint64_t.

int a=6;
int b=12;
uint64_t source=0xD0400000000000;
uint64_t mask=0xFFFFFFFFFFFFFFFF;
uint64_t result=source&((mask<<(a+63-b))>>a);//D0000000000000

But there is a problem with data larger then uint64_t (in this case an array). Also, another problem is when these bits i want to extract cross boundaries of multiple uint64_t's.
This code has to be really fast, so I have to avoid branches or any costly operations.

Is there a way to implement it with intrinsics to make it perform fast?

Answer 1

Whether you like it or not, you'll need special handling for the first and the last array element involved, with if. Basically, you have to convert your first and last into bit-number/array index pairs, and work from there. To mask out everything but the designated range, you zap everything beloe the first array index, and after the last (probably using std::fill), and special handle the elements at the first and last array index (which may be the same, which in turn entails special handling, different from the case where they are different). Very roughly (and without any error handling):

//  quot is element index,
//  rem is bit number in element.
div_t first = div( firstBitNumber, bitsInWord );
div_t last = div( lastBitNumber, bitsInWord );
std::fill( array.begin(), array.begin() + first.quot, 0 );
if ( first.quot == last.quot ) {
    array[ first.quot ] &= ((1 << last.rem) - 1) & ~((i << first.rem) - 1);
} else {
    array[ first.quot ] &= ~((i << first.rem) - 1);
    array[ last.quot ] &= ((1 << last.rem) - 1);
}
std::fill( array.begin() + last.quot + 1, array.end(), 0 );

You'll probably need some casts with the shift operators, in order to ensure they use the full size of the array elements. And of course, you definitely want to ensure that first and last are in bounds before any of this.