+++ /dev/null
-/* 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 <sys/types.h>
-#include <sys/resource.h>
-#include <sys/times.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <unistd.h>
-#include <sys/stat.h>
-#include <iostream>
-#include <iostream>
-////using namespace std;
-#include <cstdlib>
-#include <cmath>
-
-
-/** 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 */
-
projects / SXSI / XMLTree.git / blobdiff