netwerk/dns/punycode.c

   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 }