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.)