I have a long x;
I want to write a function 

long f(long x, int k)

such that it extracts every k-th bit of x, concatenates
them and returns it. Anyone can help me in writing this
function? 

examples
 x = 10101010 k = 1  f(x) = 10101010
 x = 10101010 k = 2  f(x) = 1111
 x = 10101010 k = 3  f(x) = 010 
 x = 10101010 k = 4  f(x) = 11
 
Any bit gurus here who can help me? In x86 assembly please?
What if x can be char[8] and k > 2? any MMX/SIMD Tricks applicable here?

Thanks,
--Elijah

Elijah Bailey wrote:
> I have a long x;

How wide is a long int on your CPU/OS/compiler platform?

> I want to write a function
> 
> long f(long x, int k)
> 
> such that it extracts every k-th bit of x, concatenates
> them and returns it. Anyone can help me in writing this
> function?
> 
> examples
>  x = 10101010 k = 1  f(x) = 10101010
>  x = 10101010 k = 2  f(x) = 1111
>  x = 10101010 k = 3  f(x) = 010
>  x = 10101010 k = 4  f(x) = 11
>  
> Any bit gurus here who can help me? In x86 assembly please?
> What if x can be char[8] and k > 2? any MMX/SIMD Tricks applicable here?

I see one solution using RCL/RCR (rotate through carry left/right) 
but these instructions have a latency of 5 cycles on the Athlon...

You could also use logical operations to isolate the bit you want, 
and use shift operations to place it where it should go.

Show us the code you've come up with so far.

"Elijah Bailey" <geomrock@hotmail.com> wrote in message
news:e008fef8.0312030002.39e912dc@posting.google.com...
> I have a long x;
> I want to write a function
>
> long f(long x, int k)
>
> such that it extracts every k-th bit of x, concatenates
> them and returns it. Anyone can help me in writing this
> function?
>
> examples
>  x = 10101010 k = 1  f(x) = 10101010
>  x = 10101010 k = 2  f(x) = 1111
>  x = 10101010 k = 3  f(x) = 010
>  x = 10101010 k = 4  f(x) = 11
>
> Any bit gurus here who can help me? In x86 assembly please?
> What if x can be char[8] and k > 2? any MMX/SIMD Tricks applicable here?

Offhand:

int mask, bit, xmask;

// ASSUME: 1 <= k <= (sizeof(long) * CHAR_BIT)
k--;
for(mask = 0, xmask = -1, bit = 1; xmask >= bit, bit <<= 1)
{
 x >>= k;
 xmask >>= k;
 mask |= x & bit;
}

I can't think of any reason why this wouldn't be portable; it would be best
to ask the residents of comp.lang.c.

I don't think there are any tricks with the bt/btr/bts/btc family of
instructions that you can use for speed. You may be able to use a multiply
to get the bits where you want them to be, but the method is beyond me. I
can compute a multiplier for at least some values of k by masking first. For
example, with k = 6:

mask     = 0010 0000 1000 0010 0000 1000 0010 0000b
x & mask = 00A0 0000 B000 00C0 0000 D000 00E0 0000b
mult     = 0000 0000 0010 0010 0001 0000 1000 0100b

(x & mask) * mult =

  A000 00B0 0000 C000 00D0 0000 E000 0000b
+ 0B00 000C 0000 0D00 000E 0000 0000 0000b
+ 00C0 0000 D000 00E0 0000 0000 0000 0000b
+ 000D 0000 0E00 0000 0000 0000 0000 0000b
+ 0000 E000 0000 0000 0000 0000 0000 0000b
  ---------------------------------------
= ABCD E0BC DE00 CDE0 00DE 0000 E000 0000b

((x & mask) * mult) >> 27 = ABCDEb

That's a whole 6 cycles + lookup penalties on Athlon or 21-23 cycles on P4.
The loop I gave earlier is easily >96 clocks on P4 and >12 clocks on Athlon,
so the multiply method is much faster assuming you don't miss the cache.

You may only require one table; notice that there is a relationship between
mask[k - 1] and mult[k].

-Matt

Hi, have a look at BT (for src) and BTS, BTR (for dest). They can handle bit
strings up to 4GBit in length. Unfortunately there is no BM (bit move)
instruction. Juergen.

On Wed, 03 Dec 2003 16:02:41 GMT, "Matt Taylor" <para@tampabay.rr.com>
wrote:

> "Elijah Bailey" <geomrock@hotmail.com> wrote in message
> news:e008fef8.0312030002.39e912dc@posting.google.com...
> > I have a long x;
> > I want to write a function
> >
> > long f(long x, int k)
> >
> > such that it extracts every k-th bit of x, concatenates
> > them and returns it. <snip>

> Offhand:
> 
> int mask, bit, xmask;
> 
> // ASSUME: 1 <= k <= (sizeof(long) * CHAR_BIT)
> k--;
> for(mask = 0, xmask = -1, bit = 1; xmask >= bit, bit <<= 1)
> {
>  x >>= k;
>  xmask >>= k;
>  mask |= x & bit;
> }
> 
> I can't think of any reason why this wouldn't be portable; it would be best
> to ask the residents of comp.lang.c.
> 
As a part-time resident there,  maybe I can help.

As written it doesn't even compile, you only have two segments in the
for().  Presumably you wanted the last comma to be a semicolon --
xmask >= bit is the loop condition and bit <<= 1 the iteration step.
With that change it never loops and always computes zero, because
signed -1 is not (ever) >= +1. If you make the comparison unsigned,
the signed right shift xmask >>= k is implementation-defined, and in
particular on 2sC machines including x86 often (usually?) propagates
the sign. So you would really want to make xmask unsigned long. 

But you don't need xmask at all; just iterate until all (possibly)
relevant 1 bits in _x_ have been handled. Unless you need to ensure
constant execution time for e.g. real-time schedulability or to
prevent power analysis of security/cryptographic processing, in which
cases you might be able to also/instead just add a guard bit to x.
Or if you hope/expect that the compiler will unroll the actually-
constant number of iterations (if it's beneficial).

Personally I would make x unsigned long (too) if at all possible;
bitwise values are best handled (consistently) as unsigned types.

Finally, if k is >= the "width" of the integer type, which is the
number of value (magnitude) bits plus the sign bit for signed, and
*may* be but rarely if ever is less than sizeof x * CHAR_BIT because
of padding bits, the effect is completely undefined; on quite a few
machines, including x86, it shifts modulo the number of bits so for k
== width it doesn't shift at all. This function isn't really useful
for k >= width since it only selects x & 1, so you might just prohibit
that usage; or if it is necessary, special-case it.

Oh, and I wouldn't call the result 'mask'. It isn't a mask.


- David.Thompson1 at worldnet.att.net