punycode.c

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