1 2 3#include "hfs.h" 4 5/*================ Global functions ================*/ 6 7/* 8 * hfs_find_zero_bit() 9 * 10 * Description: 11 * Given a block of memory, its length in bits, and a starting bit number, 12 * determine the number of the first zero bits (in left-to-right ordering) 13 * in that range. 14 * 15 * Returns >= 'size' if no zero bits are found in the range. 16 * 17 * Accesses memory in 32-bit aligned chunks of 32-bits and thus 18 * may read beyond the 'size'th bit. 19 */ 20hfs_u32 hfs_find_zero_bit(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset) 21{ 22 const hfs_u32 *end = start + ((size + 31) >> 5); 23 const hfs_u32 *curr = start + (offset >> 5); 24 int bit = offset % 32; 25 26 if (offset < size) { 27 /* scan the first partial hfs_u32 for zero bits */ 28 if (bit != 0) { 29 do { 30 if (!hfs_test_bit(bit, curr)) { 31 goto done; 32 } 33 ++bit; 34 } while (bit < 32); 35 bit = 0; 36 ++curr; 37 } 38 39 /* scan complete hfs_u32s for the first zero bit */ 40 while (curr < end) { 41 if (*curr == ~((hfs_u32)0)) { 42 ++curr; 43 } else { 44 while (hfs_test_bit(bit, curr)) { 45 ++bit; 46 } 47 break; 48 } 49 } 50 51done: 52 bit |= (curr - start) << 5; 53 return bit; 54 } else { 55 return size; 56 } 57} 58 59/* 60 * hfs_count_zero_bits() 61 * 62 * Description: 63 * Given a block of memory, its length in bits, and a starting bit number, 64 * determine the number of consecutive zero bits (in left-to-right ordering) 65 * in that range. 66 * 67 * Accesses memory in 32-bit aligned chunks of 32-bits and thus 68 * may read beyond the 'size'th bit. 69 */ 70hfs_u32 hfs_count_zero_bits(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset) 71{ 72 const hfs_u32 *end = start + ((size + 31) >> 5); 73 const hfs_u32 *curr = start + (offset >> 5); 74 int bit = offset % 32; 75 76 if (offset < size) { 77 /* scan the first partial hfs_u32 for one bits */ 78 if (bit != 0) { 79 do { 80 if (hfs_test_bit(bit, curr)) { 81 goto done; 82 } 83 ++bit; 84 } while (bit < 32); 85 bit = 0; 86 ++curr; 87 } 88 89 /* scan complete hfs_u32s for the first one bit */ 90 while (curr < end) { 91 if (*curr == ((hfs_u32)0)) { 92 ++curr; 93 } else { 94 while (!hfs_test_bit(bit, curr)) { 95 ++bit; 96 } 97 break; 98 } 99 } 100 101done: 102 bit |= (curr - start) << 5; 103 if (bit > size) { 104 bit = size; 105 } 106 return bit - offset; 107 } else { 108 return 0; 109 } 110} 111