Jump to content
  • Advertisement
Sign in to follow this  
Promit

Fast integer log2?

This topic is 5071 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm looking for a really fast integer log2. It can assume that the input is always a power of 2, or it can simply round off non-pow2, or whatever. This is partly useful for me and mostly just curiosity to see what kind of wacky optimizations/fast routines you guys can come up with.

Share this post


Link to post
Share on other sites
Advertisement
x86 ASM opcode: BSR (bit scan reverse). Returns the index of the highest non-zero bit. I.e. the log base two, rounding down.
Results are undefined if the original number is zero.

Share this post


Link to post
Share on other sites
Damn, that was easy.

[EDIT] Uh...I'm not too good with assembly. If I tell it to put the result in eax, can I use that to not give the function a real return statement?

Share this post


Link to post
Share on other sites

DWORD dwNumber=something other than 0;
DWORD dwLog2;

__asm
{
mov dwLog2, dwNumber
bsr dwLog2
}


I'm not good with asm (well not x86 at least) either, but that would be my best guess. Maybe someone can point out any mistakes I made?

Share this post


Link to post
Share on other sites

int pow2( int x )
{
__asm
{
bsr eax, x
ret
}

//dummy return
return 0;
}


That caused an access violation. I thought return values were in eax?

Share this post


Link to post
Share on other sites
Here is the code with stack prolog-epilog code:


#include <iostream>

using namespace std;


// logarithm function
__declspec (naked) int log2(int val)
{
// prepare stack
__asm {
push ebp
mov ebp, esp
sub esp, __LOCAL_SIZE
}

__asm {
mov eax,[val]
jz log2end
bsr eax,eax
log2end:
}

// Cleanup function
__asm
{
mov esp, ebp
pop ebp
ret
}

}

int main()
{

cout << "Result: " << log2(2) <<endl;

return 0;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The zero case will not work correctly for that however. mov doesn't set flags, you need a test as well

Share this post


Link to post
Share on other sites
Quite right. Change to:


__asm {
mov eax,[val]
test eax,0
jz log2end
bsr eax,eax
log2end:
}

Share this post


Link to post
Share on other sites
Cool.

Now can you explain to me how the prolog code works, and why you need test?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!