include/asm-m68k/bitops.h

   1 #ifndef _M68K_BITOPS_H
   2 #define _M68K_BITOPS_H
   3 /*
   4  * Copyright 1992, Linus Torvalds.
   5  *
   6  * This file is subject to the terms and conditions of the GNU General Public
   7  * License.  See the file COPYING in the main directory of this archive
   8  * for more details.
   9  */
  10
  11 #include <linux/compiler.h>
  12
  13 /*
  14  * Require 68020 or better.
  15  *
  16  * They use the standard big-endian m680x0 bit ordering.
  17  */
  18
  19 #define test_and_set_bit(nr,vaddr) \
  20   (__builtin_constant_p(nr) ? \
  21    __constant_test_and_set_bit(nr, vaddr) : \
  22    __generic_test_and_set_bit(nr, vaddr))
  23
  24 #define __test_and_set_bit(nr,vaddr) test_and_set_bit(nr,vaddr)
  25
  26 static inline int __constant_test_and_set_bit(int nr,
  27                                               volatile unsigned long *vaddr)
  28 {
  29         char retval;
  30
  31         __asm__ __volatile__ ("bset %2,%1; sne %0"
  32              : "=d" (retval), "+m" (((volatile char *)vaddr)[(nr^31) >> 3])
  33              : "di" (nr & 7));
  34
  35         return retval;
  36 }
  37
  38 static inline int __generic_test_and_set_bit(int nr,
  39                                              volatile unsigned long *vaddr)
  40 {
  41         char retval;
  42
  43         __asm__ __volatile__ ("bfset %2@{%1:#1}; sne %0"
  44              : "=d" (retval) : "d" (nr^31), "a" (vaddr) : "memory");
  45
  46         return retval;
  47 }
  48
  49 #define set_bit(nr,vaddr) \
  50   (__builtin_constant_p(nr) ? \
  51    __constant_set_bit(nr, vaddr) : \
  52    __generic_set_bit(nr, vaddr))
  53
  54 #define __set_bit(nr,vaddr) set_bit(nr,vaddr)
  55
  56 static inline void __constant_set_bit(int nr, volatile unsigned long *vaddr)
  57 {
  58         __asm__ __volatile__ ("bset %1,%0"
  59              : "+m" (((volatile char *)vaddr)[(nr^31) >> 3]) : "di" (nr & 7));
  60 }
  61
  62 static inline void __generic_set_bit(int nr, volatile unsigned long *vaddr)
  63 {
  64         __asm__ __volatile__ ("bfset %1@{%0:#1}"
  65              : : "d" (nr^31), "a" (vaddr) : "memory");
  66 }
  67
  68 #define test_and_clear_bit(nr,vaddr) \
  69   (__builtin_constant_p(nr) ? \
  70    __constant_test_and_clear_bit(nr, vaddr) : \
  71    __generic_test_and_clear_bit(nr, vaddr))
  72
  73 #define __test_and_clear_bit(nr,vaddr) test_and_clear_bit(nr,vaddr)
  74
  75 static inline int __constant_test_and_clear_bit(int nr,
  76                                                 volatile unsigned long *vaddr)
  77 {
  78         char retval;
  79
  80         __asm__ __volatile__ ("bclr %2,%1; sne %0"
  81              : "=d" (retval), "+m" (((volatile char *)vaddr)[(nr^31) >> 3])
  82              : "di" (nr & 7));
  83
  84         return retval;
  85 }
  86
  87 static inline int __generic_test_and_clear_bit(int nr,
  88                                                volatile unsigned long *vaddr)
  89 {
  90         char retval;
  91
  92         __asm__ __volatile__ ("bfclr %2@{%1:#1}; sne %0"
  93              : "=d" (retval) : "d" (nr^31), "a" (vaddr) : "memory");
  94
  95         return retval;
  96 }
  97
  98 /*
  99  * clear_bit() doesn't provide any barrier for the compiler.
 100  */
 101 #define smp_mb__before_clear_bit()      barrier()
 102 #define smp_mb__after_clear_bit()       barrier()
 103
 104 #define clear_bit(nr,vaddr) \
 105   (__builtin_constant_p(nr) ? \
 106    __constant_clear_bit(nr, vaddr) : \
 107    __generic_clear_bit(nr, vaddr))
 108 #define __clear_bit(nr,vaddr) clear_bit(nr,vaddr)
 109
 110 static inline void __constant_clear_bit(int nr, volatile unsigned long *vaddr)
 111 {
 112         __asm__ __volatile__ ("bclr %1,%0"
 113              : "+m" (((volatile char *)vaddr)[(nr^31) >> 3]) : "di" (nr & 7));
 114 }
 115
 116 static inline void __generic_clear_bit(int nr, volatile unsigned long *vaddr)
 117 {
 118         __asm__ __volatile__ ("bfclr %1@{%0:#1}"
 119              : : "d" (nr^31), "a" (vaddr) : "memory");
 120 }
 121
 122 #define test_and_change_bit(nr,vaddr) \
 123   (__builtin_constant_p(nr) ? \
 124    __constant_test_and_change_bit(nr, vaddr) : \
 125    __generic_test_and_change_bit(nr, vaddr))
 126
 127 #define __test_and_change_bit(nr,vaddr) test_and_change_bit(nr,vaddr)
 128 #define __change_bit(nr,vaddr) change_bit(nr,vaddr)
 129
 130 static inline int __constant_test_and_change_bit(int nr,
 131                                                  volatile unsigned long *vaddr)
 132 {
 133         char retval;
 134
 135         __asm__ __volatile__ ("bchg %2,%1; sne %0"
 136              : "=d" (retval), "+m" (((volatile char *)vaddr)[(nr^31) >> 3])
 137              : "di" (nr & 7));
 138
 139         return retval;
 140 }
 141
 142 static inline int __generic_test_and_change_bit(int nr,
 143                                                 volatile unsigned long *vaddr)
 144 {
 145         char retval;
 146
 147         __asm__ __volatile__ ("bfchg %2@{%1:#1}; sne %0"
 148              : "=d" (retval) : "d" (nr^31), "a" (vaddr) : "memory");
 149
 150         return retval;
 151 }
 152
 153 #define change_bit(nr,vaddr) \
 154   (__builtin_constant_p(nr) ? \
 155    __constant_change_bit(nr, vaddr) : \
 156    __generic_change_bit(nr, vaddr))
 157
 158 static inline void __constant_change_bit(int nr, volatile unsigned long *vaddr)
 159 {
 160         __asm__ __volatile__ ("bchg %1,%0"
 161              : "+m" (((volatile char *)vaddr)[(nr^31) >> 3]) : "di" (nr & 7));
 162 }
 163
 164 static inline void __generic_change_bit(int nr, volatile unsigned long *vaddr)
 165 {
 166         __asm__ __volatile__ ("bfchg %1@{%0:#1}"
 167              : : "d" (nr^31), "a" (vaddr) : "memory");
 168 }
 169
 170 static inline int test_bit(int nr, const volatile unsigned long *vaddr)
 171 {
 172         return ((1UL << (nr & 31)) & (((const volatile unsigned long *) vaddr)[nr >> 5])) != 0;
 173 }
 174
 175 static inline int find_first_zero_bit(const unsigned long *vaddr,
 176                                       unsigned size)
 177 {
 178         const unsigned long *p = vaddr;
 179         int res = 32;
 180         unsigned long num;
 181
 182         if (!size)
 183                 return 0;
 184
 185         size = (size + 31) >> 5;
 186         while (!(num = ~*p++)) {
 187                 if (!--size)
 188                         goto out;
 189         }
 190
 191         __asm__ __volatile__ ("bfffo %1{#0,#0},%0"
 192                               : "=d" (res) : "d" (num & -num));
 193         res ^= 31;
 194 out:
 195         return ((long)p - (long)vaddr - 4) * 8 + res;
 196 }
 197
 198 static inline int find_next_zero_bit(const unsigned long *vaddr, int size,
 199                                      int offset)
 200 {
 201         const unsigned long *p = vaddr + (offset >> 5);
 202         int bit = offset & 31UL, res;
 203
 204         if (offset >= size)
 205                 return size;
 206
 207         if (bit) {
 208                 unsigned long num = ~*p++ & (~0UL << bit);
 209                 offset -= bit;
 210
 211                 /* Look for zero in first longword */
 212                 __asm__ __volatile__ ("bfffo %1{#0,#0},%0"
 213                                       : "=d" (res) : "d" (num & -num));
 214                 if (res < 32)
 215                         return offset + (res ^ 31);
 216                 offset += 32;
 217         }
 218         /* No zero yet, search remaining full bytes for a zero */
 219         res = find_first_zero_bit(p, size - ((long)p - (long)vaddr) * 8);
 220         return offset + res;
 221 }
 222
 223 static inline int find_first_bit(const unsigned long *vaddr, unsigned size)
 224 {
 225         const unsigned long *p = vaddr;
 226         int res = 32;
 227         unsigned long num;
 228
 229         if (!size)
 230                 return 0;
 231
 232         size = (size + 31) >> 5;
 233         while (!(num = *p++)) {
 234                 if (!--size)
 235                         goto out;
 236         }
 237
 238         __asm__ __volatile__ ("bfffo %1{#0,#0},%0"
 239                               : "=d" (res) : "d" (num & -num));
 240         res ^= 31;
 241 out:
 242         return ((long)p - (long)vaddr - 4) * 8 + res;
 243 }
 244
 245 static inline int find_next_bit(const unsigned long *vaddr, int size,
 246                                 int offset)
 247 {
 248         const unsigned long *p = vaddr + (offset >> 5);
 249         int bit = offset & 31UL, res;
 250
 251         if (offset >= size)
 252                 return size;
 253
 254         if (bit) {
 255                 unsigned long num = *p++ & (~0UL << bit);
 256                 offset -= bit;
 257
 258                 /* Look for one in first longword */
 259                 __asm__ __volatile__ ("bfffo %1{#0,#0},%0"
 260                                       : "=d" (res) : "d" (num & -num));
 261                 if (res < 32)
 262                         return offset + (res ^ 31);
 263                 offset += 32;
 264         }
 265         /* No one yet, search remaining full bytes for a one */
 266         res = find_first_bit(p, size - ((long)p - (long)vaddr) * 8);
 267         return offset + res;
 268 }
 269
 270 /*
 271  * ffz = Find First Zero in word. Undefined if no zero exists,
 272  * so code should check against ~0UL first..
 273  */
 274 static inline unsigned long ffz(unsigned long word)
 275 {
 276         int res;
 277
 278         __asm__ __volatile__ ("bfffo %1{#0,#0},%0"
 279                               : "=d" (res) : "d" (~word & -~word));
 280         return res ^ 31;
 281 }
 282
 283 #ifdef __KERNEL__
 284
 285 /*
 286  * ffs: find first bit set. This is defined the same way as
 287  * the libc and compiler builtin ffs routines, therefore
 288  * differs in spirit from the above ffz (man ffs).
 289  */
 290
 291 static inline int ffs(int x)
 292 {
 293         int cnt;
 294
 295         asm ("bfffo %1{#0:#0},%0" : "=d" (cnt) : "dm" (x & -x));
 296
 297         return 32 - cnt;
 298 }
 299 #define __ffs(x) (ffs(x) - 1)
 300
 301 /*
 302  * fls: find last bit set.
 303  */
 304
 305 static inline int fls(int x)
 306 {
 307         int cnt;
 308
 309         asm ("bfffo %1{#0,#0},%0" : "=d" (cnt) : "dm" (x));
 310
 311         return 32 - cnt;
 312 }
 313
 314 /*
 315  * Every architecture must define this function. It's the fastest
 316  * way of searching a 140-bit bitmap where the first 100 bits are
 317  * unlikely to be set. It's guaranteed that at least one of the 140
 318  * bits is cleared.
 319  */
 320 static inline int sched_find_first_bit(const unsigned long *b)
 321 {
 322         if (unlikely(b[0]))
 323                 return __ffs(b[0]);
 324         if (unlikely(b[1]))
 325                 return __ffs(b[1]) + 32;
 326         if (unlikely(b[2]))
 327                 return __ffs(b[2]) + 64;
 328         if (b[3])
 329                 return __ffs(b[3]) + 96;
 330         return __ffs(b[4]) + 128;
 331 }
 332
 333
 334 /*
 335  * hweightN: returns the hamming weight (i.e. the number
 336  * of bits set) of a N-bit word
 337  */
 338
 339 #define hweight32(x) generic_hweight32(x)
 340 #define hweight16(x) generic_hweight16(x)
 341 #define hweight8(x) generic_hweight8(x)
 342
 343 /* Bitmap functions for the minix filesystem */
 344
 345 static inline int minix_find_first_zero_bit(const void *vaddr, unsigned size)
 346 {
 347         const unsigned short *p = vaddr, *addr = vaddr;
 348         int res;
 349         unsigned short num;
 350
 351         if (!size)
 352                 return 0;
 353
 354         size = (size >> 4) + ((size & 15) > 0);
 355         while (*p++ == 0xffff)
 356         {
 357                 if (--size == 0)
 358                         return (p - addr) << 4;
 359         }
 360
 361         num = ~*--p;
 362         __asm__ __volatile__ ("bfffo %1{#16,#16},%0"
 363                               : "=d" (res) : "d" (num & -num));
 364         return ((p - addr) << 4) + (res ^ 31);
 365 }
 366
 367 static inline int minix_test_and_set_bit(int nr, volatile void *vaddr)
 368 {
 369         char retval;
 370
 371         __asm__ __volatile__ ("bfset %2{%1:#1}; sne %0"
 372              : "=d" (retval) : "d" (nr^15), "m" (*(volatile char *)vaddr) : "memory");
 373
 374         return retval;
 375 }
 376
 377 #define minix_set_bit(nr,addr)  ((void)minix_test_and_set_bit(nr,addr))
 378
 379 static inline int minix_test_and_clear_bit(int nr, volatile void *vaddr)
 380 {
 381         char retval;
 382
 383         __asm__ __volatile__ ("bfclr %2{%1:#1}; sne %0"
 384              : "=d" (retval) : "d" (nr^15), "m" (*(volatile char *) vaddr) : "memory");
 385
 386         return retval;
 387 }
 388
 389 static inline int minix_test_bit(int nr, const volatile void *vaddr)
 390 {
 391         return ((1U << (nr & 15)) & (((const volatile unsigned short *) vaddr)[nr >> 4])) != 0;
 392 }
 393
 394 /* Bitmap functions for the ext2 filesystem. */
 395
 396 static inline int ext2_set_bit(int nr, volatile void *vaddr)
 397 {
 398         char retval;
 399
 400         __asm__ __volatile__ ("bfset %2{%1,#1}; sne %0"
 401              : "=d" (retval) : "d" (nr^7), "m" (*(volatile char *) vaddr) : "memory");
 402
 403         return retval;
 404 }
 405
 406 static inline int ext2_clear_bit(int nr, volatile void *vaddr)
 407 {
 408         char retval;
 409
 410         __asm__ __volatile__ ("bfclr %2{%1,#1}; sne %0"
 411              : "=d" (retval) : "d" (nr^7), "m" (*(volatile char *) vaddr) : "memory");
 412
 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 *vaddr)
 435 {
 436         return ((1U << (nr & 7)) & (((const volatile unsigned char *) vaddr)[nr >> 3])) != 0;
 437 }
 438
 439 static inline int ext2_find_first_zero_bit(const void *vaddr, unsigned size)
 440 {
 441         const unsigned long *p = vaddr, *addr = vaddr;
 442         int res;
 443
 444         if (!size)
 445                 return 0;
 446
 447         size = (size >> 5) + ((size & 31) > 0);
 448         while (*p++ == ~0UL)
 449         {
 450                 if (--size == 0)
 451                         return (p - addr) << 5;
 452         }
 453
 454         --p;
 455         for (res = 0; res < 32; res++)
 456                 if (!ext2_test_bit (res, p))
 457                         break;
 458         return (p - addr) * 32 + res;
 459 }
 460
 461 static inline int ext2_find_next_zero_bit(const void *vaddr, unsigned size,
 462                                           unsigned offset)
 463 {
 464         const unsigned long *addr = vaddr;
 465         const unsigned long *p = addr + (offset >> 5);
 466         int bit = offset & 31UL, res;
 467
 468         if (offset >= size)
 469                 return size;
 470
 471         if (bit) {
 472                 /* Look for zero in first longword */
 473                 for (res = bit; res < 32; res++)
 474                         if (!ext2_test_bit (res, p))
 475                                 return (p - addr) * 32 + res;
 476                 p++;
 477         }
 478         /* No zero yet, search remaining full bytes for a zero */
 479         res = ext2_find_first_zero_bit (p, size - 32 * (p - addr));
 480         return (p - addr) * 32 + res;
 481 }
 482
 483 #endif /* __KERNEL__ */
 484
 485 #endif /* _M68K_BITOPS_H */