The Tor Browser / file revision

 /*

 *******************************************************************************

 *   Copyright (C) 2001-2011, 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

 U_NAMESPACE_BEGIN

 class ByteSink;

 U_NAMESPACE_END

 /*

  * "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 void

 u_writeIdenticalLevelRun(const UChar *s, int32_t length, icu::ByteSink &sink);

 U_CFUNC int32_t

 u_writeIdenticalLevelRunTwoChars(UChar32 first, UChar32 second, uint8_t *p);

 U_CFUNC uint8_t *

 u_writeDiff(int32_t diff, uint8_t *p);

 #endif /* #if !UCONFIG_NO_COLLATION */

 #endif