Line data Source code
1 : /* punycode.c --- Implementation of punycode used to ASCII encode IDN's. 2 : Copyright (C) 2002-2020 Simon Josefsson 3 : 4 : This file is part of GNU Libidn. 5 : 6 : GNU Libidn is free software: you can redistribute it and/or 7 : modify it under the terms of either: 8 : 9 : * the GNU Lesser General Public License as published by the Free 10 : Software Foundation; either version 3 of the License, or (at 11 : your option) any later version. 12 : 13 : or 14 : 15 : * the GNU General Public License as published by the Free 16 : Software Foundation; either version 2 of the License, or (at 17 : your option) any later version. 18 : 19 : or both in parallel, as here. 20 : 21 : GNU Libidn is distributed in the hope that it will be useful, 22 : but WITHOUT ANY WARRANTY; without even the implied warranty of 23 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 24 : General Public License for more details. 25 : 26 : You should have received copies of the GNU General Public License and 27 : the GNU Lesser General Public License along with this program. If 28 : not, see <http://www.gnu.org/licenses/>. */ 29 : 30 : /* 31 : * This file is derived from RFC 3492bis written by Adam M. Costello, 32 : * downloaded from http://www.nicemice.net/idn/punycode-spec.gz on 33 : * 2015年03月02日 with SHA1 a966a8017f6be579d74a50a226accc7607c40133, a 34 : * copy of which is stored in the GNU Libidn version controlled 35 : * repository under doc/specification/punycode-spec.gz. 36 : * 37 : * The changes compared to Adam's file include: re-indentation, adding 38 : * the license boilerplate and this comment, #include of config.h and 39 : * punycode.h, adding GTK-DOC comments, changing the return code of 40 : * punycode_encode and punycode_decode from enum to int, renaming the 41 : * input_length_orig function input variable to input_length (and 42 : * renaming the internal input_length variable to input_len) in 43 : * punycode_encode. 44 : * 45 : * Adam's file contains the following: 46 : * 47 : * punycode-sample.c 2.0.0 (2004-Mar-21-Sun) 48 : * http://www.nicemice.net/idn/ 49 : * Adam M. Costello 50 : * http://www.nicemice.net/amc/ 51 : * 52 : * This is ANSI C code (C89) implementing Punycode 1.0.x. 53 : * 54 : * Disclaimer and license: Regarding this entire document or any 55 : * portion of it (including the pseudocode and C code), the author 56 : * makes no guarantees and is not responsible for any damage resulting 57 : * from its use. The author grants irrevocable permission to anyone 58 : * to use, modify, and distribute it in any way that does not diminish 59 : * the rights of anyone else to use, modify, and distribute it, 60 : * provided that redistributed derivative works do not contain 61 : * misleading author or version information. Derivative works need 62 : * not be licensed under similar terms. 63 : */ 64 : 65 : #include <config.h> 66 : 67 : /**********************************************************/ 68 : /* Implementation (would normally go in its own .c file): */ 69 : 70 : #include <string.h> 71 : 72 : #include "punycode.h" 73 : 74 : /*** Bootstring parameters for Punycode ***/ 75 : 76 : enum 77 : { base = 36, tmin = 1, tmax = 26, skew = 38, damp = 700, 78 : initial_bias = 72, initial_n = 0x80, delimiter = 0x2D 79 : }; 80 : 81 : /* basic(cp) tests whether cp is a basic code point: */ 82 : #define basic(cp) ((punycode_uint)(cp) < 0x80) 83 : 84 : /* delim(cp) tests whether cp is a delimiter: */ 85 : #define delim(cp) ((cp) == delimiter) 86 : 87 : /* decode_digit(cp) returns the numeric value of a basic code */ 88 : /* point (for use in representing integers) in the range 0 to */ 89 : /* base-1, or base if cp does not represent a value. */ 90 : 91 : static unsigned 92 82649 : decode_digit (int cp) 93 : { 94 125764 : return (unsigned) (cp - 48 < 10 ? cp - 22 : cp - 65 < 26 ? cp - 65 : 95 43115 : cp - 97 < 26 ? cp - 97 : base); 96 : } 97 : 98 : /* encode_digit(d,flag) returns the basic code point whose value */ 99 : /* (when used for representing integers) is d, which needs to be in */ 100 : /* the range 0 to base-1. The lowercase form is used unless flag is */ 101 : /* nonzero, in which case the uppercase form is used. The behavior */ 102 : /* is undefined if flag is nonzero and digit d has no uppercase form. */ 103 : 104 : static char 105 83159 : encode_digit (punycode_uint d, int flag) 106 : { 107 83159 : return d + 22 + 75 * (d < 26) - ((flag != 0) << 5); 108 : /* 0..25 map to ASCII a..z or A..Z */ 109 : /* 26..35 map to ASCII 0..9 */ 110 : } 111 : 112 : /* flagged(bcp) tests whether a basic code point is flagged */ 113 : /* (uppercase). The behavior is undefined if bcp is not a */ 114 : /* basic code point. */ 115 : 116 : #define flagged(bcp) ((punycode_uint)(bcp) - 65 < 26) 117 : 118 : /* encode_basic(bcp,flag) forces a basic code point to lowercase */ 119 : /* if flag is zero, uppercase if flag is nonzero, and returns */ 120 : /* the resulting code point. The code point is unchanged if it */ 121 : /* is caseless. The behavior is undefined if bcp is not a basic */ 122 : /* code point. */ 123 : 124 : static char 125 0 : encode_basic (punycode_uint bcp, int flag) 126 : { 127 0 : bcp -= (bcp - 97 < 26) << 5; 128 0 : return bcp + ((!flag && (bcp - 65 < 26)) << 5); 129 : } 130 : 131 : /*** Platform-specific constants ***/ 132 : 133 : /* maxint is the maximum value of a punycode_uint variable: */ 134 : static const punycode_uint maxint = -1; 135 : /* Because maxint is unsigned, -1 becomes the maximum value. */ 136 : 137 : /*** Bias adaptation function ***/ 138 : 139 : static punycode_uint 140 94497 : adapt (punycode_uint delta, punycode_uint numpoints, int firsttime) 141 : { 142 : punycode_uint k; 143 : 144 94497 : delta = firsttime ? delta / damp : delta >> 1; 145 : /* delta >> 1 is a faster way of doing delta / 2 */ 146 94497 : delta += delta / numpoints; 147 : 148 101731 : for (k = 0; delta > ((base - tmin) * tmax) / 2; k += base) 149 : { 150 7234 : delta /= base - tmin; 151 : } 152 : 153 94497 : return k + (base - tmin + 1) * delta / (delta + skew); 154 : } 155 : 156 : /*** Main encode function ***/ 157 : 158 : /** 159 : * punycode_encode: 160 : * @input_length: The number of code points in the @input array and 161 : * the number of flags in the @case_flags array. 162 : * @input: An array of code points. They are presumed to be Unicode 163 : * code points, but that is not strictly REQUIRED. The array 164 : * contains code points, not code units. UTF-16 uses code units 165 : * D800 through DFFF to refer to code points 10000..10FFFF. The 166 : * code points D800..DFFF do not occur in any valid Unicode string. 167 : * The code points that can occur in Unicode strings (0..D7FF and 168 : * E000..10FFFF) are also called Unicode scalar values. 169 : * @case_flags: A %NULL pointer or an array of boolean values parallel 170 : * to the @input array. Nonzero (true, flagged) suggests that the 171 : * corresponding Unicode character be forced to uppercase after 172 : * being decoded (if possible), and zero (false, unflagged) suggests 173 : * that it be forced to lowercase (if possible). ASCII code points 174 : * (0..7F) are encoded literally, except that ASCII letters are 175 : * forced to uppercase or lowercase according to the corresponding 176 : * case flags. If @case_flags is a %NULL pointer then ASCII letters 177 : * are left as they are, and other code points are treated as 178 : * unflagged. 179 : * @output_length: The caller passes in the maximum number of ASCII 180 : * code points that it can receive. On successful return it will 181 : * contain the number of ASCII code points actually output. 182 : * @output: An array of ASCII code points. It is *not* 183 : * null-terminated; it will contain zeros if and only if the @input 184 : * contains zeros. (Of course the caller can leave room for a 185 : * terminator and add one if needed.) 186 : * 187 : * Converts a sequence of code points (presumed to be Unicode code 188 : * points) to Punycode. 189 : * 190 : * Return value: The return value can be any of the #Punycode_status 191 : * values defined above except %PUNYCODE_BAD_INPUT. If not 192 : * %PUNYCODE_SUCCESS, then @output_size and @output might contain 193 : * garbage. 194 : **/ 195 : int 196 9261 : punycode_encode (size_t input_length, 197 : const punycode_uint input[], 198 : const unsigned char case_flags[], 199 : size_t *output_length, char output[]) 200 : { 201 : punycode_uint input_len, n, delta, h, b, bias, j, m, q, k, t; 202 : size_t out, max_out; 203 : 204 : /* The Punycode spec assumes that the input length is the same type */ 205 : /* of integer as a code point, so we need to convert the size_t to */ 206 : /* a punycode_uint, which could overflow. */ 207 : 208 9261 : if (input_length > maxint) 209 0 : return punycode_overflow; 210 9261 : input_len = (punycode_uint) input_length; 211 : 212 : /* Initialize the state: */ 213 : 214 9261 : n = initial_n; 215 9261 : delta = 0; 216 9261 : out = 0; 217 9261 : max_out = *output_length; 218 9261 : bias = initial_bias; 219 : 220 : /* Handle the basic code points: */ 221 : 222 82479 : for (j = 0; j < input_len; ++j) 223 : { 224 73427 : if (basic (input[j])) 225 : { 226 24514 : if (max_out - out < 2) 227 209 : return punycode_big_output; 228 48610 : output[out++] = case_flags ? 229 24305 : encode_basic (input[j], case_flags[j]) : (char) input[j]; 230 : } 231 48913 : else if (input[j] > 0x10FFFF 232 48913 : || (input[j] >= 0xD800 && input[j] <= 0xDBFF)) 233 0 : return punycode_bad_input; 234 : /* else if (input[j] < n) return punycode_bad_input; */ 235 : /* (not needed for Punycode with unsigned code points) */ 236 : } 237 : 238 9052 : h = b = (punycode_uint) out; 239 : /* cannot overflow because out <= input_len <= maxint */ 240 : 241 : /* h is the number of code points that have been handled, b is the */ 242 : /* number of basic code points, and out is the number of ASCII code */ 243 : /* points that have been output. */ 244 : 245 9052 : if (b > 0) 246 1788 : output[out++] = delimiter; 247 : 248 : /* Main encoding loop: */ 249 : 250 38003 : while (h < input_len) 251 : { 252 : /* All non-basic code points < n have been */ 253 : /* handled already. Find the next larger one: */ 254 : 255 784268 : for (m = maxint, j = 0; j < input_len; ++j) 256 : { 257 : /* if (basic(input[j])) continue; */ 258 : /* (not needed for Punycode) */ 259 754675 : if (input[j] >= n && input[j] < m) 260 76437 : m = input[j]; 261 : } 262 : 263 : /* Increase delta enough to advance the decoder's */ 264 : /* <n,i> state to <m,0>, but guard against overflow: */ 265 : 266 29593 : if (m - n > (maxint - delta) / (h + 1)) 267 0 : return punycode_overflow; 268 29593 : delta += (m - n) * (h + 1); 269 29593 : n = m; 270 : 271 769230 : for (j = 0; j < input_len; ++j) 272 : { 273 : /* Punycode does not need to check whether input[j] is basic: */ 274 740279 : if (input[j] < n /* || basic(input[j]) */ ) 275 : { 276 318537 : if (++delta == 0) 277 0 : return punycode_overflow; 278 : } 279 : 280 740279 : if (input[j] == n) 281 : { 282 : /* Represent delta as a generalized variable-length integer: */ 283 : 284 45572 : for (q = delta, k = base;; k += base) 285 : { 286 83801 : if (out >= max_out) 287 642 : return punycode_big_output; 288 146170 : t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */ 289 63011 : k >= bias + tmax ? tmax : k - bias; 290 83159 : if (q < t) 291 44930 : break; 292 38229 : output[out++] = encode_digit (t + (q - t) % (base - t), 0); 293 38229 : q = (q - t) / (base - t); 294 : } 295 : 296 44930 : output[out++] = encode_digit (q, case_flags && case_flags[j]); 297 44930 : bias = adapt (delta, h + 1, h == b); 298 44930 : delta = 0; 299 44930 : ++h; 300 : } 301 : } 302 : 303 28951 : ++delta, ++n; 304 : } 305 : 306 8410 : *output_length = out; 307 8410 : return punycode_success; 308 : } 309 : 310 : /*** Main decode function ***/ 311 : 312 : /** 313 : * punycode_decode: 314 : * @input_length: The number of ASCII code points in the @input array. 315 : * @input: An array of ASCII code points (0..7F). 316 : * @output_length: The caller passes in the maximum number of code 317 : * points that it can receive into the @output array (which is also 318 : * the maximum number of flags that it can receive into the 319 : * @case_flags array, if @case_flags is not a %NULL pointer). On 320 : * successful return it will contain the number of code points 321 : * actually output (which is also the number of flags actually 322 : * output, if case_flags is not a null pointer). The decoder will 323 : * never need to output more code points than the number of ASCII 324 : * code points in the input, because of the way the encoding is 325 : * defined. The number of code points output cannot exceed the 326 : * maximum possible value of a punycode_uint, even if the supplied 327 : * @output_length is greater than that. 328 : * @output: An array of code points like the input argument of 329 : * punycode_encode() (see above). 330 : * @case_flags: A %NULL pointer (if the flags are not needed by the 331 : * caller) or an array of boolean values parallel to the @output 332 : * array. Nonzero (true, flagged) suggests that the corresponding 333 : * Unicode character be forced to uppercase by the caller (if 334 : * possible), and zero (false, unflagged) suggests that it be forced 335 : * to lowercase (if possible). ASCII code points (0..7F) are output 336 : * already in the proper case, but their flags will be set 337 : * appropriately so that applying the flags would be harmless. 338 : * 339 : * Converts Punycode to a sequence of code points (presumed to be 340 : * Unicode code points). 341 : * 342 : * Return value: The return value can be any of the #Punycode_status 343 : * values defined above. If not %PUNYCODE_SUCCESS, then 344 : * @output_length, @output, and @case_flags might contain garbage. 345 : * 346 : **/ 347 : int 348 21264 : punycode_decode (size_t input_length, 349 : const char input[], 350 : size_t *output_length, 351 : punycode_uint output[], unsigned char case_flags[]) 352 : { 353 : punycode_uint n, out, i, max_out, bias, oldi, w, k, digit, t; 354 : size_t b, j, in; 355 : 356 : /* Initialize the state: */ 357 : 358 21264 : n = initial_n; 359 21264 : out = i = 0; 360 42528 : max_out = *output_length > maxint ? maxint 361 21264 : : (punycode_uint) * output_length; 362 21264 : bias = initial_bias; 363 : 364 : /* Handle the basic code points: Let b be the number of input code */ 365 : /* points before the last delimiter, or 0 if there is none, then */ 366 : /* copy the first b code points to the output. */ 367 : 368 183543 : for (b = j = 0; j < input_length; ++j) 369 162279 : if (delim (input[j])) 370 17225 : b = j; 371 21264 : if (b > max_out) 372 246 : return punycode_big_output; 373 : 374 69197 : for (j = 0; j < b; ++j) 375 : { 376 48484 : if (case_flags) 377 0 : case_flags[out] = flagged (input[j]); 378 48484 : if (!basic (input[j])) 379 305 : return punycode_bad_input; 380 48179 : output[out++] = input[j]; 381 : } 382 118108 : for (j = b + (b > 0); j < input_length; ++j) 383 97525 : if (!basic (input[j])) 384 130 : return punycode_bad_input; 385 : 386 : /* Main decoding loop: Start just after the last delimiter if any */ 387 : /* basic code points were copied; start at the beginning otherwise. */ 388 : 389 68812 : for (in = b > 0 ? b + 1 : 0; in < input_length; ++out) 390 : { 391 : 392 : /* in is the index of the next ASCII code point to be consumed, */ 393 : /* and out is the number of code points in the output array. */ 394 : 395 : /* Decode a generalized variable-length integer into delta, */ 396 : /* which gets added to i. The overflow checking is easier */ 397 : /* if we increase i as we go, then subtract off its starting */ 398 : /* value at the end to obtain delta. */ 399 : 400 50897 : for (oldi = i, w = 1, k = base;; k += base) 401 : { 402 83665 : if (in >= input_length) 403 1016 : return punycode_bad_input; 404 82649 : digit = decode_digit (input[in++]); 405 82649 : if (digit >= base) 406 86 : return punycode_bad_input; 407 82563 : if (digit > (maxint - i) / w) 408 228 : return punycode_overflow; 409 82335 : i += digit * w; 410 140884 : t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */ 411 58549 : k >= bias + tmax ? tmax : k - bias; 412 82335 : if (digit < t) 413 49567 : break; 414 32768 : if (w > maxint / (base - t)) 415 0 : return punycode_overflow; 416 32768 : w *= (base - t); 417 : } 418 : 419 49567 : bias = adapt (i - oldi, out + 1, oldi == 0); 420 : 421 : /* i was supposed to wrap around from out+1 to 0, */ 422 : /* incrementing n each time, so we'll fix that now: */ 423 : 424 49567 : if (i / (out + 1) > maxint - n) 425 0 : return punycode_overflow; 426 49567 : n += i / (out + 1); 427 49567 : if (n > 0x10FFFF || (n >= 0xD800 && n <= 0xDBFF)) 428 1136 : return punycode_bad_input; 429 48431 : i %= (out + 1); 430 : 431 : /* Insert n at position i of the output: */ 432 : 433 : /* not needed for Punycode: */ 434 : /* if (basic(n)) return punycode_bad_input; */ 435 48431 : if (out >= max_out) 436 202 : return punycode_big_output; 437 : 438 48229 : if (case_flags) 439 : { 440 0 : memmove (case_flags + i + 1, case_flags + i, out - i); 441 : /* Case of last ASCII code point determines case flag: */ 442 0 : case_flags[i] = flagged (input[in - 1]); 443 : } 444 : 445 48229 : memmove (output + i + 1, output + i, (out - i) * sizeof *output); 446 48229 : output[i++] = n; 447 : } 448 : 449 17915 : *output_length = (size_t) out; 450 : /* cannot overflow because out <= old value of *output_length */ 451 17915 : return punycode_success; 452 : } 453 : 454 : /** 455 : * punycode_uint 456 : * 457 : * Unicode code point data type, this is always a 32 bit unsigned 458 : * integer. 459 : */ 460 : 461 : /** 462 : * Punycode_status 463 : * @PUNYCODE_SUCCESS: Successful operation. This value is guaranteed 464 : * to always be zero, the remaining ones are only guaranteed to hold 465 : * non-zero values, for logical comparison purposes. 466 : * @PUNYCODE_BAD_INPUT: Input is invalid. 467 : * @PUNYCODE_BIG_OUTPUT: Output would exceed the space provided. 468 : * @PUNYCODE_OVERFLOW: Input needs wider integers to process. 469 : * 470 : * Enumerated return codes of punycode_encode() and punycode_decode(). 471 : * The value 0 is guaranteed to always correspond to success. 472 : */