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 /*
23 * C language bitmap functions written by Theodore Ts'o, 9/26/92.
24 * Modified by Pete A. Zaitcev 7/14/95 to be portable to big endian
25 * systems, as well as non-32 bit systems.
26 */
27
ext2fs_set_bit(unsigned int nr,void * addr)28 int ext2fs_set_bit(unsigned int nr,void * addr)
29 {
30 int mask, retval;
31 unsigned char *ADDR = (unsigned char *) addr;
32
33 ADDR += nr >> 3;
34 mask = 1 << (nr & 0x07);
35 retval = mask & *ADDR;
36 *ADDR |= mask;
37 return retval;
38 }
39
ext2fs_clear_bit(unsigned int nr,void * addr)40 int ext2fs_clear_bit(unsigned int nr, void * addr)
41 {
42 int mask, retval;
43 unsigned char *ADDR = (unsigned char *) addr;
44
45 ADDR += nr >> 3;
46 mask = 1 << (nr & 0x07);
47 retval = mask & *ADDR;
48 *ADDR &= ~mask;
49 return retval;
50 }
51
ext2fs_test_bit(unsigned int nr,const void * addr)52 int ext2fs_test_bit(unsigned int nr, const void * addr)
53 {
54 int mask;
55 const unsigned char *ADDR = (const unsigned char *) addr;
56
57 ADDR += nr >> 3;
58 mask = 1 << (nr & 0x07);
59 return (mask & *ADDR);
60 }
61
ext2fs_warn_bitmap(errcode_t errcode,unsigned long arg,const char * description)62 void ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg,
63 const char *description)
64 {
65 #ifndef OMIT_COM_ERR
66 if (description)
67 com_err(0, errcode, "#%lu for %s", arg, description);
68 else
69 com_err(0, errcode, "#%lu", arg);
70 #endif
71 }
72
73 /* Bitmap functions that take a 64-bit offset */
74
ext2fs_set_bit64(__u64 nr,void * addr)75 int ext2fs_set_bit64(__u64 nr, void * addr)
76 {
77 int mask, retval;
78 unsigned char *ADDR = (unsigned char *) addr;
79
80 ADDR += nr >> 3;
81 mask = 1 << (nr & 0x07);
82 retval = mask & *ADDR;
83 *ADDR |= mask;
84 return retval;
85 }
86
ext2fs_clear_bit64(__u64 nr,void * addr)87 int ext2fs_clear_bit64(__u64 nr, void * addr)
88 {
89 int mask, retval;
90 unsigned char *ADDR = (unsigned char *) addr;
91
92 ADDR += nr >> 3;
93 mask = 1 << (nr & 0x07);
94 retval = mask & *ADDR;
95 *ADDR &= ~mask;
96 return retval;
97 }
98
ext2fs_test_bit64(__u64 nr,const void * addr)99 int ext2fs_test_bit64(__u64 nr, const void * addr)
100 {
101 int mask;
102 const unsigned char *ADDR = (const unsigned char *) addr;
103
104 ADDR += nr >> 3;
105 mask = 1 << (nr & 0x07);
106 return (mask & *ADDR);
107 }
108
popcount8(unsigned int w)109 static unsigned int popcount8(unsigned int w)
110 {
111 unsigned int res = w - ((w >> 1) & 0x55);
112 res = (res & 0x33) + ((res >> 2) & 0x33);
113 return (res + (res >> 4)) & 0x0F;
114 }
115
popcount32(unsigned int w)116 static unsigned int popcount32(unsigned int w)
117 {
118 unsigned int res = w - ((w >> 1) & 0x55555555);
119 res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
120 res = (res + (res >> 4)) & 0x0F0F0F0F;
121 res = res + (res >> 8);
122 return (res + (res >> 16)) & 0x000000FF;
123 }
124
ext2fs_bitcount(const void * addr,unsigned int nbytes)125 unsigned int ext2fs_bitcount(const void *addr, unsigned int nbytes)
126 {
127 const unsigned char *cp = addr;
128 const __u32 *p;
129 unsigned int res = 0;
130
131 while (((((uintptr_t) cp) & 3) != 0) && (nbytes > 0)) {
132 res += popcount8(*cp++);
133 nbytes--;
134 }
135 p = (const __u32 *) cp;
136
137 while (nbytes > 4) {
138 res += popcount32(*p++);
139 nbytes -= 4;
140 }
141 cp = (const unsigned char *) p;
142
143 while (nbytes > 0) {
144 res += popcount8(*cp++);
145 nbytes--;
146 }
147 return res;
148 }
149