fixes on bitstring.h

Luis Useche useche at gmail.com
Wed Apr 13 19:28:40 PDT 2011


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; \
 			} \
 		} \
 	} \





More information about the Submit mailing list