1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 *******************************************************************************
5 *
6 * Copyright (C) 2003-2005, International Business Machines
7 * Corporation and others. All Rights Reserved.
8 *
9 *******************************************************************************
10 * file name: punyref.cpp
11 * encoding: UTF-8
12 * tab size: 8 (not used)
13 * indentation:4
14 *
15 * created on: 2003feb1
16 * created by: Ram Viswanadha
17 */
18
19 /*
20 Disclaimer and license
21
22 Regarding this entire document or any portion of it (including
23 the pseudocode and C code), the author makes no guarantees and
24 is not responsible for any damage resulting from its use. The
25 author grants irrevocable permission to anyone to use, modify,
26 and distribute it in any way that does not diminish the rights
27 of anyone else to use, modify, and distribute it, provided that
28 redistributed derivative works do not contain misleading author or
29 version information. Derivative works need not be licensed under
30 similar terms.
31
32 punycode.c 0.4.0 (2001-Nov-17-Sat)
33 http://www.cs.berkeley.edu/~amc/idn/
34 Adam M. Costello
35 http://www.nicemice.net/amc/
36 */
37
38 /**********************************************************/
39 /* Implementation (would normally go in its own .c file): */
40
41 #include <string.h>
42
43 #include "unicode/utypes.h"
44
45 #if !UCONFIG_NO_IDNA
46
47 #include "punyref.h"
48
49 /*** Bootstring parameters for Punycode ***/
50
51 enum { base = 36, tmin = 1, tmax = 26, skew = 38, damp = 700,
52 initial_bias = 72, initial_n = 0x80, delimiter = 0x2D };
53
54 /* basic(cp) tests whether cp is a basic code point: */
55 #define basic(cp) ((punycode_uint)(cp) < 0x80)
56
57 /* delim(cp) tests whether cp is a delimiter: */
58 #define delim(cp) ((cp) == delimiter)
59
60 U_CDECL_BEGIN
61 /* decode_digit(cp) returns the numeric value of a basic code */
62 /* point (for use in representing integers) in the range 0 to */
63 /* base-1, or base if cp is does not represent a value. */
64
decode_digit(punycode_uint cp)65 static punycode_uint decode_digit(punycode_uint cp)
66 {
67 return cp - 48 < 10 ? cp - 22 : cp - 65 < 26 ? cp - 65 :
68 cp - 97 < 26 ? cp - 97 : static_cast<punycode_uint>(base);
69 }
70
71 /* encode_digit(d,flag) returns the basic code point whose value */
72 /* (when used for representing integers) is d, which needs to be in */
73 /* the range 0 to base-1. The lowercase form is used unless flag is */
74 /* nonzero, in which case the uppercase form is used. The behavior */
75 /* is undefined if flag is nonzero and digit d has no uppercase form. */
76
encode_digit(punycode_uint d,int flag)77 static char encode_digit(punycode_uint d, int flag)
78 {
79 return (char) d + 22 + 75 * (d < 26) - ((flag != 0) << 5);
80 /* 0..25 map to ASCII a..z or A..Z */
81 /* 26..35 map to ASCII 0..9 */
82 }
83
84 /* flagged(bcp) tests whether a basic code point is flagged */
85 /* (uppercase). The behavior is undefined if bcp is not a */
86 /* basic code point. */
87
88 #define flagged(bcp) ((punycode_uint)(bcp) - 65 < 26)
89
90 /* encode_basic(bcp,flag) forces a basic code point to lowercase */
91 /* if flag is zero, uppercase if flag is nonzero, and returns */
92 /* the resulting code point. The code point is unchanged if it */
93 /* is caseless. The behavior is undefined if bcp is not a basic */
94 /* code point. */
95
encode_basic(punycode_uint bcp,int flag)96 static char encode_basic(punycode_uint bcp, int flag)
97 {
98 bcp -= (bcp - 97 < 26) << 5;
99 return (char) bcp + ((!flag && (bcp - 65 < 26)) << 5);
100 }
101
102 /*** Platform-specific constants ***/
103
104 /* maxint is the maximum value of a punycode_uint variable: */
105 static const punycode_uint maxint = (punycode_uint) (-1);
106 /* Because maxint is unsigned, -1 becomes the maximum value. */
107
108 /*** Bias adaptation function ***/
109
adapt(punycode_uint delta,punycode_uint numpoints,int firsttime)110 static punycode_uint adapt(
111 punycode_uint delta, punycode_uint numpoints, int firsttime )
112 {
113 punycode_uint k;
114
115 delta = firsttime ? delta / damp : delta >> 1;
116 /* delta >> 1 is a faster way of doing delta / 2 */
117 delta += delta / numpoints;
118
119 for (k = 0; delta > ((base - tmin) * tmax) / 2; k += base) {
120 delta /= base - tmin;
121 }
122
123 return k + (base - tmin + 1) * delta / (delta + skew);
124 }
125
126 /*** Main encode function ***/
127
punycode_encode(punycode_uint input_length,const punycode_uint input[],const unsigned char case_flags[],punycode_uint * output_length,char output[])128 enum punycode_status punycode_encode(
129 punycode_uint input_length,
130 const punycode_uint input[],
131 const unsigned char case_flags[],
132 punycode_uint *output_length,
133 char output[] )
134 {
135 punycode_uint n, delta, h, b, out, max_out, bias, j, m, q, k, t;
136
137 /* Initialize the state: */
138
139 n = initial_n;
140 delta = out = 0;
141 max_out = *output_length;
142 bias = initial_bias;
143
144 /* Handle the basic code points: */
145
146 for (j = 0; j < input_length; ++j) {
147 if (basic(input[j])) {
148 if (max_out - out < 2) return punycode_big_output;
149 output[out++] = (char)
150 (case_flags ? encode_basic(input[j], case_flags[j]) : input[j]);
151 }
152 /* else if (input[j] < n) return punycode_bad_input; */
153 /* (not needed for Punycode with unsigned code points) */
154 }
155
156 h = b = out;
157
158 /* h is the number of code points that have been handled, b is the */
159 /* number of basic code points, and out is the number of characters */
160 /* that have been output. */
161
162 if (b > 0) output[out++] = delimiter;
163
164 /* Main encoding loop: */
165
166 while (h < input_length) {
167 /* All non-basic code points < n have been */
168 /* handled already. Find the next larger one: */
169
170 for (m = maxint, j = 0; j < input_length; ++j) {
171 /* if (basic(input[j])) continue; */
172 /* (not needed for Punycode) */
173 if (input[j] >= n && input[j] < m) m = input[j];
174 }
175
176 /* Increase delta enough to advance the decoder's */
177 /* <n,i> state to <m,0>, but guard against overflow: */
178
179 if (m - n > (maxint - delta) / (h + 1)) return punycode_overflow;
180 delta += (m - n) * (h + 1);
181 n = m;
182
183 for (j = 0; j < input_length; ++j) {
184 /* Punycode does not need to check whether input[j] is basic: */
185 if (input[j] < n /* || basic(input[j]) */ ) {
186 if (++delta == 0) return punycode_overflow;
187 }
188
189 if (input[j] == n) {
190 /* Represent delta as a generalized variable-length integer: */
191
192 for (q = delta, k = base; ; k += base) {
193 if (out >= max_out) return punycode_big_output;
194 t = k <= bias /* + tmin */ ? static_cast<punycode_uint>(tmin) : /* +tmin not needed */
195 k >= bias + tmax ? static_cast<punycode_uint>(tmax) : k - bias;
196 if (q < t) break;
197 output[out++] = encode_digit(t + (q - t) % (base - t), 0);
198 q = (q - t) / (base - t);
199 }
200
201 output[out++] = encode_digit(q, case_flags && case_flags[j]);
202 bias = adapt(delta, h + 1, h == b);
203 delta = 0;
204 ++h;
205 }
206 }
207
208 ++delta, ++n;
209 }
210
211 *output_length = out;
212 return punycode_success;
213 }
214
215 /*** Main decode function ***/
216
punycode_decode(punycode_uint input_length,const char input[],punycode_uint * output_length,punycode_uint output[],unsigned char case_flags[])217 enum punycode_status punycode_decode(
218 punycode_uint input_length,
219 const char input[],
220 punycode_uint *output_length,
221 punycode_uint output[],
222 unsigned char case_flags[] )
223 {
224 punycode_uint n, out, i, max_out, bias,
225 b, j, in, oldi, w, k, digit, t;
226
227 /* Initialize the state: */
228
229 n = initial_n;
230 out = i = 0;
231 max_out = *output_length;
232 bias = initial_bias;
233
234 /* Handle the basic code points: Let b be the number of input code */
235 /* points before the last delimiter, or 0 if there is none, then */
236 /* copy the first b code points to the output. */
237
238 for (b = j = 0; j < input_length; ++j) if (delim(input[j])) b = j;
239 if (b > max_out) return punycode_big_output;
240
241 for (j = 0; j < b; ++j) {
242 if (case_flags) case_flags[out] = flagged(input[j]);
243 if (!basic(input[j])) return punycode_bad_input;
244 output[out++] = input[j];
245 }
246
247 /* Main decoding loop: Start just after the last delimiter if any */
248 /* basic code points were copied; start at the beginning otherwise. */
249
250 for (in = b > 0 ? b + 1 : 0; in < input_length; ++out) {
251
252 /* in is the index of the next character to be consumed, and */
253 /* out is the number of code points in the output array. */
254
255 /* Decode a generalized variable-length integer into delta, */
256 /* which gets added to i. The overflow checking is easier */
257 /* if we increase i as we go, then subtract off its starting */
258 /* value at the end to obtain delta. */
259
260 for (oldi = i, w = 1, k = base; ; k += base) {
261 if (in >= input_length) return punycode_bad_input;
262 digit = decode_digit(input[in++]);
263 if (digit >= base) return punycode_bad_input;
264 if (digit > (maxint - i) / w) return punycode_overflow;
265 i += digit * w;
266 t = k <= bias /* + tmin */ ? static_cast<punycode_uint>(tmin) : /* +tmin not needed */
267 k >= bias + tmax ? static_cast<punycode_uint>(tmax) : k - bias;
268 if (digit < t) break;
269 if (w > maxint / (base - t)) return punycode_overflow;
270 w *= (base - t);
271 }
272
273 bias = adapt(i - oldi, out + 1, oldi == 0);
274
275 /* i was supposed to wrap around from out+1 to 0, */
276 /* incrementing n each time, so we'll fix that now: */
277
278 if (i / (out + 1) > maxint - n) return punycode_overflow;
279 n += i / (out + 1);
280 i %= (out + 1);
281
282 /* Insert n at position i of the output: */
283
284 /* not needed for Punycode: */
285 /* if (decode_digit(n) <= base) return punycode_invalid_input; */
286 if (out >= max_out) return punycode_big_output;
287
288 if (case_flags) {
289 memmove(case_flags + i + 1, case_flags + i, out - i);
290 /* Case of last character determines uppercase flag: */
291 case_flags[i] = flagged(input[in - 1]);
292 }
293
294 memmove(output + i + 1, output + i, (out - i) * sizeof *output);
295 output[i++] = n;
296 }
297
298 *output_length = out;
299 return punycode_success;
300 }
301
302 U_CDECL_END
303
304 #endif /* #if !UCONFIG_NO_IDNA */
305