swcsa/intIndex/icsa.c

   1 #include "icsa.h"
   2
   3 // Global para que funcione a funcion de comparacion do quicksort
   4 uint *intVector;
   5
   6 // Para o quicksort
   7 int suffixCmp(const void *arg1, const void *arg2) {
   8
   9         register uint a,b;
  10         a=*((uint *) arg1);
  11         b=*((uint *) arg2);
  12
  13         while(intVector[a] == intVector[b]) { a++; b++; }
  14         return (intVector[a] - intVector[b]);
  15
  16 }
  17
  18
  19
  20 /* **NO REVISADO TAMAÑO FILE.
  21 int buildIntIndexFromFile (char *filename, char *build_options,void **index) {
  22         //char filename[255];
  23         int file;
  24         struct stat f_stat;
  25         //sprintf(filename, "%s.%s", basename,SE_FILE_EXT);
  26
  27         if( (file = open(filename, O_RDONLY)) < 0) {
  28                 printf("Cannot open file %s\n", filename);
  29                 exit(0);
  30         }
  31         if( fstat(file, &f_stat) < 0) {
  32                 printf("Cannot read information from file %s\n", filename);     exit(0);
  33         }
  34         uint sizeFile = (f_stat.st_size)/sizeof(uint);
  35
  36         uint *se = (uint *) malloc (sizeFile);
  37         uint seSize = sizeFile / sizeof(uint);
  38         read(file, se,  sizeFile);              //the samples
  39         close(file);
  40         return (buildIntIndex(se,seSize,build_options,index));
  41 }
  42 */
  43
  44 //ticsa *createIntegerCSA(uint **aintVector, uint textSize, char *build_options) {
  45 int buildIntIndex (uint *aintVector, uint n, char *build_options, void **index ){
  46         uint textSize=n;
  47         intVector = aintVector;  //global variable
  48         ticsa *myicsa;
  49         myicsa = (ticsa *) malloc (sizeof (ticsa));
  50         uint *Psi, *SAI, *C, vocSize;
  51         register uint i, j;
  52         uint nsHUFF;
  53
  54         parametersCSA(myicsa, build_options);
  55
  56         nsHUFF=myicsa->tempNSHUFF;
  57
  58         // Almacenamos o valor dalguns parametros
  59         myicsa->suffixArraySize = textSize;
  60         myicsa->D = (uint*) malloc (sizeof(uint) * ((textSize+31)/32));
  61
  62         myicsa->samplesASize = (textSize + myicsa->T_A - 1) / myicsa->T_A + 1;
  63         myicsa->samplesA = (uint *)malloc(sizeof(int) * myicsa->samplesASize);
  64         myicsa->BA = (uint*) malloc (sizeof(uint) * ((textSize+31)/32));
  65         myicsa->samplesAInvSize = (textSize + myicsa->T_AInv - 1) / myicsa->T_AInv;
  66         myicsa->samplesAInv = (uint *)malloc(sizeof(int) * myicsa->samplesAInvSize);
  67
  68         // Reservamos espacio para os vectores
  69         Psi = (uint *) malloc (sizeof(uint) * textSize);
  70
  71         // CONSTRUIMOS A FUNCION C
  72         vocSize = 0;
  73         for(i=0;i<textSize;i++) if(intVector[i]>vocSize) vocSize = intVector[i];
  74         C = (uint *) malloc(sizeof(uint) * (vocSize + 1));      // Para contar o 0 terminador
  75         for(i=0;i<vocSize;i++) C[i] = 0;
  76         for(i=0;i<textSize;i++) C[intVector[i]]++;
  77         for (i=0,j=0;i<=vocSize;i++) {
  78                 j = j + C[i];
  79                 C[i] = j;
  80         }
  81         for(i=vocSize;i>0;i--) C[i] = C[i-1];
  82         C[0] = 0;
  83
  84         // Construimos o array de sufixos (en Psi) - con quicksort
  85         printf("\n\t *BUILDING THE SUFFIX ARRAY over %d integers... (with qsort)", textSize);fflush(stdout);
  86         for(i=0; i<textSize; i++) Psi[i]=i;
  87
  88         qsort(Psi, textSize, sizeof(uint), suffixCmp);
  89
  90
  91         printf("\n\t ...... ended.");
  92
  93         // CONSTRUIMOS A INVERSA DO ARRAY DE SUFIXOS
  94         SAI = (uint *) malloc (sizeof(uint) * (textSize + 1));  // +1 para repetir na ultima posición. Evitamos un if
  95         for(i=0;i<textSize;i++) SAI[Psi[i]] = i;
  96         SAI[textSize] = SAI[0];
  97
  98         // ALMACENAMOS AS MOSTRAS DO ARRAY DE SUFIXOS
  99         for(i=0;i<((textSize+31)/32);i++) myicsa->BA[i] = 0;
 100         for(i=0; i<textSize; i+=myicsa->T_A) bitset(myicsa->BA, SAI[i]);
 101         bitset(myicsa->BA, SAI[textSize-1]);                    // A ultima posicion sempre muestreada
 102         //printf("TextSize = %d\n", textSize);
 103         myicsa->bBA = createBitmap(myicsa->BA, textSize);
 104         for(i=0,j=0; i<textSize; i++) if(bitget(myicsa->BA, i)) myicsa->samplesA[j++] = Psi[i];
 105
 106         // ALMACENAMOS AS MOSTRAS DA INVERSA DO ARRAY DE SUFIXOS
 107         for(i=0,j=0;i<textSize;i+=myicsa->T_AInv) myicsa->samplesAInv[j++] = SAI[i];
 108
 109         // CONSTRUIMOS E COMPRIMIMOS PSI
 110         printf("\n\t Creating compressed Psi...");
 111         for(i=0;i<textSize;i++) Psi[i] = SAI[Psi[i]+1];
 112         free(SAI);
 113         #ifdef PSI_HUFFMANRLE
 114         myicsa->hcPsi = huffmanCompressPsi(Psi,textSize,myicsa->T_Psi,nsHUFF);
 115         #endif
 116         #ifdef PSI_GONZALO
 117         myicsa->gcPsi = gonzaloCompressPsi(Psi,textSize,myicsa->T_Psi,nsHUFF);
 118         #endif
 119         #ifdef PSI_DELTACODES
 120         myicsa->dcPsi = deltaCompressPsi(Psi,textSize,myicsa->T_Psi);
 121         #endif
 122         free(Psi);
 123
 124         // Contruimos D
 125         for(i=0;i<((textSize+31)/32);i++) myicsa->D[i] = 0;
 126         for(i=0;i<=vocSize;i++) bitset(myicsa->D, C[i]);
 127         myicsa->bD = createBitmap(myicsa->D,textSize);
 128         free(C);
 129
 130         // VARIABLE GLOBAL QUE ALMACENA O ESTADO DOS DISPLAYS (IMPORTANTE PARA DISPLAY SECUENCIAL)
 131         // Almacena a última posición do array de sufixos que mostramos con display ou displayNext
 132         // Se nos piden un displayNext, aplicamos PSI sobre esta posición e obtemos a seguinte,
 133         // coa que podemos obter o símbolo pedido, e actualizamos displayState
 134         myicsa->displayCSAState = 0;
 135         myicsa->displayCSAPrevPosition = -2;  //needed by DisplayCSA(position)
 136
 137         aintVector = intVector;
 138         // Liberamos o espacion non necesario
 139
 140         *index = myicsa;
 141         //return (myicsa);
 142         return 0;
 143 }
 144
 145
 146 //Returns number of elements in the indexed sequence of integers
 147 int sourceLenIntIndex(void *index, uint *numInts){
 148         ticsa *myicsa = (ticsa *) index;
 149         *numInts= myicsa->suffixArraySize;
 150         return 0; //no error;
 151 }
 152
 153 int saveIntIndex(void *index, char *pathname) {
 154 //void storeStructsCSA(ticsa *myicsa, char *basename) {
 155
 156         ticsa *myicsa = (ticsa *) index;
 157         char *basename=pathname;
 158
 159         char *filename;
 160         int file;
 161
 162         // Reservamos espacio para o nome do ficheiro
 163         filename = (char *)malloc(sizeof(char)*MAX_FILENAME_LENGTH);
 164
 165         // Ficheiro co n�mero de elementos indexados (enteiros do texto orixinal)
 166         strcpy(filename, basename);
 167         strcat(filename, ".");
 168         strcat(filename, NUMBER_OF_ELEMENTS_FILE_EXT);
 169         unlink(filename);
 170         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 171                 printf("Cannot open file %s\n", filename);
 172                 exit(0);
 173         }
 174         write(file, &(myicsa->suffixArraySize), sizeof(int));
 175         close(file);
 176
 177         strcpy(filename, basename);
 178         strcat(filename, ".");
 179         strcat(filename, PSI_COMPRESSED_FILE_EXT);
 180
 181         #ifdef PSI_HUFFMANRLE
 182                 storeHuffmanCompressedPsi(&(myicsa->hcPsi), filename);
 183         #endif
 184         #ifdef PSI_GONZALO
 185                 storeGonzaloCompressedPsi(&(myicsa->gcPsi), filename);
 186         #endif
 187         #ifdef PSI_DELTACODES
 188                 storeDeltaCompressedPsi(&(myicsa->dcPsi), filename);
 189         #endif
 190
 191         // Ficheiro co vector de bits D
 192         strcpy(filename, basename);
 193         strcat(filename, ".");
 194         strcat(filename, D_FILE_EXT);
 195         unlink(filename);
 196         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 197                 printf("Cannot open file %s\n", filename);
 198                 exit(0);
 199         }
 200         write(file, myicsa->D, sizeof(int)*((myicsa->suffixArraySize+31)/32));
 201         close(file);
 202
 203         // Directorio de rank para D
 204         // Almacenamos o n�mero de superbloques seguido dos superbloques
 205         // E logo o n�mero de bloques seguido dos bloques
 206         strcpy(filename, basename);
 207         strcat(filename, ".");
 208         strcat(filename, D_RANK_DIRECTORY_FILE_EXT);
 209         saveBitmap(filename,myicsa->bD);
 210
 211         // Ficheiro coas mostras de A
 212         strcpy(filename, basename);
 213         strcat(filename, ".");
 214         strcat(filename, SAMPLES_A_FILE_EXT);
 215         unlink(filename);
 216         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 217                 printf("Cannot open file %s\n", filename);
 218                 exit(0);
 219         }
 220         write(file, myicsa->samplesA, sizeof(int) * (myicsa->samplesASize));
 221         close(file);
 222
 223         // Ficheiro co vector BA (marca as posicions de A muestreadas)
 224         strcpy(filename, basename);
 225         strcat(filename, ".");
 226         strcat(filename, BA_FILE_EXT);
 227         unlink(filename);
 228         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 229                 printf("Cannot open file %s\n", filename);
 230                 exit(0);
 231         }
 232         write(file, myicsa->BA, sizeof(int)*((myicsa->suffixArraySize+31)/32));
 233         close(file);
 234
 235         // Directorio de rank para BA
 236         strcpy(filename, basename);
 237         strcat(filename, ".");
 238         strcat(filename, BA_RANK_DIRECTORY_FILE_EXT);
 239         saveBitmap(filename, myicsa->bBA);
 240
 241         // Ficheiro coas mostras de A inversa
 242         strcpy(filename, basename);
 243         strcat(filename, ".");
 244         strcat(filename, SAMPLES_A_INV_FILE_EXT);
 245         unlink(filename);
 246         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 247                 printf("Cannot open file %s\n", filename);
 248                 exit(0);
 249         }
 250         write(file, myicsa->samplesAInv, sizeof(int) * (myicsa->samplesAInvSize));
 251         close(file);
 252
 253         // Ficheiro co periodo de muestreo de A e A inversa
 254         strcpy(filename, basename);
 255         strcat(filename, ".");
 256         strcat(filename, SAMPLING_PERIOD_A_FILE_EXT);
 257         unlink(filename);
 258         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 259                 printf("Cannot open file %s\n", filename);
 260                 exit(0);
 261         }
 262         write(file, &(myicsa->T_A), sizeof(int));
 263         write(file, &(myicsa->T_AInv), sizeof(int));
 264
 265         write(file, &(myicsa->psiSearchFactorJump), sizeof(uint));
 266
 267         close(file);
 268         free(filename);
 269         return 0; //no error.
 270 }
 271
 272 //Returns the size (in bytes) of the index over the sequence of integers.
 273 //uint CSA_size(ticsa *myicsa) {
 274 int sizeIntIndex(void *index, uint *numBytes) {
 275         ticsa *myicsa = (ticsa *) index;
 276         uint size = 0;
 277         size +=(sizeof (ticsa) * 1);
 278         size += sizeof(uint)*((myicsa->suffixArraySize+31)/32) ;  //D vector
 279         size += myicsa->bD->mem_usage;
 280         size += sizeof(uint) * myicsa->samplesASize ;  // samples A
 281         size += sizeof(uint) * myicsa->samplesAInvSize ;  // samples A^{-1}
 282         size += sizeof(uint)*((myicsa->suffixArraySize+31)/32) ;  //BA vector
 283         size += myicsa->bBA->mem_usage;
 284         #ifdef PSI_HUFFMANRLE
 285                 size +=myicsa->hcPsi.totalMem;
 286         #endif
 287         #ifdef PSI_GONZALO
 288                 size +=myicsa->gcPsi.totalMem;
 289         #endif
 290         #ifdef PSI_DELTACODES
 291                 size +=myicsa->dcPsi.totalMem;
 292         #endif
 293         *numBytes = size;
 294         return 0; //no error.
 295 }
 296
 297
 298 //ticsa *loadCSA(char *basename) {
 299 int loadIntIndex(char *pathname, void **index){
 300
 301         char *basename=pathname;
 302         char *filename;
 303         int file;
 304         uint length;
 305         char c;
 306         char *word;
 307         struct stat f_stat;
 308         uint suffixArraySize;
 309
 310         ticsa *myicsa;
 311         myicsa = (ticsa *) malloc (sizeof (ticsa) * 1);
 312
 313
 314         // VARIABLE GLOBAL QUE ALMACENA O ESTADO DOS DISPLAYS (IMPORTANTE PARA DISPLAY SECUENCIAL)
 315         // Almacena a �ltima posici�n do array de sufixos que mostramos con display ou displayNext
 316         // Se nos piden un displayNext, aplicamos PSI sobre esta posici�n e obtemos a seguinte,
 317         // coa que podemos obter o s�mbolo pedido, e actualizamos displayState
 318         myicsa->displayCSAState = 0;
 319         myicsa->displayCSAPrevPosition = -2;  //needed by DisplayCSA(position)
 320
 321         // Reservamos espacio para o nome do ficheiro
 322         filename = (char *)malloc(sizeof(char)*MAX_FILENAME_LENGTH);
 323
 324         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O NUMERO DE ELEMENTOS INDEXADOS
 325         strcpy(filename, basename);
 326         strcat(filename, ".");
 327         strcat(filename, NUMBER_OF_ELEMENTS_FILE_EXT);
 328         if( (file = open(filename, O_RDONLY)) < 0) {
 329                 printf("Cannot read file %s\n", filename);exit(0);
 330         }
 331         read(file, &suffixArraySize, sizeof(uint));
 332         myicsa->suffixArraySize = suffixArraySize;
 333         printf("Number of indexed elements (suffix array size) = %d\n", suffixArraySize);
 334
 335         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA PSI COMPRIMIDA
 336         strcpy(filename, basename);
 337         strcat(filename, ".");
 338         strcat(filename, PSI_COMPRESSED_FILE_EXT);
 339         #ifdef PSI_HUFFMANRLE
 340                 myicsa->hcPsi = loadHuffmanCompressedPsi(filename);
 341         #endif
 342         #ifdef PSI_GONZALO
 343                 myicsa->gcPsi = loadGonzaloCompressedPsi(filename);
 344         #endif
 345         #ifdef PSI_DELTACODES
 346                 myicsa->dcPsi = loadDeltaCompressedPsi(filename);
 347         #endif
 348
 349         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA D
 350         strcpy(filename, basename);
 351         strcat(filename, ".");
 352         strcat(filename, D_FILE_EXT);
 353         if( (file = open(filename, O_RDONLY)) < 0) {
 354                 printf("Cannot read file %s\n", filename); exit(0);
 355         }
 356         myicsa->D = (uint *) malloc (sizeof(uint)*((suffixArraySize+31)/32));
 357         read(file, myicsa->D, sizeof(uint)*((suffixArraySize+31)/32));
 358         printf("Bit vector D loaded (%d bits)\n", suffixArraySize);
 359
 360         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O DIRECTORIO DE RANK1 PARA D
 361         strcpy(filename, basename);
 362         strcat(filename, ".");
 363         strcat(filename, D_RANK_DIRECTORY_FILE_EXT);
 364         myicsa->bD = loadBitmap(filename,myicsa->D,suffixArraySize);
 365         {       uint ns, nb;
 366                 ns = myicsa->bD->sSize;
 367                 nb = myicsa->bD->bSize;
 368                 myicsa->bD->data = myicsa->D;
 369                 printf("Rank1 Directory for D loaded (%d superblocks, %d blocks)\n", ns, nb);
 370         }
 371
 372         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA SAMPLES A
 373         strcpy(filename, basename);
 374         strcat(filename, ".");
 375         strcat(filename, SAMPLES_A_FILE_EXT);
 376         if( (file = open(filename, O_RDONLY)) < 0) {
 377                 printf("Cannot read file %s\n", filename); exit(0);
 378         }
 379         if( fstat(file, &f_stat) < 0) {
 380                 printf("Cannot read information from file %s\n", filename);     exit(0);
 381         }
 382         myicsa->samplesASize = (f_stat.st_size)/sizeof(uint);
 383         myicsa->samplesA = (uint *)malloc(sizeof(uint) * myicsa->samplesASize);
 384         read(file, myicsa->samplesA, sizeof(uint) * myicsa->samplesASize);
 385         printf("Suffix array samples loaded (%d samples)\n", myicsa->samplesASize);
 386
 387         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA BA
 388         strcpy(filename, basename);
 389         strcat(filename, ".");
 390         strcat(filename, BA_FILE_EXT);
 391         if( (file = open(filename, O_RDONLY)) < 0) {
 392                 printf("Cannot read file %s\n", filename); exit(0);
 393         }
 394         myicsa->BA = (uint *) malloc (sizeof(uint)*((suffixArraySize+31)/32));
 395         read(file, myicsa->BA, sizeof(uint)*((suffixArraySize+31)/32));
 396         printf("Bit vector BA loaded (%d bits)\n", suffixArraySize);
 397
 398         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O DIRECTORIO DE RANK1 PARA BA
 399         strcpy(filename, basename);
 400         strcat(filename, ".");
 401         strcat(filename, BA_RANK_DIRECTORY_FILE_EXT);
 402         myicsa->bBA = loadBitmap(filename,myicsa->BA,suffixArraySize);
 403         {       uint ns, nb;
 404                 ns = myicsa->bBA->sSize;
 405                 nb = myicsa->bBA->bSize;
 406                 myicsa->bBA->data = myicsa->BA;
 407                 printf("Rank1 Directory for BA loaded (%d superblocks, %d blocks)\n", ns, nb);
 408         }
 409
 410         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA SAMPLES A INVERSA
 411         strcpy(filename, basename);
 412         strcat(filename, ".");
 413         strcat(filename, SAMPLES_A_INV_FILE_EXT);
 414         if( (file = open(filename, O_RDONLY)) < 0) {
 415                 printf("Cannot read file %s\n", filename); exit(0);
 416         }
 417         if( fstat(file, &f_stat) < 0) {
 418                 printf("Cannot read information from file %s\n", filename);     exit(0);
 419         }
 420         myicsa->samplesAInvSize = (f_stat.st_size)/(sizeof(uint));
 421         myicsa->samplesAInv = (uint *)malloc(sizeof(uint) * myicsa->samplesAInvSize);
 422         read(file, myicsa->samplesAInv, sizeof(uint) * myicsa->samplesAInvSize);
 423         printf("Suffix array inverse samples loaded (%d samples)\n", myicsa->samplesAInvSize);
 424
 425         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O PERIODO DE MUESTREO DO ARRAY DE SUFIXOS E DA INVERSA
 426         strcpy(filename, basename);
 427         strcat(filename, ".");
 428         strcat(filename, SAMPLING_PERIOD_A_FILE_EXT);
 429         if( (file = open(filename, O_RDONLY)) < 0) {
 430                 printf("Cannot read file %s\n", filename); exit(0);
 431         }
 432         read(file, &(myicsa->T_A), sizeof(uint));
 433         read(file, &(myicsa->T_AInv), sizeof(uint));
 434         printf("Sampling A Period T = %d, Sampling A inv Period TInv = %d\n", myicsa->T_A, myicsa->T_AInv);
 435
 436         read(file, &(myicsa->psiSearchFactorJump), sizeof(uint));
 437         printf("Psi Bin Search Factor-Jump is = %d\n", myicsa->psiSearchFactorJump);
 438
 439         close(file);
 440         free(filename);
 441
 442         //return myicsa;
 443         *index = myicsa;
 444         return 0;
 445 }
 446
 447
 448 //uint destroyStructsCSA(ticsa *myicsa) {
 449 int freeIntIndex(void *index) {
 450         ticsa *myicsa = (ticsa *) index;
 451                 // Liberamos o espacio reservado
 452
 453         if (!myicsa) return 0;
 454
 455         uint total=0, totaltmp=0;
 456
 457         uint nbytes;sizeIntIndex(index, &nbytes);
 458
 459         total +=(sizeof (ticsa) * 1);;
 460
 461         #ifdef PSI_HUFFMANRLE
 462                 total+= totaltmp = myicsa->hcPsi.totalMem;
 463                 destroyHuffmanCompressedPsi(&(myicsa->hcPsi));
 464         #endif
 465         #ifdef PSI_GONZALO
 466                 total+= totaltmp = myicsa->gcPsi.totalMem;
 467                 destroyGonzaloCompressedPsi(&(myicsa->gcPsi));
 468         #endif
 469         #ifdef PSI_DELTACODES
 470                 total+= totaltmp = myicsa->dcPsi.totalMem;
 471                 destroyDeltaCodesCompressedPsi(&(myicsa->dcPsi));
 472         #endif
 473         printf("\n\t[destroying  SA: compressed PSI structure] ...Freed %u bytes... RAM",totaltmp);
 474
 475         free(myicsa->D);                        total+= totaltmp =  (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 476                                                         printf("\n\t[destroying  SA: D vector] ...Freed %u bytes... RAM",totaltmp);
 477         free(myicsa->samplesA);         total+= totaltmp = (sizeof(uint) * myicsa->samplesASize);
 478                                                         printf("\n\t[destroying  Samples A: A   ] ...Freed %u bytes... RAM",totaltmp);
 479         free(myicsa->samplesAInv);      total+= totaltmp =  (sizeof(uint) * myicsa->samplesAInvSize);
 480                                                         printf("\n\t[destroying  Samples AInv: A   ] ...Freed %u bytes... RAM",totaltmp);
 481                                                 printf("\n\t[destroying  rank bit D   ] ...Freed %u bytes... RAM",myicsa->bD->mem_usage);
 482         free(myicsa->BA);                       total+= totaltmp =  (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 483                                                         printf("\n\t[destroying  SA: BA vector] ...Freed %u bytes... RAM",totaltmp);
 484
 485                                                                 total += myicsa->bD->mem_usage;
 486         destroyBitmap(myicsa->bD);
 487                                                                 total += myicsa->bBA->mem_usage;
 488         destroyBitmap(myicsa->bBA);
 489
 490         printf("\n\t**** [the whole iCSA ocuppied ... %u bytes... RAM",total);
 491         printf("\n\t**** iCSA size = %d bytes ",nbytes);
 492         printf("\n");
 493
 494         free(myicsa);
 495
 496         return 0; //no error.
 497 }
 498
 499         // Shows detailed summary info of the self-index (memory usage of each structure)
 500 int printInfoIntIndex(void *index, const char tab[]) {
 501         ticsa *myicsa = (ticsa *) index;
 502         if (!myicsa) return 0;
 503
 504         uint structure, totalpsi, totalD, totalBD, totalSA,totalSAinv, totalBA,totalBBA;
 505
 506         structure=sizeof(ticsa);
 507
 508         #ifdef PSI_HUFFMANRLE
 509                 totalpsi = myicsa->hcPsi.totalMem;
 510         #endif
 511         #ifdef PSI_GONZALO
 512                 totalpsi = myicsa->gcPsi.totalMem;
 513         #endif
 514         #ifdef PSI_DELTACODES
 515                 totalpsi = myicsa->dcPsi.totalMem;
 516         #endif
 517
 518         totalD   = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 519         totalBD  = myicsa->bD->mem_usage;
 520         totalSA  = (sizeof(uint) * myicsa->samplesASize);
 521         totalSAinv = (sizeof(uint) * myicsa->samplesAInvSize);
 522         totalBA  = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 523         totalBBA = myicsa->bBA->mem_usage;
 524
 525         uint nbytes; sizeIntIndex(index, &nbytes); //whole self-index
 526
 527         printf("\n ===================================================:");
 528         printf("\n%sSummary Self-index on integers (icsa) layer:",tab);
 529         printf("\n%s   icsa structure = %d bytes",tab, structure);
 530         printf("\n%s   psi         = %8d bytes",tab, totalpsi);
 531         printf("\n%s   D (bitmap)  = %8d bytes",tab, totalD);
 532         printf("\n%s   rank for D  = %8d bytes",tab, totalBD);
 533         printf("\n%s   SA(sampled) = %8d bytes",tab, totalSA);
 534         printf("\n%s   SAinv(samp) = %8d bytes",tab, totalSAinv);
 535         printf("\n%s   BA (bitmap) = %8d bytes",tab, totalBA);
 536         printf("\n%s   rank for BA = %8d bytes",tab, totalBBA);
 537         printf("\n%sTotal = ** %9d bytes (in RAM) ** ",tab, nbytes);
 538         printf("\n");
 539
 540         return 0; //no error.
 541 }
 542
 543
 544 // OPERACIONS DO CSA
 545
 546 // BUSCA BINARIA SOBRE MOSTRAS + 2 BUSCAS EXPONENCIAIS + 2 BUSCAS BINARIAS
 547 // 1º Busca binaria sobre o array de sufixos, elexindo como pivote un múltiplo de bin_search_psi_skip_interval (que orixinalmente foi pensado para igualar co valor de Psi).
 548 // 2º Esta busca pode deterse por:
 549 //      a) O pivote repítese entre dúas iteracións -> As ocorrencias están entre o pivote e a seguinte mostra (pivote + bin_search_psi_skip_interval) -> facemos dúas buscas binarias
 550 //      b) O pivote é unha ocorrencia do patrón -> Faise unha busca exponencial sobre mostras hacia a esquerda e outra hacia a dereita, ata atopar a unha mostra á esquerda e outra
 551 //      á dereita do intervalo de ocorrencias. Entre cada unha destas e a inmediatamente anterior da busca exponencial, faise unha busca binaria para atopar os extremos do intervalo.
 552
 553 int countIntIndex(void *index, uint *pattern, uint length, ulong *numocc, ulong *left, ulong *right){
 554         //unsigned int countCSA(ticsa *myicsa, uint *pattern, uint patternSize, uint *left, uint *right) {
 555
 556         uint patternSize = length;
 557         ticsa *myicsa = (ticsa *) index;
 558
 559         register unsigned long l, r, i;
 560         register long comp, p, previousP;
 561         //register unsigned int l, r, i;
 562         //register int comp, p, previousP;
 563         register uint bin_search_psi_skip_interval = myicsa->psiSearchFactorJump;
 564
 565         //fprintf(stderr,"\n psiSearchFactor = %d",myicsa->psiSearchFactorJump);
 566
 567         l = 0;
 568         r = (myicsa->suffixArraySize+bin_search_psi_skip_interval-2)/bin_search_psi_skip_interval*bin_search_psi_skip_interval;
 569         p = ((l+r)/2)/bin_search_psi_skip_interval * bin_search_psi_skip_interval;
 570         previousP = 0;
 571
 572         // BUSCA BINARIA SOBRE MOSTRAS
 573         while( (p != previousP) && (comp = SadCSACompare(myicsa, pattern, patternSize, p)) ) {
 574                 if(comp > 0) l = p;
 575                 else r = p;
 576                 previousP = p;
 577                 p = ((l+r)/2)/bin_search_psi_skip_interval*bin_search_psi_skip_interval;
 578         }
 579
 580         if(p==previousP) {
 581
 582                 // BUSCA BINARIA ENTRE O PIVOTE E A SEGUINTE MOSTRA
 583                 l = previousP;
 584                 r = previousP+bin_search_psi_skip_interval;
 585                 if(r > myicsa->suffixArraySize) r = myicsa->suffixArraySize - 1;
 586                 while(l < r) {
 587                         p = (l+r)/2;
 588                         if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
 589                         else l = p+1;
 590                 }
 591
 592                 if(SadCSACompare(myicsa, pattern, patternSize, r)) {
 593                         *left = l;
 594                         *right = r;
 595                         //return 0;
 596                         *numocc = 0;
 597                         return 0; //no error.
 598                 }
 599                 *left = r;
 600
 601                 l = previousP;
 602                 r = previousP+bin_search_psi_skip_interval;
 603                 if(r > myicsa->suffixArraySize) r = myicsa->suffixArraySize - 1;
 604                 while(l < r) {
 605                         p = (l+r+1)/2;
 606                         if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
 607                         else r = p-1;
 608                 }
 609                 *right = l;
 610
 611         } else {
 612
 613                 previousP = p;  // En previousP poñemos o p atopado na busca sobre as mostras
 614
 615                 // BUSCA EXPONENCIAL HACIA ATRÁS
 616                 i = 1;
 617                 p -= bin_search_psi_skip_interval;
 618                 while(p>0 && !SadCSACompare(myicsa, pattern, patternSize, p)) {
 619                         i<<=1;
 620                         p = previousP-(i*bin_search_psi_skip_interval);
 621                 }
 622                 // Busca binaria entre as duas ultimas mostras da exponencial
 623                 if(previousP > i*bin_search_psi_skip_interval) l = previousP-(i*bin_search_psi_skip_interval);
 624                 else l=0;
 625                 i>>=1;
 626                 r = previousP-(i*bin_search_psi_skip_interval);
 627                 while(l < r) {
 628                         p = (l+r)/2;
 629                         if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
 630                         else l = p+1;
 631                 }
 632                 *left = r;
 633
 634                 // BUSCA EXPONENCIAL HACIA ADIANTE
 635                 i = 1;
 636                 p = previousP+bin_search_psi_skip_interval;
 637                 while(p<myicsa->suffixArraySize && !SadCSACompare(myicsa, pattern, patternSize, p)) {
 638                         i<<=1;
 639                         p = previousP+(i*bin_search_psi_skip_interval);
 640                 }
 641                 // Busca binaria entre as duas ultimas mostras da exponencial
 642                 if(p < myicsa->suffixArraySize) r = previousP+(i*bin_search_psi_skip_interval);
 643                 else r = myicsa->suffixArraySize-1;
 644                 i>>=1;
 645                 l = previousP+(i*bin_search_psi_skip_interval);
 646                 while(l < r) {
 647                         p = (l+r+1)/2;
 648                         if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
 649                         else r = p-1;
 650                 }
 651                 *right = l;
 652         }
 653
 654         //return *right-*left+1;
 655         *numocc = (uint) *right-*left+1;
 656         return 0; //no error
 657 }
 658
 659 // Version inicial de busca binaria
 660 unsigned int countCSABin(ticsa *myicsa, uint *pattern, uint patternSize, uint *left, uint *right) {
 661         register ulong l, r, p;
 662
 663         l = 0;
 664         r = myicsa->suffixArraySize-1;
 665
 666         while(l < r) {
 667                 p = (l+r)/2;
 668                 if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
 669                 else l = p+1;
 670         }
 671
 672         // SE SON DISTINTOS O PATRON NON APARECE NO TEXTO E DEVOLVEMOS 0
 673         if(SadCSACompare(myicsa, pattern, patternSize, r)) {
 674                 *left = l;
 675                 *right = r;
 676                 return 0;
 677         }
 678
 679         // Almacenamos o limite esquerdo
 680         *left = r;
 681
 682         // SE SON IGUALES (O PATRON APARECE NO TEXTO), BUSCAMOS AGORA O LIMITE DEREITO, QUE ALMACENAREMOS EN right
 683         // NOTA: INICIAMOS A BUSQUEDA A PARTIR DO ESQUERDO...
 684         l = r;
 685         r = myicsa->suffixArraySize-1;
 686
 687         while(l < r) {
 688                 p = (l+r+1)/2;
 689                 if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
 690                 else r = p-1;
 691         }
 692
 693         // Gardamos o limite dereito
 694         *right = l;
 695
 696         return (uint) *right-*left+1;
 697 }
 698
 699 int locateIntIndex(void *index, uint *pattern, uint length, ulong **occ, ulong *numocc) {
 700         //unsigned int *locateCSA(ticsa *myicsa, uint *pattern, uint patternSize, uint *occ) {
 701
 702         ticsa *myicsa = (ticsa *) index;
 703         uint patternSize = length;
 704         ulong *positions;
 705         ulong occurrences;
 706         register ulong left, right;
 707
 708                 //occurrences = countCSA(myicsa, pattern, patternSize, &left, &right);
 709         int err;
 710         err = countIntIndex((void *) myicsa, pattern, patternSize, &occurrences, &left, &right);
 711         *numocc = occurrences;
 712
 713         if (occurrences) {
 714                 register ulong idx = 0;
 715                 positions = (ulong*) malloc(sizeof(ulong) * occurrences);
 716                 while(left<=right) positions[idx++] = A(myicsa,left++);
 717
 718                 *occ = positions;
 719                 return 0;
 720                 //return positions;
 721         }
 722
 723         (*occ)=NULL;
 724         return 0; //no error, but no occurrences.
 725
 726         //return NULL;
 727 }
 728
 729 // Devolve o enteiro do texto que ocupa a posicion dada,
 730 // e fixa o estado para poder seguir obtendo os seguintes enteiros con displayNext();
 731
 732 int displayIntIndex(void *index, ulong position, uint *value){
 733         //uint displayCSA(ticsa *myicsa, uint position) {
 734         ticsa *myicsa = (ticsa *) index;
 735         if (position == (myicsa->displayCSAPrevPosition +1)) {
 736                 myicsa->displayCSAPrevPosition = position;
 737                 //return displayCSANext(myicsa);
 738                 *value = displayCSANext(myicsa);
 739         }
 740         else {
 741                 myicsa->displayCSAPrevPosition = position;
 742                 //return displayCSAFirst(myicsa, position);
 743                 *value = displayCSAFirst(myicsa, position);
 744         }
 745         return 0; //no error
 746 }
 747
 748
 749 /**********************************************************************/
 750
 751 // Devolve o enteiro do texto que ocupa a posicion dada, e fixa o estado
 752 // para poder seguir obtendo os seguintes enteiros con displayNext();
 753 uint displayCSAFirst(ticsa *myicsa, uint position) {
 754
 755         register uint positionAux, index;
 756         register uint T_AInv = myicsa->T_AInv;
 757
 758         positionAux = myicsa->samplesAInv[position / T_AInv];
 759         for(index = 0; index < position%T_AInv; index++) {
 760                 #ifdef PSI_HUFFMANRLE
 761                         positionAux=getHuffmanPsiValue(&(myicsa->hcPsi),positionAux);
 762                 #endif
 763                 #ifdef PSI_GONZALO
 764                         positionAux=getGonzaloPsiValue(&(myicsa->gcPsi),positionAux);
 765                 #endif
 766                 #ifdef PSI_DELTACODES
 767                         positionAux=getDeltaPsiValue(&(myicsa->dcPsi),positionAux);
 768                 #endif
 769         }
 770
 771         // Fijamos a variable global para a chamada a displayNext
 772         myicsa->displayCSAState = positionAux;
 773
 774         //      return rank1(D, Dir, positionAux) - 1;
 775         return rank(myicsa->bD, positionAux) - 1;
 776 }
 777
 778
 779 // Devolve o seguinte enteiro do texto (a partir do estado)
 780 unsigned int displayCSANext(ticsa *myicsa) {
 781         #ifdef PSI_HUFFMANRLE
 782                 myicsa->displayCSAState=getHuffmanPsiValue(&(myicsa->hcPsi),myicsa->displayCSAState);
 783         #endif
 784         #ifdef PSI_GONZALO
 785                 myicsa->displayCSAState = getGonzaloPsiValue(&(myicsa->gcPsi),myicsa->displayCSAState);
 786         #endif
 787         #ifdef PSI_DELTACODES
 788                 myicsa->displayCSAState = getDeltaPsiValue(&(myicsa->dcPsi),myicsa->displayCSAState);
 789         #endif
 790         return rank(myicsa->bD, myicsa->displayCSAState) - 1;
 791 }
 792
 793
 794 // Mostra as estructuras creadas
 795 void showStructsCSA(ticsa *myicsa) {
 796
 797         unsigned int index;
 798
 799         // ESTRUCTURAS PARA CSA
 800         printf("Basic CSA structures:\n\n");
 801
 802         // VALORES DA FUNCI�N PSI (decodificando)
 803         printf("\tPSI: (Sampling period = %d)\n", myicsa->T_Psi);
 804         for(index=0; index < myicsa->suffixArraySize; index++)
 805                 #ifdef PSI_HUFFMANRLE
 806                         printf("\tPsi[%d] = %d\n", index, getHuffmanPsiValue(&(myicsa->hcPsi),index));
 807                 #endif
 808                 #ifdef PSI_GONZALO
 809                         printf("\tPsi[%d] = %d\n", index, getGonzaloPsiValue(&(myicsa->gcPsi),index));
 810                 #endif
 811                 #ifdef PSI_DELTACODES
 812                         printf("\tPsi[%d] = %d\n", index, getDeltaPsiValue(&(myicsa->dcPsi),index));
 813                 #endif
 814         printf("\n");
 815
 816         // VECTOR D DE SADAKANE CO DIRECTORIO DE RANK ASOCIADO
 817         printf("\tD = ");
 818         showBitVector(myicsa->D, myicsa->suffixArraySize);
 819         printf("\n\nSuperbloques de D:\n");
 820         {       uint ns;
 821                 uint nb;
 822                 ns = myicsa->bD->sSize;
 823                 nb= myicsa->bD->bSize;
 824                 for(index=0; index<ns; index++) {
 825                         //printf("\tDs[%d] = %d\n", index, Dir.Ds[index]);
 826                         printf("\tDs[%d] = %d\n", index, myicsa->bD->sdata[index]);
 827                 }
 828                 printf("\nBloques de D:\n");
 829
 830                 for(index=0; index<nb; index++) {
 831                         //printf("\tDb[%d] = %d\n", index, Dir.Db[index]);
 832                         printf("\tDb[%d] = %d\n", index, myicsa->bD->bdata[index]);
 833                 }
 834                 printf("\n\n");
 835         }
 836         // ESTRUCTURAS PARA ACCEDER O ARRAY DE SUFIXOS E A SUA INVERSA
 837         printf("Suffix Array Sampling Structures: (Sampling period = %d)\n", myicsa->T_A);
 838         printf("\tSuffix Array Samples:\n");
 839         for(index=0; index < myicsa->samplesASize; index++)
 840                 printf("\tSamplesA[%d] = %d\n", index, myicsa->samplesA[index]);
 841         printf("\n");
 842         printf("\tInverse Suffix Array Samples:\n");
 843         for(index=0; index < myicsa->samplesASize; index++)
 844                 printf("\tSamplesAInv[%d] = %d\n", index, myicsa->samplesAInv[index]);
 845         printf("\n");
 846
 847 }
 848
 849
 850 // Comparacion de Sadakane entre un patron (pattern) y el sufijo en la posicion p del array de sufijos
 851 // IMPORTANTE EVITAR ULTIMA CHAMADA A PSI
 852 int SadCSACompare(ticsa *myicsa, uint *pattern, uint patternSize, uint p) {
 853
 854         register unsigned int j, i, currentInteger, diff;
 855
 856         i = p;
 857         j = 0;
 858
 859         while(1) {
 860                 currentInteger = rank(myicsa->bD, i) - 1;
 861                 diff = pattern[j++] - currentInteger;
 862                 if(diff) return diff;
 863                 if(j == patternSize) return 0;
 864                 else
 865                         #ifdef PSI_HUFFMANRLE
 866                                 i=getHuffmanPsiValue(&(myicsa->hcPsi),i);
 867                         #endif
 868                         #ifdef PSI_GONZALO
 869                                 i=getGonzaloPsiValue(&(myicsa->gcPsi),i);
 870                         #endif
 871                         #ifdef PSI_DELTACODES
 872                                 i=getDeltaPsiValue(&(myicsa->dcPsi),i);
 873                         #endif
 874         }
 875
 876 }
 877
 878
 879 // Acceso a array de sufixos A
 880 inline uint A(ticsa *myicsa, uint position) {
 881
 882         register uint timesPsi, sampleValue;
 883         register uint T_A = myicsa->T_A;
 884
 885         uint proba = position;
 886
 887         timesPsi = 0;
 888         while(!bitget(myicsa->BA, position)) {
 889
 890                 #ifdef PSI_HUFFMANRLE
 891                         position=getHuffmanPsiValue(&(myicsa->hcPsi),position);
 892                 #endif
 893                 #ifdef PSI_GONZALO
 894                         position=getGonzaloPsiValue(&(myicsa->gcPsi),position);
 895                 #endif
 896                 #ifdef PSI_DELTACODES
 897                         position=getDeltaPsiValue(&(myicsa->dcPsi),position);
 898                 #endif
 899                 timesPsi++;
 900
 901         }
 902         sampleValue = myicsa->samplesA[rank(myicsa->bBA, position)-1];
 903
 904         return sampleValue - timesPsi;
 905
 906 }
 907
 908
 909 // Acceso 'a inversa do array de sufixos
 910 inline uint inverseA(ticsa *myicsa, uint offset) {
 911
 912         register uint index, inverseValue;
 913         register uint T_AInv = myicsa->T_AInv;
 914
 915         inverseValue = myicsa->samplesAInv[offset/T_AInv];
 916         for(index=0; index<(offset%T_AInv); index++)
 917                 #ifdef PSI_HUFFMANRLE
 918                         inverseValue=getHuffmanPsiValue(&(myicsa->hcPsi),inverseValue);
 919                 #endif
 920                 #ifdef PSI_GONZALO
 921                    inverseValue = getGonzaloPsiValue(&(myicsa->gcPsi),inverseValue);
 922                 #endif
 923                 #ifdef PSI_DELTACODES
 924                         inverseValue = getDeltaPsiValue(&(myicsa->dcPsi),inverseValue);
 925                 #endif
 926         return inverseValue;
 927
 928 }
 929
 930 // Initializes the parameters of the index.
 931 uint parametersCSA(ticsa *myicsa, char *build_options){
 932         char delimiters[] = " =;";
 933         int j,num_parameters;
 934         char ** parameters;
 935         int ssA,ssAinv,ssPsi,nsHuff,psiSearchFactor;
 936
 937         ssA    = DEFAULT_A_SAMPLING_PERIOD;
 938         ssAinv = DEFAULT_A_INV_SAMPLING_PERIOD;
 939         ssPsi  = DEFAULT_PSI_SAMPLING_PERIOD;
 940         nsHuff = DEFAULT_nsHUFF;
 941         psiSearchFactor = DEFAULT_PSI_BINARY_SEARCH_FACTOR;
 942
 943         if (build_options != NULL) {
 944         parse_parameters(build_options,&num_parameters, &parameters, delimiters);
 945         for (j=0; j<num_parameters;j++) {
 946
 947                 if ((strcmp(parameters[j], "sA") == 0 ) && (j < num_parameters-1) ) {
 948                         ssA=atoi(parameters[j+1]);
 949                 }
 950                 if ((strcmp(parameters[j], "sAinv") == 0 ) && (j < num_parameters-1) ) {
 951                         ssAinv=atoi(parameters[j+1]);
 952                 }
 953                 if ((strcmp(parameters[j], "sPsi") == 0 ) && (j < num_parameters-1) ) {
 954                         ssPsi=atoi(parameters[j+1]);
 955                 }
 956                 if ((strcmp(parameters[j], "nsHuff") == 0 ) && (j < num_parameters-1) ) {
 957                         nsHuff=atoi(parameters[j+1]);
 958                         nsHuff *=1024;
 959                 }
 960                 if ((strcmp(parameters[j], "psiSF") == 0 ) && (j < num_parameters-1) ) {
 961                         psiSearchFactor=atoi(parameters[j+1]);
 962                 }
 963                 j++;
 964         }
 965         free_parameters(num_parameters, &parameters);
 966         }
 967
 968         myicsa->T_A = ssA;
 969         myicsa->T_AInv = ssAinv;
 970         myicsa->T_Psi = ssPsi;
 971         myicsa->tempNSHUFF = nsHuff;
 972         myicsa->psiSearchFactorJump = psiSearchFactor * ssPsi;
 973
 974         printf("\n\t parameters for iCSA: sampleA=%d, sampleAinv=%d, samplePsi=%d",ssA,ssAinv,ssPsi);
 975         printf("\n\t              : nsHuff=%d, psiSearchFactor = %d --> jump = %d", nsHuff,psiSearchFactor, myicsa->psiSearchFactorJump);
 976 }