You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
426 lines
11 KiB
C
426 lines
11 KiB
C
/*
|
|
* This program is free software; you can redistribute it and/or modify
|
|
* it under the terms of the GNU Lesser General Public License as published by
|
|
* the Free Software Foundation; either version 2 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program 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 this program; if not, write to the Free Software
|
|
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
|
|
* 02111-1307, USA.
|
|
*
|
|
* (c) Copyright 2006,2007,2008 Jari OS Core Team <http://jarios.org>
|
|
* (c) Copyright 2008 Dmitry Gromada <gromada82@gmail.com>
|
|
* (c) Copyright 2010 Alexander Vdolainen <vdo@askele.com>
|
|
*
|
|
*
|
|
* Implements bitwise operations with multiword bitmaps
|
|
*/
|
|
|
|
#ifndef __BITWISE_H__
|
|
#define __BITWISE_H__
|
|
|
|
/* TODO: add arch deps */
|
|
//#include <arch/bitwise.h>
|
|
|
|
#ifdef BUILD_HOST_32BIT
|
|
#define BITS_PER_LONG 32
|
|
#else
|
|
#define BITS_PER_LONG 64
|
|
#endif
|
|
|
|
#if BITS_PER_LONG == 64
|
|
#define TYPE_LONG_SHIFT 6
|
|
#endif
|
|
|
|
#if BITS_PER_LONG == 32
|
|
#define TYPE_LONG_SHIFT 5
|
|
#endif
|
|
|
|
typedef struct __bitmap {
|
|
int nwords;
|
|
unsigned long *map;
|
|
} bitmap_t;
|
|
|
|
/**
|
|
* @fn static inline void bit_set(void *bitmap, int bit)
|
|
* Set bit number @a bit in the bitmap @a bitmap
|
|
* @note The limit of @a bitmap = sizeof(unsigned long)
|
|
*
|
|
* @param[out] bitmap - A pointer to the bitmap
|
|
* @param bit - Number of bit to set
|
|
*/
|
|
#ifndef ARCH_BIT_SET
|
|
static inline void bit_set(void *bitmap, int bit)
|
|
{
|
|
*(unsigned long *)bitmap |= (1UL << bit);
|
|
}
|
|
#else
|
|
#define bit_set(bitmap, bit) arch_bit_set(bitmap, bit)
|
|
#endif /* ARCH_BIT_SET */
|
|
|
|
/**
|
|
* @fn static inline void bit_clear(void *bitmap, int bit)
|
|
* Clear bit number @a bit in the bitmap @a bitmap
|
|
* @note The limit of @a bitmap = sizeof(unsigned long)
|
|
*
|
|
* @param[out] bitmap - A pointer to the bitmap
|
|
* @param bit - Number of bit to clear
|
|
*/
|
|
#ifndef ARCH_BIT_CLEAR
|
|
static inline void bit_clear(void *bitmap, int bit)
|
|
{
|
|
*(unsigned long *)bitmap &= ~(1UL << bit);
|
|
}
|
|
#else
|
|
#define bit_clear(bitmap, bit) arch_bit_clear(bitmap, bit)
|
|
#endif /* ARCH_BIT_CLEAR */
|
|
|
|
/**
|
|
* @fn static inline void bit_toggle(void *bitmap, int bit)
|
|
* Toggle bit @a bit in the bitmap @a bitmap.
|
|
* @note The limit of @a bitmap = sizeof(unsigned long)
|
|
*
|
|
* @param[out] bitmap - A pointer to the bitmap.
|
|
* @param bit - Number of bit to toggle
|
|
*/
|
|
#ifndef ARCH_BIT_TOGGLE
|
|
static inline void bit_toggle(void *bitmap, int bit)
|
|
{
|
|
*(unsigned long *)bitmap ^= (1UL << bit);
|
|
}
|
|
#else
|
|
#define bit_toggle(bitmap, bit) arch_bit_toggle(bitmap, bit)
|
|
#endif /* ARCH_BIT_TOGGLE */
|
|
|
|
/**
|
|
* @fn static inline int bit_test(void *bitmap, int bitno)
|
|
* Test if bit with number @a bitno is set in the bitmap @a bitmap.
|
|
* @note The limit of @a bitmap = sizeof(unsigned long)
|
|
*
|
|
* @param bitmap - A pointer to the bitmap.
|
|
* @param bitno - Number of bit to test
|
|
* @return 1 if bit is set and 0 otherwise
|
|
*/
|
|
#ifndef ARCH_BIT_TEST
|
|
static inline int bit_test(void *bitmap, int bitno)
|
|
{
|
|
return ((*(unsigned long *)bitmap & (1UL << bitno)) >> bitno);
|
|
}
|
|
#else
|
|
#define bit_test(bitmap, bitno) arch_bit_test(bitmap, bitno)
|
|
#endif /* ARCH_BIT_TEST */
|
|
|
|
/**
|
|
* @fn static inline int bit_test_and_set(void *bitmap, int bitno)
|
|
* @brief Get old value of bit with number @a bitno and set @a bitno bit in the bitmap
|
|
*
|
|
* This function is similar to bit_set() except it copies old bit value before
|
|
* setting it to 1 and return that value after needed bit was setted.
|
|
* @note The limit of @a bitmap = sizeof(unsigned long)
|
|
*
|
|
* @param bitmap - A pointer to the bitmap
|
|
* @param bitno - The number of bit to test and set
|
|
* @return Old value of bit with number @a bitno
|
|
*/
|
|
#ifndef ARCH_BIT_TEST_AND_SET
|
|
static inline int bit_test_and_set(void *bitmap, int bitno)
|
|
{
|
|
int val = (*(unsigned long *)bitmap & (1 << bitno));
|
|
*(unsigned long *)bitmap |= (1UL << bitno);
|
|
|
|
return val;
|
|
}
|
|
#else
|
|
#define bit_test_and_set(bitmap, bitno) arch_bit_test_and_set(bitmap, bitno)
|
|
#endif /* ARCH_BIT_TEST_AND_SET */
|
|
|
|
/**
|
|
* @fn static inline int bit_test_and_reset(void *bitmap, int bitno)
|
|
* @brief Get old value of bit with number @a bitno and clear @a bitno bit in the bitmap
|
|
*
|
|
* This function is similar to bit_clear() except it copies old bit value before
|
|
* setting it to 1 and return that value after needed bit was setted.
|
|
* @note The limit of @a bitmap = sizeof(unsigned long)
|
|
*
|
|
* @param bitmap - A pointer to the bitmap
|
|
* @param bitno - The number of bit to test and set
|
|
* @return Old value of bit with number @a bitno
|
|
*/
|
|
#ifndef ARCH_BIT_TEST_AND_RESET
|
|
static inline int bit_test_and_reset(void *bitmap, int bitno)
|
|
{
|
|
int val = (*(unsigned long *)bitmap & (1 << bitno));
|
|
*(unsigned long *)bitmap &= ~(1UL << bitno);
|
|
|
|
return val;
|
|
}
|
|
#else
|
|
#define bit_test_and_reset(bitmap, bitno) arch_bit_test_and_reset(bitmap, bitno)
|
|
#endif /* ARCH_BIT_TEST_AND_RESET */
|
|
|
|
/**
|
|
* @fn static inline long bit_find_lsf(unsigned long word)
|
|
* Find first set least significant bit.
|
|
*
|
|
* @param word - Where to search
|
|
* @return Found bit number on success, negative value on failure.
|
|
*/
|
|
#ifndef ARCH_BIT_FIND_LSF
|
|
static inline long bit_find_lsf(unsigned long word)
|
|
{
|
|
long c = 0;
|
|
|
|
while(c <= ((sizeof(unsigned long)*8) - 1)) {
|
|
if(word & (1UL << (unsigned long)c)) return c;
|
|
c++;
|
|
}
|
|
|
|
return -1;
|
|
}
|
|
#else
|
|
#define bit_find_lsf(word) arch_bit_find_lsf(word)
|
|
#endif /* ARCH_BIT_FIND_LSF */
|
|
|
|
#ifndef ARCH_ZERO_BIT_FIND_LSF
|
|
#define zero_bit_find_lsf(word) bit_find_lsf(~(unsigned long)(word))
|
|
#else
|
|
#define zero_bit_find_lsf(word) arch_zero_bit_find_lsf(word)
|
|
#endif
|
|
|
|
/**
|
|
* @fn static inline long bit_find_msf(unsigned long word)
|
|
* Find most significant set bit in the @a word.
|
|
*
|
|
* @param word - Where to search.
|
|
* @return Found bit number on success, negative value on failure.
|
|
*/
|
|
#ifndef ARCH_BIT_FIND_MSF
|
|
static inline long bit_find_msf(unsigned long word)
|
|
{
|
|
long c = -1;
|
|
|
|
while (word) {
|
|
c++;
|
|
word >>= 1;
|
|
}
|
|
|
|
return c;
|
|
}
|
|
#else
|
|
#define bit_find_msf(word) arch_bit_find_msf(word)
|
|
#endif /* ARCH_BIT_FIND_MSF */
|
|
|
|
/**
|
|
* @fn static inline long bit_find_lsfz(unsigned long word)
|
|
* Find first zero least significant bit.
|
|
*
|
|
* @param word - Where to search
|
|
* @return Found bit number on success, negative value on failure.
|
|
*/
|
|
#ifndef ARCH_BIT_FIND_LSFZ
|
|
static inline long bit_find_lsfz(unsigned long word)
|
|
{
|
|
long c = -1;
|
|
|
|
word = ~word;
|
|
|
|
for (; word; c++, word >>= 1) {
|
|
if ((word & 0x01)) {
|
|
c++;
|
|
break;
|
|
}
|
|
}
|
|
|
|
return c;
|
|
}
|
|
#else
|
|
#define bit_find_lsfz(word) arch_bit_find_lsfz(word)
|
|
#endif /* ARCH_BIT_FIND_LSFZ */
|
|
|
|
/**
|
|
* @fn static inline long bit_find_msfz(unsigned long word)
|
|
* Find most significant zero bit in the @a word.
|
|
*
|
|
* @param word - Where to search.
|
|
* @return Found bit number on success, negative value on failure.
|
|
*/
|
|
#ifndef ARCH_BIT_FIND_MSFZ
|
|
static inline long bit_find_msfz(unsigned long word)
|
|
{
|
|
long c = -1;
|
|
|
|
word = ~word;
|
|
|
|
while (word) {
|
|
c++;
|
|
word >>= 1;
|
|
}
|
|
|
|
return c;
|
|
}
|
|
#else
|
|
#define bit_find_msfz(word) arch_bit_find_msfz(word)
|
|
#endif /* ARCH_BIT_FIND_MSFZ */
|
|
|
|
/**
|
|
* @fn static inline void bits_or(void *word, unsigned long flags)
|
|
* Executes logical OR with @a word and @a flags and writes result to @a word
|
|
* @note The limit of @a word = sizeof(unsigned long)
|
|
*
|
|
* @param[out] word - A pointer to memory results will be written to
|
|
* @param flsgs - Flags that will be OR'ed with @a word
|
|
*/
|
|
#ifndef ARCH_BITS_OR
|
|
static inline void bits_or(void *word, unsigned long flags)
|
|
{
|
|
*(unsigned long *)word |= flags;
|
|
}
|
|
#define bits_or(word, flags) panic("bits_or uniplemented")
|
|
#else
|
|
#define bits_or(word, flags) arch_bits_or(word, flags)
|
|
#endif /* ARCH_BITS_OR */
|
|
|
|
/**
|
|
* @fn static inline void bits_and(void *word, unsigned long mask)
|
|
* Executes logical AND with @a word and @a mask and writes result to @a word.
|
|
* @note The limit of @a word = sizeof(unsigned long)
|
|
*
|
|
* @param[out] word - A pointer to memory results will be written to
|
|
* @param mask - A mask that will be AND'ed with @a word
|
|
*/
|
|
#ifndef ARCH_BITS_AND
|
|
static inline void bits_and(void *word, unsigned long mask)
|
|
{
|
|
*(unsigned long *)word &= mask;
|
|
}
|
|
#else
|
|
#define bits_and(word, mask) arch_bits_and(word, mask)
|
|
#endif /* ARCH_BITS_AND */
|
|
|
|
|
|
/*
|
|
* Initialize multiword bitmap
|
|
*
|
|
* @param map - pointer to the multiword bitmap
|
|
* @param bitno - memory size in bits to allocate
|
|
*
|
|
* @return 0 on success, -1 if can't allocate memory
|
|
*/
|
|
int init_bitmap(bitmap_t *bitmap, int nbits);
|
|
|
|
/*
|
|
* Free memory taken by multiword bitmap
|
|
*
|
|
* @param bitmap - bitmap to free
|
|
*/
|
|
void free_bitmap(bitmap_t *map);
|
|
|
|
/**
|
|
* Set bit number @a bit in the bitmap @a bitmap
|
|
*
|
|
* @param bitmap - A pointer to the bitmap
|
|
* @param bit - Number of bit to set
|
|
*/
|
|
void bit_set_multi(bitmap_t *bitmap, int bitno);
|
|
|
|
/**
|
|
* test bit of a multiword bitmap
|
|
*
|
|
* @param bitmap - A pointer to the bitmap
|
|
* @param bitno - The number of bit to test
|
|
*
|
|
* @return value of the specified bit
|
|
*/
|
|
int bit_test_multi(bitmap_t *bitmap, int bitno);
|
|
|
|
/**
|
|
* @brief Get old value of bit with number @a bitno and set @a bitno bit in the bitmap
|
|
*
|
|
* This function is similar to bit_set() except it copies old bit value before
|
|
* setting it to 1 and return that value after needed bit was setted.
|
|
*
|
|
* @param bitmap - A pointer to the bitmap
|
|
* @param bitno - The number of bit to test and set
|
|
*
|
|
* @return Old value of bit with number @a bitno or -1 if bitno is illegal
|
|
*/
|
|
int bit_test_and_set_multi(bitmap_t *bitmap, int bitno);
|
|
|
|
/**
|
|
* @brief Get old value of bit with number @a bitno and clear @a bitno bit in the bitmap
|
|
*
|
|
* This function is similar to bit_set() except it copies old bit value before
|
|
* setting it to 1 and return that value after needed bit was setted.
|
|
*
|
|
* @param bitmap - A pointer to the bitmap
|
|
* @param bitno - The number of bit to test and set
|
|
*
|
|
* @return Old value of bit with number @a bitno or -1 if bitno is illegal
|
|
*/
|
|
int bit_test_and_reset_multi(bitmap_t *bitmap, int bitno);
|
|
|
|
|
|
/**
|
|
* Clear bit number @a bit in the bitmap @a bitmap
|
|
*
|
|
* @param bitmap - A pointer to the bitmap
|
|
* @param bit - Number of bit to clear
|
|
*/
|
|
void bit_clear_multi(bitmap_t *bitmap, int bitno);
|
|
|
|
/*
|
|
* Set multiple bits in the multiword bitmap
|
|
*
|
|
* @param bitmap - pointer to the multimap bitmap
|
|
* @param start_bit - bit to set from
|
|
* int end_bit - bit to set upto
|
|
*/
|
|
void bitrange_set_multi(bitmap_t *bitmap, int start_bit, int end_bit);
|
|
|
|
/*
|
|
* Clear multiple bits in the multiword bitmap
|
|
*
|
|
* @param bitmap - pointer to the multimap bitmap
|
|
* @param start_bit - bit to clear from
|
|
* int end_bit - bit to clear upto
|
|
*/
|
|
void bitrange_clear_multi(bitmap_t *bitmap, int start_bit, int end_bit);
|
|
|
|
/**
|
|
* Find most significant set bit in multimap word which from the 0 bit
|
|
* upto @end_bit
|
|
*
|
|
* @param word - Where to search.
|
|
* @param end_bit - most bit to search upto
|
|
* @return Found bit number on success, negative value on failure.
|
|
*/
|
|
int bit_find_msf_multi(bitmap_t *bitmap, int mbit);
|
|
|
|
/**
|
|
* Find first set least significant bit.
|
|
*
|
|
* @param word - Where to search
|
|
* @param sbit - least bit to search from
|
|
* @return Found bit number on success, negative value on failure.
|
|
*/
|
|
int bit_find_lsf_multi(bitmap_t *bitmap, int lbit);
|
|
|
|
#ifndef ARCH_BIT_TEST_AND_CLEAR
|
|
static inline int bit_test_and_clear(void *bitmap, int bitno)
|
|
{
|
|
int val = bit_test(bitmap, bitno);
|
|
bit_clear(bitmap, bitno);
|
|
return val;
|
|
}
|
|
#else
|
|
#define bit_test_and_clear(bitmap, bitno) arch_bit_test_and_clear(bitmap, bitno)
|
|
#endif
|
|
|
|
#endif /* __BITWISE_H__ */
|