4 #include "../utils/huff.h"
7 Compresion de PSI utilizando codificación incremental e RLE para os runs.
9 Utilizamos códigos Huffman, entre os que distinguimos 4 grupos.
11 G1: Incrementos frecuentes: Entre 2 e Total - 32 negativos - 32 grandes - (máxima lonxitude dun Run == periodo de muestreo - 1))
12 G2: Código que representa que hai un run e a súa lonxitude (periodo de muestreo códigos)
13 G3: Numeros negativos (32 caracteres de escape, que representan a lonxitude da representación binaria do valor absoluto do negativo)
14 G4: Numeros grandes, maiores que os de G1 (32 caracteres de escape representando novamente a lonxitude da representación binaria do seu valor)
16 Os de G1 obtéñense directamente, tras decodificar Huffman.
17 Os de G2 transfórmanse nunha run da lonxitude obtida tras decodificar con Huffman.
18 Os de G3 van seguidos da representación binaria do valor absoluto do seu número.
19 Os de G4 van seguidos da súa representación binaria.
22 // ESTRUCTURA DE PSI COMPRIMIDA
24 unsigned int T; // Periodo de muestreo de PSI
25 THuff diffsHT; // Arbol de Huffman (codifica stream)
26 unsigned int nS; // Numero de simbolos para Huffman
27 unsigned int numberOfSamples;
28 unsigned int sampleSize; // Bits que ocupa cada mostra
29 unsigned int *samples; // Vector de mostras
30 unsigned int pointerSize; // Bits que ocupa cada punteiro
31 unsigned int *samplePointers; // Punteiros das mostras a stream
32 unsigned int streamSize; // Bits que ocupa stream
33 unsigned int *stream; // Secuencia Huffman + RLE
34 unsigned int totalMem; // the size in bytes used;
35 } HuffmanCompressedPsi;
38 // PROTOTIPOS DE FUNCIÓNS
40 // Crea as estructuras de Psi comprimida:
42 // Psi: Funcion Psi original
43 // psiSize: Numero de elementos de Psi
44 // T: Periodo de muestreo en Psi
45 // nS: Numero de simbolos que se utilizaran no arbol de Huffman
47 // Devolve unha estructura CompressedPSI que representa a Psi comprimida
48 HuffmanCompressedPsi huffmanCompressPsi(unsigned int *Psi, unsigned int psiSize, unsigned int T, unsigned int nS);
50 // Obtén un valor de Psi
52 // cPsi: A estructura que representa a Psi comprimida
53 // position: A posicion da que queremos obter o valor de Psi
54 unsigned int getHuffmanPsiValue(HuffmanCompressedPsi *cPsi, unsigned int position);
56 void storeHuffmanCompressedPsi(HuffmanCompressedPsi *compressedPsi, char *filename);
57 HuffmanCompressedPsi loadHuffmanCompressedPsi(char *filename);
59 //frees the memory used.
60 void destroyHuffmanCompressedPsi(HuffmanCompressedPsi *compressedPsi);
64 //// IMPLEMENTACIÓN DAS FUNCIÓNS
66 //void destroyHuffmanCompressedPsi(HuffmanCompressedPsi *compressedPsi) {
67 // freeHuff(compressedPsi->diffsHT);
68 // free(compressedPsi->samples);
69 // free(compressedPsi->samplePointers);
70 // free (compressedPsi->stream);
73 //HuffmanCompressedPsi huffmanCompressPsi(unsigned int *Psi, unsigned int psiSize, unsigned int T, unsigned int nS) {
75 // HuffmanCompressedPsi cPsi;
77 // int absolute_value;
78 // register unsigned int index, ptr, samplesPtr, samplePointersPtr;
79 // unsigned int runLenght, binaryLenght;
82 // unsigned int *huffmanDst;
84 // // Estructuras da funcion comprimida (para logo asignar)
85 // // Tamén se podian almacenar directamente
87 // unsigned int numberOfSamples;
88 // unsigned int *samples;
89 // unsigned int sampleSize;
90 // unsigned int *samplePointers;
91 // unsigned int pointerSize;
92 // unsigned int *stream;
93 // unsigned int streamSize;
95 // // Variables que marcan os intervalos dentro do vector de frecuencias
96 // unsigned int runLenghtStart = nS - 64 - T; // Inicio das Runs
97 // unsigned int negStart = nS - 64; // Inicio dos Negativos
98 // unsigned int bigStart = nS - 32; // Inicio dos Grandes (>runLenghtStart)
100 // // Para estadistica
101 // unsigned int totalSize;
103 // // Reservamos espacio para a distribución de valores de Psi
104 // huffmanDst = (unsigned int *)malloc(sizeof(int)*nS);
105 // for(index=0;index<nS;index++) huffmanDst[index]=0;
107 // // Inicializamos diferencias
108 // diffs = (int *)malloc(sizeof(int)*psiSize);
110 // for(index=1; index<psiSize; index++)
111 // diffs[index] = Psi[index] - Psi[index-1];
113 // // Calculamos a distribucion de frecuencias
115 // for(index=0; index<psiSize; index++) {
119 // if(diffs[index]==1) {
121 // } else { // Non estamos nun run
123 // huffmanDst[runLenght+runLenghtStart]++;
126 // if(diffs[index]>1 && diffs[index]<runLenghtStart)
127 // huffmanDst[diffs[index]]++;
129 // if(diffs[index]<0) { // Valor negativo
130 // absolute_value = -diffs[index];
131 // binaryLenght = bits(absolute_value);
132 // huffmanDst[binaryLenght+negStart-1]++;
133 // } else { // Valor grande >= 128
134 // absolute_value = diffs[index];
135 // binaryLenght = bits(absolute_value);
136 // huffmanDst[binaryLenght+bigStart-1]++;
140 // } else { // Rompemos o run porque atopamos unha mostra
142 // huffmanDst[runLenght+runLenghtStart]++;
149 // if(runLenght) huffmanDst[runLenght+runLenghtStart]++;
151 // // Creamos o arbol de Huffman
152 // diffsHT = createHuff(huffmanDst,nS-1,UNSORTED);
154 // // Calculamos o espacio total ocupado pola secuencia Huffman + RLE
155 // streamSize = diffsHT.total;
156 // for(index=negStart;index<bigStart;index++)
157 // streamSize += huffmanDst[index]*(index-negStart+1); // Negativos
158 // for(index=bigStart;index<nS;index++)
159 // streamSize += huffmanDst[index]*(index-bigStart+1); // Grandes
161 // // Calculamos o numero de mostras e o espacio ocupado por cada mostra e por cada punteiro
162 // numberOfSamples = (psiSize+T-1)/T;
163 // sampleSize = bits(psiSize);
164 // pointerSize = bits(streamSize);
166 // // Reservamos espacio para a secuencia e para as mostras e punteiros
167 // samples = (unsigned int *)malloc(sizeof(int)*((numberOfSamples*sampleSize+31)/32));
168 // samplePointers = (unsigned int *)malloc(sizeof(int)*((numberOfSamples*pointerSize+31)/32));
169 // stream = (unsigned int *)malloc(sizeof(int)*((streamSize+31)/32));
171 // // Comprimimos secuencialmente (haberá que levar un punteiro desde o inicio)
174 // samplePointersPtr = 0;
176 // for(index=0; index<psiSize; index++) {
180 // if(diffs[index]==1) {
182 // } else { // Non estamos nun run
184 // ptr = encodeHuff(diffsHT,runLenght+runLenghtStart,stream,ptr);
187 // if(diffs[index]>1 && diffs[index]<runLenghtStart) {
188 // ptr = encodeHuff(diffsHT,diffs[index],stream,ptr);
191 // if(diffs[index]<0) { // Valor negativo
192 // absolute_value = -diffs[index];
193 // binaryLenght = bits(absolute_value);
194 // ptr = encodeHuff(diffsHT,binaryLenght+negStart-1,stream,ptr);
195 // bitwrite(stream,ptr,binaryLenght,absolute_value);
196 // ptr += binaryLenght;
197 // } else { // Valor grande >= 128
198 // absolute_value = diffs[index];
199 // binaryLenght = bits(absolute_value);
200 // ptr = encodeHuff(diffsHT,binaryLenght+bigStart-1,stream,ptr);
201 // bitwrite(stream,ptr,binaryLenght,absolute_value);
202 // ptr += binaryLenght;
206 // } else { // Rompemos o run porque atopamos unha mostra
208 // ptr = encodeHuff(diffsHT,runLenght+runLenghtStart,stream,ptr);
211 // bitwrite(samples,samplesPtr,sampleSize,Psi[index]);
212 // samplesPtr += sampleSize;
213 // bitwrite(samplePointers,samplePointersPtr,pointerSize,ptr);
214 // samplePointersPtr += pointerSize;
220 // ptr = encodeHuff(diffsHT,runLenght+runLenghtStart,stream,ptr);
223 // // Amosamos o espacio ocupado
224 // totalSize = sizeof(int)*((numberOfSamples*sampleSize+31)/32) +
225 // sizeof(int)*((numberOfSamples*pointerSize+31)/32) +
226 // sizeof(int)*((streamSize+31)/32) + sizeHuff(diffsHT) +
228 // printf("Compressed Psi size = %d bytes\n", totalSize);
230 // // Necesario antes de decodificar
231 // prepareToDecode(&diffsHT);
233 // // Asignamos os valores a cPsi e devolvemolo
235 // cPsi.diffsHT = diffsHT;
237 // cPsi.numberOfSamples = numberOfSamples;
238 // cPsi.samples = samples;
239 // cPsi.sampleSize = sampleSize;
240 // cPsi.samplePointers = samplePointers;
241 // cPsi.pointerSize = pointerSize;
242 // cPsi.stream = stream;
243 // cPsi.streamSize = streamSize;
245 // //frees resources not needed in advance
249 // //returns the data structure that holds the compressed psi.
254 //unsigned int getHuffmanPsiValue(HuffmanCompressedPsi *cPsi, unsigned int position) {
256 // register unsigned int index;
257 // unsigned int sampleIndex, ptr, psiValue, huffmanCode, positionsSinceSample;
258 // unsigned int absolute_value, binaryLenght, runLenght;
260 // unsigned int runLenghtStart = cPsi->nS - 64 - cPsi->T;
261 // unsigned int negStart = cPsi->nS - 64;
262 // unsigned int bigStart = cPsi->nS - 32;
264 // sampleIndex = position / cPsi->T;
265 // psiValue = bitread(cPsi->samples,sampleIndex*cPsi->sampleSize,cPsi->sampleSize);
266 // ptr = bitread(cPsi->samplePointers,sampleIndex*cPsi->pointerSize,cPsi->pointerSize);
268 // positionsSinceSample = position%cPsi->T;
270 // for(index=0;index<positionsSinceSample;index++) {
272 // ptr = decodeHuff(&cPsi->diffsHT,&huffmanCode,cPsi->stream,ptr);
274 // if(huffmanCode < runLenghtStart) { // Incremento directo
275 // psiValue += huffmanCode;
278 // if(huffmanCode < negStart) { // Estamos nun run
279 // runLenght = huffmanCode - runLenghtStart;
280 // if(index+runLenght>=positionsSinceSample)
281 // return psiValue+positionsSinceSample-index;
283 // psiValue += runLenght;
284 // index += runLenght-1;
288 // if(huffmanCode < bigStart) { // Negativo
289 // binaryLenght = huffmanCode-negStart+1;
290 // absolute_value = bitread(cPsi->stream,ptr,binaryLenght);
291 // ptr += binaryLenght;
292 // psiValue -= absolute_value;
295 // binaryLenght = huffmanCode-bigStart+1;
296 // absolute_value = bitread(cPsi->stream,ptr,binaryLenght);
297 // ptr += binaryLenght;
298 // psiValue += absolute_value;
308 //void storeHuffmanCompressedPsi(HuffmanCompressedPsi *compressedPsi, char *filename) {
313 // if( (file = open(filename, O_WRONLY|O_CREAT, 0700)) < 0) {
314 // printf("Cannot open file %s\n", filename);
317 // write(file, &(compressedPsi->T), sizeof(int));
318 // // Almacenar o arbol de huffman
319 // H = compressedPsi->diffsHT;
320 // write(file, &H.max, sizeof(int));
321 // write(file, &H.lim, sizeof(int));
322 // write(file, &H.depth, sizeof(int));
323 //// write(file, H.s.spos, (H.lim+1)*sizeof(int));
324 // write(file, H.s.symb, (H.lim+1)*sizeof(int));
325 // write(file, H.num, (H.depth+1)*sizeof(int));
326 // write(file, H.fst, (H.depth+1)*sizeof(int));
327 // // Fin de almacenar o arbol de huffman
328 // write(file, &(compressedPsi->nS), sizeof(int));
329 // write(file, &(compressedPsi->numberOfSamples), sizeof(int));
330 // write(file, &(compressedPsi->sampleSize), sizeof(int));
331 // write(file, compressedPsi->samples, ((compressedPsi->numberOfSamples*compressedPsi->sampleSize+31)/32)*sizeof(int));
332 // write(file, &(compressedPsi->pointerSize), sizeof(int));
333 // write(file, compressedPsi->samplePointers, ((compressedPsi->numberOfSamples*compressedPsi->pointerSize+31)/32)*sizeof(int));
334 // write(file, &(compressedPsi->streamSize), sizeof(int));
335 // write(file, compressedPsi->stream, ((compressedPsi->streamSize+31)/32)*sizeof(int));
342 //HuffmanCompressedPsi loadHuffmanCompressedPsi(char *filename) {
344 // HuffmanCompressedPsi compressedPsi;
350 // if( (file = open(filename, O_RDONLY)) < 0) {
351 // printf("Cannot read file %s\n", filename);
354 // read(file, &(compressedPsi.T), sizeof(int));
355 // // Cargamos o arbol de Huffman
356 // read(file, &H.max, sizeof(int));
357 // read(file, &H.lim, sizeof(int));
358 // read(file, &H.depth, sizeof(int));
359 // //H.s.spos = (unsigned int *) malloc((H.lim+1)*sizeof(int));
360 // //H.s.spos =H.s.symb = (unsigned int *) malloc((H.lim+1)*sizeof(int));
361 // H.s.symb = (unsigned int *) malloc((H.lim+1)*sizeof(int));
362 // H.num = (unsigned int *) malloc((H.depth+1)*sizeof(int));
363 // H.fst = (unsigned int *) malloc((H.depth+1)*sizeof(int));
365 // //read(file, H.s.spos, (H.lim+1)*sizeof(int));
366 // fprintf(stderr," \n read %d spos bytes\n", (H.lim+1)*sizeof(int));
367 // read(file, H.s.symb, (H.lim+1)*sizeof(int));
369 // read(file, H.num, (H.depth+1)*sizeof(int));
370 // read(file, H.fst, (H.depth+1)*sizeof(int));
371 // compressedPsi.diffsHT = H;
372 // // Fin da carga do arbol de Huffman
373 // read(file, &(compressedPsi.nS), sizeof(int));
374 // read(file, &(compressedPsi.numberOfSamples), sizeof(int));
375 // read(file, &(compressedPsi.sampleSize), sizeof(int));
376 // compressedPsi.samples = (unsigned int *)malloc(((compressedPsi.numberOfSamples*compressedPsi.sampleSize+31)/32)*sizeof(int));
377 // read(file, compressedPsi.samples, ((compressedPsi.numberOfSamples*compressedPsi.sampleSize+31)/32)*sizeof(int));
378 // read(file, &(compressedPsi.pointerSize), sizeof(int));
379 // compressedPsi.samplePointers = (unsigned int *)malloc(((compressedPsi.numberOfSamples*compressedPsi.pointerSize+31)/32)*sizeof(int));
380 // read(file, compressedPsi.samplePointers, ((compressedPsi.numberOfSamples*compressedPsi.pointerSize+31)/32)*sizeof(int));
381 // read(file, &(compressedPsi.streamSize), sizeof(int));
382 // compressedPsi.stream = (unsigned int *)malloc(((compressedPsi.streamSize+31)/32)*sizeof(int));
383 // read(file, compressedPsi.stream, ((compressedPsi.streamSize+31)/32)*sizeof(int));
387 // return compressedPsi;