1 // Copyright (C) 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ******************************************************************************* 5 * Copyright (C) 2001-2014, International Business Machines 6 * Corporation and others. All Rights Reserved. 7 ******************************************************************************* 8 * file name: bocsu.cpp 9 * encoding: US-ASCII 10 * tab size: 8 (not used) 11 * indentation:4 12 * 13 * Author: Markus W. Scherer 14 * 15 * Modification history: 16 * 05/18/2001 weiv Made into separate module 17 */ 18 19 20 #include "unicode/utypes.h" 21 22 #if !UCONFIG_NO_COLLATION 23 24 #include "unicode/bytestream.h" 25 #include "unicode/utf16.h" 26 #include "bocsu.h" 27 28 /* 29 * encode one difference value -0x10ffff..+0x10ffff in 1..4 bytes, 30 * preserving lexical order 31 */ 32 static uint8_t * 33 u_writeDiff(int32_t diff, uint8_t *p) { 34 if(diff>=SLOPE_REACH_NEG_1) { 35 if(diff<=SLOPE_REACH_POS_1) { 36 *p++=(uint8_t)(SLOPE_MIDDLE+diff); 37 } else if(diff<=SLOPE_REACH_POS_2) { 38 *p++=(uint8_t)(SLOPE_START_POS_2+(diff/SLOPE_TAIL_COUNT)); 39 *p++=(uint8_t)(SLOPE_MIN+diff%SLOPE_TAIL_COUNT); 40 } else if(diff<=SLOPE_REACH_POS_3) { 41 p[2]=(uint8_t)(SLOPE_MIN+diff%SLOPE_TAIL_COUNT); 42 diff/=SLOPE_TAIL_COUNT; 43 p[1]=(uint8_t)(SLOPE_MIN+diff%SLOPE_TAIL_COUNT); 44 *p=(uint8_t)(SLOPE_START_POS_3+(diff/SLOPE_TAIL_COUNT)); 45 p+=3; 46 } else { 47 p[3]=(uint8_t)(SLOPE_MIN+diff%SLOPE_TAIL_COUNT); 48 diff/=SLOPE_TAIL_COUNT; 49 p[2]=(uint8_t)(SLOPE_MIN+diff%SLOPE_TAIL_COUNT); 50 diff/=SLOPE_TAIL_COUNT; 51 p[1]=(uint8_t)(SLOPE_MIN+diff%SLOPE_TAIL_COUNT); 52 *p=SLOPE_MAX; 53 p+=4; 54 } 55 } else { 56 int32_t m; 57 58 if(diff>=SLOPE_REACH_NEG_2) { 59 NEGDIVMOD(diff, SLOPE_TAIL_COUNT, m); 60 *p++=(uint8_t)(SLOPE_START_NEG_2+diff); 61 *p++=(uint8_t)(SLOPE_MIN+m); 62 } else if(diff>=SLOPE_REACH_NEG_3) { 63 NEGDIVMOD(diff, SLOPE_TAIL_COUNT, m); 64 p[2]=(uint8_t)(SLOPE_MIN+m); 65 NEGDIVMOD(diff, SLOPE_TAIL_COUNT, m); 66 p[1]=(uint8_t)(SLOPE_MIN+m); 67 *p=(uint8_t)(SLOPE_START_NEG_3+diff); 68 p+=3; 69 } else { 70 NEGDIVMOD(diff, SLOPE_TAIL_COUNT, m); 71 p[3]=(uint8_t)(SLOPE_MIN+m); 72 NEGDIVMOD(diff, SLOPE_TAIL_COUNT, m); 73 p[2]=(uint8_t)(SLOPE_MIN+m); 74 NEGDIVMOD(diff, SLOPE_TAIL_COUNT, m); 75 p[1]=(uint8_t)(SLOPE_MIN+m); 76 *p=SLOPE_MIN; 77 p+=4; 78 } 79 } 80 return p; 81 } 82 83 /* 84 * Encode the code points of a string as 85 * a sequence of byte-encoded differences (slope detection), 86 * preserving lexical order. 87 * 88 * Optimize the difference-taking for runs of Unicode text within 89 * small scripts: 90 * 91 * Most small scripts are allocated within aligned 128-blocks of Unicode 92 * code points. Lexical order is preserved if "prev" is always moved 93 * into the middle of such a block. 94 * 95 * Additionally, "prev" is moved from anywhere in the Unihan 96 * area into the middle of that area. 97 * Note that the identical-level run in a sort key is generated from 98 * NFD text - there are never Hangul characters included. 99 */ 100 U_CFUNC UChar32 101 u_writeIdenticalLevelRun(UChar32 prev, const UChar *s, int32_t length, icu::ByteSink &sink) { 102 char scratch[64]; 103 int32_t capacity; 104 105 int32_t i=0; 106 while(i<length) { 107 char *buffer=sink.GetAppendBuffer(1, length*2, scratch, (int32_t)sizeof(scratch), &capacity); 108 uint8_t *p; 109 // We must have capacity>=SLOPE_MAX_BYTES in case u_writeDiff() writes that much, 110 // but we do not want to force the sink.GetAppendBuffer() to allocate 111 // for a large min_capacity because we might actually only write one byte. 112 if(capacity<16) { 113 buffer=scratch; 114 capacity=(int32_t)sizeof(scratch); 115 } 116 p=reinterpret_cast<uint8_t *>(buffer); 117 uint8_t *lastSafe=p+capacity-SLOPE_MAX_BYTES; 118 while(i<length && p<=lastSafe) { 119 if(prev<0x4e00 || prev>=0xa000) { 120 prev=(prev&~0x7f)-SLOPE_REACH_NEG_1; 121 } else { 122 /* 123 * Unihan U+4e00..U+9fa5: 124 * double-bytes down from the upper end 125 */ 126 prev=0x9fff-SLOPE_REACH_POS_2; 127 } 128 129 UChar32 c; 130 U16_NEXT(s, i, length, c); 131 if(c==0xfffe) { 132 *p++=2; // merge separator 133 prev=0; 134 } else { 135 p=u_writeDiff(c-prev, p); 136 prev=c; 137 } 138 } 139 sink.Append(buffer, (int32_t)(p-reinterpret_cast<uint8_t *>(buffer))); 140 } 141 return prev; 142 } 143 144 #endif /* #if !UCONFIG_NO_COLLATION */ 145