include/asm-mips/bitops.h

   1 /*
   2  * include/asm-mips/bitops.h
   3  *
   4  * This file is subject to the terms and conditions of the GNU General Public
   5  * License.  See the file "COPYING" in the main directory of this archive
   6  * for more details.
   7  *
   8  * Copyright (c) 1994 - 1997  Ralf Baechle (ralf@gnu.org)
   9  */
  10 #ifndef __ASM_MIPS_BITOPS_H
  11 #define __ASM_MIPS_BITOPS_H
  12
  13 #include <linux/types.h>
  14 #include <linux/byteorder/swab.h>               /* sigh ... */
  15
  16 #ifdef __KERNEL__
  17
  18 #include <asm/sgidefs.h>
  19 #include <asm/system.h>
  20
  21 /*
  22  * Only disable interrupt for kernel mode stuff to keep usermode stuff
  23  * that dares to use kernel include files alive.
  24  */
  25 #define __bi_flags unsigned long flags
  26 #define __bi_cli() __cli()
  27 #define __bi_save_flags(x) __save_flags(x)
  28 #define __bi_restore_flags(x) __restore_flags(x)
  29 #else
  30 #define __bi_flags
  31 #define __bi_cli()
  32 #define __bi_save_flags(x)
  33 #define __bi_restore_flags(x)
  34 #endif /* __KERNEL__ */
  35
  36 /*
  37  * Note that the bit operations are defined on arrays of 32 bit sized
  38  * elements.  With respect to a future 64 bit implementation it is
  39  * wrong to use long *.  Use u32 * or int *.
  40  */
  41 extern __inline__ void set_bit(int nr, void *addr);
  42 extern __inline__ void clear_bit(int nr, void *addr);
  43 extern __inline__ void change_bit(int nr, void *addr);
  44 extern __inline__ int test_and_set_bit(int nr, void *addr);
  45 extern __inline__ int test_and_clear_bit(int nr, void *addr);
  46 extern __inline__ int test_and_change_bit(int nr, void *addr);
  47
  48 extern __inline__ int test_bit(int nr, const void *addr);
  49 #ifndef __MIPSEB__
  50 extern __inline__ int find_first_zero_bit (void *addr, unsigned size);
  51 #endif
  52 extern __inline__ int find_next_zero_bit (void * addr, int size, int offset);
  53 extern __inline__ unsigned long ffz(unsigned long word);
  54
  55 #if (_MIPS_ISA == _MIPS_ISA_MIPS2) || (_MIPS_ISA == _MIPS_ISA_MIPS3) || \
  56     (_MIPS_ISA == _MIPS_ISA_MIPS4) || (_MIPS_ISA == _MIPS_ISA_MIPS5)
  57
  58 /*
  59  * These functions for MIPS ISA > 1 are interrupt and SMP proof and
  60  * interrupt friendly
  61  */
  62 #include <asm/mipsregs.h>
  63
  64 /*
  65  * The following functions will only work for the R4000!
  66  */
  67
  68 extern __inline__ void set_bit(int nr, void *addr)
  69 {
  70         int     mask, mw;
  71
  72         addr += ((nr >> 3) & ~3);
  73         mask = 1 << (nr & 0x1f);
  74         do {
  75                 mw = load_linked(addr);
  76         } while (!store_conditional(addr, mw|mask));
  77 }
  78
  79 extern __inline__ void clear_bit(int nr, void *addr)
  80 {
  81         int     mask, mw;
  82
  83         addr += ((nr >> 3) & ~3);
  84         mask = 1 << (nr & 0x1f);
  85         do {
  86                 mw = load_linked(addr);
  87                 }
  88         while (!store_conditional(addr, mw & ~mask));
  89 }
  90
  91 extern __inline__ void change_bit(int nr, void *addr)
  92 {
  93         int     mask, mw;
  94
  95         addr += ((nr >> 3) & ~3);
  96         mask = 1 << (nr & 0x1f);
  97         do {
  98                 mw = load_linked(addr);
  99         } while (!store_conditional(addr, mw ^ mask));
 100 }
 101
 102 extern __inline__ int test_and_set_bit(int nr, void *addr)
 103 {
 104         int     mask, retval, mw;
 105
 106         addr += ((nr >> 3) & ~3);
 107         mask = 1 << (nr & 0x1f);
 108         do {
 109                 mw = load_linked(addr);
 110                 retval = (mask & mw) != 0;
 111         } while (!store_conditional(addr, mw|mask));
 112
 113         return retval;
 114 }
 115
 116 extern __inline__ int test_and_clear_bit(int nr, void *addr)
 117 {
 118         int     mask, retval, mw;
 119
 120         addr += ((nr >> 3) & ~3);
 121         mask = 1 << (nr & 0x1f);
 122         do {
 123                 mw = load_linked(addr);
 124                 retval = (mask & mw) != 0;
 125                 }
 126         while (!store_conditional(addr, mw & ~mask));
 127
 128         return retval;
 129 }
 130
 131 extern __inline__ int test_and_change_bit(int nr, void *addr)
 132 {
 133         int     mask, retval, mw;
 134
 135         addr += ((nr >> 3) & ~3);
 136         mask = 1 << (nr & 0x1f);
 137         do {
 138                 mw = load_linked(addr);
 139                 retval = (mask & mw) != 0;
 140         } while (!store_conditional(addr, mw ^ mask));
 141
 142         return retval;
 143 }
 144
 145 #else /* MIPS I */
 146
 147 extern __inline__ void set_bit(int nr, void * addr)
 148 {
 149         int     mask;
 150         int     *a = addr;
 151         __bi_flags;
 152
 153         a += nr >> 5;
 154         mask = 1 << (nr & 0x1f);
 155         __bi_save_flags(flags);
 156         __bi_cli();
 157         *a |= mask;
 158         __bi_restore_flags(flags);
 159 }
 160
 161 extern __inline__ void clear_bit(int nr, void * addr)
 162 {
 163         int     mask;
 164         int     *a = addr;
 165         __bi_flags;
 166
 167         a += nr >> 5;
 168         mask = 1 << (nr & 0x1f);
 169         __bi_save_flags(flags);
 170         __bi_cli();
 171         *a &= ~mask;
 172         __bi_restore_flags(flags);
 173 }
 174
 175 extern __inline__ void change_bit(int nr, void * addr)
 176 {
 177         int     mask;
 178         int     *a = addr;
 179         __bi_flags;
 180
 181         a += nr >> 5;
 182         mask = 1 << (nr & 0x1f);
 183         __bi_save_flags(flags);
 184         __bi_cli();
 185         *a ^= mask;
 186         __bi_restore_flags(flags);
 187 }
 188
 189 extern __inline__ int test_and_set_bit(int nr, void * addr)
 190 {
 191         int     mask, retval;
 192         int     *a = addr;
 193         __bi_flags;
 194
 195         a += nr >> 5;
 196         mask = 1 << (nr & 0x1f);
 197         __bi_save_flags(flags);
 198         __bi_cli();
 199         retval = (mask & *a) != 0;
 200         *a |= mask;
 201         __bi_restore_flags(flags);
 202
 203         return retval;
 204 }
 205
 206 extern __inline__ int test_and_clear_bit(int nr, void * addr)
 207 {
 208         int     mask, retval;
 209         int     *a = addr;
 210         __bi_flags;
 211
 212         a += nr >> 5;
 213         mask = 1 << (nr & 0x1f);
 214         __bi_save_flags(flags);
 215         __bi_cli();
 216         retval = (mask & *a) != 0;
 217         *a &= ~mask;
 218         __bi_restore_flags(flags);
 219
 220         return retval;
 221 }
 222
 223 extern __inline__ int test_and_change_bit(int nr, void * addr)
 224 {
 225         int     mask, retval;
 226         int     *a = addr;
 227         __bi_flags;
 228
 229         a += nr >> 5;
 230         mask = 1 << (nr & 0x1f);
 231         __bi_save_flags(flags);
 232         __bi_cli();
 233         retval = (mask & *a) != 0;
 234         *a ^= mask;
 235         __bi_restore_flags(flags);
 236
 237         return retval;
 238 }
 239
 240 #undef __bi_flags
 241 #undef __bi_cli()
 242 #undef __bi_save_flags(x)
 243 #undef __bi_restore_flags(x)
 244
 245 #endif /* MIPS I */
 246
 247 extern __inline__ int test_bit(int nr, const void *addr)
 248 {
 249         return ((1UL << (nr & 31)) & (((const unsigned int *) addr)[nr >> 5])) != 0;
 250 }
 251
 252 #ifndef __MIPSEB__
 253
 254 /* Little endian versions. */
 255
 256 extern __inline__ int find_first_zero_bit (void *addr, unsigned size)
 257 {
 258         unsigned long dummy;
 259         int res;
 260
 261         if (!size)
 262                 return 0;
 263
 264         __asm__ (".set\tnoreorder\n\t"
 265                 ".set\tnoat\n"
 266                 "1:\tsubu\t$1,%6,%0\n\t"
 267                 "blez\t$1,2f\n\t"
 268                 "lw\t$1,(%5)\n\t"
 269                 "addiu\t%5,4\n\t"
 270 #if (_MIPS_ISA == _MIPS_ISA_MIPS2) || (_MIPS_ISA == _MIPS_ISA_MIPS3) || \
 271     (_MIPS_ISA == _MIPS_ISA_MIPS4) || (_MIPS_ISA == _MIPS_ISA_MIPS5)
 272                 "beql\t%1,$1,1b\n\t"
 273                 "addiu\t%0,32\n\t"
 274 #else
 275                 "addiu\t%0,32\n\t"
 276                 "beq\t%1,$1,1b\n\t"
 277                 "nop\n\t"
 278                 "subu\t%0,32\n\t"
 279 #endif
 280 #ifdef __MIPSEB__
 281 #error "Fix this for big endian"
 282 #endif /* __MIPSEB__ */
 283                 "li\t%1,1\n"
 284                 "1:\tand\t%2,$1,%1\n\t"
 285                 "beqz\t%2,2f\n\t"
 286                 "sll\t%1,%1,1\n\t"
 287                 "bnez\t%1,1b\n\t"
 288                 "add\t%0,%0,1\n\t"
 289                 ".set\tat\n\t"
 290                 ".set\treorder\n"
 291                 "2:"
 292                 : "=r" (res),
 293                   "=r" (dummy),
 294                   "=r" (addr)
 295                 : "0" ((signed int) 0),
 296                   "1" ((unsigned int) 0xffffffff),
 297                   "2" (addr),
 298                   "r" (size)
 299                 : "$1");
 300
 301         return res;
 302 }
 303
 304 extern __inline__ int find_next_zero_bit (void * addr, int size, int offset)
 305 {
 306         unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
 307         int set = 0, bit = offset & 31, res;
 308         unsigned long dummy;
 309
 310         if (bit) {
 311                 /*
 312                  * Look for zero in first byte
 313                  */
 314 #ifdef __MIPSEB__
 315 #error "Fix this for big endian byte order"
 316 #endif
 317                 __asm__(".set\tnoreorder\n\t"
 318                         ".set\tnoat\n"
 319                         "1:\tand\t$1,%4,%1\n\t"
 320                         "beqz\t$1,1f\n\t"
 321                         "sll\t%1,%1,1\n\t"
 322                         "bnez\t%1,1b\n\t"
 323                         "addiu\t%0,1\n\t"
 324                         ".set\tat\n\t"
 325                         ".set\treorder\n"
 326                         "1:"
 327                         : "=r" (set),
 328                           "=r" (dummy)
 329                         : "0" (0),
 330                           "1" (1 << bit),
 331                           "r" (*p)
 332                         : "$1");
 333                 if (set < (32 - bit))
 334                         return set + offset;
 335                 set = 32 - bit;
 336                 p++;
 337         }
 338         /*
 339          * No zero yet, search remaining full bytes for a zero
 340          */
 341         res = find_first_zero_bit(p, size - 32 * (p - (unsigned int *) addr));
 342         return offset + set + res;
 343 }
 344
 345 #endif /* !(__MIPSEB__) */
 346
 347 /*
 348  * ffz = Find First Zero in word. Undefined if no zero exists,
 349  * so code should check against ~0UL first..
 350  */
 351 extern __inline__ unsigned long ffz(unsigned long word)
 352 {
 353         unsigned int    __res;
 354         unsigned int    mask = 1;
 355
 356         __asm__ (
 357                 ".set\tnoreorder\n\t"
 358                 ".set\tnoat\n\t"
 359                 "move\t%0,$0\n"
 360                 "1:\tand\t$1,%2,%1\n\t"
 361                 "beqz\t$1,2f\n\t"
 362                 "sll\t%1,1\n\t"
 363                 "bnez\t%1,1b\n\t"
 364                 "addiu\t%0,1\n\t"
 365                 ".set\tat\n\t"
 366                 ".set\treorder\n"
 367                 "2:\n\t"
 368                 : "=&r" (__res), "=r" (mask)
 369                 : "r" (word), "1" (mask)
 370                 : "$1");
 371
 372         return __res;
 373 }
 374
 375 #ifdef __KERNEL__
 376
 377 /*
 378  * ffs: find first bit set. This is defined the same way as
 379  * the libc and compiler builtin ffs routines, therefore
 380  * differs in spirit from the above ffz (man ffs).
 381  */
 382
 383 #define ffs(x) generic_ffs(x)
 384
 385 /*
 386  * hweightN: returns the hamming weight (i.e. the number
 387  * of bits set) of a N-bit word
 388  */
 389
 390 #define hweight32(x) generic_hweight32(x)
 391 #define hweight16(x) generic_hweight16(x)
 392 #define hweight8(x) generic_hweight8(x)
 393
 394 #endif /* __KERNEL__ */
 395
 396 #ifdef __MIPSEB__
 397 /* For now I steal the Sparc C versions, no need for speed, just need to
 398  * get it working.
 399  */
 400 /* find_next_zero_bit() finds the first zero bit in a bit string of length
 401  * 'size' bits, starting the search at bit 'offset'. This is largely based
 402  * on Linus's ALPHA routines, which are pretty portable BTW.
 403  */
 404
 405 extern __inline__ int find_next_zero_bit(void *addr, int size, int offset)
 406 {
 407         unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
 408         unsigned long result = offset & ~31UL;
 409         unsigned long tmp;
 410
 411         if (offset >= size)
 412                 return size;
 413         size -= result;
 414         offset &= 31UL;
 415         if (offset) {
 416                 tmp = *(p++);
 417                 tmp |= ~0UL >> (32-offset);
 418                 if (size < 32)
 419                         goto found_first;
 420                 if (~tmp)
 421                         goto found_middle;
 422                 size -= 32;
 423                 result += 32;
 424         }
 425         while (size & ~31UL) {
 426                 if (~(tmp = *(p++)))
 427                         goto found_middle;
 428                 result += 32;
 429                 size -= 32;
 430         }
 431         if (!size)
 432                 return result;
 433         tmp = *p;
 434
 435 found_first:
 436         tmp |= ~0UL << size;
 437 found_middle:
 438         return result + ffz(tmp);
 439 }
 440
 441 /* Linus sez that gcc can optimize the following correctly, we'll see if this
 442  * holds on the Sparc as it does for the ALPHA.
 443  */
 444
 445 #define find_first_zero_bit(addr, size) \
 446         find_next_zero_bit((addr), (size), 0)
 447
 448 #endif /* (__MIPSEB__) */
 449
 450 /* Now for the ext2 filesystem bit operations and helper routines. */
 451
 452 #ifdef __MIPSEB__
 453 extern __inline__ int ext2_set_bit(int nr,void * addr)
 454 {
 455         int             mask, retval, flags;
 456         unsigned char   *ADDR = (unsigned char *) addr;
 457
 458         ADDR += nr >> 3;
 459         mask = 1 << (nr & 0x07);
 460         save_flags(flags); cli();
 461         retval = (mask & *ADDR) != 0;
 462         *ADDR |= mask;
 463         restore_flags(flags);
 464         return retval;
 465 }
 466
 467 extern __inline__ int ext2_clear_bit(int nr, void * addr)
 468 {
 469         int             mask, retval, flags;
 470         unsigned char   *ADDR = (unsigned char *) addr;
 471
 472         ADDR += nr >> 3;
 473         mask = 1 << (nr & 0x07);
 474         save_flags(flags); cli();
 475         retval = (mask & *ADDR) != 0;
 476         *ADDR &= ~mask;
 477         restore_flags(flags);
 478         return retval;
 479 }
 480
 481 extern __inline__ int ext2_test_bit(int nr, const void * addr)
 482 {
 483         int                     mask;
 484         const unsigned char     *ADDR = (const unsigned char *) addr;
 485
 486         ADDR += nr >> 3;
 487         mask = 1 << (nr & 0x07);
 488         return ((mask & *ADDR) != 0);
 489 }
 490
 491 #define ext2_find_first_zero_bit(addr, size) \
 492         ext2_find_next_zero_bit((addr), (size), 0)
 493
 494 extern __inline__ unsigned long ext2_find_next_zero_bit(void *addr, unsigned long size, unsigned long offset)
 495 {
 496         unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
 497         unsigned long result = offset & ~31UL;
 498         unsigned long tmp;
 499
 500         if (offset >= size)
 501                 return size;
 502         size -= result;
 503         offset &= 31UL;
 504         if(offset) {
 505                 /* We hold the little endian value in tmp, but then the
 506                  * shift is illegal. So we could keep a big endian value
 507                  * in tmp, like this:
 508                  *
 509                  * tmp = __swab32(*(p++));
 510                  * tmp |= ~0UL >> (32-offset);
 511                  *
 512                  * but this would decrease preformance, so we change the
 513                  * shift:
 514                  */
 515                 tmp = *(p++);
 516                 tmp |= __swab32(~0UL >> (32-offset));
 517                 if(size < 32)
 518                         goto found_first;
 519                 if(~tmp)
 520                         goto found_middle;
 521                 size -= 32;
 522                 result += 32;
 523         }
 524         while(size & ~31UL) {
 525                 if(~(tmp = *(p++)))
 526                         goto found_middle;
 527                 result += 32;
 528                 size -= 32;
 529         }
 530         if(!size)
 531                 return result;
 532         tmp = *p;
 533
 534 found_first:
 535         /* tmp is little endian, so we would have to swab the shift,
 536          * see above. But then we have to swab tmp below for ffz, so
 537          * we might as well do this here.
 538          */
 539         return result + ffz(__swab32(tmp) | (~0UL << size));
 540 found_middle:
 541         return result + ffz(__swab32(tmp));
 542 }
 543 #else /* !(__MIPSEB__) */
 544
 545 /* Native ext2 byte ordering, just collapse using defines. */
 546 #define ext2_set_bit(nr, addr) test_and_set_bit((nr), (addr))
 547 #define ext2_clear_bit(nr, addr) test_and_clear_bit((nr), (addr))
 548 #define ext2_test_bit(nr, addr) test_bit((nr), (addr))
 549 #define ext2_find_first_zero_bit(addr, size) find_first_zero_bit((addr), (size))
 550 #define ext2_find_next_zero_bit(addr, size, offset) \
 551                 find_next_zero_bit((addr), (size), (offset))
 552
 553 #endif /* !(__MIPSEB__) */
 554
 555 /*
 556  * Bitmap functions for the minix filesystem.
 557  * FIXME: These assume that Minix uses the native byte/bitorder.
 558  * This limits the Minix filesystem's value for data exchange very much.
 559  */
 560 #define minix_set_bit(nr,addr) test_and_set_bit(nr,addr)
 561 #define minix_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
 562 #define minix_test_bit(nr,addr) test_bit(nr,addr)
 563 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
 564
 565 #endif /* __ASM_MIPS_BITOPS_H */