1281681Srpaulo/* 2281681Srpaulo * Bitfield 3281681Srpaulo * Copyright (c) 2013, Jouni Malinen <j@w1.fi> 4281681Srpaulo * 5281681Srpaulo * This software may be distributed under the terms of the BSD license. 6281681Srpaulo * See README for more details. 7281681Srpaulo */ 8281681Srpaulo 9281681Srpaulo#include "includes.h" 10281681Srpaulo 11281681Srpaulo#include "common.h" 12281681Srpaulo#include "bitfield.h" 13281681Srpaulo 14281681Srpaulo 15281681Srpaulostruct bitfield { 16281681Srpaulo u8 *bits; 17281681Srpaulo size_t max_bits; 18281681Srpaulo}; 19281681Srpaulo 20281681Srpaulo 21281681Srpaulostruct bitfield * bitfield_alloc(size_t max_bits) 22281681Srpaulo{ 23281681Srpaulo struct bitfield *bf; 24281681Srpaulo 25281681Srpaulo bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8); 26281681Srpaulo if (bf == NULL) 27281681Srpaulo return NULL; 28281681Srpaulo bf->bits = (u8 *) (bf + 1); 29281681Srpaulo bf->max_bits = max_bits; 30281681Srpaulo return bf; 31281681Srpaulo} 32281681Srpaulo 33281681Srpaulo 34281681Srpaulovoid bitfield_free(struct bitfield *bf) 35281681Srpaulo{ 36281681Srpaulo os_free(bf); 37281681Srpaulo} 38281681Srpaulo 39281681Srpaulo 40281681Srpaulovoid bitfield_set(struct bitfield *bf, size_t bit) 41281681Srpaulo{ 42281681Srpaulo if (bit >= bf->max_bits) 43281681Srpaulo return; 44281681Srpaulo bf->bits[bit / 8] |= BIT(bit % 8); 45281681Srpaulo} 46281681Srpaulo 47281681Srpaulo 48281681Srpaulovoid bitfield_clear(struct bitfield *bf, size_t bit) 49281681Srpaulo{ 50281681Srpaulo if (bit >= bf->max_bits) 51281681Srpaulo return; 52281681Srpaulo bf->bits[bit / 8] &= ~BIT(bit % 8); 53281681Srpaulo} 54281681Srpaulo 55281681Srpaulo 56281681Srpauloint bitfield_is_set(struct bitfield *bf, size_t bit) 57281681Srpaulo{ 58281681Srpaulo if (bit >= bf->max_bits) 59281681Srpaulo return 0; 60281681Srpaulo return !!(bf->bits[bit / 8] & BIT(bit % 8)); 61281681Srpaulo} 62281681Srpaulo 63281681Srpaulo 64281681Srpaulostatic int first_zero(u8 val) 65281681Srpaulo{ 66281681Srpaulo int i; 67281681Srpaulo for (i = 0; i < 8; i++) { 68281681Srpaulo if (!(val & 0x01)) 69281681Srpaulo return i; 70281681Srpaulo val >>= 1; 71281681Srpaulo } 72281681Srpaulo return -1; 73281681Srpaulo} 74281681Srpaulo 75281681Srpaulo 76281681Srpauloint bitfield_get_first_zero(struct bitfield *bf) 77281681Srpaulo{ 78281681Srpaulo size_t i; 79281681Srpaulo for (i = 0; i < (bf->max_bits + 7) / 8; i++) { 80281681Srpaulo if (bf->bits[i] != 0xff) 81281681Srpaulo break; 82281681Srpaulo } 83281681Srpaulo if (i == (bf->max_bits + 7) / 8) 84281681Srpaulo return -1; 85281681Srpaulo i = i * 8 + first_zero(bf->bits[i]); 86281681Srpaulo if (i >= bf->max_bits) 87281681Srpaulo return -1; 88281681Srpaulo return i; 89281681Srpaulo} 90