/***************************************************************************/

/*                                                                         */

/*  pshalgo.c                                                              */

/*                                                                         */

/*    PostScript hinting algorithm (body).                                 */

/*                                                                         */

/*  Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010   */

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

#include "pshalgo.h"

#include "pshnterr.h"

#undef  FT_COMPONENT

#define FT_COMPONENT  trace_pshalgo2

#ifdef DEBUG_HINTER

  PSH_Hint_Table  ps_debug_hint_table = 0;

  PSH_HintFunc    ps_debug_hint_func  = 0;

  PSH_Glyph       ps_debug_glyph      = 0;

#endif

#define  COMPUTE_INFLEXS  /* compute inflection points to optimize `S' */

                          /* and similar glyphs                        */

#define  STRONGER         /* slightly increase the contrast of smooth  */

                          /* hinting                                   */

  /*************************************************************************/

  /*************************************************************************/

  /*****                                                               *****/

  /*****                  BASIC HINTS RECORDINGS                       *****/

  /*****                                                               *****/

  /*************************************************************************/

  /*************************************************************************/

  /* return true if two stem hints overlap */

  static FT_Int

  psh_hint_overlap( PSH_Hint  hint1,

                    PSH_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

  psh_hint_table_done( PSH_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

  psh_hint_table_deactivate( PSH_Hint_Table  table )

  {

    FT_UInt   count = table->max_hints;

    PSH_Hint  hint  = table->hints;

    for ( ; count > 0; count--, hint++ )

    {

      psh_hint_deactivate( hint );

      hint->order = -1;

    }

  }

  /* internal function to record a new hint */

  static void

  psh_hint_table_record( PSH_Hint_Table  table,

                         FT_UInt         idx )

  {

    PSH_Hint  hint = table->hints + idx;

    if ( idx >= table->max_hints )

    {

      FT_TRACE0(( "psh_hint_table_record: invalid hint index %d\n", idx ));

      return;

    }

    /* ignore active hints */

    if ( psh_hint_is_active( hint ) )

      return;

    psh_hint_activate( hint );

    /* now scan the current active hint set to check */

    /* whether `hint' overlaps with another hint     */

    {

      PSH_Hint*  sorted = table->sort_global;

      FT_UInt    count  = table->num_hints;

      PSH_Hint   hint2;

      hint->parent = 0;

      for ( ; count > 0; count--, sorted++ )

      {

        hint2 = sorted[0];

        if ( psh_hint_overlap( hint, hint2 ) )

        {

          hint->parent = hint2;

          break;

        }

      }

    }

    if ( table->num_hints < table->max_hints )

      table->sort_global[table->num_hints++] = hint;

    else

      FT_TRACE0(( "psh_hint_table_record: too many sorted hints!  BUG!\n" ));

  }

  static void

  psh_hint_table_record_mask( PSH_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 )

        psh_hint_table_record( table, idx );

      mask >>= 1;

    }

  }

  /* create hints table */

  static FT_Error

  psh_hint_table_init( PSH_Hint_Table  table,

                       PS_Hint_Table   hints,

                       PS_Mask_Table   hint_masks,

                       PS_Mask_Table   counter_masks,

                       FT_Memory       memory )

  {

    FT_UInt   count;

    FT_Error  error;

    FT_UNUSED( counter_masks );

    count = hints->num_hints;

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

    /* initialize the `table->hints' array */

    {

      PSH_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 )

    {

      PS_Mask  mask = hint_masks->masks;

      count             = hint_masks->num_masks;

      table->hint_masks = hint_masks;

      for ( ; count > 0; count--, mask++ )

        psh_hint_table_record_mask( table, mask );

    }

    /* finally, do a linear parse in case some hints were left alone */

    if ( table->num_hints != table->max_hints )

    {

      FT_UInt  idx;

      FT_TRACE0(( "psh_hint_table_init: missing/incorrect hint masks\n" ));

      count = table->max_hints;

      for ( idx = 0; idx < count; idx++ )

        psh_hint_table_record( table, idx );

    }

  Exit:

    return error;

  }

  static void

  psh_hint_table_activate_mask( PSH_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;

    psh_hint_table_deactivate( table );

    for ( idx = 0; idx < limit; idx++ )

    {

      if ( mask == 0 )

      {

        val  = *cursor++;

        mask = 0x80;

      }

      if ( val & mask )

      {

        PSH_Hint  hint = &table->hints[idx];

        if ( !psh_hint_is_active( hint ) )

        {

          FT_UInt     count2;

#if 0

          PSH_Hint*  sort = table->sort;

          PSH_Hint   hint2;

          for ( count2 = count; count2 > 0; count2--, sort++ )

          {

            hint2 = sort[0];

            if ( psh_hint_overlap( hint, hint2 ) )

              FT_TRACE0(( "psh_hint_table_activate_mask:"

                          " found overlapping hints\n" ))

          }

#else

          count2 = 0;

#endif

          if ( count2 == 0 )

          {

            psh_hint_activate( hint );

            if ( count < table->max_hints )

              table->sort[count++] = hint;

            else

              FT_TRACE0(( "psh_hint_tableactivate_mask:"

                          " too many active hints\n" ));

          }

        }

      }

      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;

      PSH_Hint   hint1, hint2;

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

  /*****                                                               *****/

  /*************************************************************************/

  /*************************************************************************/

#if 1

  static FT_Pos

  psh_dimension_quantize_len( PSH_Dimension  dim,

                              FT_Pos         len,

                              FT_Bool        do_snapping )

  {

    if ( len <= 64 )

      len = 64;

    else

    {

      FT_Pos  delta = len - dim->stdw.widths[0].cur;

      if ( delta < 0 )

        delta = -delta;

      if ( delta < 40 )

      {

        len = dim->stdw.widths[0].cur;

        if ( len < 48 )

          len = 48;

      }

      if ( len < 3 * 64 )

      {

        delta = ( len & 63 );

        len  &= -64;

        if ( delta < 10 )

          len += delta;

        else if ( delta < 32 )

          len += 10;

        else if ( delta < 54 )

          len += 54;

        else

          len += delta;

      }

      else

        len = FT_PIX_ROUND( len );

    }

    if ( do_snapping )

      len = FT_PIX_ROUND( len );

    return  len;

  }

#endif /* 0 */

#ifdef DEBUG_HINTER

  static void

  ps_simple_scale( PSH_Hint_Table  table,

                   FT_Fixed        scale,

                   FT_Fixed        delta,

                   FT_Int          dimension )

  {

    PSH_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 ( ps_debug_hint_func )

        ps_debug_hint_func( hint, dimension );

    }

  }

#endif /* DEBUG_HINTER */

  static FT_Fixed

  psh_hint_snap_stem_side_delta( FT_Fixed  pos,

                                 FT_Fixed  len )

  {

    FT_Fixed  delta1 = FT_PIX_ROUND( pos ) - pos;

    FT_Fixed  delta2 = FT_PIX_ROUND( pos + len ) - pos - len;

    if ( FT_ABS( delta1 ) <= FT_ABS( delta2 ) )

      return delta1;

    else

      return delta2;

  }

  static void

  psh_hint_align( PSH_Hint     hint,

                  PSH_Globals  globals,

                  FT_Int       dimension,

                  PSH_Glyph    glyph )

  {

    PSH_Dimension  dim   = &globals->dimension[dimension];

    FT_Fixed       scale = dim->scale_mult;

    FT_Fixed       delta = dim->scale_delta;

    if ( !psh_hint_is_fitted( hint ) )

    {

      FT_Pos  pos = FT_MulFix( hint->org_pos, scale ) + delta;

      FT_Pos  len = FT_MulFix( hint->org_len, scale );

      FT_Int            do_snapping;

      FT_Pos            fit_len;

      PSH_AlignmentRec  align;

      /* ignore stem alignments when requested through the hint flags */

      if ( ( dimension == 0 && !glyph->do_horz_hints ) ||

           ( dimension == 1 && !glyph->do_vert_hints ) )

      {

        hint->cur_pos = pos;

        hint->cur_len = len;

        psh_hint_set_fitted( hint );

        return;

      }

      /* perform stem snapping when requested - this is necessary

       * for monochrome and LCD hinting modes only

       */

      do_snapping = ( dimension == 0 && glyph->do_horz_snapping ) ||

                    ( dimension == 1 && glyph->do_vert_snapping );

      hint->cur_len = fit_len = 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:

        {

          PSH_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 ( !psh_hint_is_fitted( parent ) )

              psh_hint_align( parent, globals, dimension, glyph );

            /* keep original relation between hints, this is, use the */

            /* scaled distance between the centers of the hints to    */

            /* compute the new position                               */

            par_org_center = parent->org_pos + ( parent->org_len >> 1 );

            par_cur_center = parent->cur_pos + ( parent->cur_len >> 1 );

            cur_org_center = hint->org_pos   + ( hint->org_len   >> 1 );

            cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );