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