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