libcds/src/basics.h

   1 /* basics.h
   2  * Copyright (C) 2005, Rodrigo Gonzalez, 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 <sys/types.h>
  27 #include <sys/resource.h>
  28 #include <sys/times.h>
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <unistd.h>
  32 #include <sys/stat.h>
  33 #include <iostream>
  34 #include <iostream>
  35 using namespace std;
  36 #include <cstdlib>
  37 #include <cmath>
  38
  39
  40 /** mask for obtaining the first 5 bits */
  41 #define mask31 0x0000001F
  42
  43 /** max function */
  44 #define max(x,y) ((x)>(y)?(x):(y))
  45 /** min function */
  46 #define min(x,y) ((x)<(y)?(x):(y))
  47
  48
  49 /** number of bits in a uint */
  50 #ifndef W
  51 #define W 32
  52 #endif
  53
  54 /** W-1 */
  55 #ifndef Wminusone
  56 #define Wminusone 31
  57 #endif
  58
  59 /** 2W*/
  60 #ifndef WW
  61 #define WW 64
  62 #endif
  63
  64 /** number of bits per uchar */
  65 #define bitsM 8
  66
  67 /** number of bytes per uint */
  68 #define BW 4
  69
  70 /** uchar = unsigned char */
  71 #ifndef uchar
  72 #define uchar unsigned char
  73 #endif
  74
  75 /** ushort = unsigned short */
  76 #ifndef ushort
  77 #define ushort unsigned short
  78 #endif
  79
  80 /** ulong = unsigned long */
  81 #ifndef ulong
  82 #define ulong unsigned long
  83 #endif
  84
  85 /** uint = unsigned int */
  86 #ifndef uint
  87 #define uint unsigned int
  88 #endif
  89
  90 /** number of different uchar values 0..255 */
  91 #define size_uchar 256
  92
  93 /** popcount array for uchars */
  94 const unsigned char __popcount_tab[] = {
  95   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,
  96   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,
  97   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,
  98   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,
  99   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,
 100   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,
 101   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,
 102   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,
 103 };
 104
 105 /** select array for uchars */
 106 const unsigned char select_tab[] = {
 107   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,
 108   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,
 109   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,
 110   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,
 111   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,
 112   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,
 113   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,
 114   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,
 115 };
 116
 117 /** prev array for uchars */
 118 const unsigned char prev_tab[] = {
 119   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,
 120   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,
 121   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,
 122   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,
 123   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,
 124   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,
 125   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,
 126   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,
 127 };
 128
 129
 130
 131 /** bits needed to represent a number between 0 and n */
 132 inline uint bits(uint n){
 133   uint b = 0;
 134   while (n) { b++; n >>= 1; }
 135   return b;
 136 }
 137
 138 /** reads bit p from e */
 139 #define bitget(e,p) ((((e)[(p)/W] >> ((p)%W))) & 1)
 140
 141 /** sets bit p in e */
 142 #define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W)))
 143
 144 /** cleans bit p in e */
 145 #define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W)))
 146
 147 /** uints required to represent e integers of n bits each */
 148 //#define uint_len(e,n) (((e)*(n))/W+(((e)*(n))%W > 0))
 149 inline uint uint_len(uint e, uint n) {
 150   return ((unsigned long long)e*n/W+((unsigned long long)e*n%W>0));
 151 }
 152
 153 /** Retrieve a given index from 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 be retrieved
 157  */
 158 inline uint get_field(uint *A, uint len, uint index) {
 159   if(len==0) return 0;
 160   register uint i=index*len/W, j=index*len-W*i, result;
 161   if (j+len <= W)
 162     result = (A[i] << (W-j-len)) >> (W-len);
 163   else {
 164     result = A[i] >> j;
 165     result = result | (A[i+1] << (WW-j-len)) >> (W-len);
 166   }
 167   return result;
 168 }
 169
 170 /** Store a given value in index into array A where every value uses len bits
 171  * @param A Array
 172  * @param len Length in bits of each field
 173  * @param index Position to store in
 174  * @param x Value to be stored
 175  */
 176 inline void set_field(uint *A, uint len, uint index, uint x) {
 177   if(len==0) return;
 178   uint i=index*len/W, j=index*len-i*W;
 179   uint mask = ((j+len) < W ? ~0u << (j+len) : 0)
 180           | ((W-j) < W ? ~0u >> (W-j) : 0);
 181   A[i] = (A[i] & mask) | x << j;
 182   if (j+len>W) {
 183     mask = ((~0u) << (len+j-W));
 184     A[i+1] = (A[i+1] & mask)| x >> (W-j);
 185   }
 186 }
 187
 188 /** Retrieve a given bitsequence from array A
 189  * @param A Array
 190  * @param ini Starting position
 191  * @param fin Retrieve until end-1
 192  */
 193 inline uint get_var_field(uint *A, uint ini, uint fin) {
 194   if(ini==fin+1) return 0;
 195   uint i=ini/W, j=ini-W*i, result;
 196   uint len = (fin-ini+1);
 197   if (j+len <= W)
 198     result = (A[i] << (W-j-len)) >> (W-len);
 199   else {
 200     result = A[i] >> j;
 201     result = result | (A[i+1] << (WW-j-len)) >> (W-len);
 202   }
 203   return result;
 204 }
 205
 206 /** Stores a given bitsequence into array A
 207  * @param A Array
 208  * @param ini Starting position
 209  * @param fin Store until end-1
 210  * @param x Value to be stored
 211  */
 212 inline void set_var_field(uint *A, uint ini, uint fin, uint x) {
 213   if(ini==fin+1) return;
 214   uint i=ini/W, j=ini-i*W;
 215   uint len = (fin-ini+1);
 216   uint mask = ((j+len) < W ? ~0u << (j+len) : 0)
 217           | ((W-j) < W ? ~0u >> (W-j) : 0);
 218   A[i] = (A[i] & mask) | x << j;
 219   if (j+len>W) {
 220     mask = ((~0u) << (len+j-W));
 221     A[i+1] = (A[i+1] & mask)| x >> (W-j);
 222   }
 223 }
 224
 225 /** Retrieve a given index from array A where every value uses 4 bits
 226  * @param A Array
 227  * @param index Position to be retrieved
 228  */
 229 inline uint get_field4(uint *A, uint index) {
 230   unsigned i=index/8, j=(index&0x7)<<2;
 231   return (A[i] << (28-j)) >> (28);
 232 }
 233
 234 /** Counts the number of 1s in x */
 235 inline uint popcount(int x){
 236   return __popcount_tab[(x >>  0) & 0xff]  + __popcount_tab[(x >>  8) & 0xff]
 237           + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff];
 238 }
 239
 240 /** Counts the number of 1s in the first 16 bits of x */
 241 inline uint popcount16(int x){
 242   return __popcount_tab[x & 0xff]  + __popcount_tab[(x >>  8) & 0xff];
 243 }
 244
 245 /** Counts the number of 1s in the first 8 bits of x */
 246 inline uint popcount8(int x){
 247   return __popcount_tab[x & 0xff];
 248 }
 249
 250 #endif  /* _BASICS_H */
 251