1*5b9c547cSRui Paulo /* 2*5b9c547cSRui Paulo * Bitfield 3*5b9c547cSRui Paulo * Copyright (c) 2013, Jouni Malinen <j@w1.fi> 4*5b9c547cSRui Paulo * 5*5b9c547cSRui Paulo * This software may be distributed under the terms of the BSD license. 6*5b9c547cSRui Paulo * See README for more details. 7*5b9c547cSRui Paulo */ 8*5b9c547cSRui Paulo 9*5b9c547cSRui Paulo #include "includes.h" 10*5b9c547cSRui Paulo 11*5b9c547cSRui Paulo #include "common.h" 12*5b9c547cSRui Paulo #include "bitfield.h" 13*5b9c547cSRui Paulo 14*5b9c547cSRui Paulo 15*5b9c547cSRui Paulo struct bitfield { 16*5b9c547cSRui Paulo u8 *bits; 17*5b9c547cSRui Paulo size_t max_bits; 18*5b9c547cSRui Paulo }; 19*5b9c547cSRui Paulo 20*5b9c547cSRui Paulo bitfield_alloc(size_t max_bits)21*5b9c547cSRui Paulostruct bitfield * bitfield_alloc(size_t max_bits) 22*5b9c547cSRui Paulo { 23*5b9c547cSRui Paulo struct bitfield *bf; 24*5b9c547cSRui Paulo 25*5b9c547cSRui Paulo bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8); 26*5b9c547cSRui Paulo if (bf == NULL) 27*5b9c547cSRui Paulo return NULL; 28*5b9c547cSRui Paulo bf->bits = (u8 *) (bf + 1); 29*5b9c547cSRui Paulo bf->max_bits = max_bits; 30*5b9c547cSRui Paulo return bf; 31*5b9c547cSRui Paulo } 32*5b9c547cSRui Paulo 33*5b9c547cSRui Paulo bitfield_free(struct bitfield * bf)34*5b9c547cSRui Paulovoid bitfield_free(struct bitfield *bf) 35*5b9c547cSRui Paulo { 36*5b9c547cSRui Paulo os_free(bf); 37*5b9c547cSRui Paulo } 38*5b9c547cSRui Paulo 39*5b9c547cSRui Paulo bitfield_set(struct bitfield * bf,size_t bit)40*5b9c547cSRui Paulovoid bitfield_set(struct bitfield *bf, size_t bit) 41*5b9c547cSRui Paulo { 42*5b9c547cSRui Paulo if (bit >= bf->max_bits) 43*5b9c547cSRui Paulo return; 44*5b9c547cSRui Paulo bf->bits[bit / 8] |= BIT(bit % 8); 45*5b9c547cSRui Paulo } 46*5b9c547cSRui Paulo 47*5b9c547cSRui Paulo bitfield_clear(struct bitfield * bf,size_t bit)48*5b9c547cSRui Paulovoid bitfield_clear(struct bitfield *bf, size_t bit) 49*5b9c547cSRui Paulo { 50*5b9c547cSRui Paulo if (bit >= bf->max_bits) 51*5b9c547cSRui Paulo return; 52*5b9c547cSRui Paulo bf->bits[bit / 8] &= ~BIT(bit % 8); 53*5b9c547cSRui Paulo } 54*5b9c547cSRui Paulo 55*5b9c547cSRui Paulo bitfield_is_set(struct bitfield * bf,size_t bit)56*5b9c547cSRui Pauloint bitfield_is_set(struct bitfield *bf, size_t bit) 57*5b9c547cSRui Paulo { 58*5b9c547cSRui Paulo if (bit >= bf->max_bits) 59*5b9c547cSRui Paulo return 0; 60*5b9c547cSRui Paulo return !!(bf->bits[bit / 8] & BIT(bit % 8)); 61*5b9c547cSRui Paulo } 62*5b9c547cSRui Paulo 63*5b9c547cSRui Paulo first_zero(u8 val)64*5b9c547cSRui Paulostatic int first_zero(u8 val) 65*5b9c547cSRui Paulo { 66*5b9c547cSRui Paulo int i; 67*5b9c547cSRui Paulo for (i = 0; i < 8; i++) { 68*5b9c547cSRui Paulo if (!(val & 0x01)) 69*5b9c547cSRui Paulo return i; 70*5b9c547cSRui Paulo val >>= 1; 71*5b9c547cSRui Paulo } 72*5b9c547cSRui Paulo return -1; 73*5b9c547cSRui Paulo } 74*5b9c547cSRui Paulo 75*5b9c547cSRui Paulo bitfield_get_first_zero(struct bitfield * bf)76*5b9c547cSRui Pauloint bitfield_get_first_zero(struct bitfield *bf) 77*5b9c547cSRui Paulo { 78*5b9c547cSRui Paulo size_t i; 79*5b9c547cSRui Paulo for (i = 0; i < (bf->max_bits + 7) / 8; i++) { 80*5b9c547cSRui Paulo if (bf->bits[i] != 0xff) 81*5b9c547cSRui Paulo break; 82*5b9c547cSRui Paulo } 83*5b9c547cSRui Paulo if (i == (bf->max_bits + 7) / 8) 84*5b9c547cSRui Paulo return -1; 85*5b9c547cSRui Paulo i = i * 8 + first_zero(bf->bits[i]); 86*5b9c547cSRui Paulo if (i >= bf->max_bits) 87*5b9c547cSRui Paulo return -1; 88*5b9c547cSRui Paulo return i; 89*5b9c547cSRui Paulo } 90