include/asm-alpha/bitops.h

   1 #ifndef _ALPHA_BITOPS_H
   2 #define _ALPHA_BITOPS_H
   3
   4 #include <linux/config.h>
   5 #include <linux/kernel.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 extern __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 extern __inline__ void
  45 __set_bit(unsigned long nr, volatile void * addr)
  46 {
  47         int *m = ((int *) addr) + (nr >> 5);
  48
  49         *m |= 1UL << (nr & 31);
  50 }
  51
  52 #define smp_mb__before_clear_bit()      smp_mb()
  53 #define smp_mb__after_clear_bit()       smp_mb()
  54
  55 extern __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         "       and %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 extern __inline__ void
  74 change_bit(unsigned long nr, volatile void * addr)
  75 {
  76         unsigned long temp;
  77         int *m = ((int *) addr) + (nr >> 5);
  78
  79         __asm__ __volatile__(
  80         "1:     ldl_l %0,%3\n"
  81         "       xor %0,%2,%0\n"
  82         "       stl_c %0,%1\n"
  83         "       beq %0,2f\n"
  84         ".subsection 2\n"
  85         "2:     br 1b\n"
  86         ".previous"
  87         :"=&r" (temp), "=m" (*m)
  88         :"Ir" (1UL << (nr & 31)), "m" (*m));
  89 }
  90
  91 extern __inline__ int
  92 test_and_set_bit(unsigned long nr, volatile void *addr)
  93 {
  94         unsigned long oldbit;
  95         unsigned long temp;
  96         int *m = ((int *) addr) + (nr >> 5);
  97
  98         __asm__ __volatile__(
  99         "1:     ldl_l %0,%4\n"
 100         "       and %0,%3,%2\n"
 101         "       bne %2,2f\n"
 102         "       xor %0,%3,%0\n"
 103         "       stl_c %0,%1\n"
 104         "       beq %0,3f\n"
 105         "2:\n"
 106 #ifdef CONFIG_SMP
 107         "       mb\n"
 108 #endif
 109         ".subsection 2\n"
 110         "3:     br 1b\n"
 111         ".previous"
 112         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
 113         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
 114
 115         return oldbit != 0;
 116 }
 117
 118 /*
 119  * WARNING: non atomic version.
 120  */
 121 extern __inline__ int
 122 __test_and_set_bit(unsigned long nr, volatile void * addr)
 123 {
 124         unsigned long mask = 1 << (nr & 0x1f);
 125         int *m = ((int *) addr) + (nr >> 5);
 126         int old = *m;
 127
 128         *m = old | mask;
 129         return (old & mask) != 0;
 130 }
 131
 132 extern __inline__ int
 133 test_and_clear_bit(unsigned long nr, volatile void * addr)
 134 {
 135         unsigned long oldbit;
 136         unsigned long temp;
 137         int *m = ((int *) addr) + (nr >> 5);
 138
 139         __asm__ __volatile__(
 140         "1:     ldl_l %0,%4\n"
 141         "       and %0,%3,%2\n"
 142         "       beq %2,2f\n"
 143         "       xor %0,%3,%0\n"
 144         "       stl_c %0,%1\n"
 145         "       beq %0,3f\n"
 146         "2:\n"
 147 #ifdef CONFIG_SMP
 148         "       mb\n"
 149 #endif
 150         ".subsection 2\n"
 151         "3:     br 1b\n"
 152         ".previous"
 153         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
 154         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
 155
 156         return oldbit != 0;
 157 }
 158
 159 /*
 160  * WARNING: non atomic version.
 161  */
 162 extern __inline__ int
 163 __test_and_clear_bit(unsigned long nr, volatile void * addr)
 164 {
 165         unsigned long mask = 1 << (nr & 0x1f);
 166         int *m = ((int *) addr) + (nr >> 5);
 167         int old = *m;
 168
 169         *m = old & ~mask;
 170         return (old & mask) != 0;
 171 }
 172
 173 extern __inline__ int
 174 test_and_change_bit(unsigned long nr, volatile void * addr)
 175 {
 176         unsigned long oldbit;
 177         unsigned long temp;
 178         int *m = ((int *) addr) + (nr >> 5);
 179
 180         __asm__ __volatile__(
 181         "1:     ldl_l %0,%4\n"
 182         "       and %0,%3,%2\n"
 183         "       xor %0,%3,%0\n"
 184         "       stl_c %0,%1\n"
 185         "       beq %0,3f\n"
 186 #ifdef CONFIG_SMP
 187         "       mb\n"
 188 #endif
 189         ".subsection 2\n"
 190         "3:     br 1b\n"
 191         ".previous"
 192         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
 193         :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory");
 194
 195         return oldbit != 0;
 196 }
 197
 198 extern __inline__ int
 199 test_bit(int nr, volatile void * addr)
 200 {
 201         return (1UL & (((const int *) addr)[nr >> 5] >> (nr & 31))) != 0UL;
 202 }
 203
 204 /*
 205  * ffz = Find First Zero in word. Undefined if no zero exists,
 206  * so code should check against ~0UL first..
 207  *
 208  * Do a binary search on the bits.  Due to the nature of large
 209  * constants on the alpha, it is worthwhile to split the search.
 210  */
 211 extern inline unsigned long ffz_b(unsigned long x)
 212 {
 213         unsigned long sum = 0;
 214
 215         x = ~x & -~x;           /* set first 0 bit, clear others */
 216         if (x & 0xF0) sum += 4;
 217         if (x & 0xCC) sum += 2;
 218         if (x & 0xAA) sum += 1;
 219
 220         return sum;
 221 }
 222
 223 extern inline unsigned long ffz(unsigned long word)
 224 {
 225 #if defined(__alpha_cix__) && defined(__alpha_fix__)
 226         /* Whee.  EV67 can calculate it directly.  */
 227         unsigned long result;
 228         __asm__("cttz %1,%0" : "=r"(result) : "r"(~word));
 229         return result;
 230 #else
 231         unsigned long bits, qofs, bofs;
 232
 233         __asm__("cmpbge %1,%2,%0" : "=r"(bits) : "r"(word), "r"(~0UL));
 234         qofs = ffz_b(bits);
 235         __asm__("extbl %1,%2,%0" : "=r"(bits) : "r"(word), "r"(qofs));
 236         bofs = ffz_b(bits);
 237
 238         return qofs*8 + bofs;
 239 #endif
 240 }
 241
 242 #ifdef __KERNEL__
 243
 244 /*
 245  * ffs: find first bit set. This is defined the same way as
 246  * the libc and compiler builtin ffs routines, therefore
 247  * differs in spirit from the above ffz (man ffs).
 248  */
 249
 250 extern inline int ffs(int word)
 251 {
 252         int result = ffz(~word);
 253         return word ? result+1 : 0;
 254 }
 255
 256 /*
 257  * hweightN: returns the hamming weight (i.e. the number
 258  * of bits set) of a N-bit word
 259  */
 260
 261 #if defined(__alpha_cix__) && defined(__alpha_fix__)
 262 /* Whee.  EV67 can calculate it directly.  */
 263 extern __inline__ unsigned long hweight64(unsigned long w)
 264 {
 265         unsigned long result;
 266         __asm__("ctpop %1,%0" : "=r"(result) : "r"(w));
 267         return result;
 268 }
 269
 270 #define hweight32(x) hweight64((x) & 0xfffffffful)
 271 #define hweight16(x) hweight64((x) & 0xfffful)
 272 #define hweight8(x)  hweight64((x) & 0xfful)
 273 #else
 274 #define hweight32(x) generic_hweight32(x)
 275 #define hweight16(x) generic_hweight16(x)
 276 #define hweight8(x)  generic_hweight8(x)
 277 #endif
 278
 279 #endif /* __KERNEL__ */
 280
 281 /*
 282  * Find next zero bit in a bitmap reasonably efficiently..
 283  */
 284 extern inline unsigned long
 285 find_next_zero_bit(void * addr, unsigned long size, unsigned long offset)
 286 {
 287         unsigned long * p = ((unsigned long *) addr) + (offset >> 6);
 288         unsigned long result = offset & ~63UL;
 289         unsigned long tmp;
 290
 291         if (offset >= size)
 292                 return size;
 293         size -= result;
 294         offset &= 63UL;
 295         if (offset) {
 296                 tmp = *(p++);
 297                 tmp |= ~0UL >> (64-offset);
 298                 if (size < 64)
 299                         goto found_first;
 300                 if (~tmp)
 301                         goto found_middle;
 302                 size -= 64;
 303                 result += 64;
 304         }
 305         while (size & ~63UL) {
 306                 if (~(tmp = *(p++)))
 307                         goto found_middle;
 308                 result += 64;
 309                 size -= 64;
 310         }
 311         if (!size)
 312                 return result;
 313         tmp = *p;
 314 found_first:
 315         tmp |= ~0UL << size;
 316         if (tmp == ~0UL)        /* Are any bits zero? */
 317                 return result + size; /* Nope. */
 318 found_middle:
 319         return result + ffz(tmp);
 320 }
 321
 322 /*
 323  * The optimizer actually does good code for this case..
 324  */
 325 #define find_first_zero_bit(addr, size) \
 326         find_next_zero_bit((addr), (size), 0)
 327
 328 #ifdef __KERNEL__
 329
 330 #define ext2_set_bit                 __test_and_set_bit
 331 #define ext2_clear_bit               __test_and_clear_bit
 332 #define ext2_test_bit                test_bit
 333 #define ext2_find_first_zero_bit     find_first_zero_bit
 334 #define ext2_find_next_zero_bit      find_next_zero_bit
 335
 336 /* Bitmap functions for the minix filesystem.  */
 337 #define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,addr)
 338 #define minix_set_bit(nr,addr) __set_bit(nr,addr)
 339 #define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,addr)
 340 #define minix_test_bit(nr,addr) test_bit(nr,addr)
 341 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
 342
 343 #endif /* __KERNEL__ */
 344
 345 #endif /* _ALPHA_BITOPS_H */