Ok, I cc it to lartc as it can be of general interest.
ffz is Find First Zero. So that it is index of first LSB
zero. In ffs indexes starts with 1 in ffz with 0.
It can be used to do some action for each zero (or one)
bit in integer.
The simplest code do do f() for each zero bit in x is:
unsigned int x,m=1,i=0;
for(;m < 0x80000000; m <<= 1,i++)
if ((m & x) == 0) f(i)
The code above will take about 32*4 x86 instructions
(and,jz,shl,jnc). There is possibility to write this in
paralel fashion but GCC will not do it. In direct implementation
of code there is little ILP (only jz+shl) so that is will
take at least 128 CPU cycles (not counting f).
When there is not many zeros in x the code above will
be ineffecient. Let''s rewrite it:
while (x != 0xffffffff) {
int i = ffz(x);
f(i);
x |= (1<<i);
}
Whis will take 7 instructions (cmp,jz,ffz,mov,shl,or,jmp)
where mov, shl and or can be interleaved with f() and thus
they latency can be hidden. But even i 7 inst case we have
complexity n*7 where n is zero-population of x. Because
there is often one or two zero bits in x we have complexity
at most 14 cycles. Compare it with 128.
devik
On Tue, 15 Feb 2000, Huang Xin Gang wrote:
> devik,hello!
>
> I read the man page of ffs() and looked ffz() in Linux kernel code, and
then I queried the assembly code
>
> "asm ("cntlzw %0,%1" : "=r" (lz) : "r"
(x));"
>
> in the __ilog2() in Linux kernel codethrough google.com.
>
> I think that ffz(int value) return the number of consecutive zero bit in
the value from leftmost.
>
> Is my comprehend right?
>
> But could you explain why ffz() is used in htb_dequeue()?
>
> I think I can understand the same usage in CBQ code with your help.
>
> Thanks.
>
> ======= 2002-07-04 10:52:00 you wrote:======>
> >find first zero. See man ffs - ffz is negated one with
> >a bit different return value.
> >I remember I was thinking about it when I first read CBQ
> >source. I remember I''ve figured its function in hour or
> >so by reading headers ...
> >devik
> >
> >On Thu, 4 Jul 2002, Huang Xin Gang wrote:
> >
> >> devik,hello!
> >>
> >> Thanks for your reply before.
> >> Now I have another question for you:
> >> I found a function ffz() used in your code of HTB.
> >> I want to know why you use this function.
> >>
> >> I will be appreciate if you reply me.
> >>
> >> Thanks.
> >>
> >> ======= 2002-07-02 12:00:00 you wrote:======> >>
> >> >you probably should grep in linux/include. Sorry
> >> >but finding definition of function is not so hard
> >> >task, is it ?
> >> >They translate to GCC3 branching hints.
> >> >devik
> >> >
> >> >On Tue, 15 Feb 2000, Huang Xin Gang wrote:
> >> >
> >> >> MartinŁŹhelloŁĄ
> >> >>
> >> >> Could you tell me the meaning of these two function?
> >> >> and what form can I change these functions into C
langague?
> >> >>
> >> >> Thanks a lot!
> >> >>
> >> >> ĄĄĄĄĄĄbest regards!
> >> >>
> >> >>
> >> >> ĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄHuang Xin Gang
> >> >>
ĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄhxgang@csnet4.cs.tsinghua.edu.cn
> >> >> ĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄ2000-02-15
> >> >>
> >>
> >> = = = = = = = = = = = = = = = = = = = > >>
> >>
> >> best regards!
> >>
> >> Huang Xin Gang
> >> hxgang@csnet4.cs.tsinghua.edu.cn
> >> 2002-07-04
> >>
>
> = = = = = = = = = = = = = = = = = = = >
>
> best regards!
>
> Huang Xin Gang
> hxgang@csnet4.cs.tsinghua.edu.cn
> 2000-02-15
>