icuSources/test/intltest/punyref.c

   1 /*
   2  *******************************************************************************
   3  *
   4  *   Copyright (C) 2003, International Business Machines
   5  *   Corporation and others.  All Rights Reserved.
   6  *
   7  *******************************************************************************
   8  *   file name:  nameprep.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 */