1 /*
2  * bitops.c --- Bitmap frobbing code.  See bitops.h for the inlined
3  * 	routines.
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 Library
9  * General Public License, version 2.
10  * %End-Header%
11  */
12 
13 #include "config.h"
14 #include <stdio.h>
15 #if HAVE_SYS_TYPES_H
16 #include <sys/types.h>
17 #endif
18 
19 #include "ext2_fs.h"
20 #include "ext2fs.h"
21 
22 #ifndef _EXT2_HAVE_ASM_BITOPS_
23 
24 /*
25  * For the benefit of those who are trying to port Linux to another
26  * architecture, here are some C-language equivalents.  You should
27  * recode these in the native assembly language, if at all possible.
28  *
29  * C language equivalents written by Theodore Ts'o, 9/26/92.
30  * Modified by Pete A. Zaitcev 7/14/95 to be portable to big endian
31  * systems, as well as non-32 bit systems.
32  */
33 
ext2fs_set_bit(unsigned int nr,void * addr)34 int ext2fs_set_bit(unsigned int nr,void * addr)
35 {
36 	int		mask, retval;
37 	unsigned char	*ADDR = (unsigned char *) addr;
38 
39 	ADDR += nr >> 3;
40 	mask = 1 << (nr & 0x07);
41 	retval = mask & *ADDR;
42 	*ADDR |= mask;
43 	return retval;
44 }
45 
ext2fs_clear_bit(unsigned int nr,void * addr)46 int ext2fs_clear_bit(unsigned int nr, void * addr)
47 {
48 	int		mask, retval;
49 	unsigned char	*ADDR = (unsigned char *) addr;
50 
51 	ADDR += nr >> 3;
52 	mask = 1 << (nr & 0x07);
53 	retval = mask & *ADDR;
54 	*ADDR &= ~mask;
55 	return retval;
56 }
57 
ext2fs_test_bit(unsigned int nr,const void * addr)58 int ext2fs_test_bit(unsigned int nr, const void * addr)
59 {
60 	int			mask;
61 	const unsigned char	*ADDR = (const unsigned char *) addr;
62 
63 	ADDR += nr >> 3;
64 	mask = 1 << (nr & 0x07);
65 	return (mask & *ADDR);
66 }
67 
68 #endif	/* !_EXT2_HAVE_ASM_BITOPS_ */
69 
ext2fs_warn_bitmap(errcode_t errcode,unsigned long arg,const char * description)70 void ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg,
71 			const char *description)
72 {
73 #ifndef OMIT_COM_ERR
74 	if (description)
75 		com_err(0, errcode, "#%lu for %s", arg, description);
76 	else
77 		com_err(0, errcode, "#%lu", arg);
78 #endif
79 }
80 
81 /*
82  * C-only 64 bit ops.
83  */
84 
ext2fs_set_bit64(__u64 nr,void * addr)85 int ext2fs_set_bit64(__u64 nr, void * addr)
86 {
87 	int		mask, retval;
88 	unsigned char	*ADDR = (unsigned char *) addr;
89 
90 	ADDR += nr >> 3;
91 	mask = 1 << (nr & 0x07);
92 	retval = mask & *ADDR;
93 	*ADDR |= mask;
94 	return retval;
95 }
96 
ext2fs_clear_bit64(__u64 nr,void * addr)97 int ext2fs_clear_bit64(__u64 nr, void * addr)
98 {
99 	int		mask, retval;
100 	unsigned char	*ADDR = (unsigned char *) addr;
101 
102 	ADDR += nr >> 3;
103 	mask = 1 << (nr & 0x07);
104 	retval = mask & *ADDR;
105 	*ADDR &= ~mask;
106 	return retval;
107 }
108 
ext2fs_test_bit64(__u64 nr,const void * addr)109 int ext2fs_test_bit64(__u64 nr, const void * addr)
110 {
111 	int			mask;
112 	const unsigned char	*ADDR = (const unsigned char *) addr;
113 
114 	ADDR += nr >> 3;
115 	mask = 1 << (nr & 0x07);
116 	return (mask & *ADDR);
117 }
118 
popcount8(unsigned int w)119 static unsigned int popcount8(unsigned int w)
120 {
121 	unsigned int res = w - ((w >> 1) & 0x55);
122 	res = (res & 0x33) + ((res >> 2) & 0x33);
123 	return (res + (res >> 4)) & 0x0F;
124 }
125 
popcount32(unsigned int w)126 static unsigned int popcount32(unsigned int w)
127 {
128 	unsigned int res = w - ((w >> 1) & 0x55555555);
129 	res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
130 	res = (res + (res >> 4)) & 0x0F0F0F0F;
131 	res = res + (res >> 8);
132 	return (res + (res >> 16)) & 0x000000FF;
133 }
134 
ext2fs_bitcount(const void * addr,unsigned int nbytes)135 unsigned int ext2fs_bitcount(const void *addr, unsigned int nbytes)
136 {
137 	const unsigned char *cp = addr;
138 	const __u32 *p;
139 	unsigned int res = 0;
140 
141 	while (((((uintptr_t) cp) & 3) != 0) && (nbytes > 0)) {
142 		res += popcount8(*cp++);
143 		nbytes--;
144 	}
145 	p = (const __u32 *) cp;
146 
147 	while (nbytes > 4) {
148 		res += popcount32(*p++);
149 		nbytes -= 4;
150 	}
151 	cp = (const unsigned char *) p;
152 
153 	while (nbytes > 0) {
154 		res += popcount8(*cp++);
155 		nbytes--;
156 	}
157 	return res;
158 }
159