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 (C) 2005-2020 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 <freetype/internal/ftmemory.h>
  24 #include <freetype/internal/ftstream.h>
  25 #include <freetype/internal/ftdebug.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
  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
  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
 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
 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 )
 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 )
 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 )
 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 )
 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 */