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