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_free(struct bitfield * bf)34 void bitfield_free(struct bitfield *bf)
35 {
36 	os_free(bf);
37 }
38 
39 
bitfield_set(struct bitfield * bf,size_t bit)40 void bitfield_set(struct bitfield *bf, size_t bit)
41 {
42 	if (bit >= bf->max_bits)
43 		return;
44 	bf->bits[bit / 8] |= BIT(bit % 8);
45 }
46 
47 
bitfield_clear(struct bitfield * bf,size_t bit)48 void bitfield_clear(struct bitfield *bf, size_t bit)
49 {
50 	if (bit >= bf->max_bits)
51 		return;
52 	bf->bits[bit / 8] &= ~BIT(bit % 8);
53 }
54 
55 
bitfield_is_set(struct bitfield * bf,size_t bit)56 int bitfield_is_set(struct bitfield *bf, size_t bit)
57 {
58 	if (bit >= bf->max_bits)
59 		return 0;
60 	return !!(bf->bits[bit / 8] & BIT(bit % 8));
61 }
62 
63 
first_zero(u8 val)64 static int first_zero(u8 val)
65 {
66 	int i;
67 	for (i = 0; i < 8; i++) {
68 		if (!(val & 0x01))
69 			return i;
70 		val >>= 1;
71 	}
72 	return -1;
73 }
74 
75 
bitfield_get_first_zero(struct bitfield * bf)76 int bitfield_get_first_zero(struct bitfield *bf)
77 {
78 	size_t i;
79 	for (i = 0; i < (bf->max_bits + 7) / 8; i++) {
80 		if (bf->bits[i] != 0xff)
81 			break;
82 	}
83 	if (i == (bf->max_bits + 7) / 8)
84 		return -1;
85 	i = i * 8 + first_zero(bf->bits[i]);
86 	if (i >= bf->max_bits)
87 		return -1;
88 	return i;
89 }
90