optimized log base 2

I''ve got a simple one...

int LogBase2(int number) {
	int steps = 0;
	while(number > 1) {
		number >> 1;
		steps++;
	}
	return steps;
} 

Inlined, of course.

I need to get this as fast as possible because it will be happening several hundred thousand times (only at load places though). Would I be better off doing a lookup table?

Does it need to be portable? How about this (32-bit x86 only):


inline unsigned log2(unsigned x)
{
    __asm bsr eax,x
}



[edited by - spock on August 29, 2003 4:20:01 PM]

int __forceinline __fastcall log2(int x)
	{
	__asm
		{
		bsr eax, x;
		}
	}
   

There, it's fixed to minimize future confusion.

[edited by - Magmai Kai Holmlor on August 29, 2003 5:56:28 PM]

quote:

---

Original post by Magmai Kai Holmlor
I think bsr needs a register for input.

---

Nope, only the destination needs to be a register.

Doh, had it backwards

Ahh scary. I've done a little assembly programming on the TI-83+ but nothing as complicated as an x86 processor. Would you mind explaining what's going on with that? I know enough that eax is a register, but what's the bsr call? Do I need to return anything from the function?

[edit] The actual value I'm passing is an unsigned short but I might change it to an unsigned int later. I used int as the parameter to make it portable in case I ever needed it later.

[edit 2] Nevermind, bsr = bitshift right, of course . I'd still like an overview of what happens though.

[edited by - Raloth on August 29, 2003 4:38:21 PM]

Actually, it's bit scan reverse. From my x86 reference:

The bsr instruction scans the bits in the second word or doubleword operand from the most significant bit to the least significant bit. The zero flag is set if all the bits are 0; otherwise, the zero flag is cleared and the destination register is loaded with the bit index of the first set bit found when scanning.

Note that since the argument "will only ever be a power of two" it can't be zero.

[edited by - spock on August 29, 2003 4:42:52 PM]

Yeah I just did some research. It''s "bit scan reverse" instead of bitshift right. Which is right, "bsr x,eax" or "bsr eax,x"? I''m still also confused on how to return the value of the function.

Most compilers on x86 platforms compile the functions to return values in eax, which is exactly what the above examples do. (The one with bsr eax, x that is).

[edited by - Mastaba on August 29, 2003 4:52:53 PM]

My log2 above should work as is with MSVC. Since it's inline assembly it will likely need to be changed if you are using another compiler.

[edited by - spock on August 29, 2003 4:57:19 PM]

But which comes first, x or eax??? You guys gave me it both ways.

My log2 above should work as is with MSVC.

It''s an x86 so the destination is the first parameter. I had it backwards.

if the source doesn''t contain any set bits then the destination is undefined, as far as i remember... so be careful like

Unfortunately bsf is slow on Athlons. Crazy idea: given the number as a float, shift right 23 bits to get biased exponent (no need to mask off sign bit - number is positive, right?), and subtract 127.

Try this.

MSN

quote:

---

Original post by Anonymous Poster
You should check if x is 0 before passing it to the bsr instruction.

---

And throw an exception? It could be argued that the result of calling log2(0) should be undefined; trying to compute the logarithm of zero is asking for trouble.

quote:

---

Original post by Jan Wassenberg
Crazy idea: given the number as a float, shift right 23 bits to get biased exponent (no need to mask off sign bit - number is positive, right?), and subtract 127.

---

I tried that when I first needed log2 and it works fine. The input was integers so I still ended up using bsr. It won''t be faster (even on Athlon) if I have to convert to a float first, right?

quote:

---

spock
I tried that when I first needed log2 and it works fine. The input was integers so I still ended up using bsr. It won''t be faster (even on Athlon) if I have to convert to a float first, right?

---

You''d have to get the ISR and count cycle times. I wouldn''t expect it to be, because after you convert to a float (fld), I think you''d have to store it back to memory (fstp), and load it from memory into eax, and then you could begin masking & shifting. If it already was a float, then the exponent is the log base 2, and it''d still take a mov, and, shift, & sub assuming it is a perfect power of 2 stored as a float .

Seems silly, when bsr is tailor fit. As a general rule, micro-code executes far, far faster than op code.

quote:

---

Original post by Anonymous Poster
This statement is not correct. A more correct statement would be "It''s with MSVC, so the destination is the first parameter." The architecture never implies anything about the assembler syntax.

---

It''s Intel syntax, so the destination is first.

Actually, converting & extracting float exponent might even be faster in optimized code: bsr/bsf are 8-14 cycle vectorpath ops. fild+fstp+mov+shr+sub latency is less, and you get 2 extra decode slots. Mem traffic isn''t a problem due to forwarding.
But that''s all theory - you''ll have to try it out

ISR?
Masking is not needed if the input is positive. This algorithm works for non-powers of 2 as well, except 0 (which is undefined anyway, as spock points out).

> Seems silly, when bsr is tailor fit.
bsr is a useful instruction - I wish they had implemented it efficiently...

> As a general rule, micro-code executes far, far faster than op code.
Obviously Top >= Tµop, but microcoded instructions (''vectorpath'') are slower - the program has to be fetched from memory during decode, which can only be done at a rate of 1 op/clock.