intl/icu/source/common/punycode.cpp@fc2d59ddac77
intl/icu/source/common/punycode.cpp
Wed, 31 Dec 2014 07:22:50 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 07:22:50 +0100
- branch
- TOR_BUG_3246
- changeset 4
- fc2d59ddac77
- permissions
- -rw-r--r--
Correct previous dual key logic pending first delivery installment.
1 /*
2 *******************************************************************************
3 *
4 * Copyright (C) 2002-2011, International Business Machines
5 * Corporation and others. All Rights Reserved.
6 *
7 *******************************************************************************
8 * file name: punycode.cpp
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 */
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/
25 Disclaimer and license
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 */
45 #include "unicode/utypes.h"
47 #if !UCONFIG_NO_IDNA
49 #include "unicode/ustring.h"
50 #include "unicode/utf.h"
51 #include "unicode/utf16.h"
52 #include "ustr_imp.h"
53 #include "cstring.h"
54 #include "cmemory.h"
55 #include "punycode.h"
56 #include "uassert.h"
59 /* Punycode ----------------------------------------------------------------- */
61 /* Punycode parameters for Bootstring */
62 #define BASE 36
63 #define TMIN 1
64 #define TMAX 26
65 #define SKEW 38
66 #define DAMP 700
67 #define INITIAL_BIAS 72
68 #define INITIAL_N 0x80
70 /* "Basic" Unicode/ASCII code points */
71 #define _HYPHEN 0X2d
72 #define DELIMITER _HYPHEN
74 #define _ZERO_ 0X30
75 #define _NINE 0x39
77 #define _SMALL_A 0X61
78 #define _SMALL_Z 0X7a
80 #define _CAPITAL_A 0X41
81 #define _CAPITAL_Z 0X5a
83 #define IS_BASIC(c) ((c)<0x80)
84 #define IS_BASIC_UPPERCASE(c) (_CAPITAL_A<=(c) && (c)<=_CAPITAL_Z)
86 /**
87 * digitToBasic() returns the basic code point whose value
88 * (when used for representing integers) is d, which must be in the
89 * range 0 to BASE-1. The lowercase form is used unless the uppercase flag is
90 * nonzero, in which case the uppercase form is used.
91 */
92 static inline char
93 digitToBasic(int32_t digit, UBool uppercase) {
94 /* 0..25 map to ASCII a..z or A..Z */
95 /* 26..35 map to ASCII 0..9 */
96 if(digit<26) {
97 if(uppercase) {
98 return (char)(_CAPITAL_A+digit);
99 } else {
100 return (char)(_SMALL_A+digit);
101 }
102 } else {
103 return (char)((_ZERO_-26)+digit);
104 }
105 }
107 /**
108 * basicToDigit[] contains the numeric value of a basic code
109 * point (for use in representing integers) in the range 0 to
110 * BASE-1, or -1 if b is does not represent a value.
111 */
112 static const int8_t
113 basicToDigit[256]={
114 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
115 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
117 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
118 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1, -1,
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,
123 -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
124 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
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,
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,
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,
135 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
136 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
137 };
139 static inline char
140 asciiCaseMap(char b, UBool uppercase) {
141 if(uppercase) {
142 if(_SMALL_A<=b && b<=_SMALL_Z) {
143 b-=(_SMALL_A-_CAPITAL_A);
144 }
145 } else {
146 if(_CAPITAL_A<=b && b<=_CAPITAL_Z) {
147 b+=(_SMALL_A-_CAPITAL_A);
148 }
149 }
150 return b;
151 }
153 /* Punycode-specific Bootstring code ---------------------------------------- */
155 /*
156 * The following code omits the {parts} of the pseudo-algorithm in the spec
157 * that are not used with the Punycode parameter set.
158 */
160 /* Bias adaptation function. */
161 static int32_t
162 adaptBias(int32_t delta, int32_t length, UBool firstTime) {
163 int32_t count;
165 if(firstTime) {
166 delta/=DAMP;
167 } else {
168 delta/=2;
169 }
171 delta+=delta/length;
172 for(count=0; delta>((BASE-TMIN)*TMAX)/2; count+=BASE) {
173 delta/=(BASE-TMIN);
174 }
176 return count+(((BASE-TMIN+1)*delta)/(delta+SKEW));
177 }
179 #define MAX_CP_COUNT 200
181 U_CFUNC int32_t
182 u_strToPunycode(const UChar *src, int32_t srcLength,
183 UChar *dest, int32_t destCapacity,
184 const UBool *caseFlags,
185 UErrorCode *pErrorCode) {
187 int32_t cpBuffer[MAX_CP_COUNT];
188 int32_t n, delta, handledCPCount, basicLength, destLength, bias, j, m, q, k, t, srcCPCount;
189 UChar c, c2;
191 /* argument checking */
192 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
193 return 0;
194 }
196 if(src==NULL || srcLength<-1 || (dest==NULL && destCapacity!=0)) {
197 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
198 return 0;
199 }
201 /*
202 * Handle the basic code points and
203 * convert extended ones to UTF-32 in cpBuffer (caseFlag in sign bit):
204 */
205 srcCPCount=destLength=0;
206 if(srcLength==-1) {
207 /* NUL-terminated input */
208 for(j=0; /* no condition */; ++j) {
209 if((c=src[j])==0) {
210 break;
211 }
212 if(srcCPCount==MAX_CP_COUNT) {
213 /* too many input code points */
214 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
215 return 0;
216 }
217 if(IS_BASIC(c)) {
218 cpBuffer[srcCPCount++]=0;
219 if(destLength<destCapacity) {
220 dest[destLength]=
221 caseFlags!=NULL ?
222 asciiCaseMap((char)c, caseFlags[j]) :
223 (char)c;
224 }
225 ++destLength;
226 } else {
227 n=(caseFlags!=NULL && caseFlags[j])<<31L;
228 if(U16_IS_SINGLE(c)) {
229 n|=c;
230 } else if(U16_IS_LEAD(c) && U16_IS_TRAIL(c2=src[j+1])) {
231 ++j;
232 n|=(int32_t)U16_GET_SUPPLEMENTARY(c, c2);
233 } else {
234 /* error: unmatched surrogate */
235 *pErrorCode=U_INVALID_CHAR_FOUND;
236 return 0;
237 }
238 cpBuffer[srcCPCount++]=n;
239 }
240 }
241 } else {
242 /* length-specified input */
243 for(j=0; j<srcLength; ++j) {
244 if(srcCPCount==MAX_CP_COUNT) {
245 /* too many input code points */
246 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
247 return 0;
248 }
249 c=src[j];
250 if(IS_BASIC(c)) {
251 cpBuffer[srcCPCount++]=0;
252 if(destLength<destCapacity) {
253 dest[destLength]=
254 caseFlags!=NULL ?
255 asciiCaseMap((char)c, caseFlags[j]) :
256 (char)c;
257 }
258 ++destLength;
259 } else {
260 n=(caseFlags!=NULL && caseFlags[j])<<31L;
261 if(U16_IS_SINGLE(c)) {
262 n|=c;
263 } else if(U16_IS_LEAD(c) && (j+1)<srcLength && U16_IS_TRAIL(c2=src[j+1])) {
264 ++j;
265 n|=(int32_t)U16_GET_SUPPLEMENTARY(c, c2);
266 } else {
267 /* error: unmatched surrogate */
268 *pErrorCode=U_INVALID_CHAR_FOUND;
269 return 0;
270 }
271 cpBuffer[srcCPCount++]=n;
272 }
273 }
274 }
276 /* Finish the basic string - if it is not empty - with a delimiter. */
277 basicLength=destLength;
278 if(basicLength>0) {
279 if(destLength<destCapacity) {
280 dest[destLength]=DELIMITER;
281 }
282 ++destLength;
283 }
285 /*
286 * handledCPCount is the number of code points that have been handled
287 * basicLength is the number of basic code points
288 * destLength is the number of chars that have been output
289 */
291 /* Initialize the state: */
292 n=INITIAL_N;
293 delta=0;
294 bias=INITIAL_BIAS;
296 /* Main encoding loop: */
297 for(handledCPCount=basicLength; handledCPCount<srcCPCount; /* no op */) {
298 /*
299 * All non-basic code points < n have been handled already.
300 * Find the next larger one:
301 */
302 for(m=0x7fffffff, j=0; j<srcCPCount; ++j) {
303 q=cpBuffer[j]&0x7fffffff; /* remove case flag from the sign bit */
304 if(n<=q && q<m) {
305 m=q;
306 }
307 }
309 /*
310 * Increase delta enough to advance the decoder's
311 * <n,i> state to <m,0>, but guard against overflow:
312 */
313 if(m-n>(0x7fffffff-MAX_CP_COUNT-delta)/(handledCPCount+1)) {
314 *pErrorCode=U_INTERNAL_PROGRAM_ERROR;
315 return 0;
316 }
317 delta+=(m-n)*(handledCPCount+1);
318 n=m;
320 /* Encode a sequence of same code points n */
321 for(j=0; j<srcCPCount; ++j) {
322 q=cpBuffer[j]&0x7fffffff; /* remove case flag from the sign bit */
323 if(q<n) {
324 ++delta;
325 } else if(q==n) {
326 /* Represent delta as a generalized variable-length integer: */
327 for(q=delta, k=BASE; /* no condition */; k+=BASE) {
329 /** RAM: comment out the old code for conformance with draft-ietf-idn-punycode-03.txt
331 t=k-bias;
332 if(t<TMIN) {
333 t=TMIN;
334 } else if(t>TMAX) {
335 t=TMAX;
336 }
337 */
339 t=k-bias;
340 if(t<TMIN) {
341 t=TMIN;
342 } else if(k>=(bias+TMAX)) {
343 t=TMAX;
344 }
346 if(q<t) {
347 break;
348 }
350 if(destLength<destCapacity) {
351 dest[destLength]=digitToBasic(t+(q-t)%(BASE-t), 0);
352 }
353 ++destLength;
354 q=(q-t)/(BASE-t);
355 }
357 if(destLength<destCapacity) {
358 dest[destLength]=digitToBasic(q, (UBool)(cpBuffer[j]<0));
359 }
360 ++destLength;
361 bias=adaptBias(delta, handledCPCount+1, (UBool)(handledCPCount==basicLength));
362 delta=0;
363 ++handledCPCount;
364 }
365 }
367 ++delta;
368 ++n;
369 }
371 return u_terminateUChars(dest, destCapacity, destLength, pErrorCode);
372 }
374 U_CFUNC int32_t
375 u_strFromPunycode(const UChar *src, int32_t srcLength,
376 UChar *dest, int32_t destCapacity,
377 UBool *caseFlags,
378 UErrorCode *pErrorCode) {
379 int32_t n, destLength, i, bias, basicLength, j, in, oldi, w, k, digit, t,
380 destCPCount, firstSupplementaryIndex, cpLength;
381 UChar b;
383 /* argument checking */
384 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
385 return 0;
386 }
388 if(src==NULL || srcLength<-1 || (dest==NULL && destCapacity!=0)) {
389 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
390 return 0;
391 }
393 if(srcLength==-1) {
394 srcLength=u_strlen(src);
395 }
397 /*
398 * Handle the basic code points:
399 * Let basicLength be the number of input code points
400 * before the last delimiter, or 0 if there is none,
401 * then copy the first basicLength code points to the output.
402 *
403 * The two following loops iterate backward.
404 */
405 for(j=srcLength; j>0;) {
406 if(src[--j]==DELIMITER) {
407 break;
408 }
409 }
410 destLength=basicLength=destCPCount=j;
411 U_ASSERT(destLength>=0);
413 while(j>0) {
414 b=src[--j];
415 if(!IS_BASIC(b)) {
416 *pErrorCode=U_INVALID_CHAR_FOUND;
417 return 0;
418 }
420 if(j<destCapacity) {
421 dest[j]=(UChar)b;
423 if(caseFlags!=NULL) {
424 caseFlags[j]=IS_BASIC_UPPERCASE(b);
425 }
426 }
427 }
429 /* Initialize the state: */
430 n=INITIAL_N;
431 i=0;
432 bias=INITIAL_BIAS;
433 firstSupplementaryIndex=1000000000;
435 /*
436 * Main decoding loop:
437 * Start just after the last delimiter if any
438 * basic code points were copied; start at the beginning otherwise.
439 */
440 for(in=basicLength>0 ? basicLength+1 : 0; in<srcLength; /* no op */) {
441 /*
442 * in is the index of the next character to be consumed, and
443 * destCPCount is the number of code points in the output array.
444 *
445 * Decode a generalized variable-length integer into delta,
446 * which gets added to i. The overflow checking is easier
447 * if we increase i as we go, then subtract off its starting
448 * value at the end to obtain delta.
449 */
450 for(oldi=i, w=1, k=BASE; /* no condition */; k+=BASE) {
451 if(in>=srcLength) {
452 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
453 return 0;
454 }
456 digit=basicToDigit[(uint8_t)src[in++]];
457 if(digit<0) {
458 *pErrorCode=U_INVALID_CHAR_FOUND;
459 return 0;
460 }
461 if(digit>(0x7fffffff-i)/w) {
462 /* integer overflow */
463 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
464 return 0;
465 }
467 i+=digit*w;
468 /** RAM: comment out the old code for conformance with draft-ietf-idn-punycode-03.txt
469 t=k-bias;
470 if(t<TMIN) {
471 t=TMIN;
472 } else if(t>TMAX) {
473 t=TMAX;
474 }
475 */
476 t=k-bias;
477 if(t<TMIN) {
478 t=TMIN;
479 } else if(k>=(bias+TMAX)) {
480 t=TMAX;
481 }
482 if(digit<t) {
483 break;
484 }
486 if(w>0x7fffffff/(BASE-t)) {
487 /* integer overflow */
488 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
489 return 0;
490 }
491 w*=BASE-t;
492 }
494 /*
495 * Modification from sample code:
496 * Increments destCPCount here,
497 * where needed instead of in for() loop tail.
498 */
499 ++destCPCount;
500 bias=adaptBias(i-oldi, destCPCount, (UBool)(oldi==0));
502 /*
503 * i was supposed to wrap around from (incremented) destCPCount to 0,
504 * incrementing n each time, so we'll fix that now:
505 */
506 if(i/destCPCount>(0x7fffffff-n)) {
507 /* integer overflow */
508 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
509 return 0;
510 }
512 n+=i/destCPCount;
513 i%=destCPCount;
514 /* not needed for Punycode: */
515 /* if (decode_digit(n) <= BASE) return punycode_invalid_input; */
517 if(n>0x10ffff || U_IS_SURROGATE(n)) {
518 /* Unicode code point overflow */
519 *pErrorCode=U_ILLEGAL_CHAR_FOUND;
520 return 0;
521 }
523 /* Insert n at position i of the output: */
524 cpLength=U16_LENGTH(n);
525 if(dest!=NULL && ((destLength+cpLength)<=destCapacity)) {
526 int32_t codeUnitIndex;
528 /*
529 * Handle indexes when supplementary code points are present.
530 *
531 * In almost all cases, there will be only BMP code points before i
532 * and even in the entire string.
533 * This is handled with the same efficiency as with UTF-32.
534 *
535 * Only the rare cases with supplementary code points are handled
536 * more slowly - but not too bad since this is an insertion anyway.
537 */
538 if(i<=firstSupplementaryIndex) {
539 codeUnitIndex=i;
540 if(cpLength>1) {
541 firstSupplementaryIndex=codeUnitIndex;
542 } else {
543 ++firstSupplementaryIndex;
544 }
545 } else {
546 codeUnitIndex=firstSupplementaryIndex;
547 U16_FWD_N(dest, codeUnitIndex, destLength, i-codeUnitIndex);
548 }
550 /* use the UChar index codeUnitIndex instead of the code point index i */
551 if(codeUnitIndex<destLength) {
552 uprv_memmove(dest+codeUnitIndex+cpLength,
553 dest+codeUnitIndex,
554 (destLength-codeUnitIndex)*U_SIZEOF_UCHAR);
555 if(caseFlags!=NULL) {
556 uprv_memmove(caseFlags+codeUnitIndex+cpLength,
557 caseFlags+codeUnitIndex,
558 destLength-codeUnitIndex);
559 }
560 }
561 if(cpLength==1) {
562 /* BMP, insert one code unit */
563 dest[codeUnitIndex]=(UChar)n;
564 } else {
565 /* supplementary character, insert two code units */
566 dest[codeUnitIndex]=U16_LEAD(n);
567 dest[codeUnitIndex+1]=U16_TRAIL(n);
568 }
569 if(caseFlags!=NULL) {
570 /* Case of last character determines uppercase flag: */
571 caseFlags[codeUnitIndex]=IS_BASIC_UPPERCASE(src[in-1]);
572 if(cpLength==2) {
573 caseFlags[codeUnitIndex+1]=FALSE;
574 }
575 }
576 }
577 destLength+=cpLength;
578 U_ASSERT(destLength>=0);
579 ++i;
580 }
582 return u_terminateUChars(dest, destCapacity, destLength, pErrorCode);
583 }
585 /* ### check notes on overflow handling - only necessary if not IDNA? are these Punycode functions to be public? */
587 #endif /* #if !UCONFIG_NO_IDNA */
