1 /* $Id: bitops.h,v 1.7 1999/08/19 22:56:33 ralf Exp $
2 *
3 * This file is subject to the terms and conditions of the GNU General Public
4 * License. See the file "COPYING" in the main directory of this archive
5 * for more details.
6 *
7 * Copyright (c) 1994 - 1997, 1999 Ralf Baechle (ralf@gnu.org)
8 */
9 #ifndef _ASM_BITOPS_H
10 #define _ASM_BITOPS_H
11
12 #include <linux/types.h>
13 #include <asm/byteorder.h> /* sigh ... */
14
15 #ifdef __KERNEL__
16
17 #include <asm/sgidefs.h>
18 #include <asm/system.h>
19 #include <linux/config.h>
20
21 /*
22 * Only disable interrupt for kernel mode stuff to keep usermode stuff
23 * that dares to use kernel include files alive.
24 */
25 #define __bi_flags unsigned long flags
26 #define __bi_cli() __cli()
27 #define __bi_save_flags(x) __save_flags(x)
28 #define __bi_save_and_cli(x) __save_and_cli(x)
29 #define __bi_restore_flags(x) __restore_flags(x)
30 #else
31 #define __bi_flags
32 #define __bi_cli()
33 #define __bi_save_flags(x)
34 #define __bi_save_and_cli(x)
35 #define __bi_restore_flags(x)
36 #endif /* __KERNEL__ */
37
38 /*
39 * Note that the bit operations are defined on arrays of 32 bit sized
40 * elements. With respect to a future 64 bit implementation it is
41 * wrong to use long *. Use u32 * or int *.
42 */
43 extern __inline__ void set_bit(int nr, void *addr);
44 extern __inline__ void clear_bit(int nr, void *addr);
45 extern __inline__ void change_bit(int nr, void *addr);
46 extern __inline__ int test_and_set_bit(int nr, void *addr);
47 extern __inline__ int test_and_clear_bit(int nr, void *addr);
48 extern __inline__ int test_and_change_bit(int nr, void *addr);
49
50 extern __inline__ int test_bit(int nr, const void *addr);
51 #ifndef __MIPSEB__
52 extern __inline__ int find_first_zero_bit (void *addr, unsigned size);
53 #endif
54 extern __inline__ int find_next_zero_bit (void * addr, int size, int offset);
55 extern __inline__ unsigned long ffz(unsigned long word);
56
57 #if defined(CONFIG_CPU_HAS_LLSC)
58
59 #include <asm/mipsregs.h>
60
61 /*
62 * These functions for MIPS ISA > 1 are interrupt and SMP proof and
63 * interrupt friendly
64 */
65
66 /*
67 * The following functions will only work for the R4000!
68 */
69
70 extern __inline__ void set_bit(int nr, void *addr)
71 {
72 int mask, mw;
73
74 addr += ((nr >> 3) & ~3);
75 mask = 1 << (nr & 0x1f);
76 do {
77 mw = load_linked(addr);
78 } while (!store_conditional(addr, mw|mask));
79 }
80
81 extern __inline__ void clear_bit(int nr, void *addr)
82 {
83 int mask, mw;
84
85 addr += ((nr >> 3) & ~3);
86 mask = 1 << (nr & 0x1f);
87 do {
88 mw = load_linked(addr);
89 }
90 while (!store_conditional(addr, mw & ~mask));
91 }
92
93 extern __inline__ void change_bit(int nr, void *addr)
94 {
95 int mask, mw;
96
97 addr += ((nr >> 3) & ~3);
98 mask = 1 << (nr & 0x1f);
99 do {
100 mw = load_linked(addr);
101 } while (!store_conditional(addr, mw ^ mask));
102 }
103
104 extern __inline__ int test_and_set_bit(int nr, void *addr)
105 {
106 int mask, retval, mw;
107
108 addr += ((nr >> 3) & ~3);
109 mask = 1 << (nr & 0x1f);
110 do {
111 mw = load_linked(addr);
112 retval = (mask & mw) != 0;
113 } while (!store_conditional(addr, mw|mask));
114
115 return retval;
116 }
117
118 extern __inline__ int test_and_clear_bit(int nr, void *addr)
119 {
120 int mask, retval, mw;
121
122 addr += ((nr >> 3) & ~3);
123 mask = 1 << (nr & 0x1f);
124 do {
125 mw = load_linked(addr);
126 retval = (mask & mw) != 0;
127 }
128 while (!store_conditional(addr, mw & ~mask));
129
130 return retval;
131 }
132
133 extern __inline__ int test_and_change_bit(int nr, void *addr)
134 {
135 int mask, retval, mw;
136
137 addr += ((nr >> 3) & ~3);
138 mask = 1 << (nr & 0x1f);
139 do {
140 mw = load_linked(addr);
141 retval = (mask & mw) != 0;
142 } while (!store_conditional(addr, mw ^ mask));
143
144 return retval;
145 }
146
147 #else /* MIPS I */
148
149 extern __inline__ void set_bit(int nr, void * addr)
150 {
151 int mask;
152 int *a = addr;
153 __bi_flags;
154
155 a += nr >> 5;
156 mask = 1 << (nr & 0x1f);
157 __bi_save_and_cli(flags);
158 *a |= mask;
159 __bi_restore_flags(flags);
160 }
161
162 extern __inline__ void clear_bit(int nr, void * addr)
163 {
164 int mask;
165 int *a = addr;
166 __bi_flags;
167
168 a += nr >> 5;
169 mask = 1 << (nr & 0x1f);
170 __bi_save_and_cli(flags);
171 *a &= ~mask;
172 __bi_restore_flags(flags);
173 }
174
175 extern __inline__ void change_bit(int nr, void * addr)
176 {
177 int mask;
178 int *a = addr;
179 __bi_flags;
180
181 a += nr >> 5;
182 mask = 1 << (nr & 0x1f);
183 __bi_save_and_cli(flags);
184 *a ^= mask;
185 __bi_restore_flags(flags);
186 }
187
188 extern __inline__ int test_and_set_bit(int nr, void * addr)
189 {
190 int mask, retval;
191 int *a = addr;
192 __bi_flags;
193
194 a += nr >> 5;
195 mask = 1 << (nr & 0x1f);
196 __bi_save_and_cli(flags);
197 retval = (mask & *a) != 0;
198 *a |= mask;
199 __bi_restore_flags(flags);
200
201 return retval;
202 }
203
204 extern __inline__ int test_and_clear_bit(int nr, void * addr)
205 {
206 int mask, retval;
207 int *a = addr;
208 __bi_flags;
209
210 a += nr >> 5;
211 mask = 1 << (nr & 0x1f);
212 __bi_save_and_cli(flags);
213 retval = (mask & *a) != 0;
214 *a &= ~mask;
215 __bi_restore_flags(flags);
216
217 return retval;
218 }
219
220 extern __inline__ int test_and_change_bit(int nr, void * addr)
221 {
222 int mask, retval;
223 int *a = addr;
224 __bi_flags;
225
226 a += nr >> 5;
227 mask = 1 << (nr & 0x1f);
228 __bi_save_and_cli(flags);
229 retval = (mask & *a) != 0;
230 *a ^= mask;
231 __bi_restore_flags(flags);
232
233 return retval;
234 }
235
236 #undef __bi_flags
237 #undef __bi_cli()
238 #undef __bi_save_flags(x)
239 #undef __bi_restore_flags(x)
240
241 #endif /* MIPS I */
242
243 extern __inline__ int test_bit(int nr, const void *addr)
244 {
245 return ((1UL << (nr & 31)) & (((const unsigned int *) addr)[nr >> 5])) != 0;
246 }
247
248 #ifndef __MIPSEB__
249
250 /* Little endian versions. */
251
252 extern __inline__ int find_first_zero_bit (void *addr, unsigned size)
253 {
254 unsigned long dummy;
255 int res;
256
257 if (!size)
258 return 0;
259
260 __asm__ (".set\tnoreorder\n\t"
261 ".set\tnoat\n"
262 "1:\tsubu\t$1,%6,%0\n\t"
263 "blez\t$1,2f\n\t"
264 "lw\t$1,(%5)\n\t"
265 "addiu\t%5,4\n\t"
266 #if (_MIPS_ISA == _MIPS_ISA_MIPS2) || (_MIPS_ISA == _MIPS_ISA_MIPS3) || \
267 (_MIPS_ISA == _MIPS_ISA_MIPS4) || (_MIPS_ISA == _MIPS_ISA_MIPS5)
268 "beql\t%1,$1,1b\n\t"
269 "addiu\t%0,32\n\t"
270 #else
271 "addiu\t%0,32\n\t"
272 "beq\t%1,$1,1b\n\t"
273 "nop\n\t"
274 "subu\t%0,32\n\t"
275 #endif
276 #ifdef __MIPSEB__
277 #error "Fix this for big endian"
278 #endif /* __MIPSEB__ */
279 "li\t%1,1\n"
280 "1:\tand\t%2,$1,%1\n\t"
281 "beqz\t%2,2f\n\t"
282 "sll\t%1,%1,1\n\t"
283 "bnez\t%1,1b\n\t"
284 "add\t%0,%0,1\n\t"
285 ".set\tat\n\t"
286 ".set\treorder\n"
287 "2:"
288 : "=r" (res),
289 "=r" (dummy),
290 "=r" (addr)
291 : "" ((signed int) 0),
292 "1" ((unsigned int) 0xffffffff),
293 "2" (addr),
294 "r" (size)
295 : "$1");
296
297 return res;
298 }
299
300 extern __inline__ int find_next_zero_bit (void * addr, int size, int offset)
301 {
302 unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
303 int set = 0, bit = offset & 31, res;
304 unsigned long dummy;
305
306 if (bit) {
307 /*
308 * Look for zero in first byte
309 */
310 #ifdef __MIPSEB__
311 #error "Fix this for big endian byte order"
312 #endif
313 __asm__(".set\tnoreorder\n\t"
314 ".set\tnoat\n"
315 "1:\tand\t$1,%4,%1\n\t"
316 "beqz\t$1,1f\n\t"
317 "sll\t%1,%1,1\n\t"
318 "bnez\t%1,1b\n\t"
319 "addiu\t%0,1\n\t"
320 ".set\tat\n\t"
321 ".set\treorder\n"
322 "1:"
323 : "=r" (set),
324 "=r" (dummy)
325 : "" (0),
326 "1" (1 << bit),
327 "r" (*p)
328 : "$1");
329 if (set < (32 - bit))
330 return set + offset;
331 set = 32 - bit;
332 p++;
333 }
334 /*
335 * No zero yet, search remaining full bytes for a zero
336 */
337 res = find_first_zero_bit(p, size - 32 * (p - (unsigned int *) addr));
338 return offset + set + res;
339 }
340
341 #endif /* !(__MIPSEB__) */
342
343 /*
344 * ffz = Find First Zero in word. Undefined if no zero exists,
345 * so code should check against ~0UL first..
346 */
347 extern __inline__ unsigned long ffz(unsigned long word)
348 {
349 unsigned int __res;
350 unsigned int mask = 1;
351
352 __asm__ (
353 ".set\tnoreorder\n\t"
354 ".set\tnoat\n\t"
355 "move\t%0,$0\n"
356 "1:\tand\t$1,%2,%1\n\t"
357 "beqz\t$1,2f\n\t"
358 "sll\t%1,1\n\t"
359 "bnez\t%1,1b\n\t"
360 "addiu\t%0,1\n\t"
361 ".set\tat\n\t"
362 ".set\treorder\n"
363 "2:\n\t"
364 : "=&r" (__res), "=r" (mask)
365 : "r" (word), "1" (mask)
366 : "$1");
367
368 return __res;
369 }
370
371 #ifdef __KERNEL__
372
373 /*
374 * ffs: find first bit set. This is defined the same way as
375 * the libc and compiler builtin ffs routines, therefore
376 * differs in spirit from the above ffz (man ffs).
377 */
378
379 #define ffs(x) generic_ffs(x)
380
381 /*
382 * hweightN: returns the hamming weight (i.e. the number
383 * of bits set) of a N-bit word
384 */
385
386 #define hweight32(x) generic_hweight32(x)
387 #define hweight16(x) generic_hweight16(x)
388 #define hweight8(x) generic_hweight8(x)
389
390 #endif /* __KERNEL__ */
391
392 #ifdef __MIPSEB__
393 /* For now I steal the Sparc C versions, no need for speed, just need to
394 * get it working.
395 */
396 /* find_next_zero_bit() finds the first zero bit in a bit string of length
397 * 'size' bits, starting the search at bit 'offset'. This is largely based
398 * on Linus's ALPHA routines, which are pretty portable BTW.
399 */
400
401 extern __inline__ int find_next_zero_bit(void *addr, int size, int offset)
402 {
403 unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
404 unsigned long result = offset & ~31UL;
405 unsigned long tmp;
406
407 if (offset >= size)
408 return size;
409 size -= result;
410 offset &= 31UL;
411 if (offset) {
412 tmp = *(p++);
413 tmp |= ~0UL >> (32-offset);
414 if (size < 32)
415 goto found_first;
416 if (~tmp)
417 goto found_middle;
418 size -= 32;
419 result += 32;
420 }
421 while (size & ~31UL) {
422 if (~(tmp = *(p++)))
423 goto found_middle;
424 result += 32;
425 size -= 32;
426 }
427 if (!size)
428 return result;
429 tmp = *p;
430
431 found_first:
432 tmp |= ~0UL << size;
433 found_middle:
434 return result + ffz(tmp);
435 }
436
437 /* Linus sez that gcc can optimize the following correctly, we'll see if this
438 * holds on the Sparc as it does for the ALPHA.
439 */
440
441 #define find_first_zero_bit(addr, size) \
442 find_next_zero_bit((addr), (size), 0)
443
444 #endif /* (__MIPSEB__) */
445
446 /* Now for the ext2 filesystem bit operations and helper routines. */
447
448 #ifdef __MIPSEB__
449 extern __inline__ int ext2_set_bit(int nr,void * addr)
450 {
451 int mask, retval, flags;
452 unsigned char *ADDR = (unsigned char *) addr;
453
454 ADDR += nr >> 3;
455 mask = 1 << (nr & 0x07);
456 save_and_cli(flags);
457 retval = (mask & *ADDR) != 0;
458 *ADDR |= mask;
459 restore_flags(flags);
460 return retval;
461 }
462
463 extern __inline__ int ext2_clear_bit(int nr, void * addr)
464 {
465 int mask, retval, flags;
466 unsigned char *ADDR = (unsigned char *) addr;
467
468 ADDR += nr >> 3;
469 mask = 1 << (nr & 0x07);
470 save_and_cli(flags);
471 retval = (mask & *ADDR) != 0;
472 *ADDR &= ~mask;
473 restore_flags(flags);
474 return retval;
475 }
476
477 extern __inline__ int ext2_test_bit(int nr, const void * addr)
478 {
479 int mask;
480 const unsigned char *ADDR = (const unsigned char *) addr;
481
482 ADDR += nr >> 3;
483 mask = 1 << (nr & 0x07);
484 return ((mask & *ADDR) != 0);
485 }
486
487 #define ext2_find_first_zero_bit(addr, size) \
488 ext2_find_next_zero_bit((addr), (size), 0)
489
490 extern __inline__ unsigned long ext2_find_next_zero_bit(void *addr, unsigned long size, unsigned long offset)
491 {
492 unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
493 unsigned long result = offset & ~31UL;
494 unsigned long tmp;
495
496 if (offset >= size)
497 return size;
498 size -= result;
499 offset &= 31UL;
500 if(offset) {
501 /* We hold the little endian value in tmp, but then the
502 * shift is illegal. So we could keep a big endian value
503 * in tmp, like this:
504 *
505 * tmp = __swab32(*(p++));
506 * tmp |= ~0UL >> (32-offset);
507 *
508 * but this would decrease preformance, so we change the
509 * shift:
510 */
511 tmp = *(p++);
512 tmp |= __swab32(~0UL >> (32-offset));
513 if(size < 32)
514 goto found_first;
515 if(~tmp)
516 goto found_middle;
517 size -= 32;
518 result += 32;
519 }
520 while(size & ~31UL) {
521 if(~(tmp = *(p++)))
522 goto found_middle;
523 result += 32;
524 size -= 32;
525 }
526 if(!size)
527 return result;
528 tmp = *p;
529
530 found_first:
531 /* tmp is little endian, so we would have to swab the shift,
532 * see above. But then we have to swab tmp below for ffz, so
533 * we might as well do this here.
534 */
535 return result + ffz(__swab32(tmp) | (~0UL << size));
536 found_middle:
537 return result + ffz(__swab32(tmp));
538 }
539 #else /* !(__MIPSEB__) */
540
541 /* Native ext2 byte ordering, just collapse using defines. */
542 #define ext2_set_bit(nr, addr) test_and_set_bit((nr), (addr))
543 #define ext2_clear_bit(nr, addr) test_and_clear_bit((nr), (addr))
544 #define ext2_test_bit(nr, addr) test_bit((nr), (addr))
545 #define ext2_find_first_zero_bit(addr, size) find_first_zero_bit((addr), (size))
546 #define ext2_find_next_zero_bit(addr, size, offset) \
547 find_next_zero_bit((addr), (size), (offset))
548
549 #endif /* !(__MIPSEB__) */
550
551 /*
552 * Bitmap functions for the minix filesystem.
553 * FIXME: These assume that Minix uses the native byte/bitorder.
554 * This limits the Minix filesystem's value for data exchange very much.
555 */
556 #define minix_test_and_set_bit(nr,addr) test_and_set_bit(nr,addr)
557 #define minix_set_bit(nr,addr) set_bit(nr,addr)
558 #define minix_test_and_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
559 #define minix_test_bit(nr,addr) test_bit(nr,addr)
560 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
561
562 #endif /* _ASM_BITOPS_H */
563
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.