| /* decomp.c - Character decomposition. |
| * |
| * Copyright (C) 1999, 2000 Tom Tromey |
| * Copyright 2000 Red Hat, Inc. |
| * |
| * SPDX-License-Identifier: LGPL-2.1-or-later |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public License |
| * along with this library; if not, see <http://www.gnu.org/licenses/>. |
| */ |
| |
| #include "config.h" |
| |
| #include <stdlib.h> |
| |
| #include "gunicode.h" |
| #include "gunidecomp.h" |
| #include "gmem.h" |
| #include "gunicomp.h" |
| #include "gunicodeprivate.h" |
| |
| |
| #define CC_PART1(Page, Char) \ |
| ((combining_class_table_part1[Page] >= G_UNICODE_MAX_TABLE_INDEX) \ |
| ? (combining_class_table_part1[Page] - G_UNICODE_MAX_TABLE_INDEX) \ |
| : (cclass_data[combining_class_table_part1[Page]][Char])) |
| |
| #define CC_PART2(Page, Char) \ |
| ((combining_class_table_part2[Page] >= G_UNICODE_MAX_TABLE_INDEX) \ |
| ? (combining_class_table_part2[Page] - G_UNICODE_MAX_TABLE_INDEX) \ |
| : (cclass_data[combining_class_table_part2[Page]][Char])) |
| |
| #define COMBINING_CLASS(Char) \ |
| (((Char) <= G_UNICODE_LAST_CHAR_PART1) \ |
| ? CC_PART1 ((Char) >> 8, (Char) & 0xff) \ |
| : (((Char) >= 0xe0000 && (Char) <= G_UNICODE_LAST_CHAR) \ |
| ? CC_PART2 (((Char) - 0xe0000) >> 8, (Char) & 0xff) \ |
| : 0)) |
| |
| /** |
| * g_unichar_combining_class: |
| * @uc: a Unicode character |
| * |
| * Determines the canonical combining class of a Unicode character. |
| * |
| * Returns: the combining class of the character |
| * |
| * Since: 2.14 |
| **/ |
| gint |
| g_unichar_combining_class (gunichar uc) |
| { |
| return COMBINING_CLASS (uc); |
| } |
| |
| /* constants for hangul syllable [de]composition */ |
| #define SBase 0xAC00 |
| #define LBase 0x1100 |
| #define VBase 0x1161 |
| #define TBase 0x11A7 |
| #define LCount 19 |
| #define VCount 21 |
| #define TCount 28 |
| #define NCount (VCount * TCount) |
| #define SCount (LCount * NCount) |
| |
| /** |
| * g_unicode_canonical_ordering: |
| * @string: (array length=len) (element-type gunichar): a UCS-4 encoded string. |
| * @len: the maximum length of @string to use. |
| * |
| * Computes the canonical ordering of a string in-place. |
| * This rearranges decomposed characters in the string |
| * according to their combining classes. See the Unicode |
| * manual for more information. |
| **/ |
| void |
| g_unicode_canonical_ordering (gunichar *string, |
| gsize len) |
| { |
| gsize i; |
| int swap = 1; |
| |
| while (swap) |
| { |
| int last; |
| swap = 0; |
| last = COMBINING_CLASS (string[0]); |
| for (i = 0; i < len - 1; ++i) |
| { |
| int next = COMBINING_CLASS (string[i + 1]); |
| if (next != 0 && last > next) |
| { |
| gsize j; |
| /* Percolate item leftward through string. */ |
| for (j = i + 1; j > 0; --j) |
| { |
| gunichar t; |
| if (COMBINING_CLASS (string[j - 1]) <= next) |
| break; |
| t = string[j]; |
| string[j] = string[j - 1]; |
| string[j - 1] = t; |
| swap = 1; |
| } |
| /* We're re-entering the loop looking at the old |
| character again. */ |
| next = last; |
| } |
| last = next; |
| } |
| } |
| } |
| |
| /* http://www.unicode.org/unicode/reports/tr15/#Hangul |
| * r should be null or have sufficient space. Calling with r == NULL will |
| * only calculate the result_len; however, a buffer with space for three |
| * characters will always be big enough. */ |
| static void |
| decompose_hangul (gunichar s, |
| gunichar *r, |
| gsize *result_len) |
| { |
| gint SIndex = s - SBase; |
| gint TIndex = SIndex % TCount; |
| |
| if (r) |
| { |
| r[0] = LBase + SIndex / NCount; |
| r[1] = VBase + (SIndex % NCount) / TCount; |
| } |
| |
| if (TIndex) |
| { |
| if (r) |
| r[2] = TBase + TIndex; |
| *result_len = 3; |
| } |
| else |
| *result_len = 2; |
| } |
| |
| /* returns a pointer to a null-terminated UTF-8 string */ |
| static const gchar * |
| find_decomposition (gunichar ch, |
| gboolean compat) |
| { |
| int start = 0; |
| int end = G_N_ELEMENTS (decomp_table); |
| |
| if (ch >= decomp_table[start].ch && |
| ch <= decomp_table[end - 1].ch) |
| { |
| while (TRUE) |
| { |
| int half = (start + end) / 2; |
| if (ch == decomp_table[half].ch) |
| { |
| int offset; |
| |
| if (compat) |
| { |
| offset = decomp_table[half].compat_offset; |
| if (offset == G_UNICODE_NOT_PRESENT_OFFSET) |
| offset = decomp_table[half].canon_offset; |
| } |
| else |
| { |
| offset = decomp_table[half].canon_offset; |
| if (offset == G_UNICODE_NOT_PRESENT_OFFSET) |
| return NULL; |
| } |
| |
| return &(decomp_expansion_string[offset]); |
| } |
| else if (half == start) |
| break; |
| else if (ch > decomp_table[half].ch) |
| start = half; |
| else |
| end = half; |
| } |
| } |
| |
| return NULL; |
| } |
| |
| /** |
| * g_unicode_canonical_decomposition: |
| * @ch: a Unicode character. |
| * @result_len: location to store the length of the return value. |
| * |
| * Computes the canonical decomposition of a Unicode character. |
| * |
| * Returns: a newly allocated string of Unicode characters. |
| * @result_len is set to the resulting length of the string. |
| * |
| * Deprecated: 2.30: Use the more flexible g_unichar_fully_decompose() |
| * instead. |
| **/ |
| gunichar * |
| g_unicode_canonical_decomposition (gunichar ch, |
| gsize *result_len) |
| { |
| const gchar *decomp; |
| const gchar *p; |
| gunichar *r; |
| |
| /* Hangul syllable */ |
| if (ch >= SBase && ch < SBase + SCount) |
| { |
| decompose_hangul (ch, NULL, result_len); |
| r = g_malloc (*result_len * sizeof (gunichar)); |
| decompose_hangul (ch, r, result_len); |
| } |
| else if ((decomp = find_decomposition (ch, FALSE)) != NULL) |
| { |
| /* Found it. */ |
| int i; |
| |
| *result_len = g_utf8_strlen (decomp, -1); |
| r = g_malloc (*result_len * sizeof (gunichar)); |
| |
| for (p = decomp, i = 0; *p != '\0'; p = g_utf8_next_char (p), i++) |
| r[i] = g_utf8_get_char (p); |
| } |
| else |
| { |
| /* Not in our table. */ |
| r = g_malloc (sizeof (gunichar)); |
| *r = ch; |
| *result_len = 1; |
| } |
| |
| return r; |
| } |
| |
| /* L,V => LV and LV,T => LVT */ |
| static gboolean |
| combine_hangul (gunichar a, |
| gunichar b, |
| gunichar *result) |
| { |
| gint LIndex = a - LBase; |
| gint SIndex = a - SBase; |
| |
| gint VIndex = b - VBase; |
| gint TIndex = b - TBase; |
| |
| if (0 <= LIndex && LIndex < LCount |
| && 0 <= VIndex && VIndex < VCount) |
| { |
| *result = SBase + (LIndex * VCount + VIndex) * TCount; |
| return TRUE; |
| } |
| else if (0 <= SIndex && SIndex < SCount && (SIndex % TCount) == 0 |
| && 0 < TIndex && TIndex < TCount) |
| { |
| *result = a + TIndex; |
| return TRUE; |
| } |
| |
| return FALSE; |
| } |
| |
| #define CI(Page, Char) \ |
| ((compose_table[Page] >= G_UNICODE_MAX_TABLE_INDEX) \ |
| ? (compose_table[Page] - G_UNICODE_MAX_TABLE_INDEX) \ |
| : (compose_data[compose_table[Page]][Char])) |
| |
| #define COMPOSE_INDEX(Char) \ |
| (((Char >> 8) > (COMPOSE_TABLE_LAST)) ? 0 : CI((Char) >> 8, (Char) & 0xff)) |
| |
| static gboolean |
| combine (gunichar a, |
| gunichar b, |
| gunichar *result) |
| { |
| gushort index_a, index_b; |
| |
| if (combine_hangul (a, b, result)) |
| return TRUE; |
| |
| index_a = COMPOSE_INDEX(a); |
| |
| if (index_a >= COMPOSE_FIRST_SINGLE_START && index_a < COMPOSE_SECOND_START) |
| { |
| if (b == compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][0]) |
| { |
| *result = compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][1]; |
| return TRUE; |
| } |
| else |
| return FALSE; |
| } |
| |
| index_b = COMPOSE_INDEX(b); |
| |
| if (index_b >= COMPOSE_SECOND_SINGLE_START) |
| { |
| if (a == compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][0]) |
| { |
| *result = compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][1]; |
| return TRUE; |
| } |
| else |
| return FALSE; |
| } |
| |
| if (index_a >= COMPOSE_FIRST_START && index_a < COMPOSE_FIRST_SINGLE_START && |
| index_b >= COMPOSE_SECOND_START && index_b < COMPOSE_SECOND_SINGLE_START) |
| { |
| gunichar res = compose_array[index_a - COMPOSE_FIRST_START][index_b - COMPOSE_SECOND_START]; |
| |
| if (res) |
| { |
| *result = res; |
| return TRUE; |
| } |
| } |
| |
| return FALSE; |
| } |
| |
| gunichar * |
| _g_utf8_normalize_wc (const gchar *str, |
| gssize max_len, |
| GNormalizeMode mode) |
| { |
| gsize n_wc; |
| gunichar *wc_buffer; |
| const char *p; |
| gsize last_start; |
| gboolean do_compat = (mode == G_NORMALIZE_NFKC || |
| mode == G_NORMALIZE_NFKD); |
| gboolean do_compose = (mode == G_NORMALIZE_NFC || |
| mode == G_NORMALIZE_NFKC); |
| |
| n_wc = 0; |
| p = str; |
| while ((max_len < 0 || p < str + max_len) && *p) |
| { |
| const gchar *decomp; |
| const char *next, *between; |
| gunichar wc; |
| |
| next = g_utf8_next_char (p); |
| /* Avoid reading truncated multibyte characters |
| which run past the end of the buffer */ |
| if (max_len < 0) |
| { |
| /* Does the character contain a NUL terminator? */ |
| for (between = &p[1]; between < next; between++) |
| { |
| if (G_UNLIKELY (!*between)) |
| return NULL; |
| } |
| } |
| else |
| { |
| if (G_UNLIKELY (next > str + max_len)) |
| return NULL; |
| } |
| wc = g_utf8_get_char (p); |
| |
| if (G_UNLIKELY (wc == (gunichar) -1)) |
| { |
| return NULL; |
| } |
| else if (wc >= SBase && wc < SBase + SCount) |
| { |
| gsize result_len; |
| decompose_hangul (wc, NULL, &result_len); |
| n_wc += result_len; |
| } |
| else |
| { |
| decomp = find_decomposition (wc, do_compat); |
| |
| if (decomp) |
| n_wc += g_utf8_strlen (decomp, -1); |
| else |
| n_wc++; |
| } |
| |
| p = next; |
| } |
| |
| wc_buffer = g_new (gunichar, n_wc + 1); |
| |
| last_start = 0; |
| n_wc = 0; |
| p = str; |
| while ((max_len < 0 || p < str + max_len) && *p) |
| { |
| gunichar wc = g_utf8_get_char (p); |
| const gchar *decomp; |
| int cc; |
| gsize old_n_wc = n_wc; |
| |
| if (wc >= SBase && wc < SBase + SCount) |
| { |
| gsize result_len; |
| decompose_hangul (wc, wc_buffer + n_wc, &result_len); |
| n_wc += result_len; |
| } |
| else |
| { |
| decomp = find_decomposition (wc, do_compat); |
| |
| if (decomp) |
| { |
| const char *pd; |
| for (pd = decomp; *pd != '\0'; pd = g_utf8_next_char (pd)) |
| wc_buffer[n_wc++] = g_utf8_get_char (pd); |
| } |
| else |
| wc_buffer[n_wc++] = wc; |
| } |
| |
| if (n_wc > 0) |
| { |
| cc = COMBINING_CLASS (wc_buffer[old_n_wc]); |
| |
| if (cc == 0) |
| { |
| g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start); |
| last_start = old_n_wc; |
| } |
| } |
| |
| p = g_utf8_next_char (p); |
| } |
| |
| if (n_wc > 0) |
| { |
| g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start); |
| last_start = n_wc; |
| (void) last_start; |
| } |
| |
| wc_buffer[n_wc] = 0; |
| |
| /* All decomposed and reordered */ |
| |
| if (do_compose && n_wc > 0) |
| { |
| gsize i, j; |
| int last_cc = 0; |
| last_start = 0; |
| |
| for (i = 0; i < n_wc; i++) |
| { |
| int cc = COMBINING_CLASS (wc_buffer[i]); |
| |
| if (i > 0 && |
| (last_cc == 0 || last_cc < cc) && |
| combine (wc_buffer[last_start], wc_buffer[i], |
| &wc_buffer[last_start])) |
| { |
| for (j = i + 1; j < n_wc; j++) |
| wc_buffer[j-1] = wc_buffer[j]; |
| n_wc--; |
| i--; |
| |
| if (i == last_start) |
| last_cc = 0; |
| else |
| last_cc = COMBINING_CLASS (wc_buffer[i-1]); |
| |
| continue; |
| } |
| |
| if (cc == 0) |
| last_start = i; |
| |
| last_cc = cc; |
| } |
| } |
| |
| wc_buffer[n_wc] = 0; |
| |
| return wc_buffer; |
| } |
| |
| /** |
| * g_utf8_normalize: |
| * @str: a UTF-8 encoded string. |
| * @len: length of @str, in bytes, or -1 if @str is nul-terminated. |
| * @mode: the type of normalization to perform. |
| * |
| * Converts a string into canonical form, standardizing |
| * such issues as whether a character with an accent |
| * is represented as a base character and combining |
| * accent or as a single precomposed character. The |
| * string has to be valid UTF-8, otherwise %NULL is |
| * returned. You should generally call g_utf8_normalize() |
| * before comparing two Unicode strings. |
| * |
| * The normalization mode %G_NORMALIZE_DEFAULT only |
| * standardizes differences that do not affect the |
| * text content, such as the above-mentioned accent |
| * representation. %G_NORMALIZE_ALL also standardizes |
| * the "compatibility" characters in Unicode, such |
| * as SUPERSCRIPT THREE to the standard forms |
| * (in this case DIGIT THREE). Formatting information |
| * may be lost but for most text operations such |
| * characters should be considered the same. |
| * |
| * %G_NORMALIZE_DEFAULT_COMPOSE and %G_NORMALIZE_ALL_COMPOSE |
| * are like %G_NORMALIZE_DEFAULT and %G_NORMALIZE_ALL, |
| * but returned a result with composed forms rather |
| * than a maximally decomposed form. This is often |
| * useful if you intend to convert the string to |
| * a legacy encoding or pass it to a system with |
| * less capable Unicode handling. |
| * |
| * Returns: (nullable): a newly allocated string, that |
| * is the normalized form of @str, or %NULL if @str |
| * is not valid UTF-8. |
| **/ |
| gchar * |
| g_utf8_normalize (const gchar *str, |
| gssize len, |
| GNormalizeMode mode) |
| { |
| gunichar *result_wc = _g_utf8_normalize_wc (str, len, mode); |
| gchar *result = NULL; |
| |
| if (G_LIKELY (result_wc != NULL)) |
| { |
| result = g_ucs4_to_utf8 (result_wc, -1, NULL, NULL, NULL); |
| g_free (result_wc); |
| } |
| |
| return result; |
| } |
| |
| static gboolean |
| decompose_hangul_step (gunichar ch, |
| gunichar *a, |
| gunichar *b) |
| { |
| gint SIndex, TIndex; |
| |
| if (ch < SBase || ch >= SBase + SCount) |
| return FALSE; /* not a hangul syllable */ |
| |
| SIndex = ch - SBase; |
| TIndex = SIndex % TCount; |
| |
| if (TIndex) |
| { |
| /* split LVT -> LV,T */ |
| *a = ch - TIndex; |
| *b = TBase + TIndex; |
| } |
| else |
| { |
| /* split LV -> L,V */ |
| *a = LBase + SIndex / NCount; |
| *b = VBase + (SIndex % NCount) / TCount; |
| } |
| |
| return TRUE; |
| } |
| |
| /** |
| * g_unichar_decompose: |
| * @ch: a Unicode character |
| * @a: (out) (not optional): return location for the first component of @ch |
| * @b: (out) (not optional): return location for the second component of @ch |
| * |
| * Performs a single decomposition step of the |
| * Unicode canonical decomposition algorithm. |
| * |
| * This function does not include compatibility |
| * decompositions. It does, however, include algorithmic |
| * Hangul Jamo decomposition, as well as 'singleton' |
| * decompositions which replace a character by a single |
| * other character. In the case of singletons *@b will |
| * be set to zero. |
| * |
| * If @ch is not decomposable, *@a is set to @ch and *@b |
| * is set to zero. |
| * |
| * Note that the way Unicode decomposition pairs are |
| * defined, it is guaranteed that @b would not decompose |
| * further, but @a may itself decompose. To get the full |
| * canonical decomposition for @ch, one would need to |
| * recursively call this function on @a. Or use |
| * g_unichar_fully_decompose(). |
| * |
| * See |
| * [UAX#15](http://unicode.org/reports/tr15/) |
| * for details. |
| * |
| * Returns: %TRUE if the character could be decomposed |
| * |
| * Since: 2.30 |
| */ |
| gboolean |
| g_unichar_decompose (gunichar ch, |
| gunichar *a, |
| gunichar *b) |
| { |
| gint start = 0; |
| gint end = G_N_ELEMENTS (decomp_step_table); |
| |
| if (decompose_hangul_step (ch, a, b)) |
| return TRUE; |
| |
| /* TODO use bsearch() */ |
| if (ch >= decomp_step_table[start].ch && |
| ch <= decomp_step_table[end - 1].ch) |
| { |
| while (TRUE) |
| { |
| gint half = (start + end) / 2; |
| const decomposition_step *p = &(decomp_step_table[half]); |
| if (ch == p->ch) |
| { |
| *a = p->a; |
| *b = p->b; |
| return TRUE; |
| } |
| else if (half == start) |
| break; |
| else if (ch > p->ch) |
| start = half; |
| else |
| end = half; |
| } |
| } |
| |
| *a = ch; |
| *b = 0; |
| |
| return FALSE; |
| } |
| |
| /** |
| * g_unichar_compose: |
| * @a: a Unicode character |
| * @b: a Unicode character |
| * @ch: (out) (not optional): return location for the composed character |
| * |
| * Performs a single composition step of the |
| * Unicode canonical composition algorithm. |
| * |
| * This function includes algorithmic Hangul Jamo composition, |
| * but it is not exactly the inverse of g_unichar_decompose(). |
| * No composition can have either of @a or @b equal to zero. |
| * To be precise, this function composes if and only if |
| * there exists a Primary Composite P which is canonically |
| * equivalent to the sequence <@a,@b>. See the Unicode |
| * Standard for the definition of Primary Composite. |
| * |
| * If @a and @b do not compose a new character, @ch is set to zero. |
| * |
| * See |
| * [UAX#15](http://unicode.org/reports/tr15/) |
| * for details. |
| * |
| * Returns: %TRUE if the characters could be composed |
| * |
| * Since: 2.30 |
| */ |
| gboolean |
| g_unichar_compose (gunichar a, |
| gunichar b, |
| gunichar *ch) |
| { |
| if (combine (a, b, ch)) |
| return TRUE; |
| |
| *ch = 0; |
| return FALSE; |
| } |
| |
| /** |
| * g_unichar_fully_decompose: |
| * @ch: a Unicode character. |
| * @compat: whether perform canonical or compatibility decomposition |
| * @result: (optional) (out caller-allocates): location to store decomposed result, or %NULL |
| * @result_len: length of @result |
| * |
| * Computes the canonical or compatibility decomposition of a |
| * Unicode character. For compatibility decomposition, |
| * pass %TRUE for @compat; for canonical decomposition |
| * pass %FALSE for @compat. |
| * |
| * The decomposed sequence is placed in @result. Only up to |
| * @result_len characters are written into @result. The length |
| * of the full decomposition (irrespective of @result_len) is |
| * returned by the function. For canonical decomposition, |
| * currently all decompositions are of length at most 4, but |
| * this may change in the future (very unlikely though). |
| * At any rate, Unicode does guarantee that a buffer of length |
| * 18 is always enough for both compatibility and canonical |
| * decompositions, so that is the size recommended. This is provided |
| * as %G_UNICHAR_MAX_DECOMPOSITION_LENGTH. |
| * |
| * See |
| * [UAX#15](http://unicode.org/reports/tr15/) |
| * for details. |
| * |
| * Returns: the length of the full decomposition. |
| * |
| * Since: 2.30 |
| **/ |
| gsize |
| g_unichar_fully_decompose (gunichar ch, |
| gboolean compat, |
| gunichar *result, |
| gsize result_len) |
| { |
| const gchar *decomp; |
| const gchar *p; |
| |
| /* Hangul syllable */ |
| if (ch >= SBase && ch < SBase + SCount) |
| { |
| gsize len, i; |
| gunichar buffer[3]; |
| decompose_hangul (ch, result ? buffer : NULL, &len); |
| if (result) |
| for (i = 0; i < len && i < result_len; i++) |
| result[i] = buffer[i]; |
| return len; |
| } |
| else if ((decomp = find_decomposition (ch, compat)) != NULL) |
| { |
| /* Found it. */ |
| gsize len, i; |
| |
| len = g_utf8_strlen (decomp, -1); |
| |
| for (p = decomp, i = 0; i < len && i < result_len; p = g_utf8_next_char (p), i++) |
| result[i] = g_utf8_get_char (p); |
| |
| return len; |
| } |
| |
| /* Does not decompose */ |
| if (result && result_len >= 1) |
| *result = ch; |
| return 1; |
| } |