bitops.h revision 76f875daa1c9c2cdc72f0c6f0f7be4bbc7f0fc07 
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 void ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap, blk_t block);
39extern void 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 void ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap, ino_t inode);
44extern void ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
45				       ino_t inode);
46extern int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap, 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					  ino_t inode);
57extern void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
58					    ino_t inode);
59extern int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
60					 ino_t inode);
61extern blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap);
62extern ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap);
63extern blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap);
64extern 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
113/*
114 * These are done by inline assembly for speed reasons.....
115 *
116 * All bitoperations return 0 if the bit was cleared before the
117 * operation and != 0 if it was not.  Bit 0 is the LSB of addr; bit 32
118 * is the LSB of (addr+1).
119 */
120
121/*
122 * Some hacks to defeat gcc over-optimizations..
123 */
124struct __dummy_h { unsigned long a[100]; };
125#define EXT2FS_ADDR (*(struct __dummy_h *) addr)
126#define EXT2FS_CONST_ADDR (*(const struct __dummy_h *) addr)
127
128_INLINE_ int ext2fs_set_bit(int nr, void * addr)
129{
130	int oldbit;
131
132	__asm__ __volatile__("btsl %2,%1\n\tsbbl %0,%0"
133		:"=r" (oldbit),"=m" (EXT2FS_ADDR)
134		:"r" (nr));
135	return oldbit;
136}
137
138_INLINE_ int ext2fs_clear_bit(int nr, void * addr)
139{
140	int oldbit;
141
142	__asm__ __volatile__("btrl %2,%1\n\tsbbl %0,%0"
143		:"=r" (oldbit),"=m" (EXT2FS_ADDR)
144		:"r" (nr));
145	return oldbit;
146}
147
148_INLINE_ int ext2fs_test_bit(int nr, const void * addr)
149{
150	int oldbit;
151
152	__asm__ __volatile__("btl %2,%1\n\tsbbl %0,%0"
153		:"=r" (oldbit)
154		:"m" (EXT2FS_CONST_ADDR),"r" (nr));
155	return oldbit;
156}
157
158#undef EXT2FS_ADDR
159
160#endif	/* i386 */
161
162#ifdef __mc68000__
163
164#define _EXT2_HAVE_ASM_BITOPS_
165
166_INLINE_ int ext2fs_set_bit(int nr,void * addr)
167{
168	char retval;
169
170	__asm__ __volatile__ ("bfset %2@{%1:#1}; sne %0"
171	     : "=d" (retval) : "d" (nr^7), "a" (addr));
172
173	return retval;
174}
175
176_INLINE_ int ext2fs_clear_bit(int nr, void * addr)
177{
178	char retval;
179
180	__asm__ __volatile__ ("bfclr %2@{%1:#1}; sne %0"
181	     : "=d" (retval) : "d" (nr^7), "a" (addr));
182
183	return retval;
184}
185
186_INLINE_ int ext2fs_test_bit(int nr, const void * addr)
187{
188	char retval;
189
190	__asm__ __volatile__ ("bftst %2@{%1:#1}; sne %0"
191	     : "=d" (retval) : "d" (nr^7), "a" (addr));
192
193	return retval;
194}
195
196#endif /* __mc68000__ */
197
198#ifdef __sparc__
199
200#define _EXT2_HAVE_ASM_BITOPS_
201
202#ifndef EXT2_OLD_BITOPS
203
204/*
205 * Do the bitops so that we are compatible with the standard i386
206 * convention.
207 */
208
209_INLINE_ int ext2fs_set_bit(int nr,void * addr)
210{
211#if 1
212	int		mask;
213	unsigned char	*ADDR = (unsigned char *) addr;
214
215	ADDR += nr >> 3;
216	mask = 1 << (nr & 0x07);
217	__asm__ __volatile__("ldub	[%0], %%g6\n\t"
218			     "or	%%g6, %2, %%g5\n\t"
219			     "stb	%%g5, [%0]\n\t"
220			     "and	%%g6, %2, %0\n"
221	: "=&r" (ADDR)
222	: "0" (ADDR), "r" (mask)
223	: "g5", "g6");
224	return (int) ADDR;
225#else
226	int		mask, retval;
227	unsigned char	*ADDR = (unsigned char *) addr;
228
229	ADDR += nr >> 3;
230	mask = 1 << (nr & 0x07);
231	retval = (mask & *ADDR) != 0;
232	*ADDR |= mask;
233	return retval;
234#endif
235}
236
237_INLINE_ int ext2fs_clear_bit(int nr, void * addr)
238{
239#if 1
240	int		mask;
241	unsigned char	*ADDR = (unsigned char *) addr;
242
243	ADDR += nr >> 3;
244	mask = 1 << (nr & 0x07);
245	__asm__ __volatile__("ldub	[%0], %%g6\n\t"
246			     "andn	%%g6, %2, %%g5\n\t"
247			     "stb	%%g5, [%0]\n\t"
248			     "and	%%g6, %2, %0\n"
249	: "=&r" (ADDR)
250	: "0" (ADDR), "r" (mask)
251	: "g5", "g6");
252	return (int) ADDR;
253
254#else
255	int		mask, retval;
256	unsigned char	*ADDR = (unsigned char *) addr;
257
258	ADDR += nr >> 3;
259	mask = 1 << (nr & 0x07);
260	retval = (mask & *ADDR) != 0;
261	*ADDR &= ~mask;
262	return retval;
263#endif
264}
265
266_INLINE_ int ext2fs_test_bit(int nr, const void * addr)
267{
268	int			mask;
269	const unsigned char	*ADDR = (const unsigned char *) addr;
270
271	ADDR += nr >> 3;
272	mask = 1 << (nr & 0x07);
273	return ((mask & *ADDR) != 0);
274}
275
276#else
277
278/* Do things the old, unplesant way. */
279
280_INLINE_ int ext2fs_set_bit(int nr, void *addr)
281{
282	int		mask, retval;
283	unsigned long	*ADDR = (unsigned long *) addr;
284
285	ADDR += nr >> 5;
286	mask = 1 << (nr & 31);
287	retval = ((mask & *ADDR) != 0);
288	*ADDR |= mask;
289	return retval;
290}
291
292_INLINE_ int ext2fs_clear_bit(int nr, void *addr)
293{
294	int		mask, retval;
295	unsigned long	*ADDR = (unsigned long *) addr;
296
297	ADDR += nr >> 5;
298	mask = 1 << (nr & 31);
299	retval = ((mask & *ADDR) != 0);
300	*ADDR &= ~mask;
301	return retval;
302}
303
304_INLINE_ int ext2fs_test_bit(int nr, const void *addr)
305{
306	int			mask;
307	const unsigned long	*ADDR = (const unsigned long *) addr;
308
309	ADDR += nr >> 5;
310	mask = 1 << (nr & 31);
311	return ((mask & *ADDR) != 0);
312}
313#endif
314
315#endif /* __sparc__ */
316
317#ifndef _EXT2_HAVE_ASM_SWAB
318
319_INLINE_ __u16 ext2fs_swab16(__u16 val)
320{
321	return (val >> 8) | (val << 8);
322}
323
324_INLINE_ __u32 ext2fs_swab32(__u32 val)
325{
326	return ((val>>24) | ((val>>8)&0xFF00) |
327		((val<<8)&0xFF0000) | (val<<24));
328}
329
330#endif /* !_EXT2_HAVE_ASM_SWAB */
331
332_INLINE_ void ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
333					 __u32 bitno);
334_INLINE_ void ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
335					   blk_t bitno);
336_INLINE_ int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
337					blk_t bitno);
338
339_INLINE_ void ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
340					 __u32 bitno)
341{
342	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
343		ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
344		return;
345	}
346	ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap);
347}
348
349_INLINE_ void ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
350					   blk_t bitno)
351{
352	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
353		ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
354		return;
355	}
356	ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap);
357}
358
359_INLINE_ int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
360					blk_t bitno)
361{
362	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
363		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
364		return 0;
365	}
366	return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
367}
368
369_INLINE_ void ext2fs_mark_block_bitmap(ext2fs_block_bitmap bitmap,
370				       blk_t block)
371{
372	ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap, block);
373}
374
375_INLINE_ void ext2fs_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
376					 blk_t block)
377{
378	ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap, block);
379}
380
381_INLINE_ int ext2fs_test_block_bitmap(ext2fs_block_bitmap bitmap,
382				       blk_t block)
383{
384	return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
385					  block);
386}
387
388_INLINE_ void ext2fs_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
389				       ino_t inode)
390{
391	ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) bitmap, inode);
392}
393
394_INLINE_ void ext2fs_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
395					 ino_t inode)
396{
397	ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) bitmap, inode);
398}
399
400_INLINE_ int ext2fs_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
401				       ino_t inode)
402{
403	return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) bitmap,
404					  inode);
405}
406
407_INLINE_ void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap,
408					    blk_t block)
409{
410#ifdef EXT2FS_DEBUG_FAST_OPS
411	if ((block < bitmap->start) || (block > bitmap->end)) {
412		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
413				   bitmap->description);
414		return;
415	}
416#endif
417	ext2fs_set_bit(block - bitmap->start, bitmap->bitmap);
418}
419
420_INLINE_ void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap,
421					      blk_t block)
422{
423#ifdef EXT2FS_DEBUG_FAST_OPS
424	if ((block < bitmap->start) || (block > bitmap->end)) {
425		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK,
426				   block, bitmap->description);
427		return;
428	}
429#endif
430	ext2fs_clear_bit(block - bitmap->start, bitmap->bitmap);
431}
432
433_INLINE_ int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap,
434					    blk_t block)
435{
436#ifdef EXT2FS_DEBUG_FAST_OPS
437	if ((block < bitmap->start) || (block > bitmap->end)) {
438		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
439				   block, bitmap->description);
440		return 0;
441	}
442#endif
443	return ext2fs_test_bit(block - bitmap->start, bitmap->bitmap);
444}
445
446_INLINE_ void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap,
447					    ino_t inode)
448{
449#ifdef EXT2FS_DEBUG_FAST_OPS
450	if ((inode < bitmap->start) || (inode > bitmap->end)) {
451		ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_MARK,
452				   inode, bitmap->description);
453		return;
454	}
455#endif
456	ext2fs_set_bit(inode - bitmap->start, bitmap->bitmap);
457}
458
459_INLINE_ void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap,
460					      ino_t inode)
461{
462#ifdef EXT2FS_DEBUG_FAST_OPS
463	if ((inode < bitmap->start) || (inode > bitmap->end)) {
464		ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_UNMARK,
465				   inode, bitmap->description);
466		return;
467	}
468#endif
469	ext2fs_clear_bit(inode - bitmap->start, bitmap->bitmap);
470}
471
472_INLINE_ int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap,
473					   ino_t inode)
474{
475#ifdef EXT2FS_DEBUG_FAST_OPS
476	if ((inode < bitmap->start) || (inode > bitmap->end)) {
477		ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
478				   inode, bitmap->description);
479		return 0;
480	}
481#endif
482	return ext2fs_test_bit(inode - bitmap->start, bitmap->bitmap);
483}
484
485_INLINE_ blk_t ext2fs_get_block_bitmap_start(ext2fs_block_bitmap bitmap)
486{
487	return bitmap->start;
488}
489
490_INLINE_ ino_t ext2fs_get_inode_bitmap_start(ext2fs_inode_bitmap bitmap)
491{
492	return bitmap->start;
493}
494
495_INLINE_ blk_t ext2fs_get_block_bitmap_end(ext2fs_block_bitmap bitmap)
496{
497	return bitmap->end;
498}
499
500_INLINE_ ino_t ext2fs_get_inode_bitmap_end(ext2fs_inode_bitmap bitmap)
501{
502	return bitmap->end;
503}
504
505_INLINE_ int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
506					    blk_t block, int num)
507{
508	int	i;
509
510	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
511		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
512				   block, bitmap->description);
513		return 0;
514	}
515	for (i=0; i < num; i++) {
516		if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
517			return 0;
518	}
519	return 1;
520}
521
522_INLINE_ int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
523						 blk_t block, int num)
524{
525	int	i;
526
527#ifdef EXT2FS_DEBUG_FAST_OPS
528	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
529		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
530				   block, bitmap->description);
531		return 0;
532	}
533#endif
534	for (i=0; i < num; i++) {
535		if (ext2fs_fast_test_block_bitmap(bitmap, block+i))
536			return 0;
537	}
538	return 1;
539}
540
541_INLINE_ void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
542					     blk_t block, int num)
543{
544	int	i;
545
546	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
547		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
548				   bitmap->description);
549		return;
550	}
551	for (i=0; i < num; i++)
552		ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap);
553}
554
555_INLINE_ void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
556						  blk_t block, int num)
557{
558	int	i;
559
560#ifdef EXT2FS_DEBUG_FAST_OPS
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#endif
567	for (i=0; i < num; i++)
568		ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap);
569}
570
571_INLINE_ void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
572					       blk_t block, int num)
573{
574	int	i;
575
576	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
577		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
578				   bitmap->description);
579		return;
580	}
581	for (i=0; i < num; i++)
582		ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap);
583}
584
585_INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
586						    blk_t block, int num)
587{
588	int	i;
589
590#ifdef EXT2FS_DEBUG_FAST_OPS
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#endif
597	for (i=0; i < num; i++)
598		ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap);
599}
600
601#undef _INLINE_
602#endif
603
604