1 /*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <stdio.h>
18 #include <stdlib.h>
19
20 #include "PhoneticStringUtils.h"
21 #include <utils/String8.h>
22
23 // We'd like 0 length string last of sorted list. So when input string is NULL
24 // or 0 length string, we use these instead.
25 #define CODEPOINT_FOR_NULL_STR 0xFFFD
26 #define STR_FOR_NULL_STR "\xEF\xBF\xBD"
27
28 // We assume that users will not notice strings not sorted properly when the
29 // first 128 characters are the same.
30 #define MAX_CODEPOINTS 128
31
32 namespace android {
33
34 // Get hiragana from halfwidth katakana.
GetHiraganaFromHalfwidthKatakana(char32_t codepoint,char32_t next_codepoint,bool * next_is_consumed)35 static int GetHiraganaFromHalfwidthKatakana(char32_t codepoint,
36 char32_t next_codepoint,
37 bool *next_is_consumed) {
38 if (codepoint < 0xFF66 || 0xFF9F < codepoint) {
39 return codepoint;
40 }
41
42 switch (codepoint) {
43 case 0xFF66: // wo
44 return 0x3092;
45 case 0xFF67: // xa
46 return 0x3041;
47 case 0xFF68: // xi
48 return 0x3043;
49 case 0xFF69: // xu
50 return 0x3045;
51 case 0xFF6A: // xe
52 return 0x3047;
53 case 0xFF6B: // xo
54 return 0x3049;
55 case 0xFF6C: // xya
56 return 0x3083;
57 case 0xFF6D: // xyu
58 return 0x3085;
59 case 0xFF6E: // xyo
60 return 0x3087;
61 case 0xFF6F: // xtsu
62 return 0x3063;
63 case 0xFF70: // -
64 return 0x30FC;
65 case 0xFF9C: // wa
66 return 0x308F;
67 case 0xFF9D: // n
68 return 0x3093;
69 break;
70 default: {
71 if (0xFF71 <= codepoint && codepoint <= 0xFF75) {
72 // a, i, u, e, o
73 if (codepoint == 0xFF73 && next_codepoint == 0xFF9E) {
74 if (next_is_consumed != NULL) {
75 *next_is_consumed = true;
76 }
77 return 0x3094; // vu
78 } else {
79 return 0x3042 + (codepoint - 0xFF71) * 2;
80 }
81 } else if (0xFF76 <= codepoint && codepoint <= 0xFF81) {
82 // ka - chi
83 if (next_codepoint == 0xFF9E) {
84 // "dakuten" (voiced mark)
85 if (next_is_consumed != NULL) {
86 *next_is_consumed = true;
87 }
88 return 0x304B + (codepoint - 0xFF76) * 2 + 1;
89 } else {
90 return 0x304B + (codepoint - 0xFF76) * 2;
91 }
92 } else if (0xFF82 <= codepoint && codepoint <= 0xFF84) {
93 // tsu, te, to (skip xtsu)
94 if (next_codepoint == 0xFF9E) {
95 // "dakuten" (voiced mark)
96 if (next_is_consumed != NULL) {
97 *next_is_consumed = true;
98 }
99 return 0x3064 + (codepoint - 0xFF82) * 2 + 1;
100 } else {
101 return 0x3064 + (codepoint - 0xFF82) * 2;
102 }
103 } else if (0xFF85 <= codepoint && codepoint <= 0xFF89) {
104 // na, ni, nu, ne, no
105 return 0x306A + (codepoint - 0xFF85);
106 } else if (0xFF8A <= codepoint && codepoint <= 0xFF8E) {
107 // ha, hi, hu, he, ho
108 if (next_codepoint == 0xFF9E) {
109 // "dakuten" (voiced mark)
110 if (next_is_consumed != NULL) {
111 *next_is_consumed = true;
112 }
113 return 0x306F + (codepoint - 0xFF8A) * 3 + 1;
114 } else if (next_codepoint == 0xFF9F) {
115 // "han-dakuten" (half voiced mark)
116 if (next_is_consumed != NULL) {
117 *next_is_consumed = true;
118 }
119 return 0x306F + (codepoint - 0xFF8A) * 3 + 2;
120 } else {
121 return 0x306F + (codepoint - 0xFF8A) * 3;
122 }
123 } else if (0xFF8F <= codepoint && codepoint <= 0xFF93) {
124 // ma, mi, mu, me, mo
125 return 0x307E + (codepoint - 0xFF8F);
126 } else if (0xFF94 <= codepoint && codepoint <= 0xFF96) {
127 // ya, yu, yo
128 return 0x3084 + (codepoint - 0xFF94) * 2;
129 } else if (0xFF97 <= codepoint && codepoint <= 0xFF9B) {
130 // ra, ri, ru, re, ro
131 return 0x3089 + (codepoint - 0xFF97);
132 }
133 // Note: 0xFF9C, 0xFF9D are handled above
134 } // end of default
135 }
136
137 return codepoint;
138 }
139
140 // Assuming input is hiragana, convert the hiragana to "normalized" hiragana.
GetNormalizedHiragana(int codepoint)141 static int GetNormalizedHiragana(int codepoint) {
142 if (codepoint < 0x3040 || 0x309F < codepoint) {
143 return codepoint;
144 }
145
146 // TODO: should care (semi-)voiced mark (0x3099, 0x309A).
147
148 // Trivial kana conversions.
149 // e.g. xa => a
150 switch (codepoint) {
151 case 0x3041:
152 case 0x3043:
153 case 0x3045:
154 case 0x3047:
155 case 0x3049:
156 case 0x308E: // xwa
157 return codepoint + 1;
158 case 0x3095: // xka
159 return 0x304B;
160 case 0x3096: // xku
161 return 0x304F;
162 default:
163 return codepoint;
164 }
165 }
166
GetNormalizedKana(char32_t codepoint,char32_t next_codepoint,bool * next_is_consumed)167 static int GetNormalizedKana(char32_t codepoint,
168 char32_t next_codepoint,
169 bool *next_is_consumed) {
170 // First, convert fullwidth katakana and halfwidth katakana to hiragana.
171 if (0x30A1 <= codepoint && codepoint <= 0x30F6) {
172 // Make fullwidth katakana same as hiragana.
173 // 96 == 0x30A1 - 0x3041c
174 codepoint = codepoint - 96;
175 } else {
176 codepoint = GetHiraganaFromHalfwidthKatakana(
177 codepoint, next_codepoint, next_is_consumed);
178 }
179
180 // Normalize Hiragana.
181 return GetNormalizedHiragana(codepoint);
182 }
183
GetPhoneticallySortableCodePoint(char32_t codepoint,char32_t next_codepoint,bool * next_is_consumed)184 int GetPhoneticallySortableCodePoint(char32_t codepoint,
185 char32_t next_codepoint,
186 bool *next_is_consumed) {
187 if (next_is_consumed != NULL) {
188 *next_is_consumed = false;
189 }
190
191 if (codepoint <= 0x0020 || codepoint == 0x3000) {
192 // Whitespace should be ignored.
193 // Note: Formally, more "whitespace" exist. This block only
194 // handles part of them
195 return -1;
196 } else if ((0x0021 <= codepoint && codepoint <= 0x007E) ||
197 (0xFF01 <= codepoint && codepoint <= 0xFF5E)) {
198 // Ascii and fullwidth ascii
199
200 if (0x0021 <= codepoint && codepoint <= 0x007E) {
201 // Convert ascii to fullwidth ascii so that they become
202 // behind hiragana.
203 // 65248 = 0xFF01 - 0x0021
204 codepoint += 65248;
205 }
206
207 // Now, there is only fullwidth ascii.
208 if (0xFF10 <= codepoint && codepoint <= 0xFF19) {
209 // Numbers should be after alphabets but before symbols.
210 // 86 = 0xFF66
211 // (the beginning of halfwidth-katakankana space) - 0xFF10
212 return codepoint + 86;
213 } else if (0xFF41 <= codepoint && codepoint <= 0xFF5A) {
214 // Make lower alphabets same as capital alphabets.
215 // 32 = 0xFF41 - 0xFF21
216 return codepoint - 32;
217 } else if (0xFF01 <= codepoint && codepoint <= 0xFF0F) {
218 // Symbols (Ascii except alphabet nor number)
219 // These should be at the end of sorting, just after numebers
220 // (see below)
221 //
222 // We use halfwidth-katakana space for storing those symbols.
223 // 111 = 0xFF70 (0xFF19 + 86 + 1) - 0xFF01
224 return codepoint + 111;
225 } else if (0xFF1A <= codepoint && codepoint <= 0xFF20) {
226 // Symbols (cont.)
227 // 101 = 0xFF7F (0xFF0F + 111 + 1) - 0xFF1A
228 return codepoint + 101;
229 } else if (0xFF3B <= codepoint && codepoint <= 0xFF40) {
230 // Symbols (cont.)
231 // 75 = 0xFF86 (0xFF20 + 101 + 1) - 0xFF3B (= 101 - 26)
232 return codepoint + 75;
233 } else if (0xFF5B <= codepoint && codepoint <= 0xFF5E) {
234 // Symbols (cont.)
235 // 49 = 0xFF8C (0xFF40 + 75 + 1) - 0xFF5B (= 75 - 26)
236 return codepoint + 49;
237 } else {
238 return codepoint;
239 }
240 } else if (codepoint == 0x02DC || codepoint == 0x223C) {
241 // tilde
242 return 0xFF5E;
243 } else if (codepoint <= 0x3040 ||
244 (0x3100 <= codepoint && codepoint < 0xFF00) ||
245 codepoint == CODEPOINT_FOR_NULL_STR) {
246 // Move Kanji and other non-Japanese characters behind symbols.
247 return codepoint + 0x10000;
248 }
249
250 // Below is Kana-related handling.
251
252 return GetNormalizedKana(codepoint, next_codepoint, next_is_consumed);
253 }
254
GetNormalizedCodePoint(char32_t codepoint,char32_t next_codepoint,bool * next_is_consumed)255 int GetNormalizedCodePoint(char32_t codepoint,
256 char32_t next_codepoint,
257 bool *next_is_consumed) {
258 if (next_is_consumed != NULL) {
259 *next_is_consumed = false;
260 }
261
262 if (codepoint <= 0x0020 || codepoint == 0x3000) {
263 // Whitespaces. Keep it as is.
264 return codepoint;
265 } else if ((0x0021 <= codepoint && codepoint <= 0x007E) ||
266 (0xFF01 <= codepoint && codepoint <= 0xFF5E)) {
267 // Ascii and fullwidth ascii. Keep it as is
268 return codepoint;
269 } else if (codepoint == 0x02DC || codepoint == 0x223C) {
270 // tilde
271 return 0xFF5E;
272 } else if (codepoint <= 0x3040 ||
273 (0x3100 <= codepoint && codepoint < 0xFF00) ||
274 codepoint == CODEPOINT_FOR_NULL_STR) {
275 // Keep it as is.
276 return codepoint;
277 }
278
279 // Below is Kana-related handling.
280
281 return GetNormalizedKana(codepoint, next_codepoint, next_is_consumed);
282 }
283
GetExpectedString(const char * src,char ** dst,size_t * dst_len,int (* get_codepoint_function)(char32_t,char32_t,bool *))284 static bool GetExpectedString(
285 const char *src, char **dst, size_t *dst_len,
286 int (*get_codepoint_function)(char32_t, char32_t, bool*)) {
287 if (dst == NULL || dst_len == NULL) {
288 return false;
289 }
290
291 if (src == NULL || *src == '\0') {
292 src = STR_FOR_NULL_STR;
293 }
294
295 char32_t codepoints[MAX_CODEPOINTS]; // if array size is changed the for loop needs to be changed
296
297 size_t src_len = utf8_length(src);
298 if (src_len == 0) {
299 return false;
300 }
301 bool next_is_consumed;
302 size_t j = 0;
303 for (size_t i = 0; i < src_len && j < MAX_CODEPOINTS;) {
304 int32_t ret = utf32_at(src, src_len, i, &i);
305 if (ret < 0) {
306 // failed to parse UTF-8
307 return false;
308 }
309 ret = get_codepoint_function(
310 static_cast<char32_t>(ret),
311 i + 1 < src_len ? src[i + 1] : 0,
312 &next_is_consumed);
313 if (ret > 0) {
314 codepoints[j] = static_cast<char32_t>(ret);
315 j++;
316 }
317 if (next_is_consumed) {
318 i++;
319 }
320 }
321 size_t length = j;
322
323 if (length == 0) {
324 // If all of codepoints are invalid, we place the string at the end of
325 // the list.
326 codepoints[0] = 0x10000 + CODEPOINT_FOR_NULL_STR;
327 length = 1;
328 }
329
330 size_t new_len = utf8_length_from_utf32(codepoints, length);
331 *dst = static_cast<char *>(malloc(new_len + 1));
332 if (*dst == NULL) {
333 return false;
334 }
335
336 if (utf32_to_utf8(codepoints, length, *dst, new_len + 1) != new_len) {
337 free(*dst);
338 *dst = NULL;
339 return false;
340 }
341
342 *dst_len = new_len;
343 return true;
344 }
345
GetPhoneticallySortableString(const char * src,char ** dst,size_t * len)346 bool GetPhoneticallySortableString(const char *src, char **dst, size_t *len) {
347 return GetExpectedString(src, dst, len, GetPhoneticallySortableCodePoint);
348 }
349
GetNormalizedString(const char * src,char ** dst,size_t * len)350 bool GetNormalizedString(const char *src, char **dst, size_t *len) {
351 return GetExpectedString(src, dst, len, GetNormalizedCodePoint);
352 }
353
354 } // namespace android
355