| // © 2016 and later: Unicode, Inc. and others. | |
| // License & terms of use: http://www.unicode.org/copyright.html | |
| /* | |
| ******************************************************************************* | |
| * Copyright (C) 2010-2011, International Business Machines | |
| * Corporation and others. All Rights Reserved. | |
| ******************************************************************************* | |
| * file name: bytestrie.cpp | |
| * encoding: UTF-8 | |
| * tab size: 8 (not used) | |
| * indentation:4 | |
| * | |
| * created on: 2010sep25 | |
| * created by: Markus W. Scherer | |
| */ | |
| #if defined(STARBOARD) | |
| #include "starboard/client_porting/poem/assert_poem.h" | |
| #include "starboard/client_porting/poem/string_poem.h" | |
| #endif // defined(STARBOARD) | |
| #include "unicode/utypes.h" | |
| #include "unicode/bytestream.h" | |
| #include "unicode/bytestrie.h" | |
| #include "unicode/uobject.h" | |
| #include "cmemory.h" | |
| #include "uassert.h" | |
| U_NAMESPACE_BEGIN | |
| BytesTrie::~BytesTrie() { | |
| uprv_free(ownedArray_); | |
| } | |
| // lead byte already shifted right by 1. | |
| int32_t | |
| BytesTrie::readValue(const uint8_t *pos, int32_t leadByte) { | |
| int32_t value; | |
| if(leadByte<kMinTwoByteValueLead) { | |
| value=leadByte-kMinOneByteValueLead; | |
| } else if(leadByte<kMinThreeByteValueLead) { | |
| value=((leadByte-kMinTwoByteValueLead)<<8)|*pos; | |
| } else if(leadByte<kFourByteValueLead) { | |
| value=((leadByte-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; | |
| } else if(leadByte==kFourByteValueLead) { | |
| value=(pos[0]<<16)|(pos[1]<<8)|pos[2]; | |
| } else { | |
| value=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; | |
| } | |
| return value; | |
| } | |
| const uint8_t * | |
| BytesTrie::jumpByDelta(const uint8_t *pos) { | |
| int32_t delta=*pos++; | |
| if(delta<kMinTwoByteDeltaLead) { | |
| // nothing to do | |
| } else if(delta<kMinThreeByteDeltaLead) { | |
| delta=((delta-kMinTwoByteDeltaLead)<<8)|*pos++; | |
| } else if(delta<kFourByteDeltaLead) { | |
| delta=((delta-kMinThreeByteDeltaLead)<<16)|(pos[0]<<8)|pos[1]; | |
| pos+=2; | |
| } else if(delta==kFourByteDeltaLead) { | |
| delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; | |
| pos+=3; | |
| } else { | |
| delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; | |
| pos+=4; | |
| } | |
| return pos+delta; | |
| } | |
| UStringTrieResult | |
| BytesTrie::current() const { | |
| const uint8_t *pos=pos_; | |
| if(pos==NULL) { | |
| return USTRINGTRIE_NO_MATCH; | |
| } else { | |
| int32_t node; | |
| return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ? | |
| valueResult(node) : USTRINGTRIE_NO_VALUE; | |
| } | |
| } | |
| UStringTrieResult | |
| BytesTrie::branchNext(const uint8_t *pos, int32_t length, int32_t inByte) { | |
| // Branch according to the current byte. | |
| if(length==0) { | |
| length=*pos++; | |
| } | |
| ++length; | |
| // The length of the branch is the number of bytes to select from. | |
| // The data structure encodes a binary search. | |
| while(length>kMaxBranchLinearSubNodeLength) { | |
| if(inByte<*pos++) { | |
| length>>=1; | |
| pos=jumpByDelta(pos); | |
| } else { | |
| length=length-(length>>1); | |
| pos=skipDelta(pos); | |
| } | |
| } | |
| // Drop down to linear search for the last few bytes. | |
| // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3 | |
| // and divides length by 2. | |
| do { | |
| if(inByte==*pos++) { | |
| UStringTrieResult result; | |
| int32_t node=*pos; | |
| U_ASSERT(node>=kMinValueLead); | |
| if(node&kValueIsFinal) { | |
| // Leave the final value for getValue() to read. | |
| result=USTRINGTRIE_FINAL_VALUE; | |
| } else { | |
| // Use the non-final value as the jump delta. | |
| ++pos; | |
| // int32_t delta=readValue(pos, node>>1); | |
| node>>=1; | |
| int32_t delta; | |
| if(node<kMinTwoByteValueLead) { | |
| delta=node-kMinOneByteValueLead; | |
| } else if(node<kMinThreeByteValueLead) { | |
| delta=((node-kMinTwoByteValueLead)<<8)|*pos++; | |
| } else if(node<kFourByteValueLead) { | |
| delta=((node-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; | |
| pos+=2; | |
| } else if(node==kFourByteValueLead) { | |
| delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; | |
| pos+=3; | |
| } else { | |
| delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; | |
| pos+=4; | |
| } | |
| // end readValue() | |
| pos+=delta; | |
| node=*pos; | |
| result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; | |
| } | |
| pos_=pos; | |
| return result; | |
| } | |
| --length; | |
| pos=skipValue(pos); | |
| } while(length>1); | |
| if(inByte==*pos++) { | |
| pos_=pos; | |
| int32_t node=*pos; | |
| return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; | |
| } else { | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| } | |
| UStringTrieResult | |
| BytesTrie::nextImpl(const uint8_t *pos, int32_t inByte) { | |
| for(;;) { | |
| int32_t node=*pos++; | |
| if(node<kMinLinearMatch) { | |
| return branchNext(pos, node, inByte); | |
| } else if(node<kMinValueLead) { | |
| // Match the first of length+1 bytes. | |
| int32_t length=node-kMinLinearMatch; // Actual match length minus 1. | |
| if(inByte==*pos++) { | |
| remainingMatchLength_=--length; | |
| pos_=pos; | |
| return (length<0 && (node=*pos)>=kMinValueLead) ? | |
| valueResult(node) : USTRINGTRIE_NO_VALUE; | |
| } else { | |
| // No match. | |
| break; | |
| } | |
| } else if(node&kValueIsFinal) { | |
| // No further matching bytes. | |
| break; | |
| } else { | |
| // Skip intermediate value. | |
| pos=skipValue(pos, node); | |
| // The next node must not also be a value node. | |
| U_ASSERT(*pos<kMinValueLead); | |
| } | |
| } | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| UStringTrieResult | |
| BytesTrie::next(int32_t inByte) { | |
| const uint8_t *pos=pos_; | |
| if(pos==NULL) { | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| if(inByte<0) { | |
| inByte+=0x100; | |
| } | |
| int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. | |
| if(length>=0) { | |
| // Remaining part of a linear-match node. | |
| if(inByte==*pos++) { | |
| remainingMatchLength_=--length; | |
| pos_=pos; | |
| int32_t node; | |
| return (length<0 && (node=*pos)>=kMinValueLead) ? | |
| valueResult(node) : USTRINGTRIE_NO_VALUE; | |
| } else { | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| } | |
| return nextImpl(pos, inByte); | |
| } | |
| UStringTrieResult | |
| BytesTrie::next(const char *s, int32_t sLength) { | |
| if(sLength<0 ? *s==0 : sLength==0) { | |
| // Empty input. | |
| return current(); | |
| } | |
| const uint8_t *pos=pos_; | |
| if(pos==NULL) { | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. | |
| for(;;) { | |
| // Fetch the next input byte, if there is one. | |
| // Continue a linear-match node without rechecking sLength<0. | |
| int32_t inByte; | |
| if(sLength<0) { | |
| for(;;) { | |
| if((inByte=*s++)==0) { | |
| remainingMatchLength_=length; | |
| pos_=pos; | |
| int32_t node; | |
| return (length<0 && (node=*pos)>=kMinValueLead) ? | |
| valueResult(node) : USTRINGTRIE_NO_VALUE; | |
| } | |
| if(length<0) { | |
| remainingMatchLength_=length; | |
| break; | |
| } | |
| if(inByte!=*pos) { | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| ++pos; | |
| --length; | |
| } | |
| } else { | |
| for(;;) { | |
| if(sLength==0) { | |
| remainingMatchLength_=length; | |
| pos_=pos; | |
| int32_t node; | |
| return (length<0 && (node=*pos)>=kMinValueLead) ? | |
| valueResult(node) : USTRINGTRIE_NO_VALUE; | |
| } | |
| inByte=*s++; | |
| --sLength; | |
| if(length<0) { | |
| remainingMatchLength_=length; | |
| break; | |
| } | |
| if(inByte!=*pos) { | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| ++pos; | |
| --length; | |
| } | |
| } | |
| for(;;) { | |
| int32_t node=*pos++; | |
| if(node<kMinLinearMatch) { | |
| UStringTrieResult result=branchNext(pos, node, inByte); | |
| if(result==USTRINGTRIE_NO_MATCH) { | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| // Fetch the next input byte, if there is one. | |
| if(sLength<0) { | |
| if((inByte=*s++)==0) { | |
| return result; | |
| } | |
| } else { | |
| if(sLength==0) { | |
| return result; | |
| } | |
| inByte=*s++; | |
| --sLength; | |
| } | |
| if(result==USTRINGTRIE_FINAL_VALUE) { | |
| // No further matching bytes. | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| pos=pos_; // branchNext() advanced pos and wrote it to pos_ . | |
| } else if(node<kMinValueLead) { | |
| // Match length+1 bytes. | |
| length=node-kMinLinearMatch; // Actual match length minus 1. | |
| if(inByte!=*pos) { | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } | |
| ++pos; | |
| --length; | |
| break; | |
| } else if(node&kValueIsFinal) { | |
| // No further matching bytes. | |
| stop(); | |
| return USTRINGTRIE_NO_MATCH; | |
| } else { | |
| // Skip intermediate value. | |
| pos=skipValue(pos, node); | |
| // The next node must not also be a value node. | |
| U_ASSERT(*pos<kMinValueLead); | |
| } | |
| } | |
| } | |
| } | |
| const uint8_t * | |
| BytesTrie::findUniqueValueFromBranch(const uint8_t *pos, int32_t length, | |
| UBool haveUniqueValue, int32_t &uniqueValue) { | |
| while(length>kMaxBranchLinearSubNodeLength) { | |
| ++pos; // ignore the comparison byte | |
| if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) { | |
| return NULL; | |
| } | |
| length=length-(length>>1); | |
| pos=skipDelta(pos); | |
| } | |
| do { | |
| ++pos; // ignore a comparison byte | |
| // handle its value | |
| int32_t node=*pos++; | |
| UBool isFinal=(UBool)(node&kValueIsFinal); | |
| int32_t value=readValue(pos, node>>1); | |
| pos=skipValue(pos, node); | |
| if(isFinal) { | |
| if(haveUniqueValue) { | |
| if(value!=uniqueValue) { | |
| return NULL; | |
| } | |
| } else { | |
| uniqueValue=value; | |
| haveUniqueValue=TRUE; | |
| } | |
| } else { | |
| if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) { | |
| return NULL; | |
| } | |
| haveUniqueValue=TRUE; | |
| } | |
| } while(--length>1); | |
| return pos+1; // ignore the last comparison byte | |
| } | |
| UBool | |
| BytesTrie::findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue) { | |
| for(;;) { | |
| int32_t node=*pos++; | |
| if(node<kMinLinearMatch) { | |
| if(node==0) { | |
| node=*pos++; | |
| } | |
| pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue); | |
| if(pos==NULL) { | |
| return FALSE; | |
| } | |
| haveUniqueValue=TRUE; | |
| } else if(node<kMinValueLead) { | |
| // linear-match node | |
| pos+=node-kMinLinearMatch+1; // Ignore the match bytes. | |
| } else { | |
| UBool isFinal=(UBool)(node&kValueIsFinal); | |
| int32_t value=readValue(pos, node>>1); | |
| if(haveUniqueValue) { | |
| if(value!=uniqueValue) { | |
| return FALSE; | |
| } | |
| } else { | |
| uniqueValue=value; | |
| haveUniqueValue=TRUE; | |
| } | |
| if(isFinal) { | |
| return TRUE; | |
| } | |
| pos=skipValue(pos, node); | |
| } | |
| } | |
| } | |
| int32_t | |
| BytesTrie::getNextBytes(ByteSink &out) const { | |
| const uint8_t *pos=pos_; | |
| if(pos==NULL) { | |
| return 0; | |
| } | |
| if(remainingMatchLength_>=0) { | |
| append(out, *pos); // Next byte of a pending linear-match node. | |
| return 1; | |
| } | |
| int32_t node=*pos++; | |
| if(node>=kMinValueLead) { | |
| if(node&kValueIsFinal) { | |
| return 0; | |
| } else { | |
| pos=skipValue(pos, node); | |
| node=*pos++; | |
| U_ASSERT(node<kMinValueLead); | |
| } | |
| } | |
| if(node<kMinLinearMatch) { | |
| if(node==0) { | |
| node=*pos++; | |
| } | |
| getNextBranchBytes(pos, ++node, out); | |
| return node; | |
| } else { | |
| // First byte of the linear-match node. | |
| append(out, *pos); | |
| return 1; | |
| } | |
| } | |
| void | |
| BytesTrie::getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out) { | |
| while(length>kMaxBranchLinearSubNodeLength) { | |
| ++pos; // ignore the comparison byte | |
| getNextBranchBytes(jumpByDelta(pos), length>>1, out); | |
| length=length-(length>>1); | |
| pos=skipDelta(pos); | |
| } | |
| do { | |
| append(out, *pos++); | |
| pos=skipValue(pos); | |
| } while(--length>1); | |
| append(out, *pos); | |
| } | |
| void | |
| BytesTrie::append(ByteSink &out, int c) { | |
| char ch=(char)c; | |
| out.Append(&ch, 1); | |
| } | |
| U_NAMESPACE_END |