/[freetype]/freetype2/src/lzw/ftzopen.c
ViewVC logotype

Contents of /freetype2/src/lzw/ftzopen.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.1 - (show annotations) (download)
Thu Oct 20 15:33:34 2005 UTC (18 years, 6 months ago) by freetype
Branch: MAIN
File MIME type: text/plain
  * src/base/ftdbgmem.c: fixes to better account for memory reallocations

  * src/lzw/ftlzw2.c, src/lzw/ftzopen.h, src/lzw/ftzopen.c, src/lzw/rules.mk:
    first version of LZW loader re-implementation. Apparently, saves about
    260 KB of heap memory when loading tir24.pcf.Z

1 #include "ftzopen.h"
2 #include FT_INTERNAL_MEMORY_H
3 #include FT_INTERNAL_STREAM_H
4 #include FT_INTERNAL_DEBUG_H
5
6 /* refill input buffer, return 0 on success, or -1 if eof
7 */
8 static int
9 ft_lzwstate_refill( FT_LzwState state )
10 {
11 int result = -1;
12
13 if ( !state->in_eof )
14 {
15 FT_ULong count = FT_Stream_TryRead( state->source,
16 state->in_buff,
17 sizeof( state->in_buff ) );
18
19 state->in_cursor = state->in_buff;
20 state->in_limit = state->in_buff + count;
21 state->in_eof = FT_BOOL( count < sizeof( state->in_buff ) );
22
23 if ( count > 0 )
24 result = 0;
25 }
26 return result;
27 }
28
29
30 /* return new code of 'num_bits', or -1 if eof
31 */
32 static FT_Int32
33 ft_lzwstate_get_code( FT_LzwState state,
34 FT_UInt num_bits )
35 {
36 FT_Int32 result = -1;
37 FT_UInt32 pad = state->pad;
38 FT_UInt pad_bits = state->pad_bits;
39
40 while ( num_bits > pad_bits )
41 {
42 if ( state->in_cursor >= state->in_limit &&
43 ft_lzwstate_refill( state ) < 0 )
44 goto Exit;
45
46 pad |= (FT_UInt32)(*state->in_cursor++) << pad_bits;
47 pad_bits += 8;
48 }
49
50 result = (FT_Int32)( pad & LZW_MASK(num_bits) );
51 state->pad_bits = pad_bits - num_bits;
52 state->pad = pad >> num_bits;
53
54 Exit:
55 return result;
56 }
57
58
59 /* grow the character stack
60 */
61 static int
62 ft_lzwstate_stack_grow( FT_LzwState state )
63 {
64 if ( state->stack_top >= state->stack_size )
65 {
66 FT_Memory memory = state->memory;
67 FT_Error error;
68 FT_UInt old_size = state->stack_size;
69 FT_UInt new_size = old_size;
70
71 new_size = new_size + (new_size >> 1) + 4;
72
73 if ( state->stack == state->stack_0 )
74 {
75 state->stack = NULL;
76 old_size = 0;
77 }
78
79 if ( FT_RENEW_ARRAY( state->stack, old_size, new_size ) )
80 return -1;
81
82 state->stack_size = new_size;
83 }
84 return 0;
85 }
86
87
88 /* grow the prefix/suffix arrays
89 */
90 static int
91 ft_lzwstate_prefix_grow( FT_LzwState state )
92 {
93 FT_UInt old_size = state->prefix_size;
94 FT_UInt new_size = old_size;
95 FT_Memory memory = state->memory;
96 FT_Error error;
97
98 if ( new_size == 0 ) /* first allocation -> 9 bits */
99 new_size = 512;
100 else
101 new_size += (new_size >> 2); /* don't grow too fast */
102
103 /* note that the 'suffix' array is located in the same memory block
104 * pointed to by 'prefix'
105 *
106 * I know that sizeof(FT_Byte) == 1 by definition, but it's clearer
107 * to write it literally
108 */
109 if ( FT_REALLOC( state->prefix,
110 old_size*(sizeof(FT_UShort)+sizeof(FT_Byte)),
111 new_size*(sizeof(FT_UShort)+sizeof(FT_Byte)) ) )
112 return -1;
113
114 /* now adjust 'suffix' and move the data accordingly */
115 state->suffix = (FT_Byte*)(state->prefix + new_size);
116
117 FT_MEM_MOVE( state->suffix,
118 state->prefix + old_size,
119 old_size * sizeof(FT_Byte) );
120
121 state->prefix_size = new_size;
122 return 0;
123 }
124
125
126 FT_LOCAL_DEF( void )
127 ft_lzwstate_reset( FT_LzwState state )
128 {
129 state->in_cursor = state->in_buff;
130 state->in_limit = state->in_buff;
131 state->in_eof = 0;
132 state->pad_bits = 0;
133 state->pad = 0;
134
135 state->stack_top = 0;
136 state->num_bits = LZW_INIT_BITS;
137 state->phase = FT_LZW_PHASE_START;
138 }
139
140
141 FT_LOCAL_DEF( void )
142 ft_lzwstate_init( FT_LzwState state,
143 FT_Stream source )
144 {
145 FT_ZERO( state );
146
147 state->source = source;
148 state->memory = source->memory;
149
150 state->prefix = NULL;
151 state->suffix = NULL;
152 state->prefix_size = 0;
153
154 state->stack = state->stack_0;
155 state->stack_size = sizeof(state->stack_0);
156
157 ft_lzwstate_reset( state );
158 }
159
160
161 FT_LOCAL_DEF( void )
162 ft_lzwstate_done( FT_LzwState state )
163 {
164 FT_Memory memory = state->memory;
165
166 ft_lzwstate_reset( state );
167
168 if ( state->stack != state->stack_0 )
169 FT_FREE( state->stack );
170
171 FT_FREE( state->prefix );
172 state->suffix = NULL;
173
174 FT_ZERO( state );
175 }
176
177
178 #define FTLZW_STACK_PUSH(c) \
179 FT_BEGIN_STMNT \
180 if ( state->stack_top >= state->stack_size && \
181 ft_lzwstate_stack_grow( state ) < 0 ) \
182 goto Eof; \
183 \
184 state->stack[ state->stack_top++ ] = (FT_Byte)(c); \
185 FT_END_STMNT
186
187
188
189 FT_LOCAL_DEF( FT_ULong )
190 ft_lzwstate_io( FT_LzwState state,
191 FT_Byte* buffer,
192 FT_ULong out_size )
193 {
194 FT_ULong result = 0;
195
196 FT_UInt num_bits = state->num_bits;
197 FT_UInt free_ent = state->free_ent;
198 FT_UInt old_char = state->old_char;
199 FT_UInt old_code = state->old_code;
200 FT_UInt in_code = state->in_code;
201
202 if ( out_size == 0 )
203 goto Exit;
204
205 switch ( state->phase )
206 {
207 case FT_LZW_PHASE_START:
208 {
209 FT_Byte max_bits;
210 FT_Int32 c;
211
212 /* skip magic bytes, and read max_bits + block_flag */
213 if ( FT_Stream_Seek( state->source, 2 ) != 0 ||
214 FT_Stream_TryRead( state->source, &max_bits, 1 ) != 1 )
215 goto Eof;
216
217 state->max_bits = max_bits & LZW_BIT_MASK;
218 state->block_mode = max_bits & LZW_BLOCK_MASK;
219 state->max_free = (FT_UInt)((1UL << state->max_bits) - 256);
220
221 if ( state->max_bits > LZW_MAX_BITS )
222 goto Eof;
223
224 num_bits = LZW_INIT_BITS;
225 free_ent = (state->block_mode ? LZW_FIRST : LZW_CLEAR) - 256;
226 in_code = 0;
227
228 state->free_bits = num_bits < state->max_bits
229 ? (FT_UInt)((1UL << num_bits) - 256)
230 : state->max_free+1;
231
232 c = ft_lzwstate_get_code( state, num_bits );
233 if ( c < 0 )
234 goto Eof;
235
236 old_code = old_char = (FT_UInt)c;
237
238 if ( buffer )
239 buffer[result] = (FT_Byte)old_char;
240
241 if ( ++result >= out_size )
242 goto Exit;
243
244 state->phase = FT_LZW_PHASE_CODE;
245 }
246 /* fall-through */
247
248 case FT_LZW_PHASE_CODE:
249 {
250 FT_Int32 c;
251 FT_UInt code;
252
253 NextCode:
254 c = ft_lzwstate_get_code( state, num_bits );
255 if ( c < 0 ) goto Eof;
256
257 code = (FT_UInt)c;
258
259 if ( code == LZW_CLEAR && state->block_mode )
260 {
261 free_ent = (LZW_FIRST-1)-256; /* why not LZW_FIRST-256 ? */
262 num_bits = LZW_INIT_BITS;
263
264 state->free_bits = num_bits < state->max_bits
265 ? (FT_UInt)((1UL << num_bits) - 256)
266 : state->max_free+1;
267
268 c = ft_lzwstate_get_code( state, num_bits );
269 if ( c < 0 ) goto Eof;
270
271 code = (FT_UInt)c;
272 }
273
274 in_code = code; /* save code for later */
275
276 if ( code >= 256U )
277 {
278 /* special case for KwKwKwK */
279 if ( code-256U >= free_ent )
280 {
281 FTLZW_STACK_PUSH( old_char );
282 code = old_code;
283 }
284
285 while ( code >= 256U )
286 {
287 FTLZW_STACK_PUSH( state->suffix[code-256] );
288 code = state->prefix[code-256];
289 }
290 }
291
292 old_char = code;
293 FTLZW_STACK_PUSH(old_char);
294
295 state->phase = FT_LZW_PHASE_STACK;
296 }
297 /* fall-through */
298
299 case FT_LZW_PHASE_STACK:
300 {
301 while ( state->stack_top > 0 )
302 {
303 --state->stack_top;
304
305 if ( buffer )
306 buffer[result] = state->stack[state->stack_top];
307
308 if ( ++result == out_size )
309 goto Exit;
310 }
311
312 /* now create new entry */
313 if ( free_ent < state->max_free )
314 {
315 if ( free_ent >= state->prefix_size &&
316 ft_lzwstate_prefix_grow( state ) < 0 )
317 goto Eof;
318
319 FT_ASSERT( free_ent < state->prefix_size );
320
321 state->prefix[free_ent] = (FT_UShort) old_code;
322 state->suffix[free_ent] = (FT_Byte) old_char;
323
324 if ( ++free_ent == state->free_bits )
325 {
326 num_bits++;
327
328 state->free_bits = num_bits < state->max_bits
329 ? (FT_UInt)((1UL << num_bits)-256)
330 : state->max_free+1;
331 }
332 }
333
334 old_code = in_code;
335
336 state->phase = FT_LZW_PHASE_CODE;
337 goto NextCode;
338 }
339
340 default: /* state == EOF */
341 ;
342 }
343 Exit:
344 state->num_bits = num_bits;
345 state->free_ent = free_ent;
346 state->old_code = old_code;
347 state->old_char = old_char;
348 state->in_code = in_code;
349
350 return result;
351
352 Eof:
353 state->phase = FT_LZW_PHASE_EOF;
354 goto Exit;
355 }

savannah-hackers-public@gnu.org
ViewVC Help
Powered by ViewVC 1.1.26