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