1 /***************************************************************************/ 2 /* */ 3 /* ftzopen.c */ 4 /* */ 5 /* FreeType support for .Z compressed files. */ 6 /* */ 7 /* This optional component relies on NetBSD's zopen(). It should mainly */ 8 /* be used to parse compressed PCF fonts, as found with many X11 server */ 9 /* distributions. */ 10 /* */ 11 /* Copyright 2005-2015 by */ 12 /* David Turner. */ 13 /* */ 14 /* This file is part of the FreeType project, and may only be used, */ 15 /* modified, and distributed under the terms of the FreeType project */ 16 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ 17 /* this file you indicate that you have read the license and */ 18 /* understand and accept it fully. */ 19 /* */ 20 /***************************************************************************/ 21 22 #include "ftzopen.h" 23 #include FT_INTERNAL_MEMORY_H 24 #include FT_INTERNAL_STREAM_H 25 #include FT_INTERNAL_DEBUG_H 26 27 28 static int 29 ft_lzwstate_refill( FT_LzwState state ) 30 { 31 FT_ULong count; 32 33 34 if ( state->in_eof ) 35 return -1; 36 37 count = FT_Stream_TryRead( state->source, 38 state->buf_tab, 39 state->num_bits ); /* WHY? */ 40 41 state->buf_size = (FT_UInt)count; 42 state->buf_total += count; 43 state->in_eof = FT_BOOL( count < state->num_bits ); 44 state->buf_offset = 0; 45 state->buf_size = ( state->buf_size << 3 ) - ( state->num_bits - 1 ); 46 47 if ( count == 0 ) /* end of file */ 48 return -1; 49 50 return 0; 51 } 52 53 54 static FT_Int32 55 ft_lzwstate_get_code( FT_LzwState state ) 56 { 57 FT_UInt num_bits = state->num_bits; 58 FT_UInt offset = state->buf_offset; 59 FT_Byte* p; 60 FT_Int result; 61 62 63 if ( state->buf_clear || 64 offset >= state->buf_size || 65 state->free_ent >= state->free_bits ) 66 { 67 if ( state->free_ent >= state->free_bits ) 68 { 69 state->num_bits = ++num_bits; 70 state->free_bits = state->num_bits < state->max_bits 71 ? (FT_UInt)( ( 1UL << num_bits ) - 256 ) 72 : state->max_free + 1; 73 } 74 75 if ( state->buf_clear ) 76 { 77 state->num_bits = num_bits = LZW_INIT_BITS; 78 state->free_bits = (FT_UInt)( ( 1UL << num_bits ) - 256 ); 79 state->buf_clear = 0; 80 } 81 82 if ( ft_lzwstate_refill( state ) < 0 ) 83 return -1; 84 85 offset = 0; 86 } 87 88 state->buf_offset = offset + num_bits; 89 90 p = &state->buf_tab[offset >> 3]; 91 offset &= 7; 92 result = *p++ >> offset; 93 offset = 8 - offset; 94 num_bits -= offset; 95 96 if ( num_bits >= 8 ) 97 { 98 result |= *p++ << offset; 99 offset += 8; 100 num_bits -= 8; 101 } 102 if ( num_bits > 0 ) 103 result |= ( *p & LZW_MASK( num_bits ) ) << offset; 104 105 return result; 106 } 107 108 109 /* grow the character stack */ 110 static int 111 ft_lzwstate_stack_grow( FT_LzwState state ) 112 { 113 if ( state->stack_top >= state->stack_size ) 114 { 115 FT_Memory memory = state->memory; 116 FT_Error error; 117 FT_Offset old_size = state->stack_size; 118 FT_Offset new_size = old_size; 119 120 new_size = new_size + ( new_size >> 1 ) + 4; 121 122 if ( state->stack == state->stack_0 ) 123 { 124 state->stack = NULL; 125 old_size = 0; 126 } 127 128 /* requirement of the character stack larger than 1<<LZW_MAX_BITS */ 129 /* implies bug in the decompression code */ 130 if ( new_size > ( 1 << LZW_MAX_BITS ) ) 131 { 132 new_size = 1 << LZW_MAX_BITS; 133 if ( new_size == old_size ) 134 return -1; 135 } 136 137 if ( FT_RENEW_ARRAY( state->stack, old_size, new_size ) ) 138 return -1; 139 140 state->stack_size = new_size; 141 } 142 return 0; 143 } 144 145 146 /* grow the prefix/suffix arrays */ 147 static int 148 ft_lzwstate_prefix_grow( FT_LzwState state ) 149 { 150 FT_UInt old_size = state->prefix_size; 151 FT_UInt new_size = old_size; 152 FT_Memory memory = state->memory; 153 FT_Error error; 154 155 156 if ( new_size == 0 ) /* first allocation -> 9 bits */ 157 new_size = 512; 158 else 159 new_size += new_size >> 2; /* don't grow too fast */ 160 161 /* 162 * Note that the `suffix' array is located in the same memory block 163 * pointed to by `prefix'. 164 * 165 * I know that sizeof(FT_Byte) == 1 by definition, but it is clearer 166 * to write it literally. 167 * 168 */ 169 if ( FT_REALLOC_MULT( state->prefix, old_size, new_size, 170 sizeof ( FT_UShort ) + sizeof ( FT_Byte ) ) ) 171 return -1; 172 173 /* now adjust `suffix' and move the data accordingly */ 174 state->suffix = (FT_Byte*)( state->prefix + new_size ); 175 176 FT_MEM_MOVE( state->suffix, 177 state->prefix + old_size, 178 old_size * sizeof ( FT_Byte ) ); 179 180 state->prefix_size = new_size; 181 return 0; 182 } 183 184 185 FT_LOCAL_DEF( void ) 186 ft_lzwstate_reset( FT_LzwState state ) 187 { 188 state->in_eof = 0; 189 state->buf_offset = 0; 190 state->buf_size = 0; 191 state->buf_clear = 0; 192 state->buf_total = 0; 193 state->stack_top = 0; 194 state->num_bits = LZW_INIT_BITS; 195 state->phase = FT_LZW_PHASE_START; 196 } 197 198 199 FT_LOCAL_DEF( void ) 200 ft_lzwstate_init( FT_LzwState state, 201 FT_Stream source ) 202 { 203 FT_ZERO( state ); 204 205 state->source = source; 206 state->memory = source->memory; 207 208 state->prefix = NULL; 209 state->suffix = NULL; 210 state->prefix_size = 0; 211 212 state->stack = state->stack_0; 213 state->stack_size = sizeof ( state->stack_0 ); 214 215 ft_lzwstate_reset( state ); 216 } 217 218 219 FT_LOCAL_DEF( void ) 220 ft_lzwstate_done( FT_LzwState state ) 221 { 222 FT_Memory memory = state->memory; 223 224 225 ft_lzwstate_reset( state ); 226 227 if ( state->stack != state->stack_0 ) 228 FT_FREE( state->stack ); 229 230 FT_FREE( state->prefix ); 231 state->suffix = NULL; 232 233 FT_ZERO( state ); 234 } 235 236 237 #define FTLZW_STACK_PUSH( c ) \ 238 FT_BEGIN_STMNT \ 239 if ( state->stack_top >= state->stack_size && \ 240 ft_lzwstate_stack_grow( state ) < 0 ) \ 241 goto Eof; \ 242 \ 243 state->stack[state->stack_top++] = (FT_Byte)(c); \ 244 FT_END_STMNT 245 246 247 FT_LOCAL_DEF( FT_ULong ) 248 ft_lzwstate_io( FT_LzwState state, 249 FT_Byte* buffer, 250 FT_ULong out_size ) 251 { 252 FT_ULong result = 0; 253 254 FT_UInt old_char = state->old_char; 255 FT_UInt old_code = state->old_code; 256 FT_UInt in_code = state->in_code; 257 258 259 if ( out_size == 0 ) 260 goto Exit; 261 262 switch ( state->phase ) 263 { 264 case FT_LZW_PHASE_START: 265 { 266 FT_Byte max_bits; 267 FT_Int32 c; 268 269 270 /* skip magic bytes, and read max_bits + block_flag */ 271 if ( FT_Stream_Seek( state->source, 2 ) != 0 || 272 FT_Stream_TryRead( state->source, &max_bits, 1 ) != 1 ) 273 goto Eof; 274 275 state->max_bits = max_bits & LZW_BIT_MASK; 276 state->block_mode = max_bits & LZW_BLOCK_MASK; 277 state->max_free = (FT_UInt)( ( 1UL << state->max_bits ) - 256 ); 278 279 if ( state->max_bits > LZW_MAX_BITS ) 280 goto Eof; 281 282 state->num_bits = LZW_INIT_BITS; 283 state->free_ent = ( state->block_mode ? LZW_FIRST 284 : LZW_CLEAR ) - 256; 285 in_code = 0; 286 287 state->free_bits = state->num_bits < state->max_bits 288 ? (FT_UInt)( ( 1UL << state->num_bits ) - 256 ) 289 : state->max_free + 1; 290 291 c = ft_lzwstate_get_code( state ); 292 if ( c < 0 || c > 255 ) 293 goto Eof; 294 295 old_code = old_char = (FT_UInt)c; 296 297 if ( buffer ) 298 buffer[result] = (FT_Byte)old_char; 299 300 if ( ++result >= out_size ) 301 goto Exit; 302 303 state->phase = FT_LZW_PHASE_CODE; 304 } 305 /* fall-through */ 306 307 case FT_LZW_PHASE_CODE: 308 { 309 FT_Int32 c; 310 FT_UInt code; 311 312 313 NextCode: 314 c = ft_lzwstate_get_code( state ); 315 if ( c < 0 ) 316 goto Eof; 317 318 code = (FT_UInt)c; 319 320 if ( code == LZW_CLEAR && state->block_mode ) 321 { 322 /* why not LZW_FIRST-256 ? */ 323 state->free_ent = ( LZW_FIRST - 1 ) - 256; 324 state->buf_clear = 1; 325 326 /* not quite right, but at least more predictable */ 327 old_code = 0; 328 old_char = 0; 329 330 goto NextCode; 331 } 332 333 in_code = code; /* save code for later */ 334 335 if ( code >= 256U ) 336 { 337 /* special case for KwKwKwK */ 338 if ( code - 256U >= state->free_ent ) 339 { 340 /* corrupted LZW stream */ 341 if ( code - 256U > state->free_ent ) 342 goto Eof; 343 344 FTLZW_STACK_PUSH( old_char ); 345 code = old_code; 346 } 347 348 while ( code >= 256U ) 349 { 350 if ( !state->prefix ) 351 goto Eof; 352 353 FTLZW_STACK_PUSH( state->suffix[code - 256] ); 354 code = state->prefix[code - 256]; 355 } 356 } 357 358 old_char = code; 359 FTLZW_STACK_PUSH( old_char ); 360 361 state->phase = FT_LZW_PHASE_STACK; 362 } 363 /* fall-through */ 364 365 case FT_LZW_PHASE_STACK: 366 { 367 while ( state->stack_top > 0 ) 368 { 369 --state->stack_top; 370 371 if ( buffer ) 372 buffer[result] = state->stack[state->stack_top]; 373 374 if ( ++result == out_size ) 375 goto Exit; 376 } 377 378 /* now create new entry */ 379 if ( state->free_ent < state->max_free ) 380 { 381 if ( state->free_ent >= state->prefix_size && 382 ft_lzwstate_prefix_grow( state ) < 0 ) 383 goto Eof; 384 385 FT_ASSERT( state->free_ent < state->prefix_size ); 386 387 state->prefix[state->free_ent] = (FT_UShort)old_code; 388 state->suffix[state->free_ent] = (FT_Byte) old_char; 389 390 state->free_ent += 1; 391 } 392 393 old_code = in_code; 394 395 state->phase = FT_LZW_PHASE_CODE; 396 goto NextCode; 397 } 398 399 default: /* state == EOF */ 400 ; 401 } 402 403 Exit: 404 state->old_code = old_code; 405 state->old_char = old_char; 406 state->in_code = in_code; 407 408 return result; 409 410 Eof: 411 state->phase = FT_LZW_PHASE_EOF; 412 goto Exit; 413 } 414 415 416 /* END */ 417