Merge master.kernel.org:/home/rmk/linux-2.6-arm
[linux-2.6.git] / include / asm-alpha / bitops.h
1 #ifndef _ALPHA_BITOPS_H
2 #define _ALPHA_BITOPS_H
3
4 #include <asm/compiler.h>
5
6 /*
7  * Copyright 1994, Linus Torvalds.
8  */
9
10 /*
11  * These have to be done with inline assembly: that way the bit-setting
12  * is guaranteed to be atomic. All bit operations return 0 if the bit
13  * was cleared before the operation and != 0 if it was not.
14  *
15  * To get proper branch prediction for the main line, we must branch
16  * forward to code at the end of this object's .text section, then
17  * branch back to restart the operation.
18  *
19  * bit 0 is the LSB of addr; bit 64 is the LSB of (addr+1).
20  */
21
22 static inline void
23 set_bit(unsigned long nr, volatile void * addr)
24 {
25         unsigned long temp;
26         int *m = ((int *) addr) + (nr >> 5);
27
28         __asm__ __volatile__(
29         "1:     ldl_l %0,%3\n"
30         "       bis %0,%2,%0\n"
31         "       stl_c %0,%1\n"
32         "       beq %0,2f\n"
33         ".subsection 2\n"
34         "2:     br 1b\n"
35         ".previous"
36         :"=&r" (temp), "=m" (*m)
37         :"Ir" (1UL << (nr & 31)), "m" (*m));
38 }
39
40 /*
41  * WARNING: non atomic version.
42  */
43 static inline void
44 __set_bit(unsigned long nr, volatile void * addr)
45 {
46         int *m = ((int *) addr) + (nr >> 5);
47
48         *m |= 1 << (nr & 31);
49 }
50
51 #define smp_mb__before_clear_bit()      smp_mb()
52 #define smp_mb__after_clear_bit()       smp_mb()
53
54 static inline void
55 clear_bit(unsigned long nr, volatile void * addr)
56 {
57         unsigned long temp;
58         int *m = ((int *) addr) + (nr >> 5);
59
60         __asm__ __volatile__(
61         "1:     ldl_l %0,%3\n"
62         "       bic %0,%2,%0\n"
63         "       stl_c %0,%1\n"
64         "       beq %0,2f\n"
65         ".subsection 2\n"
66         "2:     br 1b\n"
67         ".previous"
68         :"=&r" (temp), "=m" (*m)
69         :"Ir" (1UL << (nr & 31)), "m" (*m));
70 }
71
72 /*
73  * WARNING: non atomic version.
74  */
75 static __inline__ void
76 __clear_bit(unsigned long nr, volatile void * addr)
77 {
78         int *m = ((int *) addr) + (nr >> 5);
79
80         *m &= ~(1 << (nr & 31));
81 }
82
83 static inline void
84 change_bit(unsigned long nr, volatile void * addr)
85 {
86         unsigned long temp;
87         int *m = ((int *) addr) + (nr >> 5);
88
89         __asm__ __volatile__(
90         "1:     ldl_l %0,%3\n"
91         "       xor %0,%2,%0\n"
92         "       stl_c %0,%1\n"
93         "       beq %0,2f\n"
94         ".subsection 2\n"
95         "2:     br 1b\n"
96         ".previous"
97         :"=&r" (temp), "=m" (*m)
98         :"Ir" (1UL << (nr & 31)), "m" (*m));
99 }
100
101 /*
102  * WARNING: non atomic version.
103  */
104 static __inline__ void
105 __change_bit(unsigned long nr, volatile void * addr)
106 {
107         int *m = ((int *) addr) + (nr >> 5);
108
109         *m ^= 1 << (nr & 31);
110 }
111
112 static inline int
113 test_and_set_bit(unsigned long nr, volatile void *addr)
114 {
115         unsigned long oldbit;
116         unsigned long temp;
117         int *m = ((int *) addr) + (nr >> 5);
118
119         __asm__ __volatile__(
120         "1:     ldl_l %0,%4\n"
121         "       and %0,%3,%2\n"
122         "       bne %2,2f\n"
123         "       xor %0,%3,%0\n"
124         "       stl_c %0,%1\n"
125         "       beq %0,3f\n"
126         "2:\n"
127 #ifdef CONFIG_SMP
128         "       mb\n"
129 #endif
130         ".subsection 2\n"
131         "3:     br 1b\n"
132         ".previous"
133         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
134         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
135
136         return oldbit != 0;
137 }
138
139 /*
140  * WARNING: non atomic version.
141  */
142 static inline int
143 __test_and_set_bit(unsigned long nr, volatile void * addr)
144 {
145         unsigned long mask = 1 << (nr & 0x1f);
146         int *m = ((int *) addr) + (nr >> 5);
147         int old = *m;
148
149         *m = old | mask;
150         return (old & mask) != 0;
151 }
152
153 static inline int
154 test_and_clear_bit(unsigned long nr, volatile void * addr)
155 {
156         unsigned long oldbit;
157         unsigned long temp;
158         int *m = ((int *) addr) + (nr >> 5);
159
160         __asm__ __volatile__(
161         "1:     ldl_l %0,%4\n"
162         "       and %0,%3,%2\n"
163         "       beq %2,2f\n"
164         "       xor %0,%3,%0\n"
165         "       stl_c %0,%1\n"
166         "       beq %0,3f\n"
167         "2:\n"
168 #ifdef CONFIG_SMP
169         "       mb\n"
170 #endif
171         ".subsection 2\n"
172         "3:     br 1b\n"
173         ".previous"
174         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
175         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
176
177         return oldbit != 0;
178 }
179
180 /*
181  * WARNING: non atomic version.
182  */
183 static inline int
184 __test_and_clear_bit(unsigned long nr, volatile void * addr)
185 {
186         unsigned long mask = 1 << (nr & 0x1f);
187         int *m = ((int *) addr) + (nr >> 5);
188         int old = *m;
189
190         *m = old & ~mask;
191         return (old & mask) != 0;
192 }
193
194 static inline int
195 test_and_change_bit(unsigned long nr, volatile void * addr)
196 {
197         unsigned long oldbit;
198         unsigned long temp;
199         int *m = ((int *) addr) + (nr >> 5);
200
201         __asm__ __volatile__(
202         "1:     ldl_l %0,%4\n"
203         "       and %0,%3,%2\n"
204         "       xor %0,%3,%0\n"
205         "       stl_c %0,%1\n"
206         "       beq %0,3f\n"
207 #ifdef CONFIG_SMP
208         "       mb\n"
209 #endif
210         ".subsection 2\n"
211         "3:     br 1b\n"
212         ".previous"
213         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
214         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
215
216         return oldbit != 0;
217 }
218
219 /*
220  * WARNING: non atomic version.
221  */
222 static __inline__ int
223 __test_and_change_bit(unsigned long nr, volatile void * addr)
224 {
225         unsigned long mask = 1 << (nr & 0x1f);
226         int *m = ((int *) addr) + (nr >> 5);
227         int old = *m;
228
229         *m = old ^ mask;
230         return (old & mask) != 0;
231 }
232
233 static inline int
234 test_bit(int nr, const volatile void * addr)
235 {
236         return (1UL & (((const int *) addr)[nr >> 5] >> (nr & 31))) != 0UL;
237 }
238
239 /*
240  * ffz = Find First Zero in word. Undefined if no zero exists,
241  * so code should check against ~0UL first..
242  *
243  * Do a binary search on the bits.  Due to the nature of large
244  * constants on the alpha, it is worthwhile to split the search.
245  */
246 static inline unsigned long ffz_b(unsigned long x)
247 {
248         unsigned long sum, x1, x2, x4;
249
250         x = ~x & -~x;           /* set first 0 bit, clear others */
251         x1 = x & 0xAA;
252         x2 = x & 0xCC;
253         x4 = x & 0xF0;
254         sum = x2 ? 2 : 0;
255         sum += (x4 != 0) * 4;
256         sum += (x1 != 0);
257
258         return sum;
259 }
260
261 static inline unsigned long ffz(unsigned long word)
262 {
263 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
264         /* Whee.  EV67 can calculate it directly.  */
265         return __kernel_cttz(~word);
266 #else
267         unsigned long bits, qofs, bofs;
268
269         bits = __kernel_cmpbge(word, ~0UL);
270         qofs = ffz_b(bits);
271         bits = __kernel_extbl(word, qofs);
272         bofs = ffz_b(bits);
273
274         return qofs*8 + bofs;
275 #endif
276 }
277
278 /*
279  * __ffs = Find First set bit in word.  Undefined if no set bit exists.
280  */
281 static inline unsigned long __ffs(unsigned long word)
282 {
283 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
284         /* Whee.  EV67 can calculate it directly.  */
285         return __kernel_cttz(word);
286 #else
287         unsigned long bits, qofs, bofs;
288
289         bits = __kernel_cmpbge(0, word);
290         qofs = ffz_b(bits);
291         bits = __kernel_extbl(word, qofs);
292         bofs = ffz_b(~bits);
293
294         return qofs*8 + bofs;
295 #endif
296 }
297
298 #ifdef __KERNEL__
299
300 /*
301  * ffs: find first bit set. This is defined the same way as
302  * the libc and compiler builtin ffs routines, therefore
303  * differs in spirit from the above __ffs.
304  */
305
306 static inline int ffs(int word)
307 {
308         int result = __ffs(word) + 1;
309         return word ? result : 0;
310 }
311
312 /*
313  * fls: find last bit set.
314  */
315 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
316 static inline int fls(int word)
317 {
318         return 64 - __kernel_ctlz(word & 0xffffffff);
319 }
320 #else
321 #include <asm-generic/bitops/fls.h>
322 #endif
323 #include <asm-generic/bitops/fls64.h>
324
325 /* Compute powers of two for the given integer.  */
326 static inline long floor_log2(unsigned long word)
327 {
328 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
329         return 63 - __kernel_ctlz(word);
330 #else
331         long bit;
332         for (bit = -1; word ; bit++)
333                 word >>= 1;
334         return bit;
335 #endif
336 }
337
338 static inline long ceil_log2(unsigned long word)
339 {
340         long bit = floor_log2(word);
341         return bit + (word > (1UL << bit));
342 }
343
344 /*
345  * hweightN: returns the hamming weight (i.e. the number
346  * of bits set) of a N-bit word
347  */
348
349 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
350 /* Whee.  EV67 can calculate it directly.  */
351 static inline unsigned long hweight64(unsigned long w)
352 {
353         return __kernel_ctpop(w);
354 }
355
356 #define hweight32(x)    (unsigned int) hweight64((x) & 0xfffffffful)
357 #define hweight16(x)    (unsigned int) hweight64((x) & 0xfffful)
358 #define hweight8(x)     (unsigned int) hweight64((x) & 0xfful)
359 #else
360 #include <asm-generic/bitops/hweight.h>
361 #endif
362
363 #endif /* __KERNEL__ */
364
365 #include <asm-generic/bitops/find.h>
366
367 #ifdef __KERNEL__
368
369 /*
370  * Every architecture must define this function. It's the fastest
371  * way of searching a 140-bit bitmap where the first 100 bits are
372  * unlikely to be set. It's guaranteed that at least one of the 140
373  * bits is set.
374  */
375 static inline unsigned long
376 sched_find_first_bit(unsigned long b[3])
377 {
378         unsigned long b0 = b[0], b1 = b[1], b2 = b[2];
379         unsigned long ofs;
380
381         ofs = (b1 ? 64 : 128);
382         b1 = (b1 ? b1 : b2);
383         ofs = (b0 ? 0 : ofs);
384         b0 = (b0 ? b0 : b1);
385
386         return __ffs(b0) + ofs;
387 }
388
389 #include <asm-generic/bitops/ext2-non-atomic.h>
390
391 #define ext2_set_bit_atomic(l,n,a)   test_and_set_bit(n,a)
392 #define ext2_clear_bit_atomic(l,n,a) test_and_clear_bit(n,a)
393
394 #include <asm-generic/bitops/minix.h>
395
396 #endif /* __KERNEL__ */
397
398 #endif /* _ALPHA_BITOPS_H */