1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 *******************************************************************************
5 *
6 * Copyright (C) 2009-2014, International Business Machines
7 * Corporation and others. All Rights Reserved.
8 *
9 *******************************************************************************
10 * file name: normalizer2impl.cpp
11 * encoding: UTF-8
12 * tab size: 8 (not used)
13 * indentation:4
14 *
15 * created on: 2009nov22
16 * created by: Markus W. Scherer
17 */
18
19 // #define UCPTRIE_DEBUG
20
21 #include "unicode/utypes.h"
22
23 #if !UCONFIG_NO_NORMALIZATION
24
25 #include "unicode/bytestream.h"
26 #include "unicode/edits.h"
27 #include "unicode/normalizer2.h"
28 #include "unicode/stringoptions.h"
29 #include "unicode/ucptrie.h"
30 #include "unicode/udata.h"
31 #include "unicode/umutablecptrie.h"
32 #include "unicode/ustring.h"
33 #include "unicode/utf16.h"
34 #include "unicode/utf8.h"
35 #include "bytesinkutil.h"
36 #include "cmemory.h"
37 #include "mutex.h"
38 #include "normalizer2impl.h"
39 #include "putilimp.h"
40 #include "uassert.h"
41 #include "ucptrie_impl.h"
42 #include "uset_imp.h"
43 #include "uvector.h"
44
45 U_NAMESPACE_BEGIN
46
47 namespace {
48
49 /**
50 * UTF-8 lead byte for minNoMaybeCP.
51 * Can be lower than the actual lead byte for c.
52 * Typically U+0300 for NFC/NFD, U+00A0 for NFKC/NFKD, U+0041 for NFKC_Casefold.
53 */
leadByteForCP(UChar32 c)54 inline uint8_t leadByteForCP(UChar32 c) {
55 if (c <= 0x7f) {
56 return (uint8_t)c;
57 } else if (c <= 0x7ff) {
58 return (uint8_t)(0xc0+(c>>6));
59 } else {
60 // Should not occur because ccc(U+0300)!=0.
61 return 0xe0;
62 }
63 }
64
65 /**
66 * Returns the code point from one single well-formed UTF-8 byte sequence
67 * between cpStart and cpLimit.
68 *
69 * Trie UTF-8 macros do not assemble whole code points (for efficiency).
70 * When we do need the code point, we call this function.
71 * We should not need it for normalization-inert data (norm16==0).
72 * Illegal sequences yield the error value norm16==0 just like real normalization-inert code points.
73 */
codePointFromValidUTF8(const uint8_t * cpStart,const uint8_t * cpLimit)74 UChar32 codePointFromValidUTF8(const uint8_t *cpStart, const uint8_t *cpLimit) {
75 // Similar to U8_NEXT_UNSAFE(s, i, c).
76 U_ASSERT(cpStart < cpLimit);
77 uint8_t c = *cpStart;
78 switch(cpLimit-cpStart) {
79 case 1:
80 return c;
81 case 2:
82 return ((c&0x1f)<<6) | (cpStart[1]&0x3f);
83 case 3:
84 // no need for (c&0xf) because the upper bits are truncated after <<12 in the cast to (UChar)
85 return (UChar)((c<<12) | ((cpStart[1]&0x3f)<<6) | (cpStart[2]&0x3f));
86 case 4:
87 return ((c&7)<<18) | ((cpStart[1]&0x3f)<<12) | ((cpStart[2]&0x3f)<<6) | (cpStart[3]&0x3f);
88 default:
89 U_ASSERT(FALSE); // Should not occur.
90 return U_SENTINEL;
91 }
92 }
93
94 /**
95 * Returns the last code point in [start, p[ if it is valid and in U+1000..U+D7FF.
96 * Otherwise returns a negative value.
97 */
previousHangulOrJamo(const uint8_t * start,const uint8_t * p)98 UChar32 previousHangulOrJamo(const uint8_t *start, const uint8_t *p) {
99 if ((p - start) >= 3) {
100 p -= 3;
101 uint8_t l = *p;
102 uint8_t t1, t2;
103 if (0xe1 <= l && l <= 0xed &&
104 (t1 = (uint8_t)(p[1] - 0x80)) <= 0x3f &&
105 (t2 = (uint8_t)(p[2] - 0x80)) <= 0x3f &&
106 (l < 0xed || t1 <= 0x1f)) {
107 return ((l & 0xf) << 12) | (t1 << 6) | t2;
108 }
109 }
110 return U_SENTINEL;
111 }
112
113 /**
114 * Returns the offset from the Jamo T base if [src, limit[ starts with a single Jamo T code point.
115 * Otherwise returns a negative value.
116 */
getJamoTMinusBase(const uint8_t * src,const uint8_t * limit)117 int32_t getJamoTMinusBase(const uint8_t *src, const uint8_t *limit) {
118 // Jamo T: E1 86 A8..E1 87 82
119 if ((limit - src) >= 3 && *src == 0xe1) {
120 if (src[1] == 0x86) {
121 uint8_t t = src[2];
122 // The first Jamo T is U+11A8 but JAMO_T_BASE is 11A7.
123 // Offset 0 does not correspond to any conjoining Jamo.
124 if (0xa8 <= t && t <= 0xbf) {
125 return t - 0xa7;
126 }
127 } else if (src[1] == 0x87) {
128 uint8_t t = src[2];
129 if ((int8_t)t <= (int8_t)0x82u) {
130 return t - (0xa7 - 0x40);
131 }
132 }
133 }
134 return -1;
135 }
136
137 void
appendCodePointDelta(const uint8_t * cpStart,const uint8_t * cpLimit,int32_t delta,ByteSink & sink,Edits * edits)138 appendCodePointDelta(const uint8_t *cpStart, const uint8_t *cpLimit, int32_t delta,
139 ByteSink &sink, Edits *edits) {
140 char buffer[U8_MAX_LENGTH];
141 int32_t length;
142 int32_t cpLength = (int32_t)(cpLimit - cpStart);
143 if (cpLength == 1) {
144 // The builder makes ASCII map to ASCII.
145 buffer[0] = (uint8_t)(*cpStart + delta);
146 length = 1;
147 } else {
148 int32_t trail = *(cpLimit-1) + delta;
149 if (0x80 <= trail && trail <= 0xbf) {
150 // The delta only changes the last trail byte.
151 --cpLimit;
152 length = 0;
153 do { buffer[length++] = *cpStart++; } while (cpStart < cpLimit);
154 buffer[length++] = (uint8_t)trail;
155 } else {
156 // Decode the code point, add the delta, re-encode.
157 UChar32 c = codePointFromValidUTF8(cpStart, cpLimit) + delta;
158 length = 0;
159 U8_APPEND_UNSAFE(buffer, length, c);
160 }
161 }
162 if (edits != nullptr) {
163 edits->addReplace(cpLength, length);
164 }
165 sink.Append(buffer, length);
166 }
167
168 } // namespace
169
170 // ReorderingBuffer -------------------------------------------------------- ***
171
ReorderingBuffer(const Normalizer2Impl & ni,UnicodeString & dest,UErrorCode & errorCode)172 ReorderingBuffer::ReorderingBuffer(const Normalizer2Impl &ni, UnicodeString &dest,
173 UErrorCode &errorCode) :
174 impl(ni), str(dest),
175 start(str.getBuffer(8)), reorderStart(start), limit(start),
176 remainingCapacity(str.getCapacity()), lastCC(0) {
177 if (start == nullptr && U_SUCCESS(errorCode)) {
178 // getBuffer() already did str.setToBogus()
179 errorCode = U_MEMORY_ALLOCATION_ERROR;
180 }
181 }
182
init(int32_t destCapacity,UErrorCode & errorCode)183 UBool ReorderingBuffer::init(int32_t destCapacity, UErrorCode &errorCode) {
184 int32_t length=str.length();
185 start=str.getBuffer(destCapacity);
186 if(start==NULL) {
187 // getBuffer() already did str.setToBogus()
188 errorCode=U_MEMORY_ALLOCATION_ERROR;
189 return FALSE;
190 }
191 limit=start+length;
192 remainingCapacity=str.getCapacity()-length;
193 reorderStart=start;
194 if(start==limit) {
195 lastCC=0;
196 } else {
197 setIterator();
198 lastCC=previousCC();
199 // Set reorderStart after the last code point with cc<=1 if there is one.
200 if(lastCC>1) {
201 while(previousCC()>1) {}
202 }
203 reorderStart=codePointLimit;
204 }
205 return TRUE;
206 }
207
equals(const UChar * otherStart,const UChar * otherLimit) const208 UBool ReorderingBuffer::equals(const UChar *otherStart, const UChar *otherLimit) const {
209 int32_t length=(int32_t)(limit-start);
210 return
211 length==(int32_t)(otherLimit-otherStart) &&
212 0==u_memcmp(start, otherStart, length);
213 }
214
equals(const uint8_t * otherStart,const uint8_t * otherLimit) const215 UBool ReorderingBuffer::equals(const uint8_t *otherStart, const uint8_t *otherLimit) const {
216 U_ASSERT((otherLimit - otherStart) <= INT32_MAX); // ensured by caller
217 int32_t length = (int32_t)(limit - start);
218 int32_t otherLength = (int32_t)(otherLimit - otherStart);
219 // For equal strings, UTF-8 is at least as long as UTF-16, and at most three times as long.
220 if (otherLength < length || (otherLength / 3) > length) {
221 return FALSE;
222 }
223 // Compare valid strings from between normalization boundaries.
224 // (Invalid sequences are normalization-inert.)
225 for (int32_t i = 0, j = 0;;) {
226 if (i >= length) {
227 return j >= otherLength;
228 } else if (j >= otherLength) {
229 return FALSE;
230 }
231 // Not at the end of either string yet.
232 UChar32 c, other;
233 U16_NEXT_UNSAFE(start, i, c);
234 U8_NEXT_UNSAFE(otherStart, j, other);
235 if (c != other) {
236 return FALSE;
237 }
238 }
239 }
240
appendSupplementary(UChar32 c,uint8_t cc,UErrorCode & errorCode)241 UBool ReorderingBuffer::appendSupplementary(UChar32 c, uint8_t cc, UErrorCode &errorCode) {
242 if(remainingCapacity<2 && !resize(2, errorCode)) {
243 return FALSE;
244 }
245 if(lastCC<=cc || cc==0) {
246 limit[0]=U16_LEAD(c);
247 limit[1]=U16_TRAIL(c);
248 limit+=2;
249 lastCC=cc;
250 if(cc<=1) {
251 reorderStart=limit;
252 }
253 } else {
254 insert(c, cc);
255 }
256 remainingCapacity-=2;
257 return TRUE;
258 }
259
append(const UChar * s,int32_t length,UBool isNFD,uint8_t leadCC,uint8_t trailCC,UErrorCode & errorCode)260 UBool ReorderingBuffer::append(const UChar *s, int32_t length, UBool isNFD,
261 uint8_t leadCC, uint8_t trailCC,
262 UErrorCode &errorCode) {
263 if(length==0) {
264 return TRUE;
265 }
266 if(remainingCapacity<length && !resize(length, errorCode)) {
267 return FALSE;
268 }
269 remainingCapacity-=length;
270 if(lastCC<=leadCC || leadCC==0) {
271 if(trailCC<=1) {
272 reorderStart=limit+length;
273 } else if(leadCC<=1) {
274 reorderStart=limit+1; // Ok if not a code point boundary.
275 }
276 const UChar *sLimit=s+length;
277 do { *limit++=*s++; } while(s!=sLimit);
278 lastCC=trailCC;
279 } else {
280 int32_t i=0;
281 UChar32 c;
282 U16_NEXT(s, i, length, c);
283 insert(c, leadCC); // insert first code point
284 while(i<length) {
285 U16_NEXT(s, i, length, c);
286 if(i<length) {
287 if (isNFD) {
288 leadCC = Normalizer2Impl::getCCFromYesOrMaybe(impl.getRawNorm16(c));
289 } else {
290 leadCC = impl.getCC(impl.getNorm16(c));
291 }
292 } else {
293 leadCC=trailCC;
294 }
295 append(c, leadCC, errorCode);
296 }
297 }
298 return TRUE;
299 }
300
appendZeroCC(UChar32 c,UErrorCode & errorCode)301 UBool ReorderingBuffer::appendZeroCC(UChar32 c, UErrorCode &errorCode) {
302 int32_t cpLength=U16_LENGTH(c);
303 if(remainingCapacity<cpLength && !resize(cpLength, errorCode)) {
304 return FALSE;
305 }
306 remainingCapacity-=cpLength;
307 if(cpLength==1) {
308 *limit++=(UChar)c;
309 } else {
310 limit[0]=U16_LEAD(c);
311 limit[1]=U16_TRAIL(c);
312 limit+=2;
313 }
314 lastCC=0;
315 reorderStart=limit;
316 return TRUE;
317 }
318
appendZeroCC(const UChar * s,const UChar * sLimit,UErrorCode & errorCode)319 UBool ReorderingBuffer::appendZeroCC(const UChar *s, const UChar *sLimit, UErrorCode &errorCode) {
320 if(s==sLimit) {
321 return TRUE;
322 }
323 int32_t length=(int32_t)(sLimit-s);
324 if(remainingCapacity<length && !resize(length, errorCode)) {
325 return FALSE;
326 }
327 u_memcpy(limit, s, length);
328 limit+=length;
329 remainingCapacity-=length;
330 lastCC=0;
331 reorderStart=limit;
332 return TRUE;
333 }
334
remove()335 void ReorderingBuffer::remove() {
336 reorderStart=limit=start;
337 remainingCapacity=str.getCapacity();
338 lastCC=0;
339 }
340
removeSuffix(int32_t suffixLength)341 void ReorderingBuffer::removeSuffix(int32_t suffixLength) {
342 if(suffixLength<(limit-start)) {
343 limit-=suffixLength;
344 remainingCapacity+=suffixLength;
345 } else {
346 limit=start;
347 remainingCapacity=str.getCapacity();
348 }
349 lastCC=0;
350 reorderStart=limit;
351 }
352
resize(int32_t appendLength,UErrorCode & errorCode)353 UBool ReorderingBuffer::resize(int32_t appendLength, UErrorCode &errorCode) {
354 int32_t reorderStartIndex=(int32_t)(reorderStart-start);
355 int32_t length=(int32_t)(limit-start);
356 str.releaseBuffer(length);
357 int32_t newCapacity=length+appendLength;
358 int32_t doubleCapacity=2*str.getCapacity();
359 if(newCapacity<doubleCapacity) {
360 newCapacity=doubleCapacity;
361 }
362 if(newCapacity<256) {
363 newCapacity=256;
364 }
365 start=str.getBuffer(newCapacity);
366 if(start==NULL) {
367 // getBuffer() already did str.setToBogus()
368 errorCode=U_MEMORY_ALLOCATION_ERROR;
369 return FALSE;
370 }
371 reorderStart=start+reorderStartIndex;
372 limit=start+length;
373 remainingCapacity=str.getCapacity()-length;
374 return TRUE;
375 }
376
skipPrevious()377 void ReorderingBuffer::skipPrevious() {
378 codePointLimit=codePointStart;
379 UChar c=*--codePointStart;
380 if(U16_IS_TRAIL(c) && start<codePointStart && U16_IS_LEAD(*(codePointStart-1))) {
381 --codePointStart;
382 }
383 }
384
previousCC()385 uint8_t ReorderingBuffer::previousCC() {
386 codePointLimit=codePointStart;
387 if(reorderStart>=codePointStart) {
388 return 0;
389 }
390 UChar32 c=*--codePointStart;
391 UChar c2;
392 if(U16_IS_TRAIL(c) && start<codePointStart && U16_IS_LEAD(c2=*(codePointStart-1))) {
393 --codePointStart;
394 c=U16_GET_SUPPLEMENTARY(c2, c);
395 }
396 return impl.getCCFromYesOrMaybeCP(c);
397 }
398
399 // Inserts c somewhere before the last character.
400 // Requires 0<cc<lastCC which implies reorderStart<limit.
insert(UChar32 c,uint8_t cc)401 void ReorderingBuffer::insert(UChar32 c, uint8_t cc) {
402 for(setIterator(), skipPrevious(); previousCC()>cc;) {}
403 // insert c at codePointLimit, after the character with prevCC<=cc
404 UChar *q=limit;
405 UChar *r=limit+=U16_LENGTH(c);
406 do {
407 *--r=*--q;
408 } while(codePointLimit!=q);
409 writeCodePoint(q, c);
410 if(cc<=1) {
411 reorderStart=r;
412 }
413 }
414
415 // Normalizer2Impl --------------------------------------------------------- ***
416
417 struct CanonIterData : public UMemory {
418 CanonIterData(UErrorCode &errorCode);
419 ~CanonIterData();
420 void addToStartSet(UChar32 origin, UChar32 decompLead, UErrorCode &errorCode);
421 UMutableCPTrie *mutableTrie;
422 UCPTrie *trie;
423 UVector canonStartSets; // contains UnicodeSet *
424 };
425
~Normalizer2Impl()426 Normalizer2Impl::~Normalizer2Impl() {
427 delete fCanonIterData;
428 }
429
430 void
init(const int32_t * inIndexes,const UCPTrie * inTrie,const uint16_t * inExtraData,const uint8_t * inSmallFCD)431 Normalizer2Impl::init(const int32_t *inIndexes, const UCPTrie *inTrie,
432 const uint16_t *inExtraData, const uint8_t *inSmallFCD) {
433 minDecompNoCP = static_cast<UChar>(inIndexes[IX_MIN_DECOMP_NO_CP]);
434 minCompNoMaybeCP = static_cast<UChar>(inIndexes[IX_MIN_COMP_NO_MAYBE_CP]);
435 minLcccCP = static_cast<UChar>(inIndexes[IX_MIN_LCCC_CP]);
436
437 minYesNo = static_cast<uint16_t>(inIndexes[IX_MIN_YES_NO]);
438 minYesNoMappingsOnly = static_cast<uint16_t>(inIndexes[IX_MIN_YES_NO_MAPPINGS_ONLY]);
439 minNoNo = static_cast<uint16_t>(inIndexes[IX_MIN_NO_NO]);
440 minNoNoCompBoundaryBefore = static_cast<uint16_t>(inIndexes[IX_MIN_NO_NO_COMP_BOUNDARY_BEFORE]);
441 minNoNoCompNoMaybeCC = static_cast<uint16_t>(inIndexes[IX_MIN_NO_NO_COMP_NO_MAYBE_CC]);
442 minNoNoEmpty = static_cast<uint16_t>(inIndexes[IX_MIN_NO_NO_EMPTY]);
443 limitNoNo = static_cast<uint16_t>(inIndexes[IX_LIMIT_NO_NO]);
444 minMaybeYes = static_cast<uint16_t>(inIndexes[IX_MIN_MAYBE_YES]);
445 U_ASSERT((minMaybeYes & 7) == 0); // 8-aligned for noNoDelta bit fields
446 centerNoNoDelta = (minMaybeYes >> DELTA_SHIFT) - MAX_DELTA - 1;
447
448 normTrie=inTrie;
449
450 maybeYesCompositions=inExtraData;
451 extraData=maybeYesCompositions+((MIN_NORMAL_MAYBE_YES-minMaybeYes)>>OFFSET_SHIFT);
452
453 smallFCD=inSmallFCD;
454 }
455
456 U_CDECL_BEGIN
457
458 static uint32_t U_CALLCONV
segmentStarterMapper(const void *,uint32_t value)459 segmentStarterMapper(const void * /*context*/, uint32_t value) {
460 return value&CANON_NOT_SEGMENT_STARTER;
461 }
462
463 U_CDECL_END
464
465 void
addLcccChars(UnicodeSet & set) const466 Normalizer2Impl::addLcccChars(UnicodeSet &set) const {
467 UChar32 start = 0, end;
468 uint32_t norm16;
469 while ((end = ucptrie_getRange(normTrie, start, UCPMAP_RANGE_FIXED_LEAD_SURROGATES, INERT,
470 nullptr, nullptr, &norm16)) >= 0) {
471 if (norm16 > Normalizer2Impl::MIN_NORMAL_MAYBE_YES &&
472 norm16 != Normalizer2Impl::JAMO_VT) {
473 set.add(start, end);
474 } else if (minNoNoCompNoMaybeCC <= norm16 && norm16 < limitNoNo) {
475 uint16_t fcd16 = getFCD16(start);
476 if (fcd16 > 0xff) { set.add(start, end); }
477 }
478 start = end + 1;
479 }
480 }
481
482 void
addPropertyStarts(const USetAdder * sa,UErrorCode &) const483 Normalizer2Impl::addPropertyStarts(const USetAdder *sa, UErrorCode & /*errorCode*/) const {
484 // Add the start code point of each same-value range of the trie.
485 UChar32 start = 0, end;
486 uint32_t value;
487 while ((end = ucptrie_getRange(normTrie, start, UCPMAP_RANGE_FIXED_LEAD_SURROGATES, INERT,
488 nullptr, nullptr, &value)) >= 0) {
489 sa->add(sa->set, start);
490 if (start != end && isAlgorithmicNoNo((uint16_t)value) &&
491 (value & Normalizer2Impl::DELTA_TCCC_MASK) > Normalizer2Impl::DELTA_TCCC_1) {
492 // Range of code points with same-norm16-value algorithmic decompositions.
493 // They might have different non-zero FCD16 values.
494 uint16_t prevFCD16 = getFCD16(start);
495 while (++start <= end) {
496 uint16_t fcd16 = getFCD16(start);
497 if (fcd16 != prevFCD16) {
498 sa->add(sa->set, start);
499 prevFCD16 = fcd16;
500 }
501 }
502 }
503 start = end + 1;
504 }
505
506 /* add Hangul LV syllables and LV+1 because of skippables */
507 for(UChar c=Hangul::HANGUL_BASE; c<Hangul::HANGUL_LIMIT; c+=Hangul::JAMO_T_COUNT) {
508 sa->add(sa->set, c);
509 sa->add(sa->set, c+1);
510 }
511 sa->add(sa->set, Hangul::HANGUL_LIMIT); /* add Hangul+1 to continue with other properties */
512 }
513
514 void
addCanonIterPropertyStarts(const USetAdder * sa,UErrorCode & errorCode) const515 Normalizer2Impl::addCanonIterPropertyStarts(const USetAdder *sa, UErrorCode &errorCode) const {
516 // Add the start code point of each same-value range of the canonical iterator data trie.
517 if (!ensureCanonIterData(errorCode)) { return; }
518 // Currently only used for the SEGMENT_STARTER property.
519 UChar32 start = 0, end;
520 uint32_t value;
521 while ((end = ucptrie_getRange(fCanonIterData->trie, start, UCPMAP_RANGE_NORMAL, 0,
522 segmentStarterMapper, nullptr, &value)) >= 0) {
523 sa->add(sa->set, start);
524 start = end + 1;
525 }
526 }
527
528 const UChar *
copyLowPrefixFromNulTerminated(const UChar * src,UChar32 minNeedDataCP,ReorderingBuffer * buffer,UErrorCode & errorCode) const529 Normalizer2Impl::copyLowPrefixFromNulTerminated(const UChar *src,
530 UChar32 minNeedDataCP,
531 ReorderingBuffer *buffer,
532 UErrorCode &errorCode) const {
533 // Make some effort to support NUL-terminated strings reasonably.
534 // Take the part of the fast quick check loop that does not look up
535 // data and check the first part of the string.
536 // After this prefix, determine the string length to simplify the rest
537 // of the code.
538 const UChar *prevSrc=src;
539 UChar c;
540 while((c=*src++)<minNeedDataCP && c!=0) {}
541 // Back out the last character for full processing.
542 // Copy this prefix.
543 if(--src!=prevSrc) {
544 if(buffer!=NULL) {
545 buffer->appendZeroCC(prevSrc, src, errorCode);
546 }
547 }
548 return src;
549 }
550
551 UnicodeString &
decompose(const UnicodeString & src,UnicodeString & dest,UErrorCode & errorCode) const552 Normalizer2Impl::decompose(const UnicodeString &src, UnicodeString &dest,
553 UErrorCode &errorCode) const {
554 if(U_FAILURE(errorCode)) {
555 dest.setToBogus();
556 return dest;
557 }
558 const UChar *sArray=src.getBuffer();
559 if(&dest==&src || sArray==NULL) {
560 errorCode=U_ILLEGAL_ARGUMENT_ERROR;
561 dest.setToBogus();
562 return dest;
563 }
564 decompose(sArray, sArray+src.length(), dest, src.length(), errorCode);
565 return dest;
566 }
567
568 void
decompose(const UChar * src,const UChar * limit,UnicodeString & dest,int32_t destLengthEstimate,UErrorCode & errorCode) const569 Normalizer2Impl::decompose(const UChar *src, const UChar *limit,
570 UnicodeString &dest,
571 int32_t destLengthEstimate,
572 UErrorCode &errorCode) const {
573 if(destLengthEstimate<0 && limit!=NULL) {
574 destLengthEstimate=(int32_t)(limit-src);
575 }
576 dest.remove();
577 ReorderingBuffer buffer(*this, dest);
578 if(buffer.init(destLengthEstimate, errorCode)) {
579 decompose(src, limit, &buffer, errorCode);
580 }
581 }
582
583 // Dual functionality:
584 // buffer!=NULL: normalize
585 // buffer==NULL: isNormalized/spanQuickCheckYes
586 const UChar *
decompose(const UChar * src,const UChar * limit,ReorderingBuffer * buffer,UErrorCode & errorCode) const587 Normalizer2Impl::decompose(const UChar *src, const UChar *limit,
588 ReorderingBuffer *buffer,
589 UErrorCode &errorCode) const {
590 UChar32 minNoCP=minDecompNoCP;
591 if(limit==NULL) {
592 src=copyLowPrefixFromNulTerminated(src, minNoCP, buffer, errorCode);
593 if(U_FAILURE(errorCode)) {
594 return src;
595 }
596 limit=u_strchr(src, 0);
597 }
598
599 const UChar *prevSrc;
600 UChar32 c=0;
601 uint16_t norm16=0;
602
603 // only for quick check
604 const UChar *prevBoundary=src;
605 uint8_t prevCC=0;
606
607 for(;;) {
608 // count code units below the minimum or with irrelevant data for the quick check
609 for(prevSrc=src; src!=limit;) {
610 if( (c=*src)<minNoCP ||
611 isMostDecompYesAndZeroCC(norm16=UCPTRIE_FAST_BMP_GET(normTrie, UCPTRIE_16, c))
612 ) {
613 ++src;
614 } else if(!U16_IS_LEAD(c)) {
615 break;
616 } else {
617 UChar c2;
618 if((src+1)!=limit && U16_IS_TRAIL(c2=src[1])) {
619 c=U16_GET_SUPPLEMENTARY(c, c2);
620 norm16=UCPTRIE_FAST_SUPP_GET(normTrie, UCPTRIE_16, c);
621 if(isMostDecompYesAndZeroCC(norm16)) {
622 src+=2;
623 } else {
624 break;
625 }
626 } else {
627 ++src; // unpaired lead surrogate: inert
628 }
629 }
630 }
631 // copy these code units all at once
632 if(src!=prevSrc) {
633 if(buffer!=NULL) {
634 if(!buffer->appendZeroCC(prevSrc, src, errorCode)) {
635 break;
636 }
637 } else {
638 prevCC=0;
639 prevBoundary=src;
640 }
641 }
642 if(src==limit) {
643 break;
644 }
645
646 // Check one above-minimum, relevant code point.
647 src+=U16_LENGTH(c);
648 if(buffer!=NULL) {
649 if(!decompose(c, norm16, *buffer, errorCode)) {
650 break;
651 }
652 } else {
653 if(isDecompYes(norm16)) {
654 uint8_t cc=getCCFromYesOrMaybe(norm16);
655 if(prevCC<=cc || cc==0) {
656 prevCC=cc;
657 if(cc<=1) {
658 prevBoundary=src;
659 }
660 continue;
661 }
662 }
663 return prevBoundary; // "no" or cc out of order
664 }
665 }
666 return src;
667 }
668
669 // Decompose a short piece of text which is likely to contain characters that
670 // fail the quick check loop and/or where the quick check loop's overhead
671 // is unlikely to be amortized.
672 // Called by the compose() and makeFCD() implementations.
673 const UChar *
decomposeShort(const UChar * src,const UChar * limit,UBool stopAtCompBoundary,UBool onlyContiguous,ReorderingBuffer & buffer,UErrorCode & errorCode) const674 Normalizer2Impl::decomposeShort(const UChar *src, const UChar *limit,
675 UBool stopAtCompBoundary, UBool onlyContiguous,
676 ReorderingBuffer &buffer, UErrorCode &errorCode) const {
677 if (U_FAILURE(errorCode)) {
678 return nullptr;
679 }
680 while(src<limit) {
681 if (stopAtCompBoundary && *src < minCompNoMaybeCP) {
682 return src;
683 }
684 const UChar *prevSrc = src;
685 UChar32 c;
686 uint16_t norm16;
687 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, src, limit, c, norm16);
688 if (stopAtCompBoundary && norm16HasCompBoundaryBefore(norm16)) {
689 return prevSrc;
690 }
691 if(!decompose(c, norm16, buffer, errorCode)) {
692 return nullptr;
693 }
694 if (stopAtCompBoundary && norm16HasCompBoundaryAfter(norm16, onlyContiguous)) {
695 return src;
696 }
697 }
698 return src;
699 }
700
decompose(UChar32 c,uint16_t norm16,ReorderingBuffer & buffer,UErrorCode & errorCode) const701 UBool Normalizer2Impl::decompose(UChar32 c, uint16_t norm16,
702 ReorderingBuffer &buffer,
703 UErrorCode &errorCode) const {
704 // get the decomposition and the lead and trail cc's
705 if (norm16 >= limitNoNo) {
706 if (isMaybeOrNonZeroCC(norm16)) {
707 return buffer.append(c, getCCFromYesOrMaybe(norm16), errorCode);
708 }
709 // Maps to an isCompYesAndZeroCC.
710 c=mapAlgorithmic(c, norm16);
711 norm16=getRawNorm16(c);
712 }
713 if (norm16 < minYesNo) {
714 // c does not decompose
715 return buffer.append(c, 0, errorCode);
716 } else if(isHangulLV(norm16) || isHangulLVT(norm16)) {
717 // Hangul syllable: decompose algorithmically
718 UChar jamos[3];
719 return buffer.appendZeroCC(jamos, jamos+Hangul::decompose(c, jamos), errorCode);
720 }
721 // c decomposes, get everything from the variable-length extra data
722 const uint16_t *mapping=getMapping(norm16);
723 uint16_t firstUnit=*mapping;
724 int32_t length=firstUnit&MAPPING_LENGTH_MASK;
725 uint8_t leadCC, trailCC;
726 trailCC=(uint8_t)(firstUnit>>8);
727 if(firstUnit&MAPPING_HAS_CCC_LCCC_WORD) {
728 leadCC=(uint8_t)(*(mapping-1)>>8);
729 } else {
730 leadCC=0;
731 }
732 return buffer.append((const UChar *)mapping+1, length, TRUE, leadCC, trailCC, errorCode);
733 }
734
735 const uint8_t *
decomposeShort(const uint8_t * src,const uint8_t * limit,UBool stopAtCompBoundary,UBool onlyContiguous,ReorderingBuffer & buffer,UErrorCode & errorCode) const736 Normalizer2Impl::decomposeShort(const uint8_t *src, const uint8_t *limit,
737 UBool stopAtCompBoundary, UBool onlyContiguous,
738 ReorderingBuffer &buffer, UErrorCode &errorCode) const {
739 if (U_FAILURE(errorCode)) {
740 return nullptr;
741 }
742 while (src < limit) {
743 const uint8_t *prevSrc = src;
744 uint16_t norm16;
745 UCPTRIE_FAST_U8_NEXT(normTrie, UCPTRIE_16, src, limit, norm16);
746 // Get the decomposition and the lead and trail cc's.
747 UChar32 c = U_SENTINEL;
748 if (norm16 >= limitNoNo) {
749 if (isMaybeOrNonZeroCC(norm16)) {
750 // No boundaries around this character.
751 c = codePointFromValidUTF8(prevSrc, src);
752 if (!buffer.append(c, getCCFromYesOrMaybe(norm16), errorCode)) {
753 return nullptr;
754 }
755 continue;
756 }
757 // Maps to an isCompYesAndZeroCC.
758 if (stopAtCompBoundary) {
759 return prevSrc;
760 }
761 c = codePointFromValidUTF8(prevSrc, src);
762 c = mapAlgorithmic(c, norm16);
763 norm16 = getRawNorm16(c);
764 } else if (stopAtCompBoundary && norm16 < minNoNoCompNoMaybeCC) {
765 return prevSrc;
766 }
767 // norm16!=INERT guarantees that [prevSrc, src[ is valid UTF-8.
768 // We do not see invalid UTF-8 here because
769 // its norm16==INERT is normalization-inert,
770 // so it gets copied unchanged in the fast path,
771 // and we stop the slow path where invalid UTF-8 begins.
772 U_ASSERT(norm16 != INERT);
773 if (norm16 < minYesNo) {
774 if (c < 0) {
775 c = codePointFromValidUTF8(prevSrc, src);
776 }
777 // does not decompose
778 if (!buffer.append(c, 0, errorCode)) {
779 return nullptr;
780 }
781 } else if (isHangulLV(norm16) || isHangulLVT(norm16)) {
782 // Hangul syllable: decompose algorithmically
783 if (c < 0) {
784 c = codePointFromValidUTF8(prevSrc, src);
785 }
786 char16_t jamos[3];
787 if (!buffer.appendZeroCC(jamos, jamos+Hangul::decompose(c, jamos), errorCode)) {
788 return nullptr;
789 }
790 } else {
791 // The character decomposes, get everything from the variable-length extra data.
792 const uint16_t *mapping = getMapping(norm16);
793 uint16_t firstUnit = *mapping;
794 int32_t length = firstUnit & MAPPING_LENGTH_MASK;
795 uint8_t trailCC = (uint8_t)(firstUnit >> 8);
796 uint8_t leadCC;
797 if (firstUnit & MAPPING_HAS_CCC_LCCC_WORD) {
798 leadCC = (uint8_t)(*(mapping-1) >> 8);
799 } else {
800 leadCC = 0;
801 }
802 if (!buffer.append((const char16_t *)mapping+1, length, TRUE, leadCC, trailCC, errorCode)) {
803 return nullptr;
804 }
805 }
806 if (stopAtCompBoundary && norm16HasCompBoundaryAfter(norm16, onlyContiguous)) {
807 return src;
808 }
809 }
810 return src;
811 }
812
813 const UChar *
getDecomposition(UChar32 c,UChar buffer[4],int32_t & length) const814 Normalizer2Impl::getDecomposition(UChar32 c, UChar buffer[4], int32_t &length) const {
815 uint16_t norm16;
816 if(c<minDecompNoCP || isMaybeOrNonZeroCC(norm16=getNorm16(c))) {
817 // c does not decompose
818 return nullptr;
819 }
820 const UChar *decomp = nullptr;
821 if(isDecompNoAlgorithmic(norm16)) {
822 // Maps to an isCompYesAndZeroCC.
823 c=mapAlgorithmic(c, norm16);
824 decomp=buffer;
825 length=0;
826 U16_APPEND_UNSAFE(buffer, length, c);
827 // The mapping might decompose further.
828 norm16 = getRawNorm16(c);
829 }
830 if (norm16 < minYesNo) {
831 return decomp;
832 } else if(isHangulLV(norm16) || isHangulLVT(norm16)) {
833 // Hangul syllable: decompose algorithmically
834 length=Hangul::decompose(c, buffer);
835 return buffer;
836 }
837 // c decomposes, get everything from the variable-length extra data
838 const uint16_t *mapping=getMapping(norm16);
839 length=*mapping&MAPPING_LENGTH_MASK;
840 return (const UChar *)mapping+1;
841 }
842
843 // The capacity of the buffer must be 30=MAPPING_LENGTH_MASK-1
844 // so that a raw mapping fits that consists of one unit ("rm0")
845 // plus all but the first two code units of the normal mapping.
846 // The maximum length of a normal mapping is 31=MAPPING_LENGTH_MASK.
847 const UChar *
getRawDecomposition(UChar32 c,UChar buffer[30],int32_t & length) const848 Normalizer2Impl::getRawDecomposition(UChar32 c, UChar buffer[30], int32_t &length) const {
849 uint16_t norm16;
850 if(c<minDecompNoCP || isDecompYes(norm16=getNorm16(c))) {
851 // c does not decompose
852 return NULL;
853 } else if(isHangulLV(norm16) || isHangulLVT(norm16)) {
854 // Hangul syllable: decompose algorithmically
855 Hangul::getRawDecomposition(c, buffer);
856 length=2;
857 return buffer;
858 } else if(isDecompNoAlgorithmic(norm16)) {
859 c=mapAlgorithmic(c, norm16);
860 length=0;
861 U16_APPEND_UNSAFE(buffer, length, c);
862 return buffer;
863 }
864 // c decomposes, get everything from the variable-length extra data
865 const uint16_t *mapping=getMapping(norm16);
866 uint16_t firstUnit=*mapping;
867 int32_t mLength=firstUnit&MAPPING_LENGTH_MASK; // length of normal mapping
868 if(firstUnit&MAPPING_HAS_RAW_MAPPING) {
869 // Read the raw mapping from before the firstUnit and before the optional ccc/lccc word.
870 // Bit 7=MAPPING_HAS_CCC_LCCC_WORD
871 const uint16_t *rawMapping=mapping-((firstUnit>>7)&1)-1;
872 uint16_t rm0=*rawMapping;
873 if(rm0<=MAPPING_LENGTH_MASK) {
874 length=rm0;
875 return (const UChar *)rawMapping-rm0;
876 } else {
877 // Copy the normal mapping and replace its first two code units with rm0.
878 buffer[0]=(UChar)rm0;
879 u_memcpy(buffer+1, (const UChar *)mapping+1+2, mLength-2);
880 length=mLength-1;
881 return buffer;
882 }
883 } else {
884 length=mLength;
885 return (const UChar *)mapping+1;
886 }
887 }
888
decomposeAndAppend(const UChar * src,const UChar * limit,UBool doDecompose,UnicodeString & safeMiddle,ReorderingBuffer & buffer,UErrorCode & errorCode) const889 void Normalizer2Impl::decomposeAndAppend(const UChar *src, const UChar *limit,
890 UBool doDecompose,
891 UnicodeString &safeMiddle,
892 ReorderingBuffer &buffer,
893 UErrorCode &errorCode) const {
894 buffer.copyReorderableSuffixTo(safeMiddle);
895 if(doDecompose) {
896 decompose(src, limit, &buffer, errorCode);
897 return;
898 }
899 // Just merge the strings at the boundary.
900 bool isFirst = true;
901 uint8_t firstCC = 0, prevCC = 0, cc;
902 const UChar *p = src;
903 while (p != limit) {
904 const UChar *codePointStart = p;
905 UChar32 c;
906 uint16_t norm16;
907 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, p, limit, c, norm16);
908 if ((cc = getCC(norm16)) == 0) {
909 p = codePointStart;
910 break;
911 }
912 if (isFirst) {
913 firstCC = cc;
914 isFirst = false;
915 }
916 prevCC = cc;
917 }
918 if(limit==NULL) { // appendZeroCC() needs limit!=NULL
919 limit=u_strchr(p, 0);
920 }
921
922 if (buffer.append(src, (int32_t)(p - src), FALSE, firstCC, prevCC, errorCode)) {
923 buffer.appendZeroCC(p, limit, errorCode);
924 }
925 }
926
hasDecompBoundaryBefore(UChar32 c) const927 UBool Normalizer2Impl::hasDecompBoundaryBefore(UChar32 c) const {
928 return c < minLcccCP || (c <= 0xffff && !singleLeadMightHaveNonZeroFCD16(c)) ||
929 norm16HasDecompBoundaryBefore(getNorm16(c));
930 }
931
norm16HasDecompBoundaryBefore(uint16_t norm16) const932 UBool Normalizer2Impl::norm16HasDecompBoundaryBefore(uint16_t norm16) const {
933 if (norm16 < minNoNoCompNoMaybeCC) {
934 return TRUE;
935 }
936 if (norm16 >= limitNoNo) {
937 return norm16 <= MIN_NORMAL_MAYBE_YES || norm16 == JAMO_VT;
938 }
939 // c decomposes, get everything from the variable-length extra data
940 const uint16_t *mapping=getMapping(norm16);
941 uint16_t firstUnit=*mapping;
942 // TRUE if leadCC==0 (hasFCDBoundaryBefore())
943 return (firstUnit&MAPPING_HAS_CCC_LCCC_WORD)==0 || (*(mapping-1)&0xff00)==0;
944 }
945
hasDecompBoundaryAfter(UChar32 c) const946 UBool Normalizer2Impl::hasDecompBoundaryAfter(UChar32 c) const {
947 if (c < minDecompNoCP) {
948 return TRUE;
949 }
950 if (c <= 0xffff && !singleLeadMightHaveNonZeroFCD16(c)) {
951 return TRUE;
952 }
953 return norm16HasDecompBoundaryAfter(getNorm16(c));
954 }
955
norm16HasDecompBoundaryAfter(uint16_t norm16) const956 UBool Normalizer2Impl::norm16HasDecompBoundaryAfter(uint16_t norm16) const {
957 if(norm16 <= minYesNo || isHangulLVT(norm16)) {
958 return TRUE;
959 }
960 if (norm16 >= limitNoNo) {
961 if (isMaybeOrNonZeroCC(norm16)) {
962 return norm16 <= MIN_NORMAL_MAYBE_YES || norm16 == JAMO_VT;
963 }
964 // Maps to an isCompYesAndZeroCC.
965 return (norm16 & DELTA_TCCC_MASK) <= DELTA_TCCC_1;
966 }
967 // c decomposes, get everything from the variable-length extra data
968 const uint16_t *mapping=getMapping(norm16);
969 uint16_t firstUnit=*mapping;
970 // decomp after-boundary: same as hasFCDBoundaryAfter(),
971 // fcd16<=1 || trailCC==0
972 if(firstUnit>0x1ff) {
973 return FALSE; // trailCC>1
974 }
975 if(firstUnit<=0xff) {
976 return TRUE; // trailCC==0
977 }
978 // if(trailCC==1) test leadCC==0, same as checking for before-boundary
979 // TRUE if leadCC==0 (hasFCDBoundaryBefore())
980 return (firstUnit&MAPPING_HAS_CCC_LCCC_WORD)==0 || (*(mapping-1)&0xff00)==0;
981 }
982
983 /*
984 * Finds the recomposition result for
985 * a forward-combining "lead" character,
986 * specified with a pointer to its compositions list,
987 * and a backward-combining "trail" character.
988 *
989 * If the lead and trail characters combine, then this function returns
990 * the following "compositeAndFwd" value:
991 * Bits 21..1 composite character
992 * Bit 0 set if the composite is a forward-combining starter
993 * otherwise it returns -1.
994 *
995 * The compositions list has (trail, compositeAndFwd) pair entries,
996 * encoded as either pairs or triples of 16-bit units.
997 * The last entry has the high bit of its first unit set.
998 *
999 * The list is sorted by ascending trail characters (there are no duplicates).
1000 * A linear search is used.
1001 *
1002 * See normalizer2impl.h for a more detailed description
1003 * of the compositions list format.
1004 */
combine(const uint16_t * list,UChar32 trail)1005 int32_t Normalizer2Impl::combine(const uint16_t *list, UChar32 trail) {
1006 uint16_t key1, firstUnit;
1007 if(trail<COMP_1_TRAIL_LIMIT) {
1008 // trail character is 0..33FF
1009 // result entry may have 2 or 3 units
1010 key1=(uint16_t)(trail<<1);
1011 while(key1>(firstUnit=*list)) {
1012 list+=2+(firstUnit&COMP_1_TRIPLE);
1013 }
1014 if(key1==(firstUnit&COMP_1_TRAIL_MASK)) {
1015 if(firstUnit&COMP_1_TRIPLE) {
1016 return ((int32_t)list[1]<<16)|list[2];
1017 } else {
1018 return list[1];
1019 }
1020 }
1021 } else {
1022 // trail character is 3400..10FFFF
1023 // result entry has 3 units
1024 key1=(uint16_t)(COMP_1_TRAIL_LIMIT+
1025 (((trail>>COMP_1_TRAIL_SHIFT))&
1026 ~COMP_1_TRIPLE));
1027 uint16_t key2=(uint16_t)(trail<<COMP_2_TRAIL_SHIFT);
1028 uint16_t secondUnit;
1029 for(;;) {
1030 if(key1>(firstUnit=*list)) {
1031 list+=2+(firstUnit&COMP_1_TRIPLE);
1032 } else if(key1==(firstUnit&COMP_1_TRAIL_MASK)) {
1033 if(key2>(secondUnit=list[1])) {
1034 if(firstUnit&COMP_1_LAST_TUPLE) {
1035 break;
1036 } else {
1037 list+=3;
1038 }
1039 } else if(key2==(secondUnit&COMP_2_TRAIL_MASK)) {
1040 return ((int32_t)(secondUnit&~COMP_2_TRAIL_MASK)<<16)|list[2];
1041 } else {
1042 break;
1043 }
1044 } else {
1045 break;
1046 }
1047 }
1048 }
1049 return -1;
1050 }
1051
1052 /**
1053 * @param list some character's compositions list
1054 * @param set recursively receives the composites from these compositions
1055 */
addComposites(const uint16_t * list,UnicodeSet & set) const1056 void Normalizer2Impl::addComposites(const uint16_t *list, UnicodeSet &set) const {
1057 uint16_t firstUnit;
1058 int32_t compositeAndFwd;
1059 do {
1060 firstUnit=*list;
1061 if((firstUnit&COMP_1_TRIPLE)==0) {
1062 compositeAndFwd=list[1];
1063 list+=2;
1064 } else {
1065 compositeAndFwd=(((int32_t)list[1]&~COMP_2_TRAIL_MASK)<<16)|list[2];
1066 list+=3;
1067 }
1068 UChar32 composite=compositeAndFwd>>1;
1069 if((compositeAndFwd&1)!=0) {
1070 addComposites(getCompositionsListForComposite(getRawNorm16(composite)), set);
1071 }
1072 set.add(composite);
1073 } while((firstUnit&COMP_1_LAST_TUPLE)==0);
1074 }
1075
1076 /*
1077 * Recomposes the buffer text starting at recomposeStartIndex
1078 * (which is in NFD - decomposed and canonically ordered),
1079 * and truncates the buffer contents.
1080 *
1081 * Note that recomposition never lengthens the text:
1082 * Any character consists of either one or two code units;
1083 * a composition may contain at most one more code unit than the original starter,
1084 * while the combining mark that is removed has at least one code unit.
1085 */
recompose(ReorderingBuffer & buffer,int32_t recomposeStartIndex,UBool onlyContiguous) const1086 void Normalizer2Impl::recompose(ReorderingBuffer &buffer, int32_t recomposeStartIndex,
1087 UBool onlyContiguous) const {
1088 UChar *p=buffer.getStart()+recomposeStartIndex;
1089 UChar *limit=buffer.getLimit();
1090 if(p==limit) {
1091 return;
1092 }
1093
1094 UChar *starter, *pRemove, *q, *r;
1095 const uint16_t *compositionsList;
1096 UChar32 c, compositeAndFwd;
1097 uint16_t norm16;
1098 uint8_t cc, prevCC;
1099 UBool starterIsSupplementary;
1100
1101 // Some of the following variables are not used until we have a forward-combining starter
1102 // and are only initialized now to avoid compiler warnings.
1103 compositionsList=NULL; // used as indicator for whether we have a forward-combining starter
1104 starter=NULL;
1105 starterIsSupplementary=FALSE;
1106 prevCC=0;
1107
1108 for(;;) {
1109 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, p, limit, c, norm16);
1110 cc=getCCFromYesOrMaybe(norm16);
1111 if( // this character combines backward and
1112 isMaybe(norm16) &&
1113 // we have seen a starter that combines forward and
1114 compositionsList!=NULL &&
1115 // the backward-combining character is not blocked
1116 (prevCC<cc || prevCC==0)
1117 ) {
1118 if(isJamoVT(norm16)) {
1119 // c is a Jamo V/T, see if we can compose it with the previous character.
1120 if(c<Hangul::JAMO_T_BASE) {
1121 // c is a Jamo Vowel, compose with previous Jamo L and following Jamo T.
1122 UChar prev=(UChar)(*starter-Hangul::JAMO_L_BASE);
1123 if(prev<Hangul::JAMO_L_COUNT) {
1124 pRemove=p-1;
1125 UChar syllable=(UChar)
1126 (Hangul::HANGUL_BASE+
1127 (prev*Hangul::JAMO_V_COUNT+(c-Hangul::JAMO_V_BASE))*
1128 Hangul::JAMO_T_COUNT);
1129 UChar t;
1130 if(p!=limit && (t=(UChar)(*p-Hangul::JAMO_T_BASE))<Hangul::JAMO_T_COUNT) {
1131 ++p;
1132 syllable+=t; // The next character was a Jamo T.
1133 }
1134 *starter=syllable;
1135 // remove the Jamo V/T
1136 q=pRemove;
1137 r=p;
1138 while(r<limit) {
1139 *q++=*r++;
1140 }
1141 limit=q;
1142 p=pRemove;
1143 }
1144 }
1145 /*
1146 * No "else" for Jamo T:
1147 * Since the input is in NFD, there are no Hangul LV syllables that
1148 * a Jamo T could combine with.
1149 * All Jamo Ts are combined above when handling Jamo Vs.
1150 */
1151 if(p==limit) {
1152 break;
1153 }
1154 compositionsList=NULL;
1155 continue;
1156 } else if((compositeAndFwd=combine(compositionsList, c))>=0) {
1157 // The starter and the combining mark (c) do combine.
1158 UChar32 composite=compositeAndFwd>>1;
1159
1160 // Replace the starter with the composite, remove the combining mark.
1161 pRemove=p-U16_LENGTH(c); // pRemove & p: start & limit of the combining mark
1162 if(starterIsSupplementary) {
1163 if(U_IS_SUPPLEMENTARY(composite)) {
1164 // both are supplementary
1165 starter[0]=U16_LEAD(composite);
1166 starter[1]=U16_TRAIL(composite);
1167 } else {
1168 *starter=(UChar)composite;
1169 // The composite is shorter than the starter,
1170 // move the intermediate characters forward one.
1171 starterIsSupplementary=FALSE;
1172 q=starter+1;
1173 r=q+1;
1174 while(r<pRemove) {
1175 *q++=*r++;
1176 }
1177 --pRemove;
1178 }
1179 } else if(U_IS_SUPPLEMENTARY(composite)) {
1180 // The composite is longer than the starter,
1181 // move the intermediate characters back one.
1182 starterIsSupplementary=TRUE;
1183 ++starter; // temporarily increment for the loop boundary
1184 q=pRemove;
1185 r=++pRemove;
1186 while(starter<q) {
1187 *--r=*--q;
1188 }
1189 *starter=U16_TRAIL(composite);
1190 *--starter=U16_LEAD(composite); // undo the temporary increment
1191 } else {
1192 // both are on the BMP
1193 *starter=(UChar)composite;
1194 }
1195
1196 /* remove the combining mark by moving the following text over it */
1197 if(pRemove<p) {
1198 q=pRemove;
1199 r=p;
1200 while(r<limit) {
1201 *q++=*r++;
1202 }
1203 limit=q;
1204 p=pRemove;
1205 }
1206 // Keep prevCC because we removed the combining mark.
1207
1208 if(p==limit) {
1209 break;
1210 }
1211 // Is the composite a starter that combines forward?
1212 if(compositeAndFwd&1) {
1213 compositionsList=
1214 getCompositionsListForComposite(getRawNorm16(composite));
1215 } else {
1216 compositionsList=NULL;
1217 }
1218
1219 // We combined; continue with looking for compositions.
1220 continue;
1221 }
1222 }
1223
1224 // no combination this time
1225 prevCC=cc;
1226 if(p==limit) {
1227 break;
1228 }
1229
1230 // If c did not combine, then check if it is a starter.
1231 if(cc==0) {
1232 // Found a new starter.
1233 if((compositionsList=getCompositionsListForDecompYes(norm16))!=NULL) {
1234 // It may combine with something, prepare for it.
1235 if(U_IS_BMP(c)) {
1236 starterIsSupplementary=FALSE;
1237 starter=p-1;
1238 } else {
1239 starterIsSupplementary=TRUE;
1240 starter=p-2;
1241 }
1242 }
1243 } else if(onlyContiguous) {
1244 // FCC: no discontiguous compositions; any intervening character blocks.
1245 compositionsList=NULL;
1246 }
1247 }
1248 buffer.setReorderingLimit(limit);
1249 }
1250
1251 UChar32
composePair(UChar32 a,UChar32 b) const1252 Normalizer2Impl::composePair(UChar32 a, UChar32 b) const {
1253 uint16_t norm16=getNorm16(a); // maps an out-of-range 'a' to inert norm16
1254 const uint16_t *list;
1255 if(isInert(norm16)) {
1256 return U_SENTINEL;
1257 } else if(norm16<minYesNoMappingsOnly) {
1258 // a combines forward.
1259 if(isJamoL(norm16)) {
1260 b-=Hangul::JAMO_V_BASE;
1261 if(0<=b && b<Hangul::JAMO_V_COUNT) {
1262 return
1263 (Hangul::HANGUL_BASE+
1264 ((a-Hangul::JAMO_L_BASE)*Hangul::JAMO_V_COUNT+b)*
1265 Hangul::JAMO_T_COUNT);
1266 } else {
1267 return U_SENTINEL;
1268 }
1269 } else if(isHangulLV(norm16)) {
1270 b-=Hangul::JAMO_T_BASE;
1271 if(0<b && b<Hangul::JAMO_T_COUNT) { // not b==0!
1272 return a+b;
1273 } else {
1274 return U_SENTINEL;
1275 }
1276 } else {
1277 // 'a' has a compositions list in extraData
1278 list=getMapping(norm16);
1279 if(norm16>minYesNo) { // composite 'a' has both mapping & compositions list
1280 list+= // mapping pointer
1281 1+ // +1 to skip the first unit with the mapping length
1282 (*list&MAPPING_LENGTH_MASK); // + mapping length
1283 }
1284 }
1285 } else if(norm16<minMaybeYes || MIN_NORMAL_MAYBE_YES<=norm16) {
1286 return U_SENTINEL;
1287 } else {
1288 list=getCompositionsListForMaybe(norm16);
1289 }
1290 if(b<0 || 0x10ffff<b) { // combine(list, b) requires a valid code point b
1291 return U_SENTINEL;
1292 }
1293 #if U_SIGNED_RIGHT_SHIFT_IS_ARITHMETIC
1294 return combine(list, b)>>1;
1295 #else
1296 int32_t compositeAndFwd=combine(list, b);
1297 return compositeAndFwd>=0 ? compositeAndFwd>>1 : U_SENTINEL;
1298 #endif
1299 }
1300
1301 // Very similar to composeQuickCheck(): Make the same changes in both places if relevant.
1302 // doCompose: normalize
1303 // !doCompose: isNormalized (buffer must be empty and initialized)
1304 UBool
compose(const UChar * src,const UChar * limit,UBool onlyContiguous,UBool doCompose,ReorderingBuffer & buffer,UErrorCode & errorCode) const1305 Normalizer2Impl::compose(const UChar *src, const UChar *limit,
1306 UBool onlyContiguous,
1307 UBool doCompose,
1308 ReorderingBuffer &buffer,
1309 UErrorCode &errorCode) const {
1310 const UChar *prevBoundary=src;
1311 UChar32 minNoMaybeCP=minCompNoMaybeCP;
1312 if(limit==NULL) {
1313 src=copyLowPrefixFromNulTerminated(src, minNoMaybeCP,
1314 doCompose ? &buffer : NULL,
1315 errorCode);
1316 if(U_FAILURE(errorCode)) {
1317 return FALSE;
1318 }
1319 limit=u_strchr(src, 0);
1320 if (prevBoundary != src) {
1321 if (hasCompBoundaryAfter(*(src-1), onlyContiguous)) {
1322 prevBoundary = src;
1323 } else {
1324 buffer.removeSuffix(1);
1325 prevBoundary = --src;
1326 }
1327 }
1328 }
1329
1330 for (;;) {
1331 // Fast path: Scan over a sequence of characters below the minimum "no or maybe" code point,
1332 // or with (compYes && ccc==0) properties.
1333 const UChar *prevSrc;
1334 UChar32 c = 0;
1335 uint16_t norm16 = 0;
1336 for (;;) {
1337 if (src == limit) {
1338 if (prevBoundary != limit && doCompose) {
1339 buffer.appendZeroCC(prevBoundary, limit, errorCode);
1340 }
1341 return TRUE;
1342 }
1343 if( (c=*src)<minNoMaybeCP ||
1344 isCompYesAndZeroCC(norm16=UCPTRIE_FAST_BMP_GET(normTrie, UCPTRIE_16, c))
1345 ) {
1346 ++src;
1347 } else {
1348 prevSrc = src++;
1349 if(!U16_IS_LEAD(c)) {
1350 break;
1351 } else {
1352 UChar c2;
1353 if(src!=limit && U16_IS_TRAIL(c2=*src)) {
1354 ++src;
1355 c=U16_GET_SUPPLEMENTARY(c, c2);
1356 norm16=UCPTRIE_FAST_SUPP_GET(normTrie, UCPTRIE_16, c);
1357 if(!isCompYesAndZeroCC(norm16)) {
1358 break;
1359 }
1360 }
1361 }
1362 }
1363 }
1364 // isCompYesAndZeroCC(norm16) is false, that is, norm16>=minNoNo.
1365 // The current character is either a "noNo" (has a mapping)
1366 // or a "maybeYes" (combines backward)
1367 // or a "yesYes" with ccc!=0.
1368 // It is not a Hangul syllable or Jamo L because those have "yes" properties.
1369
1370 // Medium-fast path: Handle cases that do not require full decomposition and recomposition.
1371 if (!isMaybeOrNonZeroCC(norm16)) { // minNoNo <= norm16 < minMaybeYes
1372 if (!doCompose) {
1373 return FALSE;
1374 }
1375 // Fast path for mapping a character that is immediately surrounded by boundaries.
1376 // In this case, we need not decompose around the current character.
1377 if (isDecompNoAlgorithmic(norm16)) {
1378 // Maps to a single isCompYesAndZeroCC character
1379 // which also implies hasCompBoundaryBefore.
1380 if (norm16HasCompBoundaryAfter(norm16, onlyContiguous) ||
1381 hasCompBoundaryBefore(src, limit)) {
1382 if (prevBoundary != prevSrc && !buffer.appendZeroCC(prevBoundary, prevSrc, errorCode)) {
1383 break;
1384 }
1385 if(!buffer.append(mapAlgorithmic(c, norm16), 0, errorCode)) {
1386 break;
1387 }
1388 prevBoundary = src;
1389 continue;
1390 }
1391 } else if (norm16 < minNoNoCompBoundaryBefore) {
1392 // The mapping is comp-normalized which also implies hasCompBoundaryBefore.
1393 if (norm16HasCompBoundaryAfter(norm16, onlyContiguous) ||
1394 hasCompBoundaryBefore(src, limit)) {
1395 if (prevBoundary != prevSrc && !buffer.appendZeroCC(prevBoundary, prevSrc, errorCode)) {
1396 break;
1397 }
1398 const UChar *mapping = reinterpret_cast<const UChar *>(getMapping(norm16));
1399 int32_t length = *mapping++ & MAPPING_LENGTH_MASK;
1400 if(!buffer.appendZeroCC(mapping, mapping + length, errorCode)) {
1401 break;
1402 }
1403 prevBoundary = src;
1404 continue;
1405 }
1406 } else if (norm16 >= minNoNoEmpty) {
1407 // The current character maps to nothing.
1408 // Simply omit it from the output if there is a boundary before _or_ after it.
1409 // The character itself implies no boundaries.
1410 if (hasCompBoundaryBefore(src, limit) ||
1411 hasCompBoundaryAfter(prevBoundary, prevSrc, onlyContiguous)) {
1412 if (prevBoundary != prevSrc && !buffer.appendZeroCC(prevBoundary, prevSrc, errorCode)) {
1413 break;
1414 }
1415 prevBoundary = src;
1416 continue;
1417 }
1418 }
1419 // Other "noNo" type, or need to examine more text around this character:
1420 // Fall through to the slow path.
1421 } else if (isJamoVT(norm16) && prevBoundary != prevSrc) {
1422 UChar prev=*(prevSrc-1);
1423 if(c<Hangul::JAMO_T_BASE) {
1424 // The current character is a Jamo Vowel,
1425 // compose with previous Jamo L and following Jamo T.
1426 UChar l = (UChar)(prev-Hangul::JAMO_L_BASE);
1427 if(l<Hangul::JAMO_L_COUNT) {
1428 if (!doCompose) {
1429 return FALSE;
1430 }
1431 int32_t t;
1432 if (src != limit &&
1433 0 < (t = ((int32_t)*src - Hangul::JAMO_T_BASE)) &&
1434 t < Hangul::JAMO_T_COUNT) {
1435 // The next character is a Jamo T.
1436 ++src;
1437 } else if (hasCompBoundaryBefore(src, limit)) {
1438 // No Jamo T follows, not even via decomposition.
1439 t = 0;
1440 } else {
1441 t = -1;
1442 }
1443 if (t >= 0) {
1444 UChar32 syllable = Hangul::HANGUL_BASE +
1445 (l*Hangul::JAMO_V_COUNT + (c-Hangul::JAMO_V_BASE)) *
1446 Hangul::JAMO_T_COUNT + t;
1447 --prevSrc; // Replace the Jamo L as well.
1448 if (prevBoundary != prevSrc && !buffer.appendZeroCC(prevBoundary, prevSrc, errorCode)) {
1449 break;
1450 }
1451 if(!buffer.appendBMP((UChar)syllable, 0, errorCode)) {
1452 break;
1453 }
1454 prevBoundary = src;
1455 continue;
1456 }
1457 // If we see L+V+x where x!=T then we drop to the slow path,
1458 // decompose and recompose.
1459 // This is to deal with NFKC finding normal L and V but a
1460 // compatibility variant of a T.
1461 // We need to either fully compose that combination here
1462 // (which would complicate the code and may not work with strange custom data)
1463 // or use the slow path.
1464 }
1465 } else if (Hangul::isHangulLV(prev)) {
1466 // The current character is a Jamo Trailing consonant,
1467 // compose with previous Hangul LV that does not contain a Jamo T.
1468 if (!doCompose) {
1469 return FALSE;
1470 }
1471 UChar32 syllable = prev + c - Hangul::JAMO_T_BASE;
1472 --prevSrc; // Replace the Hangul LV as well.
1473 if (prevBoundary != prevSrc && !buffer.appendZeroCC(prevBoundary, prevSrc, errorCode)) {
1474 break;
1475 }
1476 if(!buffer.appendBMP((UChar)syllable, 0, errorCode)) {
1477 break;
1478 }
1479 prevBoundary = src;
1480 continue;
1481 }
1482 // No matching context, or may need to decompose surrounding text first:
1483 // Fall through to the slow path.
1484 } else if (norm16 > JAMO_VT) { // norm16 >= MIN_YES_YES_WITH_CC
1485 // One or more combining marks that do not combine-back:
1486 // Check for canonical order, copy unchanged if ok and
1487 // if followed by a character with a boundary-before.
1488 uint8_t cc = getCCFromNormalYesOrMaybe(norm16); // cc!=0
1489 if (onlyContiguous /* FCC */ && getPreviousTrailCC(prevBoundary, prevSrc) > cc) {
1490 // Fails FCD test, need to decompose and contiguously recompose.
1491 if (!doCompose) {
1492 return FALSE;
1493 }
1494 } else {
1495 // If !onlyContiguous (not FCC), then we ignore the tccc of
1496 // the previous character which passed the quick check "yes && ccc==0" test.
1497 const UChar *nextSrc;
1498 uint16_t n16;
1499 for (;;) {
1500 if (src == limit) {
1501 if (doCompose) {
1502 buffer.appendZeroCC(prevBoundary, limit, errorCode);
1503 }
1504 return TRUE;
1505 }
1506 uint8_t prevCC = cc;
1507 nextSrc = src;
1508 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, nextSrc, limit, c, n16);
1509 if (n16 >= MIN_YES_YES_WITH_CC) {
1510 cc = getCCFromNormalYesOrMaybe(n16);
1511 if (prevCC > cc) {
1512 if (!doCompose) {
1513 return FALSE;
1514 }
1515 break;
1516 }
1517 } else {
1518 break;
1519 }
1520 src = nextSrc;
1521 }
1522 // src is after the last in-order combining mark.
1523 // If there is a boundary here, then we continue with no change.
1524 if (norm16HasCompBoundaryBefore(n16)) {
1525 if (isCompYesAndZeroCC(n16)) {
1526 src = nextSrc;
1527 }
1528 continue;
1529 }
1530 // Use the slow path. There is no boundary in [prevSrc, src[.
1531 }
1532 }
1533
1534 // Slow path: Find the nearest boundaries around the current character,
1535 // decompose and recompose.
1536 if (prevBoundary != prevSrc && !norm16HasCompBoundaryBefore(norm16)) {
1537 const UChar *p = prevSrc;
1538 UCPTRIE_FAST_U16_PREV(normTrie, UCPTRIE_16, prevBoundary, p, c, norm16);
1539 if (!norm16HasCompBoundaryAfter(norm16, onlyContiguous)) {
1540 prevSrc = p;
1541 }
1542 }
1543 if (doCompose && prevBoundary != prevSrc && !buffer.appendZeroCC(prevBoundary, prevSrc, errorCode)) {
1544 break;
1545 }
1546 int32_t recomposeStartIndex=buffer.length();
1547 // We know there is not a boundary here.
1548 decomposeShort(prevSrc, src, FALSE /* !stopAtCompBoundary */, onlyContiguous,
1549 buffer, errorCode);
1550 // Decompose until the next boundary.
1551 src = decomposeShort(src, limit, TRUE /* stopAtCompBoundary */, onlyContiguous,
1552 buffer, errorCode);
1553 if (U_FAILURE(errorCode)) {
1554 break;
1555 }
1556 if ((src - prevSrc) > INT32_MAX) { // guard before buffer.equals()
1557 errorCode = U_INDEX_OUTOFBOUNDS_ERROR;
1558 return TRUE;
1559 }
1560 recompose(buffer, recomposeStartIndex, onlyContiguous);
1561 if(!doCompose) {
1562 if(!buffer.equals(prevSrc, src)) {
1563 return FALSE;
1564 }
1565 buffer.remove();
1566 }
1567 prevBoundary=src;
1568 }
1569 return TRUE;
1570 }
1571
1572 // Very similar to compose(): Make the same changes in both places if relevant.
1573 // pQCResult==NULL: spanQuickCheckYes
1574 // pQCResult!=NULL: quickCheck (*pQCResult must be UNORM_YES)
1575 const UChar *
composeQuickCheck(const UChar * src,const UChar * limit,UBool onlyContiguous,UNormalizationCheckResult * pQCResult) const1576 Normalizer2Impl::composeQuickCheck(const UChar *src, const UChar *limit,
1577 UBool onlyContiguous,
1578 UNormalizationCheckResult *pQCResult) const {
1579 const UChar *prevBoundary=src;
1580 UChar32 minNoMaybeCP=minCompNoMaybeCP;
1581 if(limit==NULL) {
1582 UErrorCode errorCode=U_ZERO_ERROR;
1583 src=copyLowPrefixFromNulTerminated(src, minNoMaybeCP, NULL, errorCode);
1584 limit=u_strchr(src, 0);
1585 if (prevBoundary != src) {
1586 if (hasCompBoundaryAfter(*(src-1), onlyContiguous)) {
1587 prevBoundary = src;
1588 } else {
1589 prevBoundary = --src;
1590 }
1591 }
1592 }
1593
1594 for(;;) {
1595 // Fast path: Scan over a sequence of characters below the minimum "no or maybe" code point,
1596 // or with (compYes && ccc==0) properties.
1597 const UChar *prevSrc;
1598 UChar32 c = 0;
1599 uint16_t norm16 = 0;
1600 for (;;) {
1601 if(src==limit) {
1602 return src;
1603 }
1604 if( (c=*src)<minNoMaybeCP ||
1605 isCompYesAndZeroCC(norm16=UCPTRIE_FAST_BMP_GET(normTrie, UCPTRIE_16, c))
1606 ) {
1607 ++src;
1608 } else {
1609 prevSrc = src++;
1610 if(!U16_IS_LEAD(c)) {
1611 break;
1612 } else {
1613 UChar c2;
1614 if(src!=limit && U16_IS_TRAIL(c2=*src)) {
1615 ++src;
1616 c=U16_GET_SUPPLEMENTARY(c, c2);
1617 norm16=UCPTRIE_FAST_SUPP_GET(normTrie, UCPTRIE_16, c);
1618 if(!isCompYesAndZeroCC(norm16)) {
1619 break;
1620 }
1621 }
1622 }
1623 }
1624 }
1625 // isCompYesAndZeroCC(norm16) is false, that is, norm16>=minNoNo.
1626 // The current character is either a "noNo" (has a mapping)
1627 // or a "maybeYes" (combines backward)
1628 // or a "yesYes" with ccc!=0.
1629 // It is not a Hangul syllable or Jamo L because those have "yes" properties.
1630
1631 uint16_t prevNorm16 = INERT;
1632 if (prevBoundary != prevSrc) {
1633 if (norm16HasCompBoundaryBefore(norm16)) {
1634 prevBoundary = prevSrc;
1635 } else {
1636 const UChar *p = prevSrc;
1637 uint16_t n16;
1638 UCPTRIE_FAST_U16_PREV(normTrie, UCPTRIE_16, prevBoundary, p, c, n16);
1639 if (norm16HasCompBoundaryAfter(n16, onlyContiguous)) {
1640 prevBoundary = prevSrc;
1641 } else {
1642 prevBoundary = p;
1643 prevNorm16 = n16;
1644 }
1645 }
1646 }
1647
1648 if(isMaybeOrNonZeroCC(norm16)) {
1649 uint8_t cc=getCCFromYesOrMaybe(norm16);
1650 if (onlyContiguous /* FCC */ && cc != 0 &&
1651 getTrailCCFromCompYesAndZeroCC(prevNorm16) > cc) {
1652 // The [prevBoundary..prevSrc[ character
1653 // passed the quick check "yes && ccc==0" test
1654 // but is out of canonical order with the current combining mark.
1655 } else {
1656 // If !onlyContiguous (not FCC), then we ignore the tccc of
1657 // the previous character which passed the quick check "yes && ccc==0" test.
1658 const UChar *nextSrc;
1659 for (;;) {
1660 if (norm16 < MIN_YES_YES_WITH_CC) {
1661 if (pQCResult != nullptr) {
1662 *pQCResult = UNORM_MAYBE;
1663 } else {
1664 return prevBoundary;
1665 }
1666 }
1667 if (src == limit) {
1668 return src;
1669 }
1670 uint8_t prevCC = cc;
1671 nextSrc = src;
1672 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, nextSrc, limit, c, norm16);
1673 if (isMaybeOrNonZeroCC(norm16)) {
1674 cc = getCCFromYesOrMaybe(norm16);
1675 if (!(prevCC <= cc || cc == 0)) {
1676 break;
1677 }
1678 } else {
1679 break;
1680 }
1681 src = nextSrc;
1682 }
1683 // src is after the last in-order combining mark.
1684 if (isCompYesAndZeroCC(norm16)) {
1685 prevBoundary = src;
1686 src = nextSrc;
1687 continue;
1688 }
1689 }
1690 }
1691 if(pQCResult!=NULL) {
1692 *pQCResult=UNORM_NO;
1693 }
1694 return prevBoundary;
1695 }
1696 }
1697
composeAndAppend(const UChar * src,const UChar * limit,UBool doCompose,UBool onlyContiguous,UnicodeString & safeMiddle,ReorderingBuffer & buffer,UErrorCode & errorCode) const1698 void Normalizer2Impl::composeAndAppend(const UChar *src, const UChar *limit,
1699 UBool doCompose,
1700 UBool onlyContiguous,
1701 UnicodeString &safeMiddle,
1702 ReorderingBuffer &buffer,
1703 UErrorCode &errorCode) const {
1704 if(!buffer.isEmpty()) {
1705 const UChar *firstStarterInSrc=findNextCompBoundary(src, limit, onlyContiguous);
1706 if(src!=firstStarterInSrc) {
1707 const UChar *lastStarterInDest=findPreviousCompBoundary(buffer.getStart(),
1708 buffer.getLimit(), onlyContiguous);
1709 int32_t destSuffixLength=(int32_t)(buffer.getLimit()-lastStarterInDest);
1710 UnicodeString middle(lastStarterInDest, destSuffixLength);
1711 buffer.removeSuffix(destSuffixLength);
1712 safeMiddle=middle;
1713 middle.append(src, (int32_t)(firstStarterInSrc-src));
1714 const UChar *middleStart=middle.getBuffer();
1715 compose(middleStart, middleStart+middle.length(), onlyContiguous,
1716 TRUE, buffer, errorCode);
1717 if(U_FAILURE(errorCode)) {
1718 return;
1719 }
1720 src=firstStarterInSrc;
1721 }
1722 }
1723 if(doCompose) {
1724 compose(src, limit, onlyContiguous, TRUE, buffer, errorCode);
1725 } else {
1726 if(limit==NULL) { // appendZeroCC() needs limit!=NULL
1727 limit=u_strchr(src, 0);
1728 }
1729 buffer.appendZeroCC(src, limit, errorCode);
1730 }
1731 }
1732
1733 UBool
composeUTF8(uint32_t options,UBool onlyContiguous,const uint8_t * src,const uint8_t * limit,ByteSink * sink,Edits * edits,UErrorCode & errorCode) const1734 Normalizer2Impl::composeUTF8(uint32_t options, UBool onlyContiguous,
1735 const uint8_t *src, const uint8_t *limit,
1736 ByteSink *sink, Edits *edits, UErrorCode &errorCode) const {
1737 U_ASSERT(limit != nullptr);
1738 UnicodeString s16;
1739 uint8_t minNoMaybeLead = leadByteForCP(minCompNoMaybeCP);
1740 const uint8_t *prevBoundary = src;
1741
1742 for (;;) {
1743 // Fast path: Scan over a sequence of characters below the minimum "no or maybe" code point,
1744 // or with (compYes && ccc==0) properties.
1745 const uint8_t *prevSrc;
1746 uint16_t norm16 = 0;
1747 for (;;) {
1748 if (src == limit) {
1749 if (prevBoundary != limit && sink != nullptr) {
1750 ByteSinkUtil::appendUnchanged(prevBoundary, limit,
1751 *sink, options, edits, errorCode);
1752 }
1753 return TRUE;
1754 }
1755 if (*src < minNoMaybeLead) {
1756 ++src;
1757 } else {
1758 prevSrc = src;
1759 UCPTRIE_FAST_U8_NEXT(normTrie, UCPTRIE_16, src, limit, norm16);
1760 if (!isCompYesAndZeroCC(norm16)) {
1761 break;
1762 }
1763 }
1764 }
1765 // isCompYesAndZeroCC(norm16) is false, that is, norm16>=minNoNo.
1766 // The current character is either a "noNo" (has a mapping)
1767 // or a "maybeYes" (combines backward)
1768 // or a "yesYes" with ccc!=0.
1769 // It is not a Hangul syllable or Jamo L because those have "yes" properties.
1770
1771 // Medium-fast path: Handle cases that do not require full decomposition and recomposition.
1772 if (!isMaybeOrNonZeroCC(norm16)) { // minNoNo <= norm16 < minMaybeYes
1773 if (sink == nullptr) {
1774 return FALSE;
1775 }
1776 // Fast path for mapping a character that is immediately surrounded by boundaries.
1777 // In this case, we need not decompose around the current character.
1778 if (isDecompNoAlgorithmic(norm16)) {
1779 // Maps to a single isCompYesAndZeroCC character
1780 // which also implies hasCompBoundaryBefore.
1781 if (norm16HasCompBoundaryAfter(norm16, onlyContiguous) ||
1782 hasCompBoundaryBefore(src, limit)) {
1783 if (prevBoundary != prevSrc &&
1784 !ByteSinkUtil::appendUnchanged(prevBoundary, prevSrc,
1785 *sink, options, edits, errorCode)) {
1786 break;
1787 }
1788 appendCodePointDelta(prevSrc, src, getAlgorithmicDelta(norm16), *sink, edits);
1789 prevBoundary = src;
1790 continue;
1791 }
1792 } else if (norm16 < minNoNoCompBoundaryBefore) {
1793 // The mapping is comp-normalized which also implies hasCompBoundaryBefore.
1794 if (norm16HasCompBoundaryAfter(norm16, onlyContiguous) ||
1795 hasCompBoundaryBefore(src, limit)) {
1796 if (prevBoundary != prevSrc &&
1797 !ByteSinkUtil::appendUnchanged(prevBoundary, prevSrc,
1798 *sink, options, edits, errorCode)) {
1799 break;
1800 }
1801 const uint16_t *mapping = getMapping(norm16);
1802 int32_t length = *mapping++ & MAPPING_LENGTH_MASK;
1803 if (!ByteSinkUtil::appendChange(prevSrc, src, (const UChar *)mapping, length,
1804 *sink, edits, errorCode)) {
1805 break;
1806 }
1807 prevBoundary = src;
1808 continue;
1809 }
1810 } else if (norm16 >= minNoNoEmpty) {
1811 // The current character maps to nothing.
1812 // Simply omit it from the output if there is a boundary before _or_ after it.
1813 // The character itself implies no boundaries.
1814 if (hasCompBoundaryBefore(src, limit) ||
1815 hasCompBoundaryAfter(prevBoundary, prevSrc, onlyContiguous)) {
1816 if (prevBoundary != prevSrc &&
1817 !ByteSinkUtil::appendUnchanged(prevBoundary, prevSrc,
1818 *sink, options, edits, errorCode)) {
1819 break;
1820 }
1821 if (edits != nullptr) {
1822 edits->addReplace((int32_t)(src - prevSrc), 0);
1823 }
1824 prevBoundary = src;
1825 continue;
1826 }
1827 }
1828 // Other "noNo" type, or need to examine more text around this character:
1829 // Fall through to the slow path.
1830 } else if (isJamoVT(norm16)) {
1831 // Jamo L: E1 84 80..92
1832 // Jamo V: E1 85 A1..B5
1833 // Jamo T: E1 86 A8..E1 87 82
1834 U_ASSERT((src - prevSrc) == 3 && *prevSrc == 0xe1);
1835 UChar32 prev = previousHangulOrJamo(prevBoundary, prevSrc);
1836 if (prevSrc[1] == 0x85) {
1837 // The current character is a Jamo Vowel,
1838 // compose with previous Jamo L and following Jamo T.
1839 UChar32 l = prev - Hangul::JAMO_L_BASE;
1840 if ((uint32_t)l < Hangul::JAMO_L_COUNT) {
1841 if (sink == nullptr) {
1842 return FALSE;
1843 }
1844 int32_t t = getJamoTMinusBase(src, limit);
1845 if (t >= 0) {
1846 // The next character is a Jamo T.
1847 src += 3;
1848 } else if (hasCompBoundaryBefore(src, limit)) {
1849 // No Jamo T follows, not even via decomposition.
1850 t = 0;
1851 }
1852 if (t >= 0) {
1853 UChar32 syllable = Hangul::HANGUL_BASE +
1854 (l*Hangul::JAMO_V_COUNT + (prevSrc[2]-0xa1)) *
1855 Hangul::JAMO_T_COUNT + t;
1856 prevSrc -= 3; // Replace the Jamo L as well.
1857 if (prevBoundary != prevSrc &&
1858 !ByteSinkUtil::appendUnchanged(prevBoundary, prevSrc,
1859 *sink, options, edits, errorCode)) {
1860 break;
1861 }
1862 ByteSinkUtil::appendCodePoint(prevSrc, src, syllable, *sink, edits);
1863 prevBoundary = src;
1864 continue;
1865 }
1866 // If we see L+V+x where x!=T then we drop to the slow path,
1867 // decompose and recompose.
1868 // This is to deal with NFKC finding normal L and V but a
1869 // compatibility variant of a T.
1870 // We need to either fully compose that combination here
1871 // (which would complicate the code and may not work with strange custom data)
1872 // or use the slow path.
1873 }
1874 } else if (Hangul::isHangulLV(prev)) {
1875 // The current character is a Jamo Trailing consonant,
1876 // compose with previous Hangul LV that does not contain a Jamo T.
1877 if (sink == nullptr) {
1878 return FALSE;
1879 }
1880 UChar32 syllable = prev + getJamoTMinusBase(prevSrc, src);
1881 prevSrc -= 3; // Replace the Hangul LV as well.
1882 if (prevBoundary != prevSrc &&
1883 !ByteSinkUtil::appendUnchanged(prevBoundary, prevSrc,
1884 *sink, options, edits, errorCode)) {
1885 break;
1886 }
1887 ByteSinkUtil::appendCodePoint(prevSrc, src, syllable, *sink, edits);
1888 prevBoundary = src;
1889 continue;
1890 }
1891 // No matching context, or may need to decompose surrounding text first:
1892 // Fall through to the slow path.
1893 } else if (norm16 > JAMO_VT) { // norm16 >= MIN_YES_YES_WITH_CC
1894 // One or more combining marks that do not combine-back:
1895 // Check for canonical order, copy unchanged if ok and
1896 // if followed by a character with a boundary-before.
1897 uint8_t cc = getCCFromNormalYesOrMaybe(norm16); // cc!=0
1898 if (onlyContiguous /* FCC */ && getPreviousTrailCC(prevBoundary, prevSrc) > cc) {
1899 // Fails FCD test, need to decompose and contiguously recompose.
1900 if (sink == nullptr) {
1901 return FALSE;
1902 }
1903 } else {
1904 // If !onlyContiguous (not FCC), then we ignore the tccc of
1905 // the previous character which passed the quick check "yes && ccc==0" test.
1906 const uint8_t *nextSrc;
1907 uint16_t n16;
1908 for (;;) {
1909 if (src == limit) {
1910 if (sink != nullptr) {
1911 ByteSinkUtil::appendUnchanged(prevBoundary, limit,
1912 *sink, options, edits, errorCode);
1913 }
1914 return TRUE;
1915 }
1916 uint8_t prevCC = cc;
1917 nextSrc = src;
1918 UCPTRIE_FAST_U8_NEXT(normTrie, UCPTRIE_16, nextSrc, limit, n16);
1919 if (n16 >= MIN_YES_YES_WITH_CC) {
1920 cc = getCCFromNormalYesOrMaybe(n16);
1921 if (prevCC > cc) {
1922 if (sink == nullptr) {
1923 return FALSE;
1924 }
1925 break;
1926 }
1927 } else {
1928 break;
1929 }
1930 src = nextSrc;
1931 }
1932 // src is after the last in-order combining mark.
1933 // If there is a boundary here, then we continue with no change.
1934 if (norm16HasCompBoundaryBefore(n16)) {
1935 if (isCompYesAndZeroCC(n16)) {
1936 src = nextSrc;
1937 }
1938 continue;
1939 }
1940 // Use the slow path. There is no boundary in [prevSrc, src[.
1941 }
1942 }
1943
1944 // Slow path: Find the nearest boundaries around the current character,
1945 // decompose and recompose.
1946 if (prevBoundary != prevSrc && !norm16HasCompBoundaryBefore(norm16)) {
1947 const uint8_t *p = prevSrc;
1948 UCPTRIE_FAST_U8_PREV(normTrie, UCPTRIE_16, prevBoundary, p, norm16);
1949 if (!norm16HasCompBoundaryAfter(norm16, onlyContiguous)) {
1950 prevSrc = p;
1951 }
1952 }
1953 ReorderingBuffer buffer(*this, s16, errorCode);
1954 if (U_FAILURE(errorCode)) {
1955 break;
1956 }
1957 // We know there is not a boundary here.
1958 decomposeShort(prevSrc, src, FALSE /* !stopAtCompBoundary */, onlyContiguous,
1959 buffer, errorCode);
1960 // Decompose until the next boundary.
1961 src = decomposeShort(src, limit, TRUE /* stopAtCompBoundary */, onlyContiguous,
1962 buffer, errorCode);
1963 if (U_FAILURE(errorCode)) {
1964 break;
1965 }
1966 if ((src - prevSrc) > INT32_MAX) { // guard before buffer.equals()
1967 errorCode = U_INDEX_OUTOFBOUNDS_ERROR;
1968 return TRUE;
1969 }
1970 recompose(buffer, 0, onlyContiguous);
1971 if (!buffer.equals(prevSrc, src)) {
1972 if (sink == nullptr) {
1973 return FALSE;
1974 }
1975 if (prevBoundary != prevSrc &&
1976 !ByteSinkUtil::appendUnchanged(prevBoundary, prevSrc,
1977 *sink, options, edits, errorCode)) {
1978 break;
1979 }
1980 if (!ByteSinkUtil::appendChange(prevSrc, src, buffer.getStart(), buffer.length(),
1981 *sink, edits, errorCode)) {
1982 break;
1983 }
1984 prevBoundary = src;
1985 }
1986 }
1987 return TRUE;
1988 }
1989
hasCompBoundaryBefore(const UChar * src,const UChar * limit) const1990 UBool Normalizer2Impl::hasCompBoundaryBefore(const UChar *src, const UChar *limit) const {
1991 if (src == limit || *src < minCompNoMaybeCP) {
1992 return TRUE;
1993 }
1994 UChar32 c;
1995 uint16_t norm16;
1996 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, src, limit, c, norm16);
1997 return norm16HasCompBoundaryBefore(norm16);
1998 }
1999
hasCompBoundaryBefore(const uint8_t * src,const uint8_t * limit) const2000 UBool Normalizer2Impl::hasCompBoundaryBefore(const uint8_t *src, const uint8_t *limit) const {
2001 if (src == limit) {
2002 return TRUE;
2003 }
2004 uint16_t norm16;
2005 UCPTRIE_FAST_U8_NEXT(normTrie, UCPTRIE_16, src, limit, norm16);
2006 return norm16HasCompBoundaryBefore(norm16);
2007 }
2008
hasCompBoundaryAfter(const UChar * start,const UChar * p,UBool onlyContiguous) const2009 UBool Normalizer2Impl::hasCompBoundaryAfter(const UChar *start, const UChar *p,
2010 UBool onlyContiguous) const {
2011 if (start == p) {
2012 return TRUE;
2013 }
2014 UChar32 c;
2015 uint16_t norm16;
2016 UCPTRIE_FAST_U16_PREV(normTrie, UCPTRIE_16, start, p, c, norm16);
2017 return norm16HasCompBoundaryAfter(norm16, onlyContiguous);
2018 }
2019
hasCompBoundaryAfter(const uint8_t * start,const uint8_t * p,UBool onlyContiguous) const2020 UBool Normalizer2Impl::hasCompBoundaryAfter(const uint8_t *start, const uint8_t *p,
2021 UBool onlyContiguous) const {
2022 if (start == p) {
2023 return TRUE;
2024 }
2025 uint16_t norm16;
2026 UCPTRIE_FAST_U8_PREV(normTrie, UCPTRIE_16, start, p, norm16);
2027 return norm16HasCompBoundaryAfter(norm16, onlyContiguous);
2028 }
2029
findPreviousCompBoundary(const UChar * start,const UChar * p,UBool onlyContiguous) const2030 const UChar *Normalizer2Impl::findPreviousCompBoundary(const UChar *start, const UChar *p,
2031 UBool onlyContiguous) const {
2032 while (p != start) {
2033 const UChar *codePointLimit = p;
2034 UChar32 c;
2035 uint16_t norm16;
2036 UCPTRIE_FAST_U16_PREV(normTrie, UCPTRIE_16, start, p, c, norm16);
2037 if (norm16HasCompBoundaryAfter(norm16, onlyContiguous)) {
2038 return codePointLimit;
2039 }
2040 if (hasCompBoundaryBefore(c, norm16)) {
2041 return p;
2042 }
2043 }
2044 return p;
2045 }
2046
findNextCompBoundary(const UChar * p,const UChar * limit,UBool onlyContiguous) const2047 const UChar *Normalizer2Impl::findNextCompBoundary(const UChar *p, const UChar *limit,
2048 UBool onlyContiguous) const {
2049 while (p != limit) {
2050 const UChar *codePointStart = p;
2051 UChar32 c;
2052 uint16_t norm16;
2053 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, p, limit, c, norm16);
2054 if (hasCompBoundaryBefore(c, norm16)) {
2055 return codePointStart;
2056 }
2057 if (norm16HasCompBoundaryAfter(norm16, onlyContiguous)) {
2058 return p;
2059 }
2060 }
2061 return p;
2062 }
2063
getPreviousTrailCC(const UChar * start,const UChar * p) const2064 uint8_t Normalizer2Impl::getPreviousTrailCC(const UChar *start, const UChar *p) const {
2065 if (start == p) {
2066 return 0;
2067 }
2068 int32_t i = (int32_t)(p - start);
2069 UChar32 c;
2070 U16_PREV(start, 0, i, c);
2071 return (uint8_t)getFCD16(c);
2072 }
2073
getPreviousTrailCC(const uint8_t * start,const uint8_t * p) const2074 uint8_t Normalizer2Impl::getPreviousTrailCC(const uint8_t *start, const uint8_t *p) const {
2075 if (start == p) {
2076 return 0;
2077 }
2078 int32_t i = (int32_t)(p - start);
2079 UChar32 c;
2080 U8_PREV(start, 0, i, c);
2081 return (uint8_t)getFCD16(c);
2082 }
2083
2084 // Note: normalizer2impl.cpp r30982 (2011-nov-27)
2085 // still had getFCDTrie() which built and cached an FCD trie.
2086 // That provided faster access to FCD data than getFCD16FromNormData()
2087 // but required synchronization and consumed some 10kB of heap memory
2088 // in any process that uses FCD (e.g., via collation).
2089 // minDecompNoCP etc. and smallFCD[] are intended to help with any loss of performance,
2090 // at least for ASCII & CJK.
2091
2092 // Gets the FCD value from the regular normalization data.
getFCD16FromNormData(UChar32 c) const2093 uint16_t Normalizer2Impl::getFCD16FromNormData(UChar32 c) const {
2094 uint16_t norm16=getNorm16(c);
2095 if (norm16 >= limitNoNo) {
2096 if(norm16>=MIN_NORMAL_MAYBE_YES) {
2097 // combining mark
2098 norm16=getCCFromNormalYesOrMaybe(norm16);
2099 return norm16|(norm16<<8);
2100 } else if(norm16>=minMaybeYes) {
2101 return 0;
2102 } else { // isDecompNoAlgorithmic(norm16)
2103 uint16_t deltaTrailCC = norm16 & DELTA_TCCC_MASK;
2104 if (deltaTrailCC <= DELTA_TCCC_1) {
2105 return deltaTrailCC >> OFFSET_SHIFT;
2106 }
2107 // Maps to an isCompYesAndZeroCC.
2108 c=mapAlgorithmic(c, norm16);
2109 norm16=getRawNorm16(c);
2110 }
2111 }
2112 if(norm16<=minYesNo || isHangulLVT(norm16)) {
2113 // no decomposition or Hangul syllable, all zeros
2114 return 0;
2115 }
2116 // c decomposes, get everything from the variable-length extra data
2117 const uint16_t *mapping=getMapping(norm16);
2118 uint16_t firstUnit=*mapping;
2119 norm16=firstUnit>>8; // tccc
2120 if(firstUnit&MAPPING_HAS_CCC_LCCC_WORD) {
2121 norm16|=*(mapping-1)&0xff00; // lccc
2122 }
2123 return norm16;
2124 }
2125
2126 // Dual functionality:
2127 // buffer!=NULL: normalize
2128 // buffer==NULL: isNormalized/quickCheck/spanQuickCheckYes
2129 const UChar *
makeFCD(const UChar * src,const UChar * limit,ReorderingBuffer * buffer,UErrorCode & errorCode) const2130 Normalizer2Impl::makeFCD(const UChar *src, const UChar *limit,
2131 ReorderingBuffer *buffer,
2132 UErrorCode &errorCode) const {
2133 // Tracks the last FCD-safe boundary, before lccc=0 or after properly-ordered tccc<=1.
2134 // Similar to the prevBoundary in the compose() implementation.
2135 const UChar *prevBoundary=src;
2136 int32_t prevFCD16=0;
2137 if(limit==NULL) {
2138 src=copyLowPrefixFromNulTerminated(src, minLcccCP, buffer, errorCode);
2139 if(U_FAILURE(errorCode)) {
2140 return src;
2141 }
2142 if(prevBoundary<src) {
2143 prevBoundary=src;
2144 // We know that the previous character's lccc==0.
2145 // Fetching the fcd16 value was deferred for this below-U+0300 code point.
2146 prevFCD16=getFCD16(*(src-1));
2147 if(prevFCD16>1) {
2148 --prevBoundary;
2149 }
2150 }
2151 limit=u_strchr(src, 0);
2152 }
2153
2154 // Note: In this function we use buffer->appendZeroCC() because we track
2155 // the lead and trail combining classes here, rather than leaving it to
2156 // the ReorderingBuffer.
2157 // The exception is the call to decomposeShort() which uses the buffer
2158 // in the normal way.
2159
2160 const UChar *prevSrc;
2161 UChar32 c=0;
2162 uint16_t fcd16=0;
2163
2164 for(;;) {
2165 // count code units with lccc==0
2166 for(prevSrc=src; src!=limit;) {
2167 if((c=*src)<minLcccCP) {
2168 prevFCD16=~c;
2169 ++src;
2170 } else if(!singleLeadMightHaveNonZeroFCD16(c)) {
2171 prevFCD16=0;
2172 ++src;
2173 } else {
2174 if(U16_IS_LEAD(c)) {
2175 UChar c2;
2176 if((src+1)!=limit && U16_IS_TRAIL(c2=src[1])) {
2177 c=U16_GET_SUPPLEMENTARY(c, c2);
2178 }
2179 }
2180 if((fcd16=getFCD16FromNormData(c))<=0xff) {
2181 prevFCD16=fcd16;
2182 src+=U16_LENGTH(c);
2183 } else {
2184 break;
2185 }
2186 }
2187 }
2188 // copy these code units all at once
2189 if(src!=prevSrc) {
2190 if(buffer!=NULL && !buffer->appendZeroCC(prevSrc, src, errorCode)) {
2191 break;
2192 }
2193 if(src==limit) {
2194 break;
2195 }
2196 prevBoundary=src;
2197 // We know that the previous character's lccc==0.
2198 if(prevFCD16<0) {
2199 // Fetching the fcd16 value was deferred for this below-minLcccCP code point.
2200 UChar32 prev=~prevFCD16;
2201 if(prev<minDecompNoCP) {
2202 prevFCD16=0;
2203 } else {
2204 prevFCD16=getFCD16FromNormData(prev);
2205 if(prevFCD16>1) {
2206 --prevBoundary;
2207 }
2208 }
2209 } else {
2210 const UChar *p=src-1;
2211 if(U16_IS_TRAIL(*p) && prevSrc<p && U16_IS_LEAD(*(p-1))) {
2212 --p;
2213 // Need to fetch the previous character's FCD value because
2214 // prevFCD16 was just for the trail surrogate code point.
2215 prevFCD16=getFCD16FromNormData(U16_GET_SUPPLEMENTARY(p[0], p[1]));
2216 // Still known to have lccc==0 because its lead surrogate unit had lccc==0.
2217 }
2218 if(prevFCD16>1) {
2219 prevBoundary=p;
2220 }
2221 }
2222 // The start of the current character (c).
2223 prevSrc=src;
2224 } else if(src==limit) {
2225 break;
2226 }
2227
2228 src+=U16_LENGTH(c);
2229 // The current character (c) at [prevSrc..src[ has a non-zero lead combining class.
2230 // Check for proper order, and decompose locally if necessary.
2231 if((prevFCD16&0xff)<=(fcd16>>8)) {
2232 // proper order: prev tccc <= current lccc
2233 if((fcd16&0xff)<=1) {
2234 prevBoundary=src;
2235 }
2236 if(buffer!=NULL && !buffer->appendZeroCC(c, errorCode)) {
2237 break;
2238 }
2239 prevFCD16=fcd16;
2240 continue;
2241 } else if(buffer==NULL) {
2242 return prevBoundary; // quick check "no"
2243 } else {
2244 /*
2245 * Back out the part of the source that we copied or appended
2246 * already but is now going to be decomposed.
2247 * prevSrc is set to after what was copied/appended.
2248 */
2249 buffer->removeSuffix((int32_t)(prevSrc-prevBoundary));
2250 /*
2251 * Find the part of the source that needs to be decomposed,
2252 * up to the next safe boundary.
2253 */
2254 src=findNextFCDBoundary(src, limit);
2255 /*
2256 * The source text does not fulfill the conditions for FCD.
2257 * Decompose and reorder a limited piece of the text.
2258 */
2259 decomposeShort(prevBoundary, src, FALSE, FALSE, *buffer, errorCode);
2260 if (U_FAILURE(errorCode)) {
2261 break;
2262 }
2263 prevBoundary=src;
2264 prevFCD16=0;
2265 }
2266 }
2267 return src;
2268 }
2269
makeFCDAndAppend(const UChar * src,const UChar * limit,UBool doMakeFCD,UnicodeString & safeMiddle,ReorderingBuffer & buffer,UErrorCode & errorCode) const2270 void Normalizer2Impl::makeFCDAndAppend(const UChar *src, const UChar *limit,
2271 UBool doMakeFCD,
2272 UnicodeString &safeMiddle,
2273 ReorderingBuffer &buffer,
2274 UErrorCode &errorCode) const {
2275 if(!buffer.isEmpty()) {
2276 const UChar *firstBoundaryInSrc=findNextFCDBoundary(src, limit);
2277 if(src!=firstBoundaryInSrc) {
2278 const UChar *lastBoundaryInDest=findPreviousFCDBoundary(buffer.getStart(),
2279 buffer.getLimit());
2280 int32_t destSuffixLength=(int32_t)(buffer.getLimit()-lastBoundaryInDest);
2281 UnicodeString middle(lastBoundaryInDest, destSuffixLength);
2282 buffer.removeSuffix(destSuffixLength);
2283 safeMiddle=middle;
2284 middle.append(src, (int32_t)(firstBoundaryInSrc-src));
2285 const UChar *middleStart=middle.getBuffer();
2286 makeFCD(middleStart, middleStart+middle.length(), &buffer, errorCode);
2287 if(U_FAILURE(errorCode)) {
2288 return;
2289 }
2290 src=firstBoundaryInSrc;
2291 }
2292 }
2293 if(doMakeFCD) {
2294 makeFCD(src, limit, &buffer, errorCode);
2295 } else {
2296 if(limit==NULL) { // appendZeroCC() needs limit!=NULL
2297 limit=u_strchr(src, 0);
2298 }
2299 buffer.appendZeroCC(src, limit, errorCode);
2300 }
2301 }
2302
findPreviousFCDBoundary(const UChar * start,const UChar * p) const2303 const UChar *Normalizer2Impl::findPreviousFCDBoundary(const UChar *start, const UChar *p) const {
2304 while(start<p) {
2305 const UChar *codePointLimit = p;
2306 UChar32 c;
2307 uint16_t norm16;
2308 UCPTRIE_FAST_U16_PREV(normTrie, UCPTRIE_16, start, p, c, norm16);
2309 if (c < minDecompNoCP || norm16HasDecompBoundaryAfter(norm16)) {
2310 return codePointLimit;
2311 }
2312 if (norm16HasDecompBoundaryBefore(norm16)) {
2313 return p;
2314 }
2315 }
2316 return p;
2317 }
2318
findNextFCDBoundary(const UChar * p,const UChar * limit) const2319 const UChar *Normalizer2Impl::findNextFCDBoundary(const UChar *p, const UChar *limit) const {
2320 while(p<limit) {
2321 const UChar *codePointStart=p;
2322 UChar32 c;
2323 uint16_t norm16;
2324 UCPTRIE_FAST_U16_NEXT(normTrie, UCPTRIE_16, p, limit, c, norm16);
2325 if (c < minLcccCP || norm16HasDecompBoundaryBefore(norm16)) {
2326 return codePointStart;
2327 }
2328 if (norm16HasDecompBoundaryAfter(norm16)) {
2329 return p;
2330 }
2331 }
2332 return p;
2333 }
2334
2335 // CanonicalIterator data -------------------------------------------------- ***
2336
CanonIterData(UErrorCode & errorCode)2337 CanonIterData::CanonIterData(UErrorCode &errorCode) :
2338 mutableTrie(umutablecptrie_open(0, 0, &errorCode)), trie(nullptr),
2339 canonStartSets(uprv_deleteUObject, NULL, errorCode) {}
2340
~CanonIterData()2341 CanonIterData::~CanonIterData() {
2342 umutablecptrie_close(mutableTrie);
2343 ucptrie_close(trie);
2344 }
2345
addToStartSet(UChar32 origin,UChar32 decompLead,UErrorCode & errorCode)2346 void CanonIterData::addToStartSet(UChar32 origin, UChar32 decompLead, UErrorCode &errorCode) {
2347 uint32_t canonValue = umutablecptrie_get(mutableTrie, decompLead);
2348 if((canonValue&(CANON_HAS_SET|CANON_VALUE_MASK))==0 && origin!=0) {
2349 // origin is the first character whose decomposition starts with
2350 // the character for which we are setting the value.
2351 umutablecptrie_set(mutableTrie, decompLead, canonValue|origin, &errorCode);
2352 } else {
2353 // origin is not the first character, or it is U+0000.
2354 UnicodeSet *set;
2355 if((canonValue&CANON_HAS_SET)==0) {
2356 set=new UnicodeSet;
2357 if(set==NULL) {
2358 errorCode=U_MEMORY_ALLOCATION_ERROR;
2359 return;
2360 }
2361 UChar32 firstOrigin=(UChar32)(canonValue&CANON_VALUE_MASK);
2362 canonValue=(canonValue&~CANON_VALUE_MASK)|CANON_HAS_SET|(uint32_t)canonStartSets.size();
2363 umutablecptrie_set(mutableTrie, decompLead, canonValue, &errorCode);
2364 canonStartSets.addElement(set, errorCode);
2365 if(firstOrigin!=0) {
2366 set->add(firstOrigin);
2367 }
2368 } else {
2369 set=(UnicodeSet *)canonStartSets[(int32_t)(canonValue&CANON_VALUE_MASK)];
2370 }
2371 set->add(origin);
2372 }
2373 }
2374
2375 // C++ class for friend access to private Normalizer2Impl members.
2376 class InitCanonIterData {
2377 public:
2378 static void doInit(Normalizer2Impl *impl, UErrorCode &errorCode);
2379 };
2380
2381 U_CDECL_BEGIN
2382
2383 // UInitOnce instantiation function for CanonIterData
2384 static void U_CALLCONV
initCanonIterData(Normalizer2Impl * impl,UErrorCode & errorCode)2385 initCanonIterData(Normalizer2Impl *impl, UErrorCode &errorCode) {
2386 InitCanonIterData::doInit(impl, errorCode);
2387 }
2388
2389 U_CDECL_END
2390
doInit(Normalizer2Impl * impl,UErrorCode & errorCode)2391 void InitCanonIterData::doInit(Normalizer2Impl *impl, UErrorCode &errorCode) {
2392 U_ASSERT(impl->fCanonIterData == NULL);
2393 impl->fCanonIterData = new CanonIterData(errorCode);
2394 if (impl->fCanonIterData == NULL) {
2395 errorCode=U_MEMORY_ALLOCATION_ERROR;
2396 }
2397 if (U_SUCCESS(errorCode)) {
2398 UChar32 start = 0, end;
2399 uint32_t value;
2400 while ((end = ucptrie_getRange(impl->normTrie, start,
2401 UCPMAP_RANGE_FIXED_LEAD_SURROGATES, Normalizer2Impl::INERT,
2402 nullptr, nullptr, &value)) >= 0) {
2403 // Call Normalizer2Impl::makeCanonIterDataFromNorm16() for a range of same-norm16 characters.
2404 if (value != Normalizer2Impl::INERT) {
2405 impl->makeCanonIterDataFromNorm16(start, end, value, *impl->fCanonIterData, errorCode);
2406 }
2407 start = end + 1;
2408 }
2409 #ifdef UCPTRIE_DEBUG
2410 umutablecptrie_setName(impl->fCanonIterData->mutableTrie, "CanonIterData");
2411 #endif
2412 impl->fCanonIterData->trie = umutablecptrie_buildImmutable(
2413 impl->fCanonIterData->mutableTrie, UCPTRIE_TYPE_SMALL, UCPTRIE_VALUE_BITS_32, &errorCode);
2414 umutablecptrie_close(impl->fCanonIterData->mutableTrie);
2415 impl->fCanonIterData->mutableTrie = nullptr;
2416 }
2417 if (U_FAILURE(errorCode)) {
2418 delete impl->fCanonIterData;
2419 impl->fCanonIterData = NULL;
2420 }
2421 }
2422
makeCanonIterDataFromNorm16(UChar32 start,UChar32 end,const uint16_t norm16,CanonIterData & newData,UErrorCode & errorCode) const2423 void Normalizer2Impl::makeCanonIterDataFromNorm16(UChar32 start, UChar32 end, const uint16_t norm16,
2424 CanonIterData &newData,
2425 UErrorCode &errorCode) const {
2426 if(isInert(norm16) || (minYesNo<=norm16 && norm16<minNoNo)) {
2427 // Inert, or 2-way mapping (including Hangul syllable).
2428 // We do not write a canonStartSet for any yesNo character.
2429 // Composites from 2-way mappings are added at runtime from the
2430 // starter's compositions list, and the other characters in
2431 // 2-way mappings get CANON_NOT_SEGMENT_STARTER set because they are
2432 // "maybe" characters.
2433 return;
2434 }
2435 for(UChar32 c=start; c<=end; ++c) {
2436 uint32_t oldValue = umutablecptrie_get(newData.mutableTrie, c);
2437 uint32_t newValue=oldValue;
2438 if(isMaybeOrNonZeroCC(norm16)) {
2439 // not a segment starter if it occurs in a decomposition or has cc!=0
2440 newValue|=CANON_NOT_SEGMENT_STARTER;
2441 if(norm16<MIN_NORMAL_MAYBE_YES) {
2442 newValue|=CANON_HAS_COMPOSITIONS;
2443 }
2444 } else if(norm16<minYesNo) {
2445 newValue|=CANON_HAS_COMPOSITIONS;
2446 } else {
2447 // c has a one-way decomposition
2448 UChar32 c2=c;
2449 // Do not modify the whole-range norm16 value.
2450 uint16_t norm16_2=norm16;
2451 if (isDecompNoAlgorithmic(norm16_2)) {
2452 // Maps to an isCompYesAndZeroCC.
2453 c2 = mapAlgorithmic(c2, norm16_2);
2454 norm16_2 = getRawNorm16(c2);
2455 // No compatibility mappings for the CanonicalIterator.
2456 U_ASSERT(!(isHangulLV(norm16_2) || isHangulLVT(norm16_2)));
2457 }
2458 if (norm16_2 > minYesNo) {
2459 // c decomposes, get everything from the variable-length extra data
2460 const uint16_t *mapping=getMapping(norm16_2);
2461 uint16_t firstUnit=*mapping;
2462 int32_t length=firstUnit&MAPPING_LENGTH_MASK;
2463 if((firstUnit&MAPPING_HAS_CCC_LCCC_WORD)!=0) {
2464 if(c==c2 && (*(mapping-1)&0xff)!=0) {
2465 newValue|=CANON_NOT_SEGMENT_STARTER; // original c has cc!=0
2466 }
2467 }
2468 // Skip empty mappings (no characters in the decomposition).
2469 if(length!=0) {
2470 ++mapping; // skip over the firstUnit
2471 // add c to first code point's start set
2472 int32_t i=0;
2473 U16_NEXT_UNSAFE(mapping, i, c2);
2474 newData.addToStartSet(c, c2, errorCode);
2475 // Set CANON_NOT_SEGMENT_STARTER for each remaining code point of a
2476 // one-way mapping. A 2-way mapping is possible here after
2477 // intermediate algorithmic mapping.
2478 if(norm16_2>=minNoNo) {
2479 while(i<length) {
2480 U16_NEXT_UNSAFE(mapping, i, c2);
2481 uint32_t c2Value = umutablecptrie_get(newData.mutableTrie, c2);
2482 if((c2Value&CANON_NOT_SEGMENT_STARTER)==0) {
2483 umutablecptrie_set(newData.mutableTrie, c2,
2484 c2Value|CANON_NOT_SEGMENT_STARTER, &errorCode);
2485 }
2486 }
2487 }
2488 }
2489 } else {
2490 // c decomposed to c2 algorithmically; c has cc==0
2491 newData.addToStartSet(c, c2, errorCode);
2492 }
2493 }
2494 if(newValue!=oldValue) {
2495 umutablecptrie_set(newData.mutableTrie, c, newValue, &errorCode);
2496 }
2497 }
2498 }
2499
ensureCanonIterData(UErrorCode & errorCode) const2500 UBool Normalizer2Impl::ensureCanonIterData(UErrorCode &errorCode) const {
2501 // Logically const: Synchronized instantiation.
2502 Normalizer2Impl *me=const_cast<Normalizer2Impl *>(this);
2503 umtx_initOnce(me->fCanonIterDataInitOnce, &initCanonIterData, me, errorCode);
2504 return U_SUCCESS(errorCode);
2505 }
2506
getCanonValue(UChar32 c) const2507 int32_t Normalizer2Impl::getCanonValue(UChar32 c) const {
2508 return (int32_t)ucptrie_get(fCanonIterData->trie, c);
2509 }
2510
getCanonStartSet(int32_t n) const2511 const UnicodeSet &Normalizer2Impl::getCanonStartSet(int32_t n) const {
2512 return *(const UnicodeSet *)fCanonIterData->canonStartSets[n];
2513 }
2514
isCanonSegmentStarter(UChar32 c) const2515 UBool Normalizer2Impl::isCanonSegmentStarter(UChar32 c) const {
2516 return getCanonValue(c)>=0;
2517 }
2518
getCanonStartSet(UChar32 c,UnicodeSet & set) const2519 UBool Normalizer2Impl::getCanonStartSet(UChar32 c, UnicodeSet &set) const {
2520 int32_t canonValue=getCanonValue(c)&~CANON_NOT_SEGMENT_STARTER;
2521 if(canonValue==0) {
2522 return FALSE;
2523 }
2524 set.clear();
2525 int32_t value=canonValue&CANON_VALUE_MASK;
2526 if((canonValue&CANON_HAS_SET)!=0) {
2527 set.addAll(getCanonStartSet(value));
2528 } else if(value!=0) {
2529 set.add(value);
2530 }
2531 if((canonValue&CANON_HAS_COMPOSITIONS)!=0) {
2532 uint16_t norm16=getRawNorm16(c);
2533 if(norm16==JAMO_L) {
2534 UChar32 syllable=
2535 (UChar32)(Hangul::HANGUL_BASE+(c-Hangul::JAMO_L_BASE)*Hangul::JAMO_VT_COUNT);
2536 set.add(syllable, syllable+Hangul::JAMO_VT_COUNT-1);
2537 } else {
2538 addComposites(getCompositionsList(norm16), set);
2539 }
2540 }
2541 return TRUE;
2542 }
2543
2544 U_NAMESPACE_END
2545
2546 // Normalizer2 data swapping ----------------------------------------------- ***
2547
2548 U_NAMESPACE_USE
2549
2550 U_CAPI int32_t U_EXPORT2
unorm2_swap(const UDataSwapper * ds,const void * inData,int32_t length,void * outData,UErrorCode * pErrorCode)2551 unorm2_swap(const UDataSwapper *ds,
2552 const void *inData, int32_t length, void *outData,
2553 UErrorCode *pErrorCode) {
2554 const UDataInfo *pInfo;
2555 int32_t headerSize;
2556
2557 const uint8_t *inBytes;
2558 uint8_t *outBytes;
2559
2560 const int32_t *inIndexes;
2561 int32_t indexes[Normalizer2Impl::IX_TOTAL_SIZE+1];
2562
2563 int32_t i, offset, nextOffset, size;
2564
2565 /* udata_swapDataHeader checks the arguments */
2566 headerSize=udata_swapDataHeader(ds, inData, length, outData, pErrorCode);
2567 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
2568 return 0;
2569 }
2570
2571 /* check data format and format version */
2572 pInfo=(const UDataInfo *)((const char *)inData+4);
2573 uint8_t formatVersion0=pInfo->formatVersion[0];
2574 if(!(
2575 pInfo->dataFormat[0]==0x4e && /* dataFormat="Nrm2" */
2576 pInfo->dataFormat[1]==0x72 &&
2577 pInfo->dataFormat[2]==0x6d &&
2578 pInfo->dataFormat[3]==0x32 &&
2579 (1<=formatVersion0 && formatVersion0<=4)
2580 )) {
2581 udata_printError(ds, "unorm2_swap(): data format %02x.%02x.%02x.%02x (format version %02x) is not recognized as Normalizer2 data\n",
2582 pInfo->dataFormat[0], pInfo->dataFormat[1],
2583 pInfo->dataFormat[2], pInfo->dataFormat[3],
2584 pInfo->formatVersion[0]);
2585 *pErrorCode=U_UNSUPPORTED_ERROR;
2586 return 0;
2587 }
2588
2589 inBytes=(const uint8_t *)inData+headerSize;
2590 outBytes=(uint8_t *)outData+headerSize;
2591
2592 inIndexes=(const int32_t *)inBytes;
2593 int32_t minIndexesLength;
2594 if(formatVersion0==1) {
2595 minIndexesLength=Normalizer2Impl::IX_MIN_MAYBE_YES+1;
2596 } else if(formatVersion0==2) {
2597 minIndexesLength=Normalizer2Impl::IX_MIN_YES_NO_MAPPINGS_ONLY+1;
2598 } else {
2599 minIndexesLength=Normalizer2Impl::IX_MIN_LCCC_CP+1;
2600 }
2601
2602 if(length>=0) {
2603 length-=headerSize;
2604 if(length<minIndexesLength*4) {
2605 udata_printError(ds, "unorm2_swap(): too few bytes (%d after header) for Normalizer2 data\n",
2606 length);
2607 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
2608 return 0;
2609 }
2610 }
2611
2612 /* read the first few indexes */
2613 for(i=0; i<UPRV_LENGTHOF(indexes); ++i) {
2614 indexes[i]=udata_readInt32(ds, inIndexes[i]);
2615 }
2616
2617 /* get the total length of the data */
2618 size=indexes[Normalizer2Impl::IX_TOTAL_SIZE];
2619
2620 if(length>=0) {
2621 if(length<size) {
2622 udata_printError(ds, "unorm2_swap(): too few bytes (%d after header) for all of Normalizer2 data\n",
2623 length);
2624 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
2625 return 0;
2626 }
2627
2628 /* copy the data for inaccessible bytes */
2629 if(inBytes!=outBytes) {
2630 uprv_memcpy(outBytes, inBytes, size);
2631 }
2632
2633 offset=0;
2634
2635 /* swap the int32_t indexes[] */
2636 nextOffset=indexes[Normalizer2Impl::IX_NORM_TRIE_OFFSET];
2637 ds->swapArray32(ds, inBytes, nextOffset-offset, outBytes, pErrorCode);
2638 offset=nextOffset;
2639
2640 /* swap the trie */
2641 nextOffset=indexes[Normalizer2Impl::IX_EXTRA_DATA_OFFSET];
2642 utrie_swapAnyVersion(ds, inBytes+offset, nextOffset-offset, outBytes+offset, pErrorCode);
2643 offset=nextOffset;
2644
2645 /* swap the uint16_t extraData[] */
2646 nextOffset=indexes[Normalizer2Impl::IX_SMALL_FCD_OFFSET];
2647 ds->swapArray16(ds, inBytes+offset, nextOffset-offset, outBytes+offset, pErrorCode);
2648 offset=nextOffset;
2649
2650 /* no need to swap the uint8_t smallFCD[] (new in formatVersion 2) */
2651 nextOffset=indexes[Normalizer2Impl::IX_SMALL_FCD_OFFSET+1];
2652 offset=nextOffset;
2653
2654 U_ASSERT(offset==size);
2655 }
2656
2657 return headerSize+size;
2658 }
2659
2660 #endif // !UCONFIG_NO_NORMALIZATION
2661