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 */