EnglishРусский  

   ..

   enhuffman.c

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