include/asm-m68knommu/bitops.h

   1 #ifndef _M68KNOMMU_BITOPS_H
   2 #define _M68KNOMMU_BITOPS_H
   3
   4 /*
   5  * Copyright 1992, Linus Torvalds.
   6  */
   7
   8 #include <linux/config.h>
   9 #include <linux/compiler.h>
  10 #include <asm/byteorder.h>      /* swab32 */
  11 #include <asm/system.h>         /* save_flags */
  12
  13 #ifdef __KERNEL__
  14
  15 /*
  16  *      Generic ffs().
  17  */
  18 static inline int ffs(int x)
  19 {
  20         int r = 1;
  21
  22         if (!x)
  23                 return 0;
  24         if (!(x & 0xffff)) {
  25                 x >>= 16;
  26                 r += 16;
  27         }
  28         if (!(x & 0xff)) {
  29                 x >>= 8;
  30                 r += 8;
  31         }
  32         if (!(x & 0xf)) {
  33                 x >>= 4;
  34                 r += 4;
  35         }
  36         if (!(x & 3)) {
  37                 x >>= 2;
  38                 r += 2;
  39         }
  40         if (!(x & 1)) {
  41                 x >>= 1;
  42                 r += 1;
  43         }
  44         return r;
  45 }
  46
  47 /*
  48  *      Generic __ffs().
  49  */
  50 static inline int __ffs(int x)
  51 {
  52         int r = 0;
  53
  54         if (!x)
  55                 return 0;
  56         if (!(x & 0xffff)) {
  57                 x >>= 16;
  58                 r += 16;
  59         }
  60         if (!(x & 0xff)) {
  61                 x >>= 8;
  62                 r += 8;
  63         }
  64         if (!(x & 0xf)) {
  65                 x >>= 4;
  66                 r += 4;
  67         }
  68         if (!(x & 3)) {
  69                 x >>= 2;
  70                 r += 2;
  71         }
  72         if (!(x & 1)) {
  73                 x >>= 1;
  74                 r += 1;
  75         }
  76         return r;
  77 }
  78
  79 /*
  80  * Every architecture must define this function. It's the fastest
  81  * way of searching a 140-bit bitmap where the first 100 bits are
  82  * unlikely to be set. It's guaranteed that at least one of the 140
  83  * bits is cleared.
  84  */
  85 static inline int sched_find_first_bit(unsigned long *b)
  86 {
  87         if (unlikely(b[0]))
  88                 return __ffs(b[0]);
  89         if (unlikely(b[1]))
  90                 return __ffs(b[1]) + 32;
  91         if (unlikely(b[2]))
  92                 return __ffs(b[2]) + 64;
  93         if (b[3])
  94                 return __ffs(b[3]) + 96;
  95         return __ffs(b[4]) + 128;
  96 }
  97
  98 /*
  99  * ffz = Find First Zero in word. Undefined if no zero exists,
 100  * so code should check against ~0UL first..
 101  */
 102 static __inline__ unsigned long ffz(unsigned long word)
 103 {
 104         unsigned long result = 0;
 105
 106         while(word & 1) {
 107                 result++;
 108                 word >>= 1;
 109         }
 110         return result;
 111 }
 112
 113
 114 static __inline__ void set_bit(int nr, volatile unsigned long * addr)
 115 {
 116         int     * a = (int *) addr;
 117         int     mask;
 118         unsigned long flags;
 119
 120         a += nr >> 5;
 121         mask = 1 << (nr & 0x1f);
 122         local_irq_save(flags);
 123         *a |= mask;
 124         local_irq_restore(flags);
 125 }
 126
 127 static __inline__ void __set_bit(int nr, volatile unsigned long * addr)
 128 {
 129         int     * a = (int *) addr;
 130         int     mask;
 131
 132         a += nr >> 5;
 133         mask = 1 << (nr & 0x1f);
 134         *a |= mask;
 135 }
 136
 137 /*
 138  * clear_bit() doesn't provide any barrier for the compiler.
 139  */
 140 #define smp_mb__before_clear_bit()      barrier()
 141 #define smp_mb__after_clear_bit()       barrier()
 142
 143 static __inline__ void clear_bit(int nr, volatile unsigned long * addr)
 144 {
 145         int     * a = (int *) addr;
 146         int     mask;
 147         unsigned long flags;
 148
 149         a += nr >> 5;
 150         mask = 1 << (nr & 0x1f);
 151         local_irq_save(flags);
 152         *a &= ~mask;
 153         local_irq_restore(flags);
 154 }
 155
 156 static __inline__ void __clear_bit(int nr, volatile unsigned long * addr)
 157 {
 158         int     * a = (int *) addr;
 159         int     mask;
 160
 161         a += nr >> 5;
 162         mask = 1 << (nr & 0x1f);
 163         *a &= ~mask;
 164 }
 165
 166 static __inline__ void change_bit(int nr, volatile unsigned long * addr)
 167 {
 168         int mask, flags;
 169         unsigned long *ADDR = (unsigned long *) addr;
 170
 171         ADDR += nr >> 5;
 172         mask = 1 << (nr & 31);
 173         local_irq_save(flags);
 174         *ADDR ^= mask;
 175         local_irq_restore(flags);
 176 }
 177
 178 static __inline__ void __change_bit(int nr, volatile unsigned long * addr)
 179 {
 180         int mask;
 181         unsigned long *ADDR = (unsigned long *) addr;
 182
 183         ADDR += nr >> 5;
 184         mask = 1 << (nr & 31);
 185         *ADDR ^= mask;
 186 }
 187
 188 static __inline__ int test_and_set_bit(int nr, volatile unsigned long * addr)
 189 {
 190         int     mask, retval;
 191         volatile unsigned int *a = (volatile unsigned int *) addr;
 192         unsigned long flags;
 193
 194         a += nr >> 5;
 195         mask = 1 << (nr & 0x1f);
 196         local_irq_save(flags);
 197         retval = (mask & *a) != 0;
 198         *a |= mask;
 199         local_irq_restore(flags);
 200
 201         return retval;
 202 }
 203
 204 static __inline__ int __test_and_set_bit(int nr, volatile unsigned long * addr)
 205 {
 206         int     mask, retval;
 207         volatile unsigned int *a = (volatile unsigned int *) addr;
 208
 209         a += nr >> 5;
 210         mask = 1 << (nr & 0x1f);
 211         retval = (mask & *a) != 0;
 212         *a |= mask;
 213         return retval;
 214 }
 215
 216 static __inline__ int test_and_clear_bit(int nr, volatile unsigned long * addr)
 217 {
 218         int     mask, retval;
 219         volatile unsigned int *a = (volatile unsigned int *) addr;
 220         unsigned long flags;
 221
 222         a += nr >> 5;
 223         mask = 1 << (nr & 0x1f);
 224         local_irq_save(flags);
 225         retval = (mask & *a) != 0;
 226         *a &= ~mask;
 227         local_irq_restore(flags);
 228
 229         return retval;
 230 }
 231
 232 static __inline__ int __test_and_clear_bit(int nr, volatile unsigned long * addr)
 233 {
 234         int     mask, retval;
 235         volatile unsigned int *a = (volatile unsigned int *) addr;
 236
 237         a += nr >> 5;
 238         mask = 1 << (nr & 0x1f);
 239         retval = (mask & *a) != 0;
 240         *a &= ~mask;
 241         return retval;
 242 }
 243
 244 static __inline__ int test_and_change_bit(int nr, volatile unsigned long * addr)
 245 {
 246         int     mask, retval;
 247         volatile unsigned int *a = (volatile unsigned int *) addr;
 248         unsigned long flags;
 249
 250         a += nr >> 5;
 251         mask = 1 << (nr & 0x1f);
 252         local_irq_save(flags);
 253         retval = (mask & *a) != 0;
 254         *a ^= mask;
 255         local_irq_restore(flags);
 256
 257         return retval;
 258 }
 259
 260 static __inline__ int __test_and_change_bit(int nr, volatile unsigned long * addr)
 261 {
 262         int     mask, retval;
 263         volatile unsigned int *a = (volatile unsigned int *) addr;
 264
 265         a += nr >> 5;
 266         mask = 1 << (nr & 0x1f);
 267         retval = (mask & *a) != 0;
 268         *a ^= mask;
 269         return retval;
 270 }
 271
 272 /*
 273  * This routine doesn't need to be atomic.
 274  */
 275 static __inline__ int __constant_test_bit(int nr, const volatile unsigned long * addr)
 276 {
 277         return ((1UL << (nr & 31)) & (((const volatile unsigned int *) addr)[nr >> 5])) != 0;
 278 }
 279
 280 static __inline__ int __test_bit(int nr, const volatile unsigned long * addr)
 281 {
 282         int     * a = (int *) addr;
 283         int     mask;
 284
 285         a += nr >> 5;
 286         mask = 1 << (nr & 0x1f);
 287         return ((mask & *a) != 0);
 288 }
 289
 290 #define test_bit(nr,addr) \
 291 (__builtin_constant_p(nr) ? \
 292  __constant_test_bit((nr),(addr)) : \
 293  __test_bit((nr),(addr)))
 294
 295 #define find_first_zero_bit(addr, size) \
 296         find_next_zero_bit((addr), (size), 0)
 297
 298 static __inline__ int find_next_zero_bit (void * addr, int size, int offset)
 299 {
 300         unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
 301         unsigned long result = offset & ~31UL;
 302         unsigned long tmp;
 303
 304         if (offset >= size)
 305                 return size;
 306         size -= result;
 307         offset &= 31UL;
 308         if (offset) {
 309                 tmp = *(p++);
 310                 tmp |= ~0UL >> (32-offset);
 311                 if (size < 32)
 312                         goto found_first;
 313                 if (~tmp)
 314                         goto found_middle;
 315                 size -= 32;
 316                 result += 32;
 317         }
 318         while (size & ~31UL) {
 319                 if (~(tmp = *(p++)))
 320                         goto found_middle;
 321                 result += 32;
 322                 size -= 32;
 323         }
 324         if (!size)
 325                 return result;
 326         tmp = *p;
 327
 328 found_first:
 329         tmp |= ~0UL >> size;
 330 found_middle:
 331         return result + ffz(tmp);
 332 }
 333
 334 /*
 335  * Find next one bit in a bitmap reasonably efficiently.
 336  */
 337 static __inline__ unsigned long find_next_bit(const unsigned long *addr,
 338         unsigned long size, unsigned long offset)
 339 {
 340         unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
 341         unsigned int result = offset & ~31UL;
 342         unsigned int tmp;
 343
 344         if (offset >= size)
 345                 return size;
 346         size -= result;
 347         offset &= 31UL;
 348         if (offset) {
 349                 tmp = *p++;
 350                 tmp &= ~0UL << offset;
 351                 if (size < 32)
 352                         goto found_first;
 353                 if (tmp)
 354                         goto found_middle;
 355                 size -= 32;
 356                 result += 32;
 357         }
 358         while (size >= 32) {
 359                 if ((tmp = *p++) != 0)
 360                         goto found_middle;
 361                 result += 32;
 362                 size -= 32;
 363         }
 364         if (!size)
 365                 return result;
 366         tmp = *p;
 367
 368 found_first:
 369         tmp &= ~0UL >> (32 - size);
 370         if (tmp == 0UL)        /* Are any bits set? */
 371                 return result + size; /* Nope. */
 372 found_middle:
 373         return result + __ffs(tmp);
 374 }
 375
 376 /*
 377  * hweightN: returns the hamming weight (i.e. the number
 378  * of bits set) of a N-bit word
 379  */
 380
 381 #define hweight32(x) generic_hweight32(x)
 382 #define hweight16(x) generic_hweight16(x)
 383 #define hweight8(x) generic_hweight8(x)
 384
 385
 386 static __inline__ int ext2_set_bit(int nr, volatile void * addr)
 387 {
 388         int             mask, retval;
 389         unsigned long   flags;
 390         volatile unsigned char  *ADDR = (unsigned char *) addr;
 391
 392         ADDR += nr >> 3;
 393         mask = 1 << (nr & 0x07);
 394         local_irq_save(flags);
 395         retval = (mask & *ADDR) != 0;
 396         *ADDR |= mask;
 397         local_irq_restore(flags);
 398         return retval;
 399 }
 400
 401 static __inline__ int ext2_clear_bit(int nr, volatile void * addr)
 402 {
 403         int             mask, retval;
 404         unsigned long   flags;
 405         volatile unsigned char  *ADDR = (unsigned char *) addr;
 406
 407         ADDR += nr >> 3;
 408         mask = 1 << (nr & 0x07);
 409         local_irq_save(flags);
 410         retval = (mask & *ADDR) != 0;
 411         *ADDR &= ~mask;
 412         local_irq_restore(flags);
 413         return retval;
 414 }
 415
 416 #define ext2_set_bit_atomic(lock, nr, addr)             \
 417         ({                                              \
 418                 int ret;                                \
 419                 spin_lock(lock);                        \
 420                 ret = ext2_set_bit((nr), (addr));       \
 421                 spin_unlock(lock);                      \
 422                 ret;                                    \
 423         })
 424
 425 #define ext2_clear_bit_atomic(lock, nr, addr)           \
 426         ({                                              \
 427                 int ret;                                \
 428                 spin_lock(lock);                        \
 429                 ret = ext2_clear_bit((nr), (addr));     \
 430                 spin_unlock(lock);                      \
 431                 ret;                                    \
 432         })
 433
 434 static __inline__ int ext2_test_bit(int nr, const volatile void * addr)
 435 {
 436         int     mask;
 437         const volatile unsigned char    *ADDR = (const unsigned char *) addr;
 438
 439         ADDR += nr >> 3;
 440         mask = 1 << (nr & 0x07);
 441         return ((mask & *ADDR) != 0);
 442 }
 443
 444 #define ext2_find_first_zero_bit(addr, size) \
 445         ext2_find_next_zero_bit((addr), (size), 0)
 446
 447 static __inline__ unsigned long ext2_find_next_zero_bit(void *addr, unsigned long size, unsigned long offset)
 448 {
 449         unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
 450         unsigned long result = offset & ~31UL;
 451         unsigned long tmp;
 452
 453         if (offset >= size)
 454                 return size;
 455         size -= result;
 456         offset &= 31UL;
 457         if(offset) {
 458                 /* We hold the little endian value in tmp, but then the
 459                  * shift is illegal. So we could keep a big endian value
 460                  * in tmp, like this:
 461                  *
 462                  * tmp = __swab32(*(p++));
 463                  * tmp |= ~0UL >> (32-offset);
 464                  *
 465                  * but this would decrease preformance, so we change the
 466                  * shift:
 467                  */
 468                 tmp = *(p++);
 469                 tmp |= __swab32(~0UL >> (32-offset));
 470                 if(size < 32)
 471                         goto found_first;
 472                 if(~tmp)
 473                         goto found_middle;
 474                 size -= 32;
 475                 result += 32;
 476         }
 477         while(size & ~31UL) {
 478                 if(~(tmp = *(p++)))
 479                         goto found_middle;
 480                 result += 32;
 481                 size -= 32;
 482         }
 483         if(!size)
 484                 return result;
 485         tmp = *p;
 486
 487 found_first:
 488         /* tmp is little endian, so we would have to swab the shift,
 489          * see above. But then we have to swab tmp below for ffz, so
 490          * we might as well do this here.
 491          */
 492         return result + ffz(__swab32(tmp) | (~0UL << size));
 493 found_middle:
 494         return result + ffz(__swab32(tmp));
 495 }
 496
 497 /* Bitmap functions for the minix filesystem.  */
 498 #define minix_test_and_set_bit(nr,addr) test_and_set_bit(nr,addr)
 499 #define minix_set_bit(nr,addr) set_bit(nr,addr)
 500 #define minix_test_and_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
 501 #define minix_test_bit(nr,addr) test_bit(nr,addr)
 502 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
 503
 504 /**
 505  * hweightN - returns the hamming weight of a N-bit word
 506  * @x: the word to weigh
 507  *
 508  * The Hamming Weight of a number is the total number of bits set in it.
 509  */
 510
 511 #define hweight32(x) generic_hweight32(x)
 512 #define hweight16(x) generic_hweight16(x)
 513 #define hweight8(x) generic_hweight8(x)
 514
 515 #endif /* __KERNEL__ */
 516
 517 /*
 518  * fls: find last bit set.
 519  */
 520 #define fls(x) generic_fls(x)
 521
 522 #endif /* _M68KNOMMU_BITOPS_H */