Branch data Line data Source code
1 : : #include<stdlib.h>
2 : : #include<stdio.h>
3 : : #include <assert.h>
4 : : #include <string.h>
5 : : #include <limits.h>
6 : : #include "select_lookup_tables.h"
7 : : #include "select.h"
8 : :
9 : : //#define DEBUG
10 : : #include "debug.h"
11 : :
12 : : #ifndef STEP_SELECT_TABLE
13 : : #define STEP_SELECT_TABLE 128
14 : : #endif
15 : :
16 : : #ifndef NBITS_STEP_SELECT_TABLE
17 : : #define NBITS_STEP_SELECT_TABLE 7
18 : : #endif
19 : :
20 : : #ifndef MASK_STEP_SELECT_TABLE
21 : : #define MASK_STEP_SELECT_TABLE 0x7f // 0x7f = 127
22 : : #endif
23 : :
24 : 0 : static inline void select_insert_0(cmph_uint32 * buffer)
25 : : {
26 : 0 : (*buffer) >>= 1;
27 : 0 : };
28 : :
29 : 0 : static inline void select_insert_1(cmph_uint32 * buffer)
30 : : {
31 : 0 : (*buffer) >>= 1;
32 : 0 : (*buffer) |= 0x80000000;
33 : 0 : };
34 : :
35 : 0 : void select_init(select_t * sel)
36 : : {
37 : 0 : sel->n = 0;
38 : 0 : sel->m = 0;
39 : 0 : sel->bits_vec = 0;
40 : 0 : sel->select_table = 0;
41 : 0 : };
42 : :
43 : 0 : cmph_uint32 select_get_space_usage(select_t * sel)
44 : : {
45 : : register cmph_uint32 nbits;
46 : : register cmph_uint32 vec_size;
47 : : register cmph_uint32 sel_table_size;
48 : : register cmph_uint32 space_usage;
49 : :
50 : 0 : nbits = sel->n + sel->m;
51 : 0 : vec_size = (nbits + 31) >> 5;
52 : 0 : sel_table_size = (sel->n >> NBITS_STEP_SELECT_TABLE) + 1; // (sel->n >> NBITS_STEP_SELECT_TABLE) = (sel->n/STEP_SELECT_TABLE)
53 : :
54 : 0 : space_usage = 2 * sizeof(cmph_uint32) * 8; // n and m
55 : 0 : space_usage += vec_size * (cmph_uint32) sizeof(cmph_uint32) * 8;
56 : 0 : space_usage += sel_table_size * (cmph_uint32)sizeof(cmph_uint32) * 8;
57 : 0 : return space_usage;
58 : : }
59 : :
60 : 0 : void select_destroy(select_t * sel)
61 : : {
62 : 0 : free(sel->bits_vec);
63 : 0 : free(sel->select_table);
64 : 0 : sel->bits_vec = 0;
65 : 0 : sel->select_table = 0;
66 : 0 : };
67 : :
68 : 0 : static inline void select_generate_sel_table(select_t * sel)
69 : : {
70 : 0 : register cmph_uint8 * bits_table = (cmph_uint8 *)sel->bits_vec;
71 : : register cmph_uint32 part_sum, old_part_sum;
72 : : register cmph_uint32 vec_idx, one_idx, sel_table_idx;
73 : :
74 : 0 : part_sum = vec_idx = one_idx = sel_table_idx = 0;
75 : :
76 : : for(;;)
77 : : {
78 : : // FABIANO: Should'n it be one_idx >= sel->n
79 : 0 : if(one_idx >= sel->n)
80 : 0 : break;
81 : : do
82 : : {
83 : 0 : old_part_sum = part_sum;
84 : 0 : part_sum += rank_lookup_table[bits_table[vec_idx]];
85 : 0 : vec_idx++;
86 : 0 : } while (part_sum <= one_idx);
87 : :
88 : 0 : sel->select_table[sel_table_idx] = select_lookup_table[bits_table[vec_idx - 1]][one_idx - old_part_sum] + ((vec_idx - 1) << 3); // ((vec_idx - 1) << 3) = ((vec_idx - 1) * 8)
89 : 0 : one_idx += STEP_SELECT_TABLE ;
90 : 0 : sel_table_idx++;
91 : : };
92 : 0 : };
93 : :
94 : 0 : void select_generate(select_t * sel, cmph_uint32 * keys_vec, cmph_uint32 n, cmph_uint32 m)
95 : : {
96 : : register cmph_uint32 i, j, idx;
97 : 0 : cmph_uint32 buffer = 0;
98 : :
99 : : register cmph_uint32 nbits;
100 : : register cmph_uint32 vec_size;
101 : : register cmph_uint32 sel_table_size;
102 : 0 : sel->n = n;
103 : 0 : sel->m = m; // n values in the range [0,m-1]
104 : :
105 : 0 : nbits = sel->n + sel->m;
106 : 0 : vec_size = (nbits + 31) >> 5; // (nbits + 31) >> 5 = (nbits + 31)/32
107 : :
108 : 0 : sel_table_size = (sel->n >> NBITS_STEP_SELECT_TABLE) + 1; // (sel->n >> NBITS_STEP_SELECT_TABLE) = (sel->n/STEP_SELECT_TABLE)
109 : :
110 : 0 : if(sel->bits_vec)
111 : : {
112 : 0 : free(sel->bits_vec);
113 : : }
114 : 0 : sel->bits_vec = (cmph_uint32 *)calloc(vec_size, sizeof(cmph_uint32));
115 : :
116 : 0 : if(sel->select_table)
117 : : {
118 : 0 : free(sel->select_table);
119 : : }
120 : 0 : sel->select_table = (cmph_uint32 *)calloc(sel_table_size, sizeof(cmph_uint32));
121 : :
122 : :
123 : :
124 : 0 : idx = i = j = 0;
125 : :
126 : : for(;;)
127 : : {
128 : 0 : while(keys_vec[j]==i)
129 : : {
130 : 0 : select_insert_1(&buffer);
131 : 0 : idx++;
132 : :
133 : 0 : if((idx & 0x1f) == 0 ) // (idx & 0x1f) = idx % 32
134 : 0 : sel->bits_vec[(idx >> 5) - 1] = buffer; // (idx >> 5) = idx/32
135 : 0 : j++;
136 : :
137 : 0 : if(j == sel->n)
138 : 0 : goto loop_end;
139 : :
140 : : //assert(keys_vec[j] < keys_vec[j-1]);
141 : : }
142 : :
143 : 0 : if(i == sel->m)
144 : 0 : break;
145 : :
146 : 0 : while(keys_vec[j] > i)
147 : : {
148 : 0 : select_insert_0(&buffer);
149 : 0 : idx++;
150 : :
151 : 0 : if((idx & 0x1f) == 0 ) // (idx & 0x1f) = idx % 32
152 : 0 : sel->bits_vec[(idx >> 5) - 1] = buffer; // (idx >> 5) = idx/32
153 : 0 : i++;
154 : : };
155 : :
156 : : };
157 : 0 : loop_end:
158 : 0 : if((idx & 0x1f) != 0 ) // (idx & 0x1f) = idx % 32
159 : : {
160 : 0 : buffer >>= 32 - (idx & 0x1f);
161 : 0 : sel->bits_vec[ (idx - 1) >> 5 ] = buffer;
162 : : };
163 : :
164 : 0 : select_generate_sel_table(sel);
165 : 0 : };
166 : :
167 : 0 : static inline cmph_uint32 _select_query(cmph_uint8 * bits_table, cmph_uint32 * select_table, cmph_uint32 one_idx)
168 : : {
169 : : register cmph_uint32 vec_bit_idx ,vec_byte_idx;
170 : : register cmph_uint32 part_sum, old_part_sum;
171 : :
172 : 0 : vec_bit_idx = select_table[one_idx >> NBITS_STEP_SELECT_TABLE]; // one_idx >> NBITS_STEP_SELECT_TABLE = one_idx/STEP_SELECT_TABLE
173 : 0 : vec_byte_idx = vec_bit_idx >> 3; // vec_bit_idx / 8
174 : :
175 : 0 : one_idx &= MASK_STEP_SELECT_TABLE; // one_idx %= STEP_SELECT_TABLE == one_idx &= MASK_STEP_SELECT_TABLE
176 : 0 : one_idx += rank_lookup_table[bits_table[vec_byte_idx] & ((1 << (vec_bit_idx & 0x7)) - 1)];
177 : 0 : part_sum = 0;
178 : :
179 : : do
180 : : {
181 : 0 : old_part_sum = part_sum;
182 : 0 : part_sum += rank_lookup_table[bits_table[vec_byte_idx]];
183 : 0 : vec_byte_idx++;
184 : :
185 : 0 : }while (part_sum <= one_idx);
186 : :
187 : 0 : return select_lookup_table[bits_table[vec_byte_idx - 1]][one_idx - old_part_sum] + ((vec_byte_idx-1) << 3);
188 : : }
189 : :
190 : 0 : cmph_uint32 select_query(select_t * sel, cmph_uint32 one_idx)
191 : : {
192 : 0 : return _select_query((cmph_uint8 *)sel->bits_vec, sel->select_table, one_idx);
193 : : };
194 : :
195 : :
196 : 0 : static inline cmph_uint32 _select_next_query(cmph_uint8 * bits_table, cmph_uint32 vec_bit_idx)
197 : : {
198 : : register cmph_uint32 vec_byte_idx, one_idx;
199 : : register cmph_uint32 part_sum, old_part_sum;
200 : :
201 : 0 : vec_byte_idx = vec_bit_idx >> 3;
202 : :
203 : 0 : one_idx = rank_lookup_table[bits_table[vec_byte_idx] & ((1U << (vec_bit_idx & 0x7)) - 1U)] + 1U;
204 : 0 : part_sum = 0;
205 : :
206 : : do
207 : : {
208 : 0 : old_part_sum = part_sum;
209 : 0 : part_sum += rank_lookup_table[bits_table[vec_byte_idx]];
210 : 0 : vec_byte_idx++;
211 : :
212 : 0 : }while (part_sum <= one_idx);
213 : :
214 : 0 : return select_lookup_table[bits_table[(vec_byte_idx - 1)]][(one_idx - old_part_sum)] + ((vec_byte_idx - 1) << 3);
215 : : }
216 : :
217 : 0 : cmph_uint32 select_next_query(select_t * sel, cmph_uint32 vec_bit_idx)
218 : : {
219 : 0 : return _select_next_query((cmph_uint8 *)sel->bits_vec, vec_bit_idx);
220 : : };
221 : :
222 : 0 : void select_dump(select_t *sel, char **buf, cmph_uint32 *buflen)
223 : : {
224 : 0 : register cmph_uint32 nbits = sel->n + sel->m;
225 : 0 : register cmph_uint32 vec_size = ((nbits + 31) >> 5) * (cmph_uint32)sizeof(cmph_uint32); // (nbits + 31) >> 5 = (nbits + 31)/32
226 : 0 : register cmph_uint32 sel_table_size = ((sel->n >> NBITS_STEP_SELECT_TABLE) + 1) * (cmph_uint32)sizeof(cmph_uint32); // (sel->n >> NBITS_STEP_SELECT_TABLE) = (sel->n/STEP_SELECT_TABLE)
227 : 0 : register cmph_uint32 pos = 0;
228 : :
229 : 0 : *buflen = 2*(cmph_uint32)sizeof(cmph_uint32) + vec_size + sel_table_size;
230 : :
231 : 0 : *buf = (char *)calloc(*buflen, sizeof(char));
232 : :
233 : 0 : if (!*buf)
234 : : {
235 : 0 : *buflen = UINT_MAX;
236 : 0 : return;
237 : : }
238 : :
239 : 0 : memcpy(*buf, &(sel->n), sizeof(cmph_uint32));
240 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
241 : 0 : memcpy(*buf + pos, &(sel->m), sizeof(cmph_uint32));
242 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
243 : 0 : memcpy(*buf + pos, sel->bits_vec, vec_size);
244 : 0 : pos += vec_size;
245 : 0 : memcpy(*buf + pos, sel->select_table, sel_table_size);
246 : :
247 : : DEBUGP("Dumped select structure with size %u bytes\n", *buflen);
248 : : }
249 : :
250 : 0 : void select_load(select_t * sel, const char *buf, cmph_uint32 buflen)
251 : : {
252 : 0 : register cmph_uint32 pos = 0;
253 : 0 : register cmph_uint32 nbits = 0;
254 : 0 : register cmph_uint32 vec_size = 0;
255 : 0 : register cmph_uint32 sel_table_size = 0;
256 : :
257 : 0 : memcpy(&(sel->n), buf, sizeof(cmph_uint32));
258 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
259 : 0 : memcpy(&(sel->m), buf + pos, sizeof(cmph_uint32));
260 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
261 : :
262 : 0 : nbits = sel->n + sel->m;
263 : 0 : vec_size = ((nbits + 31) >> 5) * (cmph_uint32)sizeof(cmph_uint32); // (nbits + 31) >> 5 = (nbits + 31)/32
264 : 0 : sel_table_size = ((sel->n >> NBITS_STEP_SELECT_TABLE) + 1) * (cmph_uint32)sizeof(cmph_uint32); // (sel->n >> NBITS_STEP_SELECT_TABLE) = (sel->n/STEP_SELECT_TABLE)
265 : :
266 : 0 : if(sel->bits_vec)
267 : : {
268 : 0 : free(sel->bits_vec);
269 : : }
270 : 0 : sel->bits_vec = (cmph_uint32 *)calloc(vec_size/sizeof(cmph_uint32), sizeof(cmph_uint32));
271 : :
272 : 0 : if(sel->select_table)
273 : : {
274 : 0 : free(sel->select_table);
275 : : }
276 : 0 : sel->select_table = (cmph_uint32 *)calloc(sel_table_size/sizeof(cmph_uint32), sizeof(cmph_uint32));
277 : :
278 : 0 : memcpy(sel->bits_vec, buf + pos, vec_size);
279 : 0 : pos += vec_size;
280 : 0 : memcpy(sel->select_table, buf + pos, sel_table_size);
281 : :
282 : : DEBUGP("Loaded select structure with size %u bytes\n", buflen);
283 : 0 : }
284 : :
285 : :
286 : : /** \fn void select_pack(select_t *sel, void *sel_packed);
287 : : * \brief Support the ability to pack a select structure function into a preallocated contiguous memory space pointed by sel_packed.
288 : : * \param sel points to the select structure
289 : : * \param sel_packed pointer to the contiguous memory area used to store the select structure. The size of sel_packed must be at least @see select_packed_size
290 : : */
291 : 0 : void select_pack(select_t *sel, void *sel_packed)
292 : : {
293 : 0 : if (sel && sel_packed)
294 : : {
295 : 0 : char *buf = NULL;
296 : 0 : cmph_uint32 buflen = 0;
297 : 0 : select_dump(sel, &buf, &buflen);
298 : 0 : memcpy(sel_packed, buf, buflen);
299 : 0 : free(buf);
300 : : }
301 : 0 : }
302 : :
303 : :
304 : : /** \fn cmph_uint32 select_packed_size(select_t *sel);
305 : : * \brief Return the amount of space needed to pack a select structure.
306 : : * \return the size of the packed select structure or zero for failures
307 : : */
308 : 0 : cmph_uint32 select_packed_size(select_t *sel)
309 : : {
310 : 0 : register cmph_uint32 nbits = sel->n + sel->m;
311 : 0 : register cmph_uint32 vec_size = ((nbits + 31) >> 5) * (cmph_uint32)sizeof(cmph_uint32); // (nbits + 31) >> 5 = (nbits + 31)/32
312 : 0 : register cmph_uint32 sel_table_size = ((sel->n >> NBITS_STEP_SELECT_TABLE) + 1) * (cmph_uint32)sizeof(cmph_uint32); // (sel->n >> NBITS_STEP_SELECT_TABLE) = (sel->n/STEP_SELECT_TABLE)
313 : 0 : return 2*(cmph_uint32)sizeof(cmph_uint32) + vec_size + sel_table_size;
314 : : }
315 : :
316 : :
317 : :
318 : 0 : cmph_uint32 select_query_packed(void * sel_packed, cmph_uint32 one_idx)
319 : : {
320 : 0 : register cmph_uint32 *ptr = (cmph_uint32 *)sel_packed;
321 : 0 : register cmph_uint32 n = *ptr++;
322 : 0 : register cmph_uint32 m = *ptr++;
323 : 0 : register cmph_uint32 nbits = n + m;
324 : 0 : register cmph_uint32 vec_size = (nbits + 31) >> 5; // (nbits + 31) >> 5 = (nbits + 31)/32
325 : 0 : register cmph_uint8 * bits_vec = (cmph_uint8 *)ptr;
326 : 0 : register cmph_uint32 * select_table = ptr + vec_size;
327 : :
328 : 0 : return _select_query(bits_vec, select_table, one_idx);
329 : : }
330 : :
331 : :
332 : 0 : cmph_uint32 select_next_query_packed(void * sel_packed, cmph_uint32 vec_bit_idx)
333 : : {
334 : 0 : register cmph_uint8 * bits_vec = (cmph_uint8 *)sel_packed;
335 : 0 : bits_vec += 8; // skipping n and m
336 : 0 : return _select_next_query(bits_vec, vec_bit_idx);
337 : : }
|
