2 * bitops.h --- Bitmap frobbing code. The byte swapping routines are
5 * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o.
8 * This file may be redistributed under the terms of the GNU Public
12 * i386 bitops operations taken from <asm/bitops.h>, Copyright 1992,
17 extern int ext2fs_set_bit(int nr,void * addr);
18 extern int ext2fs_clear_bit(int nr, void * addr);
19 extern int ext2fs_test_bit(int nr, const void * addr);
20 extern __u16 ext2fs_swab16(__u16 val);
21 extern __u32 ext2fs_swab32(__u32 val);
24 * EXT2FS bitmap manipulation routines.
27 /* Support for sending warning messages from the inline subroutines */
28 extern const char *ext2fs_block_string;
29 extern const char *ext2fs_inode_string;
30 extern const char *ext2fs_mark_string;
31 extern const char *ext2fs_unmark_string;
32 extern const char *ext2fs_test_string;
33 extern void ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg,
34 const char *description);
35 extern void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap,
36 int code, unsigned long arg);
38 extern int ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap, blk_t block);
39 extern int ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
41 extern int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap, blk_t block);
43 extern int ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap, ext2_ino_t inode);
44 extern int ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
46 extern int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap, ext2_ino_t inode);
48 extern void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap,
50 extern void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
52 extern int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap,
55 extern void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
57 extern void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
59 extern int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
61 extern blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap);
62 extern ext2_ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap);
63 extern blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap);
64 extern ext2_ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap);
66 extern void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
67 blk_t block, int num);
68 extern void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
69 blk_t block, int num);
70 extern int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
71 blk_t block, int num);
72 extern void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
73 blk_t block, int num);
74 extern void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
75 blk_t block, int num);
76 extern int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
77 blk_t block, int num);
78 extern void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map);
81 * The inline routines themselves...
83 * If NO_INLINE_FUNCS is defined, then we won't try to do inline
84 * functions at all; they will be included as normal functions in
87 #ifdef NO_INLINE_FUNCS
88 #if (defined(__GNUC__) && (defined(__i386__) || defined(__i486__) || \
89 defined(__i586__) || defined(__mc68000__) || \
91 /* This prevents bitops.c from trying to include the C */
92 /* function version of these functions */
93 #define _EXT2_HAVE_ASM_BITOPS_
95 #endif /* NO_INLINE_FUNCS */
97 #if (defined(INCLUDE_INLINE_FUNCS) || !defined(NO_INLINE_FUNCS))
98 #ifdef INCLUDE_INLINE_FUNCS
99 #define _INLINE_ extern
102 #define _INLINE_ extern __inline__
103 #else /* For Watcom C */
104 #define _INLINE_ extern inline
108 #if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \
109 (defined(__i386__) || defined(__i486__) || defined(__i586__)))
111 #define _EXT2_HAVE_ASM_BITOPS_
112 #define _EXT2_HAVE_ASM_SWAB_
113 #define _EXT2_HAVE_ASM_FINDBIT_
116 * These are done by inline assembly for speed reasons.....
118 * All bitoperations return 0 if the bit was cleared before the
119 * operation and != 0 if it was not. Bit 0 is the LSB of addr; bit 32
120 * is the LSB of (addr+1).
124 * Some hacks to defeat gcc over-optimizations..
126 struct __dummy_h { unsigned long a[100]; };
127 #define EXT2FS_ADDR (*(struct __dummy_h *) addr)
128 #define EXT2FS_CONST_ADDR (*(const struct __dummy_h *) addr)
130 _INLINE_ int ext2fs_set_bit(int nr, void * addr)
134 __asm__ __volatile__("btsl %2,%1\n\tsbbl %0,%0"
135 :"=r" (oldbit),"=m" (EXT2FS_ADDR)
140 _INLINE_ int ext2fs_clear_bit(int nr, void * addr)
144 __asm__ __volatile__("btrl %2,%1\n\tsbbl %0,%0"
145 :"=r" (oldbit),"=m" (EXT2FS_ADDR)
150 _INLINE_ int ext2fs_test_bit(int nr, const void * addr)
154 __asm__ __volatile__("btl %2,%1\n\tsbbl %0,%0"
156 :"m" (EXT2FS_CONST_ADDR),"r" (nr));
161 _INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size)
168 /* This looks at memory. Mark it volatile to tell gcc not to move it around */
169 __asm__ __volatile__(
171 "xorl %%eax,%%eax\n\t"
172 "xorl %%edx,%%edx\n\t"
175 "movl -4(%%edi),%%eax\n\t"
178 "1:\tsubl %%esi,%%edi\n\t"
181 :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
182 :"1" ((size + 31) >> 5), "2" (addr), "S" (addr));
186 _INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset)
188 unsigned long * p = ((unsigned long *) addr) + (offset >> 5);
189 int set = 0, bit = offset & 31, res;
193 * Look for zero in first byte
195 __asm__("bsfl %1,%0\n\t"
201 if (set < (32 - bit))
207 * No bit found yet, search remaining full bytes for a bit
209 res = ext2fs_find_first_bit_set(p, size - 32 * (p - (unsigned long *) addr));
210 return (offset + set + res);
214 #ifdef EXT2FS_ENABLE_SWAPFS
215 _INLINE_ __u32 ext2fs_swab32(__u32 val)
217 #ifdef EXT2FS_REQUIRE_486
218 __asm__("bswap %0" : "=r" (val) : "0" (val));
220 __asm__("xchgb %b0,%h0\n\t" /* swap lower bytes */
221 "rorl $16,%0\n\t" /* swap words */
222 "xchgb %b0,%h0" /* swap higher bytes */
229 _INLINE_ __u16 ext2fs_swab16(__u16 val)
231 __asm__("xchgb %b0,%h0" /* swap bytes */ \
244 #define _EXT2_HAVE_ASM_BITOPS_
246 _INLINE_ int ext2fs_set_bit(int nr,void * addr)
250 __asm__ __volatile__ ("bfset %2@{%1:#1}; sne %0"
251 : "=d" (retval) : "d" (nr^7), "a" (addr));
256 _INLINE_ int ext2fs_clear_bit(int nr, void * addr)
260 __asm__ __volatile__ ("bfclr %2@{%1:#1}; sne %0"
261 : "=d" (retval) : "d" (nr^7), "a" (addr));
266 _INLINE_ int ext2fs_test_bit(int nr, const void * addr)
270 __asm__ __volatile__ ("bftst %2@{%1:#1}; sne %0"
271 : "=d" (retval) : "d" (nr^7), "a" (addr));
276 #endif /* __mc68000__ */
280 #define _EXT2_HAVE_ASM_BITOPS_
282 #ifndef EXT2_OLD_BITOPS
285 * Do the bitops so that we are compatible with the standard i386
289 _INLINE_ int ext2fs_set_bit(int nr,void * addr)
293 unsigned char *ADDR = (unsigned char *) addr;
296 mask = 1 << (nr & 0x07);
297 __asm__ __volatile__("ldub [%0], %%g6\n\t"
298 "or %%g6, %2, %%g5\n\t"
302 : "0" (ADDR), "r" (mask)
307 unsigned char *ADDR = (unsigned char *) addr;
310 mask = 1 << (nr & 0x07);
311 retval = (mask & *ADDR) != 0;
317 _INLINE_ int ext2fs_clear_bit(int nr, void * addr)
321 unsigned char *ADDR = (unsigned char *) addr;
324 mask = 1 << (nr & 0x07);
325 __asm__ __volatile__("ldub [%0], %%g6\n\t"
326 "andn %%g6, %2, %%g5\n\t"
330 : "0" (ADDR), "r" (mask)
336 unsigned char *ADDR = (unsigned char *) addr;
339 mask = 1 << (nr & 0x07);
340 retval = (mask & *ADDR) != 0;
346 _INLINE_ int ext2fs_test_bit(int nr, const void * addr)
349 const unsigned char *ADDR = (const unsigned char *) addr;
352 mask = 1 << (nr & 0x07);
353 return ((mask & *ADDR) != 0);
358 /* Do things the old, unplesant way. */
360 _INLINE_ int ext2fs_set_bit(int nr, void *addr)
363 unsigned long *ADDR = (unsigned long *) addr;
366 mask = 1 << (nr & 31);
367 retval = ((mask & *ADDR) != 0);
372 _INLINE_ int ext2fs_clear_bit(int nr, void *addr)
375 unsigned long *ADDR = (unsigned long *) addr;
378 mask = 1 << (nr & 31);
379 retval = ((mask & *ADDR) != 0);
384 _INLINE_ int ext2fs_test_bit(int nr, const void *addr)
387 const unsigned long *ADDR = (const unsigned long *) addr;
390 mask = 1 << (nr & 31);
391 return ((mask & *ADDR) != 0);
395 #endif /* __sparc__ */
397 #if !defined(_EXT2_HAVE_ASM_SWAB_) && defined(EXT2FS_ENABLE_SWAPFS)
399 _INLINE_ __u16 ext2fs_swab16(__u16 val)
401 return (val >> 8) | (val << 8);
404 _INLINE_ __u32 ext2fs_swab32(__u32 val)
406 return ((val>>24) | ((val>>8)&0xFF00) |
407 ((val<<8)&0xFF0000) | (val<<24));
410 #endif /* !_EXT2_HAVE_ASM_SWAB */
412 #if !defined(_EXT2_HAVE_ASM_FINDBIT_)
413 /* Use the prototype from builtin_ffs() */
414 extern int ffs(unsigned int);
416 _INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size)
418 unsigned char *cp = (unsigned char *) addr;
424 while ((size > res) && (*cp == 0)) {
435 _INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset)
438 int set = 0, bit = offset & 7, res = 0, d0;
441 p = ((unsigned char *) addr) + res;
444 set = ffs(*p & ~((1 << bit) - 1));
446 return (offset & ~7) + set - 1;
450 while ((size > res) && (*p == 0)) {
458 return (res + d0 - 1);
462 /* These two routines moved to gen_bitmap.c */
463 extern int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
465 extern int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
467 _INLINE_ int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
470 _INLINE_ int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
473 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
474 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
477 return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
480 _INLINE_ int ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap,
483 return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap)
488 _INLINE_ int ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
491 return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
495 _INLINE_ int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap,
498 return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
502 _INLINE_ int ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
505 return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
509 _INLINE_ int ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
512 return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
516 _INLINE_ int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
519 return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
523 _INLINE_ void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap,
526 #ifdef EXT2FS_DEBUG_FAST_OPS
527 if ((block < bitmap->start) || (block > bitmap->end)) {
528 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
529 bitmap->description);
533 ext2fs_set_bit(block - bitmap->start, bitmap->bitmap);
536 _INLINE_ void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
539 #ifdef EXT2FS_DEBUG_FAST_OPS
540 if ((block < bitmap->start) || (block > bitmap->end)) {
541 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK,
542 block, bitmap->description);
546 ext2fs_clear_bit(block - bitmap->start, bitmap->bitmap);
549 _INLINE_ int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap,
552 #ifdef EXT2FS_DEBUG_FAST_OPS
553 if ((block < bitmap->start) || (block > bitmap->end)) {
554 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
555 block, bitmap->description);
559 return ext2fs_test_bit(block - bitmap->start, bitmap->bitmap);
562 _INLINE_ void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
565 #ifdef EXT2FS_DEBUG_FAST_OPS
566 if ((inode < bitmap->start) || (inode > bitmap->end)) {
567 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_MARK,
568 inode, bitmap->description);
572 ext2fs_set_bit(inode - bitmap->start, bitmap->bitmap);
575 _INLINE_ void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
578 #ifdef EXT2FS_DEBUG_FAST_OPS
579 if ((inode < bitmap->start) || (inode > bitmap->end)) {
580 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_UNMARK,
581 inode, bitmap->description);
585 ext2fs_clear_bit(inode - bitmap->start, bitmap->bitmap);
588 _INLINE_ int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
591 #ifdef EXT2FS_DEBUG_FAST_OPS
592 if ((inode < bitmap->start) || (inode > bitmap->end)) {
593 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
594 inode, bitmap->description);
598 return ext2fs_test_bit(inode - bitmap->start, bitmap->bitmap);
601 _INLINE_ blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap)
603 return bitmap->start;
606 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap)
608 return bitmap->start;
611 _INLINE_ blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap)
616 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap)
621 _INLINE_ int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
622 blk_t block, int num)
626 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
627 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
628 block, bitmap->description);
631 for (i=0; i < num; i++) {
632 if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
638 _INLINE_ int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
639 blk_t block, int num)
643 #ifdef EXT2FS_DEBUG_FAST_OPS
644 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
645 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
646 block, bitmap->description);
650 for (i=0; i < num; i++) {
651 if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
657 _INLINE_ void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
658 blk_t block, int num)
662 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
663 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
664 bitmap->description);
667 for (i=0; i < num; i++)
668 ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap);
671 _INLINE_ void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
672 blk_t block, int num)
676 #ifdef EXT2FS_DEBUG_FAST_OPS
677 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
678 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
679 bitmap->description);
683 for (i=0; i < num; i++)
684 ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap);
687 _INLINE_ void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
688 blk_t block, int num)
692 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
693 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
694 bitmap->description);
697 for (i=0; i < num; i++)
698 ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap);
701 _INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
702 blk_t block, int num)
706 #ifdef EXT2FS_DEBUG_FAST_OPS
707 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
708 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
709 bitmap->description);
713 for (i=0; i < num; i++)
714 ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap);