bitops.h revision 01c196b4f121cb77f50b9af2c54838aa4c6e06a0
1a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)/* 2a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * bitops.h --- Bitmap frobbing code. The byte swapping routines are 3a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * also included here. 4a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * 5a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o. 6a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * 7a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * %Begin-Header% 8a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * This file may be redistributed under the terms of the GNU Public 9a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * License. 10a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * %End-Header% 11a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * 12a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * i386 bitops operations taken from <asm/bitops.h>, Copyright 1992, 13a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) * Linus Torvalds. 14a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) */ 15a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 16a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 17a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)extern int ext2fs_set_bit(unsigned int nr,void * addr); 18a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)extern int ext2fs_clear_bit(unsigned int nr, void * addr); 19a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)extern int ext2fs_test_bit(unsigned int nr, const void * addr); 203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)extern void ext2fs_fast_set_bit(unsigned int nr,void * addr); 21a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)extern void ext2fs_fast_clear_bit(unsigned int nr, void * addr); 22a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)extern __u16 ext2fs_swab16(__u16 val); 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdochextern __u32 ext2fs_swab32(__u32 val); 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)extern __u64 ext2fs_swab64(__u64 val); 256e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 266e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#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 */ 55extern const char *ext2fs_block_string; 56extern const char *ext2fs_inode_string; 57extern const char *ext2fs_mark_string; 58extern const char *ext2fs_unmark_string; 59extern const char *ext2fs_test_string; 60extern void ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg, 61 const char *description); 62extern void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap, 63 int code, unsigned long arg); 64 65extern int ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap, blk_t block); 66extern int ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap, 67 blk_t block); 68extern int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap, blk_t block); 69 70extern int ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap, ext2_ino_t inode); 71extern int ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap, 72 ext2_ino_t inode); 73extern int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap, ext2_ino_t inode); 74 75extern void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap, 76 blk_t block); 77extern void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap, 78 blk_t block); 79extern int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap, 80 blk_t block); 81 82extern void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap, 83 ext2_ino_t inode); 84extern void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap, 85 ext2_ino_t inode); 86extern int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap, 87 ext2_ino_t inode); 88extern blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap); 89extern ext2_ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap); 90extern blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap); 91extern ext2_ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap); 92 93extern void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, 94 blk_t block, int num); 95extern void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, 96 blk_t block, int num); 97extern int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap, 98 blk_t block, int num); 99extern void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, 100 blk_t block, int num); 101extern void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, 102 blk_t block, int num); 103extern int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap, 104 blk_t block, int num); 105extern void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map); 106 107/* These routines moved to gen_bitmap.c */ 108extern int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap, 109 __u32 bitno); 110extern int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap, 111 blk_t bitno); 112extern int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap, 113 blk_t bitno); 114extern int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap, 115 blk_t block, int num); 116extern __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap); 117extern __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 */ 186struct __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 502