XZ decompressor: Fix decoding of empty LZMA2 streams
[linux-2.6.git] / lib / find_next_bit.c
1 /* find_next_bit.c: fallback find next bit implementation
2  *
3  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4  * Written by David Howells (dhowells@redhat.com)
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version
9  * 2 of the License, or (at your option) any later version.
10  */
11
12 #include <linux/bitops.h>
13 #include <linux/module.h>
14 #include <asm/types.h>
15 #include <asm/byteorder.h>
16
17 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
18
19 #ifdef CONFIG_GENERIC_FIND_NEXT_BIT
20 /*
21  * Find the next set bit in a memory region.
22  */
23 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
24                             unsigned long offset)
25 {
26         const unsigned long *p = addr + BITOP_WORD(offset);
27         unsigned long result = offset & ~(BITS_PER_LONG-1);
28         unsigned long tmp;
29
30         if (offset >= size)
31                 return size;
32         size -= result;
33         offset %= BITS_PER_LONG;
34         if (offset) {
35                 tmp = *(p++);
36                 tmp &= (~0UL << offset);
37                 if (size < BITS_PER_LONG)
38                         goto found_first;
39                 if (tmp)
40                         goto found_middle;
41                 size -= BITS_PER_LONG;
42                 result += BITS_PER_LONG;
43         }
44         while (size & ~(BITS_PER_LONG-1)) {
45                 if ((tmp = *(p++)))
46                         goto found_middle;
47                 result += BITS_PER_LONG;
48                 size -= BITS_PER_LONG;
49         }
50         if (!size)
51                 return result;
52         tmp = *p;
53
54 found_first:
55         tmp &= (~0UL >> (BITS_PER_LONG - size));
56         if (tmp == 0UL)         /* Are any bits set? */
57                 return result + size;   /* Nope. */
58 found_middle:
59         return result + __ffs(tmp);
60 }
61 EXPORT_SYMBOL(find_next_bit);
62
63 /*
64  * This implementation of find_{first,next}_zero_bit was stolen from
65  * Linus' asm-alpha/bitops.h.
66  */
67 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
68                                  unsigned long offset)
69 {
70         const unsigned long *p = addr + BITOP_WORD(offset);
71         unsigned long result = offset & ~(BITS_PER_LONG-1);
72         unsigned long tmp;
73
74         if (offset >= size)
75                 return size;
76         size -= result;
77         offset %= BITS_PER_LONG;
78         if (offset) {
79                 tmp = *(p++);
80                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
81                 if (size < BITS_PER_LONG)
82                         goto found_first;
83                 if (~tmp)
84                         goto found_middle;
85                 size -= BITS_PER_LONG;
86                 result += BITS_PER_LONG;
87         }
88         while (size & ~(BITS_PER_LONG-1)) {
89                 if (~(tmp = *(p++)))
90                         goto found_middle;
91                 result += BITS_PER_LONG;
92                 size -= BITS_PER_LONG;
93         }
94         if (!size)
95                 return result;
96         tmp = *p;
97
98 found_first:
99         tmp |= ~0UL << size;
100         if (tmp == ~0UL)        /* Are any bits zero? */
101                 return result + size;   /* Nope. */
102 found_middle:
103         return result + ffz(tmp);
104 }
105 EXPORT_SYMBOL(find_next_zero_bit);
106 #endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
107
108 #ifdef CONFIG_GENERIC_FIND_FIRST_BIT
109 /*
110  * Find the first set bit in a memory region.
111  */
112 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
113 {
114         const unsigned long *p = addr;
115         unsigned long result = 0;
116         unsigned long tmp;
117
118         while (size & ~(BITS_PER_LONG-1)) {
119                 if ((tmp = *(p++)))
120                         goto found;
121                 result += BITS_PER_LONG;
122                 size -= BITS_PER_LONG;
123         }
124         if (!size)
125                 return result;
126
127         tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
128         if (tmp == 0UL)         /* Are any bits set? */
129                 return result + size;   /* Nope. */
130 found:
131         return result + __ffs(tmp);
132 }
133 EXPORT_SYMBOL(find_first_bit);
134
135 /*
136  * Find the first cleared bit in a memory region.
137  */
138 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
139 {
140         const unsigned long *p = addr;
141         unsigned long result = 0;
142         unsigned long tmp;
143
144         while (size & ~(BITS_PER_LONG-1)) {
145                 if (~(tmp = *(p++)))
146                         goto found;
147                 result += BITS_PER_LONG;
148                 size -= BITS_PER_LONG;
149         }
150         if (!size)
151                 return result;
152
153         tmp = (*p) | (~0UL << size);
154         if (tmp == ~0UL)        /* Are any bits zero? */
155                 return result + size;   /* Nope. */
156 found:
157         return result + ffz(tmp);
158 }
159 EXPORT_SYMBOL(find_first_zero_bit);
160 #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
161
162 #ifdef __BIG_ENDIAN
163 #ifdef CONFIG_GENERIC_FIND_BIT_LE
164
165 /* include/linux/byteorder does not support "unsigned long" type */
166 static inline unsigned long ext2_swabp(const unsigned long * x)
167 {
168 #if BITS_PER_LONG == 64
169         return (unsigned long) __swab64p((u64 *) x);
170 #elif BITS_PER_LONG == 32
171         return (unsigned long) __swab32p((u32 *) x);
172 #else
173 #error BITS_PER_LONG not defined
174 #endif
175 }
176
177 /* include/linux/byteorder doesn't support "unsigned long" type */
178 static inline unsigned long ext2_swab(const unsigned long y)
179 {
180 #if BITS_PER_LONG == 64
181         return (unsigned long) __swab64((u64) y);
182 #elif BITS_PER_LONG == 32
183         return (unsigned long) __swab32((u32) y);
184 #else
185 #error BITS_PER_LONG not defined
186 #endif
187 }
188
189 unsigned long find_next_zero_bit_le(const void *addr, unsigned
190                 long size, unsigned long offset)
191 {
192         const unsigned long *p = addr;
193         unsigned long result = offset & ~(BITS_PER_LONG - 1);
194         unsigned long tmp;
195
196         if (offset >= size)
197                 return size;
198         p += BITOP_WORD(offset);
199         size -= result;
200         offset &= (BITS_PER_LONG - 1UL);
201         if (offset) {
202                 tmp = ext2_swabp(p++);
203                 tmp |= (~0UL >> (BITS_PER_LONG - offset));
204                 if (size < BITS_PER_LONG)
205                         goto found_first;
206                 if (~tmp)
207                         goto found_middle;
208                 size -= BITS_PER_LONG;
209                 result += BITS_PER_LONG;
210         }
211
212         while (size & ~(BITS_PER_LONG - 1)) {
213                 if (~(tmp = *(p++)))
214                         goto found_middle_swap;
215                 result += BITS_PER_LONG;
216                 size -= BITS_PER_LONG;
217         }
218         if (!size)
219                 return result;
220         tmp = ext2_swabp(p);
221 found_first:
222         tmp |= ~0UL << size;
223         if (tmp == ~0UL)        /* Are any bits zero? */
224                 return result + size; /* Nope. Skip ffz */
225 found_middle:
226         return result + ffz(tmp);
227
228 found_middle_swap:
229         return result + ffz(ext2_swab(tmp));
230 }
231 EXPORT_SYMBOL(find_next_zero_bit_le);
232
233 unsigned long find_next_bit_le(const void *addr, unsigned
234                 long size, unsigned long offset)
235 {
236         const unsigned long *p = addr;
237         unsigned long result = offset & ~(BITS_PER_LONG - 1);
238         unsigned long tmp;
239
240         if (offset >= size)
241                 return size;
242         p += BITOP_WORD(offset);
243         size -= result;
244         offset &= (BITS_PER_LONG - 1UL);
245         if (offset) {
246                 tmp = ext2_swabp(p++);
247                 tmp &= (~0UL << offset);
248                 if (size < BITS_PER_LONG)
249                         goto found_first;
250                 if (tmp)
251                         goto found_middle;
252                 size -= BITS_PER_LONG;
253                 result += BITS_PER_LONG;
254         }
255
256         while (size & ~(BITS_PER_LONG - 1)) {
257                 tmp = *(p++);
258                 if (tmp)
259                         goto found_middle_swap;
260                 result += BITS_PER_LONG;
261                 size -= BITS_PER_LONG;
262         }
263         if (!size)
264                 return result;
265         tmp = ext2_swabp(p);
266 found_first:
267         tmp &= (~0UL >> (BITS_PER_LONG - size));
268         if (tmp == 0UL)         /* Are any bits set? */
269                 return result + size; /* Nope. */
270 found_middle:
271         return result + __ffs(tmp);
272
273 found_middle_swap:
274         return result + __ffs(ext2_swab(tmp));
275 }
276 EXPORT_SYMBOL(find_next_bit_le);
277
278 #endif /* CONFIG_GENERIC_FIND_BIT_LE */
279 #endif /* __BIG_ENDIAN */