1 files changed, 124 insertions, 0 deletions
diff --git a/fs/hfs/bitops.c b/fs/hfs/bitops.c
new file mode 100644
index 000000000..1d3a113bb
--- /dev/null
+++ b/fs/hfs/bitops.c
@@ -0,0 +1,124 @@
+/*
+ * linux/fs/hfs/bitops.c
+ *
+ * Copyright (C) 1996  Paul H. Hargrove
+ * This file may be distributed under the terms of the GNU Public License.
+ *
+ * This file contains functions to handle bitmaps in "left-to-right"
+ * bit-order such that the MSB of a 32-bit big-endian word is bit 0.
+ * (This corresponds to bit 7 of a 32-bit little-endian word.)
+ *
+ * I have tested and confirmed that the results are identical on the
+ * Intel x86, PowerPC and DEC Alpha processors.
+ *
+ * "XXX" in a comment is a note to myself to consider changing something.
+ */
+
+#include "hfs.h"
+
+/*================ Global functions ================*/
+
+/*
+ * hfs_find_zero_bit()
+ *
+ * Description:
+ *  Given a block of memory, its length in bits, and a starting bit number,
+ *  determine the number of the first zero bits (in left-to-right ordering)
+ *  in that range.
+ *
+ *  Returns >= 'size' if no zero bits are found in the range.
+ *
+ *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
+ *  may read beyond the 'size'th bit.
+ */
+hfs_u32 hfs_find_zero_bit(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset)
+{
+	const hfs_u32 *end   = start + ((size + 31) >> 5);
+	const hfs_u32 *curr  = start + (offset >> 5);
+	int bit = offset % 32;
+	
+	if (offset < size) {
+		/* scan the first partial hfs_u32 for zero bits */
+		if (bit != 0) {
+			do {
+				if (!hfs_test_bit(bit, curr)) {
+					goto done;
+				}
+				++bit;
+			} while (bit < 32);
+			bit = 0;
+			++curr;
+		}
+	
+		/* scan complete hfs_u32s for the first zero bit */
+		while (curr < end) {
+			if (*curr == ~((hfs_u32)0)) {
+				++curr;
+			} else {
+				while (hfs_test_bit(bit, curr)) {
+					++bit;
+				}
+				break;
+			}
+		}
+
+done:
+		bit |= (curr - start) << 5;
+		return bit;
+	} else {
+		return size;
+	}
+}
+
+/*
+ * hfs_count_zero_bits()
+ *
+ * Description:
+ *  Given a block of memory, its length in bits, and a starting bit number,
+ *  determine the number of consecutive zero bits (in left-to-right ordering)
+ *  in that range.
+ *
+ *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
+ *  may read beyond the 'size'th bit.
+ */
+hfs_u32 hfs_count_zero_bits(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset)
+{
+	const hfs_u32 *end   = start + ((size + 31) >> 5);
+	const hfs_u32 *curr  = start + (offset >> 5);
+	int bit = offset % 32;
+
+	if (offset < size) {
+		/* scan the first partial hfs_u32 for one bits */
+		if (bit != 0) {
+			do {
+				if (hfs_test_bit(bit, curr)) {
+					goto done;
+				}
+				++bit;
+			} while (bit < 32);
+			bit = 0;
+			++curr;
+		}
+	
+		/* scan complete hfs_u32s for the first one bit */
+		while (curr < end) {
+			if (*curr == ((hfs_u32)0)) {
+				++curr;
+			} else {
+				while (!hfs_test_bit(bit, curr)) {
+					++bit;
+				}
+				break;
+			}
+		}
+
+done:
+		bit |= (curr - start) << 5;
+		if (bit > size) {
+			bit = size;
+		}
+		return bit - offset;
+	} else {
+		return 0;
+	}
+}