The Tor Browser: intl/icu/source/common/bytestrie.cpp@b8a032363ba2 (annotated)

intl/icu/source/common/bytestrie.cpp@b8a032363ba2 (annotated)

intl/icu/source/common/bytestrie.cpp

Thu, 22 Jan 2015 13:21:57 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Thu, 22 Jan 2015 13:21:57 +0100
branch: TOR_BUG_9701
changeset 15: b8a032363ba2
permissions: -rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

 /*
 *******************************************************************************
 *   Copyright (C) 2010-2011, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 *******************************************************************************
 *   file name:  bytestrie.cpp
 *   encoding:   US-ASCII
 *   tab size:   8 (not used)
 *   indentation:4
 *
 *   created on: 2010sep25
 *   created by: Markus W. Scherer
 */
 #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

The Tor Browser / annotate

intl/icu/source/common/bytestrie.cpp@b8a032363ba2 (annotated)

intl/icu/source/common/bytestrie.cpp