root/modules/bitvector.c

DEFINITIONS

1. bv_create
2. bv_setbit
3. bv_getbit
4. bv_set
5. bv_set2
6. bv_set4
7. bv_get
8. bv_free

   1 #include "bitvector.h"
   2 #include "stdlib.h"
   3 #include "stddef.h"
bit_vector_t* bv_create(int len, int nbits)
   6 {
bit_vector_t* bm = (bit_vector_t*)malloc(sizeof(bit_vector_t));
   8     if (bm == NULL)
   9         return NULL;
bm->ptrLen = len * nbits / 8 + 1;
bm->nElem = len;
bm->nBits = nbits;
bm->ptr = malloc(bm->ptrLen);
  15     if (bm->ptr == NULL)
  16     {
free(bm);
  18         return NULL;
  19     }
  21     return bm;
  22 }
  24 // Utility function. Use bv_set instead.
  25 static inline void bv_setbit(const bit_vector_t* bm, int pos, int val)
  26 {
  27     int bp = pos - ((pos >> 3) << 3);
  28     if (val == 0)
bm->ptr[pos >> 3] &= ~(1 << bp);
  30     else
bm->ptr[pos >> 3] |=  (1 << bp);
  32 }
  34 // Utility function. Use bv_get instead.
  35 static inline int bv_getbit(const bit_vector_t* bm, int pos)
  36 {
  37     // Note: bv_get() and other code rely on this
  38     // method returning '1' if the bit is set.
  39     // If you are interested only in the truth value,
  40     // you can use bv_testbit().
  42     int bp = pos - ((pos >> 3) << 3);
  43     return (bm->ptr[pos >> 3] & (1 << bp)) >> bp;
  44 }
  46 void bv_set(const bit_vector_t* bm, int pos, int val)
  47 {
  48     int i = bm->nBits - 1;
  49     int bitpos = pos * bm->nBits;
  50     do
  51     {
bv_setbit(bm, bitpos + i, val & (1<<i));
  53     }while(--i >= 0);
  54 }
  56 // Same as bv_set, but sets val to two consecutive elements
  57 // instead of just one.
  58 void bv_set2(const bit_vector_t* bm, int pos, int val)
  59 {
  60     int i;
  61     int bitpos = pos * bm->nBits;
  62     for (i = 0; i < bm->nBits; ++i)
  63     {
  64         int t = val & (1<<i);
bv_setbit(bm, bitpos + i, t);
bv_setbit(bm, bitpos + i + bm->nBits, t);
  67     }
  68 }
  70 // Same as bv_set, but sets val to four consecutive elements
  71 // instead of just one.
  72 void bv_set4(const bit_vector_t* bm, int pos, int val)
  73 {
  74     int i;
  75     int bitpos = pos * bm->nBits;
  76     for (i = 0; i < bm->nBits; ++i)
  77     {
  78         int t = val & (1 << i);
bv_setbit(bm, bitpos + i, t);
bv_setbit(bm, bitpos + i + bm->nBits, t);
bv_setbit(bm, bitpos + i + bm->nBits * 2, t);
bv_setbit(bm, bitpos + i + bm->nBits * 3, t);
  83     }
  84 }
  86 int bv_get(const bit_vector_t* bm, int pos)
  87 {
  88     int ret = 0;
  89     int i = bm->nBits - 1;
  90     int bitpos = pos * bm->nBits;
  91     do
  92     {
ret |= (bv_getbit(bm, bitpos + i) << i);
  94     }while(--i >= 0);
  96     return ret;
  97 }
 100 void bv_free(bit_vector_t* bm)
 101 {
 102     if (bm)
 103     {
 104         if (bm->ptr)
 105         {
free(bm->ptr);
bm->ptr = NULL;
 108         }
free(bm);
 111     }
 112 }
 114 /*
 115 // Utility function. Not sure what for, but might
 116 // be useful in the future.
 117 static int bv_testbit(bit_vector_t* bm, int pos)
 118 {
 119     int bp = pos - ((pos >> 3) << 3);
 120     return bm->ptr[pos >> 3] & (1 << bp);
 121 }
 122 
 123 
 124 // This method is designed to be used for blitting the contents of the
 125 // bit_vector into the framebuffer. The value of each element is used to
 126 // look up a color value based on the lookup-table (last parameter).
 127 // Not used currently. Never will be probably.
 128 static void bv_expand(bit_vector_t* bm, unsigned char* dst, int len, color* lookup)
 129 {
 130     int i;
 131     int k;
 132 
 133     for (i = 0; i < len; ++i)
 134     {
 135         int elem = 0;
 136         int bitpos = i * bm->nBits;
 137         for (k = 0; k < bm->nBits; ++k)
 138         {
 139             int pos = bitpos + k;
 140             int bp = pos - ((pos >> 3) << 3);
 141             if (bm->ptr[pos >> 3] & (1 << bp))
 142                 elem |= (1 << k);
 143         }
 144         dst[i] = lookup[elem];
 145         dst[i+camera_screen.buffer_size] = lookup[elem];
 146     }
 147 }
 148 */