include/asm-alpha/bitops.h

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