diff options
Diffstat (limited to 'fs/hfs/bitops.c')
-rw-r--r-- | fs/hfs/bitops.c | 124 |
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; + } +} |