The Tor Browser / file comparison
comparison: netwerk/dns/punycode.c
netwerk/dns/punycode.c
- changeset 1
- ca08bd8f51b2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:7b3a983a3e07 |
|---|---|
| 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 { base = 36, tmin = 1, tmax = 26, skew = 38, damp = 700, | |
| 33 initial_bias = 72, initial_n = 0x80, delimiter = 0x2D }; | |
| 34 | |
| 35 /* basic(cp) tests whether cp is a basic code point: */ | |
| 36 #define basic(cp) ((punycode_uint)(cp) < 0x80) | |
| 37 | |
| 38 /* delim(cp) tests whether cp is a delimiter: */ | |
| 39 #define delim(cp) ((cp) == delimiter) | |
| 40 | |
| 41 /* decode_digit(cp) returns the numeric value of a basic code */ | |
| 42 /* point (for use in representing integers) in the range 0 to */ | |
| 43 /* base-1, or base if cp is does not represent a value. */ | |
| 44 | |
| 45 static punycode_uint decode_digit(punycode_uint cp) | |
| 46 { | |
| 47 return cp - 48 < 10 ? cp - 22 : cp - 65 < 26 ? cp - 65 : | |
| 48 cp - 97 < 26 ? cp - 97 : base; | |
| 49 } | |
| 50 | |
| 51 /* encode_digit(d,flag) returns the basic code point whose value */ | |
| 52 /* (when used for representing integers) is d, which needs to be in */ | |
| 53 /* the range 0 to base-1. The lowercase form is used unless flag is */ | |
| 54 /* nonzero, in which case the uppercase form is used. The behavior */ | |
| 55 /* is undefined if flag is nonzero and digit d has no uppercase form. */ | |
| 56 | |
| 57 static char encode_digit(punycode_uint d, int flag) | |
| 58 { | |
| 59 return d + 22 + 75 * (d < 26) - ((flag != 0) << 5); | |
| 60 /* 0..25 map to ASCII a..z or A..Z */ | |
| 61 /* 26..35 map to ASCII 0..9 */ | |
| 62 } | |
| 63 | |
| 64 /* flagged(bcp) tests whether a basic code point is flagged */ | |
| 65 /* (uppercase). The behavior is undefined if bcp is not a */ | |
| 66 /* basic code point. */ | |
| 67 | |
| 68 #define flagged(bcp) ((punycode_uint)(bcp) - 65 < 26) | |
| 69 | |
| 70 /* encode_basic(bcp,flag) forces a basic code point to lowercase */ | |
| 71 /* if flag is zero, uppercase if flag is nonzero, and returns */ | |
| 72 /* the resulting code point. The code point is unchanged if it */ | |
| 73 /* is caseless. The behavior is undefined if bcp is not a basic */ | |
| 74 /* code point. */ | |
| 75 | |
| 76 static char encode_basic(punycode_uint bcp, int flag) | |
| 77 { | |
| 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( | |
| 91 punycode_uint delta, punycode_uint numpoints, int firsttime ) | |
| 92 { | |
| 93 punycode_uint k; | |
| 94 | |
| 95 delta = firsttime ? delta / damp : delta >> 1; | |
| 96 /* delta >> 1 is a faster way of doing delta / 2 */ | |
| 97 delta += delta / numpoints; | |
| 98 | |
| 99 for (k = 0; delta > ((base - tmin) * tmax) / 2; k += base) { | |
| 100 delta /= base - tmin; | |
| 101 } | |
| 102 | |
| 103 return k + (base - tmin + 1) * delta / (delta + skew); | |
| 104 } | |
| 105 | |
| 106 /*** Main encode function ***/ | |
| 107 | |
| 108 enum punycode_status punycode_encode( | |
| 109 punycode_uint input_length, | |
| 110 const punycode_uint input[], | |
| 111 const unsigned char case_flags[], | |
| 112 punycode_uint *output_length, | |
| 113 char output[] ) | |
| 114 { | |
| 115 punycode_uint n, delta, h, b, out, max_out, bias, j, m, q, k, t; | |
| 116 | |
| 117 /* Initialize the state: */ | |
| 118 | |
| 119 n = initial_n; | |
| 120 delta = out = 0; | |
| 121 max_out = *output_length; | |
| 122 bias = initial_bias; | |
| 123 | |
| 124 /* Handle the basic code points: */ | |
| 125 | |
| 126 for (j = 0; j < input_length; ++j) { | |
| 127 if (basic(input[j])) { | |
| 128 if (max_out - out < 2) return punycode_big_output; | |
| 129 output[out++] = | |
| 130 case_flags ? encode_basic(input[j], case_flags[j]) : (char)input[j]; | |
| 131 } | |
| 132 /* else if (input[j] < n) return punycode_bad_input; */ | |
| 133 /* (not needed for Punycode with unsigned code points) */ | |
| 134 } | |
| 135 | |
| 136 h = b = out; | |
| 137 | |
| 138 /* h is the number of code points that have been handled, b is the */ | |
| 139 /* number of basic code points, and out is the number of characters */ | |
| 140 /* that have been output. */ | |
| 141 | |
| 142 if (b > 0) output[out++] = delimiter; | |
| 143 | |
| 144 /* Main encoding loop: */ | |
| 145 | |
| 146 while (h < input_length) { | |
| 147 /* All non-basic code points < n have been */ | |
| 148 /* handled already. Find the next larger one: */ | |
| 149 | |
| 150 for (m = maxint, j = 0; j < input_length; ++j) { | |
| 151 /* if (basic(input[j])) continue; */ | |
| 152 /* (not needed for Punycode) */ | |
| 153 if (input[j] >= n && input[j] < m) m = input[j]; | |
| 154 } | |
| 155 | |
| 156 /* Increase delta enough to advance the decoder's */ | |
| 157 /* <n,i> state to <m,0>, but guard against overflow: */ | |
| 158 | |
| 159 if (m - n > (maxint - delta) / (h + 1)) return punycode_overflow; | |
| 160 delta += (m - n) * (h + 1); | |
| 161 n = m; | |
| 162 | |
| 163 for (j = 0; j < input_length; ++j) { | |
| 164 /* Punycode does not need to check whether input[j] is basic: */ | |
| 165 if (input[j] < n /* || basic(input[j]) */ ) { | |
| 166 if (++delta == 0) return punycode_overflow; | |
| 167 } | |
| 168 | |
| 169 if (input[j] == n) { | |
| 170 /* Represent delta as a generalized variable-length integer: */ | |
| 171 | |
| 172 for (q = delta, k = base; ; k += base) { | |
| 173 if (out >= max_out) return punycode_big_output; | |
| 174 t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */ | |
| 175 k >= bias + tmax ? tmax : k - bias; | |
| 176 if (q < t) break; | |
| 177 output[out++] = encode_digit(t + (q - t) % (base - t), 0); | |
| 178 q = (q - t) / (base - t); | |
| 179 } | |
| 180 | |
| 181 output[out++] = encode_digit(q, case_flags && case_flags[j]); | |
| 182 bias = adapt(delta, h + 1, h == b); | |
| 183 delta = 0; | |
| 184 ++h; | |
| 185 } | |
| 186 } | |
| 187 | |
| 188 ++delta, ++n; | |
| 189 } | |
| 190 | |
| 191 *output_length = out; | |
| 192 return punycode_success; | |
| 193 } | |
| 194 | |
| 195 /*** Main decode function ***/ | |
| 196 | |
| 197 enum punycode_status punycode_decode( | |
| 198 punycode_uint input_length, | |
| 199 const char input[], | |
| 200 punycode_uint *output_length, | |
| 201 punycode_uint output[], | |
| 202 unsigned char case_flags[] ) | |
| 203 { | |
| 204 punycode_uint n, out, i, max_out, bias, | |
| 205 b, j, in, oldi, w, k, digit, t; | |
| 206 | |
| 207 if (!input_length) { | |
| 208 return punycode_bad_input; | |
| 209 } | |
| 210 | |
| 211 /* Initialize the state: */ | |
| 212 | |
| 213 n = initial_n; | |
| 214 out = i = 0; | |
| 215 max_out = *output_length; | |
| 216 bias = initial_bias; | |
| 217 | |
| 218 /* Handle the basic code points: Let b be the number of input code */ | |
| 219 /* points before the last delimiter, or 0 if there is none, then */ | |
| 220 /* copy the first b code points to the output. */ | |
| 221 | |
| 222 for (b = 0, j = input_length - 1 ; j > 0; --j) { | |
| 223 if (delim(input[j])) { | |
| 224 b = j; | |
| 225 break; | |
| 226 } | |
| 227 } | |
| 228 if (b > max_out) return punycode_big_output; | |
| 229 | |
| 230 for (j = 0; j < b; ++j) { | |
| 231 if (case_flags) case_flags[out] = flagged(input[j]); | |
| 232 if (!basic(input[j])) return punycode_bad_input; | |
| 233 output[out++] = input[j]; | |
| 234 } | |
| 235 | |
| 236 /* Main decoding loop: Start just after the last delimiter if any */ | |
| 237 /* basic code points were copied; start at the beginning otherwise. */ | |
| 238 | |
| 239 for (in = b > 0 ? b + 1 : 0; in < input_length; ++out) { | |
| 240 | |
| 241 /* in is the index of the next character to be consumed, and */ | |
| 242 /* out is the number of code points in the output array. */ | |
| 243 | |
| 244 /* Decode a generalized variable-length integer into delta, */ | |
| 245 /* which gets added to i. The overflow checking is easier */ | |
| 246 /* if we increase i as we go, then subtract off its starting */ | |
| 247 /* value at the end to obtain delta. */ | |
| 248 | |
| 249 for (oldi = i, w = 1, k = base; ; k += base) { | |
| 250 if (in >= input_length) return punycode_bad_input; | |
| 251 digit = decode_digit(input[in++]); | |
| 252 if (digit >= base) return punycode_bad_input; | |
| 253 if (digit > (maxint - i) / w) return punycode_overflow; | |
| 254 i += digit * w; | |
| 255 t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */ | |
| 256 k >= bias + tmax ? tmax : k - bias; | |
| 257 if (digit < t) break; | |
| 258 if (w > maxint / (base - t)) return punycode_overflow; | |
| 259 w *= (base - t); | |
| 260 } | |
| 261 | |
| 262 bias = adapt(i - oldi, out + 1, oldi == 0); | |
| 263 | |
| 264 /* i was supposed to wrap around from out+1 to 0, */ | |
| 265 /* incrementing n each time, so we'll fix that now: */ | |
| 266 | |
| 267 if (i / (out + 1) > maxint - n) return punycode_overflow; | |
| 268 n += i / (out + 1); | |
| 269 i %= (out + 1); | |
| 270 | |
| 271 /* Insert n at position i of the output: */ | |
| 272 | |
| 273 /* not needed for Punycode: */ | |
| 274 /* if (decode_digit(n) <= base) return punycode_invalid_input; */ | |
| 275 if (out >= max_out) return punycode_big_output; | |
| 276 | |
| 277 if (case_flags) { | |
| 278 memmove(case_flags + i + 1, case_flags + i, out - i); | |
| 279 /* Case of last character determines uppercase flag: */ | |
| 280 case_flags[i] = flagged(input[in - 1]); | |
| 281 } | |
| 282 | |
| 283 memmove(output + i + 1, output + i, (out - i) * sizeof *output); | |
| 284 output[i++] = n; | |
| 285 } | |
| 286 | |
| 287 *output_length = out; | |
| 288 return punycode_success; | |
| 289 } |
