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 #undef EXT2FS_ADDR
 278
 279 #endif  /* i386 */
 280
 281 #if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \
 282      (defined(__mc68000__)))
 283
 284 #define _EXT2_HAVE_ASM_BITOPS_
 285
 286 _INLINE_ int ext2fs_set_bit(unsigned int nr,void * addr)
 287 {
 288         char retval;
 289
 290         __asm__ __volatile__ ("bfset %2@{%1:#1}; sne %0"
 291              : "=d" (retval) : "d" (nr^7), "a" (addr));
 292
 293         return retval;
 294 }
 295
 296 _INLINE_ int ext2fs_clear_bit(unsigned int nr, void * addr)
 297 {
 298         char retval;
 299
 300         __asm__ __volatile__ ("bfclr %2@{%1:#1}; sne %0"
 301              : "=d" (retval) : "d" (nr^7), "a" (addr));
 302
 303         return retval;
 304 }
 305
 306 _INLINE_ int ext2fs_test_bit(unsigned int nr, const void * addr)
 307 {
 308         char retval;
 309
 310         __asm__ __volatile__ ("bftst %2@{%1:#1}; sne %0"
 311              : "=d" (retval) : "d" (nr^7), "a" (addr));
 312
 313         return retval;
 314 }
 315
 316 #endif /* __mc68000__ */
 317
 318
 319 #if !defined(_EXT2_HAVE_ASM_SWAB_) && defined(WORDS_BIGENDIAN)
 320
 321 _INLINE_ __u16 ext2fs_swab16(__u16 val)
 322 {
 323         return (val >> 8) | (val << 8);
 324 }
 325
 326 _INLINE_ __u32 ext2fs_swab32(__u32 val)
 327 {
 328         return ((val>>24) | ((val>>8)&0xFF00) |
 329                 ((val<<8)&0xFF0000) | (val<<24));
 330 }
 331
 332 #endif /* !_EXT2_HAVE_ASM_SWAB */
 333
 334 #if !defined(_EXT2_HAVE_ASM_FINDBIT_)
 335 #include <strings.h>
 336 _INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size)
 337 {
 338         char    *cp = (char *) addr;
 339         int     res = 0, d0;
 340
 341         if (!size)
 342                 return 0;
 343
 344         while ((size > res) && (*cp == 0)) {
 345                 cp++;
 346                 res += 8;
 347         }
 348         d0 = ffs(*cp);
 349         if (d0 == 0)
 350                 return size;
 351
 352         return res + d0 - 1;
 353 }
 354
 355 _INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset)
 356 {
 357         unsigned char * p;
 358         int set = 0, bit = offset & 7, res = 0, d0;
 359
 360         res = offset >> 3;
 361         p = ((unsigned char *) addr) + res;
 362
 363         if (bit) {
 364                 set = ffs(*p & ~((1 << bit) - 1));
 365                 if (set)
 366                         return (offset & ~7) + set - 1;
 367                 p++;
 368                 res += 8;
 369         }
 370         while ((size > res) && (*p == 0)) {
 371                 p++;
 372                 res += 8;
 373         }
 374         d0 = ffs(*p);
 375         if (d0 == 0)
 376                 return size;
 377
 378         return (res + d0 - 1);
 379 }
 380 #endif
 381
 382 _INLINE_ int ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap,
 383                                        blk_t block)
 384 {
 385         return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 386                                           block);
 387 }
 388
 389 _INLINE_ int ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
 390                                          blk_t block)
 391 {
 392         return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 393                                             block);
 394 }
 395
 396 _INLINE_ int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap,
 397                                        blk_t block)
 398 {
 399         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 400                                           block);
 401 }
 402
 403 _INLINE_ int ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 404                                        ext2_ino_t inode)
 405 {
 406         return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 407                                           inode);
 408 }
 409
 410 _INLINE_ int ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 411                                          ext2_ino_t inode)
 412 {
 413         return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 414                                      inode);
 415 }
 416
 417 _INLINE_ int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
 418                                        ext2_ino_t inode)
 419 {
 420         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 421                                           inode);
 422 }
 423
 424 _INLINE_ void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap,
 425                                             blk_t block)
 426 {
 427         ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap, block);
 428 }
 429
 430 _INLINE_ void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
 431                                               blk_t block)
 432 {
 433         ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap, block);
 434 }
 435
 436 _INLINE_ int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap,
 437                                             blk_t block)
 438 {
 439         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 440                                           block);
 441 }
 442
 443 _INLINE_ void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 444                                             ext2_ino_t inode)
 445 {
 446         ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap, inode);
 447 }
 448
 449 _INLINE_ void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
 450                                               ext2_ino_t inode)
 451 {
 452         ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap, inode);
 453 }
 454
 455 _INLINE_ int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
 456                                            ext2_ino_t inode)
 457 {
 458         return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
 459                                           inode);
 460 }
 461
 462 _INLINE_ blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap)
 463 {
 464         return ext2fs_get_generic_bitmap_start((ext2fs_generic_bitmap) bitmap);
 465 }
 466
 467 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap)
 468 {
 469         return ext2fs_get_generic_bitmap_start((ext2fs_generic_bitmap) bitmap);
 470 }
 471
 472 _INLINE_ blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap)
 473 {
 474         return ext2fs_get_generic_bitmap_end((ext2fs_generic_bitmap) bitmap);
 475 }
 476
 477 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap)
 478 {
 479         return ext2fs_get_generic_bitmap_end((ext2fs_generic_bitmap) bitmap);
 480 }
 481
 482 _INLINE_ int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
 483                                                  blk_t block, int num)
 484 {
 485         return ext2fs_test_block_bitmap_range(bitmap, block, num);
 486 }
 487
 488 _INLINE_ void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 489                                                   blk_t block, int num)
 490 {
 491         ext2fs_mark_block_bitmap_range(bitmap, block, num);
 492 }
 493
 494 _INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 495                                                     blk_t block, int num)
 496 {
 497         ext2fs_unmark_block_bitmap_range(bitmap, block, num);
 498 }
 499 #undef _INLINE_
 500 #endif
 501