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) { \
148     (m)=(n)%(d); \
149     (n)/=(d); \
150     if((m)<0) { \
151         --(n); \
152         (m)+=(d); \
153     } \
154 }
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
162