/* | |

******************************************************************************* | |

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