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