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