1 /* bit vector utility routines */
3 /* (C) 2009 by Harald Welte <laforge@gnumonks.org>
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 #include <osmocore/bitvec.h>
29 #define BITNUM_FROM_COMP(byte, bit) ((byte*8)+bit)
31 static inline unsigned int bytenum_from_bitnum(unsigned int bitnum)
33 unsigned int bytenum = bitnum / 8;
38 /* convert ZERO/ONE/L/H to a bitmask at given pos in a byte */
39 static uint8_t bitval2mask(enum bit_value bit, uint8_t bitnum)
45 bitval = (0 << bitnum);
48 bitval = (1 << bitnum);
51 bitval = ((0x2b ^ (0 << bitnum)) & (1 << bitnum));
54 bitval = ((0x2b ^ (1 << bitnum)) & (1 << bitnum));
62 /* check if the bit is 0 or 1 for a given position inside a bitvec */
63 enum bit_value bitvec_get_bit_pos(const struct bitvec *bv, unsigned int bitnr)
65 unsigned int bytenum = bytenum_from_bitnum(bitnr);
66 unsigned int bitnum = 7 - (bitnr % 8);
69 if (bytenum >= bv->data_len)
72 bitval = bitval2mask(ONE, bitnum);
74 if (bv->data[bytenum] & bitval)
80 /* check if the bit is L or H for a given position inside a bitvec */
81 enum bit_value bitvec_get_bit_pos_high(const struct bitvec *bv,
84 unsigned int bytenum = bytenum_from_bitnum(bitnr);
85 unsigned int bitnum = 7 - (bitnr % 8);
88 if (bytenum >= bv->data_len)
91 bitval = bitval2mask(H, bitnum);
93 if ((bv->data[bytenum] & (1 << bitnum)) == bitval)
99 /* get the Nth set bit inside the bit vector */
100 unsigned int bitvec_get_nth_set_bit(const struct bitvec *bv, unsigned int n)
102 unsigned int i, k = 0;
104 for (i = 0; i < bv->data_len*8; i++) {
105 if (bitvec_get_bit_pos(bv, i) == ONE) {
115 /* set the bit at a given position inside a bitvec */
116 int bitvec_set_bit_pos(struct bitvec *bv, unsigned int bitnr,
119 unsigned int bytenum = bytenum_from_bitnum(bitnr);
120 unsigned int bitnum = 7 - (bitnr % 8);
123 if (bytenum >= bv->data_len)
126 /* first clear the bit */
127 bitval = bitval2mask(ONE, bitnum);
128 bv->data[bytenum] &= ~bitval;
130 /* then set it to desired value */
131 bitval = bitval2mask(bit, bitnum);
132 bv->data[bytenum] |= bitval;
137 /* set the next bit inside a bitvec */
138 int bitvec_set_bit(struct bitvec *bv, enum bit_value bit)
142 rc = bitvec_set_bit_pos(bv, bv->cur_bit, bit);
149 /* get the next bit (low/high) inside a bitvec */
150 int bitvec_get_bit_high(struct bitvec *bv)
154 rc = bitvec_get_bit_pos_high(bv, bv->cur_bit);
161 /* set multiple bits (based on array of bitvals) at current pos */
162 int bitvec_set_bits(struct bitvec *bv, enum bit_value *bits, int count)
166 for (i = 0; i < count; i++) {
167 rc = bitvec_set_bit(bv, bits[i]);
175 /* set multiple bits (based on numeric value) at current pos */
176 int bitvec_set_uint(struct bitvec *bv, unsigned int ui, int num_bits)
180 for (i = 0; i < num_bits; i++) {
182 if (ui & (1 << (num_bits - i - 1)))
184 rc = bitvec_set_bit(bv, bit);
192 /* get multiple bits (based on numeric value) from current pos */
193 int bitvec_get_uint(struct bitvec *bv, int num_bits)
198 for (i = 0; i < num_bits; i++) {
199 int bit = bitvec_get_bit_pos(bv, bv->cur_bit);
203 ui |= (1 << (num_bits - i - 1));
210 /* pad all remaining bits up to num_bits */
211 int bitvec_spare_padding(struct bitvec *bv, unsigned int up_to_bit)
215 for (i = bv->cur_bit; i <= up_to_bit; i++)
216 bitvec_set_bit(bv, L);