]> git.saurik.com Git - apple/icu.git/blob - icuSources/common/punycode.c
ICU-6.2.22.tar.gz
[apple/icu.git] / icuSources / common / punycode.c
1 /*
2 *******************************************************************************
3 *
4 * Copyright (C) 2002-2003, International Business Machines
5 * Corporation and others. All Rights Reserved.
6 *
7 *******************************************************************************
8 * file name: punycode.c
9 * encoding: US-ASCII
10 * tab size: 8 (not used)
11 * indentation:4
12 *
13 * created on: 2002jan31
14 * created by: Markus W. Scherer
15 */
16
17
18 /* This ICU code derived from: */
19 /*
20 punycode.c 0.4.0 (2001-Nov-17-Sat)
21 http://www.cs.berkeley.edu/~amc/idn/
22 Adam M. Costello
23 http://www.nicemice.net/amc/
24
25 Disclaimer and license
26
27 Regarding this entire document or any portion of it (including
28 the pseudocode and C code), the author makes no guarantees and
29 is not responsible for any damage resulting from its use. The
30 author grants irrevocable permission to anyone to use, modify,
31 and distribute it in any way that does not diminish the rights
32 of anyone else to use, modify, and distribute it, provided that
33 redistributed derivative works do not contain misleading author or
34 version information. Derivative works need not be licensed under
35 similar terms.
36 */
37 /*
38 * ICU modifications:
39 * - ICU data types and coding conventions
40 * - ICU string buffer handling with implicit source lengths
41 * and destination preflighting
42 * - UTF-16 handling
43 */
44
45 #include "unicode/utypes.h"
46
47 #if !UCONFIG_NO_IDNA
48
49 #include "ustr_imp.h"
50 #include "cstring.h"
51 #include "cmemory.h"
52 #include "punycode.h"
53 #include "unicode/ustring.h"
54
55
56 /* Punycode ----------------------------------------------------------------- */
57
58 /* Punycode parameters for Bootstring */
59 #define BASE 36
60 #define TMIN 1
61 #define TMAX 26
62 #define SKEW 38
63 #define DAMP 700
64 #define INITIAL_BIAS 72
65 #define INITIAL_N 0x80
66
67 /* "Basic" Unicode/ASCII code points */
68 #define _HYPHEN 0X2d
69 #define DELIMITER _HYPHEN
70
71 #define _ZERO_ 0X30
72 #define _NINE 0x39
73
74 #define _SMALL_A 0X61
75 #define _SMALL_Z 0X7a
76
77 #define _CAPITAL_A 0X41
78 #define _CAPITAL_Z 0X5a
79
80 #define IS_BASIC(c) ((c)<0x80)
81 #define IS_BASIC_UPPERCASE(c) (_CAPITAL_A<=(c) && (c)<=_CAPITAL_Z)
82
83 /**
84 * digitToBasic() returns the basic code point whose value
85 * (when used for representing integers) is d, which must be in the
86 * range 0 to BASE-1. The lowercase form is used unless the uppercase flag is
87 * nonzero, in which case the uppercase form is used.
88 */
89 static U_INLINE char
90 digitToBasic(int32_t digit, UBool uppercase) {
91 /* 0..25 map to ASCII a..z or A..Z */
92 /* 26..35 map to ASCII 0..9 */
93 if(digit<26) {
94 if(uppercase) {
95 return (char)(_CAPITAL_A+digit);
96 } else {
97 return (char)(_SMALL_A+digit);
98 }
99 } else {
100 return (char)((_ZERO_-26)+digit);
101 }
102 }
103
104 /**
105 * basicToDigit[] contains the numeric value of a basic code
106 * point (for use in representing integers) in the range 0 to
107 * BASE-1, or -1 if b is does not represent a value.
108 */
109 static const int8_t
110 basicToDigit[256]={
111 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
112 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
113
114 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
115 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1, -1,
116
117 -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
118 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
119
120 -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
121 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
122
123 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
124 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
125
126 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
127 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
128
129 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
130 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
131
132 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
133 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
134 };
135
136 static U_INLINE char
137 asciiCaseMap(char b, UBool uppercase) {
138 if(uppercase) {
139 if(_SMALL_A<=b && b<=_SMALL_Z) {
140 b-=(_SMALL_A-_CAPITAL_A);
141 }
142 } else {
143 if(_CAPITAL_A<=b && b<=_CAPITAL_Z) {
144 b+=(_SMALL_A-_CAPITAL_A);
145 }
146 }
147 return b;
148 }
149
150 /* Punycode-specific Bootstring code ---------------------------------------- */
151
152 /*
153 * The following code omits the {parts} of the pseudo-algorithm in the spec
154 * that are not used with the Punycode parameter set.
155 */
156
157 /* Bias adaptation function. */
158 static int32_t
159 adaptBias(int32_t delta, int32_t length, UBool firstTime) {
160 int32_t count;
161
162 if(firstTime) {
163 delta/=DAMP;
164 } else {
165 delta/=2;
166 }
167
168 delta+=delta/length;
169 for(count=0; delta>((BASE-TMIN)*TMAX)/2; count+=BASE) {
170 delta/=(BASE-TMIN);
171 }
172
173 return count+(((BASE-TMIN+1)*delta)/(delta+SKEW));
174 }
175
176 #define MAX_CP_COUNT 200
177
178 U_CFUNC int32_t
179 u_strToPunycode(const UChar *src, int32_t srcLength,
180 UChar *dest, int32_t destCapacity,
181 const UBool *caseFlags,
182 UErrorCode *pErrorCode) {
183
184 int32_t cpBuffer[MAX_CP_COUNT];
185 int32_t n, delta, handledCPCount, basicLength, destLength, bias, j, m, q, k, t, srcCPCount;
186 UChar c, c2;
187
188 /* argument checking */
189 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
190 return 0;
191 }
192
193 if(src==NULL || srcLength<-1 || (dest==NULL && destCapacity!=0)) {
194 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
195 return 0;
196 }
197
198 /*
199 * Handle the basic code points and
200 * convert extended ones to UTF-32 in cpBuffer (caseFlag in sign bit):
201 */
202 srcCPCount=destLength=0;
203 if(srcLength==-1) {
204 /* NUL-terminated input */
205 for(j=0; /* no condition */; ++j) {
206 if((c=src[j])==0) {
207 break;
208 }
209 if(srcCPCount==MAX_CP_COUNT) {
210 /* too many input code points */
211 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
212 return 0;
213 }
214 if(IS_BASIC(c)) {
215 cpBuffer[srcCPCount++]=0;
216 if(destLength<destCapacity) {
217 dest[destLength]=
218 caseFlags!=NULL ?
219 asciiCaseMap((char)c, caseFlags[j]) :
220 (char)c;
221 }
222 ++destLength;
223 } else {
224 n=(caseFlags!=NULL && caseFlags[j])<<31L;
225 if(UTF_IS_SINGLE(c)) {
226 n|=c;
227 } else if(UTF_IS_LEAD(c) && UTF_IS_TRAIL(c2=src[j+1])) {
228 ++j;
229 n|=(int32_t)UTF16_GET_PAIR_VALUE(c, c2);
230 } else {
231 /* error: unmatched surrogate */
232 *pErrorCode=U_INVALID_CHAR_FOUND;
233 return 0;
234 }
235 cpBuffer[srcCPCount++]=n;
236 }
237 }
238 } else {
239 /* length-specified input */
240 for(j=0; j<srcLength; ++j) {
241 if(srcCPCount==MAX_CP_COUNT) {
242 /* too many input code points */
243 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
244 return 0;
245 }
246 c=src[j];
247 if(IS_BASIC(c)) {
248 if(destLength<destCapacity) {
249 cpBuffer[srcCPCount++]=0;
250 dest[destLength]=
251 caseFlags!=NULL ?
252 asciiCaseMap((char)c, caseFlags[j]) :
253 (char)c;
254 }
255 ++destLength;
256 } else {
257 n=(caseFlags!=NULL && caseFlags[j])<<31L;
258 if(UTF_IS_SINGLE(c)) {
259 n|=c;
260 } else if(UTF_IS_LEAD(c) && (j+1)<srcLength && UTF_IS_TRAIL(c2=src[j+1])) {
261 ++j;
262 n|=(int32_t)UTF16_GET_PAIR_VALUE(c, c2);
263 } else {
264 /* error: unmatched surrogate */
265 *pErrorCode=U_INVALID_CHAR_FOUND;
266 return 0;
267 }
268 cpBuffer[srcCPCount++]=n;
269 }
270 }
271 }
272
273 /* Finish the basic string - if it is not empty - with a delimiter. */
274 basicLength=destLength;
275 if(basicLength>0) {
276 if(destLength<destCapacity) {
277 dest[destLength]=DELIMITER;
278 }
279 ++destLength;
280 }
281
282 /*
283 * handledCPCount is the number of code points that have been handled
284 * basicLength is the number of basic code points
285 * destLength is the number of chars that have been output
286 */
287
288 /* Initialize the state: */
289 n=INITIAL_N;
290 delta=0;
291 bias=INITIAL_BIAS;
292
293 /* Main encoding loop: */
294 for(handledCPCount=basicLength; handledCPCount<srcCPCount; /* no op */) {
295 /*
296 * All non-basic code points < n have been handled already.
297 * Find the next larger one:
298 */
299 for(m=0x7fffffff, j=0; j<srcCPCount; ++j) {
300 q=cpBuffer[j]&0x7fffffff; /* remove case flag from the sign bit */
301 if(n<=q && q<m) {
302 m=q;
303 }
304 }
305
306 /*
307 * Increase delta enough to advance the decoder's
308 * <n,i> state to <m,0>, but guard against overflow:
309 */
310 if(m-n>(0x7fffffff-MAX_CP_COUNT-delta)/(handledCPCount+1)) {
311 *pErrorCode=U_INTERNAL_PROGRAM_ERROR;
312 return 0;
313 }
314 delta+=(m-n)*(handledCPCount+1);
315 n=m;
316
317 /* Encode a sequence of same code points n */
318 for(j=0; j<srcCPCount; ++j) {
319 q=cpBuffer[j]&0x7fffffff; /* remove case flag from the sign bit */
320 if(q<n) {
321 ++delta;
322 } else if(q==n) {
323 /* Represent delta as a generalized variable-length integer: */
324 for(q=delta, k=BASE; /* no condition */; k+=BASE) {
325
326 /** RAM: comment out the old code for conformance with draft-ietf-idn-punycode-03.txt
327
328 t=k-bias;
329 if(t<TMIN) {
330 t=TMIN;
331 } else if(t>TMAX) {
332 t=TMAX;
333 }
334 */
335
336 t=k-bias;
337 if(t<TMIN) {
338 t=TMIN;
339 } else if(k>=(bias+TMAX)) {
340 t=TMAX;
341 }
342
343 if(q<t) {
344 break;
345 }
346
347 if(destLength<destCapacity) {
348 dest[destLength++]=digitToBasic(t+(q-t)%(BASE-t), 0);
349 }
350 q=(q-t)/(BASE-t);
351 }
352
353 if(destLength<destCapacity) {
354 dest[destLength++]=digitToBasic(q, (UBool)(cpBuffer[j]<0));
355 }
356 bias=adaptBias(delta, handledCPCount+1, (UBool)(handledCPCount==basicLength));
357 delta=0;
358 ++handledCPCount;
359 }
360 }
361
362 ++delta;
363 ++n;
364 }
365
366 return u_terminateUChars(dest, destCapacity, destLength, pErrorCode);
367 }
368
369 U_CFUNC int32_t
370 u_strFromPunycode(const UChar *src, int32_t srcLength,
371 UChar *dest, int32_t destCapacity,
372 UBool *caseFlags,
373 UErrorCode *pErrorCode) {
374 int32_t n, destLength, i, bias, basicLength, j, in, oldi, w, k, digit, t,
375 destCPCount, firstSupplementaryIndex, cpLength;
376 UChar b;
377
378 /* argument checking */
379 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
380 return 0;
381 }
382
383 if(src==NULL || srcLength<-1 || (dest==NULL && destCapacity!=0)) {
384 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
385 return 0;
386 }
387
388 if(srcLength==-1) {
389 srcLength=u_strlen(src);
390 }
391
392 /*
393 * Handle the basic code points:
394 * Let basicLength be the number of input code points
395 * before the last delimiter, or 0 if there is none,
396 * then copy the first basicLength code points to the output.
397 *
398 * The two following loops iterate backward.
399 */
400 for(j=srcLength; j>0;) {
401 if(src[--j]==DELIMITER) {
402 break;
403 }
404 }
405 destLength=basicLength=destCPCount=j;
406
407 while(j>0) {
408 b=src[--j];
409 if(!IS_BASIC(b)) {
410 *pErrorCode=U_INVALID_CHAR_FOUND;
411 return 0;
412 }
413
414 if(j<destCapacity) {
415 dest[j]=(UChar)b;
416
417 if(caseFlags!=NULL) {
418 caseFlags[j]=IS_BASIC_UPPERCASE(b);
419 }
420 }
421 }
422
423 /* Initialize the state: */
424 n=INITIAL_N;
425 i=0;
426 bias=INITIAL_BIAS;
427 firstSupplementaryIndex=1000000000;
428
429 /*
430 * Main decoding loop:
431 * Start just after the last delimiter if any
432 * basic code points were copied; start at the beginning otherwise.
433 */
434 for(in=basicLength>0 ? basicLength+1 : 0; in<srcLength; /* no op */) {
435 /*
436 * in is the index of the next character to be consumed, and
437 * destCPCount is the number of code points in the output array.
438 *
439 * Decode a generalized variable-length integer into delta,
440 * which gets added to i. The overflow checking is easier
441 * if we increase i as we go, then subtract off its starting
442 * value at the end to obtain delta.
443 */
444 for(oldi=i, w=1, k=BASE; /* no condition */; k+=BASE) {
445 if(in>=srcLength) {
446 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
447 return 0;
448 }
449
450 digit=basicToDigit[(uint8_t)src[in++]];
451 if(digit<0) {
452 *pErrorCode=U_INVALID_CHAR_FOUND;
453 return 0;
454 }
455 if(digit>(0x7fffffff-i)/w) {
456 /* integer overflow */
457 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
458 return 0;
459 }
460
461 i+=digit*w;
462 /** RAM: comment out the old code for conformance with draft-ietf-idn-punycode-03.txt
463 t=k-bias;
464 if(t<TMIN) {
465 t=TMIN;
466 } else if(t>TMAX) {
467 t=TMAX;
468 }
469 */
470 t=k-bias;
471 if(t<TMIN) {
472 t=TMIN;
473 } else if(k>=(bias+TMAX)) {
474 t=TMAX;
475 }
476 if(digit<t) {
477 break;
478 }
479
480 if(w>0x7fffffff/(BASE-t)) {
481 /* integer overflow */
482 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
483 return 0;
484 }
485 w*=BASE-t;
486 }
487
488 /*
489 * Modification from sample code:
490 * Increments destCPCount here,
491 * where needed instead of in for() loop tail.
492 */
493 ++destCPCount;
494 bias=adaptBias(i-oldi, destCPCount, (UBool)(oldi==0));
495
496 /*
497 * i was supposed to wrap around from (incremented) destCPCount to 0,
498 * incrementing n each time, so we'll fix that now:
499 */
500 if(i/destCPCount>(0x7fffffff-n)) {
501 /* integer overflow */
502 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
503 return 0;
504 }
505
506 n+=i/destCPCount;
507 i%=destCPCount;
508 /* not needed for Punycode: */
509 /* if (decode_digit(n) <= BASE) return punycode_invalid_input; */
510
511 if(n>0x10ffff || UTF_IS_SURROGATE(n)) {
512 /* Unicode code point overflow */
513 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
514 return 0;
515 }
516
517 /* Insert n at position i of the output: */
518 cpLength=UTF_CHAR_LENGTH(n);
519 if((destLength+cpLength)<destCapacity) {
520 int32_t codeUnitIndex;
521
522 /*
523 * Handle indexes when supplementary code points are present.
524 *
525 * In almost all cases, there will be only BMP code points before i
526 * and even in the entire string.
527 * This is handled with the same efficiency as with UTF-32.
528 *
529 * Only the rare cases with supplementary code points are handled
530 * more slowly - but not too bad since this is an insertion anyway.
531 */
532 if(i<=firstSupplementaryIndex) {
533 codeUnitIndex=i;
534 if(cpLength>1) {
535 firstSupplementaryIndex=codeUnitIndex;
536 } else {
537 ++firstSupplementaryIndex;
538 }
539 } else {
540 codeUnitIndex=firstSupplementaryIndex;
541 UTF_FWD_N(dest, codeUnitIndex, destLength, i-codeUnitIndex);
542 }
543
544 /* use the UChar index codeUnitIndex instead of the code point index i */
545 if(codeUnitIndex<destLength) {
546 uprv_memmove(dest+codeUnitIndex+cpLength,
547 dest+codeUnitIndex,
548 (destLength-codeUnitIndex)*U_SIZEOF_UCHAR);
549 if(caseFlags!=NULL) {
550 uprv_memmove(caseFlags+codeUnitIndex+cpLength,
551 caseFlags+codeUnitIndex,
552 destLength-codeUnitIndex);
553 }
554 }
555 if(cpLength==1) {
556 /* BMP, insert one code unit */
557 dest[codeUnitIndex]=(UChar)n;
558 } else {
559 /* supplementary character, insert two code units */
560 dest[codeUnitIndex]=UTF16_LEAD(n);
561 dest[codeUnitIndex+1]=UTF16_TRAIL(n);
562 }
563 if(caseFlags!=NULL) {
564 /* Case of last character determines uppercase flag: */
565 caseFlags[codeUnitIndex]=IS_BASIC_UPPERCASE(src[in-1]);
566 if(cpLength==2) {
567 caseFlags[codeUnitIndex+1]=FALSE;
568 }
569 }
570 }
571 destLength+=cpLength;
572 ++i;
573 }
574
575 return u_terminateUChars(dest, destCapacity, destLength, pErrorCode);
576 }
577
578 /* ### check notes on overflow handling - only necessary if not IDNA? are these Punycode functions to be public? */
579
580 #endif /* #if !UCONFIG_NO_IDNA */