EnglishРусский  

   ..

   dehuffman.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 /*#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 dword  STACKAPI huf_unpacknum( pshuf huf, dword bits )
 24 {
 25    dword  i = bits;
 26    dword  result = 0;
 27 
 28    while ( i )
 29    {
 30       result |= (( *huf->ptr >> huf->bit ) & 1 ) << ( bits - i-- );
 31       if ( !huf->bit )
 32       {
 33          huf->bit = 7;
 34          huf->ptr++;
 35       }
 36       else huf->bit--;
 37    }
 38 
 39    return result;
 40 }
 41 
 42 //--------------------------------------------------------------------------
 43 
 44 void  STDCALL huf_detree( pshuf huf )
 45 {
 46    dword  bits;
 47    dword  i;
 48 //   dword  freq[ 2048 ];
 49    pdword freq = huf->freq;
 50 
 51    bits = huf_unpacknum( huf, huf->numcode < 32 ? 2 : 3  ) + 1;
 52 
 53    huf->min = huf_unpacknum( huf, bits );
 54    huf->max = huf->min + huf_unpacknum( huf, bits );
 55    
 56 //   printf( "Bits = %i Min=%i Max=%i\n", bits, huf->min, huf->max );
 57    if ( huf->fixed )
 58    {
 59       for ( i = 0; i < huf->numcode; i++ )
 60       {
 61          freq[ i ] = huf_unpacknum( huf, bits );
 62 //    printf("freq=%i\n", huf->tree[i].freq );
 63       }
 64    }
 65    else
 66    {
 67       shuf   huftree;
 68       dword  code;
 69       
 70       huf_new( &huftree, PRET_ALPHABET );
 71       huftree.ptr = huf->ptr;
 72       huftree.bit = huf->bit;
 73       huftree.fixed = 1;
 74 
 75       huf_detree( &huftree );
 76       i = 0;
 77       while ( i < huf->numcode )
 78       {
 79          freq[i] = huf_inbits( &huftree );
 80 //         printf("%i:%i ", i, freq[i] );
 81          if ( freq[i] > PRET_MAXCODE )
 82          {
 83             switch ( freq[i] )
 84             {
 85                case PRET_ZERO2:
 86                   code = huf_unpacknum( &huftree, 2 ) + PRET_OFF1;
 87                   break;
 88                case PRET_ZERO4:
 89                   code = huf_unpacknum( &huftree, 4 ) + PRET_OFF2;
 90                   break;
 91 /*               case PRET_ZERO5:
 92                   code = huf_unpacknum( &huftree, 5 ) + 16;
 93                   break;*/
 94                case PRET_ZERO6:
 95                   code = huf_unpacknum( &huftree, 6 ) + PRET_OFF3;
 96                   break;
 97                case PRET_BIG:
 98                   code = huf_unpacknum( &huftree, bits );
 99                   break;
100             }
101             if ( freq[i] == PRET_BIG ) freq[ i ] = code;
102             else
103             {
104                freq[ i ] = 0;
105                while ( --code )
106                {
107                   freq[ ++i ] = 0;
108                }
109             }
110          }
111          i++;
112       }
113       
114       huf->ptr = huftree.ptr;
115       huf->bit = huftree.bit;
116 
117       huf_destroy( &huftree );
118       // Переводим длины из специального представления
119 /*      for ( i = 0; i < huf->numcode; i++ )
120       {
121          if ( !freq[i] )
122          {
123             k = i + 1;  
124             while ( k < huf->numcode && !freq[k] &&
125                   ( k - i < PRET_MAXZERO - 1 ))
126                k++;
127             if ( k > 2 )
128             {
129                i += k;
130                k -= 3;
131                if ( k < 4 )
132                   freq[ fi++ ] = ( k << 24 ) | PRET_ZERO2;
133                else
134                   if ( k < 8 )
135                      freq[ fi++ ] = ( k << 24 ) | PRET_ZERO3;
136                   else
137                      freq[ fi++ ] = ( k << 24 ) | PRET_ZERO5;
138                continue;
139             }
140          }
141          if ( freq[i] > PRET_MAXCODE )
142          {
143             freq[ fi++ ] = ( freq[i] << 24 ) | PRET_BIG;
144          }
145          else
146             freq[ fi++ ] = freq[i];
147       }*/
148    }
149    for ( i = 0; i < huf->numcode; i++ )
150    {
151       dword k;
152       // Поднимаем на минимум
153       k = huf->prevlen[ i ];
154       huf->prevlen[i] = 0;
155          if ( freq[i] <= PRET_MAXCODE )
156          {
157 //            huf->prevlen[i] = freq[ i ];
158             freq[i] = ( freq[i] + k ) % ( PRET_MAXCODE + 1 );
159             huf->prevlen[i] = ( byte )freq[ i ];
160 //            if (!huf->fixed )
161 //               printf("%i=%i ", i, huf->prevlen[i] );
162          }
163       if ( freq[i] )
164       {
165 /*         if ( freq[i] <= PRET_MAXCODE )
166          {
167             huf->prevlen[i] = freq[ i ];
168 //            freq[i] = ( freq[i] + k ) & PRET_MAXCODE;
169 //            huf->prevlen[i] = freq[ i ];
170             printf("%i=%i ", i, freq[i] );
171          }*/
172          freq[ i ] += huf->min - 1;
173       }
174 //      if ( freq[ i ] )
175 //         freq[ i ] += huf->min - 1;
176    }
177       /* Делаем предыдущую глубину из текущей, если текущая и 
178       // предыдущая > PRET_MAXCODE
179       if ( i && freq[i] <= PRET_MAXCODE && freq[ i - 1 ] <= PRET_MAXCODE )
180       {
181  //        freq[i] = ( freq[i] + 15 + freq[ i - 1 ] ) & PRET_MAXCODE ;
182       }*/
183 
184    for ( i = 0; i < huf->numcode; i++ )
185    {
186       huf->tree[i].freq = freq[i];
187    }
188    huf_normilize( huf );
189 }
190 
191 //--------------------------------------------------------------------------
192 
193 dword  STACKAPI huf_inbits( pshuf huf )
194 {
195    pshufleaf  cur = huf->root;
196 
197    do {
198       cur = (( *huf->ptr >> huf->bit ) & 1) ? cur->right : cur->left;
199       if ( !huf->bit )
200       {
201          huf->bit = 7;
202          huf->ptr++;
203       }
204       else huf->bit--;
205    } while ( cur->left );
206 
207    return cur - huf->tree;
208 }
209 
210 //--------------------------------------------------------------------------
211 
Редактировать