[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

**To**:**"Robert Elz" <kre%munnari.oz.au@localhost>****Subject**:**Re: 64-bit masks****From**:**Sad Clouds <cryintothebluesky%googlemail.com@localhost>**- Date: Sun, 29 Nov 2009 23:42:45 -0000

On Fri, 27 Nov 2009 16:00:43 -0000, Robert Elz <kre%munnari.oz.au@localhost> wrote:

Whether this is really an appropriate algorithm depends on just what youneed to know all the free objects for - if you just want to find thefirstfree object, there are easier (faster) ways, but if you really need to find all of them, this might be OK.

1. On different platforms integer could be 16, 32, or even 64-bits wide

It also needs to be portable to at least BSD, Linux and Solaris.

/opt/SUNWspro/bin/cc -xO3 find_bit.c This is my function: rom@ultra10 ptime ./a.out real 0.561 user 0.542 sys 0.009 This is Solaris ffs(): rom@ultra10 ptime ./a.out real 0.680 user 0.626 sys 0.009 I suppose it's a good start.

/* ffu_bit - find first unset bit Return: index of first unset bit (0 to 63) -1 if there were no unset bits Pre: bit_str is a 64-bit unsigned integer Post: none The function uses binary search algorithm to find 8-bit byte inside a 64-bit integer, which contains an unset bit. The function divides 64-bit integer into two 32-bit halves. It then divides each 32-bit half into two 16-bit halves. Each of the 16-bit halves is then divided into two 8-bit halves. aaaaaaaaaaaaaaaaaaaaaaa -> 1 64-bit bbbbbbbbbbb bbbbbbbbbbb -> 2 32-bit segments ccccc ccccc ccccc ccccc -> 4 16-bit segments dd dd dd dd dd dd dd dd -> 8 8-bit segments ----------------------- 7 6 5 4 3 2 1 0 -> 8-bit index */ int ffu_bit(uint64_t bit_str) { int index, i; uint64_t tmp; const uint64_t mask64 = UINT64_C(0xffffffffffffffff); const uint64_t mask32 = UINT64_C(0x00000000ffffffff); const uint64_t mask16 = UINT64_C(0x000000000000ffff); const uint64_t mask8 = UINT64_C(0x00000000000000ff); /* If all bits are 1, return -1 */ if(bit_str == mask64) return -1; /* If bits 0-31 are not all 1s */ if((bit_str & mask32) != mask32) { /* If bits 0-15 are not all 1s */ if((bit_str & mask16) != mask16) { /* If bits 0-7 are not all 1s */ if((bit_str & mask8) != mask8) index = 0; else /* bits 8-15 */ index = 1; } else /* Must be bits 16-31 */ { /* If bits 16-23 are not all 1s */ if(((bit_str >> 16) & mask8) != mask8) index = 2; else /* bits 24-32 */ index = 3; } } /* Must be bits 32-63 */ else { /* If bits 32-47 are not all 1s */ if(((bit_str >> 32) & mask16) != mask16) { /* If bits 32-39 are not all 1s */ if(((bit_str >> 32) & mask8) != mask8) index = 4; else /* bits 40-47 */ index = 5; } else /* Must be bits 48-63 */ { /* If bits 48-55 are not all 1s */ if(((bit_str >> 48) & mask8) != mask8) index = 6; else /* bits 56-63 */ index = 7; } } index *= 8; /* scale index by 8-bits in a byte */ /* Shift the 8-bit byte containing first unset bit to the far right so we can find out the exact bit index within the byte. */ tmp = bit_str >> index; for(i = 0; i < 8; i++) { if(((tmp >> i) & 0x1) == 0) break; /* found first bit set to 0 */ } index += i; return index; }

**Follow-Ups**:**Re: 64-bit masks***From:*Steven Bellovin

**Re: 64-bit masks***From:*Christos Zoulas

**Re: 64-bit masks***From:*der Mouse

**References**:**64-bit masks***From:*Sad Clouds

**Re: 64-bit masks***From:*Robert Elz

- Prev by Date:
**Re: 64-bit masks** - Next by Date:
**Re: 64-bit masks** - Previous by Thread:
**Re: 64-bit masks** - Next by Thread:
**Re: 64-bit masks** - Indexes: