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 > >> >> ĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄ[EMAIL PROTECTED] > >> >> ĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄĄ2000-02-15 > >> >> > >> > >> = = = = = = = = = = = = = = = = = = = = > >> > >> > >> best regards! > >> > >> Huang Xin Gang > >> [EMAIL PROTECTED] > >> 2002-07-04 > >> > > = = = = = = = = = = = = = = = = = = = = > > > best regards! > > Huang Xin Gang > [EMAIL PROTECTED] > 2000-02-15 > _______________________________________________ LARTC mailing list / [EMAIL PROTECTED] http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/