libs/port/normalize.c

   1 /*
   2  * Unicode normalization functions
   3  *
   4  * Copyright 2019 Huw Davies
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  */
  20
  21 #include "wine/unicode.h"
  22
  23 extern WCHAR wine_compose( const WCHAR *str ) DECLSPEC_HIDDEN;
  24 extern unsigned int wine_decompose( int flags, WCHAR ch, WCHAR *dst, unsigned int dstlen ) DECLSPEC_HIDDEN;
  25 extern const unsigned short combining_class_table[] DECLSPEC_HIDDEN;
  26
  27 static BYTE get_combining_class( WCHAR c )
  28 {
  29     return combining_class_table[combining_class_table[combining_class_table[c >> 8] + ((c >> 4) & 0xf)] + (c & 0xf)];
  30 }
  31
  32 static BOOL is_starter( WCHAR c )
  33 {
  34     return !get_combining_class( c );
  35 }
  36
  37 static BOOL reorderable_pair( WCHAR c1, WCHAR c2 )
  38 {
  39     BYTE ccc1, ccc2;
  40
  41     /* reorderable if ccc1 > ccc2 > 0 */
  42     ccc1 = get_combining_class( c1 );
  43     if (ccc1 < 2) return FALSE;
  44     ccc2 = get_combining_class( c2 );
  45     return ccc2 && (ccc1 > ccc2);
  46 }
  47
  48 static void canonical_order_substring( WCHAR *str, unsigned int len )
  49 {
  50     unsigned int i;
  51     BOOL swapped;
  52
  53     do
  54     {
  55         swapped = FALSE;
  56         for (i = 0; i < len - 1; i++)
  57         {
  58             if (reorderable_pair( str[i], str[i + 1] ))
  59             {
  60                 WCHAR tmp = str[i];
  61                 str[i] = str[i + 1];
  62                 str[i + 1] = tmp;
  63                 swapped = TRUE;
  64             }
  65         }
  66     } while (swapped);
  67 }
  68
  69 /****************************************************************************
  70  *             canonical_order_string
  71  *
  72  * Reorder the string into canonical order - D108/D109.
  73  *
  74  * Starters (chars with combining class == 0) don't move, so look for continuous
  75  * substrings of non-starters and only reorder those.
  76  */
  77 static void canonical_order_string( WCHAR *str, unsigned int len )
  78 {
  79     unsigned int i, next = 0;
  80
  81     for (i = 1; i <= len; i++)
  82     {
  83         if (i == len || is_starter( str[i] ))
  84         {
  85             if (i > next + 1) /* at least two successive non-starters */
  86                 canonical_order_substring( str + next, i - next );
  87             next = i + 1;
  88         }
  89     }
  90 }
  91
  92 unsigned int wine_decompose_string( int flags, const WCHAR *src, unsigned int src_len,
  93                                     WCHAR *dst, unsigned int dst_len )
  94 {
  95     unsigned int src_pos, dst_pos = 0, decomp_len;
  96
  97     for (src_pos = 0; src_pos < src_len; src_pos++)
  98     {
  99         if (dst_pos == dst_len) return 0;
 100         decomp_len = wine_decompose( flags, src[src_pos], dst + dst_pos, dst_len - dst_pos );
 101         if (decomp_len == 0) return 0;
 102         dst_pos += decomp_len;
 103     }
 104
 105     if (flags & WINE_DECOMPOSE_REORDER) canonical_order_string( dst, dst_pos );
 106     return dst_pos;
 107 }
 108
 109 static BOOL is_blocked( WCHAR *starter, WCHAR *ptr )
 110 {
 111     if (ptr == starter + 1) return FALSE;
 112     /* Because the string is already canonically ordered, the chars are blocked
 113        only if the previous char's combining class is equal to the test char. */
 114     if (get_combining_class( *(ptr - 1) ) == get_combining_class( *ptr )) return TRUE;
 115     return FALSE;
 116 }
 117
 118 unsigned int wine_compose_string( WCHAR *str, unsigned int len )
 119 {
 120     unsigned int i, last_starter = len;
 121     WCHAR pair[2], comp;
 122
 123     for (i = 0; i < len; i++)
 124     {
 125         pair[1] = str[i];
 126         if (last_starter == len || is_blocked( str + last_starter, str + i ) || !(comp = wine_compose( pair )))
 127         {
 128             if (is_starter( str[i] ))
 129             {
 130                 last_starter = i;
 131                 pair[0] = str[i];
 132             }
 133             continue;
 134         }
 135         str[last_starter] = pair[0] = comp;
 136         len--;
 137         memmove( str + i, str + i + 1, (len - i) * sizeof(WCHAR) );
 138         i = last_starter;
 139     }
 140     return len;
 141 }