bitops.h revision 80af12e180bdea9ed391a0aee58e31cee7641709 
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(unsigned int nr,void * addr);
18extern int ext2fs_clear_bit(unsigned int nr, void * addr);
19extern int ext2fs_test_bit(unsigned 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(unsigned 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(unsigned 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(unsigned 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(unsigned 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(unsigned 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(unsigned 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