thirdparty/freetype-2.3.12/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, 2006, 2007, 2009 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       if ( FT_RENEW_ARRAY( state->stack, old_size, new_size ) )
 128         return -1;
 129
 130       state->stack_size = new_size;
 131     }
 132     return 0;
 133   }
 134
 135
 136   /* grow the prefix/suffix arrays */
 137   static int
 138   ft_lzwstate_prefix_grow( FT_LzwState  state )
 139   {
 140     FT_UInt    old_size = state->prefix_size;
 141     FT_UInt    new_size = old_size;
 142     FT_Memory  memory   = state->memory;
 143     FT_Error   error;
 144
 145
 146     if ( new_size == 0 )  /* first allocation -> 9 bits */
 147       new_size = 512;
 148     else
 149       new_size += new_size >> 2;  /* don't grow too fast */
 150
 151     /*
 152      *  Note that the `suffix' array is located in the same memory block
 153      *  pointed to by `prefix'.
 154      *
 155      *  I know that sizeof(FT_Byte) == 1 by definition, but it is clearer
 156      *  to write it literally.
 157      *
 158      */
 159     if ( FT_REALLOC_MULT( state->prefix, old_size, new_size,
 160                           sizeof ( FT_UShort ) + sizeof ( FT_Byte ) ) )
 161       return -1;
 162
 163     /* now adjust `suffix' and move the data accordingly */
 164     state->suffix = (FT_Byte*)( state->prefix + new_size );
 165
 166     FT_MEM_MOVE( state->suffix,
 167                  state->prefix + old_size,
 168                  old_size * sizeof ( FT_Byte ) );
 169
 170     state->prefix_size = new_size;
 171     return 0;
 172   }
 173
 174
 175   FT_LOCAL_DEF( void )
 176   ft_lzwstate_reset( FT_LzwState  state )
 177   {
 178     state->in_eof     = 0;
 179     state->buf_offset = 0;
 180     state->buf_size   = 0;
 181     state->buf_clear  = 0;
 182     state->buf_total  = 0;
 183     state->stack_top  = 0;
 184     state->num_bits   = LZW_INIT_BITS;
 185     state->phase      = FT_LZW_PHASE_START;
 186   }
 187
 188
 189   FT_LOCAL_DEF( void )
 190   ft_lzwstate_init( FT_LzwState  state,
 191                     FT_Stream    source )
 192   {
 193     FT_ZERO( state );
 194
 195     state->source = source;
 196     state->memory = source->memory;
 197
 198     state->prefix      = NULL;
 199     state->suffix      = NULL;
 200     state->prefix_size = 0;
 201
 202     state->stack      = state->stack_0;
 203     state->stack_size = sizeof ( state->stack_0 );
 204
 205     ft_lzwstate_reset( state );
 206   }
 207
 208
 209   FT_LOCAL_DEF( void )
 210   ft_lzwstate_done( FT_LzwState  state )
 211   {
 212     FT_Memory  memory = state->memory;
 213
 214
 215     ft_lzwstate_reset( state );
 216
 217     if ( state->stack != state->stack_0 )
 218       FT_FREE( state->stack );
 219
 220     FT_FREE( state->prefix );
 221     state->suffix = NULL;
 222
 223     FT_ZERO( state );
 224   }
 225
 226
 227 #define FTLZW_STACK_PUSH( c )                        \
 228   FT_BEGIN_STMNT                                     \
 229     if ( state->stack_top >= state->stack_size &&    \
 230          ft_lzwstate_stack_grow( state ) < 0   )     \
 231       goto Eof;                                      \
 232                                                      \
 233     state->stack[state->stack_top++] = (FT_Byte)(c); \
 234   FT_END_STMNT
 235
 236
 237   FT_LOCAL_DEF( FT_ULong )
 238   ft_lzwstate_io( FT_LzwState  state,
 239                   FT_Byte*     buffer,
 240                   FT_ULong     out_size )
 241   {
 242     FT_ULong  result = 0;
 243
 244     FT_UInt  old_char = state->old_char;
 245     FT_UInt  old_code = state->old_code;
 246     FT_UInt  in_code  = state->in_code;
 247
 248
 249     if ( out_size == 0 )
 250       goto Exit;
 251
 252     switch ( state->phase )
 253     {
 254     case FT_LZW_PHASE_START:
 255       {
 256         FT_Byte   max_bits;
 257         FT_Int32  c;
 258
 259
 260         /* skip magic bytes, and read max_bits + block_flag */
 261         if ( FT_Stream_Seek( state->source, 2 ) != 0               ||
 262              FT_Stream_TryRead( state->source, &max_bits, 1 ) != 1 )
 263           goto Eof;
 264
 265         state->max_bits   = max_bits & LZW_BIT_MASK;
 266         state->block_mode = max_bits & LZW_BLOCK_MASK;
 267         state->max_free   = (FT_UInt)( ( 1UL << state->max_bits ) - 256 );
 268
 269         if ( state->max_bits > LZW_MAX_BITS )
 270           goto Eof;
 271
 272         state->num_bits = LZW_INIT_BITS;
 273         state->free_ent = ( state->block_mode ? LZW_FIRST
 274                                               : LZW_CLEAR ) - 256;
 275         in_code  = 0;
 276
 277         state->free_bits = state->num_bits < state->max_bits
 278                            ? (FT_UInt)( ( 1UL << state->num_bits ) - 256 )
 279                            : state->max_free + 1;
 280
 281         c = ft_lzwstate_get_code( state );
 282         if ( c < 0 )
 283           goto Eof;
 284
 285         old_code = old_char = (FT_UInt)c;
 286
 287         if ( buffer )
 288           buffer[result] = (FT_Byte)old_char;
 289
 290         if ( ++result >= out_size )
 291           goto Exit;
 292
 293         state->phase = FT_LZW_PHASE_CODE;
 294       }
 295       /* fall-through */
 296
 297     case FT_LZW_PHASE_CODE:
 298       {
 299         FT_Int32  c;
 300         FT_UInt   code;
 301
 302
 303       NextCode:
 304         c = ft_lzwstate_get_code( state );
 305         if ( c < 0 )
 306           goto Eof;
 307
 308         code = (FT_UInt)c;
 309
 310         if ( code == LZW_CLEAR && state->block_mode )
 311         {
 312           /* why not LZW_FIRST-256 ? */
 313           state->free_ent  = ( LZW_FIRST - 1 ) - 256;
 314           state->buf_clear = 1;
 315           c = ft_lzwstate_get_code( state );
 316           if ( c < 0 )
 317             goto Eof;
 318
 319           code = (FT_UInt)c;
 320         }
 321
 322         in_code = code; /* save code for later */
 323
 324         if ( code >= 256U )
 325         {
 326           /* special case for KwKwKwK */
 327           if ( code - 256U >= state->free_ent )
 328           {
 329             FTLZW_STACK_PUSH( old_char );
 330             code = old_code;
 331           }
 332
 333           while ( code >= 256U )
 334           {
 335             if ( !state->prefix )
 336               goto Eof;
 337
 338             FTLZW_STACK_PUSH( state->suffix[code - 256] );
 339             code = state->prefix[code - 256];
 340           }
 341         }
 342
 343         old_char = code;
 344         FTLZW_STACK_PUSH( old_char );
 345
 346         state->phase = FT_LZW_PHASE_STACK;
 347       }
 348       /* fall-through */
 349
 350     case FT_LZW_PHASE_STACK:
 351       {
 352         while ( state->stack_top > 0 )
 353         {
 354           --state->stack_top;
 355
 356           if ( buffer )
 357             buffer[result] = state->stack[state->stack_top];
 358
 359           if ( ++result == out_size )
 360             goto Exit;
 361         }
 362
 363         /* now create new entry */
 364         if ( state->free_ent < state->max_free )
 365         {
 366           if ( state->free_ent >= state->prefix_size &&
 367                ft_lzwstate_prefix_grow( state ) < 0  )
 368             goto Eof;
 369
 370           FT_ASSERT( state->free_ent < state->prefix_size );
 371
 372           state->prefix[state->free_ent] = (FT_UShort)old_code;
 373           state->suffix[state->free_ent] = (FT_Byte)  old_char;
 374
 375           state->free_ent += 1;
 376         }
 377
 378         old_code = in_code;
 379
 380         state->phase = FT_LZW_PHASE_CODE;
 381         goto NextCode;
 382       }
 383
 384     default:  /* state == EOF */
 385       ;
 386     }
 387
 388   Exit:
 389     state->old_code = old_code;
 390     state->old_char = old_char;
 391     state->in_code  = in_code;
 392
 393     return result;
 394
 395   Eof:
 396     state->phase = FT_LZW_PHASE_EOF;
 397     goto Exit;
 398   }
 399
 400
 401 /* END */