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 163