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