Correct copied warning message in added CmiFread
[charm.git] / src / arch / util / compress.c
1 /*
2  * =====================================================================================
3  *
4  *       Filename:  Compress.C
5  *
6  *    Description: Floating point compression/Decompression algorithm 
7  *
8  *        Version:  1.0
9  *        Created:  09/02/2012 02:53:08 PM
10  *       Revision:  none
11  *       Compiler:  gcc
12  *
13  *         Author:  Yanhua Sun 
14  *   Organization:  
15  *
16  * =====================================================================================
17  */
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <math.h>
22 struct timeval tv;
23 #include <sys/time.h>
24
25 double get_clock()
26 {
27        struct timeval tv; int ok;
28        ok = gettimeofday(&tv, NULL);
29        if (ok<0) { CmiPrintf("gettimeofday error");  }
30        return (tv.tv_sec * 1.0 + tv.tv_usec * 1.0E-6);
31 }
32
33 #define     COMPRESS 1 
34 //#define     DEBUG  1
35 #define     CHAR_BIT 8
36 #define     FLOAT_BIT CHAR_BIT*sizeof(float)
37 #define     FLOAT_BYTE sizeof(float)
38
39 #define  COMPRESS_EXP 1
40
41 #if  COMPRESS_EXP
42 #define     SETBIT(dest, i)  (dest[i>>3]) |= (1 << (i&7) )
43 #define     TESTBIT(dest, i) ((dest[i>>3]) >>  (i&7)) & 1 
44 #define     SETBIT11(dest, i)  (dest[(i)>>3]) |= (3 << ((i)&7) )
45 #define     TESTBIT11(dest, i) ((dest[(i)>>3]) >>  ((i)&7)) & 0x3l 
46
47 #else
48
49 #define TESTBIT(data, b) (data>>(b)) & 1
50 #define SETBIT(data, index, bit) (data |= ((bit)<<(index)))
51 #endif
52
53
54 /** compress char is the general algorithm   for any data*/
55 void compressChar(void *src, void *dst, int size, int *compressSize, void *bData)
56 {
57     register char *source = (char*)src;
58     register char *dest = (char*)dst;
59     register char *baseData = (char*)bData;
60     register int i;
61 #if DEBUG
62     double t1 = get_clock();
63 #endif
64
65 #if !COMPRESS 
66     memcpy(dest, source, size*sizeof(char)); 
67     *compressSize = size;
68 #else
69     register int _dataIndex = (size+7)/8;
70     memset(dest, 0, (size+7)/8 );
71     for (i = 0; i < size&&_dataIndex<size; ++i) {
72         // Bitmask everything but the exponents, then check if they match.
73          char xor_d =  source[i] ^ baseData[i];
74          short different= xor_d  & 0xff;
75          if (different) {
76              // If not, mark this exponent as "different" and store it to send with the message.
77              dest[_dataIndex] = source[i];
78              _dataIndex += 1;
79          }else
80          {
81              SETBIT(dest, i);
82          }
83
84     }
85     *compressSize = _dataIndex;
86 #endif
87 #if DEBUG
88     double t = get_clock()-t1;
89     printf(" +++++CHAR done compressing(%d===>%d) (reduction:%d) ration=%f time=%d us\n", (int)(size*sizeof(char)), *compressSize, (int)(size*sizeof(char)-*compressSize), (1-(float)*compressSize/(size*sizeof(char)))*100, (int)(t*1000000));
90 #endif
91 }
92
93 void decompressChar(void *cData, void *dData, int size, int compressSize, void *bData) {
94 #if DEBUG
95     double t1 = get_clock();
96 #endif
97 #if !COMPRESS
98     memcpy(dData, cData, size*sizeof(char));
99 #else
100     char *compressData = (char*)cData;
101     char *baseData = (char*)bData;
102     register char *decompressData =(char*)dData;
103     register int sdataIndex = (size+7)/8;
104     register char *src = (char*)compressData;
105     register int i;
106     for(i=0; i<size; ++i)
107     {
108        if(TESTBIT(src, i)) // same 
109        {
110            decompressData[i] = baseData[i];
111        }else        //different exponet
112        {
113            decompressData[i] = compressData[sdataIndex];   
114            sdataIndex += 1;
115        }
116     }
117 #endif
118 #if DEBUG
119     double t = get_clock()-t1;
120     printf("------CHAR done decompressing.....  orig size:%d time:%d us \n", (int)size, (int)(t*1000000)) ;
121 #endif
122
123 }
124
125 #if  COMPRESS_EXP
126
127 void compressFloatingPoint(void *src, void *dst, int s, int *compressSize, void *bData)
128 {
129     int size = s/FLOAT_BYTE;
130     float *source = (float*)src;
131     float *dest = (float*)dst;
132     float *baseData = (float*)bData;
133     register unsigned int *bptr = (unsigned int*) baseData;
134     register unsigned int  *uptr = (unsigned int *) source;
135     register char *uchar;
136     register int i;
137 #if DEBUG
138     double t1 = get_clock();
139 #endif
140
141 #if !COMPRESS 
142     memcpy(dest, source, size*sizeof(float)); 
143     *compressSize = s;
144 #else
145     // Is this the first time we're sending stuff to this node?
146     if (baseData == NULL) {
147         baseData = (float*)malloc(size*sizeof(float));
148         memcpy(baseData, source, size*sizeof(float));
149         memcpy(dest, source, size*sizeof(float)); 
150         *compressSize = s;
151     } else {
152         // Create message to receive the compressed buffer.
153         register unsigned char *cdst = (unsigned char*)dest; 
154         register int _dataIndex = (size+7)/8;
155         register unsigned int diff;
156         memset(cdst, 0, (size+7)/8 );
157         for (i = 0; i < size; ++i) {
158             // Bitmask everything but the exponents, then check if they match.
159         diff = (bptr[i] ^ uptr[i]) & 0xff000000 ;    
160         if (diff) {
161                 // If not, mark this exponent as "different" and store it to send with the message.
162                 SETBIT(cdst, i);
163                 memcpy(cdst+_dataIndex, &(uptr[i]), 4);
164                 _dataIndex += 4;
165             }else
166             {
167                 memcpy(cdst+_dataIndex, &(uptr[i]), 3);
168                 _dataIndex += 3;
169             }
170
171         }
172         *compressSize = _dataIndex;
173     }
174 #endif
175 #if DEBUG
176     double t = get_clock()-t1;
177     CmiPrintf(" ===> FLOATING done compressingcompressed size:(%d===>%d) (reduction:%d) ration=%f time=%d us\n", (int)(size*sizeof(float)), *compressSize, (int)(size*sizeof(float)-*compressSize), (1-(float)*compressSize/(size*sizeof(float)))*100, (int)(t*1000000));
178 #endif
179 }
180
181 void decompressFloatingPoint(void *cData, void *dData, int s, int compressSize, void *bData) {
182     int size = s/FLOAT_BYTE;
183 #if DEBUG
184     double t1 = get_clock();
185 #endif
186 #if !COMPRESS
187     memcpy(dData, cData, size*sizeof(float));
188 #else
189     float *compressData = (float*)cData;
190     float *baseData = (float*)bData;
191     register unsigned int *decompressData =(unsigned int*)dData;
192     register int _sdataIndex = (size+7)/8;
193     register char *src = (char*)compressData;
194     register int exponent;
195     register unsigned int mantissa;
196     register unsigned int *bptr = (unsigned int*)baseData;
197     register int i;
198     for(i=0; i<size; ++i)
199     {
200        if(TESTBIT(src, i)) // different
201        {
202
203            decompressData[i] = *((unsigned int*)(src+_sdataIndex));
204            _sdataIndex += 4;
205        }else        //same exponet
206        {
207            exponent = bptr[i]  & 0xff000000;
208            mantissa = *((unsigned int*)(src+_sdataIndex)) & 0x00FFFFFF;
209            mantissa |= exponent;
210            decompressData[i] = mantissa;
211            _sdataIndex += 3;
212         }
213     }
214 #endif
215 #if DEBUG
216     double t = get_clock()-t1;
217     //CmiPrintf("--- FLOATING done decompressing.....  orig size:%d\n time:%d us", (int)size, (int)(t*1000000)) ;
218 #endif
219
220 }
221
222 #else
223 void compressFloatingPoint(void *src, void *dst, int s, int *compressSize, void *bData)
224 {
225     register unsigned int *dest = (unsigned int*)dst;
226     register unsigned int *bptr = (unsigned int*) bData;
227     register unsigned int  *uptr = (unsigned int *) src;
228     int size = s/sizeof(float);
229 #if DEBUG
230     double t1 = get_clock();
231 #endif
232     
233 #if !COMPRESS 
234     memcpy(dest, src, size*sizeof(float));
235     *compressSize = s;
236 #else
237     register unsigned int comp_data = 0;
238     register int f_index = 0;
239     register int i;
240     register int j;
241     register int b;
242     register int zers;
243     register unsigned int xor_data;
244     bzero(dest, s);
245     for (i = 0; i < size; ++i) {
246         xor_data = (uptr[i])^(bptr[i]);
247         zers = 0;
248         b=FLOAT_BIT-1; 
249         while(!TESTBIT(xor_data, b) && zers<15){
250             zers++;
251             b--;
252         }
253         //set the LZC 4 bits
254         for(j=0; j<4; j++)
255         {
256             SETBIT(dest[(int)(f_index>>5)], (f_index&0x1f), TESTBIT(zers, j));
257             f_index++;
258         }
259         while(b>=0)
260         {
261             SETBIT(dest[(f_index>>5)], f_index&0x1f, TESTBIT(xor_data, b));
262             f_index++;
263             b--;
264         } 
265     }
266     *compressSize = f_index/8;
267     float compressRatio = (1-(float)(*compressSize)/s)*100;
268     
269 #if DEBUG
270     double t = get_clock()-t1;
271     CmiPrintf("===>[floating point lzc]done compressing compressed size:(%d===>%d) (reduction:%d) ration=%f Timer:%d us\n\n", (int)(size*sizeof(float)), *compressSize, (int)((size*sizeof(float)-*compressSize)), (1-(float)*compressSize/(size*sizeof(float)))*100, (int)(t*1000000));
272 #endif
273
274 #endif
275 }
276
277 void decompressFloatingPoint(void *cData, void *dData, int s, int compressSize, void *bData) {
278     int size = s/sizeof(float);
279 #if DEBUG
280     double t1 = get_clock();
281     if(CmiMyPe() == 5)
282         CmiPrintf("[%d] starting decompressing \n", CmiMyPe());
283 #endif
284 #if !COMPRESS
285     memcpy(dData, cData, size*sizeof(float));
286 #else
287     register unsigned int *compressData = (unsigned int*)cData;
288     register unsigned int *decompressData = (unsigned int*)dData;
289     register unsigned int *baseData = (unsigned int*)bData;
290     bzero(decompressData, s);
291     register int index;
292     register unsigned int xor_data;
293     register int data = 0;
294     register int d_index=0;
295     register int compp = 0;
296     register int i;
297     register int j;
298     register int f;
299     for (i=0; i<size; i++) {
300         index = FLOAT_BIT-1;
301         data = 0;
302         //read 4 bits and puts index acccordingly
303         for (f=0; f<4; f++,compp++) {
304             if(TESTBIT(compressData[(int)(compp>>5)], (compp&0x1f))){
305                 for (j=0; j < (1<<f); j++) {
306                     SETBIT(data, index, 0);
307                     index--;
308                 }
309             }
310         }
311         while(index>=0){
312             SETBIT(data, index, TESTBIT(compressData[(int)(compp>>5)], (compp&0x1f)));
313             index--; compp++;
314         }
315         xor_data = data^(baseData[i]);
316         decompressData[i] = xor_data;
317     }
318
319 #if DEBUG
320     double t = get_clock()-t1;
321     if(CmiMyPe() == 5)
322         CmiPrintf("[%d] done decompressing.....  orig size:%d time:%d us \n", CmiMyPe(), size, (int)(t*1000000));
323 #endif
324
325 #endif
326 }
327
328 #endif
329
330
331 /***************************
332  *
333  * algorithms to compress doubles
334  * *****************/
335
336 #define DOUBLE_BYTE sizeof(double)
337 #define BITS_DOUBLE sizeof(double)*8
338
339 #if COMPRESS_EXP
340
341 void compressDouble(void *src, void *dst, int s, int *compressSize, void *bData)
342 {
343     int size = s/DOUBLE_BYTE;
344     double *source = (double*)src;
345     double *dest = (double*)dst;
346     double *baseData = (double*)bData;
347     register unsigned long *bptr = (unsigned long*) baseData;
348     register unsigned long *uptr = (unsigned long*) source;
349     register char *uchar;
350     register int i;
351 #if DEBUG
352     double t1 = get_clock();
353 #endif
354
355 #if !COMPRESS 
356     memcpy(dest, source, s); 
357     *compressSize = s;
358 #else
359     // Is this the first time we're sending stuff to this node?
360     if (baseData == NULL) {
361         baseData = (double*)malloc(size*sizeof(double));
362         memcpy(baseData, source, s);
363         memcpy(dest, source, s); 
364     } else {
365         *compressSize = s;
366         // Create message to receive the compressed buffer.
367         register unsigned char *cdst = (unsigned char*)dest; 
368         register int _dataIndex = (2*size+7)/8;
369         memset(cdst, 0, (2*size+7)/8 );
370         for (i = 0; i < size; ++i) {
371             // Bitmask everything but the exponents, then check if they match.
372             unsigned long xord = bptr[i] ^ uptr[i];
373             unsigned long eight = xord &  0xff00000000000000;
374             unsigned long sixteen = xord &  0xffff000000000000;
375             if(sixteen == 0l)    //00
376             {
377                 unsigned long ui = uptr[i];
378                 memcpy(cdst+_dataIndex, &ui, 6);
379                 _dataIndex += 6;
380             }
381             else if(eight == 0l)//01
382             {
383                 SETBIT(cdst, i<<1);
384                 unsigned long ui = uptr[i];
385                 memcpy(cdst+_dataIndex, &ui, 7);
386                 _dataIndex += 7;
387             }else   //11
388             {
389                 SETBIT11(cdst, i<<1);
390                 unsigned long ui = uptr[i];
391                 memcpy(cdst+_dataIndex, &ui, 8);
392                 _dataIndex += 8;
393             }
394         }
395         *compressSize = _dataIndex;
396     }
397 #endif
398 #if DEBUG
399     double t = get_clock()-t1;
400     printf(" ===>[double lzc] done compressingcompressed size:(%d===>%d) (reduction:%d) ration=%f time=%d us\n", (int)(size*sizeof(double)), *compressSize, (int)(size*sizeof(double)-*compressSize), (1-(double)*compressSize/(size*sizeof(double)))*100, (int)(t*1000000));
401 #endif
402 }
403
404 void decompressDouble(void *cData, void *dData, int s, int compressSize, void *bData) {
405     int size = s/DOUBLE_BYTE;
406 #if DEBUG
407     double t1 = get_clock();
408 #endif
409 #if !COMPRESS
410     memcpy(dData, cData, s);
411 #else
412     double *compressData = (double*)cData;
413     double *baseData = (double*)bData;
414     register unsigned long *decompressData =(unsigned long*)dData;
415     register int _sdataIndex = (2*size+7)/8;
416     register char *src = (char*)compressData;
417     register unsigned long exponent;
418     register unsigned long mantissa;
419     register unsigned long *bptr = (unsigned long*)baseData;
420     register int i;
421     for(i=0; i<size; ++i)
422     {
423         int bitss = TESTBIT(src, i<<1);
424         if(bitss==3) // different
425         {
426
427             decompressData[i] = *((unsigned long*)(src+_sdataIndex));
428             _sdataIndex += 8;
429         }else if(bitss==1) 
430         {
431             exponent = bptr[i]  & 0xff00000000000000;
432             mantissa = *((unsigned long*)(src+_sdataIndex)) & 0x00ffffffffffffff;
433             mantissa |= exponent;
434             decompressData[i] = mantissa;   
435             _sdataIndex += 7;
436         }else
437         {
438             exponent = bptr[i]  & 0xffff000000000000;
439             mantissa = *((unsigned long*)(src+_sdataIndex)) & 0x0000ffffffffffff;
440             mantissa |= exponent;
441             decompressData[i] = mantissa;   
442             _sdataIndex += 6;
443         }
444     }
445 #endif
446 #if DEBUG
447     double t = get_clock()-t1;
448     printf("done decompressing.....  orig size:%d\n time:%d us", (int)size, (int)(t*1000000)) ;
449 #endif
450
451 }
452
453
454 #else
455
456 void compressDouble(void *src, void *dst, int s, int *compressSize, void *bData)
457 {
458     register unsigned long *dest = (unsigned long*)dst;
459     register unsigned long *bptr = (unsigned long*) bData;
460     register unsigned long  *uptr = (unsigned long*) src;
461     int size = s/sizeof(double);
462 #if DEBUG
463     double t1 = get_clock();
464 #endif
465     
466 #if !COMPRESS
467     memcpy(dest, src, size*sizeof(double));
468     *compressSize = s;
469 #else
470     register int f_index = 0;
471     register int i;
472     register int j;
473     register int b;
474     register int zers;
475     register unsigned long xor_data;
476     bzero(dest, s);
477     for (i = 0; i < size; ++i) {
478         xor_data = (uptr[i])^(bptr[i]);
479         zers = 0;
480         //int value = xor_data;
481         //printbitssimple(value);
482         //printf("\n\n");
483         b=BITS_DOUBLE-1;
484         while(!TESTBIT(xor_data, b) && zers<15){
485             zers++;
486             b--;
487         }
488         //cout<<"c: "<<zers<<endl;
489         //set the LZC 4 bits
490         for(j=0; j<4; j++)
491         {
492             SETBIT(dest[(int)(f_index>>6)], (f_index&0x3f), ((unsigned long)(TESTBIT(zers, j))));
493             f_index++;
494         }
495         while(b>=0)
496         {
497             SETBIT(dest[(f_index>>6)], f_index&0x3f, TESTBIT(xor_data, b));
498             f_index++;
499             b--;
500         }
501     }
502     /*for (int k=0; k<size; k++) {
503      printf(" %f ",dest[k]);
504      }*/
505     
506     *compressSize = f_index/8;
507     double compressRatio = (1-(double)(*compressSize)/s)*100;
508     
509 #if DEBUG
510     double t = get_clock()-t1;
511     printf("===>double lzc done compressing compressed size:(%d===>%d) (reduction:%d) ration=%f Timer:%d us\n\n", (int)(size*sizeof(double)), *compressSize, (int)((size*sizeof(double)-*compressSize)), (1-(double)*compressSize/(size*sizeof(double)))*100, (int)(t*1000000));
512 #endif
513     
514 #endif
515 }
516
517 void decompressDouble(void *cData, void *dData, int s, int compressSize, void *bData) {
518     int size = s/sizeof(double);
519 #if DEBUG
520     double t1 = get_clock();
521 #endif
522 #if !COMPRESS
523     memcpy(dData, cData, size*sizeof(double));
524 #else
525     register unsigned long *compressData = (unsigned long*)cData;
526     register unsigned long *decompressData = (unsigned long*)dData;
527     register unsigned long *baseData = (unsigned long*)bData;
528     /*for (int k=0; k<size; k++) {
529         printf("d: %d ",compressData[k]);
530     }*/
531     
532     bzero(decompressData, s);
533     register int index;
534     register unsigned long xor_data;
535     register unsigned long data = 0;
536     register int d_index=0;
537     register int compp = 0;
538     register int i;
539     register int j;
540     register int f;
541     for (i=0; i<size; i++) {
542         index = BITS_DOUBLE-1;
543         data = 0; int zers=0;
544         //read 4 bits and puts index acccordingly
545         for (f=0; f<4; f++,compp++) {
546             if(TESTBIT(compressData[(int)(compp>>6)], (compp&0x3f))){
547                 for (j=0; j < (1<<f); j++) {
548                     index--; zers++;
549                 }
550             }
551         }
552         //cout<<"d: "<<zers<<endl;
553         //printbitssimple();
554         while(index>=0){
555             SETBIT(data, index, TESTBIT(compressData[(int)(compp>>6)], (compp&0x3f)));
556             index--; compp++;
557         }
558         xor_data = data^(baseData[i]);
559         decompressData[i] = xor_data;
560     }
561     
562 #if DEBUG
563     double t = get_clock()-t1;
564     printf("done decompressing.....  orig size:%d time:%d us \n", size, (int)(t*1000000));
565 #endif
566     
567 #endif
568 }
569
570 #endif
571
572