[svlug] find_first_bit()

[Larry Colen]

Thanks a bunch, my copy of bitops.h was in assembly, and while I did
Z80 for years, and have done a bunch of other assemblers, I haven't
done x86.

This is a lot easier to read.

On Thu, May 17, 2007 at 09:52:45PM -0700, Tim Flagg wrote:
# >in the kernel bitops, like find_first_bit(), is size in bits, bytes or
# >words?
# >
# >static inline int
# >find_first_bit(const unsigned long * addr, unsigned int size)
# 
# size is in bits.  See include/asm-i386/bitops.h (with some
# comments I added):
# 
#     ...
#     321 /**
#     322  * find_first_bit - find the first set bit in a memory region
#     323  * @addr: The address to start the search at
#     324  * @size: The maximum size to search
#     325  *
#     326  * Returns the bit-number of the first set bit, not the number of 
#     the by        te
#     327  * containing a bit.
#     328  */
#     329 static inline unsigned find_first_bit(const unsigned long *addr, 
#     unsigne        d size)
#     330 {
#     331     unsigned x = 0;
#     332
#     333     while (x < size) {  // While we have more bits to check
#     334         unsigned long val = *addr++;    // Check next 4 bytes.
#     335         if (val)          // Any of these 4 bytes have a 1?
#     336             return __ffs(val) + x;  // Return bit # of the 1
# --> 337         x += (sizeof(*addr)<<3);  // Increment by 4 words * 8 bits 
# each
#     338     }
#     339     return x;
#     340 }
#     ...
# 
# Additional notes:
#     Line 337:  At this point, we have checked the next 32 bits
#     (for the i386 architecture an "unsigned long" is 4 bytes).  and they
#     didn't have any 1's
# 
#     sizeof(*addr) is the number of BYTES we look at in each loop.
#     The "<< 3" multiplies by 8 (since there are 8 bits in a byte).
# 
#     So another way to look at line 337:
#         x += 4 * 8;  // We've checked 4 more bytes * 8 bits each
# 
#     So line 333 is comparing "x" (the number of bits we've already
#     checked) with "size" (the number of bits we are supposed to check).
# 
# Tim

-- 
Spinoff tech is all well and good, but we still don't have 100 MPG passenger 
vehicles.  We have 5 MPG Hummer road hogs for guys who can't stay in their 
lanes on our Eisenhower administration sponsored(!) freeways.  -Pat Steppic

Larry Colen             lrc at red4est.com            http://www.red4est.com/lrc