// © 2017 and later: Unicode, Inc. and others. // License & terms of use: http://www.unicode.org/copyright.html // ucptrie.cpp (modified from utrie2.cpp) // created: 2017dec29 Markus W. Scherer // #define UCPTRIE_DEBUG #ifdef UCPTRIE_DEBUG # include <stdio.h> #endif #include "unicode/utypes.h" #include "unicode/ucptrie.h" #include "unicode/utf.h" #include "unicode/utf8.h" #include "unicode/utf16.h" #include "cmemory.h" #include "uassert.h" #include "ucptrie_impl.h" U_CAPI UCPTrie * U_EXPORT2 ucptrie_openFromBinary(UCPTrieType type, UCPTrieValueWidth valueWidth, const void *data, int32_t length, int32_t *pActualLength, UErrorCode *pErrorCode) { if (U_FAILURE(*pErrorCode)) { return nullptr; } if (length <= 0 || (U_POINTER_MASK_LSB(data, 3) != 0) || type < UCPTRIE_TYPE_ANY || UCPTRIE_TYPE_SMALL < type || valueWidth < UCPTRIE_VALUE_BITS_ANY || UCPTRIE_VALUE_BITS_8 < valueWidth) { *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR; return nullptr; } // Enough data for a trie header? if (length < (int32_t)sizeof(UCPTrieHeader)) { *pErrorCode = U_INVALID_FORMAT_ERROR; return nullptr; } // Check the signature. const UCPTrieHeader *header = (const UCPTrieHeader *)data; if (header->signature != UCPTRIE_SIG) { *pErrorCode = U_INVALID_FORMAT_ERROR; return nullptr; } int32_t options = header->options; int32_t typeInt = (options >> 6) & 3; int32_t valueWidthInt = options & UCPTRIE_OPTIONS_VALUE_BITS_MASK; if (typeInt > UCPTRIE_TYPE_SMALL || valueWidthInt > UCPTRIE_VALUE_BITS_8 || (options & UCPTRIE_OPTIONS_RESERVED_MASK) != 0) { *pErrorCode = U_INVALID_FORMAT_ERROR; return nullptr; } UCPTrieType actualType = (UCPTrieType)typeInt; UCPTrieValueWidth actualValueWidth = (UCPTrieValueWidth)valueWidthInt; if (type < 0) { type = actualType; } if (valueWidth < 0) { valueWidth = actualValueWidth; } if (type != actualType || valueWidth != actualValueWidth) { *pErrorCode = U_INVALID_FORMAT_ERROR; return nullptr; } // Get the length values and offsets. UCPTrie tempTrie; uprv_memset(&tempTrie, 0, sizeof(tempTrie)); tempTrie.indexLength = header->indexLength; tempTrie.dataLength = ((options & UCPTRIE_OPTIONS_DATA_LENGTH_MASK) << 4) | header->dataLength; tempTrie.index3NullOffset = header->index3NullOffset; tempTrie.dataNullOffset = ((options & UCPTRIE_OPTIONS_DATA_NULL_OFFSET_MASK) << 8) | header->dataNullOffset; tempTrie.highStart = header->shiftedHighStart << UCPTRIE_SHIFT_2; tempTrie.shifted12HighStart = (tempTrie.highStart + 0xfff) >> 12; tempTrie.type = type; tempTrie.valueWidth = valueWidth; // Calculate the actual length. int32_t actualLength = (int32_t)sizeof(UCPTrieHeader) + tempTrie.indexLength * 2; if (valueWidth == UCPTRIE_VALUE_BITS_16) { actualLength += tempTrie.dataLength * 2; } else if (valueWidth == UCPTRIE_VALUE_BITS_32) { actualLength += tempTrie.dataLength * 4; } else { actualLength += tempTrie.dataLength; } if (length < actualLength) { *pErrorCode = U_INVALID_FORMAT_ERROR; // Not enough bytes. return nullptr; } // Allocate the trie. UCPTrie *trie = (UCPTrie *)uprv_malloc(sizeof(UCPTrie)); if (trie == nullptr) { *pErrorCode = U_MEMORY_ALLOCATION_ERROR; return nullptr; } uprv_memcpy(trie, &tempTrie, sizeof(tempTrie)); #ifdef UCPTRIE_DEBUG trie->name = "fromSerialized"; #endif // Set the pointers to its index and data arrays. const uint16_t *p16 = (const uint16_t *)(header + 1); trie->index = p16; p16 += trie->indexLength; // Get the data. int32_t nullValueOffset = trie->dataNullOffset; if (nullValueOffset >= trie->dataLength) { nullValueOffset = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; } switch (valueWidth) { case UCPTRIE_VALUE_BITS_16: trie->data.ptr16 = p16; trie->nullValue = trie->data.ptr16[nullValueOffset]; break; case UCPTRIE_VALUE_BITS_32: trie->data.ptr32 = (const uint32_t *)p16; trie->nullValue = trie->data.ptr32[nullValueOffset]; break; case UCPTRIE_VALUE_BITS_8: trie->data.ptr8 = (const uint8_t *)p16; trie->nullValue = trie->data.ptr8[nullValueOffset]; break; default: // Unreachable because valueWidth was checked above. *pErrorCode = U_INVALID_FORMAT_ERROR; return nullptr; } if (pActualLength != nullptr) { *pActualLength = actualLength; } return trie; } U_CAPI void U_EXPORT2 ucptrie_close(UCPTrie *trie) { uprv_free(trie); } U_CAPI UCPTrieType U_EXPORT2 ucptrie_getType(const UCPTrie *trie) { return (UCPTrieType)trie->type; } U_CAPI UCPTrieValueWidth U_EXPORT2 ucptrie_getValueWidth(const UCPTrie *trie) { return (UCPTrieValueWidth)trie->valueWidth; } U_CAPI int32_t U_EXPORT2 ucptrie_internalSmallIndex(const UCPTrie *trie, UChar32 c) { int32_t i1 = c >> UCPTRIE_SHIFT_1; if (trie->type == UCPTRIE_TYPE_FAST) { U_ASSERT(0xffff < c && c < trie->highStart); i1 += UCPTRIE_BMP_INDEX_LENGTH - UCPTRIE_OMITTED_BMP_INDEX_1_LENGTH; } else { U_ASSERT((uint32_t)c < (uint32_t)trie->highStart && trie->highStart > UCPTRIE_SMALL_LIMIT); i1 += UCPTRIE_SMALL_INDEX_LENGTH; } int32_t i3Block = trie->index[ (int32_t)trie->index[i1] + ((c >> UCPTRIE_SHIFT_2) & UCPTRIE_INDEX_2_MASK)]; int32_t i3 = (c >> UCPTRIE_SHIFT_3) & UCPTRIE_INDEX_3_MASK; int32_t dataBlock; if ((i3Block & 0x8000) == 0) { // 16-bit indexes dataBlock = trie->index[i3Block + i3]; } else { // 18-bit indexes stored in groups of 9 entries per 8 indexes. i3Block = (i3Block & 0x7fff) + (i3 & ~7) + (i3 >> 3); i3 &= 7; dataBlock = ((int32_t)trie->index[i3Block++] << (2 + (2 * i3))) & 0x30000; dataBlock |= trie->index[i3Block + i3]; } return dataBlock + (c & UCPTRIE_SMALL_DATA_MASK); } U_CAPI int32_t U_EXPORT2 ucptrie_internalSmallU8Index(const UCPTrie *trie, int32_t lt1, uint8_t t2, uint8_t t3) { UChar32 c = (lt1 << 12) | (t2 << 6) | t3; if (c >= trie->highStart) { // Possible because the UTF-8 macro compares with shifted12HighStart which may be higher. return trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; } return ucptrie_internalSmallIndex(trie, c); } U_CAPI int32_t U_EXPORT2 ucptrie_internalU8PrevIndex(const UCPTrie *trie, UChar32 c, const uint8_t *start, const uint8_t *src) { int32_t i, length; // Support 64-bit pointers by avoiding cast of arbitrary difference. if ((src - start) <= 7) { i = length = (int32_t)(src - start); } else { i = length = 7; start = src - 7; } c = utf8_prevCharSafeBody(start, 0, &i, c, -1); i = length - i; // Number of bytes read backward from src. int32_t idx = _UCPTRIE_CP_INDEX(trie, 0xffff, c); return (idx << 3) | i; } namespace { inline uint32_t getValue(UCPTrieData data, UCPTrieValueWidth valueWidth, int32_t dataIndex) { switch (valueWidth) { case UCPTRIE_VALUE_BITS_16: return data.ptr16[dataIndex]; case UCPTRIE_VALUE_BITS_32: return data.ptr32[dataIndex]; case UCPTRIE_VALUE_BITS_8: return data.ptr8[dataIndex]; default: // Unreachable if the trie is properly initialized. return 0xffffffff; } } } // namespace U_CAPI uint32_t U_EXPORT2 ucptrie_get(const UCPTrie *trie, UChar32 c) { int32_t dataIndex; if ((uint32_t)c <= 0x7f) { // linear ASCII dataIndex = c; } else { UChar32 fastMax = trie->type == UCPTRIE_TYPE_FAST ? 0xffff : UCPTRIE_SMALL_MAX; dataIndex = _UCPTRIE_CP_INDEX(trie, fastMax, c); } return getValue(trie->data, (UCPTrieValueWidth)trie->valueWidth, dataIndex); } namespace { constexpr int32_t MAX_UNICODE = 0x10ffff; inline uint32_t maybeFilterValue(uint32_t value, uint32_t trieNullValue, uint32_t nullValue, UCPMapValueFilter *filter, const void *context) { if (value == trieNullValue) { value = nullValue; } else if (filter != nullptr) { value = filter(context, value); } return value; } UChar32 getRange(const void *t, UChar32 start, UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { if ((uint32_t)start > MAX_UNICODE) { return U_SENTINEL; } const UCPTrie *trie = reinterpret_cast<const UCPTrie *>(t); UCPTrieValueWidth valueWidth = (UCPTrieValueWidth)trie->valueWidth; if (start >= trie->highStart) { if (pValue != nullptr) { int32_t di = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; uint32_t value = getValue(trie->data, valueWidth, di); if (filter != nullptr) { value = filter(context, value); } *pValue = value; } return MAX_UNICODE; } uint32_t nullValue = trie->nullValue; if (filter != nullptr) { nullValue = filter(context, nullValue); } const uint16_t *index = trie->index; int32_t prevI3Block = -1; int32_t prevBlock = -1; UChar32 c = start; uint32_t trieValue, value = nullValue; bool haveValue = false; do { int32_t i3Block; int32_t i3; int32_t i3BlockLength; int32_t dataBlockLength; if (c <= 0xffff && (trie->type == UCPTRIE_TYPE_FAST || c <= UCPTRIE_SMALL_MAX)) { i3Block = 0; i3 = c >> UCPTRIE_FAST_SHIFT; i3BlockLength = trie->type == UCPTRIE_TYPE_FAST ? UCPTRIE_BMP_INDEX_LENGTH : UCPTRIE_SMALL_INDEX_LENGTH; dataBlockLength = UCPTRIE_FAST_DATA_BLOCK_LENGTH; } else { // Use the multi-stage index. int32_t i1 = c >> UCPTRIE_SHIFT_1; if (trie->type == UCPTRIE_TYPE_FAST) { U_ASSERT(0xffff < c && c < trie->highStart); i1 += UCPTRIE_BMP_INDEX_LENGTH - UCPTRIE_OMITTED_BMP_INDEX_1_LENGTH; } else { U_ASSERT(c < trie->highStart && trie->highStart > UCPTRIE_SMALL_LIMIT); i1 += UCPTRIE_SMALL_INDEX_LENGTH; } i3Block = trie->index[ (int32_t)trie->index[i1] + ((c >> UCPTRIE_SHIFT_2) & UCPTRIE_INDEX_2_MASK)]; if (i3Block == prevI3Block && (c - start) >= UCPTRIE_CP_PER_INDEX_2_ENTRY) { // The index-3 block is the same as the previous one, and filled with value. U_ASSERT((c & (UCPTRIE_CP_PER_INDEX_2_ENTRY - 1)) == 0); c += UCPTRIE_CP_PER_INDEX_2_ENTRY; continue; } prevI3Block = i3Block; if (i3Block == trie->index3NullOffset) { // This is the index-3 null block. if (haveValue) { if (nullValue != value) { return c - 1; } } else { trieValue = trie->nullValue; value = nullValue; if (pValue != nullptr) { *pValue = nullValue; } haveValue = true; } prevBlock = trie->dataNullOffset; c = (c + UCPTRIE_CP_PER_INDEX_2_ENTRY) & ~(UCPTRIE_CP_PER_INDEX_2_ENTRY - 1); continue; } i3 = (c >> UCPTRIE_SHIFT_3) & UCPTRIE_INDEX_3_MASK; i3BlockLength = UCPTRIE_INDEX_3_BLOCK_LENGTH; dataBlockLength = UCPTRIE_SMALL_DATA_BLOCK_LENGTH; } // Enumerate data blocks for one index-3 block. do { int32_t block; if ((i3Block & 0x8000) == 0) { block = index[i3Block + i3]; } else { // 18-bit indexes stored in groups of 9 entries per 8 indexes. int32_t group = (i3Block & 0x7fff) + (i3 & ~7) + (i3 >> 3); int32_t gi = i3 & 7; block = ((int32_t)index[group++] << (2 + (2 * gi))) & 0x30000; block |= index[group + gi]; } if (block == prevBlock && (c - start) >= dataBlockLength) { // The block is the same as the previous one, and filled with value. U_ASSERT((c & (dataBlockLength - 1)) == 0); c += dataBlockLength; } else { int32_t dataMask = dataBlockLength - 1; prevBlock = block; if (block == trie->dataNullOffset) { // This is the data null block. if (haveValue) { if (nullValue != value) { return c - 1; } } else { trieValue = trie->nullValue; value = nullValue; if (pValue != nullptr) { *pValue = nullValue; } haveValue = true; } c = (c + dataBlockLength) & ~dataMask; } else { int32_t di = block + (c & dataMask); uint32_t trieValue2 = getValue(trie->data, valueWidth, di); if (haveValue) { if (trieValue2 != trieValue) { if (filter == nullptr || maybeFilterValue(trieValue2, trie->nullValue, nullValue, filter, context) != value) { return c - 1; } trieValue = trieValue2; // may or may not help } } else { trieValue = trieValue2; value = maybeFilterValue(trieValue2, trie->nullValue, nullValue, filter, context); if (pValue != nullptr) { *pValue = value; } haveValue = true; } while ((++c & dataMask) != 0) { trieValue2 = getValue(trie->data, valueWidth, ++di); if (trieValue2 != trieValue) { if (filter == nullptr || maybeFilterValue(trieValue2, trie->nullValue, nullValue, filter, context) != value) { return c - 1; } trieValue = trieValue2; // may or may not help } } } } } while (++i3 < i3BlockLength); } while (c < trie->highStart); U_ASSERT(haveValue); int32_t di = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; uint32_t highValue = getValue(trie->data, valueWidth, di); if (maybeFilterValue(highValue, trie->nullValue, nullValue, filter, context) != value) { return c - 1; } else { return MAX_UNICODE; } } } // namespace U_CFUNC UChar32 ucptrie_internalGetRange(UCPTrieGetRange *getRange, const void *trie, UChar32 start, UCPMapRangeOption option, uint32_t surrogateValue, UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { if (option == UCPMAP_RANGE_NORMAL) { return getRange(trie, start, filter, context, pValue); } uint32_t value; if (pValue == nullptr) { // We need to examine the range value even if the caller does not want it. pValue = &value; } UChar32 surrEnd = option == UCPMAP_RANGE_FIXED_ALL_SURROGATES ? 0xdfff : 0xdbff; UChar32 end = getRange(trie, start, filter, context, pValue); if (end < 0xd7ff || start > surrEnd) { return end; } // The range overlaps with surrogates, or ends just before the first one. if (*pValue == surrogateValue) { if (end >= surrEnd) { // Surrogates followed by a non-surrogateValue range, // or surrogates are part of a larger surrogateValue range. return end; } } else { if (start <= 0xd7ff) { return 0xd7ff; // Non-surrogateValue range ends before surrogateValue surrogates. } // Start is a surrogate with a non-surrogateValue code *unit* value. // Return a surrogateValue code *point* range. *pValue = surrogateValue; if (end > surrEnd) { return surrEnd; // Surrogate range ends before non-surrogateValue rest of range. } } // See if the surrogateValue surrogate range can be merged with // an immediately following range. uint32_t value2; UChar32 end2 = getRange(trie, surrEnd + 1, filter, context, &value2); if (value2 == surrogateValue) { return end2; } return surrEnd; } U_CAPI UChar32 U_EXPORT2 ucptrie_getRange(const UCPTrie *trie, UChar32 start, UCPMapRangeOption option, uint32_t surrogateValue, UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { return ucptrie_internalGetRange(getRange, trie, start, option, surrogateValue, filter, context, pValue); } U_CAPI int32_t U_EXPORT2 ucptrie_toBinary(const UCPTrie *trie, void *data, int32_t capacity, UErrorCode *pErrorCode) { if (U_FAILURE(*pErrorCode)) { return 0; } UCPTrieType type = (UCPTrieType)trie->type; UCPTrieValueWidth valueWidth = (UCPTrieValueWidth)trie->valueWidth; if (type < UCPTRIE_TYPE_FAST || UCPTRIE_TYPE_SMALL < type || valueWidth < UCPTRIE_VALUE_BITS_16 || UCPTRIE_VALUE_BITS_8 < valueWidth || capacity < 0 || (capacity > 0 && (data == nullptr || (U_POINTER_MASK_LSB(data, 3) != 0)))) { *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR; return 0; } int32_t length = (int32_t)sizeof(UCPTrieHeader) + trie->indexLength * 2; switch (valueWidth) { case UCPTRIE_VALUE_BITS_16: length += trie->dataLength * 2; break; case UCPTRIE_VALUE_BITS_32: length += trie->dataLength * 4; break; case UCPTRIE_VALUE_BITS_8: length += trie->dataLength; break; default: // unreachable break; } if (capacity < length) { *pErrorCode = U_BUFFER_OVERFLOW_ERROR; return length; } char *bytes = (char *)data; UCPTrieHeader *header = (UCPTrieHeader *)bytes; header->signature = UCPTRIE_SIG; // "Tri3" header->options = (uint16_t)( ((trie->dataLength & 0xf0000) >> 4) | ((trie->dataNullOffset & 0xf0000) >> 8) | (trie->type << 6) | valueWidth); header->indexLength = (uint16_t)trie->indexLength; header->dataLength = (uint16_t)trie->dataLength; header->index3NullOffset = trie->index3NullOffset; header->dataNullOffset = (uint16_t)trie->dataNullOffset; header->shiftedHighStart = trie->highStart >> UCPTRIE_SHIFT_2; bytes += sizeof(UCPTrieHeader); uprv_memcpy(bytes, trie->index, trie->indexLength * 2); bytes += trie->indexLength * 2; switch (valueWidth) { case UCPTRIE_VALUE_BITS_16: uprv_memcpy(bytes, trie->data.ptr16, trie->dataLength * 2); break; case UCPTRIE_VALUE_BITS_32: uprv_memcpy(bytes, trie->data.ptr32, trie->dataLength * 4); break; case UCPTRIE_VALUE_BITS_8: uprv_memcpy(bytes, trie->data.ptr8, trie->dataLength); break; default: // unreachable break; } return length; } namespace { #ifdef UCPTRIE_DEBUG long countNull(const UCPTrie *trie) { uint32_t nullValue=trie->nullValue; int32_t length=trie->dataLength; long count=0; switch (trie->valueWidth) { case UCPTRIE_VALUE_BITS_16: for(int32_t i=0; i<length; ++i) { if(trie->data.ptr16[i]==nullValue) { ++count; } } break; case UCPTRIE_VALUE_BITS_32: for(int32_t i=0; i<length; ++i) { if(trie->data.ptr32[i]==nullValue) { ++count; } } break; case UCPTRIE_VALUE_BITS_8: for(int32_t i=0; i<length; ++i) { if(trie->data.ptr8[i]==nullValue) { ++count; } } break; default: // unreachable break; } return count; } U_CFUNC void ucptrie_printLengths(const UCPTrie *trie, const char *which) { long indexLength=trie->indexLength; long dataLength=(long)trie->dataLength; long totalLength=(long)sizeof(UCPTrieHeader)+indexLength*2+ dataLength*(trie->valueWidth==UCPTRIE_VALUE_BITS_16 ? 2 : trie->valueWidth==UCPTRIE_VALUE_BITS_32 ? 4 : 1); printf("**UCPTrieLengths(%s %s)** index:%6ld data:%6ld countNull:%6ld serialized:%6ld\n", which, trie->name, indexLength, dataLength, countNull(trie), totalLength); } #endif } // namespace // UCPMap ---- // Initially, this is the same as UCPTrie. This may well change. U_CAPI uint32_t U_EXPORT2 ucpmap_get(const UCPMap *map, UChar32 c) { return ucptrie_get(reinterpret_cast<const UCPTrie *>(map), c); } U_CAPI UChar32 U_EXPORT2 ucpmap_getRange(const UCPMap *map, UChar32 start, UCPMapRangeOption option, uint32_t surrogateValue, UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { return ucptrie_getRange(reinterpret_cast<const UCPTrie *>(map), start, option, surrogateValue, filter, context, pValue); }