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