From 252601302d45036817546c533743e5918b6b86e8 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 5 May 2024 19:38:31 +0200 Subject: Adding upstream version 1.21.3. Signed-off-by: Daniel Baumann --- lib/uninorm/decompose-internal.c | 29 +++ lib/uninorm/decompose-internal.h | 36 ++++ lib/uninorm/normalize-internal.h | 35 ++++ lib/uninorm/u-normalize-internal.h | 380 +++++++++++++++++++++++++++++++++++++ lib/uninorm/u8-normalize.c | 46 +++++ 5 files changed, 526 insertions(+) create mode 100644 lib/uninorm/decompose-internal.c create mode 100644 lib/uninorm/decompose-internal.h create mode 100644 lib/uninorm/normalize-internal.h create mode 100644 lib/uninorm/u-normalize-internal.h create mode 100644 lib/uninorm/u8-normalize.c (limited to 'lib/uninorm') diff --git a/lib/uninorm/decompose-internal.c b/lib/uninorm/decompose-internal.c new file mode 100644 index 0000000..1ed8235 --- /dev/null +++ b/lib/uninorm/decompose-internal.c @@ -0,0 +1,29 @@ +/* Decomposition of Unicode strings. + Copyright (C) 2009-2022 Free Software Foundation, Inc. + Written by Bruno Haible , 2009. + + This file 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 file 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 program. If not, see . */ + +#include + +/* Specification. */ +#include "decompose-internal.h" + +#define ELEMENT struct ucs4_with_ccc +#define COMPARE(a,b) ((a)->ccc - (b)->ccc) +#define STATIC +#define STATIC_FROMTO static +#define merge_sort_fromto gl_uninorm_decompose_merge_sort_fromto +#define merge_sort_inplace gl_uninorm_decompose_merge_sort_inplace +#include "array-mergesort.h" diff --git a/lib/uninorm/decompose-internal.h b/lib/uninorm/decompose-internal.h new file mode 100644 index 0000000..15d8250 --- /dev/null +++ b/lib/uninorm/decompose-internal.h @@ -0,0 +1,36 @@ +/* Decomposition of Unicode strings. + Copyright (C) 2009-2022 Free Software Foundation, Inc. + Written by Bruno Haible , 2009. + + This file 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 file 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 program. If not, see . */ + +#include + +#include "unitypes.h" + +/* Variant of uc_decomposition that does not produce the 'tag'. */ +extern int + uc_compat_decomposition (ucs4_t uc, ucs4_t *decomposition); + +/* A Unicode character together with its canonical combining class. */ +struct ucs4_with_ccc +{ + ucs4_t code; + int ccc; /* range 0..255 */ +}; + +/* Stable-sort an array of 'struct ucs4_with_ccc'. */ +extern void + gl_uninorm_decompose_merge_sort_inplace (struct ucs4_with_ccc *src, size_t n, + struct ucs4_with_ccc *tmp); diff --git a/lib/uninorm/normalize-internal.h b/lib/uninorm/normalize-internal.h new file mode 100644 index 0000000..aae6dbd --- /dev/null +++ b/lib/uninorm/normalize-internal.h @@ -0,0 +1,35 @@ +/* Normalization of Unicode strings. + Copyright (C) 2009-2022 Free Software Foundation, Inc. + Written by Bruno Haible , 2009. + + This file 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 file 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 program. If not, see . */ + +#include "unitypes.h" + +/* Complete definition of normalization form descriptor. */ +struct unicode_normalization_form +{ + /* Bit mask containing meta-information. + This must be the first field. */ + unsigned int description; + #define NF_IS_COMPAT_DECOMPOSING (1 << 0) + #define NF_IS_COMPOSING (1 << 1) + /* Function that decomposes a Unicode character. */ + int (*decomposer) (ucs4_t uc, ucs4_t *decomposition); + /* Function that combines two Unicode characters, a starter and another + character. */ + ucs4_t (*composer) (ucs4_t uc1, ucs4_t uc2); + /* Decomposing variant. */ + const struct unicode_normalization_form *decomposing_variant; +}; diff --git a/lib/uninorm/u-normalize-internal.h b/lib/uninorm/u-normalize-internal.h new file mode 100644 index 0000000..f0d9c6e --- /dev/null +++ b/lib/uninorm/u-normalize-internal.h @@ -0,0 +1,380 @@ +/* Decomposition and composition of Unicode strings. + Copyright (C) 2009-2022 Free Software Foundation, Inc. + Written by Bruno Haible , 2009. + + This file 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 file 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 program. If not, see . */ + +UNIT * +FUNC (uninorm_t nf, const UNIT *s, size_t n, + UNIT *resultbuf, size_t *lengthp) +{ + int (*decomposer) (ucs4_t uc, ucs4_t *decomposition) = nf->decomposer; + ucs4_t (*composer) (ucs4_t uc1, ucs4_t uc2) = nf->composer; + + /* The result being accumulated. */ + UNIT *result; + size_t length; + size_t allocated; + /* The buffer for sorting. */ + #define SORTBUF_PREALLOCATED 64 + struct ucs4_with_ccc sortbuf_preallocated[2 * SORTBUF_PREALLOCATED]; + struct ucs4_with_ccc *sortbuf; /* array of size 2 * sortbuf_allocated */ + size_t sortbuf_allocated; + size_t sortbuf_count; + + /* Initialize the accumulator. */ + if (resultbuf == NULL) + { + result = NULL; + allocated = 0; + } + else + { + result = resultbuf; + allocated = *lengthp; + } + length = 0; + + /* Initialize the buffer for sorting. */ + sortbuf = sortbuf_preallocated; + sortbuf_allocated = SORTBUF_PREALLOCATED; + sortbuf_count = 0; + + { + const UNIT *s_end = s + n; + + for (;;) + { + int count; + ucs4_t decomposed[UC_DECOMPOSITION_MAX_LENGTH]; + int decomposed_count; + int i; + + if (s < s_end) + { + /* Fetch the next character. */ + count = U_MBTOUC_UNSAFE (&decomposed[0], s, s_end - s); + decomposed_count = 1; + + /* Decompose it, recursively. + It would be possible to precompute the recursive decomposition + and store it in a table. But this would significantly increase + the size of the decomposition tables, because for example for + U+1FC1 the recursive canonical decomposition and the recursive + compatibility decomposition are different. */ + { + int curr; + + for (curr = 0; curr < decomposed_count; ) + { + /* Invariant: decomposed[0..curr-1] is fully decomposed, i.e. + all elements are atomic. */ + ucs4_t curr_decomposed[UC_DECOMPOSITION_MAX_LENGTH]; + int curr_decomposed_count; + + curr_decomposed_count = decomposer (decomposed[curr], curr_decomposed); + if (curr_decomposed_count >= 0) + { + /* Move curr_decomposed[0..curr_decomposed_count-1] over + decomposed[curr], making room. It's not worth using + memcpy() here, since the counts are so small. */ + int shift = curr_decomposed_count - 1; + + if (shift < 0) + abort (); + if (shift > 0) + { + int j; + + decomposed_count += shift; + if (decomposed_count > UC_DECOMPOSITION_MAX_LENGTH) + abort (); + for (j = decomposed_count - 1 - shift; j > curr; j--) + decomposed[j + shift] = decomposed[j]; + } + for (; shift >= 0; shift--) + decomposed[curr + shift] = curr_decomposed[shift]; + } + else + { + /* decomposed[curr] is atomic. */ + curr++; + } + } + } + } + else + { + count = 0; + decomposed_count = 0; + } + + i = 0; + for (;;) + { + ucs4_t uc; + int ccc; + + if (s < s_end) + { + /* Fetch the next character from the decomposition. */ + if (i == decomposed_count) + break; + uc = decomposed[i]; + ccc = uc_combining_class (uc); + } + else + { + /* End of string reached. */ + uc = 0; + ccc = 0; + } + + if (ccc == 0) + { + size_t j; + + /* Apply the canonical ordering algorithm to the accumulated + sequence of characters. */ + if (sortbuf_count > 1) + gl_uninorm_decompose_merge_sort_inplace (sortbuf, sortbuf_count, + sortbuf + sortbuf_count); + + if (composer != NULL) + { + /* Attempt to combine decomposed characters, as specified + in the Unicode Standard Annex #15 "Unicode Normalization + Forms". We need to check + 1. whether the first accumulated character is a + "starter" (i.e. has ccc = 0). This is usually the + case. But when the string starts with a + non-starter, the sortbuf also starts with a + non-starter. Btw, this check could also be + omitted, because the composition table has only + entries (code1, code2) for which code1 is a + starter; if the first accumulated character is not + a starter, no lookup will succeed. + 2. If the sortbuf has more than one character, check + for each of these characters that are not "blocked" + from the starter (i.e. have a ccc that is higher + than the ccc of the previous character) whether it + can be combined with the first character. + 3. If only one character is left in sortbuf, check + whether it can be combined with the next character + (also a starter). */ + if (sortbuf_count > 0 && sortbuf[0].ccc == 0) + { + for (j = 1; j < sortbuf_count; ) + { + if (sortbuf[j].ccc > sortbuf[j - 1].ccc) + { + ucs4_t combined = + composer (sortbuf[0].code, sortbuf[j].code); + if (combined) + { + size_t k; + + sortbuf[0].code = combined; + /* sortbuf[0].ccc = 0, still valid. */ + for (k = j + 1; k < sortbuf_count; k++) + sortbuf[k - 1] = sortbuf[k]; + sortbuf_count--; + continue; + } + } + j++; + } + if (s < s_end && sortbuf_count == 1) + { + ucs4_t combined = + composer (sortbuf[0].code, uc); + if (combined) + { + uc = combined; + ccc = 0; + /* uc could be further combined with subsequent + characters. So don't put it into sortbuf[0] in + this round, only in the next round. */ + sortbuf_count = 0; + } + } + } + } + + for (j = 0; j < sortbuf_count; j++) + { + ucs4_t muc = sortbuf[j].code; + + /* Append muc to the result accumulator. */ + if (length < allocated) + { + int ret = + U_UCTOMB (result + length, muc, allocated - length); + if (ret == -1) + { + errno = EINVAL; + goto fail; + } + if (ret >= 0) + { + length += ret; + goto done_appending; + } + } + { + size_t old_allocated = allocated; + size_t new_allocated = 2 * old_allocated; + if (new_allocated < 64) + new_allocated = 64; + if (new_allocated < old_allocated) /* integer overflow? */ + abort (); + { + UNIT *larger_result; + if (result == NULL) + { + larger_result = + (UNIT *) malloc (new_allocated * sizeof (UNIT)); + if (larger_result == NULL) + { + errno = ENOMEM; + goto fail; + } + } + else if (result == resultbuf) + { + larger_result = + (UNIT *) malloc (new_allocated * sizeof (UNIT)); + if (larger_result == NULL) + { + errno = ENOMEM; + goto fail; + } + U_CPY (larger_result, resultbuf, length); + } + else + { + larger_result = + (UNIT *) realloc (result, new_allocated * sizeof (UNIT)); + if (larger_result == NULL) + { + errno = ENOMEM; + goto fail; + } + } + result = larger_result; + allocated = new_allocated; + { + int ret = + U_UCTOMB (result + length, muc, allocated - length); + if (ret == -1) + { + errno = EINVAL; + goto fail; + } + if (ret < 0) + abort (); + length += ret; + goto done_appending; + } + } + } + done_appending: ; + } + + /* sortbuf is now empty. */ + sortbuf_count = 0; + } + + if (!(s < s_end)) + /* End of string reached. */ + break; + + /* Append (uc, ccc) to sortbuf. */ + if (sortbuf_count == sortbuf_allocated) + { + struct ucs4_with_ccc *new_sortbuf; + + sortbuf_allocated = 2 * sortbuf_allocated; + if (sortbuf_allocated < sortbuf_count) /* integer overflow? */ + abort (); + new_sortbuf = + (struct ucs4_with_ccc *) malloc (2 * sortbuf_allocated * sizeof (struct ucs4_with_ccc)); + if (new_sortbuf == NULL) + { + errno = ENOMEM; + goto fail; + } + memcpy (new_sortbuf, sortbuf, + sortbuf_count * sizeof (struct ucs4_with_ccc)); + if (sortbuf != sortbuf_preallocated) + free (sortbuf); + sortbuf = new_sortbuf; + } + sortbuf[sortbuf_count].code = uc; + sortbuf[sortbuf_count].ccc = ccc; + sortbuf_count++; + + i++; + } + + if (!(s < s_end)) + /* End of string reached. */ + break; + + s += count; + } + } + + if (length == 0) + { + if (result == NULL) + { + /* Return a non-NULL value. NULL means error. */ + result = (UNIT *) malloc (1); + if (result == NULL) + { + errno = ENOMEM; + goto fail; + } + } + } + else if (result != resultbuf && length < allocated) + { + /* Shrink the allocated memory if possible. */ + UNIT *memory; + + memory = (UNIT *) realloc (result, length * sizeof (UNIT)); + if (memory != NULL) + result = memory; + } + + if (sortbuf_count > 0) + abort (); + if (sortbuf != sortbuf_preallocated) + free (sortbuf); + + *lengthp = length; + return result; + + fail: + { + int saved_errno = errno; + if (sortbuf != sortbuf_preallocated) + free (sortbuf); + if (result != resultbuf) + free (result); + errno = saved_errno; + } + return NULL; +} diff --git a/lib/uninorm/u8-normalize.c b/lib/uninorm/u8-normalize.c new file mode 100644 index 0000000..fe40d11 --- /dev/null +++ b/lib/uninorm/u8-normalize.c @@ -0,0 +1,46 @@ +/* Normalization of UTF-8 strings. + Copyright (C) 2009-2022 Free Software Foundation, Inc. + Written by Bruno Haible , 2009. + + This file is free software. + It is dual-licensed under "the GNU LGPLv3+ or the GNU GPLv2+". + You can redistribute it and/or modify it under either + - the terms of the GNU Lesser General Public License as published + by the Free Software Foundation, either version 3, or (at your + option) any later version, or + - the terms of the GNU General Public License as published by the + Free Software Foundation; either version 2, or (at your option) + any later version, or + - the same dual license "the GNU LGPLv3+ or the GNU GPLv2+". + + This file 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 and the GNU General Public License + for more details. + + You should have received a copy of the GNU Lesser General Public + License and of the GNU General Public License along with this + program. If not, see . */ + +#include + +/* Specification. */ +#include "uninorm.h" + +#include +#include +#include +#include + +#include "unistr.h" +#include "unictype.h" +#include "normalize-internal.h" +#include "uninorm/decompose-internal.h" + +#define FUNC u8_normalize +#define UNIT uint8_t +#define U_MBTOUC_UNSAFE u8_mbtouc_unsafe +#define U_UCTOMB u8_uctomb +#define U_CPY u8_cpy +#include "u-normalize-internal.h" -- cgit v1.2.3