Re: bsr-algorithm?

spamtrap wrote:
Hy;

I saw the discussion about the popcnt, and it reminded me of my own
search of a solution to this function:

/* first-bit position */
static int __fastcall fbpos(short int e) {
but in MMX/XMMX.
I didn't find any slight dicussion of 'emulating' lzcnt or bsr at all,
and the solutions I could think of are very unsmart and probably
slower than sequencially transfering the data into GPRs and do the bsr
there.
I think on AltiVec helps the permutation-op, that we don't have on
x86.

Anybody got an idea about a branch-free 'emulation' of bsr?

Sure!

Getting the most significant bit is easy in SSE, as long as you don't need to work with integers larger than 2^24, or can stand the overhead of converting to double first:

Convert the 4x32-bit (i.e. 4x24-bit) integers into 4xfloat, then treat the result as integers, extracting the exponent field and subtracting 127 to get the most significant bit position.

If you have to handle zero, then you'll have to add a compare against zero either before or after the conversion, then use that as a mask to POR on top of the regular result, so that you'll return -1 for zero inputs.

Branchless, maybe 10 instructions, mostly fast opcodes.

OK?

Terje
--
- <Terje.Mathisen@xxxxxxxxxxxxx>
"almost all programming can be viewed as an exercise in caching"

.

Relevant Pages

  • Re: Basic Bit Operation Question.
    ... Say i have 11001 11010 bits which are infact 10 bits. ... then i would be adding zero. ... static int table_done = 0; ... have an appropriate newsgroups line in your header for your mail to be seen, ...
    (comp.lang.c.moderated)
  • Re: [patch 03/36] Fix Intel IOMMU write-buffer flushing
    ... by simply moving ... static int rwbf_quirk = 0; ... It was originally hard-coded to something other than zero, ... Registered Office: ...
    (Linux-Kernel)
  • bsr-algorithm?
    ... static int __fastcall fbpos{ ... __asm xor eax, eax ... I didn't find any slight dicussion of 'emulating' lzcnt or bsr at all, ...
    (comp.lang.asm.x86)
  • Getting problem while building kernel module
    ... below specified error.please help me for successful ... static int hello_init ... division by zero in #if ...
    (Linux-Kernel)
  • Re: PCI Express support for 2.4 kernel
    ... > static int a2; ... > As you can see, assembly code is identical, compiler did this trivial ... Initializing a static variable to zero ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
Quantcast