/*
 * bits.h - bitmap API definition
 *
 * Author   Ghassan Almaless (2008,2009,2010,2011,2012)
 *          Alain Greiner    (2016,2017,2018,2019,2020)
 *
 * 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 <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_remote.h>

/**********************************************************************************************
 * This file defines the API to access a generic bitmap, that can be local or remote.
 * It is implemented as an array of uint32_t words.
 * The number of entries in this array is statically defined at compile time
 * and defines the max number of items that can be registered in the bitmap.
 * The remote accesses are used in the VFS by the inum allocator.
 *********************************************************************************************/

typedef uint32_t    bitmap_t;

/**********************************************************************************************
 * This macro returns the number of 32 bits words required to register <size> entries.
 *********************************************************************************************/

#define BITMAP_SIZE(size) ( ((size) & 31) ? (((size)>>5) + 1) : ((size)>>5) )

/**********************************************************************************************
 * 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 )

/*********************************************************************************************
 * These macros are NOT used by the bitmap, but are 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 function reset all bits in a local or remote bitmap. 
 *********************************************************************************************
 * @ bitmap  : pointer on first word in the bitmap.
 * @ size    : number of bits in bitmap. 
 ********************************************************************************************/
extern void bitmap_init( bitmap_t * bitmap,
                         uint32_t   size );

extern void bitmap_remote_init( xptr_t   bitmap_xp,
                                uint32_t size );

/*********************************************************************************************
 * These functions set a specific bit in a local or remote bitmap.
 *********************************************************************************************
 * @ bitmap  : pointer on the bitmap
 * @ index   : bit index in the bitmap
 ********************************************************************************************/
extern inline void bitmap_set( bitmap_t * bitmap,
                               uint32_t   index );

extern inline void bitmap_remote_set( xptr_t    bitmap_xp,
                                      uint32_t  index );

/*********************************************************************************************
 * These functions clear a specific bit in a local or remote bitmap.
 *********************************************************************************************
 * @ bitmap  : pointer on the bitmap
 * @ index   : bit index in the bitmap
 ********************************************************************************************/
extern inline void bitmap_clear( bitmap_t * bitmap, 
                                 uint32_t   index );

extern inline void bitmap_remote_clear( xptr_t     bitmap_xp, 
                                        uint32_t   index );

/*********************************************************************************************
 * These functions search the first bit non-set in a local or remote bitmap, in the
 * range [0 , size-1], set this bit, and return the index of the found bit.
 * The lock protecting the bitmap must be taken by the caller.
 *********************************************************************************************
 * @ bitmap  : pointer on the bitmap.
 * @ size    : number of bits to scan.
 * @ returns index of found bit / returns 0xFFFFFFFF if not found.
 ********************************************************************************************/
extern uint32_t bitmap_alloc( bitmap_t * bitmap, 
                              uint32_t   size );

extern uint32_t bitmap_remote_alloc( xptr_t    bitmap_xp,
                                     uint32_t  size );

/*********************************************************************************************
 * This function returns the index of aa 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 );

/*********************************************************************************************
 * These functions return the index of first bit cleared in a local or remote 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 );

extern uint32_t bitmap_remote_ffc( xptr_t   bitmap_xp, 
                                   uint32_t size );

/*********************************************************************************************
 * This function takes a positive integer <val> as input argument, and returns the smallest
 * integer <order> such as : 1<<order >= val. 
 * In other words, <order> is the min number of bits to encode <val> values.
 *********************************************************************************************
 * @ val   : value to analyse
 * @ returns logarithm value
 ********************************************************************************************/
static inline uint32_t bits_log2( uint32_t val )
{
    uint32_t i;

    if( val > 0 )
    {
        val--;
        for( i=0 ; val > 0 ; i++ ) val = val >> 1;
        return i;
    }
    return 0;
}

#endif	/* _BITS_H_ */