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