  lua-l archive

• Subject: Re: [ANN] Lua 5.3.0 (work2) now available
• From: Jay Carlson <nop@...>
• Date: Wed, 26 Mar 2014 18:27:00 -0400

On Mar 26, 2014 2:15 PM, "Doug Currie" <doug.currie@gmail.com> wrote:

> On Wed, Mar 26, 2014 at 12:41 PM, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
>>
>> Just for curiosity, do you remember those techniques?
>
> One application that comes to my mind is extracting a signed M bit field from bit position P in a word of length N:
>
> (x << (N - (P + M))) >> (N - M)
>
> where >> is signed (otherwise the field won't be sign extended), and bit positions are little endian, M <= N, P <= N.

If you want bit-twiddling fun, you want
http://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtend which through the power of xkcd386 has been scrubbed of arithmetic shifts.

Here's the variable sign extension entry:

====
unsigned b; // number of bits representing the number in x
int x;      // sign extend this b-bit number to r
int r;      // resulting sign-extended number
int const m = 1U << (b - 1); // mask can be pre-computed if b is fixed

x = x & ((1U << b) - 1);  // (Skip this if bits in x above position b are already zero.)
r = (x ^ m) - m;

The code above requires four operations, but when the bitwidth is a constant rather than variable, it requires only two fast operations, assuming the upper bits are already zeroes.

A slightly faster but less portable method that doesn't depend on the bits in x above position b being zero is:

int const m = CHAR_BIT * sizeof(x) - b;
r = (x << m) >> m;
====

> This sort of thing comes up in embedded applications, e.g., pulling a ADC value out of a SPI packet, or parsing a binary comm buffer.

All of this starts to look suspiciously like scanf/printf at the bit level.

> This is a case where // 2^(N - M) would be fine... assuming the // and ^ operators are performant enough, which I am skeptical about in embedded processors where integer mode would be used.

I'll take that bet. All the SoCs with 32k of RAM seem to be Cortex M3s and up. 12-cycle 32-bit divider.

Jay