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