← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/third_party/icu/source/i18n/bocsu.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/third_party/icu/source/i18n/bocsu.h
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