Efficient bit field extraction from bytes array being interpreted as a bitstream, possibly using Intel's BMI Set 1

Viewed 229

In order to extract bit fields from a bytes array being interpreted as a bitstream, I am aiming to device an efficient bit field extraction function, optimized for Intel's modern CPUs (ideally making use of the new BEXTR instruction) and MS Visual Studio 2017 (I'm developing in VB.NET).

Inputs: Bitstream left to right (MSB first)
        Pos=0...7, Len=1...8
Output: bitfield at Pos in length Len (LSB right-aligned)

As an example for Pos=0...7 and Len=3 (masking omitted):

Byte0    Byte1    Shifts       
01234567 01234567 
xxx               >> 5
 xxx              >> 4
  xxx             >> 3
   xxx            >> 2
    xxx           >> 1
     xxx          n/a
      xx x        << 1 | >> 7
       x xx       << 2 | >> 6

From the example, a possibly naive implementation in pseudo-code would be:

Extract(Pos, Len, ByteAddr):=
    if 8-Pos-Len > 0
        Res:=[ByteAddr+0] >> 8-Pos-Len
        Res:=Res & (2^Len-1)
    elseif 8-Pos-Len < 0
        Res:=[ByteAddr+0] << Pos+Len-8
        Res:=Res & (2^Len-1)
        Res:=Res | ([ByteAddr+1] >> 16-Pos-Len))
    else
        Res:=[ByteAddr+0] & (2^Len-1)
    fi

Testing this on "paper" (well, notepad.exe these days) for Len=4 and Pos=0...7 shows, that the algorithm is likely to work:

Byte0    Byte1    B0>>      B0<<      &(2^Len-1) B1>>       B0|B1
                  8-Pos-Len Pos+Len-8            16-Pos-Len 
01234567 01234567 01234567  01234567  01234567   01234567   01234567
xxxx....        | 0000xxxx         |  0000xxxx          |          |
.xxxx...        | 000.xxxx         |  0000xxxx          |          |
..xxxx..        | 00..xxxx         |  0000xxxx          |          |
...xxxx.        | 0...xxxx         |  0000xxxx          |          |
....xxxx        |                  |  0000xxxx          |          |
.....xxx y.......           ....xxx0  0000xxx0   0000000y   0000xxxy
......xx yy......           ....xx00  0000xx00   000000yy   0000xxyy
.......x yyy.....           ....x000  0000x000   00000yyy   0000xyyy

Questions:

(1) For efficiency reasons, should I use a lookup table instead of 2^Len-1, or can I rely on the compiler to reliably optimize powers of 2? (Of course, I could also use (1<<Len)-1. Does the compiler do this?)

(2) In VB.NET, how would I proceed to instruct the compiler to pretty please make use of the new BEXTR instruction?

(3) Should I do this completely different, i.e. package everything in lookup tables? (After all, it's just 8 x 8 possibilities. However, it would not truly be expandable.)

0 Answers
Related