Rename.
[libidn.git] / punycode.c
blob3a3f0562fe742c1682124bfad4f9b8760e9209f4
1 /* punycode.c Implementation of punycode used to ASCII encode IDN's.
2 * Copyright (C) 2002 Adam M. Costello
3 * Copyright (C) 2002 Simon Josefsson
5 * This file is part of Libstringprep.
7 * Libstringprep is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * Libstringprep is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with Libstringprep; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 * This file is derived from from draft-ietf-idn-punycode-03.txt by
25 * Adam M. Costello.
27 * Disclaimer and license: Regarding this entire document or any
28 * portion of it (including the pseudocode and C code), the author
29 * makes no guarantees and is not responsible for any damage resulting
30 * from its use. The author grants irrevocable permission to anyone
31 * to use, modify, and distribute it in any way that does not diminish
32 * the rights of anyone else to use, modify, and distribute it,
33 * provided that redistributed derivative works do not contain
34 * misleading author or version information. Derivative works need
35 * not be licensed under similar terms.
39 #include "internal.h"
41 /*** Bootstring parameters for Punycode ***/
43 enum
44 { base = 36, tmin = 1, tmax = 26, skew = 38, damp = 700,
45 initial_bias = 72, initial_n = 0x80, delimiter = 0x2D
48 /* basic(cp) tests whether cp is a basic code point: */
49 #define basic(cp) ((unsigned long)(cp) < 0x80)
51 /* delim(cp) tests whether cp is a delimiter: */
52 #define delim(cp) ((cp) == delimiter)
54 /* decode_digit(cp) returns the numeric value of a basic code */
55 /* point (for use in representing integers) in the range 0 to */
56 /* base-1, or base if cp is does not represent a value. */
58 static unsigned long
59 decode_digit (unsigned long cp)
61 return cp - 48 < 10 ? cp - 22 : cp - 65 < 26 ? cp - 65 :
62 cp - 97 < 26 ? cp - 97 : base;
65 /* encode_digit(d,flag) returns the basic code point whose value */
66 /* (when used for representing integers) is d, which needs to be in */
67 /* the range 0 to base-1. The lowercase form is used unless flag is */
68 /* nonzero, in which case the uppercase form is used. The behavior */
69 /* is undefined if flag is nonzero and digit d has no uppercase form. */
71 static char
72 encode_digit (unsigned long d, int flag)
74 return d + 22 + 75 * (d < 26) - ((flag != 0) << 5);
75 /* 0..25 map to ASCII a..z or A..Z */
76 /* 26..35 map to ASCII 0..9 */
79 /* flagged(bcp) tests whether a basic code point is flagged */
80 /* (uppercase). The behavior is undefined if bcp is not a */
81 /* basic code point. */
83 #define flagged(bcp) ((unsigned long)(bcp) - 65 < 26)
85 /* encode_basic(bcp,flag) forces a basic code point to lowercase */
86 /* if flag is zero, uppercase if flag is nonzero, and returns */
87 /* the resulting code point. The code point is unchanged if it */
88 /* is caseless. The behavior is undefined if bcp is not a basic */
89 /* code point. */
91 static char
92 encode_basic (unsigned long bcp, int flag)
94 bcp -= (bcp - 97 < 26) << 5;
95 return bcp + ((!flag && (bcp - 65 < 26)) << 5);
98 /*** Platform-specific constants ***/
100 /* maxint is the maximum value of a unsigned long variable: */
101 static const unsigned long maxint = -1;
102 /* Because maxint is unsigned, -1 becomes the maximum value. */
104 /*** Bias adaptation function ***/
106 static unsigned long
107 adapt (unsigned long delta, unsigned long numpoints, int firsttime)
109 unsigned long k;
111 delta = firsttime ? delta / damp : delta >> 1;
112 /* delta >> 1 is a faster way of doing delta / 2 */
113 delta += delta / numpoints;
115 for (k = 0; delta > ((base - tmin) * tmax) / 2; k += base)
117 delta /= base - tmin;
120 return k + (base - tmin + 1) * delta / (delta + skew);
123 /*** Main encode function ***/
126 punycode_encode (size_t input_length,
127 const unsigned long input[],
128 const unsigned char case_flags[],
129 size_t * output_length, char output[])
131 unsigned long n, delta, b, out, bias, m, q, k, t;
132 size_t h, j, max_out;
134 /* Initialize the state: */
136 n = initial_n;
137 delta = out = 0;
138 max_out = *output_length;
139 bias = initial_bias;
141 /* Handle the basic code points: */
143 for (j = 0; j < input_length; ++j)
145 if (basic (input[j]))
147 if (max_out - out < 2)
148 return PUNYCODE_BIG_OUTPUT;
149 output[out++] =
150 case_flags ? encode_basic (input[j], case_flags[j]) : input[j];
152 /* else if (input[j] < n) return punycode_bad_input; */
153 /* (not needed for Punycode with unsigned code points) */
156 h = b = out;
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. */
162 if (b > 0)
163 output[out++] = delimiter;
165 /* Main encoding loop: */
167 while (h < input_length)
169 /* All non-basic code points < n have been */
170 /* handled already. Find the next larger one: */
172 for (m = maxint, j = 0; j < input_length; ++j)
174 /* if (basic(input[j])) continue; */
175 /* (not needed for Punycode) */
176 if (input[j] >= n && input[j] < m)
177 m = input[j];
180 /* Increase delta enough to advance the decoder's */
181 /* <n,i> state to <m,0>, but guard against overflow: */
183 if (m - n > (maxint - delta) / (h + 1))
184 return PUNYCODE_OVERFLOW;
185 delta += (m - n) * (h + 1);
186 n = m;
188 for (j = 0; j < input_length; ++j)
190 /* Punycode does not need to check whether input[j] is basic: */
191 if (input[j] < n /* || basic(input[j]) */ )
193 if (++delta == 0)
194 return PUNYCODE_OVERFLOW;
197 if (input[j] == n)
199 /* Represent delta as a generalized variable-length integer: */
201 for (q = delta, k = base;; k += base)
203 if (out >= max_out)
204 return PUNYCODE_BIG_OUTPUT;
205 t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */
206 k >= bias + tmax ? tmax : k - bias;
207 if (q < t)
208 break;
209 output[out++] = encode_digit (t + (q - t) % (base - t), 0);
210 q = (q - t) / (base - t);
213 output[out++] = encode_digit (q, case_flags && case_flags[j]);
214 bias = adapt (delta, h + 1, h == b);
215 delta = 0;
216 ++h;
220 ++delta, ++n;
223 *output_length = out;
224 return PUNYCODE_SUCCESS;
227 /*** Main decode function ***/
230 punycode_decode (size_t input_length,
231 const char input[],
232 size_t * output_length,
233 unsigned long output[], unsigned char case_flags[])
235 unsigned long n, i, bias, b, in, oldi, w, k, digit, t;
236 size_t out, max_out, j;
238 /* Initialize the state: */
240 n = initial_n;
241 out = i = 0;
242 max_out = *output_length;
243 bias = initial_bias;
245 /* Handle the basic code points: Let b be the number of input code */
246 /* points before the last delimiter, or 0 if there is none, then */
247 /* copy the first b code points to the output. */
249 for (b = j = 0; j < input_length; ++j)
250 if (delim (input[j]))
251 b = j;
252 if (b > max_out)
253 return PUNYCODE_BIG_OUTPUT;
255 for (j = 0; j < b; ++j)
257 if (case_flags)
258 case_flags[out] = flagged (input[j]);
259 if (!basic (input[j]))
260 return PUNYCODE_BAD_INPUT;
261 output[out++] = input[j];
264 /* Main decoding loop: Start just after the last delimiter if any */
265 /* basic code points were copied; start at the beginning otherwise. */
267 for (in = b > 0 ? b + 1 : 0; in < input_length; ++out)
270 /* in is the index of the next character to be consumed, and */
271 /* out is the number of code points in the output array. */
273 /* Decode a generalized variable-length integer into delta, */
274 /* which gets added to i. The overflow checking is easier */
275 /* if we increase i as we go, then subtract off its starting */
276 /* value at the end to obtain delta. */
278 for (oldi = i, w = 1, k = base;; k += base)
280 if (in >= input_length)
281 return PUNYCODE_BAD_INPUT;
282 digit = decode_digit (input[in++]);
283 if (digit >= base)
284 return PUNYCODE_BAD_INPUT;
285 if (digit > (maxint - i) / w)
286 return PUNYCODE_OVERFLOW;
287 i += digit * w;
288 t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */
289 k >= bias + tmax ? tmax : k - bias;
290 if (digit < t)
291 break;
292 if (w > maxint / (base - t))
293 return PUNYCODE_OVERFLOW;
294 w *= (base - t);
297 bias = adapt (i - oldi, out + 1, oldi == 0);
299 /* i was supposed to wrap around from out+1 to 0, */
300 /* incrementing n each time, so we'll fix that now: */
302 if (i / (out + 1) > maxint - n)
303 return PUNYCODE_OVERFLOW;
304 n += i / (out + 1);
305 i %= (out + 1);
307 /* Insert n at position i of the output: */
309 /* not needed for Punycode: */
310 /* if (decode_digit(n) <= base) return punycode_invalid_input; */
311 if (out >= max_out)
312 return PUNYCODE_BIG_OUTPUT;
314 if (case_flags)
316 memmove (case_flags + i + 1, case_flags + i, out - i);
317 /* Case of last character determines uppercase flag: */
318 case_flags[i] = flagged (input[in - 1]);
321 memmove (output + i + 1, output + i, (out - i) * sizeof *output);
322 output[i++] = n;
325 *output_length = out;
326 return PUNYCODE_SUCCESS;