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 #ifdef CONFIG_SMP
 121         "       mb\n"
 122 #endif
 123         "1:     ldl_l %0,%4\n"
 124         "       and %0,%3,%2\n"
 125         "       bne %2,2f\n"
 126         "       xor %0,%3,%0\n"
 127         "       stl_c %0,%1\n"
 128         "       beq %0,3f\n"
 129         "2:\n"
 130 #ifdef CONFIG_SMP
 131         "       mb\n"
 132 #endif
 133         ".subsection 2\n"
 134         "3:     br 1b\n"
 135         ".previous"
 136         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
 137         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
 138
 139         return oldbit != 0;
 140 }
 141
 142 /*
 143  * WARNING: non atomic version.
 144  */
 145 static inline int
 146 __test_and_set_bit(unsigned long nr, volatile void * addr)
 147 {
 148         unsigned long mask = 1 << (nr & 0x1f);
 149         int *m = ((int *) addr) + (nr >> 5);
 150         int old = *m;
 151
 152         *m = old | mask;
 153         return (old & mask) != 0;
 154 }
 155
 156 static inline int
 157 test_and_clear_bit(unsigned long nr, volatile void * addr)
 158 {
 159         unsigned long oldbit;
 160         unsigned long temp;
 161         int *m = ((int *) addr) + (nr >> 5);
 162
 163         __asm__ __volatile__(
 164 #ifdef CONFIG_SMP
 165         "       mb\n"
 166 #endif
 167         "1:     ldl_l %0,%4\n"
 168         "       and %0,%3,%2\n"
 169         "       beq %2,2f\n"
 170         "       xor %0,%3,%0\n"
 171         "       stl_c %0,%1\n"
 172         "       beq %0,3f\n"
 173         "2:\n"
 174 #ifdef CONFIG_SMP
 175         "       mb\n"
 176 #endif
 177         ".subsection 2\n"
 178         "3:     br 1b\n"
 179         ".previous"
 180         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
 181         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
 182
 183         return oldbit != 0;
 184 }
 185
 186 /*
 187  * WARNING: non atomic version.
 188  */
 189 static inline int
 190 __test_and_clear_bit(unsigned long nr, volatile void * addr)
 191 {
 192         unsigned long mask = 1 << (nr & 0x1f);
 193         int *m = ((int *) addr) + (nr >> 5);
 194         int old = *m;
 195
 196         *m = old & ~mask;
 197         return (old & mask) != 0;
 198 }
 199
 200 static inline int
 201 test_and_change_bit(unsigned long nr, volatile void * addr)
 202 {
 203         unsigned long oldbit;
 204         unsigned long temp;
 205         int *m = ((int *) addr) + (nr >> 5);
 206
 207         __asm__ __volatile__(
 208 #ifdef CONFIG_SMP
 209         "       mb\n"
 210 #endif
 211         "1:     ldl_l %0,%4\n"
 212         "       and %0,%3,%2\n"
 213         "       xor %0,%3,%0\n"
 214         "       stl_c %0,%1\n"
 215         "       beq %0,3f\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_change_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_bit(int nr, const volatile void * addr)
 244 {
 245         return (1UL & (((const int *) addr)[nr >> 5] >> (nr & 31))) != 0UL;
 246 }
 247
 248 /*
 249  * ffz = Find First Zero in word. Undefined if no zero exists,
 250  * so code should check against ~0UL first..
 251  *
 252  * Do a binary search on the bits.  Due to the nature of large
 253  * constants on the alpha, it is worthwhile to split the search.
 254  */
 255 static inline unsigned long ffz_b(unsigned long x)
 256 {
 257         unsigned long sum, x1, x2, x4;
 258
 259         x = ~x & -~x;           /* set first 0 bit, clear others */
 260         x1 = x & 0xAA;
 261         x2 = x & 0xCC;
 262         x4 = x & 0xF0;
 263         sum = x2 ? 2 : 0;
 264         sum += (x4 != 0) * 4;
 265         sum += (x1 != 0);
 266
 267         return sum;
 268 }
 269
 270 static inline unsigned long ffz(unsigned long word)
 271 {
 272 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
 273         /* Whee.  EV67 can calculate it directly.  */
 274         return __kernel_cttz(~word);
 275 #else
 276         unsigned long bits, qofs, bofs;
 277
 278         bits = __kernel_cmpbge(word, ~0UL);
 279         qofs = ffz_b(bits);
 280         bits = __kernel_extbl(word, qofs);
 281         bofs = ffz_b(bits);
 282
 283         return qofs*8 + bofs;
 284 #endif
 285 }
 286
 287 /*
 288  * __ffs = Find First set bit in word.  Undefined if no set bit exists.
 289  */
 290 static inline unsigned long __ffs(unsigned long word)
 291 {
 292 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
 293         /* Whee.  EV67 can calculate it directly.  */
 294         return __kernel_cttz(word);
 295 #else
 296         unsigned long bits, qofs, bofs;
 297
 298         bits = __kernel_cmpbge(0, word);
 299         qofs = ffz_b(bits);
 300         bits = __kernel_extbl(word, qofs);
 301         bofs = ffz_b(~bits);
 302
 303         return qofs*8 + bofs;
 304 #endif
 305 }
 306
 307 #ifdef __KERNEL__
 308
 309 /*
 310  * ffs: find first bit set. This is defined the same way as
 311  * the libc and compiler builtin ffs routines, therefore
 312  * differs in spirit from the above __ffs.
 313  */
 314
 315 static inline int ffs(int word)
 316 {
 317         int result = __ffs(word) + 1;
 318         return word ? result : 0;
 319 }
 320
 321 /*
 322  * fls: find last bit set.
 323  */
 324 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
 325 static inline int fls64(unsigned long word)
 326 {
 327         return 64 - __kernel_ctlz(word);
 328 }
 329 #else
 330 extern const unsigned char __flsm1_tab[256];
 331
 332 static inline int fls64(unsigned long x)
 333 {
 334         unsigned long t, a, r;
 335
 336         t = __kernel_cmpbge (x, 0x0101010101010101UL);
 337         a = __flsm1_tab[t];
 338         t = __kernel_extbl (x, a);
 339         r = a*8 + __flsm1_tab[t] + (x != 0);
 340
 341         return r;
 342 }
 343 #endif
 344
 345 static inline int fls(int x)
 346 {
 347         return fls64((unsigned int) x);
 348 }
 349
 350 /*
 351  * hweightN: returns the hamming weight (i.e. the number
 352  * of bits set) of a N-bit word
 353  */
 354
 355 #if defined(CONFIG_ALPHA_EV6) && defined(CONFIG_ALPHA_EV67)
 356 /* Whee.  EV67 can calculate it directly.  */
 357 static inline unsigned long hweight64(unsigned long w)
 358 {
 359         return __kernel_ctpop(w);
 360 }
 361
 362 static inline unsigned int hweight32(unsigned int w)
 363 {
 364         return hweight64(w);
 365 }
 366
 367 static inline unsigned int hweight16(unsigned int w)
 368 {
 369         return hweight64(w & 0xffff);
 370 }
 371
 372 static inline unsigned int hweight8(unsigned int w)
 373 {
 374         return hweight64(w & 0xff);
 375 }
 376 #else
 377 #include <asm-generic/bitops/hweight.h>
 378 #endif
 379 #include <asm-generic/bitops/lock.h>
 380
 381 #endif /* __KERNEL__ */
 382
 383 #include <asm-generic/bitops/find.h>
 384
 385 #ifdef __KERNEL__
 386
 387 /*
 388  * Every architecture must define this function. It's the fastest
 389  * way of searching a 140-bit bitmap where the first 100 bits are
 390  * unlikely to be set. It's guaranteed that at least one of the 140
 391  * bits is set.
 392  */
 393 static inline unsigned long
 394 sched_find_first_bit(unsigned long b[3])
 395 {
 396         unsigned long b0 = b[0], b1 = b[1], b2 = b[2];
 397         unsigned long ofs;
 398
 399         ofs = (b1 ? 64 : 128);
 400         b1 = (b1 ? b1 : b2);
 401         ofs = (b0 ? 0 : ofs);
 402         b0 = (b0 ? b0 : b1);
 403
 404         return __ffs(b0) + ofs;
 405 }
 406
 407 #include <asm-generic/bitops/ext2-non-atomic.h>
 408
 409 #define ext2_set_bit_atomic(l,n,a)   test_and_set_bit(n,a)
 410 #define ext2_clear_bit_atomic(l,n,a) test_and_clear_bit(n,a)
 411
 412 #include <asm-generic/bitops/minix.h>
 413
 414 #endif /* __KERNEL__ */
 415
 416 #endif /* _ALPHA_BITOPS_H */