1 /*
2 * linux/fs/hfs/bitops.c
3 *
4 * Copyright (C) 1996 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU General Public License.
6 *
7 * This file contains functions to handle bitmaps in "left-to-right"
8 * bit-order such that the MSB of a 32-bit big-endian word is bit 0.
9 * (This corresponds to bit 7 of a 32-bit little-endian word.)
10 *
11 * I have tested and confirmed that the results are identical on the
12 * Intel x86, PowerPC and DEC Alpha processors.
13 *
14 * "XXX" in a comment is a note to myself to consider changing something.
15 */
16
17 #include "hfs.h"
18
19 /*================ Global functions ================*/
20
21 /*
22 * hfs_find_zero_bit()
23 *
24 * Description:
25 * Given a block of memory, its length in bits, and a starting bit number,
26 * determine the number of the first zero bits (in left-to-right ordering)
27 * in that range.
28 *
29 * Returns >= 'size' if no zero bits are found in the range.
30 *
31 * Accesses memory in 32-bit aligned chunks of 32-bits and thus
32 * may read beyond the 'size'th bit.
33 */
hfs_find_zero_bit(const hfs_u32 * start,hfs_u32 size,hfs_u32 offset)34 hfs_u32 hfs_find_zero_bit(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset)
35 {
36 const hfs_u32 *end = start + ((size + 31) >> 5);
37 const hfs_u32 *curr = start + (offset >> 5);
38 int bit = offset % 32;
39
40 if (offset < size) {
41 /* scan the first partial hfs_u32 for zero bits */
42 if (bit != 0) {
43 do {
44 if (!hfs_test_bit(bit, curr)) {
45 goto done;
46 }
47 ++bit;
48 } while (bit < 32);
49 bit = 0;
50 ++curr;
51 }
52
53 /* scan complete hfs_u32s for the first zero bit */
54 while (curr < end) {
55 if (*curr == ~((hfs_u32)0)) {
56 ++curr;
57 } else {
58 while (hfs_test_bit(bit, curr)) {
59 ++bit;
60 }
61 break;
62 }
63 }
64
65 done:
66 bit |= (curr - start) << 5;
67 return bit;
68 } else {
69 return size;
70 }
71 }
72
73 /*
74 * hfs_count_zero_bits()
75 *
76 * Description:
77 * Given a block of memory, its length in bits, and a starting bit number,
78 * determine the number of consecutive zero bits (in left-to-right ordering)
79 * in that range.
80 *
81 * Accesses memory in 32-bit aligned chunks of 32-bits and thus
82 * may read beyond the 'size'th bit.
83 */
hfs_count_zero_bits(const hfs_u32 * start,hfs_u32 size,hfs_u32 offset)84 hfs_u32 hfs_count_zero_bits(const hfs_u32 *start, hfs_u32 size, hfs_u32 offset)
85 {
86 const hfs_u32 *end = start + ((size + 31) >> 5);
87 const hfs_u32 *curr = start + (offset >> 5);
88 int bit = offset % 32;
89
90 if (offset < size) {
91 /* scan the first partial hfs_u32 for one bits */
92 if (bit != 0) {
93 do {
94 if (hfs_test_bit(bit, curr)) {
95 goto done;
96 }
97 ++bit;
98 } while (bit < 32);
99 bit = 0;
100 ++curr;
101 }
102
103 /* scan complete hfs_u32s for the first one bit */
104 while (curr < end) {
105 if (*curr == ((hfs_u32)0)) {
106 ++curr;
107 } else {
108 while (!hfs_test_bit(bit, curr)) {
109 ++bit;
110 }
111 break;
112 }
113 }
114
115 done:
116 bit |= (curr - start) << 5;
117 if (bit > size) {
118 bit = size;
119 }
120 return bit - offset;
121 } else {
122 return 0;
123 }
124 }
125