1 /******************************************************************************
2 *
3 * Copyright (C) 2009, The Gentee Group. All rights reserved.
4 * This file is part of the Gentee open source project - http://www.gentee.com.
5 *
6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT").
7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS
8 * ACCEPTANCE OF THE AGREEMENT.
9 *
10 * Author: Alexey Krivonogov ( gentee )
11 *
12 ******************************************************************************/
13
14 #include "huffman.h"
15 #include "..\LZGE\lzge.h"
16
17 //--------------------------------------------------------------------------
18
19 dword STACKAPI huf_bits( pshuf huf, dword item )
20 {
21 register pshufleaf cur = huf->tree + item;
22 register dword depth = 0;
23
24 if ( !cur->up ) return 0;
25
26 do {
27 depth++;
28 cur = cur->up;
29 } while ( cur != huf->root );
30
31 return depth;
32 }
33
34 //--------------------------------------------------------------------------
35
36 void STDCALL huf_entree( pshuf huf )
37 {
38 dword bits;
39 dword i, k;
40 dword freq[ 2048 ];
41 pbyte st = huf->ptr;
42
43 // Вычитаем предыдущие длины
44
45 i = max( 2, lzge_bits( huf->min ));
46 bits = lzge_bits( huf->max - huf->min + 1 );
47 bits = max( i, bits );
48
49 huf_packnum( huf, bits - 1, huf->numcode < 32 ? 2 : 3 );
50 // if ( huf->fixed )
51 // printf("Bits=%i min=%i max=%i\n", bits, huf->min, huf->max );
52 huf_packnum( huf, huf->min, bits );
53 huf_packnum( huf, huf->max - huf->min, bits );
54 for ( i = 0; i < huf->numcode; i++ )
55 {
56 freq[ i ] = huf->tree[ i ].freq;
57 // Сдвигаем на минимум
58 k = huf->prevlen[ i ];
59 huf->prevlen[i] = 0;
60 if ( freq[i] )
61 freq[ i ] -= huf->min - 1;
62
63 if ( freq[i] <= PRET_MAXCODE )
64 {
65 huf->prevlen[i] = (byte)freq[i];
66 freq[i] = ( freq[i] - k ) % ( PRET_MAXCODE + 1 );
67 // huf->prevlen[i] = freq[i];
68 }
69 // if ( !huf->fixed && freq[i] > PRET_MAXCODE )
70 // printf("%i ", freq[i] );
71
72 }
73 if ( huf->fixed )
74 {
75 for ( i = 0; i < huf->numcode; i++ )
76 huf_packnum( huf, freq[ i ], bits );
77 }
78 else
79 {
80 shuf huftree;
81 dword fi = 0;
82
83 // Переводим длины в специальное представление
84 for ( i = 0; i < huf->numcode; i++ )
85 {
86 if ( !freq[i] )
87 {
88 k = i + 1;
89 while ( k < huf->numcode && !freq[k] &&
90 ( k - i < PRET_MAXZERO - 1 ))
91 k++;
92 // if ( k - i == PRET_MAXZERO - 1 )
93 // printf("Len=%i\n", k- i );
94 k -= i;
95 if ( k > 3 )
96 {
97 i += k - 1;
98 if ( k < PRET_OFF2 )
99 freq[ fi++ ] = (( k - PRET_OFF1 ) << 24 ) | PRET_ZERO2;
100 else
101 if ( k < PRET_OFF3 )
102 freq[ fi++ ] = (( k - PRET_OFF2 ) << 24 ) | PRET_ZERO4;
103 else
104 // freq[ fi++ ] = (( k - 16 ) << 24 ) | PRET_ZERO5;
105 freq[ fi++ ] = (( k - PRET_OFF3 ) << 24 ) | PRET_ZERO6;
106 continue;
107 }
108 }
109 if ( freq[i] > PRET_MAXCODE )
110 {
111 freq[ fi++ ] = ( freq[i] << 24 ) | PRET_BIG;
112 }
113 else
114 freq[ fi++ ] = freq[i];
115 }
116 huf_new( &huftree, PRET_ALPHABET );
117 huftree.ptr = huf->ptr;
118 huftree.bit = huf->bit;
119 huftree.fixed = 1;
120 for ( i = 0; i < fi; i++ )
121 huf_incfreq( &huftree, freq[ i ] & 0xFF );
122
123 huf_build( &huftree );
124 for ( i = 0; i < fi; i++ )
125 {
126 huf_outbits( &huftree, freq[ i ] & 0xFF );
127 //printf("%i:%i ", i, freq[i] & 0xFF );
128
129 switch ( freq[i] & 0xFF )
130 {
131 case PRET_ZERO2:
132 huf_packnum( &huftree, freq[i] >> 24, 2 );
133 break;
134 case PRET_ZERO4:
135 huf_packnum( &huftree, freq[i] >> 24, 4 );
136 break;
137 // case PRET_ZERO5:
138 // huf_packnum( &huftree, freq[i] >> 24, 5 );
139 // break;
140 case PRET_ZERO6:
141 huf_packnum( &huftree, freq[i] >> 24, 6 );
142 break;
143 case PRET_BIG:
144 huf_packnum( &huftree, freq[i] >> 24, bits );
145 break;
146 }
147 }
148 huf->ptr = huftree.ptr;
149 huf->bit = huftree.bit;
150
151 huf_destroy( &huftree );
152 }
153 /* Делаем предыдущую глубину из текущей, если текущая и
154 // предыдущая > PRET_MAXCODE
155 if ( i && freq[i] <= PRET_MAXCODE && freq[ i - 1 ] <= PRET_MAXCODE )
156 {
157 // freq[i] = ( freq[i] + PRET_MAXCODE - freq[ i - 1 ] ) & PRET_MAXCODE;
158 }*/
159 // if ( !huf->fixed ) printf("\nLen=%i\n", huf->ptr - st );
160 }
161
162 //--------------------------------------------------------------------------
163
164 void STDCALL huf_build( pshuf huf )
165 {
166 pshufleaf cur = huf->tree;
167 pshufleaf left, end;
168 pshufleaf right;
169 dword i, count = huf->numcode;
170
171 end = huf->tree + huf->allcode - 1;
172 while ( cur < end )
173 {
174 cur->up = NULL;
175 cur++;
176 }
177
178 while ( 1 )
179 {
180 // ищем две минимальных частоты
181 cur = ( pshufleaf )huf->tree;
182 left = NULL;
183 right = NULL;
184
185 i = 0;
186 while ( i++ < count )
187 {
188 if ( !cur->up && cur->freq )
189 // if ( cur->freq )
190 {
191 if ( !left || cur->freq < left->freq )
192 {
193 if ( left && !right )
194 right = left;
195 left = cur;
196 }
197 else
198 if ( !right || cur->freq < right->freq )
199 right = cur;
200 }
201 cur++;
202 }
203 if ( !right ) break;
204 // на основе этих частот составляем третью
205 cur = huf->tree + count++;
206 cur->freq = left->freq + right->freq;
207 cur->left = left;
208 cur->right = right;
209 left->up = cur;
210 // left->freq = 0;
211
212 right->up = cur;
213 // right->freq = 0;
214
215 cur->up = NULL;
216 }
217 if ( count == huf->numcode )
218 { // У нас только один элемент из алфавита
219 cur = huf->tree + count++;
220 cur->freq = left->freq;
221 cur->left = left;
222 cur->right = NULL;
223 left->up = cur;
224 cur->up = NULL;
225 }
226 huf->root = huf->tree + count - 1;
227 huf->min = 0xFF;
228 huf->max = 1;
229
230 for (i = 0; i < huf->allcode; i++ )
231 {
232 cur = huf->tree + i;
233 cur->freq = i < huf->numcode ? huf_bits( huf, i ) : 0 ;
234 if ( cur->freq && cur->freq < huf->min )
235 huf->min = cur->freq;
236 if ( cur->freq > huf->max )
237 huf->max = cur->freq;
238 }
239 huf_entree( huf );
240 huf_normilize( huf );
241 }
242
243 //--------------------------------------------------------------------------
244
245 void STACKAPI huf_incfreq( pshuf huf, dword item )
246 {
247 ( huf->tree + item )->freq++;
248 }
249
250 //--------------------------------------------------------------------------
251
252 void STACKAPI huf_outbits( pshuf huf, dword item )
253 {
254 register pshufleaf cur = huf->tree + item;
255 register pbyte ps = huf->stack;
256
257 if ( !cur->up ) return;
258
259 do {
260 *ps++ = ( cur->up->right == cur );
261 cur = cur->up;
262 } while ( cur != huf->root );
263
264 do {
265 *huf->ptr = ( *huf->ptr << 1 ) | *--ps;
266 if ( !( huf->bit = ( huf->bit + 1 ) & 7 ))
267 huf->ptr++;
268 } while ( ps > huf->stack );
269 }
270
271 //--------------------------------------------------------------------------
272
273 void STACKAPI huf_packnum( pshuf huf, dword val, dword bits )
274 {
275 // if ( val >= ( dword )(1 << bits )) printf("Ooops %i %i\n", val, bits );
276 while ( bits-- )
277 {
278 *huf->ptr = ( *huf->ptr << 1 ) | ( byte )( val & 1 );
279
280 if ( !( huf->bit = ( huf->bit + 1 ) & 7 ))
281 huf->ptr++;
282
283 val >>= 1;
284 }
285 }
286
287 //--------------------------------------------------------------------------
288
289