1 /* 2 * Copyright (c) 2018, Sam Kumar <samkumar@cs.berkeley.edu> 3 * Copyright (c) 2018, University of California, Berkeley 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of the copyright holder nor the 14 * names of its contributors may be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 * POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #ifndef BITMAP_H_ 31 #define BITMAP_H_ 32 33 #include <stdint.h> 34 #include <stdlib.h> 35 36 /* Computes the number of bytes required to store the specified number of bits. */ 37 #define BITS_TO_BYTES(bits) (((bits) >> 3) + (((bits) & 0x7) ? 1 : 0)) 38 39 /* Initializes a bitmap to all zeros. */ 40 void bmp_init(uint8_t* buf, size_t numbytes); 41 42 /* Sets the specified range of bits. START is the index 43 of the first bit to be set. LEN is the number of bits 44 to be set. */ 45 void bmp_setrange(uint8_t* buf, size_t start, size_t len); 46 47 /* Clears the specified range of bits. START is the index 48 of the first bit to be cleared. LEN is the number of bits 49 to be cleared. */ 50 void bmp_clrrange(uint8_t* buf, size_t start, size_t len); 51 52 /* Counts the number of set bits in BUF starting at START. BUF has length 53 BUFLEN, in bytes. Counts the number of set bits until it either (1) finds 54 a bit that isn't set, in which case it returns the number of set bits, 55 (2) it has counted at least LIMIT bits, in which case it returns a number 56 greater than or equal to LIMIT, or (3) reaches the end of the buffer, in 57 which case it returns exactly the number of set bits it found. */ 58 size_t bmp_countset(uint8_t* buf, size_t buflen, size_t start, size_t limit); 59 60 /* Swaps two non-overlapping regions of the bitmap. START_1 is the index of 61 the first region, START_2 is the index of the secoind region, and LEN is 62 the length of each region, in bits. */ 63 void bmp_swap(uint8_t* buf, size_t start_1, size_t start_2, size_t len); 64 65 /* Returns 1 if the bitmap is all zeros, and 0 otherwise. */ 66 int bmp_isempty(uint8_t* buf, size_t buflen); 67 68 /* Prints out the bitmap in hexadecimal (used for debugging). */ 69 void bmp_print(uint8_t* buf, size_t buflen); 70 71 #endif 72
