2 * Copyright (C) 2008, Rodrigo Gonzalez & Francisco Claude, 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
32 /** mask for obtaining the first 5 bits */
33 #define mask31 0x0000001F
36 #define max(x,y) ((x)>(y)?(x):(y))
38 #define min(x,y) ((x)<(y)?(x):(y))
41 /** number of bits in a uint */
50 /** number of bits per uchar */
53 /** number of bytes per uint */
56 /** uchar = unsigned char */
58 #define uchar unsigned char
61 /** ushort = unsigned short */
63 #define ushort unsigned short
66 /** ulong = unsigned long */
68 #define ulong unsigned long
71 /** uint = unsigned int */
73 #define uint unsigned int
76 /** number of different uchar values 0..255 */
77 #define size_uchar 256
79 /** popcount array for uchars */
80 const unsigned char __popcount_tab[] = {
81 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,
82 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,
83 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,
84 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,
85 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,
86 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,
87 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,
88 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,
91 /** select array for uchars */
92 const unsigned char select_tab[] = {
93 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,
94 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,
95 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,
96 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,
97 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,
98 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,
99 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,
100 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 /** prev array for uchars */
104 const unsigned char prev_tab[] = {
105 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,
106 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,
107 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,
108 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,
109 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
110 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
111 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
112 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
117 /** bits needed to represent a number between 0 and n */
118 inline uint bits(uint n){
120 while (n) { b++; n >>= 1; }
124 /** reads bit p from e */
125 #define bitget(e,p) ((((e)[(p)/W] >> ((p)%W))) & 1)
127 /** sets bit p in e */
128 #define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W)))
130 /** cleans bit p in e */
131 #define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W)))
133 /** uints required to represent e integers of n bits each */
134 #define uint_len(e,n) (((e)*(n))/W+(((e)*(n))%W > 0))
136 /** Retrieve a given index from array A where every value uses len bits
138 * @param len Length in bits of each field
139 * @param index Position to be retrieved
141 inline uint get_field(uint *A, uint len, uint index) {
143 register uint i=index*len/W, j=index*len-W*i, result;
145 result = (A[i] << (W-j-len)) >> (W-len);
148 result = result | (A[i+1] << (WW-j-len)) >> (W-len);
153 /** Store a given value in index into array A where every value uses len bits
155 * @param len Length in bits of each field
156 * @param index Position to store in
157 * @param x Value to be stored
159 inline void set_field(uint *A, uint len, uint index, uint x) {
161 uint i=index*len/W, j=index*len-i*W;
162 uint mask = ((j+len) < W ? ~0u << (j+len) : 0)
163 | ((W-j) < W ? ~0u >> (W-j) : 0);
164 A[i] = (A[i] & mask) | x << j;
166 mask = ((~0u) << (len+j-W));
167 A[i+1] = (A[i+1] & mask)| x >> (W-j);
171 /** Retrieve a given bitsequence from array A
173 * @param ini Starting position
174 * @param fin Retrieve until end-1
176 inline uint get_var_field(uint *A, uint ini, uint fin) {
177 if(ini==fin+1) return 0;
178 uint i=ini/W, j=ini-W*i, result;
179 uint len = (fin-ini+1);
181 result = (A[i] << (W-j-len)) >> (W-len);
184 result = result | (A[i+1] << (WW-j-len)) >> (W-len);
189 /** Stores a given bitsequence into array A
191 * @param ini Starting position
192 * @param fin Store until end-1
193 * @param x Value to be stored
195 inline void set_var_field(uint *A, uint ini, uint fin, uint x) {
196 if(ini==fin+1) return;
197 uint i=ini/W, j=ini-i*W;
198 uint len = (fin-ini+1);
199 uint mask = ((j+len) < W ? ~0u << (j+len) : 0)
200 | ((W-j) < W ? ~0u >> (W-j) : 0);
201 A[i] = (A[i] & mask) | x << j;
203 mask = ((~0u) << (len+j-W));
204 A[i+1] = (A[i+1] & mask)| x >> (W-j);
208 /** Retrieve a given index from array A where every value uses 4 bits
210 * @param index Position to be retrieved
212 inline uint get_field4(uint *A, uint index) {
213 unsigned i=index/8, j=(index&0x7)<<2;
214 return (A[i] << (28-j)) >> (28);
217 /** Counts the number of 1s in x */
218 inline uint popcount(int x){
219 return __popcount_tab[(x >> 0) & 0xff] + __popcount_tab[(x >> 8) & 0xff]
220 + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff];
223 /** Counts the number of 1s in the first 16 bits of x */
224 inline uint popcount16(int x){
225 return __popcount_tab[x & 0xff] + __popcount_tab[(x >> 8) & 0xff];
228 /** Counts the number of 1s in the first 8 bits of x */
229 inline uint popcount8(int x){
230 return __popcount_tab[x & 0xff];
233 #endif /* _BASICS_H */