13ff40c12SJohn Marino /* 23ff40c12SJohn Marino * Bitfield 33ff40c12SJohn Marino * Copyright (c) 2013, Jouni Malinen <j@w1.fi> 43ff40c12SJohn Marino * 53ff40c12SJohn Marino * This software may be distributed under the terms of the BSD license. 63ff40c12SJohn Marino * See README for more details. 73ff40c12SJohn Marino */ 83ff40c12SJohn Marino 93ff40c12SJohn Marino #include "includes.h" 103ff40c12SJohn Marino 113ff40c12SJohn Marino #include "common.h" 123ff40c12SJohn Marino #include "bitfield.h" 133ff40c12SJohn Marino 143ff40c12SJohn Marino 153ff40c12SJohn Marino struct bitfield { 163ff40c12SJohn Marino u8 *bits; 173ff40c12SJohn Marino size_t max_bits; 183ff40c12SJohn Marino }; 193ff40c12SJohn Marino 203ff40c12SJohn Marino bitfield_alloc(size_t max_bits)213ff40c12SJohn Marinostruct bitfield * bitfield_alloc(size_t max_bits) 223ff40c12SJohn Marino { 233ff40c12SJohn Marino struct bitfield *bf; 243ff40c12SJohn Marino 253ff40c12SJohn Marino bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8); 263ff40c12SJohn Marino if (bf == NULL) 273ff40c12SJohn Marino return NULL; 283ff40c12SJohn Marino bf->bits = (u8 *) (bf + 1); 293ff40c12SJohn Marino bf->max_bits = max_bits; 303ff40c12SJohn Marino return bf; 313ff40c12SJohn Marino } 323ff40c12SJohn Marino 333ff40c12SJohn Marino bitfield_free(struct bitfield * bf)343ff40c12SJohn Marinovoid bitfield_free(struct bitfield *bf) 353ff40c12SJohn Marino { 363ff40c12SJohn Marino os_free(bf); 373ff40c12SJohn Marino } 383ff40c12SJohn Marino 393ff40c12SJohn Marino bitfield_set(struct bitfield * bf,size_t bit)403ff40c12SJohn Marinovoid bitfield_set(struct bitfield *bf, size_t bit) 413ff40c12SJohn Marino { 423ff40c12SJohn Marino if (bit >= bf->max_bits) 433ff40c12SJohn Marino return; 443ff40c12SJohn Marino bf->bits[bit / 8] |= BIT(bit % 8); 453ff40c12SJohn Marino } 463ff40c12SJohn Marino 473ff40c12SJohn Marino bitfield_clear(struct bitfield * bf,size_t bit)483ff40c12SJohn Marinovoid bitfield_clear(struct bitfield *bf, size_t bit) 493ff40c12SJohn Marino { 503ff40c12SJohn Marino if (bit >= bf->max_bits) 513ff40c12SJohn Marino return; 523ff40c12SJohn Marino bf->bits[bit / 8] &= ~BIT(bit % 8); 533ff40c12SJohn Marino } 543ff40c12SJohn Marino 553ff40c12SJohn Marino bitfield_is_set(struct bitfield * bf,size_t bit)563ff40c12SJohn Marinoint bitfield_is_set(struct bitfield *bf, size_t bit) 573ff40c12SJohn Marino { 583ff40c12SJohn Marino if (bit >= bf->max_bits) 593ff40c12SJohn Marino return 0; 603ff40c12SJohn Marino return !!(bf->bits[bit / 8] & BIT(bit % 8)); 613ff40c12SJohn Marino } 623ff40c12SJohn Marino 633ff40c12SJohn Marino first_zero(u8 val)643ff40c12SJohn Marinostatic int first_zero(u8 val) 653ff40c12SJohn Marino { 663ff40c12SJohn Marino int i; 673ff40c12SJohn Marino for (i = 0; i < 8; i++) { 683ff40c12SJohn Marino if (!(val & 0x01)) 693ff40c12SJohn Marino return i; 703ff40c12SJohn Marino val >>= 1; 713ff40c12SJohn Marino } 723ff40c12SJohn Marino return -1; 733ff40c12SJohn Marino } 743ff40c12SJohn Marino 753ff40c12SJohn Marino bitfield_get_first_zero(struct bitfield * bf)763ff40c12SJohn Marinoint bitfield_get_first_zero(struct bitfield *bf) 773ff40c12SJohn Marino { 783ff40c12SJohn Marino size_t i; 79*a1157835SDaniel Fojt for (i = 0; i < (bf->max_bits + 7) / 8; i++) { 803ff40c12SJohn Marino if (bf->bits[i] != 0xff) 813ff40c12SJohn Marino break; 823ff40c12SJohn Marino } 83*a1157835SDaniel Fojt if (i == (bf->max_bits + 7) / 8) 843ff40c12SJohn Marino return -1; 853ff40c12SJohn Marino i = i * 8 + first_zero(bf->bits[i]); 863ff40c12SJohn Marino if (i >= bf->max_bits) 873ff40c12SJohn Marino return -1; 883ff40c12SJohn Marino return i; 893ff40c12SJohn Marino } 90