/src/libunistring/lib/uninorm/u-normalize-internal.h

Source
/* Decomposition and composition of Unicode strings.
   Copyright (C) 2009-2026 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 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 <https://www.gnu.org/licenses/>.  */

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 allocated;
  if (resultbuf == NULL)
    {
      result = NULL;
      allocated = 0;
    }
  else
    {
      result = resultbuf;
      allocated = *lengthp;
    }
  size_t length = 0;

  /* 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 */
    sortbuf_preallocated;
  size_t sortbuf_allocated = SORTBUF_PREALLOCATED;
  size_t sortbuf_count = 0;

  {
    const UNIT *s_end = s + n;

    for (;;)
      {
        int count;
        ucs4_t decomposed[UC_DECOMPOSITION_MAX_LENGTH];
        int decomposed_count;

        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.  */
            for (int 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)
                      {
                        decomposed_count += shift;
                        if (decomposed_count > UC_DECOMPOSITION_MAX_LENGTH)
                          abort ();
                        for (int 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;
          }

        int 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)
              {
                /* 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 (size_t 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)
                                  {
                                    sortbuf[0].code = combined;
                                    /* sortbuf[0].ccc = 0, still valid.  */
                                    for (size_t 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 (size_t 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)
              {
                sortbuf_allocated = 2 * sortbuf_allocated;
                if (sortbuf_allocated < sortbuf_count) /* integer overflow? */
                  abort ();
                struct ucs4_with_ccc *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 = (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;
}

Coverage Report

Created: 2026-03-31 07:46

Line	Count	Source
1		/* Decomposition and composition of Unicode strings.
2		Copyright (C) 2009-2026 Free Software Foundation, Inc.
3		Written by Bruno Haible <bruno@clisp.org>, 2009.
4
5		This file is free software: you can redistribute it and/or modify
6		it under the terms of the GNU Lesser General Public License as
7		published by the Free Software Foundation; either version 2.1 of the
8		License, or (at your option) any later version.
9
10		This file is distributed in the hope that it will be useful,
11		but WITHOUT ANY WARRANTY; without even the implied warranty of
12		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13		GNU Lesser General Public License for more details.
14
15		You should have received a copy of the GNU Lesser General Public License
16		along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18		UNIT *
19		FUNC (uninorm_t nf, const UNIT *s, size_t n,
20		UNIT resultbuf, size_t lengthp)
21	0	{
22	0	int (decomposer) (ucs4_t uc, ucs4_t decomposition) = nf->decomposer;
23	0	ucs4_t (*composer) (ucs4_t uc1, ucs4_t uc2) = nf->composer;
24
25		/* The result being accumulated. */
26	0	UNIT *result;
27	0	size_t allocated;
28	0	if (resultbuf == NULL)
29	0	{
30	0	result = NULL;
31	0	allocated = 0;
32	0	}
33	0	else
34	0	{
35	0	result = resultbuf;
36	0	allocated = *lengthp;
37	0	}
38	0	size_t length = 0;
39
40		/* The buffer for sorting. */
41	0	#define SORTBUF_PREALLOCATED 64
42	0	struct ucs4_with_ccc sortbuf_preallocated[2 * SORTBUF_PREALLOCATED];
43	0	struct ucs4_with_ccc sortbuf = / array of size 2 * sortbuf_allocated */
44	0	sortbuf_preallocated;
45	0	size_t sortbuf_allocated = SORTBUF_PREALLOCATED;
46	0	size_t sortbuf_count = 0;
47
48	0	{
49	0	const UNIT *s_end = s + n;
50
51	0	for (;;)
52	0	{
53	0	int count;
54	0	ucs4_t decomposed[UC_DECOMPOSITION_MAX_LENGTH];
55	0	int decomposed_count;
56
57	0	if (s < s_end)
58	0	{
59		/* Fetch the next character. */
60	0	count = U_MBTOUC_UNSAFE (&decomposed[0], s, s_end - s);
61	0	decomposed_count = 1;
62
63		/* Decompose it, recursively.
64		It would be possible to precompute the recursive decomposition
65		and store it in a table. But this would significantly increase
66		the size of the decomposition tables, because for example for
67		U+1FC1 the recursive canonical decomposition and the recursive
68		compatibility decomposition are different. */
69	0	for (int curr = 0; curr < decomposed_count; )
70	0	{
71		/* Invariant: decomposed[0..curr-1] is fully decomposed, i.e.
72		all elements are atomic. */
73	0	ucs4_t curr_decomposed[UC_DECOMPOSITION_MAX_LENGTH];
74	0	int curr_decomposed_count;
75
76	0	curr_decomposed_count = decomposer (decomposed[curr], curr_decomposed);
77	0	if (curr_decomposed_count >= 0)
78	0	{
79		/* Move curr_decomposed[0..curr_decomposed_count-1] over
80		decomposed[curr], making room. It's not worth using
81		memcpy() here, since the counts are so small. */
82	0	int shift = curr_decomposed_count - 1;
83
84	0	if (shift < 0)
85	0	abort ();
86	0	if (shift > 0)
87	0	{
88	0	decomposed_count += shift;
89	0	if (decomposed_count > UC_DECOMPOSITION_MAX_LENGTH)
90	0	abort ();
91	0	for (int j = decomposed_count - 1 - shift; j > curr; j--)
92	0	decomposed[j + shift] = decomposed[j];
93	0	}
94	0	for (; shift >= 0; shift--)
95	0	decomposed[curr + shift] = curr_decomposed[shift];
96	0	}
97	0	else
98	0	{
99		/* decomposed[curr] is atomic. */
100	0	curr++;
101	0	}
102	0	}
103	0	}
104	0	else
105	0	{
106	0	count = 0;
107	0	decomposed_count = 0;
108	0	}
109
110	0	int i = 0;
111	0	for (;;)
112	0	{
113	0	ucs4_t uc;
114	0	int ccc;
115
116	0	if (s < s_end)
117	0	{
118		/* Fetch the next character from the decomposition. */
119	0	if (i == decomposed_count)
120	0	break;
121	0	uc = decomposed[i];
122	0	ccc = uc_combining_class (uc);
123	0	}
124	0	else
125	0	{
126		/* End of string reached. */
127	0	uc = 0;
128	0	ccc = 0;
129	0	}
130
131	0	if (ccc == 0)
132	0	{
133		/* Apply the canonical ordering algorithm to the accumulated
134		sequence of characters. */
135	0	if (sortbuf_count > 1)
136	0	gl_uninorm_decompose_merge_sort_inplace (sortbuf, sortbuf_count,
137	0	sortbuf + sortbuf_count);
138
139	0	if (composer != NULL)
140	0	{
141		/* Attempt to combine decomposed characters, as specified
142		in the Unicode Standard Annex #15 "Unicode Normalization
143		Forms". We need to check
144		1. whether the first accumulated character is a
145		"starter" (i.e. has ccc = 0). This is usually the
146		case. But when the string starts with a
147		non-starter, the sortbuf also starts with a
148		non-starter. Btw, this check could also be
149		omitted, because the composition table has only
150		entries (code1, code2) for which code1 is a
151		starter; if the first accumulated character is not
152		a starter, no lookup will succeed.
153		2. If the sortbuf has more than one character, check
154		for each of these characters that are not "blocked"
155		from the starter (i.e. have a ccc that is higher
156		than the ccc of the previous character) whether it
157		can be combined with the first character.
158		3. If only one character is left in sortbuf, check
159		whether it can be combined with the next character
160		(also a starter). */
161	0	if (sortbuf_count > 0 && sortbuf[0].ccc == 0)
162	0	{
163	0	for (size_t j = 1; j < sortbuf_count; )
164	0	{
165	0	if (sortbuf[j].ccc > sortbuf[j - 1].ccc)
166	0	{
167	0	ucs4_t combined =
168	0	composer (sortbuf[0].code, sortbuf[j].code);
169	0	if (combined)
170	0	{
171	0	sortbuf[0].code = combined;
172		/* sortbuf[0].ccc = 0, still valid. */
173	0	for (size_t k = j + 1; k < sortbuf_count; k++)
174	0	sortbuf[k - 1] = sortbuf[k];
175	0	sortbuf_count--;
176	0	continue;
177	0	}
178	0	}
179	0	j++;
180	0	}
181	0	if (s < s_end && sortbuf_count == 1)
182	0	{
183	0	ucs4_t combined =
184	0	composer (sortbuf[0].code, uc);
185	0	if (combined)
186	0	{
187	0	uc = combined;
188	0	ccc = 0;
189		/* uc could be further combined with subsequent
190		characters. So don't put it into sortbuf[0] in
191		this round, only in the next round. */
192	0	sortbuf_count = 0;
193	0	}
194	0	}
195	0	}
196	0	}
197
198	0	for (size_t j = 0; j < sortbuf_count; j++)
199	0	{
200	0	ucs4_t muc = sortbuf[j].code;
201
202		/* Append muc to the result accumulator. */
203	0	if (length < allocated)
204	0	{
205	0	int ret =
206	0	U_UCTOMB (result + length, muc, allocated - length);
207	0	if (ret == -1)
208	0	{
209	0	errno = EINVAL;
210	0	goto fail;
211	0	}
212	0	if (ret >= 0)
213	0	{
214	0	length += ret;
215	0	goto done_appending;
216	0	}
217	0	}
218	0	{
219	0	size_t old_allocated = allocated;
220	0	size_t new_allocated = 2 * old_allocated;
221	0	if (new_allocated < 64)
222	0	new_allocated = 64;
223	0	if (new_allocated < old_allocated) /* integer overflow? */
224	0	abort ();
225	0	{
226	0	UNIT *larger_result;
227	0	if (result == NULL)
228	0	{
229	0	larger_result =
230	0	(UNIT ) malloc (new_allocated sizeof (UNIT));
231	0	if (larger_result == NULL)
232	0	{
233	0	errno = ENOMEM;
234	0	goto fail;
235	0	}
236	0	}
237	0	else if (result == resultbuf)
238	0	{
239	0	larger_result =
240	0	(UNIT ) malloc (new_allocated sizeof (UNIT));
241	0	if (larger_result == NULL)
242	0	{
243	0	errno = ENOMEM;
244	0	goto fail;
245	0	}
246	0	U_CPY (larger_result, resultbuf, length);
247	0	}
248	0	else
249	0	{
250	0	larger_result =
251	0	(UNIT ) realloc (result, new_allocated sizeof (UNIT));
252	0	if (larger_result == NULL)
253	0	{
254	0	errno = ENOMEM;
255	0	goto fail;
256	0	}
257	0	}
258	0	result = larger_result;
259	0	allocated = new_allocated;
260	0	{
261	0	int ret =
262	0	U_UCTOMB (result + length, muc, allocated - length);
263	0	if (ret == -1)
264	0	{
265	0	errno = EINVAL;
266	0	goto fail;
267	0	}
268	0	if (ret < 0)
269	0	abort ();
270	0	length += ret;
271	0	goto done_appending;
272	0	}
273	0	}
274	0	}
275	0	done_appending: ;
276	0	}
277
278		/* sortbuf is now empty. */
279	0	sortbuf_count = 0;
280	0	}
281
282	0	if (!(s < s_end))
283		/* End of string reached. */
284	0	break;
285
286		/* Append (uc, ccc) to sortbuf. */
287	0	if (sortbuf_count == sortbuf_allocated)
288	0	{
289	0	sortbuf_allocated = 2 * sortbuf_allocated;
290	0	if (sortbuf_allocated < sortbuf_count) /* integer overflow? */
291	0	abort ();
292	0	struct ucs4_with_ccc *new_sortbuf =
293	0	(struct ucs4_with_ccc ) malloc (2 sortbuf_allocated * sizeof (struct ucs4_with_ccc));
294	0	if (new_sortbuf == NULL)
295	0	{
296	0	errno = ENOMEM;
297	0	goto fail;
298	0	}
299	0	memcpy (new_sortbuf, sortbuf,
300	0	sortbuf_count * sizeof (struct ucs4_with_ccc));
301	0	if (sortbuf != sortbuf_preallocated)
302	0	free (sortbuf);
303	0	sortbuf = new_sortbuf;
304	0	}
305	0	sortbuf[sortbuf_count].code = uc;
306	0	sortbuf[sortbuf_count].ccc = ccc;
307	0	sortbuf_count++;
308
309	0	i++;
310	0	}
311
312	0	if (!(s < s_end))
313		/* End of string reached. */
314	0	break;
315
316	0	s += count;
317	0	}
318	0	}
319
320	0	if (length == 0)
321	0	{
322	0	if (result == NULL)
323	0	{
324		/* Return a non-NULL value. NULL means error. */
325	0	result = (UNIT *) malloc (1);
326	0	if (result == NULL)
327	0	{
328	0	errno = ENOMEM;
329	0	goto fail;
330	0	}
331	0	}
332	0	}
333	0	else if (result != resultbuf && length < allocated)
334	0	{
335		/* Shrink the allocated memory if possible. */
336	0	UNIT memory = (UNIT ) realloc (result, length * sizeof (UNIT));
337	0	if (memory != NULL)
338	0	result = memory;
339	0	}
340
341	0	if (sortbuf_count > 0)
342	0	abort ();
343	0	if (sortbuf != sortbuf_preallocated)
344	0	free (sortbuf);
345
346	0	*lengthp = length;
347	0	return result;
348
349	0	fail:
350	0	{
351	0	int saved_errno = errno;
352	0	if (sortbuf != sortbuf_preallocated)
353	0	free (sortbuf);
354	0	if (result != resultbuf)
355	0	free (result);
356	0	errno = saved_errno;
357	0	}
358		return NULL;
359	0	}