include/asm-alpha/bitops.h

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