icuSources/i18n/bocsu.h

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