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(__alpha_cix__) && defined(__alpha_fix__)
 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(__alpha_cix__) && defined(__alpha_fix__)
 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(__alpha_cix__) && defined(__alpha_fix__)
 317 static inline int fls(int word)
 318 {
 319         return 64 - __kernel_ctlz(word & 0xffffffff);
 320 }
 321 #else
 322 #define fls     generic_fls
 323 #endif
 324 #define fls64   generic_fls64
 325
 326 /* Compute powers of two for the given integer.  */
 327 static inline long floor_log2(unsigned long word)
 328 {
 329 #if defined(__alpha_cix__) && defined(__alpha_fix__)
 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(__alpha_cix__) && defined(__alpha_fix__)
 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 static inline unsigned long hweight64(unsigned long w)
 362 {
 363         unsigned long result;
 364         for (result = 0; w ; w >>= 1)
 365                 result += (w & 1);
 366         return result;
 367 }
 368
 369 #define hweight32(x) generic_hweight32(x)
 370 #define hweight16(x) generic_hweight16(x)
 371 #define hweight8(x)  generic_hweight8(x)
 372 #endif
 373
 374 #endif /* __KERNEL__ */
 375
 376 /*
 377  * Find next zero bit in a bitmap reasonably efficiently..
 378  */
 379 static inline unsigned long
 380 find_next_zero_bit(const void *addr, unsigned long size, unsigned long offset)
 381 {
 382         const unsigned long *p = addr;
 383         unsigned long result = offset & ~63UL;
 384         unsigned long tmp;
 385
 386         p += offset >> 6;
 387         if (offset >= size)
 388                 return size;
 389         size -= result;
 390         offset &= 63UL;
 391         if (offset) {
 392                 tmp = *(p++);
 393                 tmp |= ~0UL >> (64-offset);
 394                 if (size < 64)
 395                         goto found_first;
 396                 if (~tmp)
 397                         goto found_middle;
 398                 size -= 64;
 399                 result += 64;
 400         }
 401         while (size & ~63UL) {
 402                 if (~(tmp = *(p++)))
 403                         goto found_middle;
 404                 result += 64;
 405                 size -= 64;
 406         }
 407         if (!size)
 408                 return result;
 409         tmp = *p;
 410  found_first:
 411         tmp |= ~0UL << size;
 412         if (tmp == ~0UL)        /* Are any bits zero? */
 413                 return result + size; /* Nope. */
 414  found_middle:
 415         return result + ffz(tmp);
 416 }
 417
 418 /*
 419  * Find next one bit in a bitmap reasonably efficiently.
 420  */
 421 static inline unsigned long
 422 find_next_bit(const void * addr, unsigned long size, unsigned long offset)
 423 {
 424         const unsigned long *p = addr;
 425         unsigned long result = offset & ~63UL;
 426         unsigned long tmp;
 427
 428         p += offset >> 6;
 429         if (offset >= size)
 430                 return size;
 431         size -= result;
 432         offset &= 63UL;
 433         if (offset) {
 434                 tmp = *(p++);
 435                 tmp &= ~0UL << offset;
 436                 if (size < 64)
 437                         goto found_first;
 438                 if (tmp)
 439                         goto found_middle;
 440                 size -= 64;
 441                 result += 64;
 442         }
 443         while (size & ~63UL) {
 444                 if ((tmp = *(p++)))
 445                         goto found_middle;
 446                 result += 64;
 447                 size -= 64;
 448         }
 449         if (!size)
 450                 return result;
 451         tmp = *p;
 452  found_first:
 453         tmp &= ~0UL >> (64 - size);
 454         if (!tmp)
 455                 return result + size;
 456  found_middle:
 457         return result + __ffs(tmp);
 458 }
 459
 460 /*
 461  * The optimizer actually does good code for this case.
 462  */
 463 #define find_first_zero_bit(addr, size) \
 464         find_next_zero_bit((addr), (size), 0)
 465 #define find_first_bit(addr, size) \
 466         find_next_bit((addr), (size), 0)
 467
 468 #ifdef __KERNEL__
 469
 470 /*
 471  * Every architecture must define this function. It's the fastest
 472  * way of searching a 140-bit bitmap where the first 100 bits are
 473  * unlikely to be set. It's guaranteed that at least one of the 140
 474  * bits is set.
 475  */
 476 static inline unsigned long
 477 sched_find_first_bit(unsigned long b[3])
 478 {
 479         unsigned long b0 = b[0], b1 = b[1], b2 = b[2];
 480         unsigned long ofs;
 481
 482         ofs = (b1 ? 64 : 128);
 483         b1 = (b1 ? b1 : b2);
 484         ofs = (b0 ? 0 : ofs);
 485         b0 = (b0 ? b0 : b1);
 486
 487         return __ffs(b0) + ofs;
 488 }
 489
 490
 491 #define ext2_set_bit                 __test_and_set_bit
 492 #define ext2_set_bit_atomic(l,n,a)   test_and_set_bit(n,a)
 493 #define ext2_clear_bit               __test_and_clear_bit
 494 #define ext2_clear_bit_atomic(l,n,a) test_and_clear_bit(n,a)
 495 #define ext2_test_bit                test_bit
 496 #define ext2_find_first_zero_bit     find_first_zero_bit
 497 #define ext2_find_next_zero_bit      find_next_zero_bit
 498
 499 /* Bitmap functions for the minix filesystem.  */
 500 #define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,addr)
 501 #define minix_set_bit(nr,addr) __set_bit(nr,addr)
 502 #define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,addr)
 503 #define minix_test_bit(nr,addr) test_bit(nr,addr)
 504 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
 505
 506 #endif /* __KERNEL__ */
 507
 508 #endif /* _ALPHA_BITOPS_H */