eg_bit.h

Go to the documentation of this file.

/* EGlib "Efficient General Library" provides some basic structures and
 * algorithms commons in many optimization algorithms.
 *
 * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
 * 
 * This library 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.1 of the License, or (at your
 * option) any later version.
 *
 * This library 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 Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
/* ========================================================================= */
/* bit operations over arbitrary memory segnemts 
 *
 * Version 0.0.1 2003-04-11
 *
 * - 2006-01-30
 *    - Change some type definitions so that to make its behavior independent
 *    of the plataform, we choose to use bit words of size 32 bits.
 * - 2005-08-01
 *    - Fix some types to size_t for alloc/free functions
 * - 2004-11-05 
 *    - Add EGbitsetSize macro to compute the wright size of static
 *      bitsets.
 * - 2003-05-14 
 *    - Fix problem in EGbitTest
 * - 2003-04-29 
 *    - Change the parameters that are not changed to const.
 *    - Change the definition of the function to 'extern inline int' to 
 *      speed-up the running time for all funcions but EGbitNext.
 *
 * */
/* ========================================================================= */

#ifndef __EG_BIT_H__
#define __EG_BIT_H__
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <limits.h>
#include "eg_config.h"
#include "eg_macros.h"
#include "eg_mempool.h"
/* ============================================================================
   Bitset definitions and functions                                                                
   ==========================================================================*/


/* ========================================================================== */
/** @name Word lengths and related macros */
/*@{*/
#define __EGBIT_WORD_SIZE__ 32U
#define __EGBIT_SHIFT__ 5U
#define __EGBIT_MASK__ 31U
/*@}*/

/* ========================================================================== */
/** @brief Macro to compute the right size of a bitset given the desired 
 * number of bits in the bitset */
#define EGbitsetSize(__Bsize) (((__Bsize)>>__EGBIT_SHIFT__)+(((__Bsize)&__EGBIT_MASK__)?1:0))

/* ============================================================================   
   all positions are in bits not in bytes   
   the ranged operations are performed between low_wordsize(from)   
   upper_wordsize(to) where low and upper are points in the wordsize generated   
   latice, for example, if wordsize is 32, and from is 46 and to is 90, then   
   the real range will be [32,95] so, be careful and remember that the range   
   start at zero.   
      
   this function is to check if the parameter are well set up   
   ========================================================================= */
typedef int32_t bit_int_t;
typedef bit_int_t EGbitset_t;

/* ========================================================================= */
/* this function only check if the internal parameters of this utilities were
 * well set at compile time */
/* ========================================================================= */
int EGbitSanity (void);

/* ========================================================================= */
/* free a bitset */
/* ========================================================================= */
extern inline void EGfreeBitSet (void *bitfield,
                                 const size_t size,
                                 EGmemPool_t * mem)
{
  EGmemPoolFree (bitfield, size / CHAR_BIT, mem);
  return;
}

/* ========================================================================= */
/* create a bitset of 'n' bits, note that the actual size might be a bit bigger
 * for aligment reasons, it also set all bits to zero. */
/* ========================================================================= */
extern inline EGbitset_t *EGnewBitSet (EGmemPool_t * mem,
                                       size_t * n)
{

  /* local variables */
  EGbitset_t *res;

  /* padd the size *n */
  if (*n & __EGBIT_MASK__)
    *n = *n - (*n & __EGBIT_MASK__) + __EGBIT_WORD_SIZE__;

  /* looking for memory */
  res = (EGbitset_t *) EGmemPoolMalloc (mem, (*n) / CHAR_BIT);
  memset (res, 0, (*n) / CHAR_BIT);

  /* ending */
  return res;
}

/* ========================================================================= */
/* this function implements dst |= src in the range [from,to[, where from and to
 * are roneded down to the nearest complete word size. */
/* ========================================================================= */
extern inline int EGbitOr (bit_int_t * dst,
                           const bit_int_t * src,
                           const unsigned int from,
                           const unsigned int to)
{

  /* local variables */
  unsigned int i;
  unsigned int end = to >> __EGBIT_SHIFT__;

  /* doing or */
  for (i = (from >> __EGBIT_SHIFT__); i <= end; i++)
    dst[i] = dst[i] | src[i];

  /* ending */
  return 0;
}

/* ========================================================================= */
/* this function implements dst &= src in the range [from,to[, where from and to
 * are rounded down to the nearest complete word size. */
/* ========================================================================= */
extern inline int EGbitAnd (bit_int_t * dst,
                            const bit_int_t * src,
                            const unsigned int from,
                            const unsigned int to)
{

  /* local variables */
  unsigned int i;
  unsigned int end = to >> __EGBIT_SHIFT__;

  /* doing and */
  for (i = (from >> __EGBIT_SHIFT__); i <= end; i++)
    dst[i] &= src[i];

  /* ending */
  return 0;
}

/* ========================================================================= */
/* this function implement right shifts in the range [from,to[, where
 * from and to are rounded down to the nearest complete word size */
/* ========================================================================= */
extern inline int EGbitRightShift (bit_int_t * dst,
                                   const bit_int_t * src,
                                   const unsigned int shift,
                                   const unsigned int from,
                                   const unsigned int to)
{
  /* local variables */
  bit_int_t carry_on;
  register int i;
  unsigned int start = from >> __EGBIT_SHIFT__;

  /* doing the left shift */
  i = (to >> __EGBIT_SHIFT__);
  dst[i] = src[i] >> shift;
  carry_on = src[i] << (__EGBIT_WORD_SIZE__ - shift);
  for (i--; i >= (signed) start; i--)
  {
    dst[i] = (src[i] >> shift) | carry_on;
    carry_on = src[i] << (__EGBIT_WORD_SIZE__ - shift);
  }

  /* ending */
  return 0;
}

/* ========================================================================= */
/* this function implement left shifts in the range [from,to[, where
 * from and to are rounded down to the nearest complete word size */
/* ========================================================================= */
extern inline int EGbitLeftShift (bit_int_t * dst,
                                  const bit_int_t * src,
                                  const unsigned int shift,
                                  const unsigned int from,
                                  const unsigned int to)
{
  /* local variables */
  bit_int_t carry_on = 0;
  register unsigned int i;
  unsigned int end = to >> __EGBIT_SHIFT__;

  /* doing the left shift */
  i = (from >> __EGBIT_SHIFT__);
  carry_on = src[i] >> (__EGBIT_WORD_SIZE__ - shift);
  dst[i] = src[i] << shift;
  for (i++; i <= end; i++)
  {
    dst[i] = (src[i] << shift) | carry_on;
    carry_on = src[i] >> (__EGBIT_WORD_SIZE__ - shift);
  }

  /* ending */
  return 0;
}

/* ========================================================================= */
/* this function set to zero the bit dst:pos (i.e. the bit in the position 'pos'
 * */
/* ========================================================================= */
extern inline int EGbitUnset (bit_int_t * dst,
                              const unsigned int pos)
{
  MESSAGE (__EGBIT_DEBUG_LEVEL__,
           "set bit %u (chunk %u position %u)", pos,
           pos >> __EGBIT_SHIFT__, pos & __EGBIT_MASK__);

  dst[(pos >> __EGBIT_SHIFT__)] &= (~(1 << (pos & __EGBIT_MASK__)));

  return 0;
}

/* ========================================================================= */
/* this function set to one the bit dst:pos (i.e. the bit in the position 'pos'
 * */
/* ========================================================================= */
extern inline int EGbitSet (bit_int_t * const dst,
                            const unsigned int pos)
{
  MESSAGE (__EGBIT_DEBUG_LEVEL__,
           "set bit %u (chunk %u position %u)", pos,
           pos >> __EGBIT_SHIFT__, pos & __EGBIT_MASK__);

  dst[(pos >> __EGBIT_SHIFT__)] |= (1 << (pos & __EGBIT_MASK__));

  return 0;
}

/* ========================================================================= */
/* this function implement x+=y function in the range [from,to[, where
 * from and to are rounded down to the nearest complete word size */
/* ========================================================================= */
extern inline int EGbitPlus (bit_int_t * dst,
                             const bit_int_t * src,
                             const unsigned int from,
                             const unsigned int to)
{
  /* local variables */
  bit_int_t carry_on = 0,
    carry_on3 = 0,
    carry_on2 = 0;
  register unsigned int i;
  unsigned int end = to >> __EGBIT_SHIFT__;

  /* doung the sum */
  for (i = (from >> __EGBIT_SHIFT__); i <= end; i++)
  {
    carry_on2 =
      ((dst[i]) >> (__EGBIT_WORD_SIZE__ - 1)) | ((src[i]) >>
                                                 (__EGBIT_WORD_SIZE__ - 1));
    carry_on3 =
      ((dst[i]) >> (__EGBIT_WORD_SIZE__ - 1)) & ((src[i]) >>
                                                 (__EGBIT_WORD_SIZE__ - 1));
    dst[i] = dst[i] + src[i] + carry_on;
    carry_on2 &=
      (((~dst[i]) & (1ULL << (__EGBIT_WORD_SIZE__ - 1)))) >>
      (__EGBIT_WORD_SIZE__ - 1);
    carry_on = carry_on2 | carry_on3;
  }
  /* ending */
  return 0;
}

/* ========================================================================= */
/* copy one bitset to another within some range [from,to] */
/* ========================================================================= */
extern inline int EGbitCopy (bit_int_t * const a,
                             const bit_int_t * const b,
                             const unsigned int from,
                             const unsigned int to)
{
  /* copying memory */
  memcpy (a + (from >> __EGBIT_SHIFT__),
          b + (from >> __EGBIT_SHIFT__),
          sizeof (bit_int_t) * ((to - from) >> __EGBIT_SHIFT__));

  /* ending */
  return 0;
}

/* ========================================================================= */
/* tell us if a <= b bit fields are equal within some range [from,to[. */
/* ========================================================================= */
extern inline int EGbitIsLeq (const bit_int_t * a,
                              const bit_int_t * b,
                              const unsigned int from,
                              const unsigned int to)
{
  /* local variables */
  register unsigned int i;
  unsigned int start = from >> __EGBIT_SHIFT__;

  /* doing the left shift */
  i = (to >> __EGBIT_SHIFT__) - start;
  do
  {
    if (a[i] < b[i])
      return 1;
    if (a[i] > b[i])
      return 0;
  } while (i--);

  /* ending */
  return 1;
}

/* ========================================================================= */
/* tell us if these bit fields are equal within some range [from,to[. */
/* ========================================================================= */
extern inline int EGbitIsEqual (const bit_int_t * a,
                                const bit_int_t * b,
                                const unsigned int from,
                                const unsigned int to)
{
  /* local variables */
  register unsigned int i;
  unsigned int end = to >> __EGBIT_SHIFT__;

  /* doing the left shift */
  for (i = (from >> __EGBIT_SHIFT__); i <= end; i++)
  {
    if (a[i] != b[i])
      return 0;
  }

  /* ending */
  return 1;
}

/* ========================================================================= */
/* this function implements dst ^= src in the range [from,to[, where from and to
 * are rounded down to the nearest complete word size. */
/* ========================================================================= */
extern inline int EGbitXor (bit_int_t * dst,
                            const bit_int_t * src,
                            const unsigned int from,
                            const unsigned int to)
{

  /* local variables */
  unsigned int i;
  unsigned int end = to >> __EGBIT_SHIFT__;

  /* doing Xor */
  for (i = (from >> __EGBIT_SHIFT__); i <= end; i++)
    dst[i] ^= src[i];

  /* ending */
  return 0;
}

/* ========================================================================= */
/* this function implements dst = 0 in the range [from,to[, where from and to
 * are rounded down to the nearest complete word size. */
/* ========================================================================= */
extern inline int EGbitReset (bit_int_t * dst,
                              const unsigned int from,
                              const unsigned int to)
{

  /* local variables */
  unsigned int lo;
  unsigned int up;

  /* doing reset */
  lo = from >> __EGBIT_SHIFT__;
  up = to >> __EGBIT_SHIFT__;
  memset (dst + lo, 0, (up + 1 - lo) * sizeof (bit_int_t));

  /* ending */
  return 0;
}

/* ========================================================================= */
/* this function return the value of dst:pos (i.e. the value of the bit in the
 * position 'pos' */
/* ========================================================================= */
extern inline int EGbitTest (bit_int_t const *const dst,
                             const unsigned int pos)
{
  MESSAGE (__EGBIT_DEBUG_LEVEL__,
           "in EGbitTest, test bit %u (chunk %u position %u)", pos,
           pos >> __EGBIT_SHIFT__, pos & __EGBIT_MASK__);

  return (dst[(pos >> __EGBIT_SHIFT__)] & (1 << (pos & __EGBIT_MASK__)));
}

/* ========================================================================= */
/* return the next one position in the bitset from 'pos' (inclusive), if no
 * next one position is found it return a number bigger than size */
/* ========================================================================= */
extern inline unsigned int EGbitNext (const bit_int_t * dst,
                                      const unsigned int pos,
                                      const unsigned int size)
{

  /* local variables */
  unsigned int curChunk = pos >> __EGBIT_SHIFT__,
    curPos = pos;
  bit_int_t curMask = (1 << (pos & __EGBIT_MASK__));

  /* first we check the first chunk bit by bit */
  while (curMask)
  {
    if (dst[curChunk] & curMask)
      return curPos;
    curPos++;
    curMask = curMask << 1;
  }

  /* now we look chunk by chunk */
  curChunk++;
  curMask = 1;
  while ((curPos < size) && (!dst[curChunk]))
  {
    curChunk++;
    curPos += __EGBIT_WORD_SIZE__;
  }

  /* if we run out of space we exit */
  if (curPos >= size)
    return (size << 1);

  /* if we are here is because there is a one bit in 
   * the range, we are only looking for it */
  while (curMask)
  {
    if (dst[curChunk] & curMask)
      return curPos;
    curPos++;
    curMask = curMask << 1;
  }

  /* ending */
  /* if we reach this line then the code is wrong */
  EXIT (1, "This is due to a programming error or some memory overwrite");
  exit (1);
  return UINT_MAX;
}

/* ========================================================================= */
/* return the previous one position in the bitset from 'pos' (inclusive), if no
 * previous one position is found it return a number bigger than pos */
/* ========================================================================= */
extern inline unsigned int EGbitPrev (const EGbitset_t * dst,
                                      const unsigned int pos)
{

  /* local variables */
  register unsigned int curChunk = pos >> __EGBIT_SHIFT__,
    curPos = pos;
  EGbitset_t curMask = (1 << (pos & __EGBIT_MASK__));

  /* first we check the first chunk bit by bit */
  while (curMask)
  {
    if (dst[curChunk] & curMask)
      return curPos;
    curPos--;
    curMask = curMask >> 1;
  }

  /* now we look chunk by chunk */
  curChunk--;
  while ((curChunk < pos) && (!dst[curChunk]))
  {
    curChunk--;
    curPos -= __EGBIT_WORD_SIZE__;
  }

  /* if we run out of space we exit */
  if (curChunk > pos)
    return UINT_MAX;

  /* if we are here is becouse there is a one bit in the range, we are only
   * looking for it */
  curMask = 1U << __EGBIT_MASK__;
  while (curMask)
  {
    if (dst[curChunk] & curMask)
      return curPos;
    curPos--;
    curMask = curMask >> 1;
  }

  /* ending */
  /* if we reach this line then the code is wrong */
  EXIT (1, "This is due to a programming error or some memory overwrite");
  exit (1);
  return UINT_MAX;
}

/** @brief Count number of on bits on 32-bit integers.
 * @return Number of on bits in the given 32-bit integer
 * @par Description:
 * Parallel Count carries out bit counting in a parallel fashion. Consider n
 * after the first line has finished executing. Imagine splitting n into pairs
 * of bits. Each pair contains the number of ones in those two bit positions in
 * the original n. After the second line has finished executing, each nibble
 * contains the number of ones in those four bits positions in the original n.
 * Continuing this for five iterations, the 64 bits contain the number of ones
 * among these sixty-four bit positions in the original n. That is what we
 * wanted to compute.*/
extern inline EGbitset_t EGbitElemBitCount (EGbitset_t n)
{
#define EGBIT_TWO(c)     (0x1u << (c))
#define EGBIT_MASK(c)    (((unsigned int)(-1)) / (EGBIT_TWO(EGBIT_TWO(c)) + 1u))
#define EGBIT_COUNT(x,c) ((x) & EGBIT_MASK(c)) + (((x) >> (EGBIT_TWO(c))) & EGBIT_MASK(c))
  n = EGBIT_COUNT (n, 0);
  n = EGBIT_COUNT (n, 1);
  n = EGBIT_COUNT (n, 2);
  n = EGBIT_COUNT (n, 3);
  n = EGBIT_COUNT (n, 4);
#if __EGBIT_WORD_SIZE__ == 64U
  n = EGBIT_COUNT (n, 5);
#endif
#undef EGBIT_TWO
#undef EGBIT_MASK
#undef EGBIT_COUNT
  return n;
}

 /** @brief Count the number of on-bits in a bit-map */
extern inline EGbitset_t EGbitCount (bit_int_t * bitset,
                                     const unsigned int from,
                                     const unsigned int to)
{
  /* local variables */
  unsigned int i = from >> __EGBIT_SHIFT__;
  unsigned int end = to >> __EGBIT_SHIFT__;
  EGbitset_t res = 0;
  for (; i <= end; i++)
    res += EGbitElemBitCount (bitset[i]);
  return res;
}

#endif

---