X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;ds=sidebyside;f=src%2Fbasics.h;fp=src%2Fbasics.h;h=85bfe22e6f3b0702bcd4fc170004b0a0b79322cc;hb=3fd4bcef236556c7f3bff1d2be8d3f4206245501;hp=0000000000000000000000000000000000000000;hpb=dc7a566a39187bfcea70737cda7278f858cd9842;p=SXSI%2Flibcds.git diff --git a/src/basics.h b/src/basics.h new file mode 100644 index 0000000..85bfe22 --- /dev/null +++ b/src/basics.h @@ -0,0 +1,262 @@ +/* basics.h + * Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved. + * + * Some preliminary stuff + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + */ + + +#ifndef _BASICS_H +#define _BASICS_H + +#include +#include +#include +#include +#include +#include +#include +#include +#include +////using namespace std; +#include +#include + + +/** mask for obtaining the first 5 bits */ +#define mask31 0x0000001F + +/** max function */ +//#define max(x,y) ((x)>(y)?(x):(y)) +/** min function */ +//#define min(x,y) ((x)<(y)?(x):(y)) + + +/** number of bits in a uint */ +#undef W +#define W 32 + +/** W-1 */ +#undef Wminusone +#define Wminusone 31 + +/** 2W*/ +#undef WW +#define WW 64 + +/** number of bits per uchar */ +#define bitsM 8 + +/** number of bytes per uint */ +#define BW 4 + +/** uchar = unsigned char */ +#ifndef uchar +#define uchar unsigned char +#endif + +/** ushort = unsigned short */ +#ifndef ushort +#define ushort unsigned short +#endif + +/** ulong = unsigned long */ +#ifndef ulong +#define ulong unsigned long +#endif + +/** uint = unsigned int */ +#ifndef uint +#define uint unsigned int +#endif + +/** number of different uchar values 0..255 */ +#define size_uchar 256 + +/** popcount array for uchars */ +const unsigned char __popcount_tab[] = { + 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, + 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, + 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, + 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, + 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, + 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, + 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, + 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, +}; + +/** select array for uchars */ +const unsigned char select_tab[] = { + 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, + 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, + 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, + 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, + 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, + 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, + 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, + 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, +}; + +/** prev array for uchars */ +const unsigned char prev_tab[] = { + 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, + 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, + 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, + 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, + 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, + 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, + 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, + 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, +}; + + + +/** bits needed to represent a number between 0 and n */ +inline uint bits(uint n){ + uint b = 0; + while (n) { b++; n >>= 1; } + return b; +} + +/** reads bit p from e */ +#define bitget(e,p) ((((e)[(p)/W] >> ((p)%W))) & 1) + +/** sets bit p in e */ +#define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W))) + +/** cleans bit p in e */ +#define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W))) + +/** uints required to represent e integers of n bits each */ +//#define uint_len(e,n) (((e)*(n))/W+(((e)*(n))%W > 0)) +inline uint uint_len(uint e, uint n) { + return ((unsigned long long)e*n/W+((unsigned long long)e*n%W>0)); +} + +/** Retrieve a given index from array A where every value uses len bits + * @param A Array + * @param len Length in bits of each field + * @param index Position to be retrieved + */ +inline uint get_field(uint *A, uint len, uint index) { + if(len==0) return 0; + register uint i=index*len/W, j=index*len-W*i, result; + if (j+len <= W) + result = (A[i] << (W-j-len)) >> (W-len); + else { + result = A[i] >> j; + result = result | (A[i+1] << (WW-j-len)) >> (W-len); + } + return result; +} + +/** Store a given value in index into array A where every value uses len bits + * @param A Array + * @param len Length in bits of each field + * @param index Position to store in + * @param x Value to be stored + */ +inline void set_field(uint *A, uint len, uint index, uint x) { + if(len==0) return; + uint i=index*len/W, j=index*len-i*W; + uint mask = ((j+len) < W ? ~0u << (j+len) : 0) + | ((W-j) < W ? ~0u >> (W-j) : 0); + A[i] = (A[i] & mask) | x << j; + if (j+len>W) { + mask = ((~0u) << (len+j-W)); + A[i+1] = (A[i+1] & mask)| x >> (W-j); + } +} + +/** Retrieve a given bitsequence from array A + * @param A Array + * @param ini Starting position + * @param fin Retrieve until end-1 + */ +inline uint get_var_field(uint *A, uint ini, uint fin) { + if(ini==fin+1) return 0; + uint i=ini/W, j=ini-W*i, result; + uint len = (fin-ini+1); + if (j+len <= W) + result = (A[i] << (W-j-len)) >> (W-len); + else { + result = A[i] >> j; + result = result | (A[i+1] << (WW-j-len)) >> (W-len); + } + return result; +} + +/** Stores a given bitsequence into array A + * @param A Array + * @param ini Starting position + * @param fin Store until end-1 + * @param x Value to be stored + */ +inline void set_var_field(uint *A, uint ini, uint fin, uint x) { + if(ini==fin+1) return; + uint i=ini/W, j=ini-i*W; + uint len = (fin-ini+1); + uint mask = ((j+len) < W ? ~0u << (j+len) : 0) + | ((W-j) < W ? ~0u >> (W-j) : 0); + A[i] = (A[i] & mask) | x << j; + if (j+len>W) { + mask = ((~0u) << (len+j-W)); + A[i+1] = (A[i+1] & mask)| x >> (W-j); + } +} + +/** Retrieve a given index from array A where every value uses 4 bits + * @param A Array + * @param index Position to be retrieved + */ +inline uint get_field4(uint *A, uint index) { + unsigned i=index/8, j=(index&0x7)<<2; + return (A[i] << (28-j)) >> (28); +} + +/** Counts the number of 1s in x */ +inline uint popcount(int x){ + return __popcount_tab[(x >> 0) & 0xff] + __popcount_tab[(x >> 8) & 0xff] + + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff]; +} +inline unsigned int +fast_popcount(int x) +{ + uint m1 = 0x55555555; + uint m2 = 0x33333333; + uint m4 = 0x0f0f0f0f; + x -= (x >> 1) & m1; + x = (x & m2) + ((x >> 2) & m2); + x = (x + (x >> 4)) & m4; + x += x >> 8; + return (x + (x >> 16)) & 0x3f; +} + + + +/** Counts the number of 1s in the first 16 bits of x */ +inline uint popcount16(int x){ + return __popcount_tab[x & 0xff] + __popcount_tab[(x >> 8) & 0xff]; +} + +/** Counts the number of 1s in the first 8 bits of x */ +inline uint popcount8(int x){ + return __popcount_tab[x & 0xff]; +} + +#endif /* _BASICS_H */ +