Home | History | Annotate | Download | only in i18n
      1 /*
      2 *******************************************************************************
      3 *   Copyright (C) 2001-2014, International Business Machines
      4 *   Corporation and others.  All Rights Reserved.
      5 *******************************************************************************
      6 *   file name:  bocsu.h
      7 *   encoding:   US-ASCII
      8 *   tab size:   8 (not used)
      9 *   indentation:4
     10 *
     11 *   Author: Markus W. Scherer
     12 *
     13 *   Modification history:
     14 *   05/18/2001  weiv    Made into separate module
     15 */
     16 
     17 #ifndef BOCSU_H
     18 #define BOCSU_H
     19 
     20 #include "unicode/utypes.h"
     21 
     22 #if !UCONFIG_NO_COLLATION
     23 
     24 U_NAMESPACE_BEGIN
     25 
     26 class ByteSink;
     27 
     28 U_NAMESPACE_END
     29 
     30 /*
     31  * "BOCSU"
     32  * Binary Ordered Compression Scheme for Unicode
     33  *
     34  * Specific application:
     35  *
     36  * Encode a Unicode string for the identical level of a sort key.
     37  * Restrictions:
     38  * - byte stream (unsigned 8-bit bytes)
     39  * - lexical order of the identical-level run must be
     40  *   the same as code point order for the string
     41  * - avoid byte values 0, 1, 2
     42  *
     43  * Method: Slope Detection
     44  * Remember the previous code point (initial 0).
     45  * For each cp in the string, encode the difference to the previous one.
     46  *
     47  * With a compact encoding of differences, this yields good results for
     48  * small scripts and UTF-like results otherwise.
     49  *
     50  * Encoding of differences:
     51  * - Similar to a UTF, encoding the length of the byte sequence in the lead bytes.
     52  * - Does not need to be friendly for decoding or random access
     53  *   (trail byte values may overlap with lead/single byte values).
     54  * - The signedness must be encoded as the most significant part.
     55  *
     56  * We encode differences with few bytes if their absolute values are small.
     57  * For correct ordering, we must treat the entire value range -10ffff..+10ffff
     58  * in ascending order, which forbids encoding the sign and the absolute value separately.
     59  * Instead, we split the lead byte range in the middle and encode non-negative values
     60  * going up and negative values going down.
     61  *
     62  * For very small absolute values, the difference is added to a middle byte value
     63  * for single-byte encoded differences.
     64  * For somewhat larger absolute values, the difference is divided by the number
     65  * of byte values available, the modulo is used for one trail byte, and the remainder
     66  * is added to a lead byte avoiding the single-byte range.
     67  * For large absolute values, the difference is similarly encoded in three bytes.
     68  *
     69  * This encoding does not use byte values 0, 1, 2, but uses all other byte values
     70  * for lead/single bytes so that the middle range of single bytes is as large
     71  * as possible.
     72  * Note that the lead byte ranges overlap some, but that the sequences as a whole
     73  * are well ordered. I.e., even if the lead byte is the same for sequences of different
     74  * lengths, the trail bytes establish correct order.
     75  * It would be possible to encode slightly larger ranges for each length (>1) by
     76  * subtracting the lower bound of the range. However, that would also slow down the
     77  * calculation.
     78  *
     79  * For the actual string encoding, an optimization moves the previous code point value
     80  * to the middle of its Unicode script block to minimize the differences in
     81  * same-script text runs.
     82  */
     83 
     84 /* Do not use byte values 0, 1, 2 because they are separators in sort keys. */
     85 #define SLOPE_MIN           3
     86 #define SLOPE_MAX           0xff
     87 #define SLOPE_MIDDLE        0x81
     88 
     89 #define SLOPE_TAIL_COUNT    (SLOPE_MAX-SLOPE_MIN+1)
     90 
     91 #define SLOPE_MAX_BYTES     4
     92 
     93 /*
     94  * Number of lead bytes:
     95  * 1        middle byte for 0
     96  * 2*80=160 single bytes for !=0
     97  * 2*42=84  for double-byte values
     98  * 2*3=6    for 3-byte values
     99  * 2*1=2    for 4-byte values
    100  *
    101  * The sum must be <=SLOPE_TAIL_COUNT.
    102  *
    103  * Why these numbers?
    104  * - There should be >=128 single-byte values to cover 128-blocks
    105  *   with small scripts.
    106  * - There should be >=20902 single/double-byte values to cover Unihan.
    107  * - It helps CJK Extension B some if there are 3-byte values that cover
    108  *   the distance between them and Unihan.
    109  *   This also helps to jump among distant places in the BMP.
    110  * - Four-byte values are necessary to cover the rest of Unicode.
    111  *
    112  * Symmetrical lead byte counts are for convenience.
    113  * With an equal distribution of even and odd differences there is also
    114  * no advantage to asymmetrical lead byte counts.
    115  */
    116 #define SLOPE_SINGLE        80
    117 #define SLOPE_LEAD_2        42
    118 #define SLOPE_LEAD_3        3
    119 #define SLOPE_LEAD_4        1
    120 
    121 /* The difference value range for single-byters. */
    122 #define SLOPE_REACH_POS_1   SLOPE_SINGLE
    123 #define SLOPE_REACH_NEG_1   (-SLOPE_SINGLE)
    124 
    125 /* The difference value range for double-byters. */
    126 #define SLOPE_REACH_POS_2   (SLOPE_LEAD_2*SLOPE_TAIL_COUNT+(SLOPE_LEAD_2-1))
    127 #define SLOPE_REACH_NEG_2   (-SLOPE_REACH_POS_2-1)
    128 
    129 /* The difference value range for 3-byters. */
    130 #define SLOPE_REACH_POS_3   (SLOPE_LEAD_3*SLOPE_TAIL_COUNT*SLOPE_TAIL_COUNT+(SLOPE_LEAD_3-1)*SLOPE_TAIL_COUNT+(SLOPE_TAIL_COUNT-1))
    131 #define SLOPE_REACH_NEG_3   (-SLOPE_REACH_POS_3-1)
    132 
    133 /* The lead byte start values. */
    134 #define SLOPE_START_POS_2   (SLOPE_MIDDLE+SLOPE_SINGLE+1)
    135 #define SLOPE_START_POS_3   (SLOPE_START_POS_2+SLOPE_LEAD_2)
    136 
    137 #define SLOPE_START_NEG_2   (SLOPE_MIDDLE+SLOPE_REACH_NEG_1)
    138 #define SLOPE_START_NEG_3   (SLOPE_START_NEG_2-SLOPE_LEAD_2)
    139 
    140 /*
    141  * Integer division and modulo with negative numerators
    142  * yields negative modulo results and quotients that are one more than
    143  * what we need here.
    144  */
    145 #define NEGDIVMOD(n, d, m) { \
    146     (m)=(n)%(d); \
    147     (n)/=(d); \
    148     if((m)<0) { \
    149         --(n); \
    150         (m)+=(d); \
    151     } \
    152 }
    153 
    154 U_CFUNC UChar32
    155 u_writeIdenticalLevelRun(UChar32 prev, const UChar *s, int32_t length, icu::ByteSink &sink);
    156 
    157 #endif /* #if !UCONFIG_NO_COLLATION */
    158 
    159 #endif
    160