To extract bit fields from an array of bytes that are interpreted as a bit stream, I aim to create an effective bit field extraction function optimized for modern Intel processors (ideally using the new BEXTR instruction ) and MS Visual Studio 2017 (I am 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
In this example, a naive implementation in pseudo code is possible:
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 will most likely 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 can I continue instructing the compiler, please use the new BEXTR instruction?
(3) Should I do this in a completely different way, i.e. to pack everything into lookup tables? (In the end, it's only 8 x 8 possibilities. However, it will not be truly extensible.)