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