Skip to contentSkip to conversation

speed up on find_first_bit for i386 (let compiler do the work)

PATCH [email protected] 1 participant 1 message Aug 1, 2005

lore
Share & tools
lore
#0 lore raw
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?