Branch data Line data Source code
1 : : /* punycode.c - punycode encoding/decoding
2 : : Copyright (C) 2011 Simon Josefsson
3 : :
4 : : This program is free software: you can redistribute it and/or modify
5 : : it under the terms of the GNU General Public License as published by
6 : : the Free Software Foundation, either version 3 of the License, or
7 : : (at your option) any later version.
8 : :
9 : : This program is distributed in the hope that it will be useful,
10 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : : GNU General Public License for more details.
13 : :
14 : : You should have received a copy of the GNU General Public License
15 : : along with this program. If not, see <http://www.gnu.org/licenses/>.
16 : : */
17 : :
18 : : /*
19 : : Code copied from http://www.nicemice.net/idn/punycode-spec.gz on
20 : : 2011-01-04 with SHA-1 a966a8017f6be579d74a50a226accc7607c40133
21 : : labeled punycode-spec 1.0.3 (2006-Mar-23-Thu). It is modified for
22 : : Libidn2 by Simon Josefsson. License on the original code:
23 : :
24 : : punycode-spec 1.0.3 (2006-Mar-23-Thu)
25 : : http://www.nicemice.net/idn/
26 : : Adam M. Costello
27 : : http://www.nicemice.net/amc/
28 : :
29 : : B. Disclaimer and license
30 : :
31 : : Regarding this entire document or any portion of it (including
32 : : the pseudocode and C code), the author makes no guarantees and
33 : : is not responsible for any damage resulting from its use. The
34 : : author grants irrevocable permission to anyone to use, modify,
35 : : and distribute it in any way that does not diminish the rights
36 : : of anyone else to use, modify, and distribute it, provided that
37 : : redistributed derivative works do not contain misleading author or
38 : : version information. Derivative works need not be licensed under
39 : : similar terms.
40 : :
41 : : C. Punycode sample implementation
42 : :
43 : : punycode-sample.c 2.0.0 (2004-Mar-21-Sun)
44 : : http://www.nicemice.net/idn/
45 : : Adam M. Costello
46 : : http://www.nicemice.net/amc/
47 : :
48 : : This is ANSI C code (C89) implementing Punycode 1.0.x.
49 : : */
50 : :
51 : : #include <config.h>
52 : :
53 : : #include "idn2.h" /* IDN2_OK, ... */
54 : :
55 : : /* Re-definitions to avoid modifying code below too much. */
56 : : #define punycode_uint uint32_t
57 : : #define punycode_success IDN2_OK
58 : : #define punycode_overflow IDN2_PUNYCODE_OVERFLOW
59 : : #define punycode_big_output IDN2_PUNYCODE_BIG_OUTPUT
60 : : #define punycode_bad_input IDN2_PUNYCODE_BAD_INPUT
61 : : #define punycode_encode _idn2_punycode_encode
62 : : #define punycode_decode _idn2_punycode_decode
63 : :
64 : : /**********************************************************/
65 : : /* Implementation (would normally go in its own .c file): */
66 : :
67 : : #include <string.h>
68 : :
69 : : #include "punycode.h"
70 : :
71 : : /*** Bootstring parameters for Punycode ***/
72 : :
73 : : enum { base = 36, tmin = 1, tmax = 26, skew = 38, damp = 700,
74 : : initial_bias = 72, initial_n = 0x80, delimiter = 0x2D };
75 : :
76 : : /* basic(cp) tests whether cp is a basic code point: */
77 : : #define basic(cp) ((punycode_uint)(cp) < 0x80)
78 : :
79 : : /* delim(cp) tests whether cp is a delimiter: */
80 : : #define delim(cp) ((cp) == delimiter)
81 : :
82 : : /* decode_digit(cp) returns the numeric value of a basic code */
83 : : /* point (for use in representing integers) in the range 0 to */
84 : : /* base-1, or base if cp does not represent a value. */
85 : :
86 : 455 : static punycode_uint decode_digit(punycode_uint cp)
87 : : {
88 [ + + ][ - + ]: 455 : return cp - 48 < 10 ? cp - 22 : cp - 65 < 26 ? cp - 65 :
[ + - ]
89 : 315 : cp - 97 < 26 ? cp - 97 : base;
90 : : }
91 : :
92 : : /* encode_digit(d,flag) returns the basic code point whose value */
93 : : /* (when used for representing integers) is d, which needs to be in */
94 : : /* the range 0 to base-1. The lowercase form is used unless flag is */
95 : : /* nonzero, in which case the uppercase form is used. The behavior */
96 : : /* is undefined if flag is nonzero and digit d has no uppercase form. */
97 : :
98 : 3551 : static char encode_digit(punycode_uint d, int flag)
99 : : {
100 [ + + ][ - + ]: 3551 : return d + 22 + 75 * (d < 26) - ((flag != 0) << 5);
101 : : /* 0..25 map to ASCII a..z or A..Z */
102 : : /* 26..35 map to ASCII 0..9 */
103 : : }
104 : :
105 : : /* flagged(bcp) tests whether a basic code point is flagged */
106 : : /* (uppercase). The behavior is undefined if bcp is not a */
107 : : /* basic code point. */
108 : :
109 : : #define flagged(bcp) ((punycode_uint)(bcp) - 65 < 26)
110 : :
111 : : /* encode_basic(bcp,flag) forces a basic code point to lowercase */
112 : : /* if flag is zero, uppercase if flag is nonzero, and returns */
113 : : /* the resulting code point. The code point is unchanged if it */
114 : : /* is caseless. The behavior is undefined if bcp is not a basic */
115 : : /* code point. */
116 : :
117 : 0 : static char encode_basic(punycode_uint bcp, int flag)
118 : : {
119 [ # # ]: 0 : bcp -= (bcp - 97 < 26) << 5;
120 [ # # ][ # # ]: 0 : return bcp + ((!flag && (bcp - 65 < 26)) << 5);
121 : : }
122 : :
123 : : /*** Platform-specific constants ***/
124 : :
125 : : /* maxint is the maximum value of a punycode_uint variable: */
126 : : static const punycode_uint maxint = -1;
127 : : /* Because maxint is unsigned, -1 becomes the maximum value. */
128 : :
129 : : /*** Bias adaptation function ***/
130 : :
131 : 2116 : static punycode_uint adapt(
132 : : punycode_uint delta, punycode_uint numpoints, int firsttime )
133 : : {
134 : : punycode_uint k;
135 : :
136 [ + + ]: 2116 : delta = firsttime ? delta / damp : delta >> 1;
137 : : /* delta >> 1 is a faster way of doing delta / 2 */
138 : 2116 : delta += delta / numpoints;
139 : :
140 [ + + ]: 2343 : for (k = 0; delta > ((base - tmin) * tmax) / 2; k += base) {
141 : 227 : delta /= base - tmin;
142 : : }
143 : :
144 : 2116 : return k + (base - tmin + 1) * delta / (delta + skew);
145 : : }
146 : :
147 : : /*** Main encode function ***/
148 : :
149 : 383 : int punycode_encode(
150 : : size_t input_length_orig,
151 : : const punycode_uint input[],
152 : : const unsigned char case_flags[],
153 : : size_t *output_length,
154 : : char output[] )
155 : : {
156 : : punycode_uint input_length, n, delta, h, b, bias, j, m, q, k, t;
157 : : size_t out, max_out;
158 : :
159 : : /* The Punycode spec assumes that the input length is the same type */
160 : : /* of integer as a code point, so we need to convert the size_t to */
161 : : /* a punycode_uint, which could overflow. */
162 : :
163 [ - + ]: 383 : if (input_length_orig > maxint) return punycode_overflow;
164 : 383 : input_length = (punycode_uint) input_length_orig;
165 : :
166 : : /* Initialize the state: */
167 : :
168 : 383 : n = initial_n;
169 : 383 : delta = 0;
170 : 383 : out = 0;
171 : 383 : max_out = *output_length;
172 : 383 : bias = initial_bias;
173 : :
174 : : /* Handle the basic code points: */
175 : :
176 [ + + ]: 3253 : for (j = 0; j < input_length; ++j) {
177 [ + + ]: 2870 : if (basic(input[j])) {
178 [ - + ]: 969 : if (max_out - out < 2) return punycode_big_output;
179 [ - + ]: 969 : output[out++] = case_flags ?
180 : 0 : encode_basic(input[j], case_flags[j]) : (char) input[j];
181 : : }
182 : : /* else if (input[j] < n) return punycode_bad_input; */
183 : : /* (not needed for Punycode with unsigned code points) */
184 : : }
185 : :
186 : 383 : h = b = (punycode_uint) out;
187 : : /* cannot overflow because out <= input_length <= maxint */
188 : :
189 : : /* h is the number of code points that have been handled, b is the */
190 : : /* number of basic code points, and out is the number of ASCII code */
191 : : /* points that have been output. */
192 : :
193 [ + + ]: 383 : if (b > 0) output[out++] = delimiter;
194 : :
195 : : /* Main encoding loop: */
196 : :
197 [ + + ]: 1821 : while (h < input_length) {
198 : : /* All non-basic code points < n have been */
199 : : /* handled already. Find the next larger one: */
200 : :
201 [ + + ]: 21918 : for (m = maxint, j = 0; j < input_length; ++j) {
202 : : /* if (basic(input[j])) continue; */
203 : : /* (not needed for Punycode) */
204 [ + + ][ + + ]: 20476 : if (input[j] >= n && input[j] < m) m = input[j];
205 : : }
206 : :
207 : : /* Increase delta enough to advance the decoder's */
208 : : /* <n,i> state to <m,0>, but guard against overflow: */
209 : :
210 [ - + ]: 1442 : if (m - n > (maxint - delta) / (h + 1)) return punycode_overflow;
211 : 1442 : delta += (m - n) * (h + 1);
212 : 1442 : n = m;
213 : :
214 [ + + ]: 21730 : for (j = 0; j < input_length; ++j) {
215 : : /* Punycode does not need to check whether input[j] is basic: */
216 [ + + ]: 20292 : if (input[j] < n /* || basic(input[j]) */ ) {
217 [ - + ]: 10773 : if (++delta == 0) return punycode_overflow;
218 : : }
219 : :
220 [ + + ]: 20292 : if (input[j] == n) {
221 : : /* Represent delta as a generalized variable-length integer: */
222 : :
223 : 1901 : for (q = delta, k = base; ; k += base) {
224 [ + + ]: 3555 : if (out >= max_out) return punycode_big_output;
225 [ + + ][ + + ]: 3551 : t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */
226 : 2730 : k >= bias + tmax ? tmax : k - bias;
227 [ + + ]: 3551 : if (q < t) break;
228 : 1654 : output[out++] = encode_digit(t + (q - t) % (base - t), 0);
229 : 1654 : q = (q - t) / (base - t);
230 : 1654 : }
231 : :
232 [ - + ][ # # ]: 1897 : output[out++] = encode_digit(q, case_flags && case_flags[j]);
233 : 1897 : bias = adapt(delta, h + 1, h == b);
234 : 1897 : delta = 0;
235 : 1897 : ++h;
236 : : }
237 : : }
238 : :
239 : 1438 : ++delta, ++n;
240 : : }
241 : :
242 : 379 : *output_length = out;
243 : 383 : return punycode_success;
244 : : }
245 : :
246 : : /*** Main decode function ***/
247 : :
248 : 21 : int punycode_decode(
249 : : size_t input_length,
250 : : const char input[],
251 : : size_t *output_length,
252 : : punycode_uint output[],
253 : : unsigned char case_flags[] )
254 : : {
255 : : punycode_uint n, out, i, max_out, bias, oldi, w, k, digit, t;
256 : : size_t b, j, in;
257 : :
258 : : /* Initialize the state: */
259 : :
260 : 21 : n = initial_n;
261 : 21 : out = i = 0;
262 [ + - ]: 21 : max_out = *output_length > maxint ? maxint
263 : 21 : : (punycode_uint) *output_length;
264 : 21 : bias = initial_bias;
265 : :
266 : : /* Handle the basic code points: Let b be the number of input code */
267 : : /* points before the last delimiter, or 0 if there is none, then */
268 : : /* copy the first b code points to the output. */
269 : :
270 [ + + ][ + + ]: 640 : for (b = j = 0; j < input_length; ++j) if (delim(input[j])) b = j;
271 [ - + ]: 21 : if (b > max_out) return punycode_big_output;
272 : :
273 [ + + ]: 173 : for (j = 0; j < b; ++j) {
274 [ - + ]: 152 : if (case_flags) case_flags[out] = flagged(input[j]);
275 [ - + ]: 152 : if (!basic(input[j])) return punycode_bad_input;
276 : 152 : output[out++] = input[j];
277 : : }
278 : :
279 : : /* Main decoding loop: Start just after the last delimiter if any */
280 : : /* basic code points were copied; start at the beginning otherwise. */
281 : :
282 [ + + ][ + + ]: 240 : for (in = b > 0 ? b + 1 : 0; in < input_length; ++out) {
283 : :
284 : : /* in is the index of the next ASCII code point to be consumed, */
285 : : /* and out is the number of code points in the output array. */
286 : :
287 : : /* Decode a generalized variable-length integer into delta, */
288 : : /* which gets added to i. The overflow checking is easier */
289 : : /* if we increase i as we go, then subtract off its starting */
290 : : /* value at the end to obtain delta. */
291 : :
292 : 219 : for (oldi = i, w = 1, k = base; ; k += base) {
293 [ - + ]: 455 : if (in >= input_length) return punycode_bad_input;
294 : 455 : digit = decode_digit(input[in++]);
295 [ - + ]: 455 : if (digit >= base) return punycode_bad_input;
296 [ - + ]: 455 : if (digit > (maxint - i) / w) return punycode_overflow;
297 : 455 : i += digit * w;
298 [ + + ][ + + ]: 455 : t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */
299 : 373 : k >= bias + tmax ? tmax : k - bias;
300 [ + + ]: 455 : if (digit < t) break;
301 [ - + ]: 236 : if (w > maxint / (base - t)) return punycode_overflow;
302 : 236 : w *= (base - t);
303 : 236 : }
304 : :
305 : 219 : bias = adapt(i - oldi, out + 1, oldi == 0);
306 : :
307 : : /* i was supposed to wrap around from out+1 to 0, */
308 : : /* incrementing n each time, so we'll fix that now: */
309 : :
310 [ - + ]: 219 : if (i / (out + 1) > maxint - n) return punycode_overflow;
311 : 219 : n += i / (out + 1);
312 : 219 : i %= (out + 1);
313 : :
314 : : /* Insert n at position i of the output: */
315 : :
316 : : /* not needed for Punycode: */
317 : : /* if (basic(n)) return punycode_bad_input; */
318 [ - + ]: 219 : if (out >= max_out) return punycode_big_output;
319 : :
320 [ - + ]: 219 : if (case_flags) {
321 : 0 : memmove(case_flags + i + 1, case_flags + i, out - i);
322 : : /* Case of last ASCII code point determines case flag: */
323 : 0 : case_flags[i] = flagged(input[in - 1]);
324 : : }
325 : :
326 : 219 : memmove(output + i + 1, output + i, (out - i) * sizeof *output);
327 : 219 : output[i++] = n;
328 : : }
329 : :
330 : 21 : *output_length = (size_t) out;
331 : : /* cannot overflow because out <= old value of *output_length */
332 : 21 : return punycode_success;
333 : : }
|
