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