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 _INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size)
415 char *cp = (unsigned char *) addr;
421 while ((size > res) && (*cp == 0)) {
432 _INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset)
435 int set = 0, bit = offset & 7, res = 0, d0;
438 p = ((unsigned char *) addr) + res;
441 set = ffs(*p & ~((1 << bit) - 1));
443 return (offset & ~7) + set - 1;
447 while ((size > res) && (*p == 0)) {
455 return (res + d0 - 1);
459 /* These two routines moved to gen_bitmap.c */
460 extern int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
462 extern int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
464 _INLINE_ int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
467 _INLINE_ int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
470 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
471 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
474 return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
477 _INLINE_ int ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap,
480 return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap)
485 _INLINE_ int ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
488 return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
492 _INLINE_ int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap,
495 return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
499 _INLINE_ int ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
502 return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
506 _INLINE_ int ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
509 return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap,
513 _INLINE_ int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
516 return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
520 _INLINE_ void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap,
523 #ifdef EXT2FS_DEBUG_FAST_OPS
524 if ((block < bitmap->start) || (block > bitmap->end)) {
525 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
526 bitmap->description);
530 ext2fs_set_bit(block - bitmap->start, bitmap->bitmap);
533 _INLINE_ void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
536 #ifdef EXT2FS_DEBUG_FAST_OPS
537 if ((block < bitmap->start) || (block > bitmap->end)) {
538 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK,
539 block, bitmap->description);
543 ext2fs_clear_bit(block - bitmap->start, bitmap->bitmap);
546 _INLINE_ int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap,
549 #ifdef EXT2FS_DEBUG_FAST_OPS
550 if ((block < bitmap->start) || (block > bitmap->end)) {
551 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
552 block, bitmap->description);
556 return ext2fs_test_bit(block - bitmap->start, bitmap->bitmap);
559 _INLINE_ void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
562 #ifdef EXT2FS_DEBUG_FAST_OPS
563 if ((inode < bitmap->start) || (inode > bitmap->end)) {
564 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_MARK,
565 inode, bitmap->description);
569 ext2fs_set_bit(inode - bitmap->start, bitmap->bitmap);
572 _INLINE_ void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
575 #ifdef EXT2FS_DEBUG_FAST_OPS
576 if ((inode < bitmap->start) || (inode > bitmap->end)) {
577 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_UNMARK,
578 inode, bitmap->description);
582 ext2fs_clear_bit(inode - bitmap->start, bitmap->bitmap);
585 _INLINE_ int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
588 #ifdef EXT2FS_DEBUG_FAST_OPS
589 if ((inode < bitmap->start) || (inode > bitmap->end)) {
590 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
591 inode, bitmap->description);
595 return ext2fs_test_bit(inode - bitmap->start, bitmap->bitmap);
598 _INLINE_ blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap)
600 return bitmap->start;
603 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap)
605 return bitmap->start;
608 _INLINE_ blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap)
613 _INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap)
618 _INLINE_ int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
619 blk_t block, int num)
623 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
624 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
625 block, bitmap->description);
628 for (i=0; i < num; i++) {
629 if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
635 _INLINE_ int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
636 blk_t block, int num)
640 #ifdef EXT2FS_DEBUG_FAST_OPS
641 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
642 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
643 block, bitmap->description);
647 for (i=0; i < num; i++) {
648 if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
654 _INLINE_ void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
655 blk_t block, int num)
659 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
660 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
661 bitmap->description);
664 for (i=0; i < num; i++)
665 ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap);
668 _INLINE_ void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
669 blk_t block, int num)
673 #ifdef EXT2FS_DEBUG_FAST_OPS
674 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
675 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
676 bitmap->description);
680 for (i=0; i < num; i++)
681 ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap);
684 _INLINE_ void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
685 blk_t block, int num)
689 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
690 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
691 bitmap->description);
694 for (i=0; i < num; i++)
695 ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap);
698 _INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
699 blk_t block, int num)
703 #ifdef EXT2FS_DEBUG_FAST_OPS
704 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
705 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
706 bitmap->description);
710 for (i=0; i < num; i++)
711 ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap);