1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
4 *******************************************************************************
6 * Copyright (C) 2009-2014, International Business Machines
7 * Corporation and others. All Rights Reserved.
9 *******************************************************************************
10 * file name: normalizer2impl.cpp
12 * tab size: 8 (not used)
15 * created on: 2009nov22
16 * created by: Markus W. Scherer
19 #include "unicode/utypes.h"
21 #if !UCONFIG_NO_NORMALIZATION
23 #include "unicode/normalizer2.h"
24 #include "unicode/udata.h"
25 #include "unicode/ustring.h"
26 #include "unicode/utf16.h"
29 #include "normalizer2impl.h"
38 // ReorderingBuffer -------------------------------------------------------- ***
40 UBool
ReorderingBuffer::init(int32_t destCapacity
, UErrorCode
&errorCode
) {
41 int32_t length
=str
.length();
42 start
=str
.getBuffer(destCapacity
);
44 // getBuffer() already did str.setToBogus()
45 errorCode
=U_MEMORY_ALLOCATION_ERROR
;
49 remainingCapacity
=str
.getCapacity()-length
;
56 // Set reorderStart after the last code point with cc<=1 if there is one.
58 while(previousCC()>1) {}
60 reorderStart
=codePointLimit
;
65 UBool
ReorderingBuffer::equals(const UChar
*otherStart
, const UChar
*otherLimit
) const {
66 int32_t length
=(int32_t)(limit
-start
);
68 length
==(int32_t)(otherLimit
-otherStart
) &&
69 0==u_memcmp(start
, otherStart
, length
);
72 UBool
ReorderingBuffer::appendSupplementary(UChar32 c
, uint8_t cc
, UErrorCode
&errorCode
) {
73 if(remainingCapacity
<2 && !resize(2, errorCode
)) {
76 if(lastCC
<=cc
|| cc
==0) {
78 limit
[1]=U16_TRAIL(c
);
91 UBool
ReorderingBuffer::append(const UChar
*s
, int32_t length
,
92 uint8_t leadCC
, uint8_t trailCC
,
93 UErrorCode
&errorCode
) {
97 if(remainingCapacity
<length
&& !resize(length
, errorCode
)) {
100 remainingCapacity
-=length
;
101 if(lastCC
<=leadCC
|| leadCC
==0) {
103 reorderStart
=limit
+length
;
104 } else if(leadCC
<=1) {
105 reorderStart
=limit
+1; // Ok if not a code point boundary.
107 const UChar
*sLimit
=s
+length
;
108 do { *limit
++=*s
++; } while(s
!=sLimit
);
113 U16_NEXT(s
, i
, length
, c
);
114 insert(c
, leadCC
); // insert first code point
116 U16_NEXT(s
, i
, length
, c
);
118 // s must be in NFD, otherwise we need to use getCC().
119 leadCC
=Normalizer2Impl::getCCFromYesOrMaybe(impl
.getNorm16(c
));
123 append(c
, leadCC
, errorCode
);
129 UBool
ReorderingBuffer::appendZeroCC(UChar32 c
, UErrorCode
&errorCode
) {
130 int32_t cpLength
=U16_LENGTH(c
);
131 if(remainingCapacity
<cpLength
&& !resize(cpLength
, errorCode
)) {
134 remainingCapacity
-=cpLength
;
138 limit
[0]=U16_LEAD(c
);
139 limit
[1]=U16_TRAIL(c
);
147 UBool
ReorderingBuffer::appendZeroCC(const UChar
*s
, const UChar
*sLimit
, UErrorCode
&errorCode
) {
151 int32_t length
=(int32_t)(sLimit
-s
);
152 if(remainingCapacity
<length
&& !resize(length
, errorCode
)) {
155 u_memcpy(limit
, s
, length
);
157 remainingCapacity
-=length
;
163 void ReorderingBuffer::remove() {
164 reorderStart
=limit
=start
;
165 remainingCapacity
=str
.getCapacity();
169 void ReorderingBuffer::removeSuffix(int32_t suffixLength
) {
170 if(suffixLength
<(limit
-start
)) {
172 remainingCapacity
+=suffixLength
;
175 remainingCapacity
=str
.getCapacity();
181 UBool
ReorderingBuffer::resize(int32_t appendLength
, UErrorCode
&errorCode
) {
182 int32_t reorderStartIndex
=(int32_t)(reorderStart
-start
);
183 int32_t length
=(int32_t)(limit
-start
);
184 str
.releaseBuffer(length
);
185 int32_t newCapacity
=length
+appendLength
;
186 int32_t doubleCapacity
=2*str
.getCapacity();
187 if(newCapacity
<doubleCapacity
) {
188 newCapacity
=doubleCapacity
;
190 if(newCapacity
<256) {
193 start
=str
.getBuffer(newCapacity
);
195 // getBuffer() already did str.setToBogus()
196 errorCode
=U_MEMORY_ALLOCATION_ERROR
;
199 reorderStart
=start
+reorderStartIndex
;
201 remainingCapacity
=str
.getCapacity()-length
;
205 void ReorderingBuffer::skipPrevious() {
206 codePointLimit
=codePointStart
;
207 UChar c
=*--codePointStart
;
208 if(U16_IS_TRAIL(c
) && start
<codePointStart
&& U16_IS_LEAD(*(codePointStart
-1))) {
213 uint8_t ReorderingBuffer::previousCC() {
214 codePointLimit
=codePointStart
;
215 if(reorderStart
>=codePointStart
) {
218 UChar32 c
=*--codePointStart
;
219 if(c
<Normalizer2Impl::MIN_CCC_LCCC_CP
) {
224 if(U16_IS_TRAIL(c
) && start
<codePointStart
&& U16_IS_LEAD(c2
=*(codePointStart
-1))) {
226 c
=U16_GET_SUPPLEMENTARY(c2
, c
);
228 return Normalizer2Impl::getCCFromYesOrMaybe(impl
.getNorm16(c
));
231 // Inserts c somewhere before the last character.
232 // Requires 0<cc<lastCC which implies reorderStart<limit.
233 void ReorderingBuffer::insert(UChar32 c
, uint8_t cc
) {
234 for(setIterator(), skipPrevious(); previousCC()>cc
;) {}
235 // insert c at codePointLimit, after the character with prevCC<=cc
237 UChar
*r
=limit
+=U16_LENGTH(c
);
240 } while(codePointLimit
!=q
);
241 writeCodePoint(q
, c
);
247 // Normalizer2Impl --------------------------------------------------------- ***
249 struct CanonIterData
: public UMemory
{
250 CanonIterData(UErrorCode
&errorCode
);
252 void addToStartSet(UChar32 origin
, UChar32 decompLead
, UErrorCode
&errorCode
);
254 UVector canonStartSets
; // contains UnicodeSet *
257 Normalizer2Impl::~Normalizer2Impl() {
258 delete fCanonIterData
;
262 Normalizer2Impl::init(const int32_t *inIndexes
, const UTrie2
*inTrie
,
263 const uint16_t *inExtraData
, const uint8_t *inSmallFCD
) {
264 minDecompNoCP
=inIndexes
[IX_MIN_DECOMP_NO_CP
];
265 minCompNoMaybeCP
=inIndexes
[IX_MIN_COMP_NO_MAYBE_CP
];
267 minYesNo
=inIndexes
[IX_MIN_YES_NO
];
268 minYesNoMappingsOnly
=inIndexes
[IX_MIN_YES_NO_MAPPINGS_ONLY
];
269 minNoNo
=inIndexes
[IX_MIN_NO_NO
];
270 limitNoNo
=inIndexes
[IX_LIMIT_NO_NO
];
271 minMaybeYes
=inIndexes
[IX_MIN_MAYBE_YES
];
275 maybeYesCompositions
=inExtraData
;
276 extraData
=maybeYesCompositions
+(MIN_NORMAL_MAYBE_YES
-minMaybeYes
);
281 // gennorm2 enforces lccc=0 for c<MIN_CCC_LCCC_CP=U+0300.
283 for(UChar c
=0; c
<0x180; bits
>>=1) {
285 bits
=smallFCD
[c
>>8]; // one byte per 0x100 code points
288 for(int i
=0; i
<0x20; ++i
, ++c
) {
289 tccc180
[c
]=(uint8_t)getFCD16FromNormData(c
);
292 uprv_memset(tccc180
+c
, 0, 0x20);
298 uint8_t Normalizer2Impl::getTrailCCFromCompYesAndZeroCC(const UChar
*cpStart
, const UChar
*cpLimit
) const {
300 if(cpStart
==(cpLimit
-1)) {
303 c
=U16_GET_SUPPLEMENTARY(cpStart
[0], cpStart
[1]);
305 uint16_t prevNorm16
=getNorm16(c
);
306 if(prevNorm16
<=minYesNo
) {
307 return 0; // yesYes and Hangul LV/LVT have ccc=tccc=0
309 return (uint8_t)(*getMapping(prevNorm16
)>>8); // tccc from yesNo
317 LcccContext(const Normalizer2Impl
&ni
, UnicodeSet
&s
) : impl(ni
), set(s
) {}
319 void handleRange(UChar32 start
, UChar32 end
, uint16_t norm16
) {
320 if(impl
.isAlgorithmicNoNo(norm16
)) {
321 // Range of code points with same-norm16-value algorithmic decompositions.
322 // They might have different non-zero FCD16 values.
324 uint16_t fcd16
=impl
.getFCD16(start
);
325 if(fcd16
>0xff) { set
.add(start
); }
326 } while(++start
<=end
);
328 uint16_t fcd16
=impl
.getFCD16(start
);
329 if(fcd16
>0xff) { set
.add(start
, end
); }
334 const Normalizer2Impl
&impl
;
338 struct PropertyStartsContext
{
339 PropertyStartsContext(const Normalizer2Impl
&ni
, const USetAdder
*adder
)
340 : impl(ni
), sa(adder
) {}
342 const Normalizer2Impl
&impl
;
350 static UBool U_CALLCONV
351 enumLcccRange(const void *context
, UChar32 start
, UChar32 end
, uint32_t value
) {
352 ((LcccContext
*)context
)->handleRange(start
, end
, (uint16_t)value
);
356 static UBool U_CALLCONV
357 enumNorm16PropertyStartsRange(const void *context
, UChar32 start
, UChar32 end
, uint32_t value
) {
358 /* add the start code point to the USet */
359 const PropertyStartsContext
*ctx
=(const PropertyStartsContext
*)context
;
360 const USetAdder
*sa
=ctx
->sa
;
361 sa
->add(sa
->set
, start
);
362 if(start
!=end
&& ctx
->impl
.isAlgorithmicNoNo((uint16_t)value
)) {
363 // Range of code points with same-norm16-value algorithmic decompositions.
364 // They might have different non-zero FCD16 values.
365 uint16_t prevFCD16
=ctx
->impl
.getFCD16(start
);
366 while(++start
<=end
) {
367 uint16_t fcd16
=ctx
->impl
.getFCD16(start
);
368 if(fcd16
!=prevFCD16
) {
369 sa
->add(sa
->set
, start
);
377 static UBool U_CALLCONV
378 enumPropertyStartsRange(const void *context
, UChar32 start
, UChar32
/*end*/, uint32_t /*value*/) {
379 /* add the start code point to the USet */
380 const USetAdder
*sa
=(const USetAdder
*)context
;
381 sa
->add(sa
->set
, start
);
385 static uint32_t U_CALLCONV
386 segmentStarterMapper(const void * /*context*/, uint32_t value
) {
387 return value
&CANON_NOT_SEGMENT_STARTER
;
393 Normalizer2Impl::addLcccChars(UnicodeSet
&set
) const {
394 /* add the start code point of each same-value range of each trie */
395 LcccContext
context(*this, set
);
396 utrie2_enum(normTrie
, NULL
, enumLcccRange
, &context
);
400 Normalizer2Impl::addPropertyStarts(const USetAdder
*sa
, UErrorCode
& /*errorCode*/) const {
401 /* add the start code point of each same-value range of each trie */
402 PropertyStartsContext
context(*this, sa
);
403 utrie2_enum(normTrie
, NULL
, enumNorm16PropertyStartsRange
, &context
);
405 /* add Hangul LV syllables and LV+1 because of skippables */
406 for(UChar c
=Hangul::HANGUL_BASE
; c
<Hangul::HANGUL_LIMIT
; c
+=Hangul::JAMO_T_COUNT
) {
408 sa
->add(sa
->set
, c
+1);
410 sa
->add(sa
->set
, Hangul::HANGUL_LIMIT
); /* add Hangul+1 to continue with other properties */
414 Normalizer2Impl::addCanonIterPropertyStarts(const USetAdder
*sa
, UErrorCode
&errorCode
) const {
415 /* add the start code point of each same-value range of the canonical iterator data trie */
416 if(ensureCanonIterData(errorCode
)) {
417 // currently only used for the SEGMENT_STARTER property
418 utrie2_enum(fCanonIterData
->trie
, segmentStarterMapper
, enumPropertyStartsRange
, sa
);
423 Normalizer2Impl::copyLowPrefixFromNulTerminated(const UChar
*src
,
424 UChar32 minNeedDataCP
,
425 ReorderingBuffer
*buffer
,
426 UErrorCode
&errorCode
) const {
427 // Make some effort to support NUL-terminated strings reasonably.
428 // Take the part of the fast quick check loop that does not look up
429 // data and check the first part of the string.
430 // After this prefix, determine the string length to simplify the rest
432 const UChar
*prevSrc
=src
;
434 while((c
=*src
++)<minNeedDataCP
&& c
!=0) {}
435 // Back out the last character for full processing.
439 buffer
->appendZeroCC(prevSrc
, src
, errorCode
);
446 Normalizer2Impl::decompose(const UnicodeString
&src
, UnicodeString
&dest
,
447 UErrorCode
&errorCode
) const {
448 if(U_FAILURE(errorCode
)) {
452 const UChar
*sArray
=src
.getBuffer();
453 if(&dest
==&src
|| sArray
==NULL
) {
454 errorCode
=U_ILLEGAL_ARGUMENT_ERROR
;
458 decompose(sArray
, sArray
+src
.length(), dest
, src
.length(), errorCode
);
463 Normalizer2Impl::decompose(const UChar
*src
, const UChar
*limit
,
465 int32_t destLengthEstimate
,
466 UErrorCode
&errorCode
) const {
467 if(destLengthEstimate
<0 && limit
!=NULL
) {
468 destLengthEstimate
=(int32_t)(limit
-src
);
471 ReorderingBuffer
buffer(*this, dest
);
472 if(buffer
.init(destLengthEstimate
, errorCode
)) {
473 decompose(src
, limit
, &buffer
, errorCode
);
477 // Dual functionality:
478 // buffer!=NULL: normalize
479 // buffer==NULL: isNormalized/spanQuickCheckYes
481 Normalizer2Impl::decompose(const UChar
*src
, const UChar
*limit
,
482 ReorderingBuffer
*buffer
,
483 UErrorCode
&errorCode
) const {
484 UChar32 minNoCP
=minDecompNoCP
;
486 src
=copyLowPrefixFromNulTerminated(src
, minNoCP
, buffer
, errorCode
);
487 if(U_FAILURE(errorCode
)) {
490 limit
=u_strchr(src
, 0);
493 const UChar
*prevSrc
;
497 // only for quick check
498 const UChar
*prevBoundary
=src
;
502 // count code units below the minimum or with irrelevant data for the quick check
503 for(prevSrc
=src
; src
!=limit
;) {
504 if( (c
=*src
)<minNoCP
||
505 isMostDecompYesAndZeroCC(norm16
=UTRIE2_GET16_FROM_U16_SINGLE_LEAD(normTrie
, c
))
508 } else if(!U16_IS_SURROGATE(c
)) {
512 if(U16_IS_SURROGATE_LEAD(c
)) {
513 if((src
+1)!=limit
&& U16_IS_TRAIL(c2
=src
[1])) {
514 c
=U16_GET_SUPPLEMENTARY(c
, c2
);
516 } else /* trail surrogate */ {
517 if(prevSrc
<src
&& U16_IS_LEAD(c2
=*(src
-1))) {
519 c
=U16_GET_SUPPLEMENTARY(c2
, c
);
522 if(isMostDecompYesAndZeroCC(norm16
=getNorm16(c
))) {
529 // copy these code units all at once
532 if(!buffer
->appendZeroCC(prevSrc
, src
, errorCode
)) {
544 // Check one above-minimum, relevant code point.
547 if(!decompose(c
, norm16
, *buffer
, errorCode
)) {
551 if(isDecompYes(norm16
)) {
552 uint8_t cc
=getCCFromYesOrMaybe(norm16
);
553 if(prevCC
<=cc
|| cc
==0) {
561 return prevBoundary
; // "no" or cc out of order
567 // Decompose a short piece of text which is likely to contain characters that
568 // fail the quick check loop and/or where the quick check loop's overhead
569 // is unlikely to be amortized.
570 // Called by the compose() and makeFCD() implementations.
571 UBool
Normalizer2Impl::decomposeShort(const UChar
*src
, const UChar
*limit
,
572 ReorderingBuffer
&buffer
,
573 UErrorCode
&errorCode
) const {
577 UTRIE2_U16_NEXT16(normTrie
, src
, limit
, c
, norm16
);
578 if(!decompose(c
, norm16
, buffer
, errorCode
)) {
585 UBool
Normalizer2Impl::decompose(UChar32 c
, uint16_t norm16
,
586 ReorderingBuffer
&buffer
,
587 UErrorCode
&errorCode
) const {
588 // Only loops for 1:1 algorithmic mappings.
590 // get the decomposition and the lead and trail cc's
591 if(isDecompYes(norm16
)) {
592 // c does not decompose
593 return buffer
.append(c
, getCCFromYesOrMaybe(norm16
), errorCode
);
594 } else if(isHangul(norm16
)) {
595 // Hangul syllable: decompose algorithmically
597 return buffer
.appendZeroCC(jamos
, jamos
+Hangul::decompose(c
, jamos
), errorCode
);
598 } else if(isDecompNoAlgorithmic(norm16
)) {
599 c
=mapAlgorithmic(c
, norm16
);
602 // c decomposes, get everything from the variable-length extra data
603 const uint16_t *mapping
=getMapping(norm16
);
604 uint16_t firstUnit
=*mapping
;
605 int32_t length
=firstUnit
&MAPPING_LENGTH_MASK
;
606 uint8_t leadCC
, trailCC
;
607 trailCC
=(uint8_t)(firstUnit
>>8);
608 if(firstUnit
&MAPPING_HAS_CCC_LCCC_WORD
) {
609 leadCC
=(uint8_t)(*(mapping
-1)>>8);
613 return buffer
.append((const UChar
*)mapping
+1, length
, leadCC
, trailCC
, errorCode
);
619 Normalizer2Impl::getDecomposition(UChar32 c
, UChar buffer
[4], int32_t &length
) const {
620 const UChar
*decomp
=NULL
;
623 if(c
<minDecompNoCP
|| isDecompYes(norm16
=getNorm16(c
))) {
624 // c does not decompose
626 } else if(isHangul(norm16
)) {
627 // Hangul syllable: decompose algorithmically
628 length
=Hangul::decompose(c
, buffer
);
630 } else if(isDecompNoAlgorithmic(norm16
)) {
631 c
=mapAlgorithmic(c
, norm16
);
634 U16_APPEND_UNSAFE(buffer
, length
, c
);
636 // c decomposes, get everything from the variable-length extra data
637 const uint16_t *mapping
=getMapping(norm16
);
638 length
=*mapping
&MAPPING_LENGTH_MASK
;
639 return (const UChar
*)mapping
+1;
644 // The capacity of the buffer must be 30=MAPPING_LENGTH_MASK-1
645 // so that a raw mapping fits that consists of one unit ("rm0")
646 // plus all but the first two code units of the normal mapping.
647 // The maximum length of a normal mapping is 31=MAPPING_LENGTH_MASK.
649 Normalizer2Impl::getRawDecomposition(UChar32 c
, UChar buffer
[30], int32_t &length
) const {
650 // We do not loop in this method because an algorithmic mapping itself
651 // becomes a final result rather than having to be decomposed recursively.
653 if(c
<minDecompNoCP
|| isDecompYes(norm16
=getNorm16(c
))) {
654 // c does not decompose
656 } else if(isHangul(norm16
)) {
657 // Hangul syllable: decompose algorithmically
658 Hangul::getRawDecomposition(c
, buffer
);
661 } else if(isDecompNoAlgorithmic(norm16
)) {
662 c
=mapAlgorithmic(c
, norm16
);
664 U16_APPEND_UNSAFE(buffer
, length
, c
);
667 // c decomposes, get everything from the variable-length extra data
668 const uint16_t *mapping
=getMapping(norm16
);
669 uint16_t firstUnit
=*mapping
;
670 int32_t mLength
=firstUnit
&MAPPING_LENGTH_MASK
; // length of normal mapping
671 if(firstUnit
&MAPPING_HAS_RAW_MAPPING
) {
672 // Read the raw mapping from before the firstUnit and before the optional ccc/lccc word.
673 // Bit 7=MAPPING_HAS_CCC_LCCC_WORD
674 const uint16_t *rawMapping
=mapping
-((firstUnit
>>7)&1)-1;
675 uint16_t rm0
=*rawMapping
;
676 if(rm0
<=MAPPING_LENGTH_MASK
) {
678 return (const UChar
*)rawMapping
-rm0
;
680 // Copy the normal mapping and replace its first two code units with rm0.
681 buffer
[0]=(UChar
)rm0
;
682 u_memcpy(buffer
+1, (const UChar
*)mapping
+1+2, mLength
-2);
688 return (const UChar
*)mapping
+1;
693 void Normalizer2Impl::decomposeAndAppend(const UChar
*src
, const UChar
*limit
,
695 UnicodeString
&safeMiddle
,
696 ReorderingBuffer
&buffer
,
697 UErrorCode
&errorCode
) const {
698 buffer
.copyReorderableSuffixTo(safeMiddle
);
700 decompose(src
, limit
, &buffer
, errorCode
);
703 // Just merge the strings at the boundary.
704 ForwardUTrie2StringIterator
iter(normTrie
, src
, limit
);
705 uint8_t firstCC
, prevCC
, cc
;
706 firstCC
=prevCC
=cc
=getCC(iter
.next16());
709 cc
=getCC(iter
.next16());
711 if(limit
==NULL
) { // appendZeroCC() needs limit!=NULL
712 limit
=u_strchr(iter
.codePointStart
, 0);
715 if (buffer
.append(src
, (int32_t)(iter
.codePointStart
-src
), firstCC
, prevCC
, errorCode
)) {
716 buffer
.appendZeroCC(iter
.codePointStart
, limit
, errorCode
);
720 // Note: hasDecompBoundary() could be implemented as aliases to
721 // hasFCDBoundaryBefore() and hasFCDBoundaryAfter()
722 // at the cost of building the FCD trie for a decomposition normalizer.
723 UBool
Normalizer2Impl::hasDecompBoundary(UChar32 c
, UBool before
) const {
725 if(c
<minDecompNoCP
) {
728 uint16_t norm16
=getNorm16(c
);
729 if(isHangul(norm16
) || isDecompYesAndZeroCC(norm16
)) {
731 } else if(norm16
>MIN_NORMAL_MAYBE_YES
) {
732 return FALSE
; // ccc!=0
733 } else if(isDecompNoAlgorithmic(norm16
)) {
734 c
=mapAlgorithmic(c
, norm16
);
736 // c decomposes, get everything from the variable-length extra data
737 const uint16_t *mapping
=getMapping(norm16
);
738 uint16_t firstUnit
=*mapping
;
739 if((firstUnit
&MAPPING_LENGTH_MASK
)==0) {
743 // decomp after-boundary: same as hasFCDBoundaryAfter(),
744 // fcd16<=1 || trailCC==0
745 if(firstUnit
>0x1ff) {
746 return FALSE
; // trailCC>1
748 if(firstUnit
<=0xff) {
749 return TRUE
; // trailCC==0
751 // if(trailCC==1) test leadCC==0, same as checking for before-boundary
753 // TRUE if leadCC==0 (hasFCDBoundaryBefore())
754 return (firstUnit
&MAPPING_HAS_CCC_LCCC_WORD
)==0 || (*(mapping
-1)&0xff00)==0;
760 * Finds the recomposition result for
761 * a forward-combining "lead" character,
762 * specified with a pointer to its compositions list,
763 * and a backward-combining "trail" character.
765 * If the lead and trail characters combine, then this function returns
766 * the following "compositeAndFwd" value:
767 * Bits 21..1 composite character
768 * Bit 0 set if the composite is a forward-combining starter
769 * otherwise it returns -1.
771 * The compositions list has (trail, compositeAndFwd) pair entries,
772 * encoded as either pairs or triples of 16-bit units.
773 * The last entry has the high bit of its first unit set.
775 * The list is sorted by ascending trail characters (there are no duplicates).
776 * A linear search is used.
778 * See normalizer2impl.h for a more detailed description
779 * of the compositions list format.
781 int32_t Normalizer2Impl::combine(const uint16_t *list
, UChar32 trail
) {
782 uint16_t key1
, firstUnit
;
783 if(trail
<COMP_1_TRAIL_LIMIT
) {
784 // trail character is 0..33FF
785 // result entry may have 2 or 3 units
786 key1
=(uint16_t)(trail
<<1);
787 while(key1
>(firstUnit
=*list
)) {
788 list
+=2+(firstUnit
&COMP_1_TRIPLE
);
790 if(key1
==(firstUnit
&COMP_1_TRAIL_MASK
)) {
791 if(firstUnit
&COMP_1_TRIPLE
) {
792 return ((int32_t)list
[1]<<16)|list
[2];
798 // trail character is 3400..10FFFF
799 // result entry has 3 units
800 key1
=(uint16_t)(COMP_1_TRAIL_LIMIT
+
801 (((trail
>>COMP_1_TRAIL_SHIFT
))&
803 uint16_t key2
=(uint16_t)(trail
<<COMP_2_TRAIL_SHIFT
);
806 if(key1
>(firstUnit
=*list
)) {
807 list
+=2+(firstUnit
&COMP_1_TRIPLE
);
808 } else if(key1
==(firstUnit
&COMP_1_TRAIL_MASK
)) {
809 if(key2
>(secondUnit
=list
[1])) {
810 if(firstUnit
&COMP_1_LAST_TUPLE
) {
815 } else if(key2
==(secondUnit
&COMP_2_TRAIL_MASK
)) {
816 return ((int32_t)(secondUnit
&~COMP_2_TRAIL_MASK
)<<16)|list
[2];
829 * @param list some character's compositions list
830 * @param set recursively receives the composites from these compositions
832 void Normalizer2Impl::addComposites(const uint16_t *list
, UnicodeSet
&set
) const {
834 int32_t compositeAndFwd
;
837 if((firstUnit
&COMP_1_TRIPLE
)==0) {
838 compositeAndFwd
=list
[1];
841 compositeAndFwd
=(((int32_t)list
[1]&~COMP_2_TRAIL_MASK
)<<16)|list
[2];
844 UChar32 composite
=compositeAndFwd
>>1;
845 if((compositeAndFwd
&1)!=0) {
846 addComposites(getCompositionsListForComposite(getNorm16(composite
)), set
);
849 } while((firstUnit
&COMP_1_LAST_TUPLE
)==0);
853 * Recomposes the buffer text starting at recomposeStartIndex
854 * (which is in NFD - decomposed and canonically ordered),
855 * and truncates the buffer contents.
857 * Note that recomposition never lengthens the text:
858 * Any character consists of either one or two code units;
859 * a composition may contain at most one more code unit than the original starter,
860 * while the combining mark that is removed has at least one code unit.
862 void Normalizer2Impl::recompose(ReorderingBuffer
&buffer
, int32_t recomposeStartIndex
,
863 UBool onlyContiguous
) const {
864 UChar
*p
=buffer
.getStart()+recomposeStartIndex
;
865 UChar
*limit
=buffer
.getLimit();
870 UChar
*starter
, *pRemove
, *q
, *r
;
871 const uint16_t *compositionsList
;
872 UChar32 c
, compositeAndFwd
;
875 UBool starterIsSupplementary
;
877 // Some of the following variables are not used until we have a forward-combining starter
878 // and are only initialized now to avoid compiler warnings.
879 compositionsList
=NULL
; // used as indicator for whether we have a forward-combining starter
881 starterIsSupplementary
=FALSE
;
885 UTRIE2_U16_NEXT16(normTrie
, p
, limit
, c
, norm16
);
886 cc
=getCCFromYesOrMaybe(norm16
);
887 if( // this character combines backward and
889 // we have seen a starter that combines forward and
890 compositionsList
!=NULL
&&
891 // the backward-combining character is not blocked
892 (prevCC
<cc
|| prevCC
==0)
894 if(isJamoVT(norm16
)) {
895 // c is a Jamo V/T, see if we can compose it with the previous character.
896 if(c
<Hangul::JAMO_T_BASE
) {
897 // c is a Jamo Vowel, compose with previous Jamo L and following Jamo T.
898 UChar prev
=(UChar
)(*starter
-Hangul::JAMO_L_BASE
);
899 if(prev
<Hangul::JAMO_L_COUNT
) {
901 UChar syllable
=(UChar
)
902 (Hangul::HANGUL_BASE
+
903 (prev
*Hangul::JAMO_V_COUNT
+(c
-Hangul::JAMO_V_BASE
))*
904 Hangul::JAMO_T_COUNT
);
906 if(p
!=limit
&& (t
=(UChar
)(*p
-Hangul::JAMO_T_BASE
))<Hangul::JAMO_T_COUNT
) {
908 syllable
+=t
; // The next character was a Jamo T.
911 // remove the Jamo V/T
922 * No "else" for Jamo T:
923 * Since the input is in NFD, there are no Hangul LV syllables that
924 * a Jamo T could combine with.
925 * All Jamo Ts are combined above when handling Jamo Vs.
930 compositionsList
=NULL
;
932 } else if((compositeAndFwd
=combine(compositionsList
, c
))>=0) {
933 // The starter and the combining mark (c) do combine.
934 UChar32 composite
=compositeAndFwd
>>1;
936 // Replace the starter with the composite, remove the combining mark.
937 pRemove
=p
-U16_LENGTH(c
); // pRemove & p: start & limit of the combining mark
938 if(starterIsSupplementary
) {
939 if(U_IS_SUPPLEMENTARY(composite
)) {
940 // both are supplementary
941 starter
[0]=U16_LEAD(composite
);
942 starter
[1]=U16_TRAIL(composite
);
944 *starter
=(UChar
)composite
;
945 // The composite is shorter than the starter,
946 // move the intermediate characters forward one.
947 starterIsSupplementary
=FALSE
;
955 } else if(U_IS_SUPPLEMENTARY(composite
)) {
956 // The composite is longer than the starter,
957 // move the intermediate characters back one.
958 starterIsSupplementary
=TRUE
;
959 ++starter
; // temporarily increment for the loop boundary
965 *starter
=U16_TRAIL(composite
);
966 *--starter
=U16_LEAD(composite
); // undo the temporary increment
968 // both are on the BMP
969 *starter
=(UChar
)composite
;
972 /* remove the combining mark by moving the following text over it */
982 // Keep prevCC because we removed the combining mark.
987 // Is the composite a starter that combines forward?
988 if(compositeAndFwd
&1) {
990 getCompositionsListForComposite(getNorm16(composite
));
992 compositionsList
=NULL
;
995 // We combined; continue with looking for compositions.
1000 // no combination this time
1006 // If c did not combine, then check if it is a starter.
1008 // Found a new starter.
1009 if((compositionsList
=getCompositionsListForDecompYes(norm16
))!=NULL
) {
1010 // It may combine with something, prepare for it.
1012 starterIsSupplementary
=FALSE
;
1015 starterIsSupplementary
=TRUE
;
1019 } else if(onlyContiguous
) {
1020 // FCC: no discontiguous compositions; any intervening character blocks.
1021 compositionsList
=NULL
;
1024 buffer
.setReorderingLimit(limit
);
1028 Normalizer2Impl::composePair(UChar32 a
, UChar32 b
) const {
1029 uint16_t norm16
=getNorm16(a
); // maps an out-of-range 'a' to inert norm16=0
1030 const uint16_t *list
;
1031 if(isInert(norm16
)) {
1033 } else if(norm16
<minYesNoMappingsOnly
) {
1034 if(isJamoL(norm16
)) {
1035 b
-=Hangul::JAMO_V_BASE
;
1036 if(0<=b
&& b
<Hangul::JAMO_V_COUNT
) {
1038 (Hangul::HANGUL_BASE
+
1039 ((a
-Hangul::JAMO_L_BASE
)*Hangul::JAMO_V_COUNT
+b
)*
1040 Hangul::JAMO_T_COUNT
);
1044 } else if(isHangul(norm16
)) {
1045 b
-=Hangul::JAMO_T_BASE
;
1046 if(Hangul::isHangulWithoutJamoT(a
) && 0<b
&& b
<Hangul::JAMO_T_COUNT
) { // not b==0!
1052 // 'a' has a compositions list in extraData
1053 list
=extraData
+norm16
;
1054 if(norm16
>minYesNo
) { // composite 'a' has both mapping & compositions list
1055 list
+= // mapping pointer
1056 1+ // +1 to skip the first unit with the mapping lenth
1057 (*list
&MAPPING_LENGTH_MASK
); // + mapping length
1060 } else if(norm16
<minMaybeYes
|| MIN_NORMAL_MAYBE_YES
<=norm16
) {
1063 list
=maybeYesCompositions
+norm16
-minMaybeYes
;
1065 if(b
<0 || 0x10ffff<b
) { // combine(list, b) requires a valid code point b
1068 #if U_SIGNED_RIGHT_SHIFT_IS_ARITHMETIC
1069 return combine(list
, b
)>>1;
1071 int32_t compositeAndFwd
=combine(list
, b
);
1072 return compositeAndFwd
>=0 ? compositeAndFwd
>>1 : U_SENTINEL
;
1076 // Very similar to composeQuickCheck(): Make the same changes in both places if relevant.
1077 // doCompose: normalize
1078 // !doCompose: isNormalized (buffer must be empty and initialized)
1080 Normalizer2Impl::compose(const UChar
*src
, const UChar
*limit
,
1081 UBool onlyContiguous
,
1083 ReorderingBuffer
&buffer
,
1084 UErrorCode
&errorCode
) const {
1086 * prevBoundary points to the last character before the current one
1087 * that has a composition boundary before it with ccc==0 and quick check "yes".
1088 * Keeping track of prevBoundary saves us looking for a composition boundary
1089 * when we find a "no" or "maybe".
1091 * When we back out from prevSrc back to prevBoundary,
1092 * then we also remove those same characters (which had been simply copied
1093 * or canonically-order-inserted) from the ReorderingBuffer.
1094 * Therefore, at all times, the [prevBoundary..prevSrc[ source units
1095 * must correspond 1:1 to destination units at the end of the destination buffer.
1097 const UChar
*prevBoundary
=src
;
1098 UChar32 minNoMaybeCP
=minCompNoMaybeCP
;
1100 src
=copyLowPrefixFromNulTerminated(src
, minNoMaybeCP
,
1101 doCompose
? &buffer
: NULL
,
1103 if(U_FAILURE(errorCode
)) {
1106 if(prevBoundary
<src
) {
1107 // Set prevBoundary to the last character in the prefix.
1110 limit
=u_strchr(src
, 0);
1113 const UChar
*prevSrc
;
1117 // only for isNormalized
1121 // count code units below the minimum or with irrelevant data for the quick check
1122 for(prevSrc
=src
; src
!=limit
;) {
1123 if( (c
=*src
)<minNoMaybeCP
||
1124 isCompYesAndZeroCC(norm16
=UTRIE2_GET16_FROM_U16_SINGLE_LEAD(normTrie
, c
))
1127 } else if(!U16_IS_SURROGATE(c
)) {
1131 if(U16_IS_SURROGATE_LEAD(c
)) {
1132 if((src
+1)!=limit
&& U16_IS_TRAIL(c2
=src
[1])) {
1133 c
=U16_GET_SUPPLEMENTARY(c
, c2
);
1135 } else /* trail surrogate */ {
1136 if(prevSrc
<src
&& U16_IS_LEAD(c2
=*(src
-1))) {
1138 c
=U16_GET_SUPPLEMENTARY(c2
, c
);
1141 if(isCompYesAndZeroCC(norm16
=getNorm16(c
))) {
1148 // copy these code units all at once
1151 if(!buffer
.appendZeroCC(prevSrc
, src
, errorCode
)) {
1160 // Set prevBoundary to the last character in the quick check loop.
1162 if( U16_IS_TRAIL(*prevBoundary
) && prevSrc
<prevBoundary
&&
1163 U16_IS_LEAD(*(prevBoundary
-1))
1167 // The start of the current character (c).
1169 } else if(src
==limit
) {
1175 * isCompYesAndZeroCC(norm16) is false, that is, norm16>=minNoNo.
1176 * c is either a "noNo" (has a mapping) or a "maybeYes" (combines backward)
1178 * Check for Jamo V/T, then for regular characters.
1179 * c is not a Hangul syllable or Jamo L because those have "yes" properties.
1181 if(isJamoVT(norm16
) && prevBoundary
!=prevSrc
) {
1182 UChar prev
=*(prevSrc
-1);
1183 UBool needToDecompose
=FALSE
;
1184 if(c
<Hangul::JAMO_T_BASE
) {
1185 // c is a Jamo Vowel, compose with previous Jamo L and following Jamo T.
1186 prev
=(UChar
)(prev
-Hangul::JAMO_L_BASE
);
1187 if(prev
<Hangul::JAMO_L_COUNT
) {
1191 UChar syllable
=(UChar
)
1192 (Hangul::HANGUL_BASE
+
1193 (prev
*Hangul::JAMO_V_COUNT
+(c
-Hangul::JAMO_V_BASE
))*
1194 Hangul::JAMO_T_COUNT
);
1196 if(src
!=limit
&& (t
=(UChar
)(*src
-Hangul::JAMO_T_BASE
))<Hangul::JAMO_T_COUNT
) {
1198 syllable
+=t
; // The next character was a Jamo T.
1200 buffer
.setLastChar(syllable
);
1203 // If we see L+V+x where x!=T then we drop to the slow path,
1204 // decompose and recompose.
1205 // This is to deal with NFKC finding normal L and V but a
1206 // compatibility variant of a T. We need to either fully compose that
1207 // combination here (which would complicate the code and may not work
1208 // with strange custom data) or use the slow path -- or else our replacing
1209 // two input characters (L+V) with one output character (LV syllable)
1210 // would violate the invariant that [prevBoundary..prevSrc[ has the same
1211 // length as what we appended to the buffer since prevBoundary.
1212 needToDecompose
=TRUE
;
1214 } else if(Hangul::isHangulWithoutJamoT(prev
)) {
1215 // c is a Jamo Trailing consonant,
1216 // compose with previous Hangul LV that does not contain a Jamo T.
1220 buffer
.setLastChar((UChar
)(prev
+c
-Hangul::JAMO_T_BASE
));
1224 if(!needToDecompose
) {
1225 // The Jamo V/T did not compose into a Hangul syllable.
1227 if(!buffer
.appendBMP((UChar
)c
, 0, errorCode
)) {
1237 * Source buffer pointers:
1239 * all done quick check current char not yet
1240 * "yes" but (c) processed
1243 * [-------------[-------------[-------------[-------------[
1245 * orig. src prevBoundary prevSrc src limit
1248 * Destination buffer pointers inside the ReorderingBuffer:
1250 * all done might take not filled yet
1253 * [-------------[-------------[-------------[
1255 * start reorderStart limit |
1258 if(norm16
>=MIN_YES_YES_WITH_CC
) {
1259 uint8_t cc
=(uint8_t)norm16
; // cc!=0
1260 if( onlyContiguous
&& // FCC
1261 (doCompose
? buffer
.getLastCC() : prevCC
)==0 &&
1262 prevBoundary
<prevSrc
&&
1263 // buffer.getLastCC()==0 && prevBoundary<prevSrc tell us that
1264 // [prevBoundary..prevSrc[ (which is exactly one character under these conditions)
1265 // passed the quick check "yes && ccc==0" test.
1266 // Check whether the last character was a "yesYes" or a "yesNo".
1267 // If a "yesNo", then we get its trailing ccc from its
1268 // mapping and check for canonical order.
1269 // All other cases are ok.
1270 getTrailCCFromCompYesAndZeroCC(prevBoundary
, prevSrc
)>cc
1272 // Fails FCD test, need to decompose and contiguously recompose.
1276 } else if(doCompose
) {
1277 if(!buffer
.append(c
, cc
, errorCode
)) {
1281 } else if(prevCC
<=cc
) {
1287 } else if(!doCompose
&& !isMaybeOrNonZeroCC(norm16
)) {
1292 * Find appropriate boundaries around this character,
1293 * decompose the source text from between the boundaries,
1296 * We may need to remove the last few characters from the ReorderingBuffer
1297 * to account for source text that was copied or appended
1298 * but needs to take part in the recomposition.
1302 * Find the last composition boundary in [prevBoundary..src[.
1303 * It is either the decomposition of the current character (at prevSrc),
1306 if(hasCompBoundaryBefore(c
, norm16
)) {
1307 prevBoundary
=prevSrc
;
1308 } else if(doCompose
) {
1309 buffer
.removeSuffix((int32_t)(prevSrc
-prevBoundary
));
1312 // Find the next composition boundary in [src..limit[ -
1313 // modifies src to point to the next starter.
1314 src
=(UChar
*)findNextCompBoundary(src
, limit
);
1316 // Decompose [prevBoundary..src[ into the buffer and then recompose that part of it.
1317 int32_t recomposeStartIndex
=buffer
.length();
1318 if(!decomposeShort(prevBoundary
, src
, buffer
, errorCode
)) {
1321 recompose(buffer
, recomposeStartIndex
, onlyContiguous
);
1323 if(!buffer
.equals(prevBoundary
, src
)) {
1330 // Move to the next starter. We never need to look back before this point again.
1336 // Very similar to compose(): Make the same changes in both places if relevant.
1337 // pQCResult==NULL: spanQuickCheckYes
1338 // pQCResult!=NULL: quickCheck (*pQCResult must be UNORM_YES)
1340 Normalizer2Impl::composeQuickCheck(const UChar
*src
, const UChar
*limit
,
1341 UBool onlyContiguous
,
1342 UNormalizationCheckResult
*pQCResult
) const {
1344 * prevBoundary points to the last character before the current one
1345 * that has a composition boundary before it with ccc==0 and quick check "yes".
1347 const UChar
*prevBoundary
=src
;
1348 UChar32 minNoMaybeCP
=minCompNoMaybeCP
;
1350 UErrorCode errorCode
=U_ZERO_ERROR
;
1351 src
=copyLowPrefixFromNulTerminated(src
, minNoMaybeCP
, NULL
, errorCode
);
1352 if(prevBoundary
<src
) {
1353 // Set prevBoundary to the last character in the prefix.
1356 limit
=u_strchr(src
, 0);
1359 const UChar
*prevSrc
;
1365 // count code units below the minimum or with irrelevant data for the quick check
1366 for(prevSrc
=src
;;) {
1370 if( (c
=*src
)<minNoMaybeCP
||
1371 isCompYesAndZeroCC(norm16
=UTRIE2_GET16_FROM_U16_SINGLE_LEAD(normTrie
, c
))
1374 } else if(!U16_IS_SURROGATE(c
)) {
1378 if(U16_IS_SURROGATE_LEAD(c
)) {
1379 if((src
+1)!=limit
&& U16_IS_TRAIL(c2
=src
[1])) {
1380 c
=U16_GET_SUPPLEMENTARY(c
, c2
);
1382 } else /* trail surrogate */ {
1383 if(prevSrc
<src
&& U16_IS_LEAD(c2
=*(src
-1))) {
1385 c
=U16_GET_SUPPLEMENTARY(c2
, c
);
1388 if(isCompYesAndZeroCC(norm16
=getNorm16(c
))) {
1396 // Set prevBoundary to the last character in the quick check loop.
1398 if( U16_IS_TRAIL(*prevBoundary
) && prevSrc
<prevBoundary
&&
1399 U16_IS_LEAD(*(prevBoundary
-1))
1404 // The start of the current character (c).
1410 * isCompYesAndZeroCC(norm16) is false, that is, norm16>=minNoNo.
1411 * c is either a "noNo" (has a mapping) or a "maybeYes" (combines backward)
1414 if(isMaybeOrNonZeroCC(norm16
)) {
1415 uint8_t cc
=getCCFromYesOrMaybe(norm16
);
1416 if( onlyContiguous
&& // FCC
1419 prevBoundary
<prevSrc
&&
1420 // prevCC==0 && prevBoundary<prevSrc tell us that
1421 // [prevBoundary..prevSrc[ (which is exactly one character under these conditions)
1422 // passed the quick check "yes && ccc==0" test.
1423 // Check whether the last character was a "yesYes" or a "yesNo".
1424 // If a "yesNo", then we get its trailing ccc from its
1425 // mapping and check for canonical order.
1426 // All other cases are ok.
1427 getTrailCCFromCompYesAndZeroCC(prevBoundary
, prevSrc
)>cc
1430 } else if(prevCC
<=cc
|| cc
==0) {
1432 if(norm16
<MIN_YES_YES_WITH_CC
) {
1433 if(pQCResult
!=NULL
) {
1434 *pQCResult
=UNORM_MAYBE
;
1436 return prevBoundary
;
1442 if(pQCResult
!=NULL
) {
1443 *pQCResult
=UNORM_NO
;
1445 return prevBoundary
;
1449 void Normalizer2Impl::composeAndAppend(const UChar
*src
, const UChar
*limit
,
1451 UBool onlyContiguous
,
1452 UnicodeString
&safeMiddle
,
1453 ReorderingBuffer
&buffer
,
1454 UErrorCode
&errorCode
) const {
1455 if(!buffer
.isEmpty()) {
1456 const UChar
*firstStarterInSrc
=findNextCompBoundary(src
, limit
);
1457 if(src
!=firstStarterInSrc
) {
1458 const UChar
*lastStarterInDest
=findPreviousCompBoundary(buffer
.getStart(),
1460 int32_t destSuffixLength
=(int32_t)(buffer
.getLimit()-lastStarterInDest
);
1461 UnicodeString
middle(lastStarterInDest
, destSuffixLength
);
1462 buffer
.removeSuffix(destSuffixLength
);
1464 middle
.append(src
, (int32_t)(firstStarterInSrc
-src
));
1465 const UChar
*middleStart
=middle
.getBuffer();
1466 compose(middleStart
, middleStart
+middle
.length(), onlyContiguous
,
1467 TRUE
, buffer
, errorCode
);
1468 if(U_FAILURE(errorCode
)) {
1471 src
=firstStarterInSrc
;
1475 compose(src
, limit
, onlyContiguous
, TRUE
, buffer
, errorCode
);
1477 if(limit
==NULL
) { // appendZeroCC() needs limit!=NULL
1478 limit
=u_strchr(src
, 0);
1480 buffer
.appendZeroCC(src
, limit
, errorCode
);
1485 * Does c have a composition boundary before it?
1486 * True if its decomposition begins with a character that has
1487 * ccc=0 && NFC_QC=Yes (isCompYesAndZeroCC()).
1488 * As a shortcut, this is true if c itself has ccc=0 && NFC_QC=Yes
1489 * (isCompYesAndZeroCC()) so we need not decompose.
1491 UBool
Normalizer2Impl::hasCompBoundaryBefore(UChar32 c
, uint16_t norm16
) const {
1493 if(isCompYesAndZeroCC(norm16
)) {
1495 } else if(isMaybeOrNonZeroCC(norm16
)) {
1497 } else if(isDecompNoAlgorithmic(norm16
)) {
1498 c
=mapAlgorithmic(c
, norm16
);
1499 norm16
=getNorm16(c
);
1501 // c decomposes, get everything from the variable-length extra data
1502 const uint16_t *mapping
=getMapping(norm16
);
1503 uint16_t firstUnit
=*mapping
;
1504 if((firstUnit
&MAPPING_LENGTH_MASK
)==0) {
1507 if((firstUnit
&MAPPING_HAS_CCC_LCCC_WORD
) && (*(mapping
-1)&0xff00)) {
1508 return FALSE
; // non-zero leadCC
1510 int32_t i
=1; // skip over the firstUnit
1512 U16_NEXT_UNSAFE(mapping
, i
, c
);
1513 return isCompYesAndZeroCC(getNorm16(c
));
1518 UBool
Normalizer2Impl::hasCompBoundaryAfter(UChar32 c
, UBool onlyContiguous
, UBool testInert
) const {
1520 uint16_t norm16
=getNorm16(c
);
1521 if(isInert(norm16
)) {
1523 } else if(norm16
<=minYesNo
) {
1524 // Hangul: norm16==minYesNo
1525 // Hangul LVT has a boundary after it.
1526 // Hangul LV and non-inert yesYes characters combine forward.
1527 return isHangul(norm16
) && !Hangul::isHangulWithoutJamoT((UChar
)c
);
1528 } else if(norm16
>= (testInert
? minNoNo
: minMaybeYes
)) {
1530 } else if(isDecompNoAlgorithmic(norm16
)) {
1531 c
=mapAlgorithmic(c
, norm16
);
1533 // c decomposes, get everything from the variable-length extra data.
1534 // If testInert, then c must be a yesNo character which has lccc=0,
1535 // otherwise it could be a noNo.
1536 const uint16_t *mapping
=getMapping(norm16
);
1537 uint16_t firstUnit
=*mapping
;
1539 // not MAPPING_NO_COMP_BOUNDARY_AFTER
1541 // c is not deleted, and
1542 // it and its decomposition do not combine forward, and it has a starter)
1543 // and if FCC then trailCC<=1
1545 (firstUnit
&MAPPING_NO_COMP_BOUNDARY_AFTER
)==0 &&
1546 (!onlyContiguous
|| firstUnit
<=0x1ff);
1551 const UChar
*Normalizer2Impl::findPreviousCompBoundary(const UChar
*start
, const UChar
*p
) const {
1552 BackwardUTrie2StringIterator
iter(normTrie
, start
, p
);
1555 norm16
=iter
.previous16();
1556 } while(!hasCompBoundaryBefore(iter
.codePoint
, norm16
));
1557 // We could also test hasCompBoundaryAfter() and return iter.codePointLimit,
1558 // but that's probably not worth the extra cost.
1559 return iter
.codePointStart
;
1562 const UChar
*Normalizer2Impl::findNextCompBoundary(const UChar
*p
, const UChar
*limit
) const {
1563 ForwardUTrie2StringIterator
iter(normTrie
, p
, limit
);
1566 norm16
=iter
.next16();
1567 } while(!hasCompBoundaryBefore(iter
.codePoint
, norm16
));
1568 return iter
.codePointStart
;
1571 // Note: normalizer2impl.cpp r30982 (2011-nov-27)
1572 // still had getFCDTrie() which built and cached an FCD trie.
1573 // That provided faster access to FCD data than getFCD16FromNormData()
1574 // but required synchronization and consumed some 10kB of heap memory
1575 // in any process that uses FCD (e.g., via collation).
1576 // tccc180[] and smallFCD[] are intended to help with any loss of performance,
1577 // at least for Latin & CJK.
1579 // Gets the FCD value from the regular normalization data.
1580 uint16_t Normalizer2Impl::getFCD16FromNormData(UChar32 c
) const {
1581 // Only loops for 1:1 algorithmic mappings.
1583 uint16_t norm16
=getNorm16(c
);
1584 if(norm16
<=minYesNo
) {
1585 // no decomposition or Hangul syllable, all zeros
1587 } else if(norm16
>=MIN_NORMAL_MAYBE_YES
) {
1590 return norm16
|(norm16
<<8);
1591 } else if(norm16
>=minMaybeYes
) {
1593 } else if(isDecompNoAlgorithmic(norm16
)) {
1594 c
=mapAlgorithmic(c
, norm16
);
1596 // c decomposes, get everything from the variable-length extra data
1597 const uint16_t *mapping
=getMapping(norm16
);
1598 uint16_t firstUnit
=*mapping
;
1599 if((firstUnit
&MAPPING_LENGTH_MASK
)==0) {
1600 // A character that is deleted (maps to an empty string) must
1601 // get the worst-case lccc and tccc values because arbitrary
1602 // characters on both sides will become adjacent.
1605 norm16
=firstUnit
>>8; // tccc
1606 if(firstUnit
&MAPPING_HAS_CCC_LCCC_WORD
) {
1607 norm16
|=*(mapping
-1)&0xff00; // lccc
1615 // Dual functionality:
1616 // buffer!=NULL: normalize
1617 // buffer==NULL: isNormalized/quickCheck/spanQuickCheckYes
1619 Normalizer2Impl::makeFCD(const UChar
*src
, const UChar
*limit
,
1620 ReorderingBuffer
*buffer
,
1621 UErrorCode
&errorCode
) const {
1622 // Tracks the last FCD-safe boundary, before lccc=0 or after properly-ordered tccc<=1.
1623 // Similar to the prevBoundary in the compose() implementation.
1624 const UChar
*prevBoundary
=src
;
1625 int32_t prevFCD16
=0;
1627 src
=copyLowPrefixFromNulTerminated(src
, MIN_CCC_LCCC_CP
, buffer
, errorCode
);
1628 if(U_FAILURE(errorCode
)) {
1631 if(prevBoundary
<src
) {
1633 // We know that the previous character's lccc==0.
1634 // Fetching the fcd16 value was deferred for this below-U+0300 code point.
1635 prevFCD16
=getFCD16(*(src
-1));
1640 limit
=u_strchr(src
, 0);
1643 // Note: In this function we use buffer->appendZeroCC() because we track
1644 // the lead and trail combining classes here, rather than leaving it to
1645 // the ReorderingBuffer.
1646 // The exception is the call to decomposeShort() which uses the buffer
1647 // in the normal way.
1649 const UChar
*prevSrc
;
1654 // count code units with lccc==0
1655 for(prevSrc
=src
; src
!=limit
;) {
1656 if((c
=*src
)<MIN_CCC_LCCC_CP
) {
1659 } else if(!singleLeadMightHaveNonZeroFCD16(c
)) {
1663 if(U16_IS_SURROGATE(c
)) {
1665 if(U16_IS_SURROGATE_LEAD(c
)) {
1666 if((src
+1)!=limit
&& U16_IS_TRAIL(c2
=src
[1])) {
1667 c
=U16_GET_SUPPLEMENTARY(c
, c2
);
1669 } else /* trail surrogate */ {
1670 if(prevSrc
<src
&& U16_IS_LEAD(c2
=*(src
-1))) {
1672 c
=U16_GET_SUPPLEMENTARY(c2
, c
);
1676 if((fcd16
=getFCD16FromNormData(c
))<=0xff) {
1684 // copy these code units all at once
1686 if(buffer
!=NULL
&& !buffer
->appendZeroCC(prevSrc
, src
, errorCode
)) {
1693 // We know that the previous character's lccc==0.
1695 // Fetching the fcd16 value was deferred for this below-U+0300 code point.
1696 UChar32 prev
=~prevFCD16
;
1697 prevFCD16
= prev
<0x180 ? tccc180
[prev
] : getFCD16FromNormData(prev
);
1702 const UChar
*p
=src
-1;
1703 if(U16_IS_TRAIL(*p
) && prevSrc
<p
&& U16_IS_LEAD(*(p
-1))) {
1705 // Need to fetch the previous character's FCD value because
1706 // prevFCD16 was just for the trail surrogate code point.
1707 prevFCD16
=getFCD16FromNormData(U16_GET_SUPPLEMENTARY(p
[0], p
[1]));
1708 // Still known to have lccc==0 because its lead surrogate unit had lccc==0.
1714 // The start of the current character (c).
1716 } else if(src
==limit
) {
1721 // The current character (c) at [prevSrc..src[ has a non-zero lead combining class.
1722 // Check for proper order, and decompose locally if necessary.
1723 if((prevFCD16
&0xff)<=(fcd16
>>8)) {
1724 // proper order: prev tccc <= current lccc
1725 if((fcd16
&0xff)<=1) {
1728 if(buffer
!=NULL
&& !buffer
->appendZeroCC(c
, errorCode
)) {
1733 } else if(buffer
==NULL
) {
1734 return prevBoundary
; // quick check "no"
1737 * Back out the part of the source that we copied or appended
1738 * already but is now going to be decomposed.
1739 * prevSrc is set to after what was copied/appended.
1741 buffer
->removeSuffix((int32_t)(prevSrc
-prevBoundary
));
1743 * Find the part of the source that needs to be decomposed,
1744 * up to the next safe boundary.
1746 src
=findNextFCDBoundary(src
, limit
);
1748 * The source text does not fulfill the conditions for FCD.
1749 * Decompose and reorder a limited piece of the text.
1751 if(!decomposeShort(prevBoundary
, src
, *buffer
, errorCode
)) {
1761 void Normalizer2Impl::makeFCDAndAppend(const UChar
*src
, const UChar
*limit
,
1763 UnicodeString
&safeMiddle
,
1764 ReorderingBuffer
&buffer
,
1765 UErrorCode
&errorCode
) const {
1766 if(!buffer
.isEmpty()) {
1767 const UChar
*firstBoundaryInSrc
=findNextFCDBoundary(src
, limit
);
1768 if(src
!=firstBoundaryInSrc
) {
1769 const UChar
*lastBoundaryInDest
=findPreviousFCDBoundary(buffer
.getStart(),
1771 int32_t destSuffixLength
=(int32_t)(buffer
.getLimit()-lastBoundaryInDest
);
1772 UnicodeString
middle(lastBoundaryInDest
, destSuffixLength
);
1773 buffer
.removeSuffix(destSuffixLength
);
1775 middle
.append(src
, (int32_t)(firstBoundaryInSrc
-src
));
1776 const UChar
*middleStart
=middle
.getBuffer();
1777 makeFCD(middleStart
, middleStart
+middle
.length(), &buffer
, errorCode
);
1778 if(U_FAILURE(errorCode
)) {
1781 src
=firstBoundaryInSrc
;
1785 makeFCD(src
, limit
, &buffer
, errorCode
);
1787 if(limit
==NULL
) { // appendZeroCC() needs limit!=NULL
1788 limit
=u_strchr(src
, 0);
1790 buffer
.appendZeroCC(src
, limit
, errorCode
);
1794 const UChar
*Normalizer2Impl::findPreviousFCDBoundary(const UChar
*start
, const UChar
*p
) const {
1795 while(start
<p
&& previousFCD16(start
, p
)>0xff) {}
1799 const UChar
*Normalizer2Impl::findNextFCDBoundary(const UChar
*p
, const UChar
*limit
) const {
1801 const UChar
*codePointStart
=p
;
1802 if(nextFCD16(p
, limit
)<=0xff) {
1803 return codePointStart
;
1809 // CanonicalIterator data -------------------------------------------------- ***
1811 CanonIterData::CanonIterData(UErrorCode
&errorCode
) :
1812 trie(utrie2_open(0, 0, &errorCode
)),
1813 canonStartSets(uprv_deleteUObject
, NULL
, errorCode
) {}
1815 CanonIterData::~CanonIterData() {
1819 void CanonIterData::addToStartSet(UChar32 origin
, UChar32 decompLead
, UErrorCode
&errorCode
) {
1820 uint32_t canonValue
=utrie2_get32(trie
, decompLead
);
1821 if((canonValue
&(CANON_HAS_SET
|CANON_VALUE_MASK
))==0 && origin
!=0) {
1822 // origin is the first character whose decomposition starts with
1823 // the character for which we are setting the value.
1824 utrie2_set32(trie
, decompLead
, canonValue
|origin
, &errorCode
);
1826 // origin is not the first character, or it is U+0000.
1828 if((canonValue
&CANON_HAS_SET
)==0) {
1831 errorCode
=U_MEMORY_ALLOCATION_ERROR
;
1834 UChar32 firstOrigin
=(UChar32
)(canonValue
&CANON_VALUE_MASK
);
1835 canonValue
=(canonValue
&~CANON_VALUE_MASK
)|CANON_HAS_SET
|(uint32_t)canonStartSets
.size();
1836 utrie2_set32(trie
, decompLead
, canonValue
, &errorCode
);
1837 canonStartSets
.addElement(set
, errorCode
);
1838 if(firstOrigin
!=0) {
1839 set
->add(firstOrigin
);
1842 set
=(UnicodeSet
*)canonStartSets
[(int32_t)(canonValue
&CANON_VALUE_MASK
)];
1850 // Call Normalizer2Impl::makeCanonIterDataFromNorm16() for a range of same-norm16 characters.
1851 // context: the Normalizer2Impl
1852 static UBool U_CALLCONV
1853 enumCIDRangeHandler(const void *context
, UChar32 start
, UChar32 end
, uint32_t value
) {
1854 UErrorCode errorCode
= U_ZERO_ERROR
;
1856 Normalizer2Impl
*impl
= (Normalizer2Impl
*)context
;
1857 impl
->makeCanonIterDataFromNorm16(
1858 start
, end
, (uint16_t)value
, *impl
->fCanonIterData
, errorCode
);
1860 return U_SUCCESS(errorCode
);
1865 // UInitOnce instantiation function for CanonIterData
1867 static void U_CALLCONV
1868 initCanonIterData(Normalizer2Impl
*impl
, UErrorCode
&errorCode
) {
1869 U_ASSERT(impl
->fCanonIterData
== NULL
);
1870 impl
->fCanonIterData
= new CanonIterData(errorCode
);
1871 if (impl
->fCanonIterData
== NULL
) {
1872 errorCode
=U_MEMORY_ALLOCATION_ERROR
;
1874 if (U_SUCCESS(errorCode
)) {
1875 utrie2_enum(impl
->getNormTrie(), NULL
, enumCIDRangeHandler
, impl
);
1876 utrie2_freeze(impl
->fCanonIterData
->trie
, UTRIE2_32_VALUE_BITS
, &errorCode
);
1878 if (U_FAILURE(errorCode
)) {
1879 delete impl
->fCanonIterData
;
1880 impl
->fCanonIterData
= NULL
;
1886 void Normalizer2Impl::makeCanonIterDataFromNorm16(UChar32 start
, UChar32 end
, uint16_t norm16
,
1887 CanonIterData
&newData
,
1888 UErrorCode
&errorCode
) const {
1889 if(norm16
==0 || (minYesNo
<=norm16
&& norm16
<minNoNo
)) {
1890 // Inert, or 2-way mapping (including Hangul syllable).
1891 // We do not write a canonStartSet for any yesNo character.
1892 // Composites from 2-way mappings are added at runtime from the
1893 // starter's compositions list, and the other characters in
1894 // 2-way mappings get CANON_NOT_SEGMENT_STARTER set because they are
1895 // "maybe" characters.
1898 for(UChar32 c
=start
; c
<=end
; ++c
) {
1899 uint32_t oldValue
=utrie2_get32(newData
.trie
, c
);
1900 uint32_t newValue
=oldValue
;
1901 if(norm16
>=minMaybeYes
) {
1902 // not a segment starter if it occurs in a decomposition or has cc!=0
1903 newValue
|=CANON_NOT_SEGMENT_STARTER
;
1904 if(norm16
<MIN_NORMAL_MAYBE_YES
) {
1905 newValue
|=CANON_HAS_COMPOSITIONS
;
1907 } else if(norm16
<minYesNo
) {
1908 newValue
|=CANON_HAS_COMPOSITIONS
;
1910 // c has a one-way decomposition
1912 uint16_t norm16_2
=norm16
;
1913 while(limitNoNo
<=norm16_2
&& norm16_2
<minMaybeYes
) {
1914 c2
=mapAlgorithmic(c2
, norm16_2
);
1915 norm16_2
=getNorm16(c2
);
1917 if(minYesNo
<=norm16_2
&& norm16_2
<limitNoNo
) {
1918 // c decomposes, get everything from the variable-length extra data
1919 const uint16_t *mapping
=getMapping(norm16_2
);
1920 uint16_t firstUnit
=*mapping
;
1921 int32_t length
=firstUnit
&MAPPING_LENGTH_MASK
;
1922 if((firstUnit
&MAPPING_HAS_CCC_LCCC_WORD
)!=0) {
1923 if(c
==c2
&& (*(mapping
-1)&0xff)!=0) {
1924 newValue
|=CANON_NOT_SEGMENT_STARTER
; // original c has cc!=0
1927 // Skip empty mappings (no characters in the decomposition).
1929 ++mapping
; // skip over the firstUnit
1930 // add c to first code point's start set
1932 U16_NEXT_UNSAFE(mapping
, i
, c2
);
1933 newData
.addToStartSet(c
, c2
, errorCode
);
1934 // Set CANON_NOT_SEGMENT_STARTER for each remaining code point of a
1935 // one-way mapping. A 2-way mapping is possible here after
1936 // intermediate algorithmic mapping.
1937 if(norm16_2
>=minNoNo
) {
1939 U16_NEXT_UNSAFE(mapping
, i
, c2
);
1940 uint32_t c2Value
=utrie2_get32(newData
.trie
, c2
);
1941 if((c2Value
&CANON_NOT_SEGMENT_STARTER
)==0) {
1942 utrie2_set32(newData
.trie
, c2
, c2Value
|CANON_NOT_SEGMENT_STARTER
,
1949 // c decomposed to c2 algorithmically; c has cc==0
1950 newData
.addToStartSet(c
, c2
, errorCode
);
1953 if(newValue
!=oldValue
) {
1954 utrie2_set32(newData
.trie
, c
, newValue
, &errorCode
);
1959 UBool
Normalizer2Impl::ensureCanonIterData(UErrorCode
&errorCode
) const {
1960 // Logically const: Synchronized instantiation.
1961 Normalizer2Impl
*me
=const_cast<Normalizer2Impl
*>(this);
1962 umtx_initOnce(me
->fCanonIterDataInitOnce
, &initCanonIterData
, me
, errorCode
);
1963 return U_SUCCESS(errorCode
);
1966 int32_t Normalizer2Impl::getCanonValue(UChar32 c
) const {
1967 return (int32_t)utrie2_get32(fCanonIterData
->trie
, c
);
1970 const UnicodeSet
&Normalizer2Impl::getCanonStartSet(int32_t n
) const {
1971 return *(const UnicodeSet
*)fCanonIterData
->canonStartSets
[n
];
1974 UBool
Normalizer2Impl::isCanonSegmentStarter(UChar32 c
) const {
1975 return getCanonValue(c
)>=0;
1978 UBool
Normalizer2Impl::getCanonStartSet(UChar32 c
, UnicodeSet
&set
) const {
1979 int32_t canonValue
=getCanonValue(c
)&~CANON_NOT_SEGMENT_STARTER
;
1984 int32_t value
=canonValue
&CANON_VALUE_MASK
;
1985 if((canonValue
&CANON_HAS_SET
)!=0) {
1986 set
.addAll(getCanonStartSet(value
));
1987 } else if(value
!=0) {
1990 if((canonValue
&CANON_HAS_COMPOSITIONS
)!=0) {
1991 uint16_t norm16
=getNorm16(c
);
1992 if(norm16
==JAMO_L
) {
1994 (UChar32
)(Hangul::HANGUL_BASE
+(c
-Hangul::JAMO_L_BASE
)*Hangul::JAMO_VT_COUNT
);
1995 set
.add(syllable
, syllable
+Hangul::JAMO_VT_COUNT
-1);
1997 addComposites(getCompositionsList(norm16
), set
);
2005 // Normalizer2 data swapping ----------------------------------------------- ***
2009 U_CAPI
int32_t U_EXPORT2
2010 unorm2_swap(const UDataSwapper
*ds
,
2011 const void *inData
, int32_t length
, void *outData
,
2012 UErrorCode
*pErrorCode
) {
2013 const UDataInfo
*pInfo
;
2016 const uint8_t *inBytes
;
2019 const int32_t *inIndexes
;
2020 int32_t indexes
[Normalizer2Impl::IX_MIN_MAYBE_YES
+1];
2022 int32_t i
, offset
, nextOffset
, size
;
2024 /* udata_swapDataHeader checks the arguments */
2025 headerSize
=udata_swapDataHeader(ds
, inData
, length
, outData
, pErrorCode
);
2026 if(pErrorCode
==NULL
|| U_FAILURE(*pErrorCode
)) {
2030 /* check data format and format version */
2031 pInfo
=(const UDataInfo
*)((const char *)inData
+4);
2033 pInfo
->dataFormat
[0]==0x4e && /* dataFormat="Nrm2" */
2034 pInfo
->dataFormat
[1]==0x72 &&
2035 pInfo
->dataFormat
[2]==0x6d &&
2036 pInfo
->dataFormat
[3]==0x32 &&
2037 (pInfo
->formatVersion
[0]==1 || pInfo
->formatVersion
[0]==2)
2039 udata_printError(ds
, "unorm2_swap(): data format %02x.%02x.%02x.%02x (format version %02x) is not recognized as Normalizer2 data\n",
2040 pInfo
->dataFormat
[0], pInfo
->dataFormat
[1],
2041 pInfo
->dataFormat
[2], pInfo
->dataFormat
[3],
2042 pInfo
->formatVersion
[0]);
2043 *pErrorCode
=U_UNSUPPORTED_ERROR
;
2047 inBytes
=(const uint8_t *)inData
+headerSize
;
2048 outBytes
=(uint8_t *)outData
+headerSize
;
2050 inIndexes
=(const int32_t *)inBytes
;
2054 if(length
<(int32_t)sizeof(indexes
)) {
2055 udata_printError(ds
, "unorm2_swap(): too few bytes (%d after header) for Normalizer2 data\n",
2057 *pErrorCode
=U_INDEX_OUTOFBOUNDS_ERROR
;
2062 /* read the first few indexes */
2063 for(i
=0; i
<=Normalizer2Impl::IX_MIN_MAYBE_YES
; ++i
) {
2064 indexes
[i
]=udata_readInt32(ds
, inIndexes
[i
]);
2067 /* get the total length of the data */
2068 size
=indexes
[Normalizer2Impl::IX_TOTAL_SIZE
];
2072 udata_printError(ds
, "unorm2_swap(): too few bytes (%d after header) for all of Normalizer2 data\n",
2074 *pErrorCode
=U_INDEX_OUTOFBOUNDS_ERROR
;
2078 /* copy the data for inaccessible bytes */
2079 if(inBytes
!=outBytes
) {
2080 uprv_memcpy(outBytes
, inBytes
, size
);
2085 /* swap the int32_t indexes[] */
2086 nextOffset
=indexes
[Normalizer2Impl::IX_NORM_TRIE_OFFSET
];
2087 ds
->swapArray32(ds
, inBytes
, nextOffset
-offset
, outBytes
, pErrorCode
);
2090 /* swap the UTrie2 */
2091 nextOffset
=indexes
[Normalizer2Impl::IX_EXTRA_DATA_OFFSET
];
2092 utrie2_swap(ds
, inBytes
+offset
, nextOffset
-offset
, outBytes
+offset
, pErrorCode
);
2095 /* swap the uint16_t extraData[] */
2096 nextOffset
=indexes
[Normalizer2Impl::IX_SMALL_FCD_OFFSET
];
2097 ds
->swapArray16(ds
, inBytes
+offset
, nextOffset
-offset
, outBytes
+offset
, pErrorCode
);
2100 /* no need to swap the uint8_t smallFCD[] (new in formatVersion 2) */
2101 nextOffset
=indexes
[Normalizer2Impl::IX_SMALL_FCD_OFFSET
+1];
2104 U_ASSERT(offset
==size
);
2107 return headerSize
+size
;
2110 #endif // !UCONFIG_NO_NORMALIZATION