File: /usr/src/linux/fs/hfs/bitops.c

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      */
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      */
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