lib/tasort.c

   1 /* tasort.c */
   2
   3 /*
   4  * Copyright (C) 2011-2018 by Werner Lemberg.
   5  *
   6  * This file is part of the ttfautohint library, and may only be used,
   7  * modified, and distributed under the terms given in `COPYING'.  By
   8  * continuing to use, modify, or distribute this file you indicate that you
   9  * have read `COPYING' and understand and accept it fully.
  10  *
  11  * The file `COPYING' mentioned in the previous paragraph is distributed
  12  * with the ttfautohint library.
  13  */
  14
  15
  16 /* originally file `afangles.c' (2011-Mar-28) from FreeType */
  17
  18 /* heavily modified 2011 by Werner Lemberg <wl@gnu.org> */
  19
  20 #include "tatypes.h"
  21 #include "tasort.h"
  22
  23
  24 /* two bubble sort routines */
  25
  26 void
  27 ta_sort_pos(FT_UInt count,
  28             FT_Pos* table)
  29 {
  30   FT_UInt i, j;
  31   FT_Pos swap;
  32
  33
  34   for (i = 1; i < count; i++)
  35   {
  36     for (j = i; j > 0; j--)
  37     {
  38       if (table[j] >= table[j - 1])
  39         break;
  40
  41       swap = table[j];
  42       table[j] = table[j - 1];
  43       table[j - 1] = swap;
  44     }
  45   }
  46 }
  47
  48
  49 void
  50 ta_sort_and_quantize_widths(FT_UInt* count,
  51                             TA_Width table,
  52                             FT_Pos threshold)
  53 {
  54   FT_UInt i;
  55   FT_UInt j;
  56   FT_UInt cur_idx;
  57   FT_Pos cur_val;
  58   FT_Pos sum;
  59   TA_WidthRec swap;
  60
  61
  62   if (*count == 1)
  63     return;
  64
  65   /* sort */
  66   for (i = 1; i < *count; i++)
  67   {
  68     for (j = i; j > 0; j--)
  69     {
  70       if (table[j].org >= table[j - 1].org)
  71         break;
  72
  73       swap = table[j];
  74       table[j] = table[j - 1];
  75       table[j - 1] = swap;
  76     }
  77   }
  78
  79   cur_idx = 0;
  80   cur_val = table[cur_idx].org;
  81
  82   /* compute and use mean values for clusters not larger than `threshold'; */
  83   /* this is very primitive and might not yield the best result, */
  84   /* but normally, using reference character `o', `*count' is 2, */
  85   /* so the code below is fully sufficient */
  86   for (i = 1; i < *count; i++)
  87   {
  88     if (table[i].org - cur_val > threshold
  89         || i == *count - 1)
  90     {
  91       sum = 0;
  92
  93       /* fix loop for end of array */
  94       if (table[i].org - cur_val <= threshold
  95           && i == *count - 1)
  96         i++;
  97
  98       for (j = cur_idx; j < i; j++)
  99       {
 100         sum += table[j].org;
 101         table[j].org = 0;
 102       }
 103       table[cur_idx].org = sum / (FT_Pos)j;
 104
 105       if (i < *count - 1)
 106       {
 107         cur_idx = i + 1;
 108         cur_val = table[cur_idx].org;
 109       }
 110     }
 111   }
 112
 113   cur_idx = 1;
 114
 115   /* compress array to remove zero values */
 116   for (i = 1; i < *count; i++)
 117   {
 118     if (table[i].org)
 119       table[cur_idx++] = table[i];
 120   }
 121
 122   *count = cur_idx;
 123 }
 124
 125 /* end of tasort.c */