diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
commit | 36d22d82aa202bb199967e9512281e9a53db42c9 (patch) | |
tree | 105e8c98ddea1c1e4784a60a5a6410fa416be2de /intl/icu/source/i18n/collationweights.cpp | |
parent | Initial commit. (diff) | |
download | firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip |
Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'intl/icu/source/i18n/collationweights.cpp')
-rw-r--r-- | intl/icu/source/i18n/collationweights.cpp | 570 |
1 files changed, 570 insertions, 0 deletions
diff --git a/intl/icu/source/i18n/collationweights.cpp b/intl/icu/source/i18n/collationweights.cpp new file mode 100644 index 0000000000..2351484590 --- /dev/null +++ b/intl/icu/source/i18n/collationweights.cpp @@ -0,0 +1,570 @@ +// © 2016 and later: Unicode, Inc. and others. +// License & terms of use: http://www.unicode.org/copyright.html +/* +******************************************************************************* +* +* Copyright (C) 1999-2015, International Business Machines +* Corporation and others. All Rights Reserved. +* +******************************************************************************* +* file name: collationweights.cpp +* encoding: UTF-8 +* tab size: 8 (not used) +* indentation:4 +* +* created on: 2001mar08 as ucol_wgt.cpp +* created by: Markus W. Scherer +* +* This file contains code for allocating n collation element weights +* between two exclusive limits. +* It is used only internally by the collation tailoring builder. +*/ + +#include "unicode/utypes.h" + +#if !UCONFIG_NO_COLLATION + +#include "cmemory.h" +#include "collation.h" +#include "collationweights.h" +#include "uarrsort.h" +#include "uassert.h" + +#ifdef UCOL_DEBUG +# include <stdio.h> +#endif + +U_NAMESPACE_BEGIN + +/* collation element weight allocation -------------------------------------- */ + +/* helper functions for CE weights */ + +static inline uint32_t +getWeightTrail(uint32_t weight, int32_t length) { + return (uint32_t)(weight>>(8*(4-length)))&0xff; +} + +static inline uint32_t +setWeightTrail(uint32_t weight, int32_t length, uint32_t trail) { + length=8*(4-length); + return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length)); +} + +static inline uint32_t +getWeightByte(uint32_t weight, int32_t idx) { + return getWeightTrail(weight, idx); /* same calculation */ +} + +static inline uint32_t +setWeightByte(uint32_t weight, int32_t idx, uint32_t byte) { + uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */ + + idx*=8; + if(idx<32) { + mask=((uint32_t)0xffffffff)>>idx; + } else { + // Do not use uint32_t>>32 because on some platforms that does not shift at all + // while we need it to become 0. + // PowerPC: 0xffffffff>>32 = 0 (wanted) + // x86: 0xffffffff>>32 = 0xffffffff (not wanted) + // + // ANSI C99 6.5.7 Bitwise shift operators: + // "If the value of the right operand is negative + // or is greater than or equal to the width of the promoted left operand, + // the behavior is undefined." + mask=0; + } + idx=32-idx; + mask|=0xffffff00<<idx; + return (uint32_t)((weight&mask)|(byte<<idx)); +} + +static inline uint32_t +truncateWeight(uint32_t weight, int32_t length) { + return (uint32_t)(weight&(0xffffffff<<(8*(4-length)))); +} + +static inline uint32_t +incWeightTrail(uint32_t weight, int32_t length) { + return (uint32_t)(weight+(1UL<<(8*(4-length)))); +} + +static inline uint32_t +decWeightTrail(uint32_t weight, int32_t length) { + return (uint32_t)(weight-(1UL<<(8*(4-length)))); +} + +CollationWeights::CollationWeights() + : middleLength(0), rangeIndex(0), rangeCount(0) { + for(int32_t i = 0; i < 5; ++i) { + minBytes[i] = maxBytes[i] = 0; + } +} + +void +CollationWeights::initForPrimary(UBool compressible) { + middleLength=1; + minBytes[1] = Collation::MERGE_SEPARATOR_BYTE + 1; + maxBytes[1] = Collation::TRAIL_WEIGHT_BYTE; + if(compressible) { + minBytes[2] = Collation::PRIMARY_COMPRESSION_LOW_BYTE + 1; + maxBytes[2] = Collation::PRIMARY_COMPRESSION_HIGH_BYTE - 1; + } else { + minBytes[2] = 2; + maxBytes[2] = 0xff; + } + minBytes[3] = 2; + maxBytes[3] = 0xff; + minBytes[4] = 2; + maxBytes[4] = 0xff; +} + +void +CollationWeights::initForSecondary() { + // We use only the lower 16 bits for secondary weights. + middleLength=3; + minBytes[1] = 0; + maxBytes[1] = 0; + minBytes[2] = 0; + maxBytes[2] = 0; + minBytes[3] = Collation::LEVEL_SEPARATOR_BYTE + 1; + maxBytes[3] = 0xff; + minBytes[4] = 2; + maxBytes[4] = 0xff; +} + +void +CollationWeights::initForTertiary() { + // We use only the lower 16 bits for tertiary weights. + middleLength=3; + minBytes[1] = 0; + maxBytes[1] = 0; + minBytes[2] = 0; + maxBytes[2] = 0; + // We use only 6 bits per byte. + // The other bits are used for case & quaternary weights. + minBytes[3] = Collation::LEVEL_SEPARATOR_BYTE + 1; + maxBytes[3] = 0x3f; + minBytes[4] = 2; + maxBytes[4] = 0x3f; +} + +uint32_t +CollationWeights::incWeight(uint32_t weight, int32_t length) const { + for(;;) { + uint32_t byte=getWeightByte(weight, length); + if(byte<maxBytes[length]) { + return setWeightByte(weight, length, byte+1); + } else { + // Roll over, set this byte to the minimum and increment the previous one. + weight=setWeightByte(weight, length, minBytes[length]); + --length; + U_ASSERT(length > 0); + } + } +} + +uint32_t +CollationWeights::incWeightByOffset(uint32_t weight, int32_t length, int32_t offset) const { + for(;;) { + offset += getWeightByte(weight, length); + if((uint32_t)offset <= maxBytes[length]) { + return setWeightByte(weight, length, offset); + } else { + // Split the offset between this byte and the previous one. + offset -= minBytes[length]; + weight = setWeightByte(weight, length, minBytes[length] + offset % countBytes(length)); + offset /= countBytes(length); + --length; + U_ASSERT(length > 0); + } + } +} + +void +CollationWeights::lengthenRange(WeightRange &range) const { + int32_t length=range.length+1; + range.start=setWeightTrail(range.start, length, minBytes[length]); + range.end=setWeightTrail(range.end, length, maxBytes[length]); + range.count*=countBytes(length); + range.length=length; +} + +/* for uprv_sortArray: sort ranges in weight order */ +static int32_t U_CALLCONV +compareRanges(const void * /*context*/, const void *left, const void *right) { + uint32_t l, r; + + l=((const CollationWeights::WeightRange *)left)->start; + r=((const CollationWeights::WeightRange *)right)->start; + if(l<r) { + return -1; + } else if(l>r) { + return 1; + } else { + return 0; + } +} + +UBool +CollationWeights::getWeightRanges(uint32_t lowerLimit, uint32_t upperLimit) { + U_ASSERT(lowerLimit != 0); + U_ASSERT(upperLimit != 0); + + /* get the lengths of the limits */ + int32_t lowerLength=lengthOfWeight(lowerLimit); + int32_t upperLength=lengthOfWeight(upperLimit); + +#ifdef UCOL_DEBUG + printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength); + printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength); +#endif + U_ASSERT(lowerLength>=middleLength); + // Permit upperLength<middleLength: The upper limit for secondaries is 0x10000. + + if(lowerLimit>=upperLimit) { +#ifdef UCOL_DEBUG + printf("error: no space between lower & upper limits\n"); +#endif + return false; + } + + /* check that neither is a prefix of the other */ + if(lowerLength<upperLength) { + if(lowerLimit==truncateWeight(upperLimit, lowerLength)) { +#ifdef UCOL_DEBUG + printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit); +#endif + return false; + } + } + /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */ + + WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */ + uprv_memset(lower, 0, sizeof(lower)); + uprv_memset(&middle, 0, sizeof(middle)); + uprv_memset(upper, 0, sizeof(upper)); + + /* + * With the limit lengths of 1..4, there are up to 7 ranges for allocation: + * range minimum length + * lower[4] 4 + * lower[3] 3 + * lower[2] 2 + * middle 1 + * upper[2] 2 + * upper[3] 3 + * upper[4] 4 + * + * We are now going to calculate up to 7 ranges. + * Some of them will typically overlap, so we will then have to merge and eliminate ranges. + */ + uint32_t weight=lowerLimit; + for(int32_t length=lowerLength; length>middleLength; --length) { + uint32_t trail=getWeightTrail(weight, length); + if(trail<maxBytes[length]) { + lower[length].start=incWeightTrail(weight, length); + lower[length].end=setWeightTrail(weight, length, maxBytes[length]); + lower[length].length=length; + lower[length].count=maxBytes[length]-trail; + } + weight=truncateWeight(weight, length-1); + } + if(weight<0xff000000) { + middle.start=incWeightTrail(weight, middleLength); + } else { + // Prevent overflow for primary lead byte FF + // which would yield a middle range starting at 0. + middle.start=0xffffffff; // no middle range + } + + weight=upperLimit; + for(int32_t length=upperLength; length>middleLength; --length) { + uint32_t trail=getWeightTrail(weight, length); + if(trail>minBytes[length]) { + upper[length].start=setWeightTrail(weight, length, minBytes[length]); + upper[length].end=decWeightTrail(weight, length); + upper[length].length=length; + upper[length].count=trail-minBytes[length]; + } + weight=truncateWeight(weight, length-1); + } + middle.end=decWeightTrail(weight, middleLength); + + /* set the middle range */ + middle.length=middleLength; + if(middle.end>=middle.start) { + middle.count=(int32_t)((middle.end-middle.start)>>(8*(4-middleLength)))+1; + } else { + /* no middle range, eliminate overlaps */ + for(int32_t length=4; length>middleLength; --length) { + if(lower[length].count>0 && upper[length].count>0) { + // Note: The lowerEnd and upperStart weights are versions of + // lowerLimit and upperLimit (which are lowerLimit<upperLimit), + // truncated (still less-or-equal) + // and then with their last bytes changed to the + // maxByte (for lowerEnd) or minByte (for upperStart). + const uint32_t lowerEnd=lower[length].end; + const uint32_t upperStart=upper[length].start; + UBool merged=false; + + if(lowerEnd>upperStart) { + // These two lower and upper ranges collide. + // Since lowerLimit<upperLimit and lowerEnd and upperStart + // are versions with only their last bytes modified + // (and following ones removed/reset to 0), + // lowerEnd>upperStart is only possible + // if the leading bytes are equal + // and lastByte(lowerEnd)>lastByte(upperStart). + U_ASSERT(truncateWeight(lowerEnd, length-1)== + truncateWeight(upperStart, length-1)); + // Intersect these two ranges. + lower[length].end=upper[length].end; + lower[length].count= + (int32_t)getWeightTrail(lower[length].end, length)- + (int32_t)getWeightTrail(lower[length].start, length)+1; + // count might be <=0 in which case there is no room, + // and the range-collecting code below will ignore this range. + merged=true; + } else if(lowerEnd==upperStart) { + // Not possible, unless minByte==maxByte which is not allowed. + U_ASSERT(minBytes[length]<maxBytes[length]); + } else /* lowerEnd<upperStart */ { + if(incWeight(lowerEnd, length)==upperStart) { + // Merge adjacent ranges. + lower[length].end=upper[length].end; + lower[length].count+=upper[length].count; // might be >countBytes + merged=true; + } + } + if(merged) { + // Remove all shorter ranges. + // There was no room available for them between the ranges we just merged. + upper[length].count=0; + while(--length>middleLength) { + lower[length].count=upper[length].count=0; + } + break; + } + } + } + } + +#ifdef UCOL_DEBUG + /* print ranges */ + for(int32_t length=4; length>=2; --length) { + if(lower[length].count>0) { + printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count); + } + } + if(middle.count>0) { + printf("middle .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count); + } + for(int32_t length=2; length<=4; ++length) { + if(upper[length].count>0) { + printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count); + } + } +#endif + + /* copy the ranges, shortest first, into the result array */ + rangeCount=0; + if(middle.count>0) { + uprv_memcpy(ranges, &middle, sizeof(WeightRange)); + rangeCount=1; + } + for(int32_t length=middleLength+1; length<=4; ++length) { + /* copy upper first so that later the middle range is more likely the first one to use */ + if(upper[length].count>0) { + uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange)); + ++rangeCount; + } + if(lower[length].count>0) { + uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange)); + ++rangeCount; + } + } + return rangeCount>0; +} + +UBool +CollationWeights::allocWeightsInShortRanges(int32_t n, int32_t minLength) { + // See if the first few minLength and minLength+1 ranges have enough weights. + for(int32_t i = 0; i < rangeCount && ranges[i].length <= (minLength + 1); ++i) { + if(n <= ranges[i].count) { + // Use the first few minLength and minLength+1 ranges. + if(ranges[i].length > minLength) { + // Reduce the number of weights from the last minLength+1 range + // which might sort before some minLength ranges, + // so that we use all weights in the minLength ranges. + ranges[i].count = n; + } + rangeCount = i + 1; +#ifdef UCOL_DEBUG + printf("take first %ld ranges\n", rangeCount); +#endif + + if(rangeCount>1) { + /* sort the ranges by weight values */ + UErrorCode errorCode=U_ZERO_ERROR; + uprv_sortArray(ranges, rangeCount, sizeof(WeightRange), + compareRanges, nullptr, false, &errorCode); + /* ignore error code: we know that the internal sort function will not fail here */ + } + return true; + } + n -= ranges[i].count; // still >0 + } + return false; +} + +UBool +CollationWeights::allocWeightsInMinLengthRanges(int32_t n, int32_t minLength) { + // See if the minLength ranges have enough weights + // when we split one and lengthen the following ones. + int32_t count = 0; + int32_t minLengthRangeCount; + for(minLengthRangeCount = 0; + minLengthRangeCount < rangeCount && + ranges[minLengthRangeCount].length == minLength; + ++minLengthRangeCount) { + count += ranges[minLengthRangeCount].count; + } + + int32_t nextCountBytes = countBytes(minLength + 1); + if(n > count * nextCountBytes) { return false; } + + // Use the minLength ranges. Merge them, and then split again as necessary. + uint32_t start = ranges[0].start; + uint32_t end = ranges[0].end; + for(int32_t i = 1; i < minLengthRangeCount; ++i) { + if(ranges[i].start < start) { start = ranges[i].start; } + if(ranges[i].end > end) { end = ranges[i].end; } + } + + // Calculate how to split the range between minLength (count1) and minLength+1 (count2). + // Goal: + // count1 + count2 * nextCountBytes = n + // count1 + count2 = count + // These turn into + // (count - count2) + count2 * nextCountBytes = n + // and then into the following count1 & count2 computations. + int32_t count2 = (n - count) / (nextCountBytes - 1); // number of weights to be lengthened + int32_t count1 = count - count2; // number of minLength weights + if(count2 == 0 || (count1 + count2 * nextCountBytes) < n) { + // round up + ++count2; + --count1; + U_ASSERT((count1 + count2 * nextCountBytes) >= n); + } + + ranges[0].start = start; + + if(count1 == 0) { + // Make one long range. + ranges[0].end = end; + ranges[0].count = count; + lengthenRange(ranges[0]); + rangeCount = 1; + } else { + // Split the range, lengthen the second part. +#ifdef UCOL_DEBUG + printf("split the range number %ld (out of %ld minLength ranges) by %ld:%ld\n", + splitRange, rangeCount, count1, count2); +#endif + + // Next start = start + count1. First end = 1 before that. + ranges[0].end = incWeightByOffset(start, minLength, count1 - 1); + ranges[0].count = count1; + + ranges[1].start = incWeight(ranges[0].end, minLength); + ranges[1].end = end; + ranges[1].length = minLength; // +1 when lengthened + ranges[1].count = count2; // *countBytes when lengthened + lengthenRange(ranges[1]); + rangeCount = 2; + } + return true; +} + +/* + * call getWeightRanges and then determine heuristically + * which ranges to use for a given number of weights between (excluding) + * two limits + */ +UBool +CollationWeights::allocWeights(uint32_t lowerLimit, uint32_t upperLimit, int32_t n) { +#ifdef UCOL_DEBUG + puts(""); +#endif + + if(!getWeightRanges(lowerLimit, upperLimit)) { +#ifdef UCOL_DEBUG + printf("error: unable to get Weight ranges\n"); +#endif + return false; + } + + /* try until we find suitably large ranges */ + for(;;) { + /* get the smallest number of bytes in a range */ + int32_t minLength=ranges[0].length; + + if(allocWeightsInShortRanges(n, minLength)) { break; } + + if(minLength == 4) { +#ifdef UCOL_DEBUG + printf("error: the maximum number of %ld weights is insufficient for n=%ld\n", + minLengthCount, n); +#endif + return false; + } + + if(allocWeightsInMinLengthRanges(n, minLength)) { break; } + + /* no good match, lengthen all minLength ranges and iterate */ +#ifdef UCOL_DEBUG + printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1); +#endif + for(int32_t i=0; i<rangeCount && ranges[i].length==minLength; ++i) { + lengthenRange(ranges[i]); + } + } + +#ifdef UCOL_DEBUG + puts("final ranges:"); + for(int32_t i=0; i<rangeCount; ++i) { + printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .count=%ld\n", + i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].count); + } +#endif + + rangeIndex = 0; + return true; +} + +uint32_t +CollationWeights::nextWeight() { + if(rangeIndex >= rangeCount) { + return 0xffffffff; + } else { + /* get the next weight */ + WeightRange &range = ranges[rangeIndex]; + uint32_t weight = range.start; + if(--range.count == 0) { + /* this range is finished */ + ++rangeIndex; + } else { + /* increment the weight for the next value */ + range.start = incWeight(weight, range.length); + U_ASSERT(range.start <= range.end); + } + + return weight; + } +} + +U_NAMESPACE_END + +#endif /* #if !UCONFIG_NO_COLLATION */ |