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

/*                                                                         */

/*  ttkern.c                                                               */

/*                                                                         */

/*    Load the basic TrueType kerning table.  This doesn't handle          */

/*    kerning data within the GPOS table at the moment.                    */

/*                                                                         */

/*  Copyright 1996-2001, 2002, 2003, 2004, 2005, 2006, 2007, 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_DEBUG_H

#include FT_INTERNAL_STREAM_H

#include FT_TRUETYPE_TAGS_H

#include "ttkern.h"

#include "sferrors.h"

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

  /*                                                                       */

  /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */

  /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */

  /* messages during execution.                                            */

  /*                                                                       */

#undef  FT_COMPONENT

#define FT_COMPONENT  trace_ttkern

#undef  TT_KERN_INDEX

#define TT_KERN_INDEX( g1, g2 )  ( ( (FT_ULong)(g1) << 16 ) | (g2) )

  FT_LOCAL_DEF( FT_Error )

  tt_face_load_kern( TT_Face    face,

                     FT_Stream  stream )

  {

    FT_Error   error;

    FT_ULong   table_size;

    FT_Byte*   p;

    FT_Byte*   p_limit;

    FT_UInt    nn, num_tables;

    FT_UInt32  avail = 0, ordered = 0;

    /* the kern table is optional; exit silently if it is missing */

    error = face->goto_table( face, TTAG_kern, stream, &table_size );

    if ( error )

      goto Exit;

    if ( table_size < 4 )  /* the case of a malformed table */

    {

      FT_ERROR(( "tt_face_load_kern:"

                 " kerning table is too small - ignored\n" ));

      error = SFNT_Err_Table_Missing;

      goto Exit;

    }

    if ( FT_FRAME_EXTRACT( table_size, face->kern_table ) )

    {

      FT_ERROR(( "tt_face_load_kern:"

                 " could not extract kerning table\n" ));

      goto Exit;

    }

    face->kern_table_size = table_size;

    p       = face->kern_table;

    p_limit = p + table_size;

    p         += 2; /* skip version */

    num_tables = FT_NEXT_USHORT( p );

    if ( num_tables > 32 ) /* we only support up to 32 sub-tables */

      num_tables = 32;

    for ( nn = 0; nn < num_tables; nn++ )

    {

      FT_UInt    num_pairs, length, coverage;

      FT_Byte*   p_next;

      FT_UInt32  mask = (FT_UInt32)1UL << nn;

      if ( p + 6 > p_limit )

        break;

      p_next = p;

      p += 2; /* skip version */

      length   = FT_NEXT_USHORT( p );

      coverage = FT_NEXT_USHORT( p );

      if ( length <= 6 )

        break;

      p_next += length;

      if ( p_next > p_limit )  /* handle broken table */

        p_next = p_limit;

      /* only use horizontal kerning tables */

      if ( ( coverage & ~8 ) != 0x0001 ||

           p + 8 > p_limit             )

        goto NextTable;

      num_pairs = FT_NEXT_USHORT( p );

      p        += 6;

      if ( ( p_next - p ) < 6 * (int)num_pairs ) /* handle broken count */

        num_pairs = (FT_UInt)( ( p_next - p ) / 6 );

      avail |= mask;

      /*

       *  Now check whether the pairs in this table are ordered.

       *  We then can use binary search.

       */

      if ( num_pairs > 0 )

      {

        FT_ULong  count;

        FT_ULong  old_pair;

        old_pair = FT_NEXT_ULONG( p );

        p       += 2;

        for ( count = num_pairs - 1; count > 0; count-- )

        {

          FT_UInt32  cur_pair;

          cur_pair = FT_NEXT_ULONG( p );

          if ( cur_pair <= old_pair )

            break;

          p += 2;

          old_pair = cur_pair;

        }

        if ( count == 0 )

          ordered |= mask;

      }

    NextTable:

      p = p_next;

    }

    face->num_kern_tables = nn;

    face->kern_avail_bits = avail;

    face->kern_order_bits = ordered;

  Exit:

    return error;

  }

  FT_LOCAL_DEF( void )

  tt_face_done_kern( TT_Face  face )

  {

    FT_Stream  stream = face->root.stream;

    FT_FRAME_RELEASE( face->kern_table );

    face->kern_table_size = 0;

    face->num_kern_tables = 0;

    face->kern_avail_bits = 0;

    face->kern_order_bits = 0;

  }

  FT_LOCAL_DEF( FT_Int )

  tt_face_get_kerning( TT_Face  face,

                       FT_UInt  left_glyph,

                       FT_UInt  right_glyph )

  {

    FT_Int    result = 0;

    FT_UInt   count, mask = 1;

    FT_Byte*  p       = face->kern_table;

    FT_Byte*  p_limit = p + face->kern_table_size;

    p   += 4;

    mask = 0x0001;

    for ( count = face->num_kern_tables;

          count > 0 && p + 6 <= p_limit;

          count--, mask <<= 1 )

    {

      FT_Byte* base     = p;

      FT_Byte* next     = base;

      FT_UInt  version  = FT_NEXT_USHORT( p );

      FT_UInt  length   = FT_NEXT_USHORT( p );

      FT_UInt  coverage = FT_NEXT_USHORT( p );

      FT_UInt  num_pairs;

      FT_Int   value    = 0;

      FT_UNUSED( version );

      next = base + length;

      if ( next > p_limit )  /* handle broken table */

        next = p_limit;

      if ( ( face->kern_avail_bits & mask ) == 0 )

        goto NextTable;

      if ( p + 8 > next )

        goto NextTable;

      num_pairs = FT_NEXT_USHORT( p );

      p        += 6;

      if ( ( next - p ) < 6 * (int)num_pairs )  /* handle broken count  */

        num_pairs = (FT_UInt)( ( next - p ) / 6 );

      switch ( coverage >> 8 )

      {

      case 0:

        {

          FT_ULong  key0 = TT_KERN_INDEX( left_glyph, right_glyph );

          if ( face->kern_order_bits & mask )   /* binary search */

          {

            FT_UInt   min = 0;

            FT_UInt   max = num_pairs;

            while ( min < max )

            {

              FT_UInt   mid = ( min + max ) >> 1;

              FT_Byte*  q   = p + 6 * mid;

              FT_ULong  key;

              key = FT_NEXT_ULONG( q );

              if ( key == key0 )

              {

                value = FT_PEEK_SHORT( q );

                goto Found;

              }

              if ( key < key0 )

                min = mid + 1;

              else

                max = mid;

            }

          }

          else /* linear search */

          {

            FT_UInt  count2;

            for ( count2 = num_pairs; count2 > 0; count2-- )

            {

              FT_ULong  key = FT_NEXT_ULONG( p );

              if ( key == key0 )

              {

                value = FT_PEEK_SHORT( p );

                goto Found;

              }

              p += 2;

            }

          }

        }

        break;

       /*

        *  We don't support format 2 because we haven't seen a single font

        *  using it in real life...

        */

      default:

        ;

      }

      goto NextTable;

    Found:

      if ( coverage & 8 ) /* override or add */

        result = value;

      else

        result += value;

    NextTable:

      p = next;

    }

    return result;

  }

#undef TT_KERN_INDEX

/* END */