source: thirdparty/SZ/sz/src/Huffman.c @ 9ee2ce3

Revision 9ee2ce3, 21.6 KB checked in by Hal Finkel <hfinkel@…>, 6 years ago (diff)

importing new SZ files
  • Property mode set to 100644
Line 
1/**
2 *  @file Huffman.c
3 *  @author Sheng Di
4 *  @date Aug., 2016
5 *  @brief Customized Huffman Encoding, Compression and Decompression functions
6 *  (C) 2016 by Mathematics and Computer Science (MCS), Argonne National Laboratory.
7 *      See COPYRIGHT in top-level directory.
8 */
9
10#include <stdio.h>
11#include <stdlib.h>
12#include <string.h>
13#include "Huffman.h"
14#include "sz.h"
15
16
17HuffmanTree* createHuffmanTree(int stateNum)
18{                       
19        HuffmanTree *huffmanTree = (HuffmanTree*)malloc(sizeof(HuffmanTree));
20        memset(huffmanTree, 0, sizeof(HuffmanTree));
21        huffmanTree->stateNum = stateNum;
22        huffmanTree->allNodes = 2*stateNum;
23       
24        huffmanTree->pool = (struct node_t*)malloc(huffmanTree->allNodes*2*sizeof(struct node_t));
25        huffmanTree->qqq = (node*)malloc(huffmanTree->allNodes*2*sizeof(node));
26        huffmanTree->code = (unsigned long**)malloc(huffmanTree->stateNum*sizeof(unsigned long*));
27        huffmanTree->cout = (unsigned char *)malloc(huffmanTree->stateNum*sizeof(unsigned char));
28       
29        memset(huffmanTree->pool, 0, huffmanTree->allNodes*2*sizeof(struct node_t));
30        memset(huffmanTree->qqq, 0, huffmanTree->allNodes*2*sizeof(node));
31    memset(huffmanTree->code, 0, huffmanTree->stateNum*sizeof(unsigned long*));
32    memset(huffmanTree->cout, 0, huffmanTree->stateNum*sizeof(unsigned char));
33        huffmanTree->qq = huffmanTree->qqq - 1;
34        huffmanTree->n_nodes = 0;
35    huffmanTree->n_inode = 0;
36    huffmanTree->qend = 1;     
37   
38    return huffmanTree;
39}
40
41HuffmanTree* createDefaultHuffmanTree()
42{
43        int maxRangeRadius = 32768;
44        int stateNum = maxRangeRadius << 1; //*2
45
46    return createHuffmanTree(stateNum);
47}
48 
49node new_node(HuffmanTree* huffmanTree, size_t freq, unsigned int c, node a, node b)
50{
51        node n = huffmanTree->pool + huffmanTree->n_nodes++;
52        if (freq) 
53        {
54                n->c = c;
55                n->freq = freq;
56                n->t = 1;
57        }
58        else {
59                n->left = a; 
60                n->right = b;
61                n->freq = a->freq + b->freq;
62                n->t = 0;
63                //n->c = 0;
64        }
65        return n;
66}
67 
68node new_node2(HuffmanTree *huffmanTree, unsigned int c, unsigned char t)
69{
70        huffmanTree->pool[huffmanTree->n_nodes].c = c;
71        huffmanTree->pool[huffmanTree->n_nodes].t = t;
72        return huffmanTree->pool + huffmanTree->n_nodes++;
73} 
74 
75/* priority queue */
76void qinsert(HuffmanTree *huffmanTree, node n)
77{
78        int j, i = huffmanTree->qend++;
79        while ((j = (i>>1)))  //j=i/2
80        {
81                if (huffmanTree->qq[j]->freq <= n->freq) break;
82                huffmanTree->qq[i] = huffmanTree->qq[j], i = j;
83        }
84        huffmanTree->qq[i] = n;
85}
86 
87node qremove(HuffmanTree* huffmanTree)
88{
89        int i, l;
90        node n = huffmanTree->qq[i = 1];
91 
92        if (huffmanTree->qend < 2) return 0;
93        huffmanTree->qend --;
94        while ((l = (i<<1)) < huffmanTree->qend)  //l=(i*2)
95        {
96                if (l + 1 < huffmanTree->qend && huffmanTree->qq[l + 1]->freq < huffmanTree->qq[l]->freq) l++;
97                huffmanTree->qq[i] = huffmanTree->qq[l], i = l;
98        }
99        huffmanTree->qq[i] = huffmanTree->qq[huffmanTree->qend];
100        return n;
101}
102 
103/* walk the tree and put 0s and 1s */
104/**
105 * @out1 should be set to 0.
106 * @out2 should be 0 as well.
107 * @index: the index of the byte
108 * */
109void build_code(HuffmanTree *huffmanTree, node n, int len, unsigned long out1, unsigned long out2)
110{
111        if (n->t) {
112                huffmanTree->code[n->c] = (unsigned long*)malloc(2*sizeof(unsigned long));
113                if(len<=64)
114                {
115                        (huffmanTree->code[n->c])[0] = out1 << (64 - len);
116                        (huffmanTree->code[n->c])[1] = out2;
117                }
118                else
119                {
120                        (huffmanTree->code[n->c])[0] = out1;
121                        (huffmanTree->code[n->c])[1] = out2 << (128 - len);
122                }
123                huffmanTree->cout[n->c] = (unsigned char)len;
124                return;
125        }
126        int index = len >> 6; //=len/64
127        if(index == 0)
128        {
129                out1 = out1 << 1;
130                out1 = out1 | 0;
131                build_code(huffmanTree, n->left, len + 1, out1, 0);
132                out1 = out1 | 1;
133                build_code(huffmanTree, n->right, len + 1, out1, 0);           
134        }
135        else
136        {
137                if(len%64!=0)
138                        out2 = out2 << 1;
139                out2 = out2 | 0;
140                build_code(huffmanTree, n->left, len + 1, out1, out2);
141                out2 = out2 | 1;
142                build_code(huffmanTree, n->right, len + 1, out1, out2); 
143        }
144}
145
146void init(HuffmanTree* huffmanTree, int *s, size_t length)
147{
148        size_t i, index;
149        size_t *freq = (size_t *)malloc(huffmanTree->allNodes*sizeof(size_t));
150        memset(freq, 0, huffmanTree->allNodes*sizeof(size_t));
151        for(i = 0;i < length;i++) 
152        {
153                //index = 0;
154                //index = (index | s[i])<<8;
155                //index = index | s[i+1];
156                index = s[i];
157                freq[index]++;
158        }
159 
160        for (i = 0; i < huffmanTree->allNodes; i++)
161                if (freq[i]) 
162                        qinsert(huffmanTree, new_node(huffmanTree, freq[i], i, 0, 0));
163 
164        while (huffmanTree->qend > 2) 
165                qinsert(huffmanTree, new_node(huffmanTree, 0, 0, qremove(huffmanTree), qremove(huffmanTree)));
166 
167        build_code(huffmanTree, huffmanTree->qq[1], 0, 0, 0);
168        free(freq);
169}
170 
171void encode(HuffmanTree *huffmanTree, int *s, size_t length, unsigned char *out, size_t *outSize)
172{
173        size_t i = 0;
174        unsigned char bitSize = 0, byteSize, byteSizep;
175        int state;
176        unsigned char *p = out;
177        int lackBits = 0;
178        //long totalBitSize = 0, maxBitSize = 0, bitSize21 = 0, bitSize32 = 0;
179        for (i = 0;i<length;i++) 
180        {
181                //state = 0;
182                //state = (state | s[i])<<8;
183                //state = state | s[i+1];
184               
185                state = s[i];
186                bitSize = huffmanTree->cout[state];     
187               
188                //printf("%d %d : %d %u\n",i, state, bitSize, (code[state])[0] >> (64-cout[state]));
189                //debug: compute the average bitSize and the count that is over 32...   
190                /*if(bitSize>=21)
191                        bitSize21++;
192                if(bitSize>=32)
193                        bitSize32++;
194                if(maxBitSize<bitSize)
195                        maxBitSize = bitSize;
196                totalBitSize+=bitSize;*/
197
198                if(lackBits==0)
199                {
200                        byteSize = bitSize%8==0 ? bitSize/8 : bitSize/8+1; //it's equal to the number of bytes involved (for *outSize)
201                        byteSizep = bitSize/8; //it's used to move the pointer p for next data
202                        if(byteSize<=8)                         
203                        {
204                                longToBytes_bigEndian(p, (huffmanTree->code[state])[0]);
205                                p += byteSizep;
206                        }
207                        else //byteSize>8
208                        {
209                                longToBytes_bigEndian(p, (huffmanTree->code[state])[0]);
210                                p += 8;                 
211                                longToBytes_bigEndian(p, (huffmanTree->code[state])[1]);
212                                p += (byteSizep - 8);           
213                        }
214                        *outSize += byteSize;
215                        lackBits = bitSize%8==0 ? 0 : 8 - bitSize%8;
216                }
217                else
218                {
219                        *p = (*p) | (unsigned char)((huffmanTree->code[state])[0] >> (64 - lackBits));                 
220                        if(lackBits < bitSize)
221                        {
222                                p++;
223                                //(*outSize)++;
224                                long newCode = (huffmanTree->code[state])[0] << lackBits;
225                                longToBytes_bigEndian(p, newCode);                             
226
227                                if(bitSize<=64)
228                                {
229                                        bitSize -= lackBits;
230                                        byteSize = bitSize%8==0 ? bitSize/8 : bitSize/8+1;
231                                        byteSizep = bitSize/8;
232                                        p += byteSizep;
233                                        (*outSize)+=byteSize;
234                                        lackBits = bitSize%8==0 ? 0 : 8 - bitSize%8;
235                                }
236                                else //bitSize > 64
237                                {
238                                        byteSizep = 7; //must be 7 bytes, because lackBits!=0
239                                        p+=byteSizep;
240                                        (*outSize)+=byteSize;
241                                       
242                                        bitSize -= 64;
243                                        if(lackBits < bitSize)
244                                        {
245                                                *p = (*p) | (unsigned char)((huffmanTree->code[state])[0] >> (64 - lackBits));
246                                                p++;
247                                                //(*outSize)++;                                         
248                                                newCode = (huffmanTree->code[state])[1] << lackBits;
249                                                longToBytes_bigEndian(p, newCode);
250                                                bitSize -= lackBits;
251                                                byteSize = bitSize%8==0 ? bitSize/8 : bitSize/8+1;
252                                                byteSizep = bitSize/8;
253                                                p += byteSizep;
254                                                (*outSize)+=byteSize;
255                                                lackBits = bitSize%8==0 ? 0 : 8 - bitSize%8;                                           
256                                        }
257                                        else //lackBits >= bitSize
258                                        {
259                                                *p = (*p) | (unsigned char)((huffmanTree->code[state])[0] >> (64 - bitSize));
260                                                lackBits -= bitSize;
261                                        }               
262                                }
263                        }
264                        else //lackBits >= bitSize
265                        {
266                                lackBits -= bitSize;
267                                if(lackBits==0)
268                                        p++;
269                        }
270                }
271        }
272//      for(i=0;i<stateNum;i++)
273//              if(code[i]!=NULL) free(code[i]);
274        /*printf("max bitsize = %d\n", maxBitSize);
275        printf("bitSize21 ratio = %f\n", ((float)bitSize21)/length);
276        printf("bitSize32 ratio = %f\n", ((float)bitSize32)/length);
277        printf("avg bit size = %f\n", ((float)totalBitSize)/length);*/
278}
279 
280void decode(unsigned char *s, size_t targetLength, node t, int *out)
281{
282        size_t i = 0, byteIndex = 0, count = 0;
283        int r; 
284        node n = t;
285       
286        if(n->t) //root->t==1 means that all state values are the same (constant)
287        {
288                for(count=0;count<targetLength;count++)
289                        out[count] = n->c;
290                return;
291        }
292       
293        for(i=0;count<targetLength;i++)
294        {
295               
296                byteIndex = i>>3; //i/8
297                r = i%8;
298                if(((s[byteIndex] >> (7-r)) & 0x01) == 0)
299                        n = n->left;
300                else
301                        n = n->right;
302
303                if (n->t) {
304                        //putchar(n->c);
305                        out[count] = n->c;
306                        n = t; 
307                        count++;
308                }
309        }
310//      putchar('\n');
311        if (t != n) printf("garbage input\n");
312        return;
313} 
314         
315void pad_tree_uchar(HuffmanTree* huffmanTree, unsigned char* L, unsigned char* R, unsigned int* C, unsigned char* t, unsigned int i, node root)
316{
317        C[i] = root->c;
318        t[i] = root->t;
319        node lroot = root->left;
320        if(lroot!=0)
321        {
322                huffmanTree->n_inode++;
323                L[i] = huffmanTree->n_inode;
324                pad_tree_uchar(huffmanTree, L,R,C,t, huffmanTree->n_inode, lroot);
325        }
326        node rroot = root->right;
327        if(rroot!=0)
328        {
329                huffmanTree->n_inode++;
330                R[i] = huffmanTree->n_inode;
331                pad_tree_uchar(huffmanTree, L,R,C,t, huffmanTree->n_inode, rroot);
332        }
333} 
334
335void pad_tree_ushort(HuffmanTree* huffmanTree, unsigned short* L, unsigned short* R, unsigned int* C, unsigned char* t, unsigned int i, node root)
336{
337        C[i] = root->c;
338        t[i] = root->t;
339        node lroot = root->left;
340        if(lroot!=0)
341        {
342                huffmanTree->n_inode++;
343                L[i] = huffmanTree->n_inode;
344                pad_tree_ushort(huffmanTree,L,R,C,t,huffmanTree->n_inode, lroot);
345        }
346        node rroot = root->right;
347        if(rroot!=0)
348        {
349                huffmanTree->n_inode++;
350                R[i] = huffmanTree->n_inode;
351                pad_tree_ushort(huffmanTree,L,R,C,t,huffmanTree->n_inode, rroot);
352        }       
353}
354
355void pad_tree_uint(HuffmanTree* huffmanTree, unsigned int* L, unsigned int* R, unsigned int* C, unsigned char* t, unsigned int i, node root)
356{
357        C[i] = root->c;
358        t[i] = root->t;
359        node lroot = root->left;
360        if(lroot!=0)
361        {
362                huffmanTree->n_inode++;
363                L[i] = huffmanTree->n_inode;
364                pad_tree_uint(huffmanTree,L,R,C,t,huffmanTree->n_inode, lroot);
365        }
366        node rroot = root->right;
367        if(rroot!=0)
368        {
369                huffmanTree->n_inode++;
370                R[i] = huffmanTree->n_inode;
371                pad_tree_uint(huffmanTree,L,R,C,t,huffmanTree->n_inode, rroot);
372        }
373}
374 
375unsigned int convert_HuffTree_to_bytes_anyStates(HuffmanTree* huffmanTree, int nodeCount, unsigned char** out) 
376{
377        //printf("nodeCount=%d\n", nodeCount);
378        if(nodeCount<=256)
379        {
380                unsigned char* L = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
381                memset(L, 0, nodeCount*sizeof(unsigned char));
382                unsigned char* R = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
383                memset(R, 0, nodeCount*sizeof(unsigned char));
384                unsigned int* C = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));
385                memset(C, 0, nodeCount*sizeof(unsigned int));
386                unsigned char* t = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
387                memset(t, 0, nodeCount*sizeof(unsigned char));
388
389                pad_tree_uchar(huffmanTree,L,R,C,t,0,huffmanTree->qq[1]);
390
391                unsigned int totalSize = 1+3*nodeCount*sizeof(unsigned char)+nodeCount*sizeof(unsigned int);   
392                *out = (unsigned char*)malloc(totalSize*sizeof(unsigned char));
393                (*out)[0] = (unsigned char)sysEndianType;
394                memcpy(*out+1, L, nodeCount*sizeof(unsigned char));
395                memcpy((*out)+1+nodeCount*sizeof(unsigned char),R,nodeCount*sizeof(unsigned char));
396                memcpy((*out)+1+2*nodeCount*sizeof(unsigned char),C,nodeCount*sizeof(unsigned int));
397                memcpy((*out)+1+2*nodeCount*sizeof(unsigned char)+nodeCount*sizeof(unsigned int), t, nodeCount*sizeof(unsigned char));
398                free(L);
399                free(R);
400                free(C);
401                free(t);
402                return totalSize;
403
404        }
405        else if(nodeCount<=65536)
406        {
407                unsigned short* L = (unsigned short*)malloc(nodeCount*sizeof(unsigned short));
408                memset(L, 0, nodeCount*sizeof(unsigned short));
409                unsigned short* R = (unsigned short*)malloc(nodeCount*sizeof(unsigned short));
410                memset(R, 0, nodeCount*sizeof(unsigned short));
411                unsigned int* C = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));       
412                memset(C, 0, nodeCount*sizeof(unsigned int));           
413                unsigned char* t = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
414                memset(t, 0, nodeCount*sizeof(unsigned char));         
415                pad_tree_ushort(huffmanTree,L,R,C,t,0,huffmanTree->qq[1]);
416                unsigned int totalSize = 1+2*nodeCount*sizeof(unsigned short)+nodeCount*sizeof(unsigned char) + nodeCount*sizeof(unsigned int);
417                *out = (unsigned char*)malloc(totalSize);
418                (*out)[0] = (unsigned char)sysEndianType;               
419                memcpy(*out+1, L, nodeCount*sizeof(unsigned short));
420                memcpy((*out)+1+nodeCount*sizeof(unsigned short),R,nodeCount*sizeof(unsigned short));
421                memcpy((*out)+1+2*nodeCount*sizeof(unsigned short),C,nodeCount*sizeof(unsigned int));
422                memcpy((*out)+1+2*nodeCount*sizeof(unsigned short)+nodeCount*sizeof(unsigned int),t,nodeCount*sizeof(unsigned char));
423                free(L);
424                free(R);
425                free(C);
426                free(t);               
427                return totalSize;
428        }
429        else //nodeCount>65536
430        {
431                unsigned int* L = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));
432                memset(L, 0, nodeCount*sizeof(unsigned int));
433                unsigned int* R = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));
434                memset(R, 0, nodeCount*sizeof(unsigned int));
435                unsigned int* C = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));       
436                memset(C, 0, nodeCount*sizeof(unsigned int));
437                unsigned char* t = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
438                memset(t, 0, nodeCount*sizeof(unsigned char));
439                pad_tree_uint(huffmanTree, L,R,C,t,0,huffmanTree->qq[1]);
440               
441                //debug
442                //node root = new_node2(0,0);
443                //unpad_tree_uint(L,R,C,t,0,root);             
444               
445                unsigned int totalSize = 1+3*nodeCount*sizeof(unsigned int)+nodeCount*sizeof(unsigned char);
446                *out = (unsigned char*)malloc(totalSize);
447                (*out)[0] = (unsigned char)sysEndianType;
448                memcpy(*out+1, L, nodeCount*sizeof(unsigned int));
449                memcpy((*out)+1+nodeCount*sizeof(unsigned int),R,nodeCount*sizeof(unsigned int));
450                memcpy((*out)+1+2*nodeCount*sizeof(unsigned int),C,nodeCount*sizeof(unsigned int));
451                memcpy((*out)+1+3*nodeCount*sizeof(unsigned int),t,nodeCount*sizeof(unsigned char));
452                free(L);
453                free(R);
454                free(C);
455                free(t);
456                return totalSize;               
457        }
458}
459
460void unpad_tree_uchar(HuffmanTree* huffmanTree, unsigned char* L, unsigned char* R, unsigned int* C, unsigned char *t, unsigned int i, node root)
461{
462        //root->c = C[i];
463        if(root->t==0)
464        {
465                unsigned char l, r;
466                l = L[i];
467                if(l!=0)
468                {
469                        node lroot = new_node2(huffmanTree,C[l],t[l]);
470                        root->left = lroot;
471                        unpad_tree_uchar(huffmanTree,L,R,C,t,l,lroot);
472                }
473                r = R[i];
474                if(r!=0)
475                {
476                        node rroot = new_node2(huffmanTree,C[r],t[r]);
477                        root->right = rroot;
478                        unpad_tree_uchar(huffmanTree,L,R,C,t,r,rroot);
479                }
480        }
481}
482
483void unpad_tree_ushort(HuffmanTree* huffmanTree, unsigned short* L, unsigned short* R, unsigned int* C, unsigned char* t, unsigned int i, node root)
484{
485        //root->c = C[i];
486        if(root->t==0)
487        {
488                unsigned short l, r;
489                l = L[i];
490                if(l!=0)
491                {
492                        node lroot = new_node2(huffmanTree,C[l],t[l]);
493                        root->left = lroot;
494                        unpad_tree_ushort(huffmanTree,L,R,C,t,l,lroot);
495                }
496                r = R[i];
497                if(r!=0)
498                {
499                        node rroot = new_node2(huffmanTree,C[r],t[r]);
500                        root->right = rroot;
501                        unpad_tree_ushort(huffmanTree,L,R,C,t,r,rroot);
502                }
503        }
504}
505
506void unpad_tree_uint(HuffmanTree* huffmanTree, unsigned int* L, unsigned int* R, unsigned int* C, unsigned char* t, unsigned int i, node root)
507{
508        //root->c = C[i];
509        if(root->t==0)
510        {
511                unsigned int l, r;
512                l = L[i];
513                if(l!=0)
514                {
515                        node lroot = new_node2(huffmanTree,C[l],t[l]);
516                        root->left = lroot;
517                        unpad_tree_uint(huffmanTree,L,R,C,t,l,lroot);
518                }
519                r = R[i];
520                if(r!=0)
521                {
522                        node rroot = new_node2(huffmanTree,C[r],t[r]);
523                        root->right = rroot;
524                        unpad_tree_uint(huffmanTree,L,R,C,t,r,rroot);
525                }
526        }
527}
528
529node reconstruct_HuffTree_from_bytes_anyStates(HuffmanTree *huffmanTree, unsigned char* bytes, int nodeCount)
530{
531        //printf("nodeCount=%d\n", nodeCount);
532        if(nodeCount<=256)
533        {
534                unsigned char* L = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
535                memset(L, 0, nodeCount*sizeof(unsigned char));
536                unsigned char* R = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
537                memset(R, 0, nodeCount*sizeof(unsigned char));
538                unsigned int* C = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));
539                memset(C, 0, nodeCount*sizeof(unsigned int));
540                unsigned char* t = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
541                memset(t, 0, nodeCount*sizeof(unsigned char));
542                unsigned char cmpSysEndianType = bytes[0];
543                if(cmpSysEndianType!=(unsigned char)sysEndianType)
544                {
545                        unsigned char* p = (unsigned char*)(bytes+1+2*nodeCount*sizeof(unsigned char));
546                        size_t i = 0, size = nodeCount*sizeof(unsigned int);
547                        while(1)
548                        {
549                                symTransform_4bytes(p);
550                                i+=sizeof(unsigned int);
551                                if(i<size)
552                                        p+=sizeof(unsigned int);
553                                else
554                                        break;
555                        }               
556                }
557                memcpy(L, bytes+1, nodeCount*sizeof(unsigned char));
558                memcpy(R, bytes+1+nodeCount*sizeof(unsigned char), nodeCount*sizeof(unsigned char));
559                memcpy(C, bytes+1+2*nodeCount*sizeof(unsigned char), nodeCount*sizeof(unsigned int));   
560                memcpy(t, bytes+1+2*nodeCount*sizeof(unsigned char)+nodeCount*sizeof(unsigned int), nodeCount*sizeof(unsigned char));
561                node root = new_node2(huffmanTree, C[0],t[0]);
562                unpad_tree_uchar(huffmanTree,L,R,C,t,0,root);
563                free(L);
564                free(R);
565                free(C);
566                free(t);
567                return root;
568        }
569        else if(nodeCount<=65536)
570        {
571                unsigned short* L = (unsigned short*)malloc(nodeCount*sizeof(unsigned short));
572                memset(L, 0, nodeCount*sizeof(unsigned short));
573                unsigned short* R = (unsigned short*)malloc(nodeCount*sizeof(unsigned short));
574                memset(R, 0, nodeCount*sizeof(unsigned short));
575                unsigned int* C = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));       
576                memset(C, 0, nodeCount*sizeof(unsigned int));           
577                unsigned char* t = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
578                memset(t, 0, nodeCount*sizeof(unsigned char)); 
579                               
580                unsigned char cmpSysEndianType = bytes[0];     
581                if(cmpSysEndianType!=(unsigned char)sysEndianType)
582                {
583                        unsigned char* p = (unsigned char*)(bytes+1);
584                        size_t i = 0, size = 3*nodeCount*sizeof(unsigned int);
585                        while(1)
586                        {
587                                symTransform_4bytes(p);
588                                i+=sizeof(unsigned int);
589                                if(i<size)
590                                        p+=sizeof(unsigned int);
591                                else
592                                        break;
593                        }               
594                }
595
596                memcpy(L, bytes+1, nodeCount*sizeof(unsigned short));
597                memcpy(R, bytes+1+nodeCount*sizeof(unsigned short), nodeCount*sizeof(unsigned short));
598                memcpy(C, bytes+1+2*nodeCount*sizeof(unsigned short), nodeCount*sizeof(unsigned int)); 
599
600                memcpy(t, bytes+1+2*nodeCount*sizeof(unsigned short)+nodeCount*sizeof(unsigned int), nodeCount*sizeof(unsigned char)); 
601
602                node root = new_node2(huffmanTree,0,0);
603                unpad_tree_ushort(huffmanTree,L,R,C,t,0,root);
604                free(L);
605                free(R);
606                free(C);
607                free(t);               
608                return root;                           
609        }
610        else //nodeCount>65536
611        {
612                unsigned int* L = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));
613                memset(L, 0, nodeCount*sizeof(unsigned int));
614                unsigned int* R = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));
615                memset(R, 0, nodeCount*sizeof(unsigned int));
616                unsigned int* C = (unsigned int*)malloc(nodeCount*sizeof(unsigned int));       
617                memset(C, 0, nodeCount*sizeof(unsigned int));
618                unsigned char* t = (unsigned char*)malloc(nodeCount*sizeof(unsigned char));
619                memset(t, 0, nodeCount*sizeof(unsigned char));
620                unsigned char cmpSysEndianType = bytes[0];
621                if(cmpSysEndianType!=(unsigned char)sysEndianType)
622                {
623                        unsigned char* p = (unsigned char*)(bytes+1);
624                        size_t i = 0, size = 3*nodeCount*sizeof(unsigned int);
625                        while(1)
626                        {
627                                symTransform_4bytes(p);
628                                i+=sizeof(unsigned int);
629                                if(i<size)
630                                        p+=sizeof(unsigned int);
631                                else
632                                        break;
633                        }
634                }
635
636                memcpy(L, bytes+1, nodeCount*sizeof(unsigned int));
637                memcpy(R, bytes+1+nodeCount*sizeof(unsigned int), nodeCount*sizeof(unsigned int));
638                memcpy(C, bytes+1+2*nodeCount*sizeof(unsigned int), nodeCount*sizeof(unsigned int));   
639       
640                memcpy(t, bytes+1+3*nodeCount*sizeof(unsigned int), nodeCount*sizeof(unsigned char));                   
641                                       
642                node root = new_node2(huffmanTree,0,0);
643                unpad_tree_uint(huffmanTree,L,R,C,t,0,root);
644                free(L);
645                free(R);
646                free(C);
647                free(t);
648                return root;
649        }
650}
651
652void encode_withTree(HuffmanTree* huffmanTree, int *s, size_t length, unsigned char **out, size_t *outSize)
653{
654        size_t i; 
655        int nodeCount = 0;
656        unsigned char *treeBytes, buffer[4];
657       
658        init(huffmanTree, s, length);
659        for (i = 0; i < huffmanTree->stateNum; i++)
660                if (huffmanTree->code[i]) nodeCount++; 
661        nodeCount = nodeCount*2-1;
662        unsigned int treeByteSize = convert_HuffTree_to_bytes_anyStates(huffmanTree,nodeCount, &treeBytes);
663        //printf("treeByteSize=%d\n", treeByteSize);
664        *out = (unsigned char*)malloc(length*sizeof(int)+treeByteSize);
665        intToBytes_bigEndian(buffer, nodeCount);
666        memcpy(*out, buffer, 4);
667        intToBytes_bigEndian(buffer, huffmanTree->stateNum/2); //real number of intervals
668        memcpy(*out+4, buffer, 4);
669        memcpy(*out+8, treeBytes, treeByteSize);
670        free(treeBytes);
671        size_t enCodeSize = 0;
672        encode(huffmanTree, s, length, *out+8+treeByteSize, &enCodeSize);
673        *outSize = 8+treeByteSize+enCodeSize;
674       
675        //unsigned short state[length];
676        //decode(*out+4+treeByteSize, enCodeSize, qqq[0], state);
677        //printf("dataSeriesLength=%d",length );
678}
679
680/**
681 * @par *out rememmber to allocate targetLength short_type data for it beforehand.
682 *
683 * */
684void decode_withTree(HuffmanTree* huffmanTree, unsigned char *s, size_t targetLength, int *out)
685{
686        size_t encodeStartIndex;
687        size_t nodeCount = bytesToInt_bigEndian(s);
688        node root = reconstruct_HuffTree_from_bytes_anyStates(huffmanTree,s+8, nodeCount);
689       
690        //sdi: Debug
691/*      build_code(root, 0, 0, 0);
692        int i;
693        unsigned long code_1, code_2;
694        for (i = 0; i < stateNum; i++)
695                if (code[i])
696                {               
697                        printf("%d: %lu,%lu ; %u\n", i, (code[i])[0],(code[i])[1], cout[i]);
698                        //code_1 = (code[i])[0];
699                }*/
700       
701        if(nodeCount<=256)
702                encodeStartIndex = 1+3*nodeCount*sizeof(unsigned char)+nodeCount*sizeof(unsigned int);
703        else if(nodeCount<=65536)
704                encodeStartIndex = 1+2*nodeCount*sizeof(unsigned short)+nodeCount*sizeof(unsigned char)+nodeCount*sizeof(unsigned int);
705        else
706                encodeStartIndex = 1+3*nodeCount*sizeof(unsigned int)+nodeCount*sizeof(unsigned char);
707        decode(s+8+encodeStartIndex, targetLength, root, out);
708}
709
710void SZ_ReleaseHuffman(HuffmanTree* huffmanTree)
711{
712        size_t i;
713        free(huffmanTree->pool);
714        huffmanTree->pool = NULL;
715        free(huffmanTree->qqq);
716        huffmanTree->qqq = NULL;
717        for(i=0;i<huffmanTree->stateNum;i++)
718        {
719                if(huffmanTree->code[i]!=NULL)
720                        free(huffmanTree->code[i]);
721        }
722        free(huffmanTree->code);
723        huffmanTree->code = NULL;
724        free(huffmanTree->cout);
725        huffmanTree->cout = NULL;       
726        free(huffmanTree);
727        huffmanTree = NULL;
728}
Note: See TracBrowser for help on using the repository browser.