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