Bug #2049

fixes on bitstring.h

Added by useche over 3 years ago. Updated over 3 years ago.

Status:ClosedStart date:
Priority:NormalDue date:
Assignee:-% Done:

0%

Category:-
Target version:-

Description

Hi Guys,

I found some problems in your implementation of bitstring.h. First,
the bit_nsearch was trying to find a cluster of zeros longer than
required. It also miss a break making the loop go through the entire
bitstring.
I also found that the implementation of fls was incorrect. The patch
also includes a fix where I replace the old fls with a modified
version of ffs which also makes the code more consistent.

Below, I am attaching the patch.

Thanks,
Luis.

--- /home/lmarmol/Projects/SoftPM/out-of-core/include/bitstring.h 2011-04-08
12:01:00.992644001 -0400
+++ bitstring.h 2011-04-13 17:08:56.196957002 -0400
@@ -153,34 +153,23 @@
*(value) = _value; \
} while (0)

-#define _fls(mask, value) do { \
- int _fmask = (mask); \
- int *_value = (value); \
- int _bit = 0; \
- if (_fmask == 0) { \
- *(_value) = 0; \
- break; \
- } \
- for (_bit = 1; _fmask != 1; _bit++) \
- _fmask = (unsigned char) _fmask >> 1; \
- *(_value) = _bit; \
-} while (0)
-
/* find last bit set in name */
-#define bit_fls(name, nbits, value) do { \
+#define bit_fls(name, nbits, value) do { \
bitstr_t *_name = (name); \
- int _nbits = (nbits); \
- int _byte = _bit_byte(_nbits - 1); \
- int *_value = (value); \
- int _mask = 0;\
+ int _byte, _nbits = (nbits); \
+ int _startbyte = _bit_byte(_nbits - 1), _value = -1; \
if (_nbits > 0) \
- for (; _byte >= 0; _byte--) { \
- if (!_name[_byte]) \
- continue; \
- _fls(_name[_byte], &_mask); \
- break; \
- } \
- *(_value) = (_mask * (_byte + 1)) - 1; \
+ for (_byte = _startbyte; _byte >= 0; --_byte) \
+ if (_name[_byte]) { \
+ bitstr_t _lb; \
+ _value = _byte << 3; \
+ for (_lb = _name[_byte]; _lb != 0x1; \
+ ++_value, _lb >>= 1); \
+ break; \
+ } \
+ if (_value >= nbits) \
+ _value = -1; \
+ *(value) = _value; \
} while (0)

/* find clear range of length len */
@@ -203,7 +192,7 @@
continue; \
} \
} else { \
- if (_tmplen >= 0) { \
+ if (_tmplen > 0) { \
if (bit_test((_name), _bit) == 0) { \
_tmplen--; \
} else { \
@@ -213,6 +202,7 @@
} \
} else { \
*(_value) = _bit0; \
+ break; \
} \
} \
} \

History

#1 Updated by vsrinivas over 3 years ago

Your changes are correct; thanks! Committed as
74851543a21675a1410e368afc1c1c4238e10d45.

Also available in: Atom PDF