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