source: tags/svn.1.5.4/ARBDB/adcompr.cxx

Last change on this file was 8309, checked in by westram, 14 years ago
  • moved much code into static scope

(partly reverted by [8310])

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 32.1 KB
Line 
1// =============================================================== //
2//                                                                 //
3//   File      : adcompr.cxx                                       //
4//   Purpose   :                                                   //
5//                                                                 //
6//   Institute of Microbiology (Technical University Munich)       //
7//   http://www.arb-home.de/                                       //
8//                                                                 //
9// =============================================================== //
10
11#include <climits>
12
13#include <arbdbt.h>
14
15#include "gb_t_prot.h"
16#include "gb_compress.h"
17#include "gb_localdata.h"
18
19#include <static_assert.h>
20
21#if defined(DEBUG)
22// #define TEST_HUFFMAN_CODE
23#endif // DEBUG
24
25#define GBTUM_COMPRESS_TREE_SIZE 32
26
27
28#define GB_READ_BIT(p, c, bp, result)    if (!bp) { c = *(p++); bp = 8; }; result = (c>>7); result &= 1; c <<= 1; bp--
29
30#define GB_INIT_WRITE_BITS(p, bp) *p = 0; bp = 8
31
32#define GB_WRITE_BITS(p, bp, bitc, bits, i)     \
33    if (bp<=0) { bp += 8; p++;  *p = 0; }       \
34    if ((i=bp-bitc)<0) {                        \
35        *p |=  bits>>(-i);                      \
36        i += 8;                                 \
37        bp += 8; p++; *p = 0;                   \
38    }                                           \
39    *p |=  bits<<i;                             \
40    bp-=bitc;
41
42#define GB_READ_BITS(p, c, bp, bitc, bits) {    \
43        long _i;                                \
44        int _r;                                 \
45        bits = 0;                               \
46        for (_i=bitc-1; _i>=0; _i--) {          \
47            GB_READ_BIT(p, c, bp, _r);          \
48            bits = (bits<<1) + _r;              \
49        } }
50
51
52STATIC_ATTRIBUTED(__ATTR__USERESULT, GB_ERROR gb_check_huffmann_tree(gb_compress_tree *t)) {
53    if (t->leave)
54        return 0;
55    if (!t->son[0])
56        return GB_export_error("Database entry corrupt (zero left son)");
57    if (!t->son[1])
58        return GB_export_error("Database entry corrupt (zero right son)");
59
60    {
61        GB_ERROR err = gb_check_huffmann_tree(t->son[0]);
62        if (err) return err;
63    }
64    return gb_check_huffmann_tree(t->son[1]);
65}
66
67#if defined(TEST_HUFFMAN_CODE)
68static void gb_dump_huffmann_tree(gb_compress_tree *t, const char *prefix) {
69    if (t->leave) {
70        long command = (long)t->son[1];
71        printf("%s", prefix);
72
73        switch (command) {
74            case GB_CS_END: printf(" [GB_CS_END]\n"); break;
75            case GB_CS_ID: printf(" [GB_CS_ID]\n"); break;
76            case GB_CS_OK: {
77                long val = (long)t->son[0];
78                printf(": value=%li (='%c')\n", val, (char)val);
79                break;
80            }
81            default: {
82                long val = (long)t->son[0];
83                printf(" other command (%li) value=%li (='%c')\n", command, val, (char)val);
84                break;
85            }
86        }
87    }
88    else {
89        int   len        = strlen(prefix);
90        char *my_prefix  = malloc(len+2);
91        strcpy(my_prefix, prefix);
92        my_prefix[len+1] = 0;
93        my_prefix[len]   = '0';
94        gb_dump_huffmann_tree(t->son[0], my_prefix);
95        my_prefix[len]   = '1';
96        gb_dump_huffmann_tree(t->son[1], my_prefix);
97        free(my_prefix);
98    }
99}
100static void gb_dump_huffmann_list(gb_compress_list *bc, const char *prefix) {
101    if (bc->command == GB_CD_NODE) {
102        int   len        = strlen(prefix);
103        char *my_prefix  = malloc(len+2);
104        strcpy(my_prefix, prefix);
105        my_prefix[len+1] = 0;
106        my_prefix[len]   = '0';
107        gb_dump_huffmann_list(bc->son[0], my_prefix);
108        my_prefix[len]   = '1';
109        gb_dump_huffmann_list(bc->son[1], my_prefix);
110        free(my_prefix);
111    }
112    else {
113        printf("%s  value=%i (='%c') count=%li\n", prefix, bc->value, (char)bc->value, bc->count);
114    }
115}
116
117#endif // TEST_HUFFMAN_CODE
118
119gb_compress_tree *gb_build_uncompress_tree(const unsigned char *data, long short_flag, char **end) {
120    gb_compress_tree    *Main, *t;
121    long                 bits, mask, i;
122    const unsigned char *p;
123    GB_ERROR             error;
124
125    Main = (gb_compress_tree *)gbm_get_mem(sizeof(gb_compress_tree), GBM_CB_INDEX);
126    for (p=data; *p; p+=3+short_flag) {
127        bits = p[0];
128        mask = 0x80;
129        for (i=7; i; i--, mask=mask>>1) if (mask & bits) break; // find first bit
130        if (!i) {
131            GB_internal_error("Data corrupt");
132            return 0;
133        }
134        t = Main;
135        for (; i; i--) {
136            if (t->leave) {
137                GB_export_error("Corrupt data !!!");
138                return 0;
139            }
140            mask = mask>>1;
141            if (mask & bits) {
142                if (!t->son[1]) {
143                    t->son[1] = (gb_compress_tree *)gbm_get_mem(sizeof(gb_compress_tree), GBM_CB_INDEX);
144                }
145                t=t->son[1];
146            }
147            else {
148                if (!t->son[0]) {
149                    t->son[0] = (gb_compress_tree *)gbm_get_mem(sizeof(gb_compress_tree), GBM_CB_INDEX);
150                }
151                t=t->son[0];
152            }
153        }
154        if (t->leave) {
155            GB_export_error("Corrupt data !!!");
156            return 0;
157        }
158        t->leave = 1;
159        if (short_flag) {
160            t->son[0] = (gb_compress_tree *)(long)((p[2]<<8)+p[3]);
161        }
162        else {
163            t->son[0] = (gb_compress_tree *)(long)(p[2]);
164        }
165        t->son[1] = (gb_compress_tree *)(long)p[1]; // command
166    }
167    if (end) *end = ((char *)p)+1;
168    if ((error = gb_check_huffmann_tree(Main))) {
169        GB_internal_errorf("%s", error);
170        gb_free_compress_tree(Main);
171        return 0;
172    }
173
174#if defined(TEST_HUFFMAN_CODE)
175    printf("Huffman tree:\n");
176    gb_dump_huffmann_tree(Main, "");
177#endif // TEST_HUFFMAN_CODE
178
179    return Main;
180}
181
182void gb_free_compress_tree(gb_compress_tree *tree) {
183    if (tree) {
184        if (!tree->leave) {
185            if (tree->son[0]) gb_free_compress_tree(tree->son[0]);
186            if (tree->son[1])gb_free_compress_tree(tree->son[1]);
187        }
188    }
189    gbm_free_mem(tree, sizeof(gb_compress_tree), GBM_CB_INDEX);
190}
191
192gb_compress_list *gb_build_compress_list(const unsigned char *data, long short_flag, long *size) {
193    int                  i, maxi, bitc;
194    int                  val, bits, mask, value;
195    const unsigned char *p;
196
197    enum gb_compress_list_commands command = (enum gb_compress_list_commands)0;
198
199    maxi = 0;
200    val  = bits = mask = value = bitc = 0;
201    for (p=data; *p; p+=3+short_flag) {
202        i = (p[2]);
203        if (short_flag) {
204            i = (i<<8)+p[3];
205        }
206        if (i>maxi) maxi = i;
207    }
208    *size = maxi;
209
210    gb_compress_list *list = (gb_compress_list *)GB_calloc(sizeof(gb_compress_list), (size_t)maxi+1);
211
212    maxi = 0;
213    val = -1;
214
215    for (p=data; *p; p+=3+short_flag) {
216        val = (p[2]);
217        if (short_flag) val = (val<<8)+p[3];
218
219        for (i=maxi; i<val; i++) {
220            list[i].command = command;
221            list[i].mask    = mask;
222            list[i].bitcnt  = bitc;
223            list[i].bits    = bits;
224            list[i].value   = value;
225        }
226        maxi = val;
227
228        command = (enum gb_compress_list_commands)(p[1]);
229        bits = p[0];
230        mask = 0x80;
231        for (bitc=7; bitc; bitc--, mask=mask>>1) if (mask & bits) break; // find first bit
232        mask = 0xff>>(8-bitc);
233        bits = bits & mask;
234        value = val;
235    }
236    i = val;
237    list[i].command = command;
238    list[i].mask    = mask;
239    list[i].bitcnt  = bitc;
240    list[i].bits    = bits;
241    list[i].value   = value;
242    return list;
243}
244
245// ------------------------
246//      bit compression
247
248
249char *gb_compress_bits(const char *source, long size, const unsigned char *c_0, long *msize)
250{
251    const unsigned char *s      = (const unsigned char *)source;
252    char                *buffer = GB_give_other_buffer(source, size);
253    char                *dest   = buffer;
254
255    long  i, j;
256    int   bitptr, bits, bitc;
257    int   zo_flag = 0;
258    long  len;
259    int   h_i, command;
260    int   isNull[256];
261
262    for (i = 0; i<256; ++i) isNull[i] = 0;
263    for (i = 0; c_0[i]; ++i) isNull[c_0[i]] = 1;
264
265    GB_INIT_WRITE_BITS(dest, bitptr);
266    for (len = size, i = 0; len; len--) {
267        if (zo_flag == isNull[*(s++)]) {
268            zo_flag = 1 - zo_flag;
269            for (command = GB_CS_SUB; command != GB_CS_OK;) {
270                if (i>gb_local->bc_size) j = gb_local->bc_size; else j = i;
271                bits = gb_local->bitcompress[j].bits;
272                bitc = gb_local->bitcompress[j].bitcnt;
273                command = gb_local->bitcompress[j].command;
274                i -= gb_local->bitcompress[j].value;
275                GB_WRITE_BITS(dest, bitptr, bitc, bits, h_i);
276            }
277            i = 0;
278        }
279        i++;
280    }
281    for (command = GB_CS_SUB; command != GB_CS_OK;) {
282        if (i>gb_local->bc_size) j = gb_local->bc_size; else j = i;
283        bits = gb_local->bitcompress[j].bits;
284        bitc = gb_local->bitcompress[j].bitcnt;
285        command = gb_local->bitcompress[j].command;
286        i -= gb_local->bitcompress[j].value;
287        GB_WRITE_BITS(dest, bitptr, bitc, bits, h_i);
288    }
289    *msize = dest - buffer + 1;
290    return buffer;
291}
292
293
294GB_BUFFER gb_uncompress_bits(const char *source, long size, char c_0, char c_1)
295{
296    const char       *s;
297    char             *p, *buffer, ch = 0, outc;
298    long              bitp, lastpos, pos;
299    gb_compress_tree *Main, *t;
300    long              command;
301
302    Main = gb_local->bituncompress;
303    bitp = 0;
304    s = source;
305    buffer = p = GB_give_other_buffer(source, size+1);
306    outc = c_0;
307
308    for (pos = 0; pos<size;) {
309        lastpos = pos;
310        for (command = GB_CS_SUB; command != GB_CS_OK;) {
311            for (t=Main; !t->leave;) {
312                int bit;
313                GB_READ_BIT(s, ch, bitp, bit);
314                t = t->son[bit];
315            }
316            command = (long) t->son[1];
317            pos += (long)t->son[0];
318        }
319        for (; lastpos<pos; lastpos++) *(p++) = outc;
320        if (outc==c_0) outc=c_1; else outc=c_0;
321    }
322    *p = 0;
323    return buffer;
324}
325
326
327
328/* Runlength encoding produces..
329 *
330 * from source: string
331 * dest:   [command]+
332 *
333 * command     data                     meaning
334 *
335 * -122        low high byte            'byte' was repeated 'low'+256*'high' times
336 * -119..-1    byte                     'byte' was repeated -'command' times
337 * 0           ---                      end
338 * 1..119      [byte]+                 'command' data bytes follow
339 */
340
341static char *g_b_write_run(char *dest, int scount, int lastbyte) {
342    while (scount> 0xffff) {
343        *(dest++) = 0x100-122;
344        *(dest++) = 0xff;
345        *(dest++) = 0xff;
346        *(dest++) = lastbyte;
347        scount -= 0xffff;
348    }
349    if (scount >250) {
350        *(dest++) = 0x100-122;
351        *(dest++) = scount & 0xff;
352        *(dest++) = (scount >> 8) & 0xff;
353        *(dest++) = lastbyte;
354        return dest;
355    }
356
357    while (scount>120) {                            // 120 blocks
358        *(dest++) = 0x100 - 120;
359        *(dest++) = lastbyte;
360        scount -= 120;
361    }
362
363    if (scount) {                       // and rest
364        *(dest++) = -scount;
365        *(dest++) = lastbyte;
366    }
367    return dest;
368}
369
370#define GB_COPY_NONRUN(dest, source, len)       \
371    while (len > 120) {                         \
372        int _i = 120;                           \
373        char *_p;                               \
374        len -= _i;                              \
375        *(dest++) = _i;                         \
376        _p = dest; dest+=_i;                    \
377        while (_i--) {                          \
378            *(_p++) = *(source++);              \
379        }                                       \
380    }                                           \
381    if  (len >0) {                              \
382        int _i = len;                           \
383        char *_p;                               \
384        len = 0;                                \
385        *(dest++) = _i;                         \
386        _p = dest; dest+=_i;                    \
387        while (_i--) {                          \
388            *(_p++) = *(source++);              \
389        }                                       \
390    }
391
392void gb_compress_equal_bytes_2(const char *source, long size, long *msize, char *dest) {
393    long        i;                                  // length counter
394    int         last, rbyte;                        // next and akt value
395    long        scount;                             // same count; count equal bytes
396    char       *buffer = dest;
397    const char *sourcenequal;                       // begin of non equal section
398    long        hi;                                 // to temporary store i
399    int         hsize;
400
401    sourcenequal = source;
402    rbyte = *(source ++);
403    last = -1;
404    for (i=size-1; i;) {
405        if (rbyte!=last) {                          // Search an equal pair
406            last = rbyte;
407            rbyte = *(source ++); i--;
408            continue;
409        }                                           // last rbyte *(source)
410        hi = i+1;
411        while (i) {                                 // get equal bytes
412            rbyte = *(source ++); i--;
413            if (rbyte!=last) break;
414        }
415        scount = hi-i;                              // number of equal bytes ; at end e.b.-1
416        if (scount <= GB_RUNLENGTH_SIZE) continue;  // less than 4-> no runlength compression
417
418        /* compression !!!
419         * 1. copy unequal bytes
420         * 2. fill rest
421         */
422
423        hsize   = source - sourcenequal - scount -1; // hsize of non equal bytes
424        source  = sourcenequal;
425        hi      = i;                                // i=unequal length
426        GB_COPY_NONRUN(dest, source, hsize);
427        dest    = g_b_write_run(dest, scount, last);
428        source += scount;                           // now equal bytes
429
430        sourcenequal = source++;                    // no rbyte written yet
431        last         = rbyte;
432        i            = hi;
433        if (i) {
434            rbyte = *(source++); i--;
435        }
436    }
437    // and now rest which is not compressed
438    hsize = source - sourcenequal;
439    source = sourcenequal;
440    GB_COPY_NONRUN(dest, source, hsize);
441
442    *(dest++) = 0;                  // end of data
443    *msize = dest-buffer;
444    if (*msize >size*9/8) printf("ssize %d, dsize %d\n", (int)size, (int)*msize);
445}
446
447static GB_BUFFER gb_compress_equal_bytes(const char *source, long size, long *msize, int last_flag) {
448    char *dest;
449    char *buffer;
450
451    dest  = buffer = GB_give_other_buffer(source, size*9/8);
452    *(dest++) = GB_COMPRESSION_RUNLENGTH | last_flag;
453    gb_compress_equal_bytes_2(source, size, msize, dest);
454    (*msize) ++;            // Tag byte
455    return buffer;
456}
457
458struct huffmann_list {
459    huffmann_list    *next;
460    long              val;
461    gb_compress_list *element;
462};
463
464static huffmann_list *huffmann_listhead = NULL;
465
466static void gb_compress_huffmann_add_to_list(long val, gb_compress_list *element) {
467    huffmann_list *dat, *search, *searchlast;
468
469    dat          = (huffmann_list *)gbm_get_mem(sizeof(huffmann_list), GBM_CB_INDEX);
470    dat->val     = val;
471    dat->element = element;
472
473    searchlast = 0;
474    for (search = huffmann_listhead; search; search = search->next) {
475        if (val<search->val) break;
476        searchlast = search;
477    }
478    if (huffmann_listhead) {
479        if (searchlast) {
480            dat->next = searchlast->next;
481            searchlast->next = dat;
482        }
483        else {
484            dat->next = huffmann_listhead;
485            huffmann_listhead = dat;
486        }
487    }
488    else {
489        huffmann_listhead = dat;
490    }
491}
492
493static long gb_compress_huffmann_pop(long *val, gb_compress_list **element) {
494    huffmann_list *dat;
495    if ((dat = huffmann_listhead)) {
496        huffmann_listhead = dat->next;
497        *val = dat->val;
498        *element = dat->element;
499        gbm_free_mem(dat, sizeof(huffmann_list), GBM_CB_INDEX);
500        return 1;
501    }
502    else {
503        GB_internal_error("huffman compression failed");
504        return 0;
505    }
506}
507
508static char *gb_compress_huffmann_rek(gb_compress_list *bc, int bits, int bitcnt, char *dest) {
509    if (bc->command == GB_CD_NODE) {
510        dest = gb_compress_huffmann_rek(bc->son[0], (bits<<1), bitcnt+1, dest);
511        dest = gb_compress_huffmann_rek(bc->son[1], (bits<<1)+1, bitcnt+1, dest);
512        gbm_free_mem(bc, sizeof(gb_compress_list), GBM_CB_INDEX);
513        return dest;
514    }
515    else {
516        *(dest++) = bits;
517        *(dest++) = bc->command;
518        *(dest++) = bc->value;
519        bc->bitcnt = bitcnt;
520        bc->mask = 0xff>>(8-bitcnt);
521        bc->bits = bits&bc->mask;
522        return dest;
523    }
524}
525
526static GB_BUFFER gb_compress_huffmann(GB_CBUFFER source, long size, long *msize, int last_flag) {
527    char          *buffer;
528    unsigned char *s;
529    char          *dest;
530    int            val, h_i, command;
531    long           id = 0, end, len;
532
533    gb_compress_list  bitcompress[257], *pbc;
534    gb_compress_list *pbid;
535
536    memset((char *)(&bitcompress[0]), 0, sizeof(gb_compress_list)*257);
537    end = 256;
538
539    dest = buffer = GB_give_other_buffer(source, size*2+3*GBTUM_COMPRESS_TREE_SIZE+1);
540    *(dest++) = GB_COMPRESSION_HUFFMANN | last_flag;
541
542    {
543        long level;
544        long i;
545        long restcount;
546
547        long vali[2] = { 0, 0 };
548
549        gb_compress_list *element1 = 0;
550        gb_compress_list *element2 = 0;
551        gb_compress_list *bc       = 0;
552
553        s = (unsigned char *)source;
554        for (len = size; len; len--) {
555            bitcompress[*(s++)].count++;
556        }
557        level = size/GBTUM_COMPRESS_TREE_SIZE;
558        restcount = 0;
559        for (i=0; i<256; i++) {
560            bitcompress[i].value = (int)i;
561            if (bitcompress[i].count>level) {
562                gb_compress_huffmann_add_to_list(bitcompress[i].count, &bitcompress[i]);
563                bitcompress[i].command = GB_CS_OK;
564            }
565            else {
566                restcount += bitcompress[i].count;
567                bitcompress[i].count = 0;
568                id = i;
569                bitcompress[i].command = GB_CS_ID;
570            }
571        }
572        bitcompress[end].command = GB_CS_END;
573
574        gb_compress_huffmann_add_to_list(restcount, &bitcompress[id]);
575        gb_compress_huffmann_add_to_list(1, &bitcompress[end]);
576        while (huffmann_listhead->next) {
577            gb_compress_huffmann_pop(&(vali[0]), &element1);
578            gb_compress_huffmann_pop(&(vali[1]), &element2);
579
580            bc          = (gb_compress_list *)gbm_get_mem(sizeof(gb_compress_list), GBM_CB_INDEX);
581            bc->command = GB_CD_NODE;
582            bc->son[0]  = element1;
583            bc->son[1]  = element2;
584
585            if (element1->command == GB_CD_NODE) {
586                bc->bits = element1->bits+1;
587                if (element2->command == GB_CD_NODE && element2->bits >= bc->bits) bc->bits = element2->bits+1;
588            }
589            else {
590                if (element2->command == GB_CD_NODE) {
591                    bc->bits = element2->bits+1;
592                }
593                else {
594                    bc->bits = 1;
595                }
596            }
597
598            gb_assert(bc->bits <= 7); // max. 7 bits allowed
599
600            // if already 6 bits used -> put to end of list; otherwise sort in
601            gb_compress_huffmann_add_to_list(bc->bits >= 6 ? LONG_MAX : vali[0]+vali[1], bc);
602        }
603        gb_compress_huffmann_pop(&(vali[0]), &element1);
604#if defined(TEST_HUFFMAN_CODE)
605        printf("huffman list:\n");
606        gb_dump_huffmann_list(bc, "");
607#endif // TEST_HUFFMAN_CODE
608        dest      = gb_compress_huffmann_rek(bc, 1, 0, dest);
609        *(dest++) = 0;
610    }
611    pbid =  &bitcompress[id];
612    s = (unsigned char *)source;
613    {
614        int bitptr, bits, bitc;
615
616        GB_INIT_WRITE_BITS(dest, bitptr);
617        for (len = size; len; len--) {
618            val = *(s++);
619            command = bitcompress[val].command;
620            if (command == GB_CS_OK) {
621                pbc = &bitcompress[val];
622                bits = pbc->bits;
623                bitc = pbc->bitcnt;
624                GB_WRITE_BITS(dest, bitptr, bitc, bits, h_i);
625            }
626            else {
627                bits = pbid->bits;
628                bitc = pbid->bitcnt;
629                GB_WRITE_BITS(dest, bitptr, bitc, bits, h_i);
630
631                bits = val;
632                bitc = 8;
633                GB_WRITE_BITS(dest, bitptr, bitc, bits, h_i);
634            }
635        }
636        bits = bitcompress[end].bits;
637        bitc = bitcompress[end].bitcnt;
638        GB_WRITE_BITS(dest, bitptr, bitc, bits, h_i);
639    }
640    *msize = dest - buffer + 1;
641#if defined(TEST_HUFFMAN_CODE)
642    printf("huffman compression %li -> %li (%5.2f %%)\n", size, *msize, (double)((double)(*msize)/size*100));
643#endif // TEST_HUFFMAN_CODE
644    if (*msize >size*2) printf("ssize %d, size %d\n", (int)size, (int)*msize);
645    return buffer;
646}
647
648
649static GB_BUFFER gb_uncompress_equal_bytes(GB_CBUFFER s, long size, long *new_size) {
650    const signed char *source = (signed char*)s;
651    char              *dest;
652    unsigned int       c;
653    long               j;
654    long               i, k;
655    char              *buffer;
656
657    dest = buffer = GB_give_other_buffer((char *)source, size);
658
659#if defined(DEBUG) && 0
660    printf("gb_uncompress_equal_bytes(size=%li):\n", size);
661#endif // DEBUG
662
663    for (i=size; i;) {
664        j = *(source++);
665#if defined(DEBUG) && 0
666        printf("size=%li (code=%i)\n", i, (int)j);
667#endif // DEBUG
668        if (j>0) {                                  // uncompressed data block
669            if (j>i) j=i;
670            i -= j;
671            for (; j; j--) {
672                *(dest++) = (char)(*(source++));
673            }
674        }
675        else {                                      // equal bytes compressed
676            if (!j) break;                          // end symbol
677            if (j == -122) {
678                j = *(source++) & 0xff;
679                j |= ((*(source++)) << 8) &0xff00;
680                j = -j;
681            }
682            c = *(source++);
683            i += j;
684            if (i<0) {
685                j += -i;
686                i = 0;
687            }
688            if (j<-30) {                            // set multiple bytes
689                j = -j;
690                if (((long)dest) & 1) {
691                    *(dest++) = c;
692                    j--;
693                }
694                if (((long)dest) &2) {
695                    *(dest++) = c;
696                    *(dest++) = c;
697                    j-=2;
698                }
699                c &= 0xff;                          // copy c to upper bytes
700                c |= (c<<8);
701                c |= (c<<16);
702                k  = j&3;
703                j  = j>>2;
704                for (; j; j--) {
705                    *((GB_UINT4 *)dest) = c;
706                    dest += sizeof(GB_UINT4);
707                }
708                j = k;
709                for (; j; j--) *(dest++) = c;
710            }
711            else {
712                for (; j; j++) *(dest++) = c;
713            }
714        }
715    }
716
717    *new_size = dest-buffer;
718    gb_assert(size >= *new_size);                   // buffer overflow
719
720    return buffer;
721}
722
723static GB_BUFFER gb_uncompress_huffmann(GB_CBUFFER source, long maxsize, long *new_size) {
724    gb_compress_tree *un_tree, *t;
725
726    char *data[1];
727    char *p, *buffer;
728    long  bitp;
729    char  ch = 0, *s;
730    long  val, command;
731
732    un_tree = gb_build_uncompress_tree((unsigned char *)source, 0, data);
733    if (!un_tree) return 0;
734
735    bitp = 0;
736    buffer = p = GB_give_other_buffer(source, maxsize);
737    s = data[0];
738    while (1) {
739        for (t = un_tree; !t->leave;) {
740            int bit;
741            GB_READ_BIT(s, ch, bitp, bit);
742            t = t->son[bit];
743        }
744        command = (long) t->son[1];
745        if (command == GB_CS_END) break;
746        if (command == GB_CS_ID) {
747            GB_READ_BITS(s, ch, bitp, 8, val);
748        }
749        else {
750            val = (long) t->son[0];
751        }
752        *(p++) = (int)val;
753    }
754    gb_free_compress_tree(un_tree);
755
756    *new_size = p-buffer;
757    gb_assert(maxsize >= *new_size);                // buffer overflow
758
759    return buffer;
760}
761
762GB_BUFFER gb_uncompress_bytes(GB_CBUFFER source, long size, long *new_size) {
763    char *data     = gb_uncompress_huffmann(source, size, new_size);
764    if (data) data = gb_uncompress_equal_bytes(data, size, new_size);
765    gb_assert(!data || size >= *new_size);          // buffer overflow
766    return data;
767}
768
769// -------------------------------------------------
770//      Compress long and floats (4 byte values)
771
772
773GB_BUFFER gb_uncompress_longs_old(GB_CBUFFER source, long size, long *new_size)
774{                               // size is byte value
775    char *res  = 0;
776    char *data = gb_uncompress_huffmann(source, (size*9)/8, new_size);
777    if (data) {
778        char *p, *s0, *s1, *s2, *s3;
779        GB_UINT4  mi, i;
780
781        data = gb_uncompress_equal_bytes(data, size, new_size);
782
783        gb_assert(*new_size == size);
784        res = p = GB_give_other_buffer(data, size);
785
786        COMPILE_ASSERT(sizeof(GB_UINT4) == 4);
787
788        mi = (GB_UINT4)(size / 4);
789        s0 = data + 0 * mi;
790        s1 = data + 1 * mi;
791        s2 = data + 2 * mi;
792        s3 = data + 3 * mi;
793
794        for (i = 0; i < mi; i++) {
795            *(p++) = *(s0++);
796            *(p++) = *(s1++);
797            *(p++) = *(s2++);
798            *(p++) = *(s3++);
799        }
800
801        *new_size = mi*4;
802    }
803    return res;
804}
805
806
807static GB_BUFFER gb_uncompress_longs(GB_CBUFFER data, long size, long *new_size) {
808    const char *s0, *s1, *s2, *s3;
809    char       *p, *res;
810    long        mi, i;
811
812    res = p = GB_give_other_buffer(data, size);
813
814    COMPILE_ASSERT(sizeof(GB_UINT4) == 4);
815
816    mi = size / 4;
817    s0 = data + 0 * mi;
818    s1 = data + 1 * mi;
819    s2 = data + 2 * mi;
820    s3 = data + 3 * mi;
821
822    for (i = 0; i < mi; i++) {
823        *(p++) = *(s0++);
824        *(p++) = *(s1++);
825        *(p++) = *(s2++);
826        *(p++) = *(s3++);
827    }
828
829    *new_size = mi*4;
830    return res;
831}
832
833static GB_BUFFER gb_compress_longs(GB_CBUFFER source, long size, int last_flag) {
834    long        mi, i;
835    const char *p;
836    char       *s0, *s1, *s2, *s3;
837    char       *dest = GB_give_other_buffer(source, size+1);
838
839    mi = size/4;
840    p = source;
841    *(dest) = GB_COMPRESSION_SORTBYTES | last_flag;
842    s0 = dest + 0*mi + 1;
843    s1 = dest + 1*mi + 1;
844    s2 = dest + 2*mi + 1;
845    s3 = dest + 3*mi + 1;
846    for (i=0; i<mi; i++) {
847        *(s0++) = *(p++);
848        *(s1++) = *(p++);
849        *(s2++) = *(p++);
850        *(s3++) = *(p++);
851    }
852    return dest;
853}
854
855// -----------------------------
856//      Dictionary Functions
857
858GB_DICTIONARY * gb_get_dictionary(GB_MAIN_TYPE *Main, GBQUARK key) {
859    gb_Key *ks = &Main->keys[key];
860    if (ks->gb_key_disabled) return 0;
861    if (!ks->gb_key) {
862        gb_load_single_key_data((GBDATA *)Main->data, key);
863        if (Main->gb_key_data && !ks->gb_key) {
864            GB_internal_error("Couldn't load gb_key");
865        }
866    }
867    return Main->keys[key].dictionary;
868}
869
870bool GB_is_dictionary_compressed(GBDATA *gbd) {
871    int         type = GB_TYPE(gbd);
872    const char *data = GB_GETDATA(gbd);
873
874    if (data) {
875        if (gbd->flags.compressed_data) {
876            long     size     = GB_UNCOMPRESSED_SIZE(gbd, type);
877            int      last     = 0;
878            GB_ERROR error    = 0;
879            long     new_size = -1;                 // dummy
880
881            while (!last) {
882                int c = *((unsigned char *)(data++));
883
884                if (c & GB_COMPRESSION_LAST) {
885                    last = 1;
886                    c &= ~GB_COMPRESSION_LAST;
887                }
888
889                if (c == GB_COMPRESSION_DICTIONARY) {
890                    return true;
891                }
892
893                if (c == GB_COMPRESSION_HUFFMANN) {
894                    data = gb_uncompress_huffmann(data, size + GB_COMPRESSION_TAGS_SIZE_MAX, &new_size);
895                }
896                else if (c == GB_COMPRESSION_RUNLENGTH) {
897                    data = gb_uncompress_equal_bytes(data, size + GB_COMPRESSION_TAGS_SIZE_MAX, &new_size);
898                }
899                else if (c == GB_COMPRESSION_SEQUENCE) {
900                    data = gb_uncompress_by_sequence(gbd, data, size, &error, &new_size);
901                }
902                else if (c == GB_COMPRESSION_SORTBYTES) {
903                    data = gb_uncompress_longs(data, size, &new_size);
904                }
905                else {
906                    error = GB_export_errorf("Internal Error: Cannot uncompress data of field '%s'", GB_read_key_pntr(gbd));
907                }
908
909                if (error) {
910                    GB_internal_error(error);
911                    break;
912                }
913            }
914        }
915    }
916
917    return false;
918}
919
920// -----------------------------------
921//      Top compression algorithms
922
923GB_BUFFER gb_compress_data(GBDATA *gbd, int key, GB_CBUFFER source, long size, long *msize, GB_COMPRESSION_MASK max_compr, bool pre_compressed) {
924    // Compress a data string.
925    //
926    // Returns:
927    // - NULL if no compression makes sense
928    // - otherwise returns compressed data and stores its size in 'msize'
929
930    char *data;
931    int   last_flag = GB_COMPRESSION_LAST;
932
933    if (pre_compressed) {
934        last_flag = 0;
935    }
936
937    gb_assert(1);
938
939    if (max_compr & GB_COMPRESSION_SORTBYTES) {
940        source = gb_compress_longs(source, size, last_flag);
941        last_flag = 0;
942        size++;                 // @@@ OLI
943    }
944    else if (max_compr & GB_COMPRESSION_DICTIONARY) {
945        GB_MAIN_TYPE *Main = GB_MAIN(gbd);
946        GB_DICTIONARY *dict;
947        if (!key) {
948            key = GB_KEY_QUARK(gbd);
949        }
950        dict = gb_get_dictionary(Main, key);
951        if (dict) {
952            long real_size = size-(GB_TYPE(gbd)==GB_STRING); // for strings w/o trailing zero
953
954            if (real_size) {
955                data = gb_compress_by_dictionary(dict, source, real_size, msize, last_flag, 9999, 3);
956
957                if ((*msize<=10 && size>10) || *msize < size*7/8) {  // successfull compression
958                    source = data;
959                    size = *msize;
960                    last_flag = 0;
961                }
962            }
963        }
964
965    }
966    if (max_compr & GB_COMPRESSION_RUNLENGTH && size > GB_RUNLENGTH_MIN_SIZE) {
967        data = gb_compress_equal_bytes(source, size, msize, last_flag);
968        if (*msize < size-10 && *msize < size*7/8) { // successfull compression
969            source = data;
970            size = *msize;
971            last_flag = 0;
972        }
973    }
974
975    if (max_compr & GB_COMPRESSION_HUFFMANN && size > GB_HUFFMAN_MIN_SIZE) {
976        data = gb_compress_huffmann(source, size, msize, last_flag);
977        if (*msize < size-10 && *msize < size*7/8) { // successfull compression
978            source = data;
979            size = *msize;
980            last_flag = 0;
981        }
982    }
983
984    *msize = size;
985
986    if (last_flag) return 0;                        // no compression
987    return (char *)source;
988}
989
990GB_CBUFFER gb_uncompress_data(GBDATA *gbd, GB_CBUFFER source, long size) {
991    int         last     = 0;
992    const char *data     = (char *)source;
993    long        new_size = -1;
994    GB_ERROR    error    = 0;
995
996    while (!last) {
997        int c = *((unsigned char *)(data++));
998        if (c & GB_COMPRESSION_LAST) {
999            last = 1;
1000            c &= ~GB_COMPRESSION_LAST;
1001        }
1002        if (c == GB_COMPRESSION_HUFFMANN) {
1003            data = gb_uncompress_huffmann(data, size + GB_COMPRESSION_TAGS_SIZE_MAX, &new_size);
1004        }
1005        else if (c == GB_COMPRESSION_RUNLENGTH) {
1006            data = gb_uncompress_equal_bytes(data, size + GB_COMPRESSION_TAGS_SIZE_MAX, &new_size);
1007        }
1008        else if (c == GB_COMPRESSION_DICTIONARY) {
1009            data = gb_uncompress_by_dictionary(gbd, data, size + GB_COMPRESSION_TAGS_SIZE_MAX, &new_size);
1010        }
1011        else if (c == GB_COMPRESSION_SEQUENCE) {
1012            data = gb_uncompress_by_sequence(gbd, data, size, &error, &new_size);
1013        }
1014        else if (c == GB_COMPRESSION_SORTBYTES) {
1015            data = gb_uncompress_longs(data, size, &new_size);
1016        }
1017        else {
1018            error = GBS_global_string("Internal Error: Cannot uncompress data of field '%s'", GB_read_key_pntr(gbd));
1019        }
1020
1021        if (!data && !error) error = GB_await_error();
1022        if (error) last = 1;                        // sth went wrong, stop
1023    }
1024
1025    if (!error && new_size != size) {
1026        error = GBS_global_string("Wrong decompressed size (expected=%li, got=%li)", size, new_size);
1027    }
1028
1029    if (error) {
1030        GB_export_error(error);
1031        data = 0;
1032    }
1033
1034    return data;
1035}
1036
Note: See TracBrowser for help on using the repository browser.