Context Navigation

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

Visit:

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
52	STATIC_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)
68	static 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	}
100	static 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
119	gb_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
182	void 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
192	gb_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
249	char 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
294	GB_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
341	static 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
392	void 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 >size9/8) printf("ssize %d, dsize %d\n", (int)size, (int)*msize);
445	}
446
447	static 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
458	struct huffmann_list {
459	huffmann_list *next;
460	long val;
461	gb_compress_list *element;
462	};
463
464	static huffmann_list *huffmann_listhead = NULL;
465
466	static 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
493	static 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
508	static 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
526	static 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, size2+3GBTUM_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 >size2) printf("ssize %d, size %d\n", (int)size, (int)*msize);
645	return buffer;
646	}
647
648
649	static 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
723	static 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
762	GB_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
773	GB_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, (size9)/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 = mi4;
802	}
803	return res;
804	}
805
806
807	static 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 = mi4;
830	return res;
831	}
832
833	static 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
858	GB_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
870	bool 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
923	GB_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
990	GB_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.

Download in other formats: