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