EnglishРусский  

   ..

   huffman.c

   huffman.h

Реклама

Инсталлятор CreateInstall
Бесплатные и коммерческие инсталляторы

  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 
Редактировать