speed up on find_first_bit for i386 (let compiler do the work)
Quoted 13 lines
static inline int
new_find_first_bit(const unsigned long *b, unsigned size){ int x = 0; do { unsigned long v = *b++; if (v) return __ffs(v) + x; if (x >= size) break; x += 32; } while (1); return x; }
Wait a minute... suppose that size == 32 and the bitmap is one word of all zeros. Dynamic execution will overflow the buffer:
int x = 0;
unsigned long v = *b++; /* Zero */
if (v) /* False, v == 0 */
if (x >= size) /* False, 0 < 32 */
x += 32;
} while (1);
unsigned long v = *b++; /* Buffer overflow */
if (v) /* Random value, suppose non-zero */
return __ffs(v) + x; /* >= 32 */
That should be:
static inline int new_find_first_bit(const unsigned long *b, unsigned size)
int x = 0;
do {
unsigned long v = *b++;
if (v)
return __ffs(v) + x;
} while ((x += 32) < size);
return size;
}Note that we assume that the trailing long is padded with zeros.
In truth, it should probably be either
static inline unsigned new_find_first_bit(u32 const *b, unsigned size)
int x = 0;
do {
u32 v = *b++;
if (v)
return __ffs(v) + x;
} while ((x += 32) < size);
return size;
}or
static inline unsigned new_find_first_bit(unsigned long const *b, unsigned size)
unsigned x = 0;
do {
unsigned long v = *b++;
if (v)
return __ffs(v) + x;
} while ((x += CHAR_BIT * sizeof *b) < size);
return size;
}Do we actually store bitmaps on 64-bit machines with 32 significant bits per ulong?