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

   1 /**
   2 *******************************************************************************
   3 * Copyright (C) 1996-2009, International Business Machines Corporation and    *
   4 * others. All Rights Reserved.                                                *
   5 *******************************************************************************
   6 */
   7 package com.ibm.icu.impl;
   8
   9 import com.ibm.icu.text.UCharacterIterator;
  10
  11 /**
  12  * <p>Binary Ordered Compression for Unicode</p>
  13  *
  14  * <p>Users are strongly encouraged to read the ICU paper on
  15  * <a href="http://www.icu-project.org/docs/papers/binary_ordered_compression_for_unicode.html">
  16  * BOCU</a> before attempting to use this class.</p>
  17  *
  18  * <p>BOCU is used to compress unicode text into a stream of unsigned
  19  * bytes.  For many kinds of text the compression compares favorably
  20  * to UTF-8, and for some kinds of text (such as CJK) it does better.
  21  * The resulting bytes will compare in the same order as the original
  22  * code points.  The byte stream does not contain the values 0, 1, or
  23  * 2.</p>
  24  *
  25  * <p>One example of a use of BOCU is in
  26  * com.ibm.icu.text.Collator#getCollationKey(String) for a RuleBasedCollator object with
  27  * collation strength IDENTICAL. The result CollationKey will consist of the
  28  * collation order of the source string followed by the BOCU result of the
  29  * source string.
  30  * </p>
  31  *
  32  * <p>Unlike a UTF encoding, BOCU-compressed text is not suitable for
  33  * random access.</p>
  34  *
  35  * <p>Method: Slope Detection<br> Remember the previous code point
  36  * (initial 0).  For each code point in the string, encode the
  37  * difference with the previous one.  Similar to a UTF, the length of
  38  * the byte sequence is encoded in the lead bytes.  Unlike a UTF, the
  39  * trail byte values may overlap with lead/single byte values.  The
  40  * signedness of the difference must be encoded as the most
  41  * significant part.</p>
  42  *
  43  * <p>We encode differences with few bytes if their absolute values
  44  * are small.  For correct ordering, we must treat the entire value
  45  * range -10ffff..+10ffff in ascending order, which forbids encoding
  46  * the sign and the absolute value separately. Instead, we split the
  47  * lead byte range in the middle and encode non-negative values going
  48  * up and negative values going down.</p>
  49  *
  50  * <p>For very small absolute values, the difference is added to a
  51  * middle byte value for single-byte encoded differences.  For
  52  * somewhat larger absolute values, the difference is divided by the
  53  * number of byte values available, the modulo is used for one trail
  54  * byte, and the remainder is added to a lead byte avoiding the
  55  * single-byte range.  For large absolute values, the difference is
  56  * similarly encoded in three bytes. (Syn Wee, I need examples
  57  * here.)</p>
  58  *
  59  * <p>BOCU does not use byte values 0, 1, or 2, but uses all other
  60  * byte values for lead and single bytes, so that the middle range of
  61  * single bytes is as large as possible.</p>
  62  *
  63  * <p>Note that the lead byte ranges overlap some, but that the
  64  * sequences as a whole are well ordered. I.e., even if the lead byte
  65  * is the same for sequences of different lengths, the trail bytes
  66  * establish correct order.  It would be possible to encode slightly
  67  * larger ranges for each length (>1) by subtracting the lower bound
  68  * of the range. However, that would also slow down the calculation.
  69  * (Syn Wee, need an example).</p>
  70  *
  71  * <p>For the actual string encoding, an optimization moves the
  72  * previous code point value to the middle of its Unicode script block
  73  * to minimize the differences in same-script text runs.  (Syn Wee,
  74  * need an example.)</p>
  75  *
  76  * @author Syn Wee Quek
  77  * @since release 2.2, May 3rd 2002
  78  */
  79 public class BOCU
  80 {
  81     // public constructors --------------------------------------------------
  82
  83     // public methods -------------------------------------------------------
  84
  85     /**
  86      * <p>Encode the code points of a string as a sequence of bytes,
  87      * preserving lexical order.</p>
  88      * <p>The minimum size of buffer required for the compression can be
  89      * preflighted by getCompressionLength(String).</p>
  90      * @param source text source
  91      * @param buffer output buffer
  92      * @param offset to start writing to
  93      * @return end offset where the writing stopped
  94      * @see #getCompressionLength(String)
  95      * @exception ArrayIndexOutOfBoundsException thrown if size of buffer is
  96      *            too small for the output.
  97      */
  98     public static int compress(String source, byte buffer[], int offset)
  99     {
 100         int prev = 0;
 101         UCharacterIterator iterator = UCharacterIterator.getInstance(source);
 102         int codepoint = iterator.nextCodePoint();
 103         while (codepoint != UCharacterIterator.DONE) {
 104             if (prev < 0x4e00 || prev >= 0xa000) {
 105                 prev = (prev & ~0x7f) - SLOPE_REACH_NEG_1_;
 106             }
 107             else {
 108                 // Unihan U+4e00..U+9fa5:
 109                 // double-bytes down from the upper end
 110                 prev = 0x9fff - SLOPE_REACH_POS_2_;
 111             }
 112
 113             offset = writeDiff(codepoint - prev, buffer, offset);
 114             prev = codepoint;
 115             codepoint = iterator.nextCodePoint();
 116         }
 117         return offset;
 118     }
 119
 120     /**
 121      * Return the number of  bytes that compress() would write.
 122      * @param source text source string
 123      * @return the length of the BOCU result
 124      * @see #compress(String, byte[], int)
 125      */
 126     public static int getCompressionLength(String source)
 127     {
 128         int prev = 0;
 129         int result = 0;
 130         UCharacterIterator iterator =  UCharacterIterator.getInstance(source);
 131         int codepoint = iterator.nextCodePoint();
 132         while (codepoint != UCharacterIterator.DONE) {
 133             if (prev < 0x4e00 || prev >= 0xa000) {
 134                 prev = (prev & ~0x7f) - SLOPE_REACH_NEG_1_;
 135             }
 136             else {
 137                 // Unihan U+4e00..U+9fa5:
 138                 // double-bytes down from the upper end
 139                 prev = 0x9fff - SLOPE_REACH_POS_2_;
 140             }
 141
 142             codepoint = iterator.nextCodePoint();
 143             result += lengthOfDiff(codepoint - prev);
 144             prev = codepoint;
 145         }
 146         return result;
 147     }
 148
 149     // public setter methods -------------------------------------------------
 150
 151     // public getter methods ------------------------------------------------
 152
 153     // public other methods -------------------------------------------------
 154
 155     // protected constructor ------------------------------------------------
 156
 157     // protected data members ------------------------------------------------
 158
 159     // protected methods -----------------------------------------------------
 160
 161     // private data members --------------------------------------------------
 162
 163     /**
 164      * Do not use byte values 0, 1, 2 because they are separators in sort keys.
 165      */
 166     private static final int SLOPE_MIN_ = 3;
 167     private static final int SLOPE_MAX_ = 0xff;
 168     private static final int SLOPE_MIDDLE_ = 0x81;
 169     private static final int SLOPE_TAIL_COUNT_ = SLOPE_MAX_ - SLOPE_MIN_ + 1;
 170     //private static final int SLOPE_MAX_BYTES_ = 4;
 171
 172     /**
 173      * Number of lead bytes:
 174      * 1        middle byte for 0
 175      * 2*80=160 single bytes for !=0
 176      * 2*42=84  for double-byte values
 177      * 2*3=6    for 3-byte values
 178      * 2*1=2    for 4-byte values
 179      *
 180      * The sum must be <=SLOPE_TAIL_COUNT.
 181      *
 182      * Why these numbers?
 183      * - There should be >=128 single-byte values to cover 128-blocks
 184      *   with small scripts.
 185      * - There should be >=20902 single/double-byte values to cover Unihan.
 186      * - It helps CJK Extension B some if there are 3-byte values that cover
 187      *   the distance between them and Unihan.
 188      *   This also helps to jump among distant places in the BMP.
 189      * - Four-byte values are necessary to cover the rest of Unicode.
 190      *
 191      * Symmetrical lead byte counts are for convenience.
 192      * With an equal distribution of even and odd differences there is also
 193      * no advantage to asymmetrical lead byte counts.
 194      */
 195     private static final int SLOPE_SINGLE_ = 80;
 196     private static final int SLOPE_LEAD_2_ = 42;
 197     private static final int SLOPE_LEAD_3_ = 3;
 198     //private static final int SLOPE_LEAD_4_ = 1;
 199
 200     /**
 201      * The difference value range for single-byters.
 202      */
 203     private static final int SLOPE_REACH_POS_1_ = SLOPE_SINGLE_;
 204     private static final int SLOPE_REACH_NEG_1_ = (-SLOPE_SINGLE_);
 205
 206     /**
 207      * The difference value range for double-byters.
 208      */
 209     private static final int SLOPE_REACH_POS_2_ =
 210         SLOPE_LEAD_2_ * SLOPE_TAIL_COUNT_ + SLOPE_LEAD_2_ - 1;
 211     private static final int SLOPE_REACH_NEG_2_ = (-SLOPE_REACH_POS_2_ - 1);
 212
 213     /**
 214      * The difference value range for 3-byters.
 215      */
 216     private static final int SLOPE_REACH_POS_3_ = SLOPE_LEAD_3_
 217         * SLOPE_TAIL_COUNT_
 218         * SLOPE_TAIL_COUNT_
 219         + (SLOPE_LEAD_3_ - 1)
 220         * SLOPE_TAIL_COUNT_ +
 221         (SLOPE_TAIL_COUNT_ - 1);
 222     private static final int SLOPE_REACH_NEG_3_ = (-SLOPE_REACH_POS_3_ - 1);
 223
 224     /**
 225      * The lead byte start values.
 226      */
 227     private static final int SLOPE_START_POS_2_ = SLOPE_MIDDLE_
 228         + SLOPE_SINGLE_ + 1;
 229     private static final int SLOPE_START_POS_3_ = SLOPE_START_POS_2_
 230         + SLOPE_LEAD_2_;
 231     private static final int SLOPE_START_NEG_2_ = SLOPE_MIDDLE_ +
 232         SLOPE_REACH_NEG_1_;
 233     private static final int SLOPE_START_NEG_3_ = SLOPE_START_NEG_2_
 234         - SLOPE_LEAD_2_;
 235
 236     // private constructor ---------------------------------------------------
 237
 238     /**
 239      * Constructor private to prevent initialization
 240      */
 241     ///CLOVER:OFF
 242     private BOCU()
 243     {
 244     }
 245     ///CLOVER:ON
 246
 247     // private methods -------------------------------------------------------
 248
 249     /**
 250      * Integer division and modulo with negative numerators
 251      * yields negative modulo results and quotients that are one more than
 252      * what we need here.
 253      * @param number which operations are to be performed on
 254      * @param factor the factor to use for division
 255      * @return (result of division) << 32 | modulo
 256      */
 257     private static final long getNegDivMod(int number, int factor)
 258     {
 259         int modulo = number % factor;
 260         long result = number / factor;
 261         if (modulo < 0) {
 262             -- result;
 263             modulo += factor;
 264         }
 265         return (result << 32) | modulo;
 266     }
 267
 268     /**
 269      * Encode one difference value -0x10ffff..+0x10ffff in 1..3 bytes,
 270      * preserving lexical order
 271      * @param diff
 272      * @param buffer byte buffer to append to
 273      * @param offset to the byte buffer to start appending
 274      * @return end offset where the appending stops
 275      */
 276     private static final int writeDiff(int diff, byte buffer[], int offset)
 277     {
 278         if (diff >= SLOPE_REACH_NEG_1_) {
 279             if (diff <= SLOPE_REACH_POS_1_) {
 280                 buffer[offset ++] = (byte)(SLOPE_MIDDLE_ + diff);
 281             }
 282             else if (diff <= SLOPE_REACH_POS_2_) {
 283                 buffer[offset ++] = (byte)(SLOPE_START_POS_2_
 284                                            + (diff / SLOPE_TAIL_COUNT_));
 285                 buffer[offset ++] = (byte)(SLOPE_MIN_ +
 286                                            (diff % SLOPE_TAIL_COUNT_));
 287             }
 288             else if (diff <= SLOPE_REACH_POS_3_) {
 289                 buffer[offset + 2] = (byte)(SLOPE_MIN_
 290                                             + (diff % SLOPE_TAIL_COUNT_));
 291                 diff /= SLOPE_TAIL_COUNT_;
 292                 buffer[offset + 1] = (byte)(SLOPE_MIN_
 293                                             + (diff % SLOPE_TAIL_COUNT_));
 294                 buffer[offset] = (byte)(SLOPE_START_POS_3_
 295                                         + (diff / SLOPE_TAIL_COUNT_));
 296                 offset += 3;
 297             }
 298             else {
 299                 buffer[offset + 3] = (byte)(SLOPE_MIN_
 300                                             + diff % SLOPE_TAIL_COUNT_);
 301                 diff /= SLOPE_TAIL_COUNT_;
 302                 buffer[offset] = (byte)(SLOPE_MIN_
 303                                         + diff % SLOPE_TAIL_COUNT_);
 304                 diff /= SLOPE_TAIL_COUNT_;
 305                 buffer[offset + 1] = (byte)(SLOPE_MIN_
 306                                             + diff % SLOPE_TAIL_COUNT_);
 307                 buffer[offset] = (byte)SLOPE_MAX_;
 308                 offset += 4;
 309             }
 310         }
 311         else {
 312             long division = getNegDivMod(diff, SLOPE_TAIL_COUNT_);
 313             int modulo = (int)division;
 314             if (diff >= SLOPE_REACH_NEG_2_) {
 315                 diff = (int)(division >> 32);
 316                 buffer[offset ++] = (byte)(SLOPE_START_NEG_2_ + diff);
 317                 buffer[offset ++] = (byte)(SLOPE_MIN_ + modulo);
 318             }
 319             else if (diff >= SLOPE_REACH_NEG_3_) {
 320                 buffer[offset + 2] = (byte)(SLOPE_MIN_ + modulo);
 321                 diff = (int)(division >> 32);
 322                 division = getNegDivMod(diff, SLOPE_TAIL_COUNT_);
 323                 modulo = (int)division;
 324                 diff = (int)(division >> 32);
 325                 buffer[offset + 1] = (byte)(SLOPE_MIN_ + modulo);
 326                 buffer[offset] = (byte)(SLOPE_START_NEG_3_ + diff);
 327                 offset += 3;
 328             }
 329             else {
 330                 buffer[offset + 3] = (byte)(SLOPE_MIN_ + modulo);
 331                 diff = (int)(division >> 32);
 332                 division = getNegDivMod(diff, SLOPE_TAIL_COUNT_);
 333                 modulo = (int)division;
 334                 diff = (int)(division >> 32);
 335                 buffer[offset + 2] = (byte)(SLOPE_MIN_ + modulo);
 336                 division = getNegDivMod(diff, SLOPE_TAIL_COUNT_);
 337                 modulo = (int)division;
 338                 buffer[offset + 1] = (byte)(SLOPE_MIN_ + modulo);
 339                 buffer[offset] = SLOPE_MIN_;
 340                 offset += 4;
 341             }
 342         }
 343         return offset;
 344     }
 345
 346     /**
 347      * How many bytes would writeDiff() write?
 348      * @param diff
 349      */
 350     private static final int lengthOfDiff(int diff)
 351     {
 352         if (diff >= SLOPE_REACH_NEG_1_) {
 353             if (diff <= SLOPE_REACH_POS_1_) {
 354                 return 1;
 355             }
 356             else if (diff <= SLOPE_REACH_POS_2_) {
 357                 return 2;
 358             }
 359             else if(diff <= SLOPE_REACH_POS_3_) {
 360                 return 3;
 361             }
 362             else {
 363                 return 4;
 364             }
 365         }
 366         else {
 367             if (diff >= SLOPE_REACH_NEG_2_) {
 368                 return 2;
 369             }
 370             else if (diff >= SLOPE_REACH_NEG_3_) {
 371                 return 3;
 372             }
 373             else {
 374                 return 4;
 375             }
 376         }
 377     }
 378 }