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