src/lzw/ftzopen.c

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