From 920f8ef668b03c65ca414bd6d53db314da920d1f Mon Sep 17 00:00:00 2001
From: Lai Jiangshan <laijs@cn.fujitsu.com>
Date: Fri, 14 Oct 2011 09:59:42 -0500
Subject: [PATCH] rculfhash: simplify get_count_order()

[ Edit by Mathieu Desnoyers:

- Updated comments.
- Quick benchmark on Intel(R) Atom(TM) CPU Z520   @ 1.33GHz:

get_count_order_ulong, from 0 to 100000000:

previous:  3.840s
new:       3.187s

- Test comparing bit-exactness for ranges near 0:

/*
 * fls: returns the position of the most significant bit.
 * Returns 0 if no bit is set, else returns the position of the most
 * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
 */
static inline
unsigned int fls_u32(uint32_t x)
{
	int r;

	asm("bsrl %1,%0\n\t"
	    "jnz 1f\n\t"
	    "movl $-1,%0\n\t"
	    "1:\n\t"
	    : "=r" (r) : "rm" (x));
	return r + 1;
}

static inline
unsigned int fls_u64(uint64_t x)
{
	long r;

	asm("bsrq %1,%0\n\t"
	    "jnz 1f\n\t"
	    "movq $-1,%0\n\t"
	    "1:\n\t"
	    : "=r" (r) : "rm" (x));
	return r + 1;
}

static __attribute__((unused))
unsigned int fls_u64(uint64_t x)
{
	unsigned int r = 64;

	if (!x)
		return 0;

	if (!(x & 0xFFFFFFFF00000000ULL)) {
		x <<= 32;
		r -= 32;
	}
	if (!(x & 0xFFFF000000000000ULL)) {
		x <<= 16;
		r -= 16;
	}
	if (!(x & 0xFF00000000000000ULL)) {
		x <<= 8;
		r -= 8;
	}
	if (!(x & 0xF000000000000000ULL)) {
		x <<= 4;
		r -= 4;
	}
	if (!(x & 0xC000000000000000ULL)) {
		x <<= 2;
		r -= 2;
	}
	if (!(x & 0x8000000000000000ULL)) {
		x <<= 1;
		r -= 1;
	}
	return r;
}

static __attribute__((unused))
unsigned int fls_u32(uint32_t x)
{
	unsigned int r = 32;

	if (!x)
		return 0;
	if (!(x & 0xFFFF0000U)) {
		x <<= 16;
		r -= 16;
	}
	if (!(x & 0xFF000000U)) {
		x <<= 8;
		r -= 8;
	}
	if (!(x & 0xF0000000U)) {
		x <<= 4;
		r -= 4;
	}
	if (!(x & 0xC0000000U)) {
		x <<= 2;
		r -= 2;
	}
	if (!(x & 0x80000000U)) {
		x <<= 1;
		r -= 1;
	}
	return r;
}

unsigned int fls_ulong(unsigned long x)
{
	return fls_u32(x);
	return fls_u64(x);
}

int get_count_order_u32(uint32_t x)
{
	int order;

	order = fls_u32(x) - 1;
	if (x & (x - 1))
		order++;
	return order;
}

int get_count_order_ulong(unsigned long x)
{
	int order;

	order = fls_ulong(x) - 1;
	if (x & (x - 1))
		order++;
	return order;
}

int test_get_count_order_u32(uint32_t x)
{
	if (!x)
		return -1;
	return fls_u32(x - 1);
}

/* find the minimum order that x <= (1UL << order) */
int test_get_count_order_ulong(unsigned long x)
{
	if (!x)
		return -1;
	return fls_ulong(x - 1);
}

int main(int argc, char **argv)
{
	unsigned long i;

	for (i = 0UL; i < 10000; i++) {
		if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
			printf("Error for %lu\n", i);
	}

	for (i = 4294967293UL; i != 0; i++) {
		if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
			printf("Error for %lu\n", i);
	}

	return 0;
}

]

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 rculfhash.c | 24 ++++++++++++++----------
 1 file changed, 14 insertions(+), 10 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index cf822fc..fe8beed 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -446,24 +446,28 @@ unsigned int fls_ulong(unsigned long x)
 #endif
 }
 
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
 int get_count_order_u32(uint32_t x)
 {
-	int order;
+	if (!x)
+		return -1;
 
-	order = fls_u32(x) - 1;
-	if (x & (x - 1))
-		order++;
-	return order;
+	return fls_u32(x - 1);
 }
 
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
 int get_count_order_ulong(unsigned long x)
 {
-	int order;
+	if (!x)
+		return -1;
 
-	order = fls_ulong(x) - 1;
-	if (x & (x - 1))
-		order++;
-	return order;
+	return fls_ulong(x - 1);
 }
 
 #ifdef POISON_FREE
-- 
2.34.1