icuSources/common/bytestrie.cpp

   1 /*
   2 *******************************************************************************
   3 *   Copyright (C) 2010-2011, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 *   file name:  bytestrie.cpp
   7 *   encoding:   US-ASCII
   8 *   tab size:   8 (not used)
   9 *   indentation:4
  10 *
  11 *   created on: 2010sep25
  12 *   created by: Markus W. Scherer
  13 */
  14
  15 #include "unicode/utypes.h"
  16 #include "unicode/bytestream.h"
  17 #include "unicode/bytestrie.h"
  18 #include "unicode/uobject.h"
  19 #include "cmemory.h"
  20 #include "uassert.h"
  21
  22 U_NAMESPACE_BEGIN
  23
  24 BytesTrie::~BytesTrie() {
  25     uprv_free(ownedArray_);
  26 }
  27
  28 // lead byte already shifted right by 1.
  29 int32_t
  30 BytesTrie::readValue(const uint8_t *pos, int32_t leadByte) {
  31     int32_t value;
  32     if(leadByte<kMinTwoByteValueLead) {
  33         value=leadByte-kMinOneByteValueLead;
  34     } else if(leadByte<kMinThreeByteValueLead) {
  35         value=((leadByte-kMinTwoByteValueLead)<<8)|*pos;
  36     } else if(leadByte<kFourByteValueLead) {
  37         value=((leadByte-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1];
  38     } else if(leadByte==kFourByteValueLead) {
  39         value=(pos[0]<<16)|(pos[1]<<8)|pos[2];
  40     } else {
  41         value=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3];
  42     }
  43     return value;
  44 }
  45
  46 const uint8_t *
  47 BytesTrie::jumpByDelta(const uint8_t *pos) {
  48     int32_t delta=*pos++;
  49     if(delta<kMinTwoByteDeltaLead) {
  50         // nothing to do
  51     } else if(delta<kMinThreeByteDeltaLead) {
  52         delta=((delta-kMinTwoByteDeltaLead)<<8)|*pos++;
  53     } else if(delta<kFourByteDeltaLead) {
  54         delta=((delta-kMinThreeByteDeltaLead)<<16)|(pos[0]<<8)|pos[1];
  55         pos+=2;
  56     } else if(delta==kFourByteDeltaLead) {
  57         delta=(pos[0]<<16)|(pos[1]<<8)|pos[2];
  58         pos+=3;
  59     } else {
  60         delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3];
  61         pos+=4;
  62     }
  63     return pos+delta;
  64 }
  65
  66 UStringTrieResult
  67 BytesTrie::current() const {
  68     const uint8_t *pos=pos_;
  69     if(pos==NULL) {
  70         return USTRINGTRIE_NO_MATCH;
  71     } else {
  72         int32_t node;
  73         return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ?
  74                 valueResult(node) : USTRINGTRIE_NO_VALUE;
  75     }
  76 }
  77
  78 UStringTrieResult
  79 BytesTrie::branchNext(const uint8_t *pos, int32_t length, int32_t inByte) {
  80     // Branch according to the current byte.
  81     if(length==0) {
  82         length=*pos++;
  83     }
  84     ++length;
  85     // The length of the branch is the number of bytes to select from.
  86     // The data structure encodes a binary search.
  87     while(length>kMaxBranchLinearSubNodeLength) {
  88         if(inByte<*pos++) {
  89             length>>=1;
  90             pos=jumpByDelta(pos);
  91         } else {
  92             length=length-(length>>1);
  93             pos=skipDelta(pos);
  94         }
  95     }
  96     // Drop down to linear search for the last few bytes.
  97     // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3
  98     // and divides length by 2.
  99     do {
 100         if(inByte==*pos++) {
 101             UStringTrieResult result;
 102             int32_t node=*pos;
 103             U_ASSERT(node>=kMinValueLead);
 104             if(node&kValueIsFinal) {
 105                 // Leave the final value for getValue() to read.
 106                 result=USTRINGTRIE_FINAL_VALUE;
 107             } else {
 108                 // Use the non-final value as the jump delta.
 109                 ++pos;
 110                 // int32_t delta=readValue(pos, node>>1);
 111                 node>>=1;
 112                 int32_t delta;
 113                 if(node<kMinTwoByteValueLead) {
 114                     delta=node-kMinOneByteValueLead;
 115                 } else if(node<kMinThreeByteValueLead) {
 116                     delta=((node-kMinTwoByteValueLead)<<8)|*pos++;
 117                 } else if(node<kFourByteValueLead) {
 118                     delta=((node-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1];
 119                     pos+=2;
 120                 } else if(node==kFourByteValueLead) {
 121                     delta=(pos[0]<<16)|(pos[1]<<8)|pos[2];
 122                     pos+=3;
 123                 } else {
 124                     delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3];
 125                     pos+=4;
 126                 }
 127                 // end readValue()
 128                 pos+=delta;
 129                 node=*pos;
 130                 result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE;
 131             }
 132             pos_=pos;
 133             return result;
 134         }
 135         --length;
 136         pos=skipValue(pos);
 137     } while(length>1);
 138     if(inByte==*pos++) {
 139         pos_=pos;
 140         int32_t node=*pos;
 141         return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE;
 142     } else {
 143         stop();
 144         return USTRINGTRIE_NO_MATCH;
 145     }
 146 }
 147
 148 UStringTrieResult
 149 BytesTrie::nextImpl(const uint8_t *pos, int32_t inByte) {
 150     for(;;) {
 151         int32_t node=*pos++;
 152         if(node<kMinLinearMatch) {
 153             return branchNext(pos, node, inByte);
 154         } else if(node<kMinValueLead) {
 155             // Match the first of length+1 bytes.
 156             int32_t length=node-kMinLinearMatch;  // Actual match length minus 1.
 157             if(inByte==*pos++) {
 158                 remainingMatchLength_=--length;
 159                 pos_=pos;
 160                 return (length<0 && (node=*pos)>=kMinValueLead) ?
 161                         valueResult(node) : USTRINGTRIE_NO_VALUE;
 162             } else {
 163                 // No match.
 164                 break;
 165             }
 166         } else if(node&kValueIsFinal) {
 167             // No further matching bytes.
 168             break;
 169         } else {
 170             // Skip intermediate value.
 171             pos=skipValue(pos, node);
 172             // The next node must not also be a value node.
 173             U_ASSERT(*pos<kMinValueLead);
 174         }
 175     }
 176     stop();
 177     return USTRINGTRIE_NO_MATCH;
 178 }
 179
 180 UStringTrieResult
 181 BytesTrie::next(int32_t inByte) {
 182     const uint8_t *pos=pos_;
 183     if(pos==NULL) {
 184         return USTRINGTRIE_NO_MATCH;
 185     }
 186     if(inByte<0) {
 187         inByte+=0x100;
 188     }
 189     int32_t length=remainingMatchLength_;  // Actual remaining match length minus 1.
 190     if(length>=0) {
 191         // Remaining part of a linear-match node.
 192         if(inByte==*pos++) {
 193             remainingMatchLength_=--length;
 194             pos_=pos;
 195             int32_t node;
 196             return (length<0 && (node=*pos)>=kMinValueLead) ?
 197                     valueResult(node) : USTRINGTRIE_NO_VALUE;
 198         } else {
 199             stop();
 200             return USTRINGTRIE_NO_MATCH;
 201         }
 202     }
 203     return nextImpl(pos, inByte);
 204 }
 205
 206 UStringTrieResult
 207 BytesTrie::next(const char *s, int32_t sLength) {
 208     if(sLength<0 ? *s==0 : sLength==0) {
 209         // Empty input.
 210         return current();
 211     }
 212     const uint8_t *pos=pos_;
 213     if(pos==NULL) {
 214         return USTRINGTRIE_NO_MATCH;
 215     }
 216     int32_t length=remainingMatchLength_;  // Actual remaining match length minus 1.
 217     for(;;) {
 218         // Fetch the next input byte, if there is one.
 219         // Continue a linear-match node without rechecking sLength<0.
 220         int32_t inByte;
 221         if(sLength<0) {
 222             for(;;) {
 223                 if((inByte=*s++)==0) {
 224                     remainingMatchLength_=length;
 225                     pos_=pos;
 226                     int32_t node;
 227                     return (length<0 && (node=*pos)>=kMinValueLead) ?
 228                             valueResult(node) : USTRINGTRIE_NO_VALUE;
 229                 }
 230                 if(length<0) {
 231                     remainingMatchLength_=length;
 232                     break;
 233                 }
 234                 if(inByte!=*pos) {
 235                     stop();
 236                     return USTRINGTRIE_NO_MATCH;
 237                 }
 238                 ++pos;
 239                 --length;
 240             }
 241         } else {
 242             for(;;) {
 243                 if(sLength==0) {
 244                     remainingMatchLength_=length;
 245                     pos_=pos;
 246                     int32_t node;
 247                     return (length<0 && (node=*pos)>=kMinValueLead) ?
 248                             valueResult(node) : USTRINGTRIE_NO_VALUE;
 249                 }
 250                 inByte=*s++;
 251                 --sLength;
 252                 if(length<0) {
 253                     remainingMatchLength_=length;
 254                     break;
 255                 }
 256                 if(inByte!=*pos) {
 257                     stop();
 258                     return USTRINGTRIE_NO_MATCH;
 259                 }
 260                 ++pos;
 261                 --length;
 262             }
 263         }
 264         for(;;) {
 265             int32_t node=*pos++;
 266             if(node<kMinLinearMatch) {
 267                 UStringTrieResult result=branchNext(pos, node, inByte);
 268                 if(result==USTRINGTRIE_NO_MATCH) {
 269                     return USTRINGTRIE_NO_MATCH;
 270                 }
 271                 // Fetch the next input byte, if there is one.
 272                 if(sLength<0) {
 273                     if((inByte=*s++)==0) {
 274                         return result;
 275                     }
 276                 } else {
 277                     if(sLength==0) {
 278                         return result;
 279                     }
 280                     inByte=*s++;
 281                     --sLength;
 282                 }
 283                 if(result==USTRINGTRIE_FINAL_VALUE) {
 284                     // No further matching bytes.
 285                     stop();
 286                     return USTRINGTRIE_NO_MATCH;
 287                 }
 288                 pos=pos_;  // branchNext() advanced pos and wrote it to pos_ .
 289             } else if(node<kMinValueLead) {
 290                 // Match length+1 bytes.
 291                 length=node-kMinLinearMatch;  // Actual match length minus 1.
 292                 if(inByte!=*pos) {
 293                     stop();
 294                     return USTRINGTRIE_NO_MATCH;
 295                 }
 296                 ++pos;
 297                 --length;
 298                 break;
 299             } else if(node&kValueIsFinal) {
 300                 // No further matching bytes.
 301                 stop();
 302                 return USTRINGTRIE_NO_MATCH;
 303             } else {
 304                 // Skip intermediate value.
 305                 pos=skipValue(pos, node);
 306                 // The next node must not also be a value node.
 307                 U_ASSERT(*pos<kMinValueLead);
 308             }
 309         }
 310     }
 311 }
 312
 313 const uint8_t *
 314 BytesTrie::findUniqueValueFromBranch(const uint8_t *pos, int32_t length,
 315                                      UBool haveUniqueValue, int32_t &uniqueValue) {
 316     while(length>kMaxBranchLinearSubNodeLength) {
 317         ++pos;  // ignore the comparison byte
 318         if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) {
 319             return NULL;
 320         }
 321         length=length-(length>>1);
 322         pos=skipDelta(pos);
 323     }
 324     do {
 325         ++pos;  // ignore a comparison byte
 326         // handle its value
 327         int32_t node=*pos++;
 328         UBool isFinal=(UBool)(node&kValueIsFinal);
 329         int32_t value=readValue(pos, node>>1);
 330         pos=skipValue(pos, node);
 331         if(isFinal) {
 332             if(haveUniqueValue) {
 333                 if(value!=uniqueValue) {
 334                     return NULL;
 335                 }
 336             } else {
 337                 uniqueValue=value;
 338                 haveUniqueValue=TRUE;
 339             }
 340         } else {
 341             if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) {
 342                 return NULL;
 343             }
 344             haveUniqueValue=TRUE;
 345         }
 346     } while(--length>1);
 347     return pos+1;  // ignore the last comparison byte
 348 }
 349
 350 UBool
 351 BytesTrie::findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue) {
 352     for(;;) {
 353         int32_t node=*pos++;
 354         if(node<kMinLinearMatch) {
 355             if(node==0) {
 356                 node=*pos++;
 357             }
 358             pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue);
 359             if(pos==NULL) {
 360                 return FALSE;
 361             }
 362             haveUniqueValue=TRUE;
 363         } else if(node<kMinValueLead) {
 364             // linear-match node
 365             pos+=node-kMinLinearMatch+1;  // Ignore the match bytes.
 366         } else {
 367             UBool isFinal=(UBool)(node&kValueIsFinal);
 368             int32_t value=readValue(pos, node>>1);
 369             if(haveUniqueValue) {
 370                 if(value!=uniqueValue) {
 371                     return FALSE;
 372                 }
 373             } else {
 374                 uniqueValue=value;
 375                 haveUniqueValue=TRUE;
 376             }
 377             if(isFinal) {
 378                 return TRUE;
 379             }
 380             pos=skipValue(pos, node);
 381         }
 382     }
 383 }
 384
 385 int32_t
 386 BytesTrie::getNextBytes(ByteSink &out) const {
 387     const uint8_t *pos=pos_;
 388     if(pos==NULL) {
 389         return 0;
 390     }
 391     if(remainingMatchLength_>=0) {
 392         append(out, *pos);  // Next byte of a pending linear-match node.
 393         return 1;
 394     }
 395     int32_t node=*pos++;
 396     if(node>=kMinValueLead) {
 397         if(node&kValueIsFinal) {
 398             return 0;
 399         } else {
 400             pos=skipValue(pos, node);
 401             node=*pos++;
 402             U_ASSERT(node<kMinValueLead);
 403         }
 404     }
 405     if(node<kMinLinearMatch) {
 406         if(node==0) {
 407             node=*pos++;
 408         }
 409         getNextBranchBytes(pos, ++node, out);
 410         return node;
 411     } else {
 412         // First byte of the linear-match node.
 413         append(out, *pos);
 414         return 1;
 415     }
 416 }
 417
 418 void
 419 BytesTrie::getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out) {
 420     while(length>kMaxBranchLinearSubNodeLength) {
 421         ++pos;  // ignore the comparison byte
 422         getNextBranchBytes(jumpByDelta(pos), length>>1, out);
 423         length=length-(length>>1);
 424         pos=skipDelta(pos);
 425     }
 426     do {
 427         append(out, *pos++);
 428         pos=skipValue(pos);
 429     } while(--length>1);
 430     append(out, *pos);
 431 }
 432
 433 void
 434 BytesTrie::append(ByteSink &out, int c) {
 435     char ch=(char)c;
 436     out.Append(&ch, 1);
 437 }
 438
 439 U_NAMESPACE_END