swcsa/intIndex/psiDeltaCode.c

   1 #include "psiDeltaCode.h"
   2
   3 void destroyDeltaCodesCompressedPsi(DeltaCompressedPsi *compressedPsi) {
   4         free(compressedPsi->deltaCodes);
   5         free(compressedPsi->samples);
   6         free(compressedPsi->pointers);
   7 }
   8
   9
  10 DeltaCompressedPsi deltaCompressPsi(unsigned int *Psi, unsigned int psiSize, unsigned int T) {
  11
  12         DeltaCompressedPsi cPsi;
  13
  14         int numberOfSamples;
  15         register int diff, deltaCodesPos;
  16         register unsigned int k, p, aux, diffpositive, code, index;
  17         unsigned int samplesIndex, codeLenght, currentInput, wordsDeltaCodes, totalSize;
  18         unsigned int *deltaCodes;
  19         unsigned int *samples;
  20         unsigned int *pointers;
  21
  22         // Auxiliar para deltaCodes (estimamos como espacio maximo o do array de sufixos)
  23         unsigned int *deltaCodesAux;
  24
  25         // Calculamos o mellor valor para negativeGap <= 64
  26         unsigned int negativeGap;
  27         register unsigned int maxNegativeBits = 0;
  28         k = psiSize;
  29         while(k) {
  30                 k >>= 1;
  31                 maxNegativeBits++;
  32         }
  33         if(maxNegativeBits<=26) negativeGap = 64;
  34         else negativeGap = 1<<(32-maxNegativeBits);
  35
  36         // Reservamos espacio para as estructuras
  37         numberOfSamples = (psiSize + T - 1) / T;
  38         samples = (unsigned int *)malloc(sizeof(int)*numberOfSamples);
  39         pointers = (unsigned int *)malloc(sizeof(int)*numberOfSamples);
  40
  41         deltaCodesAux = (unsigned int *)malloc(sizeof(int)*psiSize);
  42         for(index=0; index<psiSize; index++) deltaCodesAux[index] = 0;
  43
  44         samplesIndex = 0;
  45         deltaCodesPos = 0;
  46         for(index=0; index<psiSize; index++) {
  47
  48                 if(index % T) {
  49
  50                         diff = Psi[index] - currentInput;
  51                         currentInput = Psi[index];
  52
  53                         // Calculamos o codigo correspondente
  54                         if(diff>0) diffpositive = (negativeGap*diff-1)/(negativeGap-1);
  55                         else diffpositive = -negativeGap*diff;
  56
  57                         k = 0;
  58                         aux = diffpositive;
  59                         while(aux) {
  60                                 aux >>= 1;
  61                                 k++;
  62                         }
  63                         aux = k;
  64                         p = 0;
  65                         while(aux) {
  66                                 aux >>= 1;
  67                                 p++;
  68                         }
  69
  70                         code = diffpositive & ((1<<(k-1))-1);
  71                         codeLenght = 2*p+k-2;
  72
  73                         // Primeiro metemos os p-1 0's iniciais
  74                         deltaCodesPos += p-1;
  75
  76                         // Agora metemos os p bits de k
  77                         if( ((deltaCodesPos%32) + p) > 32 ) {
  78                                 deltaCodesAux[deltaCodesPos/32] |= (k>>((deltaCodesPos%32)+p-32));
  79                                 deltaCodesAux[deltaCodesPos/32+1] = (k<<(64-(deltaCodesPos%32)-p));
  80                         } else {
  81                                 deltaCodesAux[deltaCodesPos/32] |= (k<<(32-p-(deltaCodesPos%32)));
  82                         }
  83                         deltaCodesPos += p;
  84
  85                         // Por �ltimo metemos os k-1 bits de code (sen o 1 inicial)
  86                         if( ((deltaCodesPos%32) + (k-1)) > 32 ) {
  87                                 deltaCodesAux[deltaCodesPos/32] |= (code>>((deltaCodesPos%32)+(k-1)-32));
  88                                 deltaCodesAux[deltaCodesPos/32+1] = (code<<(64-(deltaCodesPos%32)-(k-1)));
  89                         } else {
  90                                 deltaCodesAux[deltaCodesPos/32] |= (code<<(32-(k-1)-(deltaCodesPos%32)));
  91                         }
  92                         deltaCodesPos += k-1;
  93
  94                 } else {
  95                         samples[samplesIndex] = Psi[index];
  96                         pointers[samplesIndex++] = deltaCodesPos;
  97                         currentInput = Psi[index];
  98                 }
  99
 100         }
 101
 102         // Ahora que xa sabemos o espacio necesario para os deltaCodes, reservamolo e liberamos a estructura auxiliar
 103         wordsDeltaCodes = (deltaCodesPos+31)/32;
 104         deltaCodes = (unsigned int *)malloc(sizeof(int)*wordsDeltaCodes);
 105         for(index=0;index<wordsDeltaCodes;index++) deltaCodes[index] = deltaCodesAux[index];
 106         free(deltaCodesAux);
 107
 108         totalSize = sizeof(int)*wordsDeltaCodes + 2*sizeof(int)*numberOfSamples + 4*sizeof(int);
 109         printf("\n\tCompressed Psi size = %d bytes\n", totalSize);
 110
 111         // Asignamos os valores a cPsi e devolvemolo
 112         cPsi.T = T;
 113         cPsi.negativeGap = negativeGap;
 114         cPsi.deltaCodesSize = wordsDeltaCodes;
 115         cPsi.deltaCodes = deltaCodes;
 116         cPsi.numberOfSamples = numberOfSamples;
 117         cPsi.samples = samples;
 118         cPsi.pointers = pointers;
 119         cPsi.totalMem = totalSize;
 120
 121         return cPsi;
 122
 123 }
 124
 125
 126 int getDeltaPsiValue(DeltaCompressedPsi *cPsi, unsigned int position) {
 127
 128         int result;
 129         register unsigned int code, aux, pointerAux, mask, pointer, toDecode, p, k;
 130
 131         // Collemos a mostra inmediatamente inferior, e o punteiro o array de codigos
 132         // pointer = punteiro absoluto sobre deltaCodes
 133         result = cPsi->samples[position/cPsi->T];
 134         pointer = cPsi->pointers[position/cPsi->T];
 135
 136         // Calculamos o numero de codigos a decodificar a partir da mostra
 137         toDecode = position % cPsi->T;
 138
 139         while(toDecode--) {
 140
 141                 // Collemos o n�mero ceros iniciais
 142                 // Po�emos o inicio do c�digo nun enteiro (code) alineado a esquerda
 143                 // Non importa que non colla todo o c�digo, pero si temos asegurado que
 144                 // colle p e k (k<=32 (6bits), p<=5bits)
 145                 code = (cPsi->deltaCodes[pointer/32] << (pointer%32)) |
 146                            ((pointer%32 != 0) * (cPsi->deltaCodes[pointer/32+1] >> (32-(pointer%32))));
 147
 148                 //Ahora contamos o n�mero de ceros (p) que hai nas posicions da esquerda de code
 149                 p = 1;
 150                 while(!(code & 0x80000000)) {
 151                         code <<= 1;
 152                         p++;
 153                 }
 154
 155                 // Ahora calculamos o numero de digitos da representacion binaria do codigo (k)
 156                 k = code >> (32-p);
 157
 158                 // Actualizamos o punteiro global sobre deltaCodes
 159                 pointer += 2*p-1;
 160
 161                 // Po�emos a representacion binaria do codigo nun enteiro (code) alineado a esquerda
 162                 code = (cPsi->deltaCodes[pointer/32] << (pointer%32)) |
 163                            ((pointer%32 != 0) * (cPsi->deltaCodes[pointer/32+1] >> (32-(pointer%32))));
 164                 code = ((code >> 1) | 0x80000000) >> (32-k);
 165                 pointer += k-1;
 166
 167                 // Bixecci�n
 168                 if(code % cPsi->negativeGap) result += (code - (code/cPsi->negativeGap));
 169                 else result -= code/cPsi->negativeGap;
 170
 171         }
 172
 173         return result;
 174
 175 }
 176
 177
 178 void storeDeltaCompressedPsi(DeltaCompressedPsi *compressedPsi, char *filename) {
 179
 180         int file;
 181
 182         if( (file = open(filename, O_WRONLY|O_CREAT, 0700)) < 0) {
 183                 printf("Cannot open file %s\n", filename);
 184                 exit(0);
 185         }
 186         write(file, &(compressedPsi->T), sizeof(int));
 187         write(file, &(compressedPsi->negativeGap), sizeof(int));
 188         write(file, &(compressedPsi->deltaCodesSize), sizeof(int));
 189         write(file, compressedPsi->deltaCodes, compressedPsi->deltaCodesSize*sizeof(int));
 190         write(file, &(compressedPsi->numberOfSamples), sizeof(int));
 191         write(file,     compressedPsi->samples, compressedPsi->numberOfSamples*sizeof(int));
 192         write(file,     compressedPsi->pointers, compressedPsi->numberOfSamples*sizeof(int));
 193         write(file, &(compressedPsi->totalMem), sizeof(int));
 194
 195         close(file);
 196
 197 }
 198
 199
 200 DeltaCompressedPsi loadDeltaCompressedPsi(char *filename) {
 201
 202         DeltaCompressedPsi compressedPsi;
 203
 204         int file;
 205
 206         if( (file = open(filename, O_RDONLY)) < 0) {
 207                 printf("Cannot read file %s\n", filename);
 208                 exit(0);
 209         }
 210         read(file, &(compressedPsi.T), sizeof(int));
 211         read(file, &(compressedPsi.negativeGap), sizeof(int));
 212         read(file, &(compressedPsi.deltaCodesSize), sizeof(int));
 213         compressedPsi.deltaCodes = (unsigned int *)malloc(compressedPsi.deltaCodesSize*sizeof(int));
 214         read(file, compressedPsi.deltaCodes, compressedPsi.deltaCodesSize*sizeof(int));
 215         read(file, &(compressedPsi.numberOfSamples), sizeof(int));
 216         compressedPsi.samples = (unsigned int *)malloc(compressedPsi.numberOfSamples*sizeof(int));
 217         compressedPsi.pointers = (unsigned int *)malloc(compressedPsi.numberOfSamples*sizeof(int));
 218         read(file, compressedPsi.samples, compressedPsi.numberOfSamples*sizeof(int));
 219         read(file, compressedPsi.pointers, compressedPsi.numberOfSamples*sizeof(int));
 220         read(file, &(compressedPsi.totalMem), sizeof(int));
 221
 222         close(file);
 223
 224         return compressedPsi;
 225
 226 }