← Back to branch summary

~ubuntu-branches/ubuntu/trusty/gobject-introspection/trusty

« back to all changes in this revision

Viewing changes to girepository/cmph/compressed_rank.c

  • Committer: Bazaar Package Importer
  • Author(s): Emilio Pozuelo Monfort
  • Date: 2011-03-22 00:32:36 UTC
  • mfrom: (1.4.1 upstream) (3.3.33 multiarch)
  • Revision ID: james.westby@ubuntu.com-20110322003236-4spdgfk1vai6xay1
Tags: 0.10.4-2
Upload to unstable.

Show diffs side-by-side

added added

removed removed

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