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
26U_NAMESPACE_BEGIN
27
28class ByteSink;
29
30U_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
156U_CFUNC UChar32
157u_writeIdenticalLevelRun(UChar32 prev, const UChar *s, int32_t length, icu::ByteSink &sink);
158
159#endif /* #if !UCONFIG_NO_COLLATION */
160
161#endif
162