girepository/cmph/bdz.c

   1 #include "bdz.h"
   2 #include "cmph_structs.h"
   3 #include "bdz_structs.h"
   4 #include "hash.h"
   5 #include "bitbool.h"
   6
   7 #include <math.h>
   8 #include <stdlib.h>
   9 #include <stdio.h>
  10 #include <assert.h>
  11 #include <string.h>
  12 //#define DEBUG
  13 #include "debug.h"
  14 #define UNASSIGNED 3U
  15 #define NULL_EDGE 0xffffffff
  16
  17 //cmph_uint32 ngrafos = 0;
  18 //cmph_uint32 ngrafos_aciclicos = 0;
  19 // table used for looking up the number of assigned vertices  a 8-bit integer
  20 const cmph_uint8 bdz_lookup_table[] =
  21 {
  22 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  23 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  24 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  25 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2, 1,
  26 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  27 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  28 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  29 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2, 1,
  30 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  31 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  32 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3, 2,
  33 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2, 1,
  34 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2, 1,
  35 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2, 1,
  36 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2, 1,
  37 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 0
  38 };
  39
  40 typedef struct
  41 {
  42         cmph_uint32 vertices[3];
  43         cmph_uint32 next_edges[3];
  44 }bdz_edge_t;
  45
  46 typedef cmph_uint32 * bdz_queue_t;
  47
  48 static void bdz_alloc_queue(bdz_queue_t * queuep, cmph_uint32 nedges)
  49 {
  50         (*queuep)=malloc(nedges*sizeof(cmph_uint32));
  51 };
  52 static void bdz_free_queue(bdz_queue_t * queue)
  53 {
  54         free(*queue);
  55 };
  56
  57 typedef struct
  58 {
  59         cmph_uint32 nedges;
  60         bdz_edge_t * edges;
  61         cmph_uint32 * first_edge;
  62         cmph_uint8 * vert_degree;
  63 }bdz_graph3_t;
  64
  65
  66 static void bdz_alloc_graph3(bdz_graph3_t * graph3, cmph_uint32 nedges, cmph_uint32 nvertices)
  67 {
  68         graph3->edges=malloc(nedges*sizeof(bdz_edge_t));
  69         graph3->first_edge=malloc(nvertices*sizeof(cmph_uint32));
  70         graph3->vert_degree=malloc((size_t)nvertices);
  71 };
  72 static void bdz_init_graph3(bdz_graph3_t * graph3, cmph_uint32 nedges, cmph_uint32 nvertices)
  73 {
  74         memset(graph3->first_edge,0xff,nvertices*sizeof(cmph_uint32));
  75         memset(graph3->vert_degree,0,(size_t)nvertices);
  76         graph3->nedges=0;
  77 };
  78 static void bdz_free_graph3(bdz_graph3_t *graph3)
  79 {
  80         free(graph3->edges);
  81         free(graph3->first_edge);
  82         free(graph3->vert_degree);
  83 };
  84
  85 static void bdz_partial_free_graph3(bdz_graph3_t *graph3)
  86 {
  87         free(graph3->first_edge);
  88         free(graph3->vert_degree);
  89         graph3->first_edge = NULL;
  90         graph3->vert_degree = NULL;
  91 };
  92
  93 static void bdz_add_edge(bdz_graph3_t * graph3, cmph_uint32 v0, cmph_uint32 v1, cmph_uint32 v2)
  94 {
  95         graph3->edges[graph3->nedges].vertices[0]=v0;
  96         graph3->edges[graph3->nedges].vertices[1]=v1;
  97         graph3->edges[graph3->nedges].vertices[2]=v2;
  98         graph3->edges[graph3->nedges].next_edges[0]=graph3->first_edge[v0];
  99         graph3->edges[graph3->nedges].next_edges[1]=graph3->first_edge[v1];
 100         graph3->edges[graph3->nedges].next_edges[2]=graph3->first_edge[v2];
 101         graph3->first_edge[v0]=graph3->first_edge[v1]=graph3->first_edge[v2]=graph3->nedges;
 102         graph3->vert_degree[v0]++;
 103         graph3->vert_degree[v1]++;
 104         graph3->vert_degree[v2]++;
 105         graph3->nedges++;
 106 };
 107
 108 static void bdz_dump_graph(bdz_graph3_t* graph3, cmph_uint32 nedges, cmph_uint32 nvertices)
 109 {
 110         cmph_uint32 i;
 111         for(i=0;i<nedges;i++){
 112                 printf("\nedge %d %d %d %d ",i,graph3->edges[i].vertices[0],
 113                         graph3->edges[i].vertices[1],graph3->edges[i].vertices[2]);
 114                 printf(" nexts %d %d %d",graph3->edges[i].next_edges[0],
 115                                 graph3->edges[i].next_edges[1],graph3->edges[i].next_edges[2]);
 116         };
 117
 118         for(i=0;i<nvertices;i++){
 119                 printf("\nfirst for vertice %d %d ",i,graph3->first_edge[i]);
 120
 121         };
 122 };
 123
 124 static void bdz_remove_edge(bdz_graph3_t * graph3, cmph_uint32 curr_edge)
 125 {
 126         cmph_uint32 i,j=0,vert,edge1,edge2;
 127         for(i=0;i<3;i++){
 128                 vert=graph3->edges[curr_edge].vertices[i];
 129                 edge1=graph3->first_edge[vert];
 130                 edge2=NULL_EDGE;
 131                 while(edge1!=curr_edge&&edge1!=NULL_EDGE){
 132                         edge2=edge1;
 133                         if(graph3->edges[edge1].vertices[0]==vert){
 134                                 j=0;
 135                         } else if(graph3->edges[edge1].vertices[1]==vert){
 136                                 j=1;
 137                         } else
 138                                 j=2;
 139                         edge1=graph3->edges[edge1].next_edges[j];
 140                 };
 141                 if(edge1==NULL_EDGE){
 142                         printf("\nerror remove edge %d dump graph",curr_edge);
 143                         bdz_dump_graph(graph3,graph3->nedges,graph3->nedges+graph3->nedges/4);
 144                         exit(-1);
 145                 };
 146
 147                 if(edge2!=NULL_EDGE){
 148                         graph3->edges[edge2].next_edges[j] =
 149                                 graph3->edges[edge1].next_edges[i];
 150                 } else
 151                         graph3->first_edge[vert]=
 152                                 graph3->edges[edge1].next_edges[i];
 153                 graph3->vert_degree[vert]--;
 154         };
 155
 156 };
 157
 158 static int bdz_generate_queue(cmph_uint32 nedges, cmph_uint32 nvertices, bdz_queue_t queue, bdz_graph3_t* graph3)
 159 {
 160         cmph_uint32 i,v0,v1,v2;
 161         cmph_uint32 queue_head=0,queue_tail=0;
 162         cmph_uint32 curr_edge;
 163         cmph_uint32 tmp_edge;
 164         cmph_uint8 * marked_edge =malloc((size_t)(nedges >> 3) + 1);
 165         memset(marked_edge, 0, (size_t)(nedges >> 3) + 1);
 166
 167         for(i=0;i<nedges;i++){
 168                 v0=graph3->edges[i].vertices[0];
 169                 v1=graph3->edges[i].vertices[1];
 170                 v2=graph3->edges[i].vertices[2];
 171                 if(graph3->vert_degree[v0]==1 ||
 172                                 graph3->vert_degree[v1]==1 ||
 173                                 graph3->vert_degree[v2]==1){
 174                         if(!GETBIT(marked_edge,i)) {
 175                                 queue[queue_head++]=i;
 176                                 SETBIT(marked_edge,i);
 177                         }
 178                 };
 179         };
 180         while(queue_tail!=queue_head){
 181                 curr_edge=queue[queue_tail++];
 182                 bdz_remove_edge(graph3,curr_edge);
 183                 v0=graph3->edges[curr_edge].vertices[0];
 184                 v1=graph3->edges[curr_edge].vertices[1];
 185                 v2=graph3->edges[curr_edge].vertices[2];
 186                 if(graph3->vert_degree[v0]==1 ) {
 187                         tmp_edge=graph3->first_edge[v0];
 188                         if(!GETBIT(marked_edge,tmp_edge)) {
 189                                 queue[queue_head++]=tmp_edge;
 190                                 SETBIT(marked_edge,tmp_edge);
 191                         };
 192
 193                 };
 194                 if(graph3->vert_degree[v1]==1) {
 195                         tmp_edge=graph3->first_edge[v1];
 196                         if(!GETBIT(marked_edge,tmp_edge)){
 197                                 queue[queue_head++]=tmp_edge;
 198                                 SETBIT(marked_edge,tmp_edge);
 199                         };
 200
 201                 };
 202                 if(graph3->vert_degree[v2]==1){
 203                         tmp_edge=graph3->first_edge[v2];
 204                         if(!GETBIT(marked_edge,tmp_edge)){
 205                                 queue[queue_head++]=tmp_edge;
 206                                 SETBIT(marked_edge,tmp_edge);
 207                         };
 208                 };
 209         };
 210         free(marked_edge);
 211         return (int)(queue_head-nedges);/* returns 0 if successful otherwies return negative number*/
 212 };
 213
 214 static int bdz_mapping(cmph_config_t *mph, bdz_graph3_t* graph3, bdz_queue_t queue);
 215 static void assigning(bdz_config_data_t *bdz, bdz_graph3_t* graph3, bdz_queue_t queue);
 216 static void ranking(bdz_config_data_t *bdz);
 217 static cmph_uint32 rank(cmph_uint32 b, cmph_uint32 * ranktable, cmph_uint8 * g, cmph_uint32 vertex);
 218
 219 bdz_config_data_t *bdz_config_new(void)
 220 {
 221         bdz_config_data_t *bdz;
 222         bdz = (bdz_config_data_t *)malloc(sizeof(bdz_config_data_t));
 223         assert(bdz);
 224         memset(bdz, 0, sizeof(bdz_config_data_t));
 225         bdz->hashfunc = CMPH_HASH_JENKINS;
 226         bdz->g = NULL;
 227         bdz->hl = NULL;
 228         bdz->k = 0; //kth index in ranktable, $k = log_2(n=3r)/\varepsilon$
 229         bdz->b = 7; // number of bits of k
 230         bdz->ranktablesize = 0; //number of entries in ranktable, $n/k +1$
 231         bdz->ranktable = NULL; // rank table
 232         return bdz;
 233 }
 234
 235 void bdz_config_destroy(cmph_config_t *mph)
 236 {
 237         bdz_config_data_t *data = (bdz_config_data_t *)mph->data;
 238         DEBUGP("Destroying algorithm dependent data\n");
 239         free(data);
 240 }
 241
 242 void bdz_config_set_b(cmph_config_t *mph, cmph_uint32 b)
 243 {
 244         bdz_config_data_t *bdz = (bdz_config_data_t *)mph->data;
 245         if (b <= 2 || b > 10) b = 7; // validating restrictions over parameter b.
 246         bdz->b = (cmph_uint8)b;
 247         DEBUGP("b: %u\n", b);
 248
 249 }
 250
 251 void bdz_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs)
 252 {
 253         bdz_config_data_t *bdz = (bdz_config_data_t *)mph->data;
 254         CMPH_HASH *hashptr = hashfuncs;
 255         cmph_uint32 i = 0;
 256         while(*hashptr != CMPH_HASH_COUNT)
 257         {
 258                 if (i >= 1) break; //bdz only uses one linear hash function
 259                 bdz->hashfunc = *hashptr;
 260                 ++i, ++hashptr;
 261         }
 262 }
 263
 264 cmph_t *bdz_new(cmph_config_t *mph, double c)
 265 {
 266         cmph_t *mphf = NULL;
 267         bdz_data_t *bdzf = NULL;
 268         cmph_uint32 iterations;
 269         bdz_queue_t edges;
 270         bdz_graph3_t graph3;
 271         bdz_config_data_t *bdz = (bdz_config_data_t *)mph->data;
 272         #ifdef CMPH_TIMING
 273         double construction_time_begin = 0.0;
 274         double construction_time = 0.0;
 275         ELAPSED_TIME_IN_SECONDS(&construction_time_begin);
 276         #endif
 277
 278
 279         if (c == 0) c = 1.23; // validating restrictions over parameter c.
 280         DEBUGP("c: %f\n", c);
 281         bdz->m = mph->key_source->nkeys;
 282         bdz->r = (cmph_uint32)ceil((c * mph->key_source->nkeys)/3);
 283         if ((bdz->r % 2) == 0) bdz->r+=1;
 284         bdz->n = 3*bdz->r;
 285
 286         bdz->k = (1U << bdz->b);
 287         DEBUGP("b: %u -- k: %u\n", bdz->b, bdz->k);
 288
 289         bdz->ranktablesize = (cmph_uint32)ceil(bdz->n/(double)bdz->k);
 290         DEBUGP("ranktablesize: %u\n", bdz->ranktablesize);
 291
 292
 293         bdz_alloc_graph3(&graph3, bdz->m, bdz->n);
 294         bdz_alloc_queue(&edges,bdz->m);
 295         DEBUGP("Created hypergraph\n");
 296
 297         DEBUGP("m (edges): %u n (vertices): %u  r: %u c: %f \n", bdz->m, bdz->n, bdz->r, c);
 298
 299         // Mapping step
 300         iterations = 1000;
 301         if (mph->verbosity)
 302         {
 303                 fprintf(stderr, "Entering mapping step for mph creation of %u keys with graph sized %u\n", bdz->m, bdz->n);
 304         }
 305         while(1)
 306         {
 307                 int ok;
 308                 DEBUGP("linear hash function \n");
 309                 bdz->hl = hash_state_new(bdz->hashfunc, 15);
 310
 311                 ok = bdz_mapping(mph, &graph3, edges);
 312                 //ok = 0;
 313                 if (!ok)
 314                 {
 315                         --iterations;
 316                         hash_state_destroy(bdz->hl);
 317                         bdz->hl = NULL;
 318                         DEBUGP("%u iterations remaining\n", iterations);
 319                         if (mph->verbosity)
 320                         {
 321                                 fprintf(stderr, "acyclic graph creation failure - %u iterations remaining\n", iterations);
 322                         }
 323                         if (iterations == 0) break;
 324                 }
 325                 else break;
 326         }
 327
 328         if (iterations == 0)
 329         {
 330                 bdz_free_queue(&edges);
 331                 bdz_free_graph3(&graph3);
 332                 return NULL;
 333         }
 334         bdz_partial_free_graph3(&graph3);
 335         // Assigning step
 336         if (mph->verbosity)
 337         {
 338                 fprintf(stderr, "Entering assigning step for mph creation of %u keys with graph sized %u\n", bdz->m, bdz->n);
 339         }
 340         assigning(bdz, &graph3, edges);
 341
 342         bdz_free_queue(&edges);
 343         bdz_free_graph3(&graph3);
 344         if (mph->verbosity)
 345         {
 346                 fprintf(stderr, "Entering ranking step for mph creation of %u keys with graph sized %u\n", bdz->m, bdz->n);
 347         }
 348         ranking(bdz);
 349         #ifdef CMPH_TIMING
 350         ELAPSED_TIME_IN_SECONDS(&construction_time);
 351         #endif
 352         mphf = (cmph_t *)malloc(sizeof(cmph_t));
 353         mphf->algo = mph->algo;
 354         bdzf = (bdz_data_t *)malloc(sizeof(bdz_data_t));
 355         bdzf->g = bdz->g;
 356         bdz->g = NULL; //transfer memory ownership
 357         bdzf->hl = bdz->hl;
 358         bdz->hl = NULL; //transfer memory ownership
 359         bdzf->ranktable = bdz->ranktable;
 360         bdz->ranktable = NULL; //transfer memory ownership
 361         bdzf->ranktablesize = bdz->ranktablesize;
 362         bdzf->k = bdz->k;
 363         bdzf->b = bdz->b;
 364         bdzf->n = bdz->n;
 365         bdzf->m = bdz->m;
 366         bdzf->r = bdz->r;
 367         mphf->data = bdzf;
 368         mphf->size = bdz->m;
 369
 370         DEBUGP("Successfully generated minimal perfect hash\n");
 371         if (mph->verbosity)
 372         {
 373                 fprintf(stderr, "Successfully generated minimal perfect hash function\n");
 374         }
 375
 376
 377         #ifdef CMPH_TIMING
 378         register cmph_uint32 space_usage = bdz_packed_size(mphf)*8;
 379         register cmph_uint32 keys_per_bucket = 1;
 380         construction_time = construction_time - construction_time_begin;
 381         fprintf(stdout, "%u\t%.2f\t%u\t%.4f\t%.4f\n", bdz->m, bdz->m/(double)bdz->n, keys_per_bucket, construction_time, space_usage/(double)bdz->m);
 382         #endif
 383
 384         return mphf;
 385 }
 386
 387
 388 static int bdz_mapping(cmph_config_t *mph, bdz_graph3_t* graph3, bdz_queue_t queue)
 389 {
 390         cmph_uint32 e;
 391         int cycles = 0;
 392         cmph_uint32 hl[3];
 393         bdz_config_data_t *bdz = (bdz_config_data_t *)mph->data;
 394         bdz_init_graph3(graph3, bdz->m, bdz->n);
 395         mph->key_source->rewind(mph->key_source->data);
 396         for (e = 0; e < mph->key_source->nkeys; ++e)
 397         {
 398                 cmph_uint32 h0, h1, h2;
 399                 cmph_uint32 keylen;
 400                 char *key = NULL;
 401                 mph->key_source->read(mph->key_source->data, &key, &keylen);
 402                 hash_vector(bdz->hl, key, keylen,hl);
 403                 h0 = hl[0] % bdz->r;
 404                 h1 = hl[1] % bdz->r + bdz->r;
 405                 h2 = hl[2] % bdz->r + (bdz->r << 1);
 406                 mph->key_source->dispose(mph->key_source->data, key, keylen);
 407                 bdz_add_edge(graph3,h0,h1,h2);
 408         }
 409         cycles = bdz_generate_queue(bdz->m, bdz->n, queue, graph3);
 410         return (cycles == 0);
 411 }
 412
 413 static void assigning(bdz_config_data_t *bdz, bdz_graph3_t* graph3, bdz_queue_t queue)
 414 {
 415         cmph_uint32 i;
 416         cmph_uint32 nedges=graph3->nedges;
 417         cmph_uint32 curr_edge;
 418         cmph_uint32 v0,v1,v2;
 419         cmph_uint8 * marked_vertices =malloc((size_t)(bdz->n >> 3) + 1);
 420         cmph_uint32 sizeg = (cmph_uint32)ceil(bdz->n/4.0);
 421         bdz->g = (cmph_uint8 *)calloc((size_t)(sizeg), sizeof(cmph_uint8));
 422         memset(marked_vertices, 0, (size_t)(bdz->n >> 3) + 1);
 423         memset(bdz->g, 0xff, (size_t)(sizeg));
 424
 425         for(i=nedges-1;i+1>=1;i--){
 426                 curr_edge=queue[i];
 427                 v0=graph3->edges[curr_edge].vertices[0];
 428                 v1=graph3->edges[curr_edge].vertices[1];
 429                 v2=graph3->edges[curr_edge].vertices[2];
 430                 DEBUGP("B:%u %u %u -- %u %u %u\n", v0, v1, v2, GETVALUE(bdz->g, v0), GETVALUE(bdz->g, v1), GETVALUE(bdz->g, v2));
 431                 if(!GETBIT(marked_vertices, v0)){
 432                         if(!GETBIT(marked_vertices,v1))
 433                         {
 434                                 SETVALUE1(bdz->g, v1, UNASSIGNED);
 435                                 SETBIT(marked_vertices, v1);
 436                         }
 437                         if(!GETBIT(marked_vertices,v2))
 438                         {
 439                                 SETVALUE1(bdz->g, v2, UNASSIGNED);
 440                                 SETBIT(marked_vertices, v2);
 441                         }
 442                         SETVALUE1(bdz->g, v0, (6-(GETVALUE(bdz->g, v1) + GETVALUE(bdz->g,v2)))%3);
 443                         SETBIT(marked_vertices, v0);
 444                 } else if(!GETBIT(marked_vertices, v1)) {
 445                         if(!GETBIT(marked_vertices, v2))
 446                         {
 447                                 SETVALUE1(bdz->g, v2, UNASSIGNED);
 448                                 SETBIT(marked_vertices, v2);
 449                         }
 450                         SETVALUE1(bdz->g, v1, (7-(GETVALUE(bdz->g, v0)+GETVALUE(bdz->g, v2)))%3);
 451                         SETBIT(marked_vertices, v1);
 452                 }else {
 453                         SETVALUE1(bdz->g, v2, (8-(GETVALUE(bdz->g,v0)+GETVALUE(bdz->g, v1)))%3);
 454                         SETBIT(marked_vertices, v2);
 455                 }
 456                 DEBUGP("A:%u %u %u -- %u %u %u\n", v0, v1, v2, GETVALUE(bdz->g, v0), GETVALUE(bdz->g, v1), GETVALUE(bdz->g, v2));
 457         };
 458         free(marked_vertices);
 459 }
 460
 461
 462 static void ranking(bdz_config_data_t *bdz)
 463 {
 464         cmph_uint32 i, j, offset = 0U, count = 0U, size = (bdz->k >> 2U), nbytes_total = (cmph_uint32)ceil(bdz->n/4.0), nbytes;
 465         bdz->ranktable = (cmph_uint32 *)calloc((size_t)bdz->ranktablesize, sizeof(cmph_uint32));
 466         // ranktable computation
 467         bdz->ranktable[0] = 0;
 468         i = 1;
 469         while(1)
 470         {
 471                 if(i == bdz->ranktablesize) break;
 472                 nbytes = size < nbytes_total? size : nbytes_total;
 473                 for(j = 0; j < nbytes; j++)
 474                 {
 475                         count += bdz_lookup_table[*(bdz->g + offset + j)];
 476                 }
 477                 bdz->ranktable[i] = count;
 478                 offset += nbytes;
 479                 nbytes_total -= size;
 480                 i++;
 481         }
 482 }
 483
 484
 485 int bdz_dump(cmph_t *mphf, FILE *fd)
 486 {
 487         char *buf = NULL;
 488         cmph_uint32 buflen;
 489         register size_t nbytes;
 490         bdz_data_t *data = (bdz_data_t *)mphf->data;
 491         __cmph_dump(mphf, fd);
 492
 493         hash_state_dump(data->hl, &buf, &buflen);
 494         DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
 495         nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
 496         nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
 497         free(buf);
 498
 499         nbytes = fwrite(&(data->n), sizeof(cmph_uint32), (size_t)1, fd);
 500         nbytes = fwrite(&(data->m), sizeof(cmph_uint32), (size_t)1, fd);
 501         nbytes = fwrite(&(data->r), sizeof(cmph_uint32), (size_t)1, fd);
 502
 503         cmph_uint32 sizeg = (cmph_uint32)ceil(data->n/4.0);
 504         nbytes = fwrite(data->g, sizeof(cmph_uint8)*sizeg, (size_t)1, fd);
 505
 506         nbytes = fwrite(&(data->k), sizeof(cmph_uint32), (size_t)1, fd);
 507         nbytes = fwrite(&(data->b), sizeof(cmph_uint8), (size_t)1, fd);
 508         nbytes = fwrite(&(data->ranktablesize), sizeof(cmph_uint32), (size_t)1, fd);
 509
 510         nbytes = fwrite(data->ranktable, sizeof(cmph_uint32)*(data->ranktablesize), (size_t)1, fd);
 511         #ifdef DEBUG
 512         cmph_uint32 i;
 513         fprintf(stderr, "G: ");
 514         for (i = 0; i < data->n; ++i) fprintf(stderr, "%u ", GETVALUE(data->g, i));
 515         fprintf(stderr, "\n");
 516         #endif
 517         return 1;
 518 }
 519
 520 void bdz_load(FILE *f, cmph_t *mphf)
 521 {
 522         char *buf = NULL;
 523         cmph_uint32 buflen, sizeg;
 524         register size_t nbytes;
 525         bdz_data_t *bdz = (bdz_data_t *)malloc(sizeof(bdz_data_t));
 526
 527         DEBUGP("Loading bdz mphf\n");
 528         mphf->data = bdz;
 529
 530         nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
 531         DEBUGP("Hash state has %u bytes\n", buflen);
 532         buf = (char *)malloc((size_t)buflen);
 533         nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
 534         bdz->hl = hash_state_load(buf, buflen);
 535         free(buf);
 536
 537
 538         DEBUGP("Reading m and n\n");
 539         nbytes = fread(&(bdz->n), sizeof(cmph_uint32), (size_t)1, f);
 540         nbytes = fread(&(bdz->m), sizeof(cmph_uint32), (size_t)1, f);
 541         nbytes = fread(&(bdz->r), sizeof(cmph_uint32), (size_t)1, f);
 542         sizeg = (cmph_uint32)ceil(bdz->n/4.0);
 543         bdz->g = (cmph_uint8 *)calloc((size_t)(sizeg), sizeof(cmph_uint8));
 544         nbytes = fread(bdz->g, sizeg*sizeof(cmph_uint8), (size_t)1, f);
 545
 546         nbytes = fread(&(bdz->k), sizeof(cmph_uint32), (size_t)1, f);
 547         nbytes = fread(&(bdz->b), sizeof(cmph_uint8), (size_t)1, f);
 548         nbytes = fread(&(bdz->ranktablesize), sizeof(cmph_uint32), (size_t)1, f);
 549
 550         bdz->ranktable = (cmph_uint32 *)calloc((size_t)bdz->ranktablesize, sizeof(cmph_uint32));
 551         nbytes = fread(bdz->ranktable, sizeof(cmph_uint32)*(bdz->ranktablesize), (size_t)1, f);
 552
 553         #ifdef DEBUG
 554         cmph_uint32  i = 0;
 555         fprintf(stderr, "G: ");
 556         for (i = 0; i < bdz->n; ++i) fprintf(stderr, "%u ", GETVALUE(bdz->g,i));
 557         fprintf(stderr, "\n");
 558         #endif
 559         return;
 560 }
 561
 562
 563 /*
 564 static cmph_uint32 bdz_search_ph(cmph_t *mphf, const char *key, cmph_uint32 keylen)
 565 {
 566         bdz_data_t *bdz = mphf->data;
 567         cmph_uint32 hl[3];
 568         hash_vector(bdz->hl, key, keylen, hl);
 569         cmph_uint32 vertex;
 570         hl[0] = hl[0] % bdz->r;
 571         hl[1] = hl[1] % bdz->r + bdz->r;
 572         hl[2] = hl[2] % bdz->r + (bdz->r << 1);
 573         vertex = hl[(GETVALUE(bdz->g, hl[0]) + GETVALUE(bdz->g, hl[1]) + GETVALUE(bdz->g, hl[2])) % 3];
 574         return vertex;
 575 }
 576 */
 577
 578 static inline cmph_uint32 rank(cmph_uint32 b, cmph_uint32 * ranktable, cmph_uint8 * g, cmph_uint32 vertex)
 579 {
 580         register cmph_uint32 index = vertex >> b;
 581         register cmph_uint32 base_rank = ranktable[index];
 582         register cmph_uint32 beg_idx_v = index << b;
 583         register cmph_uint32 beg_idx_b = beg_idx_v >> 2;
 584         register cmph_uint32 end_idx_b = vertex >> 2;
 585         while(beg_idx_b < end_idx_b)
 586         {
 587                 base_rank += bdz_lookup_table[*(g + beg_idx_b++)];
 588
 589         }
 590         beg_idx_v = beg_idx_b << 2;
 591         while(beg_idx_v < vertex)
 592         {
 593                 if(GETVALUE(g, beg_idx_v) != UNASSIGNED) base_rank++;
 594                 beg_idx_v++;
 595         }
 596
 597         return base_rank;
 598 }
 599
 600 cmph_uint32 bdz_search(cmph_t *mphf, const char *key, cmph_uint32 keylen)
 601 {
 602         register cmph_uint32 vertex;
 603         register bdz_data_t *bdz = mphf->data;
 604         cmph_uint32 hl[3];
 605         hash_vector(bdz->hl, key, keylen, hl);
 606         hl[0] = hl[0] % bdz->r;
 607         hl[1] = hl[1] % bdz->r + bdz->r;
 608         hl[2] = hl[2] % bdz->r + (bdz->r << 1);
 609         vertex = hl[(GETVALUE(bdz->g, hl[0]) + GETVALUE(bdz->g, hl[1]) + GETVALUE(bdz->g, hl[2])) % 3];
 610         return rank(bdz->b, bdz->ranktable, bdz->g, vertex);
 611 }
 612
 613
 614 void bdz_destroy(cmph_t *mphf)
 615 {
 616         bdz_data_t *data = (bdz_data_t *)mphf->data;
 617         free(data->g);
 618         hash_state_destroy(data->hl);
 619         free(data->ranktable);
 620         free(data);
 621         free(mphf);
 622 }
 623
 624 /** \fn void bdz_pack(cmph_t *mphf, void *packed_mphf);
 625  *  \brief Support the ability to pack a perfect hash function into a preallocated contiguous memory space pointed by packed_mphf.
 626  *  \param mphf pointer to the resulting mphf
 627  *  \param packed_mphf pointer to the contiguous memory area used to store the resulting mphf. The size of packed_mphf must be at least cmph_packed_size()
 628  */
 629 void bdz_pack(cmph_t *mphf, void *packed_mphf)
 630 {
 631         bdz_data_t *data = (bdz_data_t *)mphf->data;
 632         cmph_uint8 * ptr = packed_mphf;
 633
 634         // packing hl type
 635         CMPH_HASH hl_type = hash_get_type(data->hl);
 636         *((cmph_uint32 *) ptr) = hl_type;
 637         ptr += sizeof(cmph_uint32);
 638
 639         // packing hl
 640         hash_state_pack(data->hl, ptr);
 641         ptr += hash_state_packed_size(hl_type);
 642
 643         // packing r
 644         *((cmph_uint32 *) ptr) = data->r;
 645         ptr += sizeof(data->r);
 646
 647         // packing ranktablesize
 648         *((cmph_uint32 *) ptr) = data->ranktablesize;
 649         ptr += sizeof(data->ranktablesize);
 650
 651         // packing ranktable
 652         memcpy(ptr, data->ranktable, sizeof(cmph_uint32)*(data->ranktablesize));
 653         ptr += sizeof(cmph_uint32)*(data->ranktablesize);
 654
 655         // packing b
 656         *ptr++ = data->b;
 657
 658         // packing g
 659         cmph_uint32 sizeg = (cmph_uint32)ceil(data->n/4.0);
 660         memcpy(ptr, data->g,  sizeof(cmph_uint8)*sizeg);
 661 }
 662
 663 /** \fn cmph_uint32 bdz_packed_size(cmph_t *mphf);
 664  *  \brief Return the amount of space needed to pack mphf.
 665  *  \param mphf pointer to a mphf
 666  *  \return the size of the packed function or zero for failures
 667  */
 668 cmph_uint32 bdz_packed_size(cmph_t *mphf)
 669 {
 670         bdz_data_t *data = (bdz_data_t *)mphf->data;
 671
 672         CMPH_HASH hl_type = hash_get_type(data->hl);
 673
 674         return (cmph_uint32)(sizeof(CMPH_ALGO) + hash_state_packed_size(hl_type) + 3*sizeof(cmph_uint32) + sizeof(cmph_uint32)*(data->ranktablesize) + sizeof(cmph_uint8) + sizeof(cmph_uint8)* (cmph_uint32)(ceil(data->n/4.0)));
 675 }
 676
 677 /** cmph_uint32 bdz_search(void *packed_mphf, const char *key, cmph_uint32 keylen);
 678  *  \brief Use the packed mphf to do a search.
 679  *  \param  packed_mphf pointer to the packed mphf
 680  *  \param key key to be hashed
 681  *  \param keylen key legth in bytes
 682  *  \return The mphf value
 683  */
 684 cmph_uint32 bdz_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen)
 685 {
 686
 687         register cmph_uint32 vertex;
 688         register CMPH_HASH hl_type  = *(cmph_uint32 *)packed_mphf;
 689         register cmph_uint8 *hl_ptr = (cmph_uint8 *)(packed_mphf) + 4;
 690
 691         register cmph_uint32 *ranktable = (cmph_uint32*)(hl_ptr + hash_state_packed_size(hl_type));
 692
 693         register cmph_uint32 r = *ranktable++;
 694         register cmph_uint32 ranktablesize = *ranktable++;
 695         register cmph_uint8 * g = (cmph_uint8 *)(ranktable + ranktablesize);
 696         register cmph_uint8 b = *g++;
 697
 698         cmph_uint32 hl[3];
 699         hash_vector_packed(hl_ptr, hl_type, key, keylen, hl);
 700         hl[0] = hl[0] % r;
 701         hl[1] = hl[1] % r + r;
 702         hl[2] = hl[2] % r + (r << 1);
 703         vertex = hl[(GETVALUE(g, hl[0]) + GETVALUE(g, hl[1]) + GETVALUE(g, hl[2])) % 3];
 704         return rank(b, ranktable, g, vertex);
 705 }