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 static inline void select_insert_0(cmph_uint32 * buffer)
25 {
26 (*buffer) >>= 1;
27 };
28
29 static inline void select_insert_1(cmph_uint32 * buffer)
30 {
31 (*buffer) >>= 1;
32 (*buffer) |= 0x80000000;
33 };
34
35 void select_init(select_t * sel)
36 {
37 sel->n = 0;
38 sel->m = 0;
39 sel->bits_vec = 0;
40 sel->select_table = 0;
41 };
42
43 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 nbits = sel->n + sel->m;
51 vec_size = (nbits + 31) >> 5;
52 sel_table_size = (sel->n >> NBITS_STEP_SELECT_TABLE) + 1; // (sel->n >> NBITS_STEP_SELECT_TABLE) = (sel->n/STEP_SELECT_TABLE)
53
54 space_usage = 2 * sizeof(cmph_uint32) * 8; // n and m
55 space_usage += vec_size * (cmph_uint32) sizeof(cmph_uint32) * 8;
56 space_usage += sel_table_size * (cmph_uint32)sizeof(cmph_uint32) * 8;
57 return space_usage;
58 }
59
60 void select_destroy(select_t * sel)
61 {
62 free(sel->bits_vec);
63 free(sel->select_table);
64 sel->bits_vec = 0;
65 sel->select_table = 0;
66 };
67
68 static inline void select_generate_sel_table(select_t * sel)
69 {
70 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 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 if(one_idx >= sel->n)
80 break;
81 do
82 {
83 old_part_sum = part_sum;
84 part_sum += rank_lookup_table[bits_table[vec_idx]];
85 vec_idx++;
86 } while (part_sum <= one_idx);
87
88 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 one_idx += STEP_SELECT_TABLE ;
90 sel_table_idx++;
91 };
92 };
93
94 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 cmph_uint32 buffer = 0;
98
99 register cmph_uint32 nbits;
100 register cmph_uint32 vec_size;
101 register cmph_uint32 sel_table_size;
102 sel->n = n;
103 sel->m = m; // n values in the range [0,m-1]
104
105 nbits = sel->n + sel->m;
106 vec_size = (nbits + 31) >> 5; // (nbits + 31) >> 5 = (nbits + 31)/32
107
108 sel_table_size = (sel->n >> NBITS_STEP_SELECT_TABLE) + 1; // (sel->n >> NBITS_STEP_SELECT_TABLE) = (sel->n/STEP_SELECT_TABLE)
109
110 if(sel->bits_vec)
111 {
112 free(sel->bits_vec);
113 }
114 sel->bits_vec = (cmph_uint32 *)calloc(vec_size, sizeof(cmph_uint32));
115
116 if(sel->select_table)
117 {
118 free(sel->select_table);
119 }
120 sel->select_table = (cmph_uint32 *)calloc(sel_table_size, sizeof(cmph_uint32));
121
122
123
124 idx = i = j = 0;
125
126 for(;;)
127 {
128 while(keys_vec[j]==i)
129 {
130 select_insert_1(&buffer);
131 idx++;
132
133 if((idx & 0x1f) == 0 ) // (idx & 0x1f) = idx % 32
134 sel->bits_vec[(idx >> 5) - 1] = buffer; // (idx >> 5) = idx/32
135 j++;
136
137 if(j == sel->n)
138 goto loop_end;
139
140 //assert(keys_vec[j] < keys_vec[j-1]);
141 }
142
143 if(i == sel->m)
144 break;
145
146 while(keys_vec[j] > i)
147 {
148 select_insert_0(&buffer);
149 idx++;
150
151 if((idx & 0x1f) == 0 ) // (idx & 0x1f) = idx % 32
152 sel->bits_vec[(idx >> 5) - 1] = buffer; // (idx >> 5) = idx/32
153 i++;
154 };
155
156 };
157 loop_end:
158 if((idx & 0x1f) != 0 ) // (idx & 0x1f) = idx % 32
159 {
160 buffer >>= 32 - (idx & 0x1f);
161 sel->bits_vec[ (idx - 1) >> 5 ] = buffer;
162 };
163
164 select_generate_sel_table(sel);
165 };
166
167 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 vec_bit_idx = select_table[one_idx >> NBITS_STEP_SELECT_TABLE]; // one_idx >> NBITS_STEP_SELECT_TABLE = one_idx/STEP_SELECT_TABLE
173 vec_byte_idx = vec_bit_idx >> 3; // vec_bit_idx / 8
174
175 one_idx &= MASK_STEP_SELECT_TABLE; // one_idx %= STEP_SELECT_TABLE == one_idx &= MASK_STEP_SELECT_TABLE
176 one_idx += rank_lookup_table[bits_table[vec_byte_idx] & ((1 << (vec_bit_idx & 0x7)) - 1)];
177 part_sum = 0;
178
179 do
180 {
181 old_part_sum = part_sum;
182 part_sum += rank_lookup_table[bits_table[vec_byte_idx]];
183 vec_byte_idx++;
184
185 }while (part_sum <= one_idx);
186
187 return select_lookup_table[bits_table[vec_byte_idx - 1]][one_idx - old_part_sum] + ((vec_byte_idx-1) << 3);
188 }
189
190 cmph_uint32 select_query(select_t * sel, cmph_uint32 one_idx)
191 {
192 return _select_query((cmph_uint8 *)sel->bits_vec, sel->select_table, one_idx);
193 };
194
195
196 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 vec_byte_idx = vec_bit_idx >> 3;
202
203 one_idx = rank_lookup_table[bits_table[vec_byte_idx] & ((1U << (vec_bit_idx & 0x7)) - 1U)] + 1U;
204 part_sum = 0;
205
206 do
207 {
208 old_part_sum = part_sum;
209 part_sum += rank_lookup_table[bits_table[vec_byte_idx]];
210 vec_byte_idx++;
211
212 }while (part_sum <= one_idx);
213
214 return select_lookup_table[bits_table[(vec_byte_idx - 1)]][(one_idx - old_part_sum)] + ((vec_byte_idx - 1) << 3);
215 }
216
217 cmph_uint32 select_next_query(select_t * sel, cmph_uint32 vec_bit_idx)
218 {
219 return _select_next_query((cmph_uint8 *)sel->bits_vec, vec_bit_idx);
220 };
221
222 void select_dump(select_t *sel, char **buf, cmph_uint32 *buflen)
223 {
224 register cmph_uint32 nbits = sel->n + sel->m;
225 register cmph_uint32 vec_size = ((nbits + 31) >> 5) * (cmph_uint32)sizeof(cmph_uint32); // (nbits + 31) >> 5 = (nbits + 31)/32
226 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 register cmph_uint32 pos = 0;
228
229 *buflen = 2*(cmph_uint32)sizeof(cmph_uint32) + vec_size + sel_table_size;
230
231 *buf = (char *)calloc(*buflen, sizeof(char));
232
233 if (!*buf)
234 {
235 *buflen = UINT_MAX;
236 return;
237 }
238
239 memcpy(*buf, &(sel->n), sizeof(cmph_uint32));
240 pos += (cmph_uint32)sizeof(cmph_uint32);
241 memcpy(*buf + pos, &(sel->m), sizeof(cmph_uint32));
242 pos += (cmph_uint32)sizeof(cmph_uint32);
243 memcpy(*buf + pos, sel->bits_vec, vec_size);
244 pos += vec_size;
245 memcpy(*buf + pos, sel->select_table, sel_table_size);
246
247 DEBUGP("Dumped select structure with size %u bytes\n", *buflen);
248 }
249
250 void select_load(select_t * sel, const char *buf, cmph_uint32 buflen)
251 {
252 register cmph_uint32 pos = 0;
253 register cmph_uint32 nbits = 0;
254 register cmph_uint32 vec_size = 0;
255 register cmph_uint32 sel_table_size = 0;
256
257 memcpy(&(sel->n), buf, sizeof(cmph_uint32));
258 pos += (cmph_uint32)sizeof(cmph_uint32);
259 memcpy(&(sel->m), buf + pos, sizeof(cmph_uint32));
260 pos += (cmph_uint32)sizeof(cmph_uint32);
261
262 nbits = sel->n + sel->m;
263 vec_size = ((nbits + 31) >> 5) * (cmph_uint32)sizeof(cmph_uint32); // (nbits + 31) >> 5 = (nbits + 31)/32
264 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 if(sel->bits_vec)
267 {
268 free(sel->bits_vec);
269 }
270 sel->bits_vec = (cmph_uint32 *)calloc(vec_size/sizeof(cmph_uint32), sizeof(cmph_uint32));
271
272 if(sel->select_table)
273 {
274 free(sel->select_table);
275 }
276 sel->select_table = (cmph_uint32 *)calloc(sel_table_size/sizeof(cmph_uint32), sizeof(cmph_uint32));
277
278 memcpy(sel->bits_vec, buf + pos, vec_size);
279 pos += vec_size;
280 memcpy(sel->select_table, buf + pos, sel_table_size);
281
282 DEBUGP("Loaded select structure with size %u bytes\n", buflen);
283 }
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 void select_pack(select_t *sel, void *sel_packed)
292 {
293 if (sel && sel_packed)
294 {
295 char *buf = NULL;
296 cmph_uint32 buflen = 0;
297 select_dump(sel, &buf, &buflen);
298 memcpy(sel_packed, buf, buflen);
299 free(buf);
300 }
301 }
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 cmph_uint32 select_packed_size(select_t *sel)
309 {
310 register cmph_uint32 nbits = sel->n + sel->m;
311 register cmph_uint32 vec_size = ((nbits + 31) >> 5) * (cmph_uint32)sizeof(cmph_uint32); // (nbits + 31) >> 5 = (nbits + 31)/32
312 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 return 2*(cmph_uint32)sizeof(cmph_uint32) + vec_size + sel_table_size;
314 }
315
316
317
318 cmph_uint32 select_query_packed(void * sel_packed, cmph_uint32 one_idx)
319 {
320 register cmph_uint32 *ptr = (cmph_uint32 *)sel_packed;
321 register cmph_uint32 n = *ptr++;
322 register cmph_uint32 m = *ptr++;
323 register cmph_uint32 nbits = n + m;
324 register cmph_uint32 vec_size = (nbits + 31) >> 5; // (nbits + 31) >> 5 = (nbits + 31)/32
325 register cmph_uint8 * bits_vec = (cmph_uint8 *)ptr;
326 register cmph_uint32 * select_table = ptr + vec_size;
327
328 return _select_query(bits_vec, select_table, one_idx);
329 }
330
331
332 cmph_uint32 select_next_query_packed(void * sel_packed, cmph_uint32 vec_bit_idx)
333 {
334 register cmph_uint8 * bits_vec = (cmph_uint8 *)sel_packed;
335 bits_vec += 8; // skipping n and m
336 return _select_next_query(bits_vec, vec_bit_idx);
337 }