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 /*#ifdef LAUNCHER
16 #include "K:\Gentee\Gentee Language\Opti Launcher\memory.h"
17 #else
18 #include "K:\Gentee\Gentee Language\VM Lib\memory.h"
19 #endif
20 */
21 //--------------------------------------------------------------------------
22
23 pshuf STDCALL huf_new( pshuf huf, dword alphabet )
24 {
25 huf->allcode = ( alphabet + ( alphabet & 0x1 )) << 1;
26 huf->stack = mem_allocz( 1024 );
27 huf->prevlen = mem_allocz( 2048 );
28 huf->tree = mem_allocz( huf->allcode * sizeof( shufleaf ));
29 huf->numcode = alphabet;
30 huf->root = NULL;
31 huf->bit = 0;
32 huf->fixed = 0;
33 huf->normalize = ( pdword )mem_alloc( 2048 * sizeof( dword ) );
34 huf->freq = ( pdword )mem_alloc( 2048 * sizeof( dword ) );
35 // huf->pretree = 0;
36 // huf->maxfreq = 512;//1000;
37 return huf;
38 }
39
40 //--------------------------------------------------------------------------
41
42 void STDCALL huf_destroy( pshuf huf )
43 {
44 mem_free( huf->tree );
45 mem_free( huf->stack );
46 mem_free( huf->prevlen );
47 mem_free( huf->normalize );
48 mem_free( huf->freq );
49 }
50
51 //--------------------------------------------------------------------------
52
53 void STDCALL huf_normilize( pshuf huf )
54 {
55 pshufleaf cur, node;
56 dword i, codes, count;
57 // pshufleaf prevstk[ 2048 ];
58 pdword prev = huf->normalize;
59
60 for ( i = 0; i < 2048; i++ )
61 prev[ i ] = 0;//( dword )NULL;
62
63 codes = huf->numcode;
64 while ( 1 )
65 {
66 cur = huf->tree;
67 count = 0;
68 while ( cur < huf->tree + codes )
69 {
70 if ( cur->freq )
71 {
72 count++;
73 // Есть или нет с таким же количеством битов
74 if ( prev[ cur->freq ] )
75 {
76 // Образуем новый элемент
77 node = huf->tree + codes++;
78 node->freq = cur->freq - 1;
79 node->left = ( pshufleaf )prev[ cur->freq ];
80 node->right = cur;
81 (( pshufleaf)prev[ cur->freq ])->up = node;
82 prev[ cur->freq ] = 0;//NULL;
83 cur->up = node;
84 if ( !node->freq ) break;
85 }
86 else
87 {
88 prev[ cur->freq ] = ( dword )cur;
89 }
90 cur->freq = 0;
91 }
92 cur++;
93 }
94 if ( count == 1 )
95 {
96 node = huf->tree + codes;
97 node->freq = 0;
98 node->left = ( pshufleaf )prev[ 1 ];
99 node->right = NULL;
100 (( pshufleaf)prev[ 1 ])->up = node;
101 }
102 if ( !node->freq ) break;
103 }
104 huf->root = node;
105 huf->root->up = NULL;
106 }
107
108 //--------------------------------------------------------------------------
109 // Упаковываем дерево - возвращаем количество бит.
110 // Упакованные данные находятся в huf->inout 1 байт = 1 бит
111 /*dword STDCALL huf_entree( pshuf huf )
112 {
113 dword i;
114
115 huf->size = 0;
116 for ( i = 0; i < huf->numcode; i++ )
117 {
118 // if ( !i )
119 // printf("Freq = %i\n", huf->tree[ i ].freq );
120 huf_pack( huf, huf->tree[ i ].freq, 8 );
121 // huf->inout[ i ] = huf->tree[ i ].freq;
122 }
123 // huf->size = huf->numcode;
124
125 dword length[ 1024 ];
126 dword min, max, i = 0, k;
127 pshufleaf cur = huf->tree;
128 pshufleaf end = huf->tree + huf->numcode;
129 shuf huftree;
130
131 length[ i ] = min = max = cur->freq;
132 cur++;
133 while ( cur < end )
134 {
135 if ( cur->freq )
136 {
137 if ( !min || cur->freq < min ) min = cur->freq;
138 else
139 if ( cur->freq > max ) max = cur->freq;
140 }
141 if ( ( length[ i ] & 0xFFFF ) == cur->freq && ( length[i] >> 24 ) < 77 )
142 length[ i ] += 0x01000000;
143 else
144 length[ ++i ] = cur->freq;
145 cur++;
146 }
147 if ( !huf->pretree )
148 {
149 huf_new( &huftree, 20 ); // 0 - 15 + 16 17 18 19
150 huftree.pretree = 1;
151
152 for ( k = 0; k <= i; k++ )
153 {
154 dword code = length[ k ] & 0xFFFF;
155 dword repeat = length[ k ] >> 24;
156
157 if ( code > 15 )
158 {
159 huf_incfreq( &huftree, code );
160 }
161 else
162 huf_incfreq( &huftree, code );
163 if ( repeat )
164 {
165 if ( repeat < 3 )
166 {
167 if ( repeat == 2 )
168 huf_incfreq( &huftree, code );
169 huf_incfreq( &huftree, code );
170 // huf_incfreq( &huftree, code ? code - min + 1 : 0 );
171 // huf_incfreq( &huftree, code ? code - min + 1 : 0 );
172 }
173 else
174 if ( repeat < 7 )
175 {
176 // huf_incfreq( &huftree, huftree.numcode - 3 );
177 huf_incfreq( &huftree, huftree.numcode - 3 );
178 }
179 else
180 if ( repeat < 15 )
181 {
182 huf_incfreq( &huftree, huftree.numcode - 2 );
183 }
184 else
185 {
186 huf_incfreq( &huftree, huftree.numcode - 1 );
187 }
188 }
189 }
190 huf_build( &huftree );
191 mem_copy( huf->inout, huftree.inout, huftree.size );
192 huf->size = huftree.size;
193
194 // huf->stree = huftree.stree + more;
195 for ( i = 0; i < huftree.numcode; i++ )
196 {
197 // huf->stree += huf_bits( &huftree, i );
198 }
199 // printf("%x ", length[ i ]);
200 huf_destroy( &huftree );
201 printf("SIZE = %i\n", huf->size );
202 }
203 else
204 {
205 dword bits;//, shift = 0;
206
207 huf->size = 0;
208 // shift = min - 1;
209 // if ( shift > 3 ) shift = 3;
210 // max -= shift;
211 // Упаковываем количество бит на элемент
212 if ( max < 4 ) bits = 2;
213 else bits = max < 8 ? 3 : 4;
214 huf_pack( huf, bits - 1, 2 );
215 // huf_pack( huf, shift, 2 );
216 // printf("min=%i shift=%i\n", min, shift);
217 cur = huf->tree;
218 while ( cur < end )
219 {
220 huf_pack( huf, cur->freq, bits );
221 printf("%x ", cur->freq );
222 cur++;
223 }
224 // huf->stree = 4; // min
225 // huf->stree += 4; // count ( numcode - 4 )
226 // huf->stree += huf->numcode * 4; // Длины pre-codes
227 // for ( k = 0; i < huftree.numcode; i++ )
228 // {
229 // printf("%x ", length[ k ]);
230 // huf->stree += huf_bits( &huftree, i );
231 // }
232 // for ( k = 0; k <= i; k++ )
233 // printf("%x ", length[ k ]);
234 // printf("MaxLEN=%i\n", max );
235 }
236 // huf->inout[ out++ ] =
237 // printf("Len=%i min=%i max=%i\n", i, min, max );
238 // huf->stree = i;
239 // for ( i = 0; i <= huf->stree; i++ )
240 // printf("%x ", length[ i ]);
241 // huf_init( huftree, huf->)
242 // huf->stree = 0;
243 return huf->size;
244 }*/
245
246 //--------------------------------------------------------------------------
247
248 /*
249 void OSAPI loc_hufleafchange( pshufleaf one, pshufleaf two, bool rec )
250 {
251 // Следует иметьь ввиду что частота one не может быть меньше частоты two
252 pshufleaf upone = one->up;
253 // onepair - пара к one
254 pshufleaf onepair = ( upone->left == one ? upone->right : upone->left );
255 // maxchild - ребенок с большей частотой у two
256 pshufleaf maxchild = ( two->left ? ( two->left->freq >
257 two->right->freq ? two->left : two->right ) : NULL );
258
259 if ( upone->left == one )
260 upone->left = two;
261 else
262 upone->right = two;
263 if ( two->up->left == two )
264 two->up->left = one;
265 else
266 two->up->right = one;
267 one->up = two->up;
268 two->up = upone;
269
270 // Сейчас возможна ситуация что дети pair будут иметь больше
271 // вес чем старая пара onepair к cur.
272 if ( rec && maxchild && onepair->freq < maxchild->freq )
273 {
274 // достаточно изменить частоту у two
275 two->freq -= maxchild->freq - onepair->freq;
276 // меняем их местами
277 loc_hufleafchange( maxchild, onepair, 0 );
278 }
279 // ни один ребенок onepair не может быть больше two
280 }
281
282 //--------------------------------------------------------------------------
283
284 void OSAPI huf_init( pshuf huf )
285 {
286 word numcode = ( word )PARA( huf );
287 pshufleaf hufcur;
288 word i = 0;
289
290 huf->tree = obj_create( huf, &arr_info, ( pvoid )
291 LONGMAKE( numcode<<1, sizeof( shufleaf )) );
292 huf->numcode = numcode;
293 huf->maxfreq = 512;//1000;
294
295 // Инициализируем дерево частотами и значениями алфавита
296 hufcur = ( pshufleaf )huf->tree->buf.buf;
297 while ( i < huf->numcode )
298 {
299 mem_zero( hufcur, sizeof( shufleaf ));
300 hufcur->code = i++;
301 hufcur->freq = i;
302 hufcur++;
303 }
304
305 CMD( huf, HufTreeBuild );
306 }
307
308 //--------------------------------------------------------------------------
309
310 void OSAPI huf_treebuild( pshuf huf )
311 {
312 pshufleaf cur = ( pshufleaf )huf->tree->buf.buf;
313 pshufleaf left;
314 pshufleaf right;
315 long i = 0;
316 long full = huf->numcode + huf->numcode - 1;
317
318 huf->allcode = huf->numcode;
319 while ( i++ < full )
320 {
321 cur->up = NULL;
322 cur++;
323 }
324
325 while ( huf->allcode < full )
326 {
327 // ищем две минимальных частоты
328 cur = ( pshufleaf )huf->tree->buf.buf;
329 left = NULL;
330 right = NULL;
331
332 i = 0;
333 while ( i++ < huf->allcode )
334 {
335 if ( !cur->up )
336 {
337 if ( !left || cur->freq < left->freq )
338 {
339 if ( left && !right )
340 right = left;
341 left = cur;
342 }
343 else
344 if ( !right || cur->freq < right->freq )
345 right = cur;
346 }
347 cur++;
348 }
349 // на основе этих частот составляем третью
350 cur = CMDA( huf->tree, IDataPtr, huf->allcode++ );
351 cur->code = huf->allcode - 1;
352 cur->freq = left->freq + right->freq;
353 cur->left = left;
354 cur->right = right;
355 left->up = cur;
356 right->up = cur;
357 }
358 cur->up = NULL;
359 huf->root = cur;
360 }
361
362 //--------------------------------------------------------------------------
363
364 void OSAPI huf_update( pshuf huf, word code )
365 {
366 pshufleaf cur = CMDA( huf->tree, IDataPtr, code );
367 pshufleaf upcur; // хозяин элемента
368 pshufleaf pair; // пара хозяина
369 long i;
370
371 while ( cur )
372 {
373 upcur = cur->up;
374
375 // Перемещение возможно тогда когда есть верхние элементы
376 if ( upcur && upcur->up )
377 {
378 // Сравнивать надо с элементом выше на один уровень
379 // Этот элемент является парой хозяина
380 pair = ( upcur->up->left == upcur ? upcur->up->right :
381 upcur->up->left );
382
383 // Менять можно только в том случае если частоты сейчас равны,
384 // а при увеличении у cur будет на 1 больше
385 if ( cur->freq >= pair->freq )
386 loc_hufleafchange( cur, pair, TRUE );
387 }
388 // Меняем частоту у cur
389 cur->freq++;
390 cur = cur->up;
391 }
392 if ( huf->root->freq >= huf->maxfreq )
393 {
394 cur = ( pshufleaf )huf->tree->buf.buf;
395 for ( i = 0; i < huf->allcode; i++ )
396 cur++->freq >>= 1;
397 }
398 }
399
400 //--------------------------------------------------------------------------
401
402 retend OSAPI huf_func( pshuf huf )
403 {
404 switch ( PARCMD( huf ))
405 {
406 case ObjInit:
407 huf_init( huf );
408 break;
409
410 case HufTreeBuild:
411 huf_treebuild( huf );
412 break;
413
414 case HufUpdate:
415 huf_update( huf, ( word )PARA( huf ));
416 goto retobj;
417
418 default:
419 return CONTINUE;
420 }
421 return BREAK;
422
423 retobj:
424 return BREAKOBJ;
425 }
426
427 //--------------------------------------------------------------------------
428
429 sobjinfo huf_info = { sizeof( shuf ), ty_Huf, &obj_info, huf_func,
430 POSTPAR_NONE };
431 */
432 //--------------------------------------------------------------------------
433