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