jars/icu4j-52_1/main/classes/core/src/com/ibm/icu/impl/BMPSet.java

   1 /*
   2  ******************************************************************************
   3  *
   4  *   Copyright (C) 2009-2011, International Business Machines
   5  *   Corporation and others.  All Rights Reserved.
   6  *
   7  ******************************************************************************
   8  */
   9
  10 package com.ibm.icu.impl;
  11
  12 import com.ibm.icu.text.UnicodeSet.SpanCondition;
  13
  14 /*
  15  * Helper class for frozen UnicodeSets, implements contains() and span() optimized for BMP code points.
  16  *
  17  * Latin-1: Look up bytes. 2-byte characters: Bits organized vertically. 3-byte characters: Use zero/one/mixed data
  18  * per 64-block in U+0000..U+FFFF, with mixed for illegal ranges. Supplementary characters: Call contains() on the
  19  * parent set.
  20  */
  21 public final class BMPSet {
  22     public static int U16_SURROGATE_OFFSET = ((0xd800 << 10) + 0xdc00 - 0x10000);
  23
  24     /*
  25      * One boolean ('true' or 'false') per Latin-1 character.
  26      */
  27     private boolean[] latin1Contains;
  28
  29     /*
  30      * One bit per code point from U+0000..U+07FF. The bits are organized vertically; consecutive code points
  31      * correspond to the same bit positions in consecutive table words. With code point parts lead=c{10..6}
  32      * trail=c{5..0} it is set.contains(c)==(table7FF[trail] bit lead)
  33      *
  34      * Bits for 0..7F (non-shortest forms) are set to the result of contains(FFFD) for faster validity checking at
  35      * runtime.
  36      */
  37     private int[] table7FF;
  38
  39     /*
  40      * One bit per 64 BMP code points. The bits are organized vertically; consecutive 64-code point blocks
  41      * correspond to the same bit position in consecutive table words. With code point parts lead=c{15..12}
  42      * t1=c{11..6} test bits (lead+16) and lead in bmpBlockBits[t1]. If the upper bit is 0, then the lower bit
  43      * indicates if contains(c) for all code points in the 64-block. If the upper bit is 1, then the block is mixed
  44      * and set.contains(c) must be called.
  45      *
  46      * Bits for 0..7FF (non-shortest forms) and D800..DFFF are set to the result of contains(FFFD) for faster
  47      * validity checking at runtime.
  48      */
  49     private int[] bmpBlockBits;
  50
  51     /*
  52      * Inversion list indexes for restricted binary searches in findCodePoint(), from findCodePoint(U+0800, U+1000,
  53      * U+2000, .., U+F000, U+10000). U+0800 is the first 3-byte-UTF-8 code point. Code points below U+0800 are
  54      * always looked up in the bit tables. The last pair of indexes is for finding supplementary code points.
  55      */
  56     private int[] list4kStarts;
  57
  58     /*
  59      * The inversion list of the parent set, for the slower contains() implementation for mixed BMP blocks and for
  60      * supplementary code points. The list is terminated with list[listLength-1]=0x110000.
  61      */
  62     private final int[] list;
  63     private final int listLength; // length used; list may be longer to minimize reallocs
  64
  65     public BMPSet(final int[] parentList, int parentListLength) {
  66         list = parentList;
  67         listLength = parentListLength;
  68         latin1Contains = new boolean[0x100];
  69         table7FF = new int[64];
  70         bmpBlockBits = new int[64];
  71         list4kStarts = new int[18];
  72
  73         /*
  74          * Set the list indexes for binary searches for U+0800, U+1000, U+2000, .., U+F000, U+10000. U+0800 is the
  75          * first 3-byte-UTF-8 code point. Lower code points are looked up in the bit tables. The last pair of
  76          * indexes is for finding supplementary code points.
  77          */
  78         list4kStarts[0] = findCodePoint(0x800, 0, listLength - 1);
  79         int i;
  80         for (i = 1; i <= 0x10; ++i) {
  81             list4kStarts[i] = findCodePoint(i << 12, list4kStarts[i - 1], listLength - 1);
  82         }
  83         list4kStarts[0x11] = listLength - 1;
  84
  85         initBits();
  86     }
  87
  88     public BMPSet(final BMPSet otherBMPSet, final int[] newParentList, int newParentListLength) {
  89         list = newParentList;
  90         listLength = newParentListLength;
  91         latin1Contains = otherBMPSet.latin1Contains.clone();
  92         table7FF = otherBMPSet.table7FF.clone();
  93         bmpBlockBits = otherBMPSet.bmpBlockBits.clone();
  94         list4kStarts = otherBMPSet.list4kStarts.clone();
  95     }
  96
  97     public boolean contains(int c) {
  98         if (c <= 0xff) {
  99             return (latin1Contains[c]);
 100         } else if (c <= 0x7ff) {
 101             return ((table7FF[c & 0x3f] & (1 << (c >> 6))) != 0);
 102         } else if (c < 0xd800 || (c >= 0xe000 && c <= 0xffff)) {
 103             int lead = c >> 12;
 104             int twoBits = (bmpBlockBits[(c >> 6) & 0x3f] >> lead) & 0x10001;
 105             if (twoBits <= 1) {
 106                 // All 64 code points with the same bits 15..6
 107                 // are either in the set or not.
 108                 return (0 != twoBits);
 109             } else {
 110                 // Look up the code point in its 4k block of code points.
 111                 return containsSlow(c, list4kStarts[lead], list4kStarts[lead + 1]);
 112             }
 113         } else if (c <= 0x10ffff) {
 114             // surrogate or supplementary code point
 115             return containsSlow(c, list4kStarts[0xd], list4kStarts[0x11]);
 116         } else {
 117             // Out-of-range code points get false, consistent with long-standing
 118             // behavior of UnicodeSet.contains(c).
 119             return false;
 120         }
 121     }
 122
 123     /*
 124      * Span the initial substring for which each character c has spanCondition==contains(c). It must be
 125      * spanCondition==0 or 1.
 126      *
 127      * @param start The start index
 128      * @param end   The end   index
 129      * @return The length of the span.
 130      *
 131      * NOTE: to reduce the overhead of function call to contains(c), it is manually inlined here. Check for
 132      * sufficient length for trail unit for each surrogate pair. Handle single surrogates as surrogate code points
 133      * as usual in ICU.
 134      */
 135     public final int span(CharSequence s, int start, int end, SpanCondition spanCondition) {
 136         char c, c2;
 137         int i = start;
 138         int limit = Math.min(s.length(), end);
 139         if (SpanCondition.NOT_CONTAINED != spanCondition) {
 140             // span
 141             while (i < limit) {
 142                 c = s.charAt(i);
 143                 if (c <= 0xff) {
 144                     if (!latin1Contains[c]) {
 145                         break;
 146                     }
 147                 } else if (c <= 0x7ff) {
 148                     if ((table7FF[c & 0x3f] & (1 << (c >> 6))) == 0) {
 149                         break;
 150                     }
 151                 } else if (c < 0xd800 ||
 152                            c >= 0xdc00 || (i + 1) == limit || (c2 = s.charAt(i + 1)) < 0xdc00 || c2 >= 0xe000) {
 153                     int lead = c >> 12;
 154                     int twoBits = (bmpBlockBits[(c >> 6) & 0x3f] >> lead) & 0x10001;
 155                     if (twoBits <= 1) {
 156                         // All 64 code points with the same bits 15..6
 157                         // are either in the set or not.
 158                         if (twoBits == 0) {
 159                             break;
 160                         }
 161                     } else {
 162                         // Look up the code point in its 4k block of code points.
 163                         if (!containsSlow(c, list4kStarts[lead], list4kStarts[lead + 1])) {
 164                             break;
 165                         }
 166                     }
 167                 } else {
 168                     // surrogate pair
 169                     int supplementary = UCharacterProperty.getRawSupplementary(c, c2);
 170                     if (!containsSlow(supplementary, list4kStarts[0x10], list4kStarts[0x11])) {
 171                         break;
 172                     }
 173                     ++i;
 174                 }
 175                 ++i;
 176             }
 177         } else {
 178             // span not
 179             while (i < limit) {
 180                 c = s.charAt(i);
 181                 if (c <= 0xff) {
 182                     if (latin1Contains[c]) {
 183                         break;
 184                     }
 185                 } else if (c <= 0x7ff) {
 186                     if ((table7FF[c & 0x3f] & (1 << (c >> 6))) != 0) {
 187                         break;
 188                     }
 189                 } else if (c < 0xd800 ||
 190                            c >= 0xdc00 || (i + 1) == limit || (c2 = s.charAt(i + 1)) < 0xdc00 || c2 >= 0xe000) {
 191                     int lead = c >> 12;
 192                     int twoBits = (bmpBlockBits[(c >> 6) & 0x3f] >> lead) & 0x10001;
 193                     if (twoBits <= 1) {
 194                         // All 64 code points with the same bits 15..6
 195                         // are either in the set or not.
 196                         if (twoBits != 0) {
 197                             break;
 198                         }
 199                     } else {
 200                         // Look up the code point in its 4k block of code points.
 201                         if (containsSlow(c, list4kStarts[lead], list4kStarts[lead + 1])) {
 202                             break;
 203                         }
 204                     }
 205                 } else {
 206                     // surrogate pair
 207                     int supplementary = UCharacterProperty.getRawSupplementary(c, c2);
 208                     if (containsSlow(supplementary, list4kStarts[0x10], list4kStarts[0x11])) {
 209                         break;
 210                     }
 211                     ++i;
 212                 }
 213                 ++i;
 214             }
 215         }
 216         return i - start;
 217     }
 218
 219     /*
 220      * Symmetrical with span().
 221      * Span the trailing substring for which each character c has spanCondition==contains(c). It must be s.length >=
 222      * limit and spanCondition==0 or 1.
 223      *
 224      * @return The string index which starts the span (i.e. inclusive).
 225      */
 226     public final int spanBack(CharSequence s, int limit, SpanCondition spanCondition) {
 227         char c, c2;
 228
 229         limit = Math.min(s.length(), limit);
 230         if (SpanCondition.NOT_CONTAINED != spanCondition) {
 231             // span
 232             for (;;) {
 233                 c = s.charAt(--limit);
 234                 if (c <= 0xff) {
 235                     if (!latin1Contains[c]) {
 236                         break;
 237                     }
 238                 } else if (c <= 0x7ff) {
 239                     if ((table7FF[c & 0x3f] & (1 << (c >> 6))) == 0) {
 240                         break;
 241                     }
 242                 } else if (c < 0xd800 ||
 243                            c < 0xdc00 || 0 == limit || (c2 = s.charAt(limit - 1)) < 0xd800 || c2 >= 0xdc00) {
 244                     int lead = c >> 12;
 245                     int twoBits = (bmpBlockBits[(c >> 6) & 0x3f] >> lead) & 0x10001;
 246                     if (twoBits <= 1) {
 247                         // All 64 code points with the same bits 15..6
 248                         // are either in the set or not.
 249                         if (twoBits == 0) {
 250                             break;
 251                         }
 252                     } else {
 253                         // Look up the code point in its 4k block of code points.
 254                         if (!containsSlow(c, list4kStarts[lead], list4kStarts[lead + 1])) {
 255                             break;
 256                         }
 257                     }
 258                 } else {
 259                     // surrogate pair
 260                     int supplementary = UCharacterProperty.getRawSupplementary(c2, c);
 261                     if (!containsSlow(supplementary, list4kStarts[0x10], list4kStarts[0x11])) {
 262                         break;
 263                     }
 264                     --limit;
 265                 }
 266                 if (0 == limit) {
 267                     return 0;
 268                 }
 269             }
 270         } else {
 271             // span not
 272             for (;;) {
 273                 c = s.charAt(--limit);
 274                 if (c <= 0xff) {
 275                     if (latin1Contains[c]) {
 276                         break;
 277                     }
 278                 } else if (c <= 0x7ff) {
 279                     if ((table7FF[c & 0x3f] & (1 << (c >> 6))) != 0) {
 280                         break;
 281                     }
 282                 } else if (c < 0xd800 ||
 283                            c < 0xdc00 || 0 == limit || (c2 = s.charAt(limit - 1)) < 0xd800 || c2 >= 0xdc00) {
 284                     int lead = c >> 12;
 285                     int twoBits = (bmpBlockBits[(c >> 6) & 0x3f] >> lead) & 0x10001;
 286                     if (twoBits <= 1) {
 287                         // All 64 code points with the same bits 15..6
 288                         // are either in the set or not.
 289                         if (twoBits != 0) {
 290                             break;
 291                         }
 292                     } else {
 293                         // Look up the code point in its 4k block of code points.
 294                         if (containsSlow(c, list4kStarts[lead], list4kStarts[lead + 1])) {
 295                             break;
 296                         }
 297                     }
 298                 } else {
 299                     // surrogate pair
 300                     int supplementary = UCharacterProperty.getRawSupplementary(c2, c);
 301                     if (containsSlow(supplementary, list4kStarts[0x10], list4kStarts[0x11])) {
 302                         break;
 303                     }
 304                     --limit;
 305                 }
 306                 if (0 == limit) {
 307                     return 0;
 308                 }
 309             }
 310         }
 311         return limit + 1;
 312     }
 313
 314     /*
 315      * Set bits in a bit rectangle in "vertical" bit organization. start<limit<=0x800
 316      */
 317     private static void set32x64Bits(int[] table, int start, int limit) {
 318         assert (64 == table.length);
 319         int lead = start >> 6;  // Named for UTF-8 2-byte lead byte with upper 5 bits.
 320         int trail = start & 0x3f;  // Named for UTF-8 2-byte trail byte with lower 6 bits.
 321
 322         // Set one bit indicating an all-one block.
 323         int bits = 1 << lead;
 324         if ((start + 1) == limit) { // Single-character shortcut.
 325             table[trail] |= bits;
 326             return;
 327         }
 328
 329         int limitLead = limit >> 6;
 330         int limitTrail = limit & 0x3f;
 331
 332         if (lead == limitLead) {
 333             // Partial vertical bit column.
 334             while (trail < limitTrail) {
 335                 table[trail++] |= bits;
 336             }
 337         } else {
 338             // Partial vertical bit column,
 339             // followed by a bit rectangle,
 340             // followed by another partial vertical bit column.
 341             if (trail > 0) {
 342                 do {
 343                     table[trail++] |= bits;
 344                 } while (trail < 64);
 345                 ++lead;
 346             }
 347             if (lead < limitLead) {
 348                 bits = ~((1 << lead) - 1);
 349                 if (limitLead < 0x20) {
 350                     bits &= (1 << limitLead) - 1;
 351                 }
 352                 for (trail = 0; trail < 64; ++trail) {
 353                     table[trail] |= bits;
 354                 }
 355             }
 356             // limit<=0x800. If limit==0x800 then limitLead=32 and limitTrail=0.
 357             // In that case, bits=1<<limitLead == 1<<0 == 1
 358             // (because Java << uses only the lower 5 bits of the shift operand)
 359             // but the bits value is not used because trail<limitTrail is already false.
 360             bits = 1 << limitLead;
 361             for (trail = 0; trail < limitTrail; ++trail) {
 362                 table[trail] |= bits;
 363             }
 364         }
 365     }
 366
 367     private void initBits() {
 368         int start, limit;
 369         int listIndex = 0;
 370
 371         // Set latin1Contains[].
 372         do {
 373             start = list[listIndex++];
 374             if (listIndex < listLength) {
 375                 limit = list[listIndex++];
 376             } else {
 377                 limit = 0x110000;
 378             }
 379             if (start >= 0x100) {
 380                 break;
 381             }
 382             do {
 383                 latin1Contains[start++] = true;
 384             } while (start < limit && start < 0x100);
 385         } while (limit <= 0x100);
 386
 387         // Set table7FF[].
 388         while (start < 0x800) {
 389             set32x64Bits(table7FF, start, limit <= 0x800 ? limit : 0x800);
 390             if (limit > 0x800) {
 391                 start = 0x800;
 392                 break;
 393             }
 394
 395             start = list[listIndex++];
 396             if (listIndex < listLength) {
 397                 limit = list[listIndex++];
 398             } else {
 399                 limit = 0x110000;
 400             }
 401         }
 402
 403         // Set bmpBlockBits[].
 404         int minStart = 0x800;
 405         while (start < 0x10000) {
 406             if (limit > 0x10000) {
 407                 limit = 0x10000;
 408             }
 409
 410             if (start < minStart) {
 411                 start = minStart;
 412             }
 413             if (start < limit) { // Else: Another range entirely in a known mixed-value block.
 414                 if (0 != (start & 0x3f)) {
 415                     // Mixed-value block of 64 code points.
 416                     start >>= 6;
 417                     bmpBlockBits[start & 0x3f] |= 0x10001 << (start >> 6);
 418                     start = (start + 1) << 6; // Round up to the next block boundary.
 419                     minStart = start; // Ignore further ranges in this block.
 420                 }
 421                 if (start < limit) {
 422                     if (start < (limit & ~0x3f)) {
 423                         // Multiple all-ones blocks of 64 code points each.
 424                         set32x64Bits(bmpBlockBits, start >> 6, limit >> 6);
 425                     }
 426
 427                     if (0 != (limit & 0x3f)) {
 428                         // Mixed-value block of 64 code points.
 429                         limit >>= 6;
 430                         bmpBlockBits[limit & 0x3f] |= 0x10001 << (limit >> 6);
 431                         limit = (limit + 1) << 6; // Round up to the next block boundary.
 432                         minStart = limit; // Ignore further ranges in this block.
 433                     }
 434                 }
 435             }
 436
 437             if (limit == 0x10000) {
 438                 break;
 439             }
 440
 441             start = list[listIndex++];
 442             if (listIndex < listLength) {
 443                 limit = list[listIndex++];
 444             } else {
 445                 limit = 0x110000;
 446             }
 447         }
 448     }
 449
 450
 451     /**
 452      * Same as UnicodeSet.findCodePoint(int c) except that the binary search is restricted for finding code
 453      * points in a certain range.
 454      *
 455      * For restricting the search for finding in the range start..end, pass in lo=findCodePoint(start) and
 456      * hi=findCodePoint(end) with 0<=lo<=hi<len. findCodePoint(c) defaults to lo=0 and hi=len-1.
 457      *
 458      * @param c
 459      *            a character in a subrange of MIN_VALUE..MAX_VALUE
 460      * @param lo
 461      *            The lowest index to be returned.
 462      * @param hi
 463      *            The highest index to be returned.
 464      * @return the smallest integer i in the range lo..hi, inclusive, such that c < list[i]
 465      */
 466     private int findCodePoint(int c, int lo, int hi) {
 467         /* Examples:
 468                                            findCodePoint(c)
 469            set              list[]         c=0 1 3 4 7 8
 470            ===              ==============   ===========
 471            []               [110000]         0 0 0 0 0 0
 472            [\u0000-\u0003]  [0, 4, 110000]   1 1 1 2 2 2
 473            [\u0004-\u0007]  [4, 8, 110000]   0 0 0 1 1 2
 474            [:Any:]          [0, 110000]      1 1 1 1 1 1
 475          */
 476
 477         // Return the smallest i such that c < list[i]. Assume
 478         // list[len - 1] == HIGH and that c is legal (0..HIGH-1).
 479         if (c < list[lo])
 480             return lo;
 481         // High runner test. c is often after the last range, so an
 482         // initial check for this condition pays off.
 483         if (lo >= hi || c >= list[hi - 1])
 484             return hi;
 485         // invariant: c >= list[lo]
 486         // invariant: c < list[hi]
 487         for (;;) {
 488             int i = (lo + hi) >>> 1;
 489             if (i == lo) {
 490                 break; // Found!
 491             } else if (c < list[i]) {
 492                 hi = i;
 493             } else {
 494                 lo = i;
 495             }
 496         }
 497         return hi;
 498     }
 499
 500     private final boolean containsSlow(int c, int lo, int hi) {
 501         return (0 != (findCodePoint(c, lo, hi) & 1));
 502     }
 503 }
 504