c_cpp/readscorr/2bitarray.h

   1 // by Hu Xuesong
   2
   3 #ifndef _GA_TBITARRAY_H
   4 #define _GA_TBITARRAY_H
   5
   6 #include "gtypendef.h"
   7 #include <stdint.h>
   8 #include <stdlib.h>
   9
  10 #include <limits.h>             /* for CHAR_BIT */
  11
  12 #define CHAR_TBIT (CHAR_BIT>>1) // 8/2 = 4
  13
  14 #define TBITSHIFT(b) (((b) % CHAR_TBIT)<<1)
  15
  16 #define TBITMASK(b) /* Returns the bit mask of a byte */ \
  17     (3 << TBITSHIFT(b))
  18
  19 #define TBITSLOT(b) ((b) / CHAR_TBIT) // Just the index of char[]
  20
  21 #define TBITGETVALUE(a, b) /* Get Value */ \
  22     (((a)[TBITSLOT(b)] >> TBITSHIFT(b)) & 3)
  23 //  (((a)[2BITSLOT(b)] & 2BITMASK(b)) >> 2BITSHIFT(b))
  24
  25 #define TBITNSLOTS(nb) ((2*(nb) + CHAR_BIT - 1) / CHAR_BIT) // caltulate the length of char[]. x*2 can overflow while x<<1 cannot.
  26
  27 /*
  28 __inline void TBITSetValue ( char arr[], size_t index, uint_fast8_t value );
  29 __inline uint_fast8_t TBITSaturatedADD ( char arr[], size_t index, int_fast8_t value );
  30 __inline uint_fast8_t TBITSaturatedINC ( char arr[], size_t index );
  31 __inline uint_fast8_t TBITSaturatedDEC ( char arr[], size_t index );
  32 */
  33
  34 // I find gcc will not inline functions in other c files, thus move them here.
  35
  36 FORCE_INLINE void TBITSetValue ( char arr[], size_t index, uint_fast8_t value ) {
  37     if (value>3) value=3;
  38     unsigned char theByte=(arr[TBITSLOT(index)]) & ~TBITMASK(index);
  39     theByte |= value << TBITSHIFT(index);
  40     arr[TBITSLOT(index)] = theByte;
  41 }
  42
  43 FORCE_INLINE uint_fast8_t TBITSaturatedADD ( char arr[], size_t index, int_fast8_t value ) {
  44     unsigned char theByte = (arr[TBITSLOT(index)]);
  45     int_fast8_t theValue = (theByte >> TBITSHIFT(index)) & 3 ;
  46     if (value==0) {
  47         return (uint_fast8_t) theValue;
  48     } else if (value > 0) {
  49         if (theValue > 3-value) theValue=3;
  50           else theValue += value;
  51     } else {
  52         if (theValue < -value) theValue =0;
  53           else theValue += value;
  54     }
  55     theByte &= ~TBITMASK(index);
  56     theByte |= theValue << TBITSHIFT(index);
  57     arr[TBITSLOT(index)] = theByte;
  58     return (uint_fast8_t) theValue;
  59 }
  60
  61 FORCE_INLINE uint_fast8_t TBITSaturatedINC ( char arr[], size_t index ) {
  62     unsigned char theByte = (arr[TBITSLOT(index)]);
  63     uint_fast8_t theValue = (theByte >> TBITSHIFT(index)) & 3 ;
  64     if (theValue==3) {
  65         return 3;
  66     } else {
  67         ++theValue;
  68         theByte &= ~TBITMASK(index);
  69         theByte |= theValue << TBITSHIFT(index);
  70         arr[TBITSLOT(index)] = theByte;
  71         return theValue;
  72     }
  73 }
  74
  75 FORCE_INLINE uint_fast8_t TBITSaturatedDEC ( char arr[], size_t index ) {
  76     unsigned char theByte = (arr[TBITSLOT(index)]);
  77     uint_fast8_t theValue = (theByte >> TBITSHIFT(index)) & 3 ;
  78     if (theValue==0) {
  79         return 0;
  80     } else {
  81         --theValue;
  82         theByte &= ~TBITMASK(index);
  83         theByte |= theValue << TBITSHIFT(index);
  84         arr[TBITSLOT(index)] = theByte;
  85         return theValue;
  86     }
  87 }
  88
  89
  90
  91 #endif /* 2bitarray.h */
  92
  93 // Original comments for bitarray:
  94 /*
  95 (If you don't have <limits.h>, try using 8 for CHAR_BIT.)
  96
  97 Here are some usage examples. To declare an ``array'' of 47 bits:
  98
  99         char bitarray[BITNSLOTS(47)];
 100
 101 To set the 23rd bit:
 102
 103         BITSET(bitarray, 23);
 104
 105 To test the 35th bit:
 106
 107         if(BITTEST(bitarray, 35)) ...
 108
 109 To compute the union of two bit arrays and place it in a third array
 110 (with all three arrays declared as above):
 111
 112         for(i = 0; i < BITNSLOTS(47); i++)
 113                 array3[i] = array1[i] | array2[i];
 114
 115 To compute the intersection, use & instead of |.
 116
 117 As a more realistic example, here is a quick implementation of the Sieve
 118 of Eratosthenes, for computing prime numbers:
 119
 120 #include <stdio.h>
 121 #include <string.h>
 122
 123 #define MAX 10000
 124
 125 int main()
 126 {
 127         char bitarray[BITNSLOTS(MAX)];
 128         int i, j;
 129
 130         memset(bitarray, 0, BITNSLOTS(MAX));
 131
 132         for(i = 2; i < MAX; i++) {
 133                 if(!BITTEST(bitarray, i)) {
 134                         printf("%d\n", i);
 135                         for(j = i + i; j < MAX; j += i)
 136                                 BITSET(bitarray, j);
 137                 }
 138         }
 139         return 0;
 140 }
 141 */
 142