Index: icu46/source/i18n/bocsu.h |
=================================================================== |
--- icu46/source/i18n/bocsu.h (revision 0) |
+++ icu46/source/i18n/bocsu.h (revision 0) |
@@ -0,0 +1,162 @@ |
+/* |
+******************************************************************************* |
+* Copyright (C) 2001-2003, International Business Machines |
+* Corporation and others. All Rights Reserved. |
+******************************************************************************* |
+* file name: bocsu.c |
+* encoding: US-ASCII |
+* tab size: 8 (not used) |
+* indentation:4 |
+* |
+* Author: Markus W. Scherer |
+* |
+* Modification history: |
+* 05/18/2001 weiv Made into separate module |
+*/ |
+ |
+#ifndef BOCSU_H |
+#define BOCSU_H |
+ |
+#include "unicode/utypes.h" |
+ |
+#if !UCONFIG_NO_COLLATION |
+ |
+/* |
+ * "BOCSU" |
+ * Binary Ordered Compression Scheme for Unicode |
+ * |
+ * Specific application: |
+ * |
+ * Encode a Unicode string for the identical level of a sort key. |
+ * Restrictions: |
+ * - byte stream (unsigned 8-bit bytes) |
+ * - lexical order of the identical-level run must be |
+ * the same as code point order for the string |
+ * - avoid byte values 0, 1, 2 |
+ * |
+ * Method: Slope Detection |
+ * Remember the previous code point (initial 0). |
+ * For each cp in the string, encode the difference to the previous one. |
+ * |
+ * With a compact encoding of differences, this yields good results for |
+ * small scripts and UTF-like results otherwise. |
+ * |
+ * Encoding of differences: |
+ * - Similar to a UTF, encoding the length of the byte sequence in the lead bytes. |
+ * - Does not need to be friendly for decoding or random access |
+ * (trail byte values may overlap with lead/single byte values). |
+ * - The signedness must be encoded as the most significant part. |
+ * |
+ * We encode differences with few bytes if their absolute values are small. |
+ * For correct ordering, we must treat the entire value range -10ffff..+10ffff |
+ * in ascending order, which forbids encoding the sign and the absolute value separately. |
+ * Instead, we split the lead byte range in the middle and encode non-negative values |
+ * going up and negative values going down. |
+ * |
+ * For very small absolute values, the difference is added to a middle byte value |
+ * for single-byte encoded differences. |
+ * For somewhat larger absolute values, the difference is divided by the number |
+ * of byte values available, the modulo is used for one trail byte, and the remainder |
+ * is added to a lead byte avoiding the single-byte range. |
+ * For large absolute values, the difference is similarly encoded in three bytes. |
+ * |
+ * This encoding does not use byte values 0, 1, 2, but uses all other byte values |
+ * for lead/single bytes so that the middle range of single bytes is as large |
+ * as possible. |
+ * Note that the lead byte ranges overlap some, but that the sequences as a whole |
+ * are well ordered. I.e., even if the lead byte is the same for sequences of different |
+ * lengths, the trail bytes establish correct order. |
+ * It would be possible to encode slightly larger ranges for each length (>1) by |
+ * subtracting the lower bound of the range. However, that would also slow down the |
+ * calculation. |
+ * |
+ * For the actual string encoding, an optimization moves the previous code point value |
+ * to the middle of its Unicode script block to minimize the differences in |
+ * same-script text runs. |
+ */ |
+ |
+/* Do not use byte values 0, 1, 2 because they are separators in sort keys. */ |
+#define SLOPE_MIN 3 |
+#define SLOPE_MAX 0xff |
+#define SLOPE_MIDDLE 0x81 |
+ |
+#define SLOPE_TAIL_COUNT (SLOPE_MAX-SLOPE_MIN+1) |
+ |
+#define SLOPE_MAX_BYTES 4 |
+ |
+/* |
+ * Number of lead bytes: |
+ * 1 middle byte for 0 |
+ * 2*80=160 single bytes for !=0 |
+ * 2*42=84 for double-byte values |
+ * 2*3=6 for 3-byte values |
+ * 2*1=2 for 4-byte values |
+ * |
+ * The sum must be <=SLOPE_TAIL_COUNT. |
+ * |
+ * Why these numbers? |
+ * - There should be >=128 single-byte values to cover 128-blocks |
+ * with small scripts. |
+ * - There should be >=20902 single/double-byte values to cover Unihan. |
+ * - It helps CJK Extension B some if there are 3-byte values that cover |
+ * the distance between them and Unihan. |
+ * This also helps to jump among distant places in the BMP. |
+ * - Four-byte values are necessary to cover the rest of Unicode. |
+ * |
+ * Symmetrical lead byte counts are for convenience. |
+ * With an equal distribution of even and odd differences there is also |
+ * no advantage to asymmetrical lead byte counts. |
+ */ |
+#define SLOPE_SINGLE 80 |
+#define SLOPE_LEAD_2 42 |
+#define SLOPE_LEAD_3 3 |
+#define SLOPE_LEAD_4 1 |
+ |
+/* The difference value range for single-byters. */ |
+#define SLOPE_REACH_POS_1 SLOPE_SINGLE |
+#define SLOPE_REACH_NEG_1 (-SLOPE_SINGLE) |
+ |
+/* The difference value range for double-byters. */ |
+#define SLOPE_REACH_POS_2 (SLOPE_LEAD_2*SLOPE_TAIL_COUNT+(SLOPE_LEAD_2-1)) |
+#define SLOPE_REACH_NEG_2 (-SLOPE_REACH_POS_2-1) |
+ |
+/* The difference value range for 3-byters. */ |
+#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)) |
+#define SLOPE_REACH_NEG_3 (-SLOPE_REACH_POS_3-1) |
+ |
+/* The lead byte start values. */ |
+#define SLOPE_START_POS_2 (SLOPE_MIDDLE+SLOPE_SINGLE+1) |
+#define SLOPE_START_POS_3 (SLOPE_START_POS_2+SLOPE_LEAD_2) |
+ |
+#define SLOPE_START_NEG_2 (SLOPE_MIDDLE+SLOPE_REACH_NEG_1) |
+#define SLOPE_START_NEG_3 (SLOPE_START_NEG_2-SLOPE_LEAD_2) |
+ |
+/* |
+ * Integer division and modulo with negative numerators |
+ * yields negative modulo results and quotients that are one more than |
+ * what we need here. |
+ */ |
+#define NEGDIVMOD(n, d, m) { \ |
+ (m)=(n)%(d); \ |
+ (n)/=(d); \ |
+ if((m)<0) { \ |
+ --(n); \ |
+ (m)+=(d); \ |
+ } \ |
+} |
+ |
+U_CFUNC int32_t |
+u_writeIdenticalLevelRun(const UChar *s, int32_t length, uint8_t *p); |
+ |
+U_CFUNC int32_t |
+u_writeIdenticalLevelRunTwoChars(UChar32 first, UChar32 second, uint8_t *p); |
+ |
+U_CFUNC int32_t |
+u_lengthOfIdenticalLevelRun(const UChar *s, int32_t length); |
+ |
+U_CFUNC uint8_t * |
+u_writeDiff(int32_t diff, uint8_t *p); |
+ |
+#endif /* #if !UCONFIG_NO_COLLATION */ |
+ |
+#endif |
Property changes on: icu46/source/i18n/bocsu.h |
___________________________________________________________________ |
Added: svn:eol-style |
+ LF |