/***************************************************************************//*                                                                         *//*  pshalgo2.c                                                             *//*                                                                         *//*    PostScript hinting algorithm 2 (body).                               *//*                                                                         *//*  Copyright 2001, 2002 by                                                *//*  David Turner, Robert Wilhelm, and Werner Lemberg.                      *//*                                                                         *//*  This file is part of the FreeType project, and may only be used        *//*  modified and distributed under the terms of the FreeType project       *//*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     *//*  this file you indicate that you have read the license and              *//*  understand and accept it fully.                                        *//*                                                                         *//***************************************************************************/#include <ft2build.h>#include FT_INTERNAL_OBJECTS_H#include FT_INTERNAL_DEBUG_H#include "pshalgo2.h"#undef  FT_COMPONENT#define FT_COMPONENT  trace_pshalgo2#ifdef DEBUG_HINTER  extern PSH2_Hint_Table  ps2_debug_hint_table = 0;  extern PSH2_HintFunc    ps2_debug_hint_func  = 0;  extern PSH2_Glyph       ps2_debug_glyph      = 0;#endif  /*************************************************************************/  /*************************************************************************/  /*****                                                               *****/  /*****                  BASIC HINTS RECORDINGS                       *****/  /*****                                                               *****/  /*************************************************************************/  /*************************************************************************/  /* return true iff two stem hints overlap */  static FT_Int  psh2_hint_overlap( PSH2_Hint  hint1,                     PSH2_Hint  hint2 )  {    return ( hint1->org_pos + hint1->org_len >= hint2->org_pos &&             hint2->org_pos + hint2->org_len >= hint1->org_pos );  }  /* destroy hints table */  static void  psh2_hint_table_done( PSH2_Hint_Table  table,                        FT_Memory        memory )  {    FT_FREE( table->zones );    table->num_zones = 0;    table->zone      = 0;    FT_FREE( table->sort );    FT_FREE( table->hints );    table->num_hints   = 0;    table->max_hints   = 0;    table->sort_global = 0;  }  /* deactivate all hints in a table */  static void  psh2_hint_table_deactivate( PSH2_Hint_Table  table )  {    FT_UInt   count = table->max_hints;    PSH2_Hint  hint  = table->hints;    for ( ; count > 0; count--, hint++ )    {      psh2_hint_deactivate( hint );      hint->order = -1;    }  }  /* internal function used to record a new hint */  static void  psh2_hint_table_record( PSH2_Hint_Table  table,                          FT_UInt          idx )  {    PSH2_Hint  hint = table->hints + idx;    if ( idx >= table->max_hints )    {      FT_ERROR(( "%s.activate: invalid hint index %d\n", idx ));      return;    }    /* ignore active hints */    if ( psh2_hint_is_active( hint ) )      return;    psh2_hint_activate( hint );    /* now scan the current active hint set in order to determine */    /* if we are overlapping with another segment                 */    {      PSH2_Hint*  sorted = table->sort_global;      FT_UInt     count  = table->num_hints;      PSH2_Hint   hint2;      hint->parent = 0;      for ( ; count > 0; count--, sorted++ )      {        hint2 = sorted[0];        if ( psh2_hint_overlap( hint, hint2 ) )        {          hint->parent = hint2;          break;        }      }    }    if ( table->num_hints < table->max_hints )      table->sort_global[table->num_hints++] = hint;    else      FT_ERROR(( "%s.activate: too many sorted hints!  BUG!\n",                 "ps.fitter" ));  }  static void  psh2_hint_table_record_mask( PSH2_Hint_Table  table,                               PS_Mask          hint_mask )  {    FT_Int    mask = 0, val = 0;    FT_Byte*  cursor = hint_mask->bytes;    FT_UInt   idx, limit;    limit = hint_mask->num_bits;    for ( idx = 0; idx < limit; idx++ )    {      if ( mask == 0 )      {        val  = *cursor++;        mask = 0x80;      }      if ( val & mask )        psh2_hint_table_record( table, idx );      mask >>= 1;    }  }  /* create hints table */  static FT_Error  psh2_hint_table_init( PSH2_Hint_Table  table,                        PS_Hint_Table    hints,                        PS_Mask_Table    hint_masks,                        PS_Mask_Table    counter_masks,                        FT_Memory        memory )  {    FT_UInt   count = hints->num_hints;    FT_Error  error;    FT_UNUSED( counter_masks );    /* allocate our tables */    if ( FT_NEW_ARRAY( table->sort,  2 * count     ) ||         FT_NEW_ARRAY( table->hints,     count     ) ||         FT_NEW_ARRAY( table->zones, 2 * count + 1 ) )      goto Exit;    table->max_hints   = count;    table->sort_global = table->sort + count;    table->num_hints   = 0;    table->num_zones   = 0;    table->zone        = 0;    /* now, initialize the "hints" array */    {      PSH2_Hint  write = table->hints;      PS_Hint    read  = hints->hints;      for ( ; count > 0; count--, write++, read++ )      {        write->org_pos = read->pos;        write->org_len = read->len;        write->flags   = read->flags;      }    }    /* we now need to determine the initial "parent" stems; first  */    /* activate the hints that are given by the initial hint masks */    if ( hint_masks )    {      FT_UInt  Count = hint_masks->num_masks;      PS_Mask  Mask  = hint_masks->masks;      table->hint_masks = hint_masks;      for ( ; Count > 0; Count--, Mask++ )        psh2_hint_table_record_mask( table, Mask );    }    /* now, do a linear parse in case some hints were left alone */    if ( table->num_hints != table->max_hints )    {      FT_UInt   Index, Count;      FT_ERROR(( "%s.init: missing/incorrect hint masks!\n" ));      Count = table->max_hints;      for ( Index = 0; Index < Count; Index++ )        psh2_hint_table_record( table, Index );    }  Exit:    return error;  }  static void  psh2_hint_table_activate_mask( PSH2_Hint_Table  table,                                 PS_Mask          hint_mask )  {    FT_Int    mask = 0, val = 0;    FT_Byte*  cursor = hint_mask->bytes;    FT_UInt   idx, limit, count;    limit = hint_mask->num_bits;    count = 0;    psh2_hint_table_deactivate( table );    for ( idx = 0; idx < limit; idx++ )    {      if ( mask == 0 )      {        val  = *cursor++;        mask = 0x80;      }      if ( val & mask )      {        PSH2_Hint  hint = &table->hints[idx];        if ( !psh2_hint_is_active( hint ) )        {          FT_UInt     count2;#if 0          PSH2_Hint*  sort = table->sort;          PSH2_Hint   hint2;          for ( count2 = count; count2 > 0; count2--, sort++ )          {            hint2 = sort[0];            if ( psh2_hint_overlap( hint, hint2 ) )              FT_ERROR(( "%s.activate_mask: found overlapping hints\n",                         "psf.hint" ));          }#else          count2 = 0;#endif          if ( count2 == 0 )          {            psh2_hint_activate( hint );            if ( count < table->max_hints )              table->sort[count++] = hint;            else              FT_ERROR(( "%s.activate_mask: too many active hints\n",                         "psf.hint" ));          }        }      }      mask >>= 1;    }    table->num_hints = count;    /* now, sort the hints; they are guaranteed to not overlap */    /* so we can compare their "org_pos" field directly        */    {      FT_Int      i1, i2;      PSH2_Hint   hint1, hint2;      PSH2_Hint*  sort = table->sort;      /* a simple bubble sort will do, since in 99% of cases, the hints */      /* will be already sorted -- and the sort will be linear          */      for ( i1 = 1; i1 < (FT_Int)count; i1++ )      {        hint1 = sort[i1];        for ( i2 = i1 - 1; i2 >= 0; i2-- )        {          hint2 = sort[i2];          if ( hint2->org_pos < hint1->org_pos )            break;          sort[i2 + 1] = hint2;          sort[i2]     = hint1;        }      }    }  }  /*************************************************************************/  /*************************************************************************/  /*****                                                               *****/  /*****               HINTS GRID-FITTING AND OPTIMIZATION             *****/  /*****                                                               *****/  /*************************************************************************/  /*************************************************************************/#ifdef DEBUG_HINTER  static void  ps2_simple_scale( PSH2_Hint_Table  table,                    FT_Fixed         scale,                    FT_Fixed         delta,                    FT_Int           dimension )  {    PSH2_Hint  hint;    FT_UInt    count;    for ( count = 0; count < table->max_hints; count++ )    {      hint = table->hints + count;      hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta;      hint->cur_len = FT_MulFix( hint->org_len, scale );      if ( ps2_debug_hint_func )        ps2_debug_hint_func( hint, dimension );    }  }#endif  static void  psh2_hint_align( PSH2_Hint    hint,                   PSH_Globals  globals,                   FT_Int       dimension )  {    PSH_Dimension  dim   = &globals->dimension[dimension];    FT_Fixed       scale = dim->scale_mult;    FT_Fixed       delta = dim->scale_delta;    if ( !psh2_hint_is_fitted(hint) )    {      FT_Pos  pos = FT_MulFix( hint->org_pos, scale ) + delta;      FT_Pos  len = FT_MulFix( hint->org_len, scale );      FT_Pos  fit_center;      FT_Pos  fit_len;      PSH_AlignmentRec  align;      /* compute fitted width/height */      fit_len = 0;      if ( hint->org_len )      {        fit_len = psh_dimension_snap_width( dim, hint->org_len );        if ( fit_len < 64 )          fit_len = 64;        else          fit_len = ( fit_len + 32 ) & -64;      }      hint->cur_len = fit_len;      /* check blue zones for horizontal stems */      align.align = PSH_BLUE_ALIGN_NONE;      align.align_bot = align.align_top = 0;      if ( dimension == 1 )        psh_blues_snap_stem( &globals->blues,                             hint->org_pos + hint->org_len,                             hint->org_pos,                             &align );      switch ( align.align )      {      case PSH_BLUE_ALIGN_TOP:        /* the top of the stem is aligned against a blue zone */        hint->cur_pos = align.align_top - fit_len;        break;      case PSH_BLUE_ALIGN_BOT:        /* the bottom of the stem is aligned against a blue zone */        hint->cur_pos = align.align_bot;        break;      case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:        /* both edges of the stem are aligned against blue zones */        hint->cur_pos = align.align_bot;        hint->cur_len = align.align_top - align.align_bot;        break;      default:        {          PSH2_Hint  parent = hint->parent;          if ( parent )          {            FT_Pos  par_org_center, par_cur_center;            FT_Pos  cur_org_center, cur_delta;            /* ensure that parent is already fitted */            if ( !psh2_hint_is_fitted( parent ) )              psh2_hint_align( parent, globals, dimension );            par_org_center = parent->org_pos + ( parent->org_len / 2);            par_cur_center = parent->cur_pos + ( parent->cur_len / 2);            cur_org_center = hint->org_pos   + ( hint->org_len   / 2);            cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );#if 0            if ( cur_delta >= 0 )              cur_delta = ( cur_delta + 16 ) & -64;            else              cur_delta = -( (-cur_delta + 16 ) & -64 );#endif            pos = par_cur_center + cur_delta - ( len >> 1 );          }          /* normal processing */          if ( ( fit_len / 64 ) & 1 )          {            /* odd number of pixels */            fit_center = ( ( pos + ( len >> 1 ) ) & -64 ) + 32;          }          else          {            /* even number of pixels */            fit_center = ( pos + ( len >> 1 ) + 32 ) & -64;          }          hint->cur_pos = fit_center - ( fit_len >> 1 );        }      }      psh2_hint_set_fitted( hint );#ifdef DEBUG_HINTER      if ( ps2_debug_hint_func )        ps2_debug_hint_func( hint, dimension );#endif    }  }  static void  psh2_hint_table_align_hints( PSH2_Hint_Table  table,                               PSH_Globals      globals,                               FT_Int           dimension )  {    PSH2_Hint      hint;    FT_UInt        count;#ifdef DEBUG_HINTER    PSH_Dimension  dim   = &globals->dimension[dimension];    FT_Fixed       scale = dim->scale_mult;    FT_Fixed       delta = dim->scale_delta;    if ( ps_debug_no_vert_hints && dimension == 0 )    {      ps2_simple_scale( table, scale, delta, dimension );      return;    }    if ( ps_debug_no_horz_hints && dimension == 1 )    {      ps2_simple_scale( table, scale, delta, dimension );      return;    }#endif    hint  = table->hints;    count = table->max_hints;    for ( ; count > 0; count--, hint++ )      psh2_hint_align( hint, globals, dimension );  }  /*************************************************************************/  /*************************************************************************/  /*****                                                               *****/  /*****                POINTS INTERPOLATION ROUTINES                  *****/  /*****                                                               *****/  /*************************************************************************/  /*************************************************************************/#define PSH2_ZONE_MIN  -3200000#define PSH2_ZONE_MAX  +3200000#define xxDEBUG_ZONES