/* ** Copyright (C) 2005-2006 by Carnegie Mellon University. ** ** @OPENSOURCE_HEADER_START@ ** ** Use of the SILK system and related source code is subject to the terms ** of the following licenses: ** ** GNU Public License (GPL) Rights pursuant to Version 2, June 1991 ** Government Purpose License Rights (GPLR) pursuant to DFARS 252.225-7013 ** ** NO WARRANTY ** ** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER ** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY ** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN ** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY ** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT ** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE, ** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE ** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT, ** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY ** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF ** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES. ** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF ** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON ** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE ** DELIVERABLES UNDER THIS LICENSE. ** ** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie ** Mellon University, its trustees, officers, employees, and agents from ** all claims or demands made against them (and any related losses, ** expenses, or attorney's fees) arising out of, or relating to Licensee's ** and/or its sub licensees' negligent use or willful misuse of or ** negligent conduct or willful misconduct regarding the Software, ** facilities, or other rights or assistance granted by Carnegie Mellon ** University under this License, including, but not limited to, any ** claims of product liability, personal injury, death, damage to ** property, or violation of any laws or regulations. ** ** Carnegie Mellon University Software Engineering Institute authored ** documents are sponsored by the U.S. Department of Defense under ** Contract F19628-00-C-0003. Carnegie Mellon University retains ** copyrights in all material produced under this contract. The U.S. ** Government retains a non-exclusive, royalty-free license to publish or ** reproduce these documents, or allow others to do so, for U.S. ** Government purposes only pursuant to the copyright license under the ** contract clause at 252.227.7013. ** ** @OPENSOURCE_HEADER_END@ */ /* ** skbitmap.c ** ** Bitmap creatation and deletion. ** */ #include "silk.h" RCSIDENT("$SiLK: skbitmap.c 3409 2006-04-11 23:06:27Z mthomas $"); #include "utils.h" /* LOCAL DEFINES AND TYPEDEFS */ /* Return number of 32bit words needed to hold a bitmap with * 'num_bits' elements */ #define BITMAP_GET_WORD_COUNT(num_bits) \ (((num_bits) >> 5) + ((((num_bits) & 0x1F)==0) ? 0 : 1)) /* FUNCTION DEFINITIONS */ int skBitmapCreate(sk_bitmap_t **bitmap_out, uint32_t num_bits) { uint32_t word_count = BITMAP_GET_WORD_COUNT(num_bits); assert(bitmap_out); if (num_bits == 0) { return -1; } *bitmap_out = calloc(1, sizeof(sk_bitmap_t)); if (*bitmap_out == NULL) { return -1; } (*bitmap_out)->map = calloc(word_count, sizeof(uint32_t)); if (NULL == (*bitmap_out)->map) { free(*bitmap_out); return -1; } (*bitmap_out)->num_bits = num_bits; return 0; } void skBitmapDestroy(sk_bitmap_t **bitmap) { if (!bitmap || !*bitmap) { return; } free((*bitmap)->map); (*bitmap)->map = NULL; free(*bitmap); *bitmap = NULL; } void skBitmapClearAllBits(sk_bitmap_t *bitmap) { uint32_t word_count; assert(bitmap); word_count = BITMAP_GET_WORD_COUNT(bitmap->num_bits); memset(bitmap->map, 0, word_count * sizeof(uint32_t)); bitmap->count = 0; } uint32_t skBitmapGetSizeF(const sk_bitmap_t *bitmap) { assert(bitmap); return bitmap->num_bits; } uint32_t skBitmapGetHighCountF(const sk_bitmap_t *bitmap) { assert(bitmap); return bitmap->count; } int skBitmapGetBitF(const sk_bitmap_t *bitmap, uint32_t pos) { assert(bitmap); assert(pos < bitmap->num_bits); return (_BMAP_IS_SET(bitmap, pos) ? 1 : 0); } void skBitmapSetBitF(sk_bitmap_t *bitmap, uint32_t pos) { assert(bitmap); assert(pos < bitmap->num_bits); if ( !_BMAP_IS_SET(bitmap, pos)) { (bitmap)->map[_BMAP_INDEX(pos)] |= _BMAP_OFFSET(pos); ++(bitmap)->count; } } void skBitmapClearBitF(sk_bitmap_t *bitmap, uint32_t pos) { assert(bitmap); assert(pos < bitmap->num_bits); if (_BMAP_IS_SET(bitmap, pos)) { (bitmap)->map[_BMAP_INDEX(pos)] &= ~_BMAP_OFFSET(pos); --(bitmap)->count; } } /* ************* IP OCTET BITMAPS ******************* */ void skOctetMapClear(skOctetMap_t *octetmap) { assert(octetmap); memset(octetmap->m_octets, 0, sizeof(skOctetMap_t)); } int skOctetMapGetIpF(const skOctetMap_t *octetmap, uint32_t ip) { assert(octetmap); return (_OMAP_IP_IS_SET(octetmap, ip) ? 1 : 0); } /* Initialize iterator */ int skOctetMapIteratorInitialize( skOctetMapIterator_t *out_iter, const skOctetMap_t *octetmap) { assert(out_iter); if (octetmap == NULL) { return -1; } out_iter->omap = octetmap; skOctetMapIteratorReset(out_iter); return 0; } /* Get next entry in tree */ skIteratorStatus_t skOctetMapIteratorNext( uint32_t *out_ip, skOctetMapIterator_t *iter) { assert(out_ip); /* ** If the line was parsed as a dotted quad, CIDR block, etc., then ** unroll the bitmaps into individual IPs and add them. */ for ( ; iter->i_octet[0] < 256; ++iter->i_octet[0]) { if ( !_OMAP_OCT_IS_SET(iter->omap, 0, iter->i_octet[0])) { continue; } for ( ; iter->i_octet[1] < 256; ++iter->i_octet[1]) { if ( !_OMAP_OCT_IS_SET(iter->omap, 1, iter->i_octet[1])) { continue; } for ( ; iter->i_octet[2] < 256; ++iter->i_octet[2]) { if ( !_OMAP_OCT_IS_SET(iter->omap, 2, iter->i_octet[2])) { continue; } for ( ; iter->i_octet[3] < 256; ++iter->i_octet[3]) { if ( !_OMAP_OCT_IS_SET(iter->omap, 3, iter->i_octet[3])) { continue; } *out_ip = ((iter->i_octet[0] << 24) | (iter->i_octet[1] << 16) | (iter->i_octet[2] << 8) | (iter->i_octet[3])); /* prepare to search from next address */ ++iter->i_octet[3]; return SK_ITERATOR_OK; } iter->i_octet[3] = 0; } iter->i_octet[2] = 0; } iter->i_octet[1] = 0; } return SK_ITERATOR_NO_MORE_ENTRIES; } /* Reset iterator */ void skOctetMapIteratorReset(skOctetMapIterator_t *iter) { assert(iter); memset(iter->i_octet, 0, 4 * sizeof(uint16_t)); }