include/asm-parisc/bitops.h

   1 #ifndef _PARISC_BITOPS_H
   2 #define _PARISC_BITOPS_H
   3
   4 #include <linux/compiler.h>
   5 #include <asm/system.h>
   6 #include <asm/byteorder.h>
   7 #include <asm/atomic.h>
   8
   9 /*
  10  * HP-PARISC specific bit operations
  11  * for a detailed description of the functions please refer
  12  * to include/asm-i386/bitops.h or kerneldoc
  13  */
  14
  15 #ifdef __LP64__
  16 #   define SHIFT_PER_LONG 6
  17 #ifndef BITS_PER_LONG
  18 #   define BITS_PER_LONG 64
  19 #endif
  20 #else
  21 #   define SHIFT_PER_LONG 5
  22 #ifndef BITS_PER_LONG
  23 #   define BITS_PER_LONG 32
  24 #endif
  25 #endif
  26
  27 #define CHOP_SHIFTCOUNT(x) ((x) & (BITS_PER_LONG - 1))
  28
  29
  30 #define smp_mb__before_clear_bit()      smp_mb()
  31 #define smp_mb__after_clear_bit()       smp_mb()
  32
  33 static __inline__ void set_bit(int nr, volatile unsigned long * address)
  34 {
  35         unsigned long mask;
  36         unsigned long *addr = (unsigned long *) address;
  37         unsigned long flags;
  38
  39         addr += (nr >> SHIFT_PER_LONG);
  40         mask = 1L << CHOP_SHIFTCOUNT(nr);
  41         _atomic_spin_lock_irqsave(addr, flags);
  42         *addr |= mask;
  43         _atomic_spin_unlock_irqrestore(addr, flags);
  44 }
  45
  46 static __inline__ void __set_bit(int nr, volatile unsigned long * address)
  47 {
  48         unsigned long mask;
  49         unsigned long *addr = (unsigned long *) address;
  50
  51         addr += (nr >> SHIFT_PER_LONG);
  52         mask = 1L << CHOP_SHIFTCOUNT(nr);
  53         *addr |= mask;
  54 }
  55
  56 static __inline__ void clear_bit(int nr, volatile unsigned long * address)
  57 {
  58         unsigned long mask;
  59         unsigned long *addr = (unsigned long *) address;
  60         unsigned long flags;
  61
  62         addr += (nr >> SHIFT_PER_LONG);
  63         mask = 1L << CHOP_SHIFTCOUNT(nr);
  64         _atomic_spin_lock_irqsave(addr, flags);
  65         *addr &= ~mask;
  66         _atomic_spin_unlock_irqrestore(addr, flags);
  67 }
  68
  69 static __inline__ void __clear_bit(unsigned long nr, volatile unsigned long * address)
  70 {
  71         unsigned long mask;
  72         unsigned long *addr = (unsigned long *) address;
  73
  74         addr += (nr >> SHIFT_PER_LONG);
  75         mask = 1L << CHOP_SHIFTCOUNT(nr);
  76         *addr &= ~mask;
  77 }
  78
  79 static __inline__ void change_bit(int nr, volatile unsigned long * address)
  80 {
  81         unsigned long mask;
  82         unsigned long *addr = (unsigned long *) address;
  83         unsigned long flags;
  84
  85         addr += (nr >> SHIFT_PER_LONG);
  86         mask = 1L << CHOP_SHIFTCOUNT(nr);
  87         _atomic_spin_lock_irqsave(addr, flags);
  88         *addr ^= mask;
  89         _atomic_spin_unlock_irqrestore(addr, flags);
  90 }
  91
  92 static __inline__ void __change_bit(int nr, volatile unsigned long * address)
  93 {
  94         unsigned long mask;
  95         unsigned long *addr = (unsigned long *) address;
  96
  97         addr += (nr >> SHIFT_PER_LONG);
  98         mask = 1L << CHOP_SHIFTCOUNT(nr);
  99         *addr ^= mask;
 100 }
 101
 102 static __inline__ int test_and_set_bit(int nr, volatile unsigned long * address)
 103 {
 104         unsigned long mask;
 105         unsigned long *addr = (unsigned long *) address;
 106         int oldbit;
 107         unsigned long flags;
 108
 109         addr += (nr >> SHIFT_PER_LONG);
 110         mask = 1L << CHOP_SHIFTCOUNT(nr);
 111         _atomic_spin_lock_irqsave(addr, flags);
 112         oldbit = (*addr & mask) ? 1 : 0;
 113         *addr |= mask;
 114         _atomic_spin_unlock_irqrestore(addr, flags);
 115
 116         return oldbit;
 117 }
 118
 119 static __inline__ int __test_and_set_bit(int nr, volatile unsigned long * address)
 120 {
 121         unsigned long mask;
 122         unsigned long *addr = (unsigned long *) address;
 123         int oldbit;
 124
 125         addr += (nr >> SHIFT_PER_LONG);
 126         mask = 1L << CHOP_SHIFTCOUNT(nr);
 127         oldbit = (*addr & mask) ? 1 : 0;
 128         *addr |= mask;
 129
 130         return oldbit;
 131 }
 132
 133 static __inline__ int test_and_clear_bit(int nr, volatile unsigned long * address)
 134 {
 135         unsigned long mask;
 136         unsigned long *addr = (unsigned long *) address;
 137         int oldbit;
 138         unsigned long flags;
 139
 140         addr += (nr >> SHIFT_PER_LONG);
 141         mask = 1L << CHOP_SHIFTCOUNT(nr);
 142         _atomic_spin_lock_irqsave(addr, flags);
 143         oldbit = (*addr & mask) ? 1 : 0;
 144         *addr &= ~mask;
 145         _atomic_spin_unlock_irqrestore(addr, flags);
 146
 147         return oldbit;
 148 }
 149
 150 static __inline__ int __test_and_clear_bit(int nr, volatile unsigned long * address)
 151 {
 152         unsigned long mask;
 153         unsigned long *addr = (unsigned long *) address;
 154         int oldbit;
 155
 156         addr += (nr >> SHIFT_PER_LONG);
 157         mask = 1L << CHOP_SHIFTCOUNT(nr);
 158         oldbit = (*addr & mask) ? 1 : 0;
 159         *addr &= ~mask;
 160
 161         return oldbit;
 162 }
 163
 164 static __inline__ int test_and_change_bit(int nr, volatile unsigned long * address)
 165 {
 166         unsigned long mask;
 167         unsigned long *addr = (unsigned long *) address;
 168         int oldbit;
 169         unsigned long flags;
 170
 171         addr += (nr >> SHIFT_PER_LONG);
 172         mask = 1L << CHOP_SHIFTCOUNT(nr);
 173         _atomic_spin_lock_irqsave(addr, flags);
 174         oldbit = (*addr & mask) ? 1 : 0;
 175         *addr ^= mask;
 176         _atomic_spin_unlock_irqrestore(addr, flags);
 177
 178         return oldbit;
 179 }
 180
 181 static __inline__ int __test_and_change_bit(int nr, volatile unsigned long * address)
 182 {
 183         unsigned long mask;
 184         unsigned long *addr = (unsigned long *) address;
 185         int oldbit;
 186
 187         addr += (nr >> SHIFT_PER_LONG);
 188         mask = 1L << CHOP_SHIFTCOUNT(nr);
 189         oldbit = (*addr & mask) ? 1 : 0;
 190         *addr ^= mask;
 191
 192         return oldbit;
 193 }
 194
 195 static __inline__ int test_bit(int nr, const volatile unsigned long *address)
 196 {
 197         unsigned long mask;
 198         const unsigned long *addr = (const unsigned long *)address;
 199
 200         addr += (nr >> SHIFT_PER_LONG);
 201         mask = 1L << CHOP_SHIFTCOUNT(nr);
 202
 203         return !!(*addr & mask);
 204 }
 205
 206 #ifdef __KERNEL__
 207
 208 /**
 209  * __ffs - find first bit in word. returns 0 to "BITS_PER_LONG-1".
 210  * @word: The word to search
 211  *
 212  * __ffs() return is undefined if no bit is set.
 213  *
 214  * 32-bit fast __ffs by LaMont Jones "lamont At hp com".
 215  * 64-bit enhancement by Grant Grundler "grundler At parisc-linux org".
 216  * (with help from willy/jejb to get the semantics right)
 217  *
 218  * This algorithm avoids branches by making use of nullification.
 219  * One side effect of "extr" instructions is it sets PSW[N] bit.
 220  * How PSW[N] (nullify next insn) gets set is determined by the
 221  * "condition" field (eg "<>" or "TR" below) in the extr* insn.
 222  * Only the 1st and one of either the 2cd or 3rd insn will get executed.
 223  * Each set of 3 insn will get executed in 2 cycles on PA8x00 vs 16 or so
 224  * cycles for each mispredicted branch.
 225  */
 226
 227 static __inline__ unsigned long __ffs(unsigned long x)
 228 {
 229         unsigned long ret;
 230
 231         __asm__(
 232 #if BITS_PER_LONG > 32
 233                 " ldi       63,%1\n"
 234                 " extrd,u,*<>  %0,63,32,%%r0\n"
 235                 " extrd,u,*TR  %0,31,32,%0\n"   /* move top 32-bits down */
 236                 " addi    -32,%1,%1\n"
 237 #else
 238                 " ldi       31,%1\n"
 239 #endif
 240                 " extru,<>  %0,31,16,%%r0\n"
 241                 " extru,TR  %0,15,16,%0\n"      /* xxxx0000 -> 0000xxxx */
 242                 " addi    -16,%1,%1\n"
 243                 " extru,<>  %0,31,8,%%r0\n"
 244                 " extru,TR  %0,23,8,%0\n"       /* 0000xx00 -> 000000xx */
 245                 " addi    -8,%1,%1\n"
 246                 " extru,<>  %0,31,4,%%r0\n"
 247                 " extru,TR  %0,27,4,%0\n"       /* 000000x0 -> 0000000x */
 248                 " addi    -4,%1,%1\n"
 249                 " extru,<>  %0,31,2,%%r0\n"
 250                 " extru,TR  %0,29,2,%0\n"       /* 0000000y, 1100b -> 0011b */
 251                 " addi    -2,%1,%1\n"
 252                 " extru,=  %0,31,1,%%r0\n"      /* check last bit */
 253                 " addi    -1,%1,%1\n"
 254                         : "+r" (x), "=r" (ret) );
 255         return ret;
 256 }
 257
 258 /* Undefined if no bit is zero. */
 259 #define ffz(x)  __ffs(~x)
 260
 261 /*
 262  * ffs: find first bit set. returns 1 to BITS_PER_LONG or 0 (if none set)
 263  * This is defined the same way as the libc and compiler builtin
 264  * ffs routines, therefore differs in spirit from the above ffz (man ffs).
 265  */
 266 static __inline__ int ffs(int x)
 267 {
 268         return x ? (__ffs((unsigned long)x) + 1) : 0;
 269 }
 270
 271 /*
 272  * fls: find last (most significant) bit set.
 273  * fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
 274  */
 275
 276 static __inline__ int fls(int x)
 277 {
 278         int ret;
 279         if (!x)
 280                 return 0;
 281
 282         __asm__(
 283         "       ldi             1,%1\n"
 284         "       extru,<>        %0,15,16,%%r0\n"
 285         "       zdep,TR         %0,15,16,%0\n"          /* xxxx0000 */
 286         "       addi            16,%1,%1\n"
 287         "       extru,<>        %0,7,8,%%r0\n"
 288         "       zdep,TR         %0,23,24,%0\n"          /* xx000000 */
 289         "       addi            8,%1,%1\n"
 290         "       extru,<>        %0,3,4,%%r0\n"
 291         "       zdep,TR         %0,27,28,%0\n"          /* x0000000 */
 292         "       addi            4,%1,%1\n"
 293         "       extru,<>        %0,1,2,%%r0\n"
 294         "       zdep,TR         %0,29,30,%0\n"          /* y0000000 (y&3 = 0) */
 295         "       addi            2,%1,%1\n"
 296         "       extru,=         %0,0,1,%%r0\n"
 297         "       addi            1,%1,%1\n"              /* if y & 8, add 1 */
 298                 : "+r" (x), "=r" (ret) );
 299
 300         return ret;
 301 }
 302
 303 /*
 304  * hweightN: returns the hamming weight (i.e. the number
 305  * of bits set) of a N-bit word
 306  */
 307 #define hweight64(x)                                            \
 308 ({                                                              \
 309         unsigned long __x = (x);                                \
 310         unsigned int __w;                                       \
 311         __w = generic_hweight32((unsigned int) __x);            \
 312         __w += generic_hweight32((unsigned int) (__x>>32));     \
 313         __w;                                                    \
 314 })
 315 #define hweight32(x) generic_hweight32(x)
 316 #define hweight16(x) generic_hweight16(x)
 317 #define hweight8(x) generic_hweight8(x)
 318
 319 /*
 320  * Every architecture must define this function. It's the fastest
 321  * way of searching a 140-bit bitmap where the first 100 bits are
 322  * unlikely to be set. It's guaranteed that at least one of the 140
 323  * bits is cleared.
 324  */
 325 static inline int sched_find_first_bit(const unsigned long *b)
 326 {
 327 #ifndef __LP64__
 328         if (unlikely(b[0]))
 329                 return __ffs(b[0]);
 330         if (unlikely(b[1]))
 331                 return __ffs(b[1]) + 32;
 332         if (unlikely(b[2]))
 333                 return __ffs(b[2]) + 64;
 334         if (b[3])
 335                 return __ffs(b[3]) + 96;
 336         return __ffs(b[4]) + 128;
 337 #else
 338         if (unlikely(b[0]))
 339                 return __ffs(b[0]);
 340         if (unlikely(((unsigned int)b[1])))
 341                 return __ffs(b[1]) + 64;
 342         if (b[1] >> 32)
 343                 return __ffs(b[1] >> 32) + 96;
 344         return __ffs(b[2]) + 128;
 345 #endif
 346 }
 347
 348 #endif /* __KERNEL__ */
 349
 350 /*
 351  * This implementation of find_{first,next}_zero_bit was stolen from
 352  * Linus' asm-alpha/bitops.h.
 353  */
 354 #define find_first_zero_bit(addr, size) \
 355         find_next_zero_bit((addr), (size), 0)
 356
 357 static __inline__ unsigned long find_next_zero_bit(const void * addr, unsigned long size, unsigned long offset)
 358 {
 359         const unsigned long * p = ((unsigned long *) addr) + (offset >> SHIFT_PER_LONG);
 360         unsigned long result = offset & ~(BITS_PER_LONG-1);
 361         unsigned long tmp;
 362
 363         if (offset >= size)
 364                 return size;
 365         size -= result;
 366         offset &= (BITS_PER_LONG-1);
 367         if (offset) {
 368                 tmp = *(p++);
 369                 tmp |= ~0UL >> (BITS_PER_LONG-offset);
 370                 if (size < BITS_PER_LONG)
 371                         goto found_first;
 372                 if (~tmp)
 373                         goto found_middle;
 374                 size -= BITS_PER_LONG;
 375                 result += BITS_PER_LONG;
 376         }
 377         while (size & ~(BITS_PER_LONG -1)) {
 378                 if (~(tmp = *(p++)))
 379                         goto found_middle;
 380                 result += BITS_PER_LONG;
 381                 size -= BITS_PER_LONG;
 382         }
 383         if (!size)
 384                 return result;
 385         tmp = *p;
 386 found_first:
 387         tmp |= ~0UL << size;
 388 found_middle:
 389         return result + ffz(tmp);
 390 }
 391
 392 static __inline__ unsigned long find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset)
 393 {
 394         const unsigned long *p = addr + (offset >> 6);
 395         unsigned long result = offset & ~(BITS_PER_LONG-1);
 396         unsigned long tmp;
 397
 398         if (offset >= size)
 399                 return size;
 400         size -= result;
 401         offset &= (BITS_PER_LONG-1);
 402         if (offset) {
 403                 tmp = *(p++);
 404                 tmp &= (~0UL << offset);
 405                 if (size < BITS_PER_LONG)
 406                         goto found_first;
 407                 if (tmp)
 408                         goto found_middle;
 409                 size -= BITS_PER_LONG;
 410                 result += BITS_PER_LONG;
 411         }
 412         while (size & ~(BITS_PER_LONG-1)) {
 413                 if ((tmp = *(p++)))
 414                         goto found_middle;
 415                 result += BITS_PER_LONG;
 416                 size -= BITS_PER_LONG;
 417         }
 418         if (!size)
 419                 return result;
 420         tmp = *p;
 421
 422 found_first:
 423         tmp &= (~0UL >> (BITS_PER_LONG - size));
 424         if (tmp == 0UL)        /* Are any bits set? */
 425                 return result + size; /* Nope. */
 426 found_middle:
 427         return result + __ffs(tmp);
 428 }
 429
 430 /**
 431  * find_first_bit - find the first set bit in a memory region
 432  * @addr: The address to start the search at
 433  * @size: The maximum size to search
 434  *
 435  * Returns the bit-number of the first set bit, not the number of the byte
 436  * containing a bit.
 437  */
 438 #define find_first_bit(addr, size) \
 439         find_next_bit((addr), (size), 0)
 440
 441 #define _EXT2_HAVE_ASM_BITOPS_
 442
 443 #ifdef __KERNEL__
 444 /*
 445  * test_and_{set,clear}_bit guarantee atomicity without
 446  * disabling interrupts.
 447  */
 448 #ifdef __LP64__
 449 #define ext2_set_bit(nr, addr)          __test_and_set_bit((nr) ^ 0x38, (unsigned long *)addr)
 450 #define ext2_set_bit_atomic(l,nr,addr)  test_and_set_bit((nr) ^ 0x38, (unsigned long *)addr)
 451 #define ext2_clear_bit(nr, addr)        __test_and_clear_bit((nr) ^ 0x38, (unsigned long *)addr)
 452 #define ext2_clear_bit_atomic(l,nr,addr) test_and_clear_bit((nr) ^ 0x38, (unsigned long *)addr)
 453 #else
 454 #define ext2_set_bit(nr, addr)          __test_and_set_bit((nr) ^ 0x18, (unsigned long *)addr)
 455 #define ext2_set_bit_atomic(l,nr,addr)  test_and_set_bit((nr) ^ 0x18, (unsigned long *)addr)
 456 #define ext2_clear_bit(nr, addr)        __test_and_clear_bit((nr) ^ 0x18, (unsigned long *)addr)
 457 #define ext2_clear_bit_atomic(l,nr,addr) test_and_clear_bit((nr) ^ 0x18, (unsigned long *)addr)
 458 #endif
 459
 460 #endif  /* __KERNEL__ */
 461
 462 static __inline__ int ext2_test_bit(int nr, __const__ void * addr)
 463 {
 464         __const__ unsigned char *ADDR = (__const__ unsigned char *) addr;
 465
 466         return (ADDR[nr >> 3] >> (nr & 7)) & 1;
 467 }
 468
 469 /*
 470  * This implementation of ext2_find_{first,next}_zero_bit was stolen from
 471  * Linus' asm-alpha/bitops.h and modified for a big-endian machine.
 472  */
 473
 474 #define ext2_find_first_zero_bit(addr, size) \
 475         ext2_find_next_zero_bit((addr), (size), 0)
 476
 477 extern __inline__ unsigned long ext2_find_next_zero_bit(void *addr,
 478         unsigned long size, unsigned long offset)
 479 {
 480         unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
 481         unsigned int result = offset & ~31UL;
 482         unsigned int tmp;
 483
 484         if (offset >= size)
 485                 return size;
 486         size -= result;
 487         offset &= 31UL;
 488         if (offset) {
 489                 tmp = cpu_to_le32p(p++);
 490                 tmp |= ~0UL >> (32-offset);
 491                 if (size < 32)
 492                         goto found_first;
 493                 if (tmp != ~0U)
 494                         goto found_middle;
 495                 size -= 32;
 496                 result += 32;
 497         }
 498         while (size >= 32) {
 499                 if ((tmp = cpu_to_le32p(p++)) != ~0U)
 500                         goto found_middle;
 501                 result += 32;
 502                 size -= 32;
 503         }
 504         if (!size)
 505                 return result;
 506         tmp = cpu_to_le32p(p);
 507 found_first:
 508         tmp |= ~0U << size;
 509 found_middle:
 510         return result + ffz(tmp);
 511 }
 512
 513 /* Bitmap functions for the minix filesystem.  */
 514 #define minix_test_and_set_bit(nr,addr) ext2_set_bit(nr,addr)
 515 #define minix_set_bit(nr,addr) ((void)ext2_set_bit(nr,addr))
 516 #define minix_test_and_clear_bit(nr,addr) ext2_clear_bit(nr,addr)
 517 #define minix_test_bit(nr,addr) ext2_test_bit(nr,addr)
 518 #define minix_find_first_zero_bit(addr,size) ext2_find_first_zero_bit(addr,size)
 519
 520 #endif /* _PARISC_BITOPS_H */