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