1 #include "psiHuffmanRLE.h"
3 // IMPLEMENTACION DAS FUNCIONS
5 void destroyHuffmanCompressedPsi(HuffmanCompressedPsi *compressedPsi) {
6 freeHuff2(compressedPsi->diffsHT);
7 free(compressedPsi->samples);
8 free(compressedPsi->samplePointers);
9 free (compressedPsi->stream);
12 HuffmanCompressedPsi huffmanCompressPsi(unsigned int *Psi, unsigned int psiSize, unsigned int T, unsigned int nS) {
14 HuffmanCompressedPsi cPsi;
17 register unsigned int index, ptr, samplesPtr, samplePointersPtr;
18 unsigned int runLenght, binaryLenght;
21 unsigned int *huffmanDst;
23 // Estructuras da funcion comprimida (para logo asignar)
24 // Tam�n se podian almacenar directamente
26 unsigned int numberOfSamples;
27 unsigned int *samples;
28 unsigned int sampleSize;
29 unsigned int *samplePointers;
30 unsigned int pointerSize;
32 unsigned int streamSize;
34 // Variables que marcan os intervalos dentro do vector de frecuencias
35 unsigned int runLenghtStart = nS - 64 - T; // Inicio das Runs
36 unsigned int negStart = nS - 64; // Inicio dos Negativos
37 unsigned int bigStart = nS - 32; // Inicio dos Grandes (>runLenghtStart)
40 unsigned int totalSize;
42 // Reservamos espacio para a distribuci�n de valores de Psi
43 huffmanDst = (unsigned int *)malloc(sizeof(int)*nS);
44 for(index=0;index<nS;index++) huffmanDst[index]=0;
46 // Inicializamos diferencias
47 diffs = (int *)malloc(sizeof(int)*psiSize);
49 for(index=1; index<psiSize; index++)
50 diffs[index] = Psi[index] - Psi[index-1];
52 // Calculamos a distribucion de frecuencias
54 for(index=0; index<psiSize; index++) {
60 } else { // Non estamos nun run
62 huffmanDst[runLenght+runLenghtStart]++;
65 if(diffs[index]>1 && diffs[index]<runLenghtStart)
66 huffmanDst[diffs[index]]++;
68 if(diffs[index]<0) { // Valor negativo
69 absolute_value = -diffs[index];
70 binaryLenght = bits(absolute_value);
71 huffmanDst[binaryLenght+negStart-1]++;
72 } else { // Valor grande >= 128
73 absolute_value = diffs[index];
74 binaryLenght = bits(absolute_value);
75 huffmanDst[binaryLenght+bigStart-1]++;
79 } else { // Rompemos o run porque atopamos unha mostra
81 huffmanDst[runLenght+runLenghtStart]++;
88 if(runLenght) huffmanDst[runLenght+runLenghtStart]++;
90 // Creamos o arbol de Huffman
91 diffsHT = createHuff(huffmanDst,nS-1,UNSORTED);
93 // Calculamos o espacio total ocupado pola secuencia Huffman + RLE
94 streamSize = diffsHT.total;
95 for(index=negStart;index<bigStart;index++)
96 streamSize += huffmanDst[index]*(index-negStart+1); // Negativos
97 for(index=bigStart;index<nS;index++)
98 streamSize += huffmanDst[index]*(index-bigStart+1); // Grandes
100 // Calculamos o numero de mostras e o espacio ocupado por cada mostra e por cada punteiro
101 numberOfSamples = (psiSize+T-1)/T;
102 sampleSize = bits(psiSize);
103 pointerSize = bits(streamSize);
105 // Reservamos espacio para a secuencia e para as mostras e punteiros
106 samples = (unsigned int *)malloc(sizeof(uint)*((numberOfSamples*sampleSize+31)/32));
107 samples[((numberOfSamples*sampleSize+31)/32)-1] =0000; //initialized only to avoid valgrind warnings
108 samplePointers = (unsigned int *)malloc(sizeof(int)*((numberOfSamples*pointerSize+31)/32));
109 samplePointers[((numberOfSamples*pointerSize+31)/32)-1] = 0000; //initialized only to avoid valgrind warnings
110 stream = (unsigned int *)malloc(sizeof(int)*((streamSize+31)/32));
111 stream[((streamSize+31)/32)-1]=0000;//initialized only to avoid valgrind warnings
113 // Comprimimos secuencialmente (haber� que levar un punteiro desde o inicio)
116 samplePointersPtr = 0;
118 for(index=0; index<psiSize; index++) {
122 if(diffs[index]==1) {
124 } else { // Non estamos nun run
126 ptr = encodeHuff(diffsHT,runLenght+runLenghtStart,stream,ptr);
129 if(diffs[index]>1 && diffs[index]<runLenghtStart) {
130 ptr = encodeHuff(diffsHT,diffs[index],stream,ptr);
133 if(diffs[index]<0) { // Valor negativo
134 absolute_value = -diffs[index];
135 binaryLenght = bits(absolute_value);
136 ptr = encodeHuff(diffsHT,binaryLenght+negStart-1,stream,ptr);
137 bitwrite(stream,ptr,binaryLenght,absolute_value);
139 } else { // Valor grande >= 128
140 absolute_value = diffs[index];
141 binaryLenght = bits(absolute_value);
142 ptr = encodeHuff(diffsHT,binaryLenght+bigStart-1,stream,ptr);
143 bitwrite(stream,ptr,binaryLenght,absolute_value);
148 } else { // Rompemos o run porque atopamos unha mostra
150 ptr = encodeHuff(diffsHT,runLenght+runLenghtStart,stream,ptr);
153 bitwrite(samples,samplesPtr,sampleSize,Psi[index]);
154 samplesPtr += sampleSize;
155 bitwrite(samplePointers,samplePointersPtr,pointerSize,ptr);
156 samplePointersPtr += pointerSize;
162 ptr = encodeHuff(diffsHT,runLenght+runLenghtStart,stream,ptr);
165 // Amosamos o espacio ocupado
166 totalSize = sizeof(HuffmanCompressedPsi) +
167 sizeof(int)*((numberOfSamples*sampleSize+31)/32) +
168 sizeof(int)*((numberOfSamples*pointerSize+31)/32) +
169 sizeof(int)*((streamSize+31)/32) + sizeHuff2(diffsHT);
171 printf("\n\t Compressed Psi size = %d bytes, with %d different symbols.", totalSize, nS);
173 // Necesario antes de decodificar
174 prepareToDecode(&diffsHT);
176 // Asignamos os valores a cPsi e devolvemolo
178 cPsi.diffsHT = diffsHT;
180 cPsi.numberOfSamples = numberOfSamples;
181 cPsi.samples = samples;
182 cPsi.sampleSize = sampleSize;
183 cPsi.samplePointers = samplePointers;
184 cPsi.pointerSize = pointerSize;
185 cPsi.stream = stream;
186 cPsi.streamSize = streamSize;
187 cPsi.totalMem = totalSize;
189 //frees resources not needed in advance
193 //returns the data structure that holds the compressed psi.
198 unsigned int getHuffmanPsiValue(HuffmanCompressedPsi *cPsi, unsigned int position) {
200 register unsigned int index;
201 unsigned int sampleIndex, ptr, psiValue, huffmanCode, positionsSinceSample;
202 unsigned int absolute_value, binaryLenght, runLenght;
204 unsigned int runLenghtStart = cPsi->nS - 64 - cPsi->T;
205 unsigned int negStart = cPsi->nS - 64;
206 unsigned int bigStart = cPsi->nS - 32;
208 sampleIndex = position / cPsi->T;
209 psiValue = bitread(cPsi->samples,sampleIndex*cPsi->sampleSize,cPsi->sampleSize);
210 ptr = bitread(cPsi->samplePointers,sampleIndex*cPsi->pointerSize,cPsi->pointerSize);
212 positionsSinceSample = position%cPsi->T;
214 for(index=0;index<positionsSinceSample;index++) {
216 ptr = decodeHuff(&cPsi->diffsHT,&huffmanCode,cPsi->stream,ptr);
218 if(huffmanCode < runLenghtStart) { // Incremento directo
219 psiValue += huffmanCode;
222 if(huffmanCode < negStart) { // Estamos nun run
223 runLenght = huffmanCode - runLenghtStart;
224 if(index+runLenght>=positionsSinceSample)
225 return psiValue+positionsSinceSample-index;
227 psiValue += runLenght;
228 index += runLenght-1;
232 if(huffmanCode < bigStart) { // Negativo
233 binaryLenght = huffmanCode-negStart+1;
234 absolute_value = bitread(cPsi->stream,ptr,binaryLenght);
236 psiValue -= absolute_value;
239 binaryLenght = huffmanCode-bigStart+1;
240 absolute_value = bitread(cPsi->stream,ptr,binaryLenght);
242 psiValue += absolute_value;
252 void storeHuffmanCompressedPsi(HuffmanCompressedPsi *compressedPsi, char *filename) {
257 if( (file = open(filename, O_WRONLY|O_CREAT, 0700)) < 0) {
258 printf("Cannot open file %s\n", filename);
261 write(file, &(compressedPsi->T), sizeof(int));
262 // Almacenar o arbol de huffman
263 H = compressedPsi->diffsHT;
264 write(file, &H.max, sizeof(int));
265 write(file, &H.lim, sizeof(int));
266 write(file, &H.depth, sizeof(int));
267 // write(file, H.s.spos, (H.lim+1)*sizeof(int));
268 write(file, H.s.symb, (H.lim+1)*sizeof(int));
269 write(file, H.num, (H.depth+1)*sizeof(int));
270 write(file, H.fst, (H.depth+1)*sizeof(int));
271 // Fin de almacenar o arbol de huffman
272 write(file, &(compressedPsi->nS), sizeof(int));
273 write(file, &(compressedPsi->numberOfSamples), sizeof(int));
274 write(file, &(compressedPsi->sampleSize), sizeof(int));
275 write(file, compressedPsi->samples, ((compressedPsi->numberOfSamples*compressedPsi->sampleSize+31)/32)*sizeof(int));
276 write(file, &(compressedPsi->pointerSize), sizeof(int));
277 write(file, compressedPsi->samplePointers, ((compressedPsi->numberOfSamples*compressedPsi->pointerSize+31)/32)*sizeof(int));
278 write(file, &(compressedPsi->streamSize), sizeof(int));
279 write(file, compressedPsi->stream, ((compressedPsi->streamSize+31)/32)*sizeof(int));
280 write(file, &(compressedPsi->totalMem), sizeof(int));
287 HuffmanCompressedPsi loadHuffmanCompressedPsi(char *filename) {
289 HuffmanCompressedPsi compressedPsi;
295 if( (file = open(filename, O_RDONLY)) < 0) {
296 printf("Cannot read file %s\n", filename);
299 read(file, &(compressedPsi.T), sizeof(int));
300 // Cargamos o arbol de Huffman
301 read(file, &H.max, sizeof(int));
302 read(file, &H.lim, sizeof(int));
303 read(file, &H.depth, sizeof(int));
304 //H.s.spos = (unsigned int *) malloc((H.lim+1)*sizeof(int));
305 //H.s.spos =H.s.symb = (unsigned int *) malloc((H.lim+1)*sizeof(int));
306 H.s.symb = (unsigned int *) malloc((H.lim+1)*sizeof(int));
307 H.num = (unsigned int *) malloc((H.depth+1)*sizeof(int));
308 H.fst = (unsigned int *) malloc((H.depth+1)*sizeof(int));
310 //read(file, H.s.spos, (H.lim+1)*sizeof(int));
311 //fprintf(stderr," \n read %d spos bytes\n", (H.lim+1)*sizeof(int));
312 read(file, H.s.symb, (H.lim+1)*sizeof(int));
314 read(file, H.num, (H.depth+1)*sizeof(int));
315 read(file, H.fst, (H.depth+1)*sizeof(int));
316 compressedPsi.diffsHT = H;
317 // Fin da carga do arbol de Huffman
318 read(file, &(compressedPsi.nS), sizeof(int));
319 read(file, &(compressedPsi.numberOfSamples), sizeof(int));
320 read(file, &(compressedPsi.sampleSize), sizeof(int));
321 compressedPsi.samples = (unsigned int *)malloc(((compressedPsi.numberOfSamples*compressedPsi.sampleSize+31)/32)*sizeof(int));
322 read(file, compressedPsi.samples, ((compressedPsi.numberOfSamples*compressedPsi.sampleSize+31)/32)*sizeof(int));
323 read(file, &(compressedPsi.pointerSize), sizeof(int));
324 compressedPsi.samplePointers = (unsigned int *)malloc(((compressedPsi.numberOfSamples*compressedPsi.pointerSize+31)/32)*sizeof(int));
325 read(file, compressedPsi.samplePointers, ((compressedPsi.numberOfSamples*compressedPsi.pointerSize+31)/32)*sizeof(int));
326 read(file, &(compressedPsi.streamSize), sizeof(int));
327 compressedPsi.stream = (unsigned int *)malloc(((compressedPsi.streamSize+31)/32)*sizeof(int));
328 read(file, compressedPsi.stream, ((compressedPsi.streamSize+31)/32)*sizeof(int));
329 read(file, &(compressedPsi.totalMem), sizeof(int));
333 return compressedPsi;