00001
00038 #include "bitarray.h"
00039
00040 #include <string.h>
00041
00042 // De Bruijn constant coefficents.
00043 static const uint8_t DeBruijn_coefficents[32] =
00044 {
00045   0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
00046   31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
00047 };
00048
00055 int bitarray_firstSetBit(BitArray *bitx)
00056 {
00057     ASSERT(bitx);
00058
00059     uint8_t *b = bitx->array;
00060     size_t bytes = bitx->size;
00061     int curr = 0;
00062
00063     while (bytes)
00064     {
00065         uint32_t data = 0;
00066         size_t len = MIN(bytes, (size_t)4);
00067         memcpy(&data, b, len);
00068
00069         if (data)
00070             return (DeBruijn_coefficents[((uint32_t)((data & -data) * 0x077CB531U)) >> 27] + curr);
00071
00072         bytes -= 4;
00073         curr += 32;
00074         b += len;
00075     }
00076
00077     return -1;
00078 }