libcds/src/basics.h

   1 /* basics.h
   2  * Copyright (C) 2008, Rodrigo Gonzalez & Francisco Claude, all rights reserved.
   3  *
   4  * Some preliminary stuff
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22
  23 #ifndef _BASICS_H
  24 #define _BASICS_H
  25
  26 #include <iostream>
  27 using namespace std;
  28 #include <cstdlib>
  29 #include <cmath>
  30
  31
  32 /** mask for obtaining the first 5 bits */
  33 #define mask31 0x0000001F
  34
  35 /** max function */
  36 #define max(x,y) ((x)>(y)?(x):(y))
  37 /** min function */
  38 #define min(x,y) ((x)<(y)?(x):(y))
  39
  40
  41 /** number of bits in a uint */
  42 #define W 32
  43
  44 /** W-1 */
  45 #define Wminusone 31
  46
  47 /** 2W*/
  48 #define WW 64
  49
  50 /** number of bits per uchar */
  51 #define bitsM 8
  52
  53 /** number of bytes per uint */
  54 #define BW 4
  55
  56 /** uchar = unsigned char */
  57 #ifndef uchar
  58 #define uchar unsigned char
  59 #endif
  60
  61 /** ushort = unsigned short */
  62 #ifndef ushort
  63 #define ushort unsigned short
  64 #endif
  65
  66 /** ulong = unsigned long */
  67 #ifndef ulong
  68 #define ulong unsigned long
  69 #endif
  70
  71 /** uint = unsigned int */
  72 #ifndef uint
  73 #define uint unsigned int
  74 #endif
  75
  76 /** number of different uchar values 0..255 */
  77 #define size_uchar 256
  78
  79 /** popcount array for uchars */
  80 const unsigned char __popcount_tab[] = {
  81   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  82   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  83   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  84   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  85   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  86   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  87   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  88   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  89 };
  90
  91 /** select array for uchars */
  92 const unsigned char select_tab[] = {
  93   0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
  94   6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
  95   7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
  96   6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
  97   8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
  98   6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
  99   7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
 100   6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
 101 };
 102
 103 /** prev array for uchars */
 104 const unsigned char prev_tab[] = {
 105   0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 106   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 107   7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 108   7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 109   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 110   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 111   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 112   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 113 };
 114
 115
 116
 117 /** bits needed to represent a number between 0 and n */
 118 inline uint bits(uint n){
 119   uint b = 0;
 120   while (n) { b++; n >>= 1; }
 121   return b;
 122 }
 123
 124 /** reads bit p from e */
 125 #define bitget(e,p) ((((e)[(p)/W] >> ((p)%W))) & 1)
 126
 127 /** sets bit p in e */
 128 #define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W)))
 129
 130 /** cleans bit p in e */
 131 #define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W)))
 132
 133 /** uints required to represent e integers of n bits each */
 134 #define uint_len(e,n) (((e)*(n))/W+(((e)*(n))%W > 0))
 135
 136 /** Retrieve a given index from array A where every value uses len bits
 137  * @param A Array
 138  * @param len Length in bits of each field
 139  * @param index Position to be retrieved
 140  */
 141 inline uint get_field(uint *A, uint len, uint index) {
 142   if(len==0) return 0;
 143   register uint i=index*len/W, j=index*len-W*i, result;
 144   if (j+len <= W)
 145     result = (A[i] << (W-j-len)) >> (W-len);
 146   else {
 147     result = A[i] >> j;
 148     result = result | (A[i+1] << (WW-j-len)) >> (W-len);
 149   }
 150   return result;
 151 }
 152
 153 /** Store a given value in index into array A where every value uses len bits
 154  * @param A Array
 155  * @param len Length in bits of each field
 156  * @param index Position to store in
 157  * @param x Value to be stored
 158  */
 159 inline void set_field(uint *A, uint len, uint index, uint x) {
 160   if(len==0) return;
 161   uint i=index*len/W, j=index*len-i*W;
 162   uint mask = ((j+len) < W ? ~0u << (j+len) : 0)
 163           | ((W-j) < W ? ~0u >> (W-j) : 0);
 164   A[i] = (A[i] & mask) | x << j;
 165   if (j+len>W) {
 166     mask = ((~0u) << (len+j-W));
 167     A[i+1] = (A[i+1] & mask)| x >> (W-j);
 168   }
 169 }
 170
 171 /** Retrieve a given bitsequence from array A
 172  * @param A Array
 173  * @param ini Starting position
 174  * @param fin Retrieve until end-1
 175  */
 176 inline uint get_var_field(uint *A, uint ini, uint fin) {
 177   if(ini==fin+1) return 0;
 178   uint i=ini/W, j=ini-W*i, result;
 179   uint len = (fin-ini+1);
 180   if (j+len <= W)
 181     result = (A[i] << (W-j-len)) >> (W-len);
 182   else {
 183     result = A[i] >> j;
 184     result = result | (A[i+1] << (WW-j-len)) >> (W-len);
 185   }
 186   return result;
 187 }
 188
 189 /** Stores a given bitsequence into array A
 190  * @param A Array
 191  * @param ini Starting position
 192  * @param fin Store until end-1
 193  * @param x Value to be stored
 194  */
 195 inline void set_var_field(uint *A, uint ini, uint fin, uint x) {
 196   if(ini==fin+1) return;
 197   uint i=ini/W, j=ini-i*W;
 198   uint len = (fin-ini+1);
 199   uint mask = ((j+len) < W ? ~0u << (j+len) : 0)
 200           | ((W-j) < W ? ~0u >> (W-j) : 0);
 201   A[i] = (A[i] & mask) | x << j;
 202   if (j+len>W) {
 203     mask = ((~0u) << (len+j-W));
 204     A[i+1] = (A[i+1] & mask)| x >> (W-j);
 205   }
 206 }
 207
 208 /** Retrieve a given index from array A where every value uses 4 bits
 209  * @param A Array
 210  * @param index Position to be retrieved
 211  */
 212 inline uint get_field4(uint *A, uint index) {
 213   unsigned i=index/8, j=(index&0x7)<<2;
 214   return (A[i] << (28-j)) >> (28);
 215 }
 216
 217 /** Counts the number of 1s in x */
 218 inline uint popcount(int x){
 219   return __popcount_tab[(x >>  0) & 0xff]  + __popcount_tab[(x >>  8) & 0xff]
 220           + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff];
 221 }
 222
 223 /** Counts the number of 1s in the first 16 bits of x */
 224 inline uint popcount16(int x){
 225   return __popcount_tab[x & 0xff]  + __popcount_tab[(x >>  8) & 0xff];
 226 }
 227
 228 /** Counts the number of 1s in the first 8 bits of x */
 229 inline uint popcount8(int x){
 230   return __popcount_tab[x & 0xff];
 231 }
 232
 233 #endif  /* _BASICS_H */
 234