1 /*
2 * Bitfield
3 * Copyright (c) 2013, Jouni Malinen <j@w1.fi>
4 *
5 * This software may be distributed under the terms of the BSD license.
6 * See README for more details.
7 */
8
9 #include "includes.h"
10
11 #include "common.h"
12 #include "bitfield.h"
13
14
15 struct bitfield {
16 u8 *bits;
17 size_t max_bits;
18 };
19
20
bitfield_alloc(size_t max_bits)21 struct bitfield * bitfield_alloc(size_t max_bits)
22 {
23 struct bitfield *bf;
24
25 bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8);
26 if (bf == NULL)
27 return NULL;
28 bf->bits = (u8 *) (bf + 1);
29 bf->max_bits = max_bits;
30 return bf;
31 }
32
33
bitfield_alloc_data(const u8 * data,size_t len)34 struct bitfield * bitfield_alloc_data(const u8 *data, size_t len)
35 {
36 struct bitfield *bf;
37
38 bf = os_zalloc(sizeof(*bf) + len);
39 if (!bf)
40 return NULL;
41
42 bf->bits = (u8 *) (bf + 1);
43 os_memcpy(bf->bits, data, len);
44 bf->max_bits = len * 8;
45
46 return bf;
47 }
48
49
bitfield_dup(const struct bitfield * orig)50 struct bitfield * bitfield_dup(const struct bitfield *orig)
51 {
52 struct bitfield *bf;
53
54 if (!orig)
55 return NULL;
56
57 bf = os_memdup(orig, sizeof(*orig) + (orig->max_bits + 7) / 8);
58 if (!bf)
59 return NULL;
60
61 bf->bits = (u8 *) (bf + 1);
62
63 return bf;
64 }
65
66
bitfield_free(struct bitfield * bf)67 void bitfield_free(struct bitfield *bf)
68 {
69 os_free(bf);
70 }
71
72
bitfield_set(struct bitfield * bf,size_t bit)73 void bitfield_set(struct bitfield *bf, size_t bit)
74 {
75 if (bit >= bf->max_bits)
76 return;
77 bf->bits[bit / 8] |= BIT(bit % 8);
78 }
79
80
bitfield_clear(struct bitfield * bf,size_t bit)81 void bitfield_clear(struct bitfield *bf, size_t bit)
82 {
83 if (bit >= bf->max_bits)
84 return;
85 bf->bits[bit / 8] &= ~BIT(bit % 8);
86 }
87
88
bitfield_is_set(const struct bitfield * bf,size_t bit)89 int bitfield_is_set(const struct bitfield *bf, size_t bit)
90 {
91 if (bit >= bf->max_bits)
92 return 0;
93 return !!(bf->bits[bit / 8] & BIT(bit % 8));
94 }
95
96
first_zero(u8 val)97 static int first_zero(u8 val)
98 {
99 int i;
100 for (i = 0; i < 8; i++) {
101 if (!(val & 0x01))
102 return i;
103 val >>= 1;
104 }
105 return -1;
106 }
107
108
bitfield_get_first_zero(struct bitfield * bf)109 int bitfield_get_first_zero(struct bitfield *bf)
110 {
111 size_t i;
112 for (i = 0; i < (bf->max_bits + 7) / 8; i++) {
113 if (bf->bits[i] != 0xff)
114 break;
115 }
116 if (i == (bf->max_bits + 7) / 8)
117 return -1;
118 i = i * 8 + first_zero(bf->bits[i]);
119 if (i >= bf->max_bits)
120 return -1;
121 return i;
122 }
123
124
bitfield_union_in_place(struct bitfield * a,const struct bitfield * b)125 int bitfield_union_in_place(struct bitfield *a, const struct bitfield *b)
126 {
127 size_t i, upper;
128
129 if (!a || !b || a->max_bits < b->max_bits)
130 return -1;
131
132 upper = (b->max_bits + 7) / 8;
133
134 for (i = 0 ; i < upper; i++)
135 a->bits[i] |= b->bits[i];
136
137 return 0;
138 }
139
140
bitfield_union(const struct bitfield * a,const struct bitfield * b)141 struct bitfield * bitfield_union(const struct bitfield *a,
142 const struct bitfield *b)
143 {
144 struct bitfield *res;
145 int ret;
146
147 if (!a || !b)
148 return NULL;
149
150 if (a->max_bits > b->max_bits) {
151 res = bitfield_dup(a);
152 ret = bitfield_union_in_place(res, b);
153 } else {
154 res = bitfield_dup(b);
155 ret = bitfield_union_in_place(res, a);
156 }
157
158 if (!ret)
159 return res;
160
161 os_free(res);
162 return NULL;
163 }
164
165
bitfield_intersect_in_place(struct bitfield * a,const struct bitfield * b)166 int bitfield_intersect_in_place(struct bitfield *a,
167 const struct bitfield *b)
168 {
169 size_t i, upper;
170
171 if (!a || !b)
172 return -1;
173
174 if (a->max_bits < b->max_bits)
175 upper = (a->max_bits + 7) / 8;
176 else
177 upper = (b->max_bits + 7) / 8;
178
179
180 for (i = 0 ; i < upper; i++)
181 a->bits[i] &= b->bits[i];
182
183 upper = (a->max_bits + 7) / 8;
184 for (; i < upper; i++)
185 a->bits[i] = 0;
186
187 return 0;
188 }
189
190
bitfield_is_subset(const struct bitfield * a,const struct bitfield * b)191 int bitfield_is_subset(const struct bitfield *a, const struct bitfield *b)
192 {
193 size_t i, upper;
194
195 if (!a || !b)
196 return -1;
197
198 if (a->max_bits < b->max_bits)
199 return 0;
200
201 upper = (b->max_bits + 7) / 8;
202
203 for (i = 0; i < upper; i++) {
204 u8 res = a->bits[i] & b->bits[i];
205
206 if (res != b->bits[i])
207 return 0;
208 }
209
210 return 1;
211 }
212
213
bitfield_size(const struct bitfield * bf)214 size_t bitfield_size(const struct bitfield *bf)
215 {
216 if (!bf)
217 return 0;
218 return bf->max_bits;
219 }
220
221
bitfield_intersects(const struct bitfield * a,const struct bitfield * b)222 int bitfield_intersects(const struct bitfield *a, const struct bitfield *b)
223 {
224 size_t i, upper;
225
226 if (!a || !b)
227 return -1;
228
229 if (a->max_bits < b->max_bits)
230 upper = (a->max_bits + 7) / 8;
231 else
232 upper = (b->max_bits + 7) / 8;
233
234 for (i = 0; i < upper; i++)
235 if (a->bits[i] & b->bits[i])
236 return 1;
237
238 return 0;
239 }
240
241
bitfield_dump(struct bitfield * bf,const char * title)242 void bitfield_dump(struct bitfield *bf, const char *title)
243 {
244 wpa_printf(MSG_DEBUG, "bitfield: %s: max_bits=%zu",
245 title, bf->max_bits);
246 wpa_hexdump(MSG_DEBUG, "bits: ", bf->bits, bf->max_bits / 8);
247 }
248