Branch data Line data Source code
1 : : #include<stdlib.h>
2 : : #include<stdio.h>
3 : : #include<limits.h>
4 : : #include<string.h>
5 : : #include"compressed_rank.h"
6 : : #include"bitbool.h"
7 : : // #define DEBUG
8 : : #include"debug.h"
9 : 0 : static inline cmph_uint32 compressed_rank_i_log2(cmph_uint32 x)
10 : : {
11 : 0 : register cmph_uint32 res = 0;
12 : :
13 : 0 : while(x > 1)
14 : : {
15 : 0 : x >>= 1;
16 : 0 : res++;
17 : : }
18 : 0 : return res;
19 : : };
20 : :
21 : 0 : void compressed_rank_init(compressed_rank_t * cr)
22 : : {
23 : 0 : cr->max_val = 0;
24 : 0 : cr->n = 0;
25 : 0 : cr->rem_r = 0;
26 : 0 : select_init(&cr->sel);
27 : 0 : cr->vals_rems = 0;
28 : 0 : }
29 : :
30 : 0 : void compressed_rank_destroy(compressed_rank_t * cr)
31 : : {
32 : 0 : free(cr->vals_rems);
33 : 0 : cr->vals_rems = 0;
34 : 0 : select_destroy(&cr->sel);
35 : 0 : }
36 : :
37 : 0 : void compressed_rank_generate(compressed_rank_t * cr, cmph_uint32 * vals_table, cmph_uint32 n)
38 : : {
39 : : register cmph_uint32 i,j;
40 : : register cmph_uint32 rems_mask;
41 : 0 : register cmph_uint32 * select_vec = 0;
42 : 0 : cr->n = n;
43 : 0 : cr->max_val = vals_table[cr->n - 1];
44 : 0 : cr->rem_r = compressed_rank_i_log2(cr->max_val/cr->n);
45 : 0 : if(cr->rem_r == 0)
46 : : {
47 : 0 : cr->rem_r = 1;
48 : : }
49 : 0 : select_vec = (cmph_uint32 *) calloc(cr->max_val >> cr->rem_r, sizeof(cmph_uint32));
50 : 0 : cr->vals_rems = (cmph_uint32 *) calloc(BITS_TABLE_SIZE(cr->n, cr->rem_r), sizeof(cmph_uint32));
51 : 0 : rems_mask = (1U << cr->rem_r) - 1U;
52 : :
53 : 0 : for(i = 0; i < cr->n; i++)
54 : : {
55 : 0 : set_bits_value(cr->vals_rems, i, vals_table[i] & rems_mask, cr->rem_r, rems_mask);
56 : : }
57 : :
58 : 0 : for(i = 1, j = 0; i <= cr->max_val >> cr->rem_r; i++)
59 : : {
60 : 0 : while(i > (vals_table[j] >> cr->rem_r))
61 : : {
62 : 0 : j++;
63 : : }
64 : 0 : select_vec[i - 1] = j;
65 : : };
66 : :
67 : :
68 : : // FABIANO: before it was (cr->total_length >> cr->rem_r) + 1. But I wiped out the + 1 because
69 : : // I changed the select structure to work up to m, instead of up to m - 1.
70 : 0 : select_generate(&cr->sel, select_vec, cr->max_val >> cr->rem_r, cr->n);
71 : :
72 : 0 : free(select_vec);
73 : 0 : }
74 : :
75 : 0 : cmph_uint32 compressed_rank_query(compressed_rank_t * cr, cmph_uint32 idx)
76 : : {
77 : : register cmph_uint32 rems_mask;
78 : : register cmph_uint32 val_quot, val_rem;
79 : : register cmph_uint32 sel_res, rank;
80 : :
81 : 0 : if(idx > cr->max_val)
82 : : {
83 : 0 : return cr->n;
84 : : }
85 : :
86 : 0 : val_quot = idx >> cr->rem_r;
87 : 0 : rems_mask = (1U << cr->rem_r) - 1U;
88 : 0 : val_rem = idx & rems_mask;
89 : 0 : if(val_quot == 0)
90 : : {
91 : 0 : rank = sel_res = 0;
92 : : }
93 : : else
94 : : {
95 : 0 : sel_res = select_query(&cr->sel, val_quot - 1) + 1;
96 : 0 : rank = sel_res - val_quot;
97 : : }
98 : :
99 : : do
100 : : {
101 : 0 : if(GETBIT32(cr->sel.bits_vec, sel_res))
102 : : {
103 : 0 : break;
104 : : }
105 : 0 : if(get_bits_value(cr->vals_rems, rank, cr->rem_r, rems_mask) >= val_rem)
106 : : {
107 : 0 : break;
108 : : }
109 : 0 : sel_res++;
110 : 0 : rank++;
111 : : } while(1);
112 : :
113 : 0 : return rank;
114 : : }
115 : :
116 : 0 : cmph_uint32 compressed_rank_get_space_usage(compressed_rank_t * cr)
117 : : {
118 : 0 : register cmph_uint32 space_usage = select_get_space_usage(&cr->sel);
119 : 0 : space_usage += BITS_TABLE_SIZE(cr->n, cr->rem_r)*(cmph_uint32)sizeof(cmph_uint32)*8;
120 : 0 : space_usage += 3*(cmph_uint32)sizeof(cmph_uint32)*8;
121 : 0 : return space_usage;
122 : : }
123 : :
124 : 0 : void compressed_rank_dump(compressed_rank_t * cr, char **buf, cmph_uint32 *buflen)
125 : : {
126 : 0 : register cmph_uint32 sel_size = select_packed_size(&(cr->sel));
127 : 0 : register cmph_uint32 vals_rems_size = BITS_TABLE_SIZE(cr->n, cr->rem_r) * (cmph_uint32)sizeof(cmph_uint32);
128 : 0 : register cmph_uint32 pos = 0;
129 : 0 : char * buf_sel = 0;
130 : 0 : cmph_uint32 buflen_sel = 0;
131 : : #ifdef DEBUG
132 : : cmph_uint32 i;
133 : : #endif
134 : :
135 : 0 : *buflen = 4*(cmph_uint32)sizeof(cmph_uint32) + sel_size + vals_rems_size;
136 : :
137 : : DEBUGP("sel_size = %u\n", sel_size);
138 : : DEBUGP("vals_rems_size = %u\n", vals_rems_size);
139 : :
140 : 0 : *buf = (char *)calloc(*buflen, sizeof(char));
141 : :
142 : 0 : if (!*buf)
143 : : {
144 : 0 : *buflen = UINT_MAX;
145 : 0 : return;
146 : : }
147 : :
148 : : // dumping max_val, n and rem_r
149 : 0 : memcpy(*buf, &(cr->max_val), sizeof(cmph_uint32));
150 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
151 : : DEBUGP("max_val = %u\n", cr->max_val);
152 : :
153 : 0 : memcpy(*buf + pos, &(cr->n), sizeof(cmph_uint32));
154 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
155 : : DEBUGP("n = %u\n", cr->n);
156 : :
157 : 0 : memcpy(*buf + pos, &(cr->rem_r), sizeof(cmph_uint32));
158 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
159 : : DEBUGP("rem_r = %u\n", cr->rem_r);
160 : :
161 : : // dumping sel
162 : 0 : select_dump(&cr->sel, &buf_sel, &buflen_sel);
163 : 0 : memcpy(*buf + pos, &buflen_sel, sizeof(cmph_uint32));
164 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
165 : : DEBUGP("buflen_sel = %u\n", buflen_sel);
166 : :
167 : 0 : memcpy(*buf + pos, buf_sel, buflen_sel);
168 : :
169 : : #ifdef DEBUG
170 : : i = 0;
171 : : for(i = 0; i < buflen_sel; i++)
172 : : {
173 : : DEBUGP("pos = %u -- buf_sel[%u] = %u\n", pos, i, *(*buf + pos + i));
174 : : }
175 : : #endif
176 : 0 : pos += buflen_sel;
177 : :
178 : 0 : free(buf_sel);
179 : :
180 : : // dumping vals_rems
181 : 0 : memcpy(*buf + pos, cr->vals_rems, vals_rems_size);
182 : : #ifdef DEBUG
183 : : for(i = 0; i < vals_rems_size; i++)
184 : : {
185 : : DEBUGP("pos = %u -- vals_rems_size = %u -- vals_rems[%u] = %u\n", pos, vals_rems_size, i, *(*buf + pos + i));
186 : : }
187 : : #endif
188 : 0 : pos += vals_rems_size;
189 : :
190 : : DEBUGP("Dumped compressed rank structure with size %u bytes\n", *buflen);
191 : : }
192 : :
193 : 0 : void compressed_rank_load(compressed_rank_t * cr, const char *buf, cmph_uint32 buflen)
194 : : {
195 : 0 : register cmph_uint32 pos = 0;
196 : 0 : cmph_uint32 buflen_sel = 0;
197 : 0 : register cmph_uint32 vals_rems_size = 0;
198 : : #ifdef DEBUG
199 : : cmph_uint32 i;
200 : : #endif
201 : :
202 : : // loading max_val, n, and rem_r
203 : 0 : memcpy(&(cr->max_val), buf, sizeof(cmph_uint32));
204 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
205 : : DEBUGP("max_val = %u\n", cr->max_val);
206 : :
207 : 0 : memcpy(&(cr->n), buf + pos, sizeof(cmph_uint32));
208 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
209 : : DEBUGP("n = %u\n", cr->n);
210 : :
211 : 0 : memcpy(&(cr->rem_r), buf + pos, sizeof(cmph_uint32));
212 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
213 : : DEBUGP("rem_r = %u\n", cr->rem_r);
214 : :
215 : : // loading sel
216 : 0 : memcpy(&buflen_sel, buf + pos, sizeof(cmph_uint32));
217 : 0 : pos += (cmph_uint32)sizeof(cmph_uint32);
218 : : DEBUGP("buflen_sel = %u\n", buflen_sel);
219 : :
220 : 0 : select_load(&cr->sel, buf + pos, buflen_sel);
221 : : #ifdef DEBUG
222 : : i = 0;
223 : : for(i = 0; i < buflen_sel; i++)
224 : : {
225 : : DEBUGP("pos = %u -- buf_sel[%u] = %u\n", pos, i, *(buf + pos + i));
226 : : }
227 : : #endif
228 : 0 : pos += buflen_sel;
229 : :
230 : : // loading vals_rems
231 : 0 : if(cr->vals_rems)
232 : : {
233 : 0 : free(cr->vals_rems);
234 : : }
235 : 0 : vals_rems_size = BITS_TABLE_SIZE(cr->n, cr->rem_r);
236 : 0 : cr->vals_rems = (cmph_uint32 *) calloc(vals_rems_size, sizeof(cmph_uint32));
237 : 0 : vals_rems_size *= 4;
238 : 0 : memcpy(cr->vals_rems, buf + pos, vals_rems_size);
239 : :
240 : : #ifdef DEBUG
241 : : for(i = 0; i < vals_rems_size; i++)
242 : : {
243 : : DEBUGP("pos = %u -- vals_rems_size = %u -- vals_rems[%u] = %u\n", pos, vals_rems_size, i, *(buf + pos + i));
244 : : }
245 : : #endif
246 : 0 : pos += vals_rems_size;
247 : :
248 : : DEBUGP("Loaded compressed rank structure with size %u bytes\n", buflen);
249 : 0 : }
250 : :
251 : :
252 : :
253 : 0 : void compressed_rank_pack(compressed_rank_t *cr, void *cr_packed)
254 : : {
255 : 0 : if (cr && cr_packed)
256 : : {
257 : 0 : char *buf = NULL;
258 : 0 : cmph_uint32 buflen = 0;
259 : 0 : compressed_rank_dump(cr, &buf, &buflen);
260 : 0 : memcpy(cr_packed, buf, buflen);
261 : 0 : free(buf);
262 : : }
263 : 0 : }
264 : :
265 : 0 : cmph_uint32 compressed_rank_packed_size(compressed_rank_t *cr)
266 : : {
267 : 0 : register cmph_uint32 sel_size = select_packed_size(&cr->sel);
268 : 0 : register cmph_uint32 vals_rems_size = BITS_TABLE_SIZE(cr->n, cr->rem_r) * (cmph_uint32)sizeof(cmph_uint32);
269 : 0 : return 4 * (cmph_uint32)sizeof(cmph_uint32) + sel_size + vals_rems_size;
270 : : }
271 : :
272 : 0 : cmph_uint32 compressed_rank_query_packed(void * cr_packed, cmph_uint32 idx)
273 : : {
274 : : // unpacking cr_packed
275 : 0 : register cmph_uint32 *ptr = (cmph_uint32 *)cr_packed;
276 : 0 : register cmph_uint32 max_val = *ptr++;
277 : 0 : register cmph_uint32 n = *ptr++;
278 : 0 : register cmph_uint32 rem_r = *ptr++;
279 : 0 : register cmph_uint32 buflen_sel = *ptr++;
280 : 0 : register cmph_uint32 * sel_packed = ptr;
281 : :
282 : 0 : register cmph_uint32 * bits_vec = sel_packed + 2; // skipping n and m
283 : :
284 : 0 : register cmph_uint32 * vals_rems = (ptr += (buflen_sel >> 2));
285 : :
286 : : // compressed sequence query computation
287 : : register cmph_uint32 rems_mask;
288 : : register cmph_uint32 val_quot, val_rem;
289 : : register cmph_uint32 sel_res, rank;
290 : :
291 : 0 : if(idx > max_val)
292 : : {
293 : 0 : return n;
294 : : }
295 : :
296 : 0 : val_quot = idx >> rem_r;
297 : 0 : rems_mask = (1U << rem_r) - 1U;
298 : 0 : val_rem = idx & rems_mask;
299 : 0 : if(val_quot == 0)
300 : : {
301 : 0 : rank = sel_res = 0;
302 : : }
303 : : else
304 : : {
305 : 0 : sel_res = select_query_packed(sel_packed, val_quot - 1) + 1;
306 : 0 : rank = sel_res - val_quot;
307 : : }
308 : :
309 : : do
310 : : {
311 : 0 : if(GETBIT32(bits_vec, sel_res))
312 : : {
313 : 0 : break;
314 : : }
315 : 0 : if(get_bits_value(vals_rems, rank, rem_r, rems_mask) >= val_rem)
316 : : {
317 : 0 : break;
318 : : }
319 : 0 : sel_res++;
320 : 0 : rank++;
321 : : } while(1);
322 : :
323 : 0 : return rank;
324 : : }
325 : :
326 : :
327 : :
|
