include/asm-mips/bitops.h

   1 /*
   2  * This file is subject to the terms and conditions of the GNU General Public
   3  * License.  See the file "COPYING" in the main directory of this archive
   4  * for more details.
   5  *
   6  * Copyright (c) 1994 - 1997, 1999, 2000  Ralf Baechle (ralf@gnu.org)
   7  * Copyright (c) 1999, 2000  Silicon Graphics, Inc.
   8  */
   9 #ifndef _ASM_BITOPS_H
  10 #define _ASM_BITOPS_H
  11
  12 #include <linux/config.h>
  13 #include <linux/compiler.h>
  14 #include <linux/types.h>
  15 #include <asm/bug.h>
  16 #include <asm/byteorder.h>              /* sigh ... */
  17 #include <asm/cpu-features.h>
  18
  19 #if (_MIPS_SZLONG == 32)
  20 #define SZLONG_LOG 5
  21 #define SZLONG_MASK 31UL
  22 #define __LL            "ll     "
  23 #define __SC            "sc     "
  24 #define cpu_to_lelongp(x) cpu_to_le32p((__u32 *) (x))
  25 #elif (_MIPS_SZLONG == 64)
  26 #define SZLONG_LOG 6
  27 #define SZLONG_MASK 63UL
  28 #define __LL            "lld    "
  29 #define __SC            "scd    "
  30 #define cpu_to_lelongp(x) cpu_to_le64p((__u64 *) (x))
  31 #endif
  32
  33 #ifdef __KERNEL__
  34
  35 #include <asm/interrupt.h>
  36 #include <asm/sgidefs.h>
  37 #include <asm/war.h>
  38
  39 /*
  40  * clear_bit() doesn't provide any barrier for the compiler.
  41  */
  42 #define smp_mb__before_clear_bit()      smp_mb()
  43 #define smp_mb__after_clear_bit()       smp_mb()
  44
  45 /*
  46  * Only disable interrupt for kernel mode stuff to keep usermode stuff
  47  * that dares to use kernel include files alive.
  48  */
  49
  50 #define __bi_flags                      unsigned long flags
  51 #define __bi_local_irq_save(x)          local_irq_save(x)
  52 #define __bi_local_irq_restore(x)       local_irq_restore(x)
  53 #else
  54 #define __bi_flags
  55 #define __bi_local_irq_save(x)
  56 #define __bi_local_irq_restore(x)
  57 #endif /* __KERNEL__ */
  58
  59 /*
  60  * set_bit - Atomically set a bit in memory
  61  * @nr: the bit to set
  62  * @addr: the address to start counting from
  63  *
  64  * This function is atomic and may not be reordered.  See __set_bit()
  65  * if you do not require the atomic guarantees.
  66  * Note that @nr may be almost arbitrarily large; this function is not
  67  * restricted to acting on a single-word quantity.
  68  */
  69 static inline void set_bit(unsigned long nr, volatile unsigned long *addr)
  70 {
  71         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
  72         unsigned long temp;
  73
  74         if (cpu_has_llsc && R10000_LLSC_WAR) {
  75                 __asm__ __volatile__(
  76                 "       .set    mips3                                   \n"
  77                 "1:     " __LL "%0, %1                  # set_bit       \n"
  78                 "       or      %0, %2                                  \n"
  79                 "       " __SC  "%0, %1                                 \n"
  80                 "       beqzl   %0, 1b                                  \n"
  81                 "       .set    mips0                                   \n"
  82                 : "=&r" (temp), "=m" (*m)
  83                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
  84         } else if (cpu_has_llsc) {
  85                 __asm__ __volatile__(
  86                 "       .set    mips3                                   \n"
  87                 "1:     " __LL "%0, %1                  # set_bit       \n"
  88                 "       or      %0, %2                                  \n"
  89                 "       " __SC  "%0, %1                                 \n"
  90                 "       beqz    %0, 1b                                  \n"
  91                 "       .set    mips0                                   \n"
  92                 : "=&r" (temp), "=m" (*m)
  93                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
  94         } else {
  95                 volatile unsigned long *a = addr;
  96                 unsigned long mask;
  97                 __bi_flags;
  98
  99                 a += nr >> SZLONG_LOG;
 100                 mask = 1UL << (nr & SZLONG_MASK);
 101                 __bi_local_irq_save(flags);
 102                 *a |= mask;
 103                 __bi_local_irq_restore(flags);
 104         }
 105 }
 106
 107 /*
 108  * __set_bit - Set a bit in memory
 109  * @nr: the bit to set
 110  * @addr: the address to start counting from
 111  *
 112  * Unlike set_bit(), this function is non-atomic and may be reordered.
 113  * If it's called on the same region of memory simultaneously, the effect
 114  * may be that only one operation succeeds.
 115  */
 116 static inline void __set_bit(unsigned long nr, volatile unsigned long * addr)
 117 {
 118         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 119
 120         *m |= 1UL << (nr & SZLONG_MASK);
 121 }
 122
 123 /*
 124  * clear_bit - Clears a bit in memory
 125  * @nr: Bit to clear
 126  * @addr: Address to start counting from
 127  *
 128  * clear_bit() is atomic and may not be reordered.  However, it does
 129  * not contain a memory barrier, so if it is used for locking purposes,
 130  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
 131  * in order to ensure changes are visible on other processors.
 132  */
 133 static inline void clear_bit(unsigned long nr, volatile unsigned long *addr)
 134 {
 135         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 136         unsigned long temp;
 137
 138         if (cpu_has_llsc && R10000_LLSC_WAR) {
 139                 __asm__ __volatile__(
 140                 "       .set    mips3                                   \n"
 141                 "1:     " __LL "%0, %1                  # clear_bit     \n"
 142                 "       and     %0, %2                                  \n"
 143                 "       " __SC "%0, %1                                  \n"
 144                 "       beqzl   %0, 1b                                  \n"
 145                 "       .set    mips0                                   \n"
 146                 : "=&r" (temp), "=m" (*m)
 147                 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
 148         } else if (cpu_has_llsc) {
 149                 __asm__ __volatile__(
 150                 "       .set    mips3                                   \n"
 151                 "1:     " __LL "%0, %1                  # clear_bit     \n"
 152                 "       and     %0, %2                                  \n"
 153                 "       " __SC "%0, %1                                  \n"
 154                 "       beqz    %0, 1b                                  \n"
 155                 "       .set    mips0                                   \n"
 156                 : "=&r" (temp), "=m" (*m)
 157                 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
 158         } else {
 159                 volatile unsigned long *a = addr;
 160                 unsigned long mask;
 161                 __bi_flags;
 162
 163                 a += nr >> SZLONG_LOG;
 164                 mask = 1UL << (nr & SZLONG_MASK);
 165                 __bi_local_irq_save(flags);
 166                 *a &= ~mask;
 167                 __bi_local_irq_restore(flags);
 168         }
 169 }
 170
 171 /*
 172  * __clear_bit - Clears a bit in memory
 173  * @nr: Bit to clear
 174  * @addr: Address to start counting from
 175  *
 176  * Unlike clear_bit(), this function is non-atomic and may be reordered.
 177  * If it's called on the same region of memory simultaneously, the effect
 178  * may be that only one operation succeeds.
 179  */
 180 static inline void __clear_bit(unsigned long nr, volatile unsigned long * addr)
 181 {
 182         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 183
 184         *m &= ~(1UL << (nr & SZLONG_MASK));
 185 }
 186
 187 /*
 188  * change_bit - Toggle a bit in memory
 189  * @nr: Bit to change
 190  * @addr: Address to start counting from
 191  *
 192  * change_bit() is atomic and may not be reordered.
 193  * Note that @nr may be almost arbitrarily large; this function is not
 194  * restricted to acting on a single-word quantity.
 195  */
 196 static inline void change_bit(unsigned long nr, volatile unsigned long *addr)
 197 {
 198         if (cpu_has_llsc && R10000_LLSC_WAR) {
 199                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 200                 unsigned long temp;
 201
 202                 __asm__ __volatile__(
 203                 "       .set    mips3                           \n"
 204                 "1:     " __LL "%0, %1          # change_bit    \n"
 205                 "       xor     %0, %2                          \n"
 206                 "       " __SC  "%0, %1                         \n"
 207                 "       beqzl   %0, 1b                          \n"
 208                 "       .set    mips0                           \n"
 209                 : "=&r" (temp), "=m" (*m)
 210                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
 211         } else if (cpu_has_llsc) {
 212                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 213                 unsigned long temp;
 214
 215                 __asm__ __volatile__(
 216                 "       .set    mips3                           \n"
 217                 "1:     " __LL "%0, %1          # change_bit    \n"
 218                 "       xor     %0, %2                          \n"
 219                 "       " __SC  "%0, %1                         \n"
 220                 "       beqz    %0, 1b                          \n"
 221                 "       .set    mips0                           \n"
 222                 : "=&r" (temp), "=m" (*m)
 223                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
 224         } else {
 225                 volatile unsigned long *a = addr;
 226                 unsigned long mask;
 227                 __bi_flags;
 228
 229                 a += nr >> SZLONG_LOG;
 230                 mask = 1UL << (nr & SZLONG_MASK);
 231                 __bi_local_irq_save(flags);
 232                 *a ^= mask;
 233                 __bi_local_irq_restore(flags);
 234         }
 235 }
 236
 237 /*
 238  * __change_bit - Toggle a bit in memory
 239  * @nr: the bit to change
 240  * @addr: the address to start counting from
 241  *
 242  * Unlike change_bit(), this function is non-atomic and may be reordered.
 243  * If it's called on the same region of memory simultaneously, the effect
 244  * may be that only one operation succeeds.
 245  */
 246 static inline void __change_bit(unsigned long nr, volatile unsigned long * addr)
 247 {
 248         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 249
 250         *m ^= 1UL << (nr & SZLONG_MASK);
 251 }
 252
 253 /*
 254  * test_and_set_bit - Set a bit and return its old value
 255  * @nr: Bit to set
 256  * @addr: Address to count from
 257  *
 258  * This operation is atomic and cannot be reordered.
 259  * It also implies a memory barrier.
 260  */
 261 static inline int test_and_set_bit(unsigned long nr,
 262         volatile unsigned long *addr)
 263 {
 264         if (cpu_has_llsc && R10000_LLSC_WAR) {
 265                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 266                 unsigned long temp, res;
 267
 268                 __asm__ __volatile__(
 269                 "       .set    mips3                                   \n"
 270                 "1:     " __LL "%0, %1          # test_and_set_bit      \n"
 271                 "       or      %2, %0, %3                              \n"
 272                 "       " __SC  "%2, %1                                 \n"
 273                 "       beqzl   %2, 1b                                  \n"
 274                 "       and     %2, %0, %3                              \n"
 275 #ifdef CONFIG_SMP
 276                 "       sync                                            \n"
 277 #endif
 278                 "       .set    mips0                                   \n"
 279                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 280                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 281                 : "memory");
 282
 283                 return res != 0;
 284         } else if (cpu_has_llsc) {
 285                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 286                 unsigned long temp, res;
 287
 288                 __asm__ __volatile__(
 289                 "       .set    push                                    \n"
 290                 "       .set    noreorder                               \n"
 291                 "       .set    mips3                                   \n"
 292                 "1:     " __LL "%0, %1          # test_and_set_bit      \n"
 293                 "       or      %2, %0, %3                              \n"
 294                 "       " __SC  "%2, %1                                 \n"
 295                 "       beqz    %2, 1b                                  \n"
 296                 "        and    %2, %0, %3                              \n"
 297 #ifdef CONFIG_SMP
 298                 "       sync                                            \n"
 299 #endif
 300                 "       .set    pop                                     \n"
 301                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 302                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 303                 : "memory");
 304
 305                 return res != 0;
 306         } else {
 307                 volatile unsigned long *a = addr;
 308                 unsigned long mask;
 309                 int retval;
 310                 __bi_flags;
 311
 312                 a += nr >> SZLONG_LOG;
 313                 mask = 1UL << (nr & SZLONG_MASK);
 314                 __bi_local_irq_save(flags);
 315                 retval = (mask & *a) != 0;
 316                 *a |= mask;
 317                 __bi_local_irq_restore(flags);
 318
 319                 return retval;
 320         }
 321 }
 322
 323 /*
 324  * __test_and_set_bit - Set a bit and return its old value
 325  * @nr: Bit to set
 326  * @addr: Address to count from
 327  *
 328  * This operation is non-atomic and can be reordered.
 329  * If two examples of this operation race, one can appear to succeed
 330  * but actually fail.  You must protect multiple accesses with a lock.
 331  */
 332 static inline int __test_and_set_bit(unsigned long nr,
 333         volatile unsigned long *addr)
 334 {
 335         volatile unsigned long *a = addr;
 336         unsigned long mask;
 337         int retval;
 338
 339         a += nr >> SZLONG_LOG;
 340         mask = 1UL << (nr & SZLONG_MASK);
 341         retval = (mask & *a) != 0;
 342         *a |= mask;
 343
 344         return retval;
 345 }
 346
 347 /*
 348  * test_and_clear_bit - Clear a bit and return its old value
 349  * @nr: Bit to clear
 350  * @addr: Address to count from
 351  *
 352  * This operation is atomic and cannot be reordered.
 353  * It also implies a memory barrier.
 354  */
 355 static inline int test_and_clear_bit(unsigned long nr,
 356         volatile unsigned long *addr)
 357 {
 358         if (cpu_has_llsc && R10000_LLSC_WAR) {
 359                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 360                 unsigned long temp, res;
 361
 362                 __asm__ __volatile__(
 363                 "       .set    mips3                                   \n"
 364                 "1:     " __LL  "%0, %1         # test_and_clear_bit    \n"
 365                 "       or      %2, %0, %3                              \n"
 366                 "       xor     %2, %3                                  \n"
 367                 "       " __SC  "%2, %1                                 \n"
 368                 "       beqzl   %2, 1b                                  \n"
 369                 "       and     %2, %0, %3                              \n"
 370 #ifdef CONFIG_SMP
 371                 "       sync                                            \n"
 372 #endif
 373                 "       .set    mips0                                   \n"
 374                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 375                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 376                 : "memory");
 377
 378                 return res != 0;
 379         } else if (cpu_has_llsc) {
 380                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 381                 unsigned long temp, res;
 382
 383                 __asm__ __volatile__(
 384                 "       .set    push                                    \n"
 385                 "       .set    noreorder                               \n"
 386                 "       .set    mips3                                   \n"
 387                 "1:     " __LL  "%0, %1         # test_and_clear_bit    \n"
 388                 "       or      %2, %0, %3                              \n"
 389                 "       xor     %2, %3                                  \n"
 390                 "       " __SC  "%2, %1                                 \n"
 391                 "       beqz    %2, 1b                                  \n"
 392                 "        and    %2, %0, %3                              \n"
 393 #ifdef CONFIG_SMP
 394                 "       sync                                            \n"
 395 #endif
 396                 "       .set    pop                                     \n"
 397                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 398                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 399                 : "memory");
 400
 401                 return res != 0;
 402         } else {
 403                 volatile unsigned long *a = addr;
 404                 unsigned long mask;
 405                 int retval;
 406                 __bi_flags;
 407
 408                 a += nr >> SZLONG_LOG;
 409                 mask = 1UL << (nr & SZLONG_MASK);
 410                 __bi_local_irq_save(flags);
 411                 retval = (mask & *a) != 0;
 412                 *a &= ~mask;
 413                 __bi_local_irq_restore(flags);
 414
 415                 return retval;
 416         }
 417 }
 418
 419 /*
 420  * __test_and_clear_bit - Clear a bit and return its old value
 421  * @nr: Bit to clear
 422  * @addr: Address to count from
 423  *
 424  * This operation is non-atomic and can be reordered.
 425  * If two examples of this operation race, one can appear to succeed
 426  * but actually fail.  You must protect multiple accesses with a lock.
 427  */
 428 static inline int __test_and_clear_bit(unsigned long nr,
 429         volatile unsigned long * addr)
 430 {
 431         volatile unsigned long *a = addr;
 432         unsigned long mask;
 433         int retval;
 434
 435         a += (nr >> SZLONG_LOG);
 436         mask = 1UL << (nr & SZLONG_MASK);
 437         retval = ((mask & *a) != 0);
 438         *a &= ~mask;
 439
 440         return retval;
 441 }
 442
 443 /*
 444  * test_and_change_bit - Change a bit and return its old value
 445  * @nr: Bit to change
 446  * @addr: Address to count from
 447  *
 448  * This operation is atomic and cannot be reordered.
 449  * It also implies a memory barrier.
 450  */
 451 static inline int test_and_change_bit(unsigned long nr,
 452         volatile unsigned long *addr)
 453 {
 454         if (cpu_has_llsc && R10000_LLSC_WAR) {
 455                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 456                 unsigned long temp, res;
 457
 458                 __asm__ __volatile__(
 459                 "       .set    mips3                                   \n"
 460                 "1:     " __LL  "%0, %1         # test_and_change_bit   \n"
 461                 "       xor     %2, %0, %3                              \n"
 462                 "       " __SC  "%2, %1                                 \n"
 463                 "       beqzl   %2, 1b                                  \n"
 464                 "       and     %2, %0, %3                              \n"
 465 #ifdef CONFIG_SMP
 466                 "       sync                                            \n"
 467 #endif
 468                 "       .set    mips0                                   \n"
 469                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 470                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 471                 : "memory");
 472
 473                 return res != 0;
 474         } else if (cpu_has_llsc) {
 475                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 476                 unsigned long temp, res;
 477
 478                 __asm__ __volatile__(
 479                 "       .set    push                                    \n"
 480                 "       .set    noreorder                               \n"
 481                 "       .set    mips3                                   \n"
 482                 "1:     " __LL  "%0, %1         # test_and_change_bit   \n"
 483                 "       xor     %2, %0, %3                              \n"
 484                 "       " __SC  "\t%2, %1                               \n"
 485                 "       beqz    %2, 1b                                  \n"
 486                 "        and    %2, %0, %3                              \n"
 487 #ifdef CONFIG_SMP
 488                 "       sync                                            \n"
 489 #endif
 490                 "       .set    pop                                     \n"
 491                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 492                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 493                 : "memory");
 494
 495                 return res != 0;
 496         } else {
 497                 volatile unsigned long *a = addr;
 498                 unsigned long mask, retval;
 499                 __bi_flags;
 500
 501                 a += nr >> SZLONG_LOG;
 502                 mask = 1UL << (nr & SZLONG_MASK);
 503                 __bi_local_irq_save(flags);
 504                 retval = (mask & *a) != 0;
 505                 *a ^= mask;
 506                 __bi_local_irq_restore(flags);
 507
 508                 return retval;
 509         }
 510 }
 511
 512 /*
 513  * __test_and_change_bit - Change a bit and return its old value
 514  * @nr: Bit to change
 515  * @addr: Address to count from
 516  *
 517  * This operation is non-atomic and can be reordered.
 518  * If two examples of this operation race, one can appear to succeed
 519  * but actually fail.  You must protect multiple accesses with a lock.
 520  */
 521 static inline int __test_and_change_bit(unsigned long nr,
 522         volatile unsigned long *addr)
 523 {
 524         volatile unsigned long *a = addr;
 525         unsigned long mask;
 526         int retval;
 527
 528         a += (nr >> SZLONG_LOG);
 529         mask = 1UL << (nr & SZLONG_MASK);
 530         retval = ((mask & *a) != 0);
 531         *a ^= mask;
 532
 533         return retval;
 534 }
 535
 536 #undef __bi_flags
 537 #undef __bi_local_irq_save
 538 #undef __bi_local_irq_restore
 539
 540 /*
 541  * test_bit - Determine whether a bit is set
 542  * @nr: bit number to test
 543  * @addr: Address to start counting from
 544  */
 545 static inline int test_bit(unsigned long nr, const volatile unsigned long *addr)
 546 {
 547         return 1UL & (addr[nr >> SZLONG_LOG] >> (nr & SZLONG_MASK));
 548 }
 549
 550 /*
 551  * Return the bit position (0..63) of the most significant 1 bit in a word
 552  * Returns -1 if no 1 bit exists
 553  */
 554 static inline int __ilog2(unsigned long x)
 555 {
 556         int lz;
 557
 558         if (sizeof(x) == 4) {
 559                 __asm__ (
 560                 "       .set    push                                    \n"
 561                 "       .set    mips32                                  \n"
 562                 "       clz     %0, %1                                  \n"
 563                 "       .set    pop                                     \n"
 564                 : "=r" (lz)
 565                 : "r" (x));
 566
 567                 return 31 - lz;
 568         }
 569
 570         BUG_ON(sizeof(x) != 8);
 571
 572         __asm__ (
 573         "       .set    push                                            \n"
 574         "       .set    mips64                                          \n"
 575         "       dclz    %0, %1                                          \n"
 576         "       .set    pop                                             \n"
 577         : "=r" (lz)
 578         : "r" (x));
 579
 580         return 63 - lz;
 581 }
 582
 583 /*
 584  * __ffs - find first bit in word.
 585  * @word: The word to search
 586  *
 587  * Returns 0..SZLONG-1
 588  * Undefined if no bit exists, so code should check against 0 first.
 589  */
 590 static inline unsigned long __ffs(unsigned long word)
 591 {
 592 #if defined(CONFIG_CPU_MIPS32) || defined(CONFIG_CPU_MIPS64)
 593         return __ilog2(word & -word);
 594 #else
 595         int b = 0, s;
 596
 597 #ifdef CONFIG_32BIT
 598         s = 16; if (word << 16 != 0) s = 0; b += s; word >>= s;
 599         s =  8; if (word << 24 != 0) s = 0; b += s; word >>= s;
 600         s =  4; if (word << 28 != 0) s = 0; b += s; word >>= s;
 601         s =  2; if (word << 30 != 0) s = 0; b += s; word >>= s;
 602         s =  1; if (word << 31 != 0) s = 0; b += s;
 603
 604         return b;
 605 #endif
 606 #ifdef CONFIG_64BIT
 607         s = 32; if (word << 32 != 0) s = 0; b += s; word >>= s;
 608         s = 16; if (word << 48 != 0) s = 0; b += s; word >>= s;
 609         s =  8; if (word << 56 != 0) s = 0; b += s; word >>= s;
 610         s =  4; if (word << 60 != 0) s = 0; b += s; word >>= s;
 611         s =  2; if (word << 62 != 0) s = 0; b += s; word >>= s;
 612         s =  1; if (word << 63 != 0) s = 0; b += s;
 613
 614         return b;
 615 #endif
 616 #endif
 617 }
 618
 619 /*
 620  * ffs - find first bit set.
 621  * @word: The word to search
 622  *
 623  * Returns 1..SZLONG
 624  * Returns 0 if no bit exists
 625  */
 626
 627 static inline unsigned long ffs(unsigned long word)
 628 {
 629         if (!word)
 630                 return 0;
 631
 632         return __ffs(word) + 1;
 633 }
 634
 635 /*
 636  * ffz - find first zero in word.
 637  * @word: The word to search
 638  *
 639  * Undefined if no zero exists, so code should check against ~0UL first.
 640  */
 641 static inline unsigned long ffz(unsigned long word)
 642 {
 643         return __ffs (~word);
 644 }
 645
 646 /*
 647  * fls - find last bit set.
 648  * @word: The word to search
 649  *
 650  * Returns 1..SZLONG
 651  * Returns 0 if no bit exists
 652  */
 653 static inline unsigned long fls(unsigned long word)
 654 {
 655 #ifdef CONFIG_32BIT
 656 #ifdef CONFIG_CPU_MIPS32
 657         __asm__ ("clz %0, %1" : "=r" (word) : "r" (word));
 658
 659         return 32 - word;
 660 #else
 661         {
 662         int r = 32, s;
 663
 664         if (word == 0)
 665                 return 0;
 666
 667         s = 16; if ((word & 0xffff0000)) s = 0; r -= s; word <<= s;
 668         s = 8;  if ((word & 0xff000000)) s = 0; r -= s; word <<= s;
 669         s = 4;  if ((word & 0xf0000000)) s = 0; r -= s; word <<= s;
 670         s = 2;  if ((word & 0xc0000000)) s = 0; r -= s; word <<= s;
 671         s = 1;  if ((word & 0x80000000)) s = 0; r -= s;
 672
 673         return r;
 674         }
 675 #endif
 676 #endif /* CONFIG_32BIT */
 677
 678 #ifdef CONFIG_64BIT
 679 #ifdef CONFIG_CPU_MIPS64
 680
 681         __asm__ ("dclz %0, %1" : "=r" (word) : "r" (word));
 682
 683         return 64 - word;
 684 #else
 685         {
 686         int r = 64, s;
 687
 688         if (word == 0)
 689                 return 0;
 690
 691         s = 32; if ((word & 0xffffffff00000000UL)) s = 0; r -= s; word <<= s;
 692         s = 16; if ((word & 0xffff000000000000UL)) s = 0; r -= s; word <<= s;
 693         s = 8;  if ((word & 0xff00000000000000UL)) s = 0; r -= s; word <<= s;
 694         s = 4;  if ((word & 0xf000000000000000UL)) s = 0; r -= s; word <<= s;
 695         s = 2;  if ((word & 0xc000000000000000UL)) s = 0; r -= s; word <<= s;
 696         s = 1;  if ((word & 0x8000000000000000UL)) s = 0; r -= s;
 697
 698         return r;
 699         }
 700 #endif
 701 #endif /* CONFIG_64BIT */
 702 }
 703
 704 #define fls64(x)   generic_fls64(x)
 705
 706 /*
 707  * find_next_zero_bit - find the first zero bit in a memory region
 708  * @addr: The address to base the search on
 709  * @offset: The bitnumber to start searching at
 710  * @size: The maximum size to search
 711  */
 712 static inline unsigned long find_next_zero_bit(const unsigned long *addr,
 713         unsigned long size, unsigned long offset)
 714 {
 715         const unsigned long *p = addr + (offset >> SZLONG_LOG);
 716         unsigned long result = offset & ~SZLONG_MASK;
 717         unsigned long tmp;
 718
 719         if (offset >= size)
 720                 return size;
 721         size -= result;
 722         offset &= SZLONG_MASK;
 723         if (offset) {
 724                 tmp = *(p++);
 725                 tmp |= ~0UL >> (_MIPS_SZLONG-offset);
 726                 if (size < _MIPS_SZLONG)
 727                         goto found_first;
 728                 if (~tmp)
 729                         goto found_middle;
 730                 size -= _MIPS_SZLONG;
 731                 result += _MIPS_SZLONG;
 732         }
 733         while (size & ~SZLONG_MASK) {
 734                 if (~(tmp = *(p++)))
 735                         goto found_middle;
 736                 result += _MIPS_SZLONG;
 737                 size -= _MIPS_SZLONG;
 738         }
 739         if (!size)
 740                 return result;
 741         tmp = *p;
 742
 743 found_first:
 744         tmp |= ~0UL << size;
 745         if (tmp == ~0UL)                /* Are any bits zero? */
 746                 return result + size;   /* Nope. */
 747 found_middle:
 748         return result + ffz(tmp);
 749 }
 750
 751 #define find_first_zero_bit(addr, size) \
 752         find_next_zero_bit((addr), (size), 0)
 753
 754 /*
 755  * find_next_bit - find the next set bit in a memory region
 756  * @addr: The address to base the search on
 757  * @offset: The bitnumber to start searching at
 758  * @size: The maximum size to search
 759  */
 760 static inline unsigned long find_next_bit(const unsigned long *addr,
 761         unsigned long size, unsigned long offset)
 762 {
 763         const unsigned long *p = addr + (offset >> SZLONG_LOG);
 764         unsigned long result = offset & ~SZLONG_MASK;
 765         unsigned long tmp;
 766
 767         if (offset >= size)
 768                 return size;
 769         size -= result;
 770         offset &= SZLONG_MASK;
 771         if (offset) {
 772                 tmp = *(p++);
 773                 tmp &= ~0UL << offset;
 774                 if (size < _MIPS_SZLONG)
 775                         goto found_first;
 776                 if (tmp)
 777                         goto found_middle;
 778                 size -= _MIPS_SZLONG;
 779                 result += _MIPS_SZLONG;
 780         }
 781         while (size & ~SZLONG_MASK) {
 782                 if ((tmp = *(p++)))
 783                         goto found_middle;
 784                 result += _MIPS_SZLONG;
 785                 size -= _MIPS_SZLONG;
 786         }
 787         if (!size)
 788                 return result;
 789         tmp = *p;
 790
 791 found_first:
 792         tmp &= ~0UL >> (_MIPS_SZLONG - size);
 793         if (tmp == 0UL)                 /* Are any bits set? */
 794                 return result + size;   /* Nope. */
 795 found_middle:
 796         return result + __ffs(tmp);
 797 }
 798
 799 /*
 800  * find_first_bit - find the first set bit in a memory region
 801  * @addr: The address to start the search at
 802  * @size: The maximum size to search
 803  *
 804  * Returns the bit-number of the first set bit, not the number of the byte
 805  * containing a bit.
 806  */
 807 #define find_first_bit(addr, size) \
 808         find_next_bit((addr), (size), 0)
 809
 810 #ifdef __KERNEL__
 811
 812 /*
 813  * Every architecture must define this function. It's the fastest
 814  * way of searching a 140-bit bitmap where the first 100 bits are
 815  * unlikely to be set. It's guaranteed that at least one of the 140
 816  * bits is cleared.
 817  */
 818 static inline int sched_find_first_bit(const unsigned long *b)
 819 {
 820 #ifdef CONFIG_32BIT
 821         if (unlikely(b[0]))
 822                 return __ffs(b[0]);
 823         if (unlikely(b[1]))
 824                 return __ffs(b[1]) + 32;
 825         if (unlikely(b[2]))
 826                 return __ffs(b[2]) + 64;
 827         if (b[3])
 828                 return __ffs(b[3]) + 96;
 829         return __ffs(b[4]) + 128;
 830 #endif
 831 #ifdef CONFIG_64BIT
 832         if (unlikely(b[0]))
 833                 return __ffs(b[0]);
 834         if (unlikely(b[1]))
 835                 return __ffs(b[1]) + 64;
 836         return __ffs(b[2]) + 128;
 837 #endif
 838 }
 839
 840 /*
 841  * hweightN - returns the hamming weight of a N-bit word
 842  * @x: the word to weigh
 843  *
 844  * The Hamming Weight of a number is the total number of bits set in it.
 845  */
 846
 847 #define hweight64(x)    generic_hweight64(x)
 848 #define hweight32(x)    generic_hweight32(x)
 849 #define hweight16(x)    generic_hweight16(x)
 850 #define hweight8(x)     generic_hweight8(x)
 851
 852 static inline int __test_and_set_le_bit(unsigned long nr, unsigned long *addr)
 853 {
 854         unsigned char   *ADDR = (unsigned char *) addr;
 855         int             mask, retval;
 856
 857         ADDR += nr >> 3;
 858         mask = 1 << (nr & 0x07);
 859         retval = (mask & *ADDR) != 0;
 860         *ADDR |= mask;
 861
 862         return retval;
 863 }
 864
 865 static inline int __test_and_clear_le_bit(unsigned long nr, unsigned long *addr)
 866 {
 867         unsigned char   *ADDR = (unsigned char *) addr;
 868         int             mask, retval;
 869
 870         ADDR += nr >> 3;
 871         mask = 1 << (nr & 0x07);
 872         retval = (mask & *ADDR) != 0;
 873         *ADDR &= ~mask;
 874
 875         return retval;
 876 }
 877
 878 static inline int test_le_bit(unsigned long nr, const unsigned long * addr)
 879 {
 880         const unsigned char     *ADDR = (const unsigned char *) addr;
 881         int                     mask;
 882
 883         ADDR += nr >> 3;
 884         mask = 1 << (nr & 0x07);
 885
 886         return ((mask & *ADDR) != 0);
 887 }
 888
 889 static inline unsigned long find_next_zero_le_bit(unsigned long *addr,
 890         unsigned long size, unsigned long offset)
 891 {
 892         unsigned long *p = ((unsigned long *) addr) + (offset >> SZLONG_LOG);
 893         unsigned long result = offset & ~SZLONG_MASK;
 894         unsigned long tmp;
 895
 896         if (offset >= size)
 897                 return size;
 898         size -= result;
 899         offset &= SZLONG_MASK;
 900         if (offset) {
 901                 tmp = cpu_to_lelongp(p++);
 902                 tmp |= ~0UL >> (_MIPS_SZLONG-offset); /* bug or feature ? */
 903                 if (size < _MIPS_SZLONG)
 904                         goto found_first;
 905                 if (~tmp)
 906                         goto found_middle;
 907                 size -= _MIPS_SZLONG;
 908                 result += _MIPS_SZLONG;
 909         }
 910         while (size & ~SZLONG_MASK) {
 911                 if (~(tmp = cpu_to_lelongp(p++)))
 912                         goto found_middle;
 913                 result += _MIPS_SZLONG;
 914                 size -= _MIPS_SZLONG;
 915         }
 916         if (!size)
 917                 return result;
 918         tmp = cpu_to_lelongp(p);
 919
 920 found_first:
 921         tmp |= ~0UL << size;
 922         if (tmp == ~0UL)                /* Are any bits zero? */
 923                 return result + size;   /* Nope. */
 924
 925 found_middle:
 926         return result + ffz(tmp);
 927 }
 928
 929 #define find_first_zero_le_bit(addr, size) \
 930         find_next_zero_le_bit((addr), (size), 0)
 931
 932 #define ext2_set_bit(nr,addr) \
 933         __test_and_set_le_bit((nr),(unsigned long*)addr)
 934 #define ext2_clear_bit(nr, addr) \
 935         __test_and_clear_le_bit((nr),(unsigned long*)addr)
 936  #define ext2_set_bit_atomic(lock, nr, addr)            \
 937 ({                                                      \
 938         int ret;                                        \
 939         spin_lock(lock);                                \
 940         ret = ext2_set_bit((nr), (addr));               \
 941         spin_unlock(lock);                              \
 942         ret;                                            \
 943 })
 944
 945 #define ext2_clear_bit_atomic(lock, nr, addr)           \
 946 ({                                                      \
 947         int ret;                                        \
 948         spin_lock(lock);                                \
 949         ret = ext2_clear_bit((nr), (addr));             \
 950         spin_unlock(lock);                              \
 951         ret;                                            \
 952 })
 953 #define ext2_test_bit(nr, addr) test_le_bit((nr),(unsigned long*)addr)
 954 #define ext2_find_first_zero_bit(addr, size) \
 955         find_first_zero_le_bit((unsigned long*)addr, size)
 956 #define ext2_find_next_zero_bit(addr, size, off) \
 957         find_next_zero_le_bit((unsigned long*)addr, size, off)
 958
 959 /*
 960  * Bitmap functions for the minix filesystem.
 961  *
 962  * FIXME: These assume that Minix uses the native byte/bitorder.
 963  * This limits the Minix filesystem's value for data exchange very much.
 964  */
 965 #define minix_test_and_set_bit(nr,addr) test_and_set_bit(nr,addr)
 966 #define minix_set_bit(nr,addr) set_bit(nr,addr)
 967 #define minix_test_and_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
 968 #define minix_test_bit(nr,addr) test_bit(nr,addr)
 969 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
 970
 971 #endif /* __KERNEL__ */
 972
 973 #endif /* _ASM_BITOPS_H */