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, unsigned long *vaddr)
  27 {
  28         char *p = (char *)vaddr + (nr ^ 31) / 8;
  29         char retval;
  30
  31         __asm__ __volatile__ ("bset %2,%1; sne %0"
  32                         : "=d" (retval), "+m" (*p)
  33                         : "di" (nr & 7));
  34
  35         return retval;
  36 }
  37
  38 static inline int __generic_test_and_set_bit(int nr, unsigned long *vaddr)
  39 {
  40         char retval;
  41
  42         __asm__ __volatile__ ("bfset %2{%1:#1}; sne %0"
  43                         : "=d" (retval) : "d" (nr^31), "o" (*vaddr) : "memory");
  44
  45         return retval;
  46 }
  47
  48 #define set_bit(nr,vaddr) \
  49   (__builtin_constant_p(nr) ? \
  50    __constant_set_bit(nr, vaddr) : \
  51    __generic_set_bit(nr, vaddr))
  52
  53 #define __set_bit(nr,vaddr) set_bit(nr,vaddr)
  54
  55 static inline void __constant_set_bit(int nr, volatile unsigned long *vaddr)
  56 {
  57         char *p = (char *)vaddr + (nr ^ 31) / 8;
  58         __asm__ __volatile__ ("bset %1,%0"
  59                         : "+m" (*p) : "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), "o" (*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, unsigned long *vaddr)
  76 {
  77         char *p = (char *)vaddr + (nr ^ 31) / 8;
  78         char retval;
  79
  80         __asm__ __volatile__ ("bclr %2,%1; sne %0"
  81                         : "=d" (retval), "+m" (*p)
  82                         : "di" (nr & 7));
  83
  84         return retval;
  85 }
  86
  87 static inline int __generic_test_and_clear_bit(int nr, unsigned long *vaddr)
  88 {
  89         char retval;
  90
  91         __asm__ __volatile__ ("bfclr %2{%1:#1}; sne %0"
  92                         : "=d" (retval) : "d" (nr^31), "o" (*vaddr) : "memory");
  93
  94         return retval;
  95 }
  96
  97 /*
  98  * clear_bit() doesn't provide any barrier for the compiler.
  99  */
 100 #define smp_mb__before_clear_bit()      barrier()
 101 #define smp_mb__after_clear_bit()       barrier()
 102
 103 #define clear_bit(nr,vaddr) \
 104   (__builtin_constant_p(nr) ? \
 105    __constant_clear_bit(nr, vaddr) : \
 106    __generic_clear_bit(nr, vaddr))
 107 #define __clear_bit(nr,vaddr) clear_bit(nr,vaddr)
 108
 109 static inline void __constant_clear_bit(int nr, volatile unsigned long *vaddr)
 110 {
 111         char *p = (char *)vaddr + (nr ^ 31) / 8;
 112         __asm__ __volatile__ ("bclr %1,%0"
 113                         : "+m" (*p) : "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), "o" (*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, unsigned long *vaddr)
 131 {
 132         char *p = (char *)vaddr + (nr ^ 31) / 8;
 133         char retval;
 134
 135         __asm__ __volatile__ ("bchg %2,%1; sne %0"
 136                         : "=d" (retval), "+m" (*p)
 137                         : "di" (nr & 7));
 138
 139         return retval;
 140 }
 141
 142 static inline int __generic_test_and_change_bit(int nr, unsigned long *vaddr)
 143 {
 144         char retval;
 145
 146         __asm__ __volatile__ ("bfchg %2{%1:#1}; sne %0"
 147                         : "=d" (retval) : "d" (nr^31), "o" (*vaddr) : "memory");
 148
 149         return retval;
 150 }
 151
 152 #define change_bit(nr,vaddr) \
 153   (__builtin_constant_p(nr) ? \
 154    __constant_change_bit(nr, vaddr) : \
 155    __generic_change_bit(nr, vaddr))
 156
 157 static inline void __constant_change_bit(int nr, unsigned long *vaddr)
 158 {
 159         char *p = (char *)vaddr + (nr ^ 31) / 8;
 160         __asm__ __volatile__ ("bchg %1,%0"
 161                         : "+m" (*p) : "di" (nr & 7));
 162 }
 163
 164 static inline void __generic_change_bit(int nr, unsigned long *vaddr)
 165 {
 166         __asm__ __volatile__ ("bfchg %1{%0:#1}"
 167                         : : "d" (nr^31), "o" (*vaddr) : "memory");
 168 }
 169
 170 static inline int test_bit(int nr, const unsigned long *vaddr)
 171 {
 172         return (vaddr[nr >> 5] & (1UL << (nr & 31))) != 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 #define minix_test_and_set_bit(nr, addr)        test_and_set_bit((nr) ^ 16, (unsigned long *)(addr))
 368 #define minix_set_bit(nr,addr)                  set_bit((nr) ^ 16, (unsigned long *)(addr))
 369 #define minix_test_and_clear_bit(nr, addr)      test_and_clear_bit((nr) ^ 16, (unsigned long *)(addr))
 370
 371 static inline int minix_test_bit(int nr, const void *vaddr)
 372 {
 373         const unsigned short *p = vaddr;
 374         return (p[nr >> 4] & (1U << (nr & 15))) != 0;
 375 }
 376
 377 /* Bitmap functions for the ext2 filesystem. */
 378
 379 #define ext2_set_bit(nr, addr)                  test_and_set_bit((nr) ^ 24, (unsigned long *)(addr))
 380 #define ext2_set_bit_atomic(lock, nr, addr)     test_and_set_bit((nr) ^ 24, (unsigned long *)(addr))
 381 #define ext2_clear_bit(nr, addr)                test_and_clear_bit((nr) ^ 24, (unsigned long *)(addr))
 382 #define ext2_clear_bit_atomic(lock, nr, addr)   test_and_clear_bit((nr) ^ 24, (unsigned long *)(addr))
 383
 384 static inline int ext2_test_bit(int nr, const void *vaddr)
 385 {
 386         const unsigned char *p = vaddr;
 387         return (p[nr >> 3] & (1U << (nr & 7))) != 0;
 388 }
 389
 390 static inline int ext2_find_first_zero_bit(const void *vaddr, unsigned size)
 391 {
 392         const unsigned long *p = vaddr, *addr = vaddr;
 393         int res;
 394
 395         if (!size)
 396                 return 0;
 397
 398         size = (size >> 5) + ((size & 31) > 0);
 399         while (*p++ == ~0UL)
 400         {
 401                 if (--size == 0)
 402                         return (p - addr) << 5;
 403         }
 404
 405         --p;
 406         for (res = 0; res < 32; res++)
 407                 if (!ext2_test_bit (res, p))
 408                         break;
 409         return (p - addr) * 32 + res;
 410 }
 411
 412 static inline int ext2_find_next_zero_bit(const void *vaddr, unsigned size,
 413                                           unsigned offset)
 414 {
 415         const unsigned long *addr = vaddr;
 416         const unsigned long *p = addr + (offset >> 5);
 417         int bit = offset & 31UL, res;
 418
 419         if (offset >= size)
 420                 return size;
 421
 422         if (bit) {
 423                 /* Look for zero in first longword */
 424                 for (res = bit; res < 32; res++)
 425                         if (!ext2_test_bit (res, p))
 426                                 return (p - addr) * 32 + res;
 427                 p++;
 428         }
 429         /* No zero yet, search remaining full bytes for a zero */
 430         res = ext2_find_first_zero_bit (p, size - 32 * (p - addr));
 431         return (p - addr) * 32 + res;
 432 }
 433
 434 #endif /* __KERNEL__ */
 435
 436 #endif /* _M68K_BITOPS_H */