Re: bsr-algorithm?

On May 22, 10:29 am, spamtrap <spamt...@xxxxxxxxxx> wrote:
Why didn't you tell us that up front?

Didn't expect somebody want's to crack his head with me.

Please specify exactly what your input format is, and what you need as
the final output!

My input format is any integer-type, my output is any float-format
(even custom ones with let's say 1.15.16).

The short input is probably signed 16-bit values, right?

For that function, yes. Can be a long, long long or quadl too.

How should they be converted, i.e. which features of the input do you
actually need to extract?

Can you post a pseudo-code version of the full algorithm?

Pseudo, no, real yes:

inline void importl(const DataType tht) {
DataType t = tht;

/* prepare value and set sign */
bitfield = ZEROp;
/* zero (no negative zero possible) */
if (t == 0)
return;
/* negative (two's complement) */
if (t < 0)
bitfield = ZEROn, t = -t;

/* scan size */
// DataType e = (size - 1) - lzcnt(t);
DataType e = fbpos(t);

/* exponent too big */
if (e > BIAS) {
bitfield |= INFp;
return;
}

/* scan size */
DataType s = fraction - e;

/* fraction too big */
if (s < 0)
t >>= -s, s = 0;

/* normalize fraction and done */
bitfield |= ((e + BIAS) << fraction) | ((t << s) & MAXf);
}

I gave up searching for a MMX version of it (and SSE, ...).
Not because of the branches, but because of the fbpos() I absolutely
couldn't figure out a basic mmx/xmms-solution.

Ciao
Niels


If you're OK with the mask and not the bit index, then one idea is to
replicate the leftmost 1 all the way to the right by repeatedly
shifting the value to the right and OR'ing:

T GetLeftmostOneMask (T x) // T is unsigned type
{
// replicate leftmost 1 to all bits to the right
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16; // last for sizeof(T)*CHAR_BIT==32
x |= x >> 32; // last for sizeof(T)*CHAR_BIT==64
x |= x >> 64; // last for sizeof(T)*CHAR_BIT==128
// reset all 1's but the leftmost
x ^= x >> 1;
return x;
}

The above might be optimizable. And the bit index may actually be
obtained by counting the replicated 1's.

If there was a quick way to reverse bits, this could be reduced to a
much simpler problem of finding of the rightmost 1.

Alex

.