summaryrefslogtreecommitdiff
path: root/lib/uninorm/u-normalize-internal.h
blob: 70c325513e931f07bb2a1acf8a0485e758763ba8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
/* Decomposition and composition of Unicode strings.
   Copyright (C) 2009 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 2009.

   This program 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 3 of the License, or
   (at your option) any later version.

   This program 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 <http://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 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));
		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;
}