14b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt/* 24b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt * Bitfield 34b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt * Copyright (c) 2013, Jouni Malinen <j@w1.fi> 44b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt * 54b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt * This software may be distributed under the terms of the BSD license. 64b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt * See README for more details. 74b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt */ 84b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 94b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt#include "includes.h" 104b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 114b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt#include "common.h" 124b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt#include "bitfield.h" 134b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 144b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 154b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtstruct bitfield { 164b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt u8 *bits; 174b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt size_t max_bits; 184b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt}; 194b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 204b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 214b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtstruct bitfield * bitfield_alloc(size_t max_bits) 224b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt{ 234b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt struct bitfield *bf; 244b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 254b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8); 264b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (bf == NULL) 274b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return NULL; 284b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt bf->bits = (u8 *) (bf + 1); 294b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt bf->max_bits = max_bits; 304b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return bf; 314b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt} 324b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 334b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 344b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtvoid bitfield_free(struct bitfield *bf) 354b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt{ 364b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt os_free(bf); 374b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt} 384b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 394b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 404b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtvoid bitfield_set(struct bitfield *bf, size_t bit) 414b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt{ 424b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (bit >= bf->max_bits) 434b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return; 444b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt bf->bits[bit / 8] |= BIT(bit % 8); 454b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt} 464b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 474b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 484b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtvoid bitfield_clear(struct bitfield *bf, size_t bit) 494b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt{ 504b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (bit >= bf->max_bits) 514b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return; 524b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt bf->bits[bit / 8] &= ~BIT(bit % 8); 534b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt} 544b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 554b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 564b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtint bitfield_is_set(struct bitfield *bf, size_t bit) 574b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt{ 584b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (bit >= bf->max_bits) 594b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return 0; 604b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return !!(bf->bits[bit / 8] & BIT(bit % 8)); 614b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt} 624b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 634b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 644b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtstatic int first_zero(u8 val) 654b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt{ 664b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt int i; 674b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt for (i = 0; i < 8; i++) { 684b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (!(val & 0x01)) 694b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return i; 704b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt val >>= 1; 714b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt } 724b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return -1; 734b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt} 744b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 754b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt 764b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidtint bitfield_get_first_zero(struct bitfield *bf) 774b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt{ 784b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt size_t i; 794b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt for (i = 0; i <= (bf->max_bits + 7) / 8; i++) { 804b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (bf->bits[i] != 0xff) 814b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt break; 824b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt } 834b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (i > (bf->max_bits + 7) / 8) 844b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return -1; 854b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt i = i * 8 + first_zero(bf->bits[i]); 864b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt if (i >= bf->max_bits) 874b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return -1; 884b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt return i; 894b06059785b935dd1f4f09314e4e12c417d2c6a4Dmitry Shmidt} 90