2 * Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved.
4 * Some preliminary stuff
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.
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.
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
26 #include <sys/types.h>
27 #include <sys/resource.h>
28 #include <sys/times.h>
40 /** mask for obtaining the first 5 bits */
41 #define mask31 0x0000001F
44 //#define max(x,y) ((x)>(y)?(x):(y))
46 //#define min(x,y) ((x)<(y)?(x):(y))
49 /** number of bits in a uint */
61 /** number of bits per uchar */
64 /** number of bytes per uint */
67 /** uchar = unsigned char */
69 #define uchar unsigned char
72 /** ushort = unsigned short */
74 #define ushort unsigned short
77 /** ulong = unsigned long */
79 #define ulong unsigned long
82 /** uint = unsigned int */
84 #define uint unsigned int
87 /** number of different uchar values 0..255 */
88 #define size_uchar 256
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,
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,
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,
128 /** bits needed to represent a number between 0 and n */
129 inline uint bits(uint n){
131 while (n) { b++; n >>= 1; }
135 /** reads bit p from e */
136 #define bitget(e,p) ((((e)[(p)/W] >> ((p)%W))) & 1)
138 /** sets bit p in e */
139 #define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W)))
141 /** cleans bit p in e */
142 #define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W)))
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));
150 /** Retrieve a given index from array A where every value uses len bits
152 * @param len Length in bits of each field
153 * @param index Position to be retrieved
155 inline uint get_field(uint *A, uint len, uint index) {
157 register uint i=index*len/W, j=index*len-W*i, result;
159 result = (A[i] << (W-j-len)) >> (W-len);
162 result = result | (A[i+1] << (WW-j-len)) >> (W-len);
167 /** Store a given value in index into array A where every value uses len bits
169 * @param len Length in bits of each field
170 * @param index Position to store in
171 * @param x Value to be stored
173 inline void set_field(uint *A, uint len, uint index, uint x) {
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;
180 mask = ((~0u) << (len+j-W));
181 A[i+1] = (A[i+1] & mask)| x >> (W-j);
185 /** Retrieve a given bitsequence from array A
187 * @param ini Starting position
188 * @param fin Retrieve until end-1
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);
195 result = (A[i] << (W-j-len)) >> (W-len);
198 result = result | (A[i+1] << (WW-j-len)) >> (W-len);
203 /** Stores a given bitsequence into array A
205 * @param ini Starting position
206 * @param fin Store until end-1
207 * @param x Value to be stored
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;
217 mask = ((~0u) << (len+j-W));
218 A[i+1] = (A[i+1] & mask)| x >> (W-j);
222 /** Retrieve a given index from array A where every value uses 4 bits
224 * @param index Position to be retrieved
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);
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];
239 uint m1 = 0x55555555;
240 uint m2 = 0x33333333;
241 uint m4 = 0x0f0f0f0f;
243 x = (x & m2) + ((x >> 2) & m2);
244 x = (x + (x >> 4)) & m4;
246 return (x + (x >> 16)) & 0x3f;
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];
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];
261 #endif /* _BASICS_H */