/* * bits.h - bits manipulation helper functions * * Author Ghassan Almaless (2008,2009,2010,2011,2012) * Alain Greiner (2016) * * Copyright (c) UPMC Sorbonne Universites * * This file is part of ALMOS-MKH. * * ALMOS-MKH is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2.0 of the License. * * ALMOS-MKH is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with ALMOS-MKH; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef _BITS_H_ #define _BITS_H_ #include #include /********************************************************************************************* * These macros are NOT used by the bitmap, but can be useful in other contexts... [AG] *********************************************************************************************/ #define ARROUND_UP(val, size) (((val) & ((size) -1)) ? ((val) & ~((size)-1)) + (size) : (val)) #define ARROUND_DOWN(val, size) ((val) & ~((size) - 1)) #define ABS(x) (((x) < 0) ? -(x) : (x)) #define MIN(x,y) (((x) < (y)) ? (x) : (y)) #define MAX(x,y) (((x) < (y)) ? (y) : (x)) /********************************************************************************************** * This macro returns the smallest power of 2 value, that is larger or equal to data value. * It returns 0xFFFFFFFF if data is larger than 0x80000000. *********************************************************************************************/ #define POW2_ROUNDUP(data) ( (data <= 0x00000001) ? 0x00000001 : \ (data <= 0x00000002) ? 0x00000002 : \ (data <= 0x00000004) ? 0x00000004 : \ (data <= 0x00000008) ? 0x00000008 : \ (data <= 0x00000010) ? 0x00000010 : \ (data <= 0x00000020) ? 0x00000020 : \ (data <= 0x00000040) ? 0x00000040 : \ (data <= 0x00000080) ? 0x00000080 : \ (data <= 0x00000100) ? 0x00000100 : \ (data <= 0x00000200) ? 0x00000200 : \ (data <= 0x00000400) ? 0x00000400 : \ (data <= 0x00000800) ? 0x00000800 : \ (data <= 0x00001000) ? 0x00001000 : \ (data <= 0x00002000) ? 0x00002000 : \ (data <= 0x00004000) ? 0x00004000 : \ (data <= 0x00008000) ? 0x00008000 : \ (data <= 0x00010000) ? 0x00010000 : \ (data <= 0x00020000) ? 0x00020000 : \ (data <= 0x00040000) ? 0x00040000 : \ (data <= 0x00080000) ? 0x00080000 : \ (data <= 0x00100000) ? 0x00100000 : \ (data <= 0x00200000) ? 0x00200000 : \ (data <= 0x00400000) ? 0x00400000 : \ (data <= 0x00800000) ? 0x00800000 : \ (data <= 0x01000000) ? 0x01000000 : \ (data <= 0x02000000) ? 0x02000000 : \ (data <= 0x04000000) ? 0x04000000 : \ (data <= 0x08000000) ? 0x08000000 : \ (data <= 0x10000000) ? 0x10000000 : \ (data <= 0x20000000) ? 0x20000000 : \ (data <= 0x40000000) ? 0x40000000 : \ (data <= 0x80000000) ? 0x80000000 : 0xFFFFFFFF ) /********************************************************************************************** * This macro returns the number of 32 bits words required to register entries. *********************************************************************************************/ #define BITMAP_SIZE(size) ( ((size) & 31) ? (((size)>>5) + 1) : ((size)>>5) ) typedef uint32_t bitmap_t; /********************************************************************************************* * This function reset all bits in a bitmap. (array ot 32 bits words). ********************************************************************************************* * @ bitmap : pointer on first word in the bitmap. * @ len : number of bits to reset. ********************************************************************************************/ void bitmap_init( bitmap_t * bitmap, uint32_t len ); /********************************************************************************************* * This function set a specific bit in a bitmap. ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ index : bit index in the bitmap ********************************************************************************************/ extern inline void bitmap_set( bitmap_t * bitmap, uint32_t index ); /********************************************************************************************* * This function clear a specific bit in a bitmap. ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ index : bit index in the bitmap ********************************************************************************************/ extern inline void bitmap_clear( bitmap_t * bitmap, uint32_t index ); /********************************************************************************************* * This function returns a specific bit in a bitmap. ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ index : bit index in the bitmap * @ returns true if bitmap[index] is set ********************************************************************************************/ extern inline bool_t bitmap_state( bitmap_t * bitmap, uint32_t index ); /********************************************************************************************* * This function set a range of bits in a bitmap : [index ... (index + len)[ ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ index : first bit index in the bitmap * @ len : number of bits to set ********************************************************************************************/ extern void bitmap_set_range( bitmap_t * bitmap, uint32_t index, uint32_t len ); /********************************************************************************************* * This function reset a range of bits in a bitmap : [index ... (index + len)[ ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ index : first bit index in the bitmap * @ len : number of bits to clear ********************************************************************************************/ extern void bitmap_clear_range( bitmap_t * bitmap, uint32_t index, uint32_t len ); /********************************************************************************************* * This function returns the index of first bit set in a bitmap, starting from index. ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ index : first bit to analyse in the bitmap * @ size : number of bits to analyse in bitmap * @ returns index if found / returns 0xFFFFFFFF if bit not found ********************************************************************************************/ extern uint32_t bitmap_ffs2( bitmap_t * bitmap, uint32_t index, uint32_t size ); /********************************************************************************************* * This function returns the index of first bit cleared in a bitmap, starting from index. ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ index : first bit to analyse in the bitmap * @ size : number of bits to analyse in bitmap * @ returns index if found / returns 0xFFFFFFFF if bit not found ********************************************************************************************/ extern uint32_t bitmap_ffc2( bitmap_t * bitmap, uint32_t index, uint32_t size ); /********************************************************************************************* * This function returns the index of first bit set in a bitmap, starting from bit 0. ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ size : number of bits to analyse in bitmap * @ returns index if found / returns 0xFFFFFFFF if bit not found ********************************************************************************************/ extern uint32_t bitmap_ffs( bitmap_t * bitmap, uint32_t size ); /********************************************************************************************* * This function returns the index of first bit cleared in a bitmap, starting from bit 0. ********************************************************************************************* * @ bitmap : pointer on the bitmap * @ size : number of bits to analyse in bitmap * @ returns index if found / returns 0xFFFFFFFF if bit not found ********************************************************************************************/ extern uint32_t bitmap_ffc( bitmap_t * bitmap, uint32_t size ); /********************************************************************************************* * This function returns the number of bits to code a non-zero unsigned integer value. ********************************************************************************************* * @ val : value to analyse * @ returns number of bits ********************************************************************************************/ static inline uint32_t bits_nr( uint32_t val ) { register uint32_t i; for( i=0 ; val > 0 ; i++ ) val = val >> 1; return i; } /********************************************************************************************* * This function takes an unsigned integer value as input argument, and returns another * unsigned integer, that is the (base 2) logarithm of the smallest power of 2 contained * in the input value. ********************************************************************************************* * @ val : value to analyse * @ returns logarithm value ********************************************************************************************/ static inline uint32_t bits_log2( uint32_t val ) { return (val == 0) ? 1 : bits_nr( val ) - 1; } #endif /* _BITS_H_ */