* Lai Jiangshan ([email protected]) wrote: > Signed-off-by: Lai Jiangshan <[email protected]>
Merged with edit: commit 920f8ef668b03c65ca414bd6d53db314da920d1f Author: Lai Jiangshan <[email protected]> Date: Fri Oct 14 09:59:42 2011 -0500 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 <[email protected]> Signed-off-by: Mathieu Desnoyers <[email protected]> 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 > --- > rculfhash.c | 18 ++++++++---------- > 1 files changed, 8 insertions(+), 10 deletions(-) > > diff --git a/rculfhash.c b/rculfhash.c > index 7b880d7..eca3a4e 100644 > --- a/rculfhash.c > +++ b/rculfhash.c > @@ -445,24 +445,22 @@ unsigned int fls_ulong(unsigned long x) > #endif > } > > +/* find the minimum order that x <= (1UL << order) */ > 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); > } > > +/* find the minimum order that x <= (1UL << order) */ > 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 > -- > 1.7.4.4 > -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com _______________________________________________ ltt-dev mailing list [email protected] http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
