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