Sunday, January 06, 2008

latex and footnotes

In latex if you have a footnote and a figure with b (bottom) placement attribute on the same page, then the figure will be placed under the footnote. The result is really ugly....

I was searching for a way to fix this. Of course the straight-forward solution is to use the h (here) attribute in the figure and put the figure's code in the position you want, but this is not the best thing to do.

Well.. there is a way to force the footnotes to be always placed at the bottom of the page. You can do this by using the footmisc-package. By using this package you can change the default typesetting of footnotes. If you include the line:
\usepackage[bottom]{footmisc}
in latex preamble you get the desired footnotes behavior.

Thursday, January 03, 2008

Bit Operations: find first zero bit

If anybody cares here is an algorithm to find the first zero bit in a number:
  1. Invert the number
  2. Compute the two's complement of the inverted number
  3. AND the results of (1) and (2)
  4. Find the position by computing the binary logarithm of (3)
e.x.
For the number 10110111
  1. 01001000
  2. 10111000
  3. 01001000 AND 10111000 = 00001000
  4. log2(00001000) = 3
But in a x86 processor environment there is a more simple way to do this since Intel provides a specific assembly instruction for this purpose called bsfl. This instruction return the position (index) of the least significant bit set to 1 in a 32-bit word. By using inline assembly, someone can easily create a function that finds the first zero bit by inverting a number and feeding it to this instruction. For 8-bit numbers, the code for this in gcc would look like this:
/*
* find the position of the first 0 in a 8-bit array
*/
inline unsigned short find_first_zero(uint8_t bit_array)
{
unsigned pos = 0;

__asm__("bsfl %1,%0\n\t"
"jne 1f\n\t"
"movl $32, %0\n"
"1:"
: "=r" (pos)
: "r" (~(bit_array)));

if (pos > 7)
return 8;

return (unsigned short) pos;
}