lib/ext2fs/bitops.h

   1 /*
   2  * bitops.h --- Bitmap frobbing code.  The byte swapping routines are
   3  *      also included here.
   4  *
   5  * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o.
   6  *
   7  * %Begin-Header%
   8  * This file may be redistributed under the terms of the GNU Public
   9  * License.
  10  * %End-Header%
  11  *
  12  * i386 bitops operations taken from <asm/bitops.h>, Copyright 1992,
  13  * Linus Torvalds.
  14  */
  15
  16
  17 extern int ext2fs_set_bit(unsigned int nr,void * addr);
  18 extern int ext2fs_clear_bit(unsigned int nr, void * addr);
  19 extern int ext2fs_test_bit(unsigned int nr, const void * addr);
  20 extern void ext2fs_fast_set_bit(unsigned int nr,void * addr);
  21 extern void ext2fs_fast_clear_bit(unsigned int nr, void * addr);
  22 extern __u16 ext2fs_swab16(__u16 val);
  23 extern __u32 ext2fs_swab32(__u32 val);
  24 extern __u64 ext2fs_swab64(__u64 val);
  25
  26 #ifdef WORDS_BIGENDIAN
  27 #define ext2fs_cpu_to_le64(x) ext2fs_swab64((x))
  28 #define ext2fs_le64_to_cpu(x) ext2fs_swab64((x))
  29 #define ext2fs_cpu_to_le32(x) ext2fs_swab32((x))
  30 #define ext2fs_le32_to_cpu(x) ext2fs_swab32((x))
  31 #define ext2fs_cpu_to_le16(x) ext2fs_swab16((x))
  32 #define ext2fs_le16_to_cpu(x) ext2fs_swab16((x))
  33 #define ext2fs_cpu_to_be32(x) ((__u32)(x))
  34 #define ext2fs_be32_to_cpu(x) ((__u32)(x))
  35 #define ext2fs_cpu_to_be16(x) ((__u16)(x))
  36 #define ext2fs_be16_to_cpu(x) ((__u16)(x))
  37 #else
  38 #define ext2fs_cpu_to_le64(x) ((__u64)(x))
  39 #define ext2fs_le64_to_cpu(x) ((__u64)(x))
  40 #define ext2fs_cpu_to_le32(x) ((__u32)(x))
  41 #define ext2fs_le32_to_cpu(x) ((__u32)(x))
  42 #define ext2fs_cpu_to_le16(x) ((__u16)(x))
  43 #define ext2fs_le16_to_cpu(x) ((__u16)(x))
  44 #define ext2fs_cpu_to_be32(x) ext2fs_swab32((x))
  45 #define ext2fs_be32_to_cpu(x) ext2fs_swab32((x))
  46 #define ext2fs_cpu_to_be16(x) ext2fs_swab16((x))
  47 #define ext2fs_be16_to_cpu(x) ext2fs_swab16((x))
  48 #endif
  49
  50 /*
  51  * EXT2FS bitmap manipulation routines.
  52  */
  53
  54 /* Support for sending warning messages from the inline subroutines */
  55 extern const char *ext2fs_block_string;
  56 extern const char *ext2fs_inode_string;
  57 extern const char *ext2fs_mark_string;
  58 extern const char *ext2fs_unmark_string;
  59 extern const char *ext2fs_test_string;
  60 extern void ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg,
  61                                const char *description);
  62 extern void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap,
  63                                 int code, unsigned long arg);
  64
  65 extern int ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap, blk_t block);
  66 extern int ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
  67                                        blk_t block);
  68 extern int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap, blk_t block);
  69
  70 extern int ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap, ext2_ino_t inode);
  71 extern int ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
  72                                        ext2_ino_t inode);
  73 extern int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap, ext2_ino_t inode);
  74
  75 extern void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap,
  76                                           blk_t block);
  77 extern void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
  78                                             blk_t block);
  79 extern int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap,
  80                                          blk_t block);
  81
  82 extern void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
  83                                           ext2_ino_t inode);
  84 extern void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
  85                                             ext2_ino_t inode);
  86 extern int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
  87                                          ext2_ino_t inode);
  88 extern blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap);
  89 extern ext2_ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap);
  90 extern blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap);
  91 extern ext2_ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap);
  92
  93 extern void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
  94                                            blk_t block, int num);
  95 extern void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
  96                                              blk_t block, int num);
  97 extern int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
  98                                           blk_t block, int num);
  99 extern void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 100                                                 blk_t block, int num);
 101 extern void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 102                                                   blk_t block, int num);
 103 extern int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
 104                                                blk_t block, int num);
 105 extern void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map);
 106
 107 /* These routines moved to gen_bitmap.c */
 108 extern int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
 109                                          __u32 bitno);
 110 extern int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
 111                                            blk_t bitno);
 112 extern int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
 113                                       blk_t bitno);
 114 extern int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
 115                                           blk_t block, int num);
 116 extern __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap);
 117 extern __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap);
 118
 119 /*
 120  * The inline routines themselves...
 121  *
 122  * If NO_INLINE_FUNCS is defined, then we won't try to do inline
 123  * functions at all; they will be included as normal functions in
 124  * inline.c
 125  */
 126 #ifdef NO_INLINE_FUNCS
 127 #if (defined(__GNUC__) && (defined(__i386__) || defined(__i486__) || \
 128                            defined(__i586__) || defined(__mc68000__)))
 129         /* This prevents bitops.c from trying to include the C */
 130         /* function version of these functions */
 131 #define _EXT2_HAVE_ASM_BITOPS_
 132 #endif
 133 #endif /* NO_INLINE_FUNCS */
 134
 135 #if (defined(INCLUDE_INLINE_FUNCS) || !defined(NO_INLINE_FUNCS))
 136 #ifdef INCLUDE_INLINE_FUNCS
 137 #define _INLINE_ extern
 138 #else
 139 #ifdef __GNUC__
 140 #define _INLINE_ extern __inline__
 141 #else                           /* For Watcom C */
 142 #define _INLINE_ extern inline
 143 #endif
 144 #endif
 145
 146 /*
 147  * Fast bit set/clear functions that doesn't need to return the
 148  * previous bit value.
 149  */
 150
 151 _INLINE_ void ext2fs_fast_set_bit(unsigned int nr,void * addr)
 152 {
 153         unsigned char   *ADDR = (unsigned char *) addr;
 154
 155         ADDR += nr >> 3;
 156         *ADDR |= (1 << (nr & 0x07));
 157 }
 158
 159 _INLINE_ void ext2fs_fast_clear_bit(unsigned int nr, void * addr)
 160 {
 161         unsigned char   *ADDR = (unsigned char *) addr;
 162
 163         ADDR += nr >> 3;
 164         *ADDR &= ~(1 << (nr & 0x07));
 165 }
 166
 167
 168 #if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \
 169      (defined(__i386__) || defined(__i486__) || defined(__i586__)))
 170
 171 #define _EXT2_HAVE_ASM_BITOPS_
 172 #define _EXT2_HAVE_ASM_SWAB_
 173 #define _EXT2_HAVE_ASM_FINDBIT_
 174
 175 /*
 176  * These are done by inline assembly for speed reasons.....
 177  *
 178  * All bitoperations return 0 if the bit was cleared before the
 179  * operation and != 0 if it was not.  Bit 0 is the LSB of addr; bit 32
 180  * is the LSB of (addr+1).
 181  */
 182
 183 /*
 184  * Some hacks to defeat gcc over-optimizations..
 185  */
 186 struct __dummy_h { unsigned long a[100]; };
 187 #define EXT2FS_ADDR (*(struct __dummy_h *) addr)
 188 #define EXT2FS_CONST_ADDR (*(const struct __dummy_h *) addr)
 189
 190 _INLINE_ int ext2fs_set_bit(unsigned int nr, void * addr)
 191 {
 192         int oldbit;
 193
 194         addr = (void *) (((unsigned char *) addr) + (nr >> 3));
 195         __asm__ __volatile__("btsl %2,%1\n\tsbbl %0,%0"
 196                 :"=r" (oldbit),"+m" (EXT2FS_ADDR)
 197                 :"r" (nr & 7));
 198         return oldbit;
 199 }
 200
 201 _INLINE_ int ext2fs_clear_bit(unsigned int nr, void * addr)
 202 {
 203         int oldbit;
 204
 205         addr = (void *) (((unsigned char *) addr) + (nr >> 3));
 206         __asm__ __volatile__("btrl %2,%1\n\tsbbl %0,%0"
 207                 :"=r" (oldbit),"+m" (EXT2FS_ADDR)
 208                 :"r" (nr & 7));
 209         return oldbit;
 210 }
 211
 212 _INLINE_ int ext2fs_test_bit(unsigned int nr, const void * addr)
 213 {
 214         int oldbit;
 215
 216         addr = (const void *) (((const unsigned char *) addr) + (nr >> 3));
 217         __asm__ __volatile__("btl %2,%1\n\tsbbl %0,%0"
 218                 :"=r" (oldbit)
 219                 :"m" (EXT2FS_CONST_ADDR),"r" (nr & 7));
 220         return oldbit;
 221 }
 222
 223 #if 0
 224 _INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size)
 225 {
 226         int d0, d1, d2;
 227         int res;
 228
 229         if (!size)
 230                 return 0;
 231         /* This looks at memory. Mark it volatile to tell gcc not to move it around */
 232         __asm__ __volatile__(
 233                 "cld\n\t"
 234                 "xorl %%eax,%%eax\n\t"
 235                 "xorl %%edx,%%edx\n\t"
 236                 "repe; scasl\n\t"
 237                 "je 1f\n\t"
 238                 "movl -4(%%edi),%%eax\n\t"
 239                 "subl $4,%%edi\n\t"
 240                 "bsfl %%eax,%%edx\n"
 241                 "1:\tsubl %%esi,%%edi\n\t"
 242                 "shll $3,%%edi\n\t"
 243                 "addl %%edi,%%edx"
 244                 :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
 245                 :"1" ((size + 31) >> 5), "2" (addr), "S" (addr));
 246         return res;
 247 }
 248
 249 _INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset)
 250 {
 251         unsigned long * p = ((unsigned long *) addr) + (offset >> 5);
 252         int set = 0, bit = offset & 31, res;
 253
 254         if (bit) {
 255                 /*
 256                  * Look for zero in first byte
 257                  */
 258                 __asm__("bsfl %1,%0\n\t"
 259                         "jne 1f\n\t"
 260                         "movl $32, %0\n"
 261                         "1:"
 262                         : "=r" (set)
 263                         : "r" (*p >> bit));
 264                 if (set < (32 - bit))
 265                         return set + offset;
 266                 set = 32 - bit;
 267                 p++;
 268         }
 269         /*
 270          * No bit found yet, search remaining full bytes for a bit
 271          */
 272         res = ext2fs_find_first_bit_set(p, size - 32 * (p - (unsigned long *) addr));
 273         return (offset + set + res);
 274 }
 275 #endif
 276
 277 _INLINE_ __u32 ext2fs_swab32(__u32 val)
 278 {
 279 #ifdef EXT2FS_REQUIRE_486
 280         __asm__("bswap %0" : "=r" (val) : "0" (val));
 281 #else
 282         __asm__("xchgb %b0,%h0\n\t"     /* swap lower bytes     */
 283                 "rorl $16,%0\n\t"       /* swap words           */
 284                 "xchgb %b0,%h0"         /* swap higher bytes    */
 285                 :"=q" (val)
 286                 : "0" (val));
 287 #endif
 288         return val;
 289 }
 290
 291 _INLINE_ __u16 ext2fs_swab16(__u16 val)
 292 {
 293         __asm__("xchgb %b0,%h0"         /* swap bytes           */ \
 294                 : "=q" (val) \
 295                 :  "0" (val)); \
 296                 return val;
 297 }
 298
 299 _INLINE_ __u64 ext2fs_swab64(__u64 val)
 300 {
 301         return (ext2fs_swab32(val >> 32) |
 302                 (((__u64)ext2fs_swab32(val & 0xFFFFFFFFUL)) << 32));
 303 }
 304
 305 #undef EXT2FS_ADDR
 306
 307 #endif  /* i386 */
 308
 309 #if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \
 310      (defined(__mc68000__)))
 311
 312 #define _EXT2_HAVE_ASM_BITOPS_
 313
 314 _INLINE_ int ext2fs_set_bit(unsigned int nr,void * addr)
 315 {
 316         char retval;
 317
 318         __asm__ __volatile__ ("bfset %2@{%1:#1}; sne %0"
 319              : "=d" (retval) : "d" (nr^7), "a" (addr));
 320
 321         return retval;
 322 }
 323
 324 _INLINE_ int ext2fs_clear_bit(unsigned int nr, void * addr)
 325 {
 326         char retval;
 327
 328         __asm__ __volatile__ ("bfclr %2@{%1:#1}; sne %0"
 329              : "=d" (retval) : "d" (nr^7), "a" (addr));
 330
 331         return retval;
 332 }
 333
 334 _INLINE_ int ext2fs_test_bit(unsigned int nr, const void * addr)
 335 {
 336         char retval;
 337
 338         __asm__ __volatile__ ("bftst %2@{%1:#1}; sne %0"
 339              : "=d" (retval) : "d" (nr^7), "a" (addr));
 340
 341         return retval;
 342 }
 343
 344 #endif /* __mc68000__ */
 345
 346
 347 #if !defined(_EXT2_HAVE_ASM_SWAB_)
 348
 349 _INLINE_ __u16 ext2fs_swab16(__u16 val)
 350 {
 351         return (val >> 8) | (val << 8);
 352 }
 353
 354 _INLINE_ __u32 ext2fs_swab32(__u32 val)
 355 {
 356         return ((val>>24) | ((val>>8)&0xFF00) |
 357                 ((val<<8)&0xFF0000) | (val<<24));
 358 }
 359
 360 #endif /* !_EXT2_HAVE_ASM_SWAB */
 361
 362 #if !defined(_EXT2_HAVE_ASM_FINDBIT_)
 363 #include <strings.h>
 364 _INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size)
 365 {
 366         char    *cp = (char *) addr;
 367         int     res = 0, d0;
 368
 369         if (!size)
 370                 return 0;
 371
 372         while ((size > res) && (*cp == 0)) {
 373                 cp++;
 374                 res += 8;
 375         }
 376         d0 = ffs(*cp);
 377         if (d0 == 0)
 378                 return size;
 379
 380         return res + d0 - 1;
 381 }
 382
 383 _INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset)
 384 {
 385         unsigned char * p;
 386         int set = 0, bit = offset & 7, res = 0, d0;
 387
 388         res = offset >> 3;
 389         p = ((unsigned char *) addr) + res;
 390
 391         if (bit) {
 392                 set = ffs(*p & ~((1 << bit) - 1));
 393                 if (set)
 394                         return (offset & ~7) + set - 1;
 395                 p++;
 396                 res += 8;
 397         }
 398         while ((size > res) && (*p == 0)) {
 399                 p++;
 400                 res += 8;
 401         }
 402         d0 = ffs(*p);
 403         if (d0 == 0)
 404                 return size;
 405
 406         return (res + d0 - 1);
 407 }
 408 #endif
 409
 410 _INLINE_ int ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap,
 411                                        blk_t block)
 412 {
 413         return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 414                                           block);
 415 }
 416
 417 _INLINE_ int ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
 418                                          blk_t block)
 419 {
 420         return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 421                                             block);
 422 }
 423
 424 _INLINE_ int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap,
 425                                        blk_t block)
 426 {
 427         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 428                                           block);
 429 }
 430
 431 _INLINE_ int ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 432                                        ext2_ino_t inode)
 433 {
 434         return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 435                                           inode);
 436 }
 437
 438 _INLINE_ int ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 439                                          ext2_ino_t inode)
 440 {
 441         return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 442                                      inode);
 443 }
 444
 445 _INLINE_ int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
 446                                        ext2_ino_t inode)
 447 {
 448         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 449                                           inode);
 450 }
 451
 452 _INLINE_ void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap,
 453                                             blk_t block)
 454 {
 455         ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap, block);
 456 }
 457
 458 _INLINE_ void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
 459                                               blk_t block)
 460 {
 461         ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap, block);
 462 }
 463
 464 _INLINE_ int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap,
 465                                             blk_t block)
 466 {
 467         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 468                                           block);
 469 }
 470
 471 _INLINE_ void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 472                                             ext2_ino_t inode)
 473 {
 474         ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap, inode);
 475 }
 476
 477 _INLINE_ void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 478                                               ext2_ino_t inode)
 479 {
 480         ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap, inode);
 481 }
 482
 483 _INLINE_ int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
 484                                            ext2_ino_t inode)
 485 {
 486         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 487                                           inode);
 488 }
 489
 490 _INLINE_ blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap)
 491 {
 492         return ext2fs_get_generic_bitmap_start((ext2fs_generic_bitmap) bitmap);
 493 }
 494
 495 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap)
 496 {
 497         return ext2fs_get_generic_bitmap_start((ext2fs_generic_bitmap) bitmap);
 498 }
 499
 500 _INLINE_ blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap)
 501 {
 502         return ext2fs_get_generic_bitmap_end((ext2fs_generic_bitmap) bitmap);
 503 }
 504
 505 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap)
 506 {
 507         return ext2fs_get_generic_bitmap_end((ext2fs_generic_bitmap) bitmap);
 508 }
 509
 510 _INLINE_ int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
 511                                                  blk_t block, int num)
 512 {
 513         return ext2fs_test_block_bitmap_range(bitmap, block, num);
 514 }
 515
 516 _INLINE_ void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 517                                                   blk_t block, int num)
 518 {
 519         ext2fs_mark_block_bitmap_range(bitmap, block, num);
 520 }
 521
 522 _INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 523                                                     blk_t block, int num)
 524 {
 525         ext2fs_unmark_block_bitmap_range(bitmap, block, num);
 526 }
 527 #undef _INLINE_
 528 #endif
 529