jars/icu4j-4_4_2-src/main/tests/core/src/com/ibm/icu/dev/test/stringprep/PunycodeReference.java

   1 /*\r
   2  *******************************************************************************\r
   3  * Copyright (C) 2003-2007, International Business Machines Corporation and    *\r
   4  * others. All Rights Reserved.                                                *\r
   5  *******************************************************************************\r
   6 */\r
   7 \r
   8 /*\r
   9  * \r
  10 Disclaimer and license\r
  11 \r
  12     Regarding this entire document or any portion of it (including\r
  13     the pseudocode and C code), the author makes no guarantees and\r
  14     is not responsible for any damage resulting from its use.  The\r
  15     author grants irrevocable permission to anyone to use, modify,\r
  16     and distribute it in any way that does not diminish the rights\r
  17     of anyone else to use, modify, and distribute it, provided that\r
  18     redistributed derivative works do not contain misleading author or\r
  19     version information.  Derivative works need not be licensed under\r
  20     similar terms.\r
  21 \r
  22 punycode.c 0.4.0 (2001-Nov-17-Sat)\r
  23 http://www.cs.berkeley.edu/~amc/idn/\r
  24 Adam M. Costello\r
  25 http://www.nicemice.net/amc/\r
  26 */\r
  27 \r
  28 package com.ibm.icu.dev.test.stringprep;\r
  29 import com.ibm.icu.text.StringPrepParseException;\r
  30 import com.ibm.icu.text.UCharacterIterator;\r
  31 import com.ibm.icu.text.UTF16;\r
  32 \r
  33 /**\r
  34  * The implementation is direct port of C code in the RFC\r
  35  */\r
  36 \r
  37 public final class PunycodeReference {\r
  38     /*** punycode status codes */\r
  39     public static final int punycode_success=0;\r
  40     public static final int punycode_bad_input=1;   /* Input is invalid.                       */\r
  41     public static final int punycode_big_output=2;  /* Output would exceed the space provided. */\r
  42     public static final int punycode_overflow =3;    /* Input needs wider integers to process.  */\r
  43     \r
  44     /*** Bootstring parameters for Punycode ***/\r
  45     private static final int base = 36;\r
  46     private static final int tmin = 1;\r
  47     private static final int tmax = 26;\r
  48     private static final int skew = 38;\r
  49     private static final int damp = 700;\r
  50     private static final int initial_bias = 72;\r
  51     private static final int initial_n = 0x80;\r
  52     private static final int delimiter = 0x2D;\r
  53     \r
  54     \r
  55 //    private static final long UNSIGNED_INT_MASK = 0xffffffffL;\r
  56     \r
  57     /* basic(cp) tests whether cp is a basic code point: */\r
  58     private static boolean basic(int cp){\r
  59         return (char)(cp) < 0x80;\r
  60     }\r
  61 \r
  62     /* delim(cp) tests whether cp is a delimiter: */\r
  63     private static boolean delim(int cp){\r
  64         return ((cp) == delimiter);\r
  65     }\r
  66 \r
  67     /* decode_digit(cp) returns the numeric value of a basic code */\r
  68     /* point (for use in representing integers) in the range 0 to */\r
  69     /* base-1, or base if cp is does not represent a value.       */\r
  70 \r
  71     private static int decode_digit(int cp)\r
  72     {\r
  73       return  cp - 48 < 10 ? cp - 22 :  cp - 65 < 26 ? cp - 65 :\r
  74               cp - 97 < 26 ? cp - 97 :  base;\r
  75     }\r
  76 \r
  77     /* encode_digit(d,flag) returns the basic code point whose value      */\r
  78     /* (when used for representing integers) is d, which needs to be in   */\r
  79     /* the range 0 to base-1.  The lowercase form is used unless flag is  */\r
  80     /* nonzero, in which case the uppercase form is used.  The behavior   */\r
  81     /* is undefined if flag is nonzero and digit d has no uppercase form. */\r
  82 \r
  83     private static char encode_digit(int d, int flag)\r
  84     {\r
  85       return (char) (d + 22 + (75 * ((d < 26) ? 1 : 0) - (((flag != 0) ? 1 :0) << 5)));\r
  86       /*  0..25 map to ASCII a..z or A..Z */\r
  87       /* 26..35 map to ASCII 0..9         */\r
  88     }\r
  89 \r
  90     /* flagged(bcp) tests whether a basic code point is flagged */\r
  91     /* (uppercase).  The behavior is undefined if bcp is not a  */\r
  92     /* basic code point.                                        */\r
  93 \r
  94     private static boolean flagged(int bcp){\r
  95          return ((bcp) - 65 < 26);\r
  96     }\r
  97 \r
  98     /* encode_basic(bcp,flag) forces a basic code point to lowercase */\r
  99     /* if flag is zero, uppercase if flag is nonzero, and returns    */\r
 100     /* the resulting code point.  The code point is unchanged if it  */\r
 101     /* is caseless.  The behavior is undefined if bcp is not a basic */\r
 102     /* code point.                                                   */\r
 103 \r
 104     private static char encode_basic(int bcp, int flag)\r
 105     {\r
 106       bcp -= (((bcp - 97) < 26) ? 1 :0 ) << 5;\r
 107       boolean mybcp = (bcp - 65 < 26);\r
 108       return (char) (bcp + (((flag==0) && mybcp ) ? 1 : 0 ) << 5);\r
 109     }\r
 110 \r
 111     /*** Platform-specific constants ***/\r
 112 \r
 113     /* maxint is the maximum value of a punycode_uint variable: */\r
 114     private static long maxint = 0xFFFFFFFFL;\r
 115     /* Because maxint is unsigned, -1 becomes the maximum value. */\r
 116 \r
 117     /*** Bias adaptation function ***/\r
 118 \r
 119     private static int adapt(int delta, int numpoints, boolean firsttime ){\r
 120       int k;\r
 121 \r
 122       delta = (firsttime==true) ? delta / damp : delta >> 1;\r
 123       /* delta >> 1 is a faster way of doing delta / 2 */\r
 124       delta += delta / numpoints;\r
 125 \r
 126       for (k = 0;  delta > ((base - tmin) * tmax) / 2;  k += base) {\r
 127         delta /= base - tmin;\r
 128       }\r
 129 \r
 130       return k + (base - tmin + 1) * delta / (delta + skew);\r
 131     }\r
 132 \r
 133     /*** Main encode function ***/\r
 134 \r
 135     public static final int encode(   int input_length,\r
 136                                       int input[],\r
 137                                       char[] case_flags,\r
 138                                       int[] output_length,\r
 139                                       char output[] ){\r
 140       int delta, h, b, out, max_out, bias, j, q, k, t;\r
 141       long m,n;\r
 142       /* Initialize the state: */\r
 143 \r
 144       n = initial_n;\r
 145       delta = out = 0;\r
 146       max_out = output_length[0];\r
 147       bias = initial_bias;\r
 148 \r
 149       /* Handle the basic code points: */\r
 150 \r
 151       for (j = 0;  j < input_length;  ++j) {\r
 152         if (basic(input[j])) {\r
 153           if (max_out - out < 2) return punycode_big_output;\r
 154           output[out++] = (char)\r
 155             (case_flags!=null ?  encode_basic(input[j], case_flags[j]) : input[j]);\r
 156         }\r
 157         /* else if (input[j] < n) return punycode_bad_input; */\r
 158         /* (not needed for Punycode with unsigned code points) */\r
 159       }\r
 160 \r
 161       h = b = out;\r
 162 \r
 163       /* h is the number of code points that have been handled, b is the  */\r
 164       /* number of basic code points, and out is the number of characters */\r
 165       /* that have been output.                                           */\r
 166 \r
 167       if (b > 0) output[out++] = delimiter;\r
 168 \r
 169       /* Main encoding loop: */\r
 170 \r
 171       while (h < input_length) {\r
 172         /* All non-basic code points < n have been     */\r
 173         /* handled already.  Find the next larger one: */\r
 174 \r
 175         for (m = maxint, j = 0;  j < input_length;  ++j) {\r
 176           /* if (basic(input[j])) continue; */\r
 177           /* (not needed for Punycode) */\r
 178           if (input[j] >= n && input[j] < m) m = input[j];\r
 179         }\r
 180 \r
 181         /* Increase delta enough to advance the decoder's    */\r
 182         /* <n,i> state to <m,0>, but guard against overflow: */\r
 183 \r
 184         if (m - n > (maxint - delta) / (h + 1)) return punycode_overflow;\r
 185         delta += (m - n) * (h + 1);\r
 186         n = m;\r
 187 \r
 188         for (j = 0;  j < input_length;  ++j) {\r
 189           /* Punycode does not need to check whether input[j] is basic: */\r
 190           if (input[j] < n /* || basic(input[j]) */ ) {\r
 191             if (++delta == 0) return punycode_overflow;\r
 192           }\r
 193 \r
 194           if (input[j] == n) {\r
 195             /* Represent delta as a generalized variable-length integer: */\r
 196 \r
 197             for (q = delta, k = base;  ;  k += base) {\r
 198               if (out >= max_out) return punycode_big_output;\r
 199               t = k <= bias /* + tmin */ ? tmin :     /* +tmin not needed */\r
 200                   k >= bias + tmax ? tmax : k - bias;\r
 201               if (q < t) break;\r
 202               output[out++] = encode_digit(t + (q - t) % (base - t), 0);\r
 203               q = (q - t) / (base - t);\r
 204             }\r
 205 \r
 206             output[out++] = encode_digit(q, (case_flags !=null) ? case_flags[j] : 0);\r
 207             bias = adapt(delta, h + 1, (h == b));\r
 208             delta = 0;\r
 209             ++h;\r
 210           }\r
 211         }\r
 212 \r
 213         ++delta;\r
 214         ++n;\r
 215       }\r
 216 \r
 217       output_length[0] = out;\r
 218       return punycode_success;\r
 219     }\r
 220     \r
 221     public static final StringBuffer encode(StringBuffer input,char[] case_flags)\r
 222                                throws StringPrepParseException{\r
 223         int[] in = new int[input.length()];\r
 224         int inLen = 0;\r
 225         int ch;\r
 226         StringBuffer result = new StringBuffer();\r
 227         UCharacterIterator iter = UCharacterIterator.getInstance(input);\r
 228         while((ch=iter.nextCodePoint())!= UCharacterIterator.DONE){\r
 229             in[inLen++]=ch;\r
 230         }\r
 231 \r
 232         int[] outLen =  new int[1];\r
 233         outLen[0] = input.length()*4;\r
 234         char[] output = new char[outLen[0]];\r
 235         int rc = punycode_success;\r
 236         for(;;){\r
 237             rc = encode(inLen,in,case_flags, outLen, output);\r
 238             if(rc==punycode_big_output){\r
 239                 outLen[0] = outLen[0]*4;\r
 240                 output = new char[outLen[0]];\r
 241                 // continue to convert\r
 242                 continue;\r
 243             }\r
 244             break;\r
 245         }\r
 246         if(rc==punycode_success){\r
 247             return result.append(output,0,outLen[0]);\r
 248         }\r
 249         getException(rc);\r
 250         return result;\r
 251     }\r
 252 \r
 253     private static void getException(int rc) \r
 254                    throws StringPrepParseException{\r
 255          switch(rc){\r
 256              case punycode_big_output:\r
 257                 throw new StringPrepParseException("The output capacity was not sufficient.",StringPrepParseException.BUFFER_OVERFLOW_ERROR);\r
 258              case punycode_bad_input:\r
 259                 throw new StringPrepParseException("Illegal char found in the input",StringPrepParseException.ILLEGAL_CHAR_FOUND);\r
 260              case punycode_overflow:\r
 261                 throw new StringPrepParseException("Invalid char found in the input",StringPrepParseException.INVALID_CHAR_FOUND);   \r
 262          }\r
 263         \r
 264     }\r
 265     private static final int MAX_BUFFER_SIZE = 100;\r
 266     \r
 267     public static final StringBuffer decode(StringBuffer input,char[] case_flags)\r
 268                                throws StringPrepParseException{\r
 269         char[] in = input.toString().toCharArray();\r
 270         int[] outLen = new int[1];\r
 271         outLen[0] = MAX_BUFFER_SIZE;\r
 272         int[] output = new int[outLen[0]];\r
 273         int rc = punycode_success;\r
 274         StringBuffer result = new StringBuffer();\r
 275         for(;;){\r
 276             rc = decode(input.length(),in, outLen, output,case_flags);\r
 277             if(rc==punycode_big_output){\r
 278                 outLen[0] = output.length * 4;\r
 279                 output = new int[outLen[0]];\r
 280                 continue;\r
 281             }\r
 282             break;\r
 283         }\r
 284         if(rc==punycode_success){\r
 285             for(int i=0; i < outLen[0]; i++ ){\r
 286                 UTF16.append(result,output[i]);\r
 287             }\r
 288         }else{\r
 289             getException(rc);\r
 290         }\r
 291         return result;\r
 292     }\r
 293     \r
 294     /*** Main decode function ***/\r
 295     public static final int decode(int input_length,\r
 296                              char[] input,\r
 297                              int[] output_length,\r
 298                              int[] output,\r
 299                              char[] case_flags ){\r
 300       int n, out, i, max_out, bias,\r
 301                      b, j, in, oldi, w, k, digit, t;\r
 302 \r
 303       /* Initialize the state: */\r
 304 \r
 305       n = initial_n;\r
 306       out = i = 0;\r
 307       max_out = output_length[0];\r
 308       bias = initial_bias;\r
 309 \r
 310       /* Handle the basic code points:  Let b be the number of input code */\r
 311       /* points before the last delimiter, or 0 if there is none, then    */\r
 312       /* copy the first b code points to the output.                      */\r
 313 \r
 314       for (b = j = 0;  j < input_length;  ++j){\r
 315            if (delim(input[j])==true){\r
 316                 b = j;\r
 317            }\r
 318       }\r
 319       if (b > max_out) return punycode_big_output;\r
 320 \r
 321       for (j = 0;  j < b;  ++j) {\r
 322         if (case_flags != null) case_flags[out] = (char)(flagged(input[j]) ? 1 : 0);\r
 323         if (!basic(input[j])) return punycode_bad_input;\r
 324         output[out++] = input[j];\r
 325       }\r
 326 \r
 327       /* Main decoding loop:  Start just after the last delimiter if any  */\r
 328       /* basic code points were copied; start at the beginning otherwise. */\r
 329 \r
 330       for (in = b > 0 ? b + 1 : 0;  in < input_length;  ++out) {\r
 331 \r
 332         /* in is the index of the next character to be consumed, and */\r
 333         /* out is the number of code points in the output array.     */\r
 334 \r
 335         /* Decode a generalized variable-length integer into delta,  */\r
 336         /* which gets added to i.  The overflow checking is easier   */\r
 337         /* if we increase i as we go, then subtract off its starting */\r
 338         /* value at the end to obtain delta.                         */\r
 339 \r
 340         for (oldi = i, w = 1, k = base;  ;  k += base) {\r
 341           if (in >= input_length) return punycode_bad_input;\r
 342           digit = decode_digit(input[in++]);\r
 343           if (digit >= base) return punycode_bad_input;\r
 344           if (digit > (maxint - i) / w) return punycode_overflow;\r
 345           i += digit * w;\r
 346           t = (k <= bias) /* + tmin */ ? tmin :     /* +tmin not needed */\r
 347               (k >= (bias + tmax)) ? tmax : k - bias;\r
 348           if (digit < t) break;\r
 349           if (w > maxint / (base - t)) return punycode_overflow;\r
 350           w *= (base - t);\r
 351         }\r
 352 \r
 353         bias = adapt(i - oldi, out + 1, (oldi == 0));\r
 354 \r
 355         /* i was supposed to wrap around from out+1 to 0,   */\r
 356         /* incrementing n each time, so we'll fix that now: */\r
 357 \r
 358         if (i / (out + 1) > maxint - n) return punycode_overflow;\r
 359         n += i / (out + 1);\r
 360         i %= (out + 1);\r
 361 \r
 362         /* Insert n at position i of the output: */\r
 363 \r
 364         /* not needed for Punycode: */\r
 365         /* if (decode_digit(n) <= base) return punycode_invalid_input; */\r
 366         if (out >= max_out) return punycode_big_output;\r
 367 \r
 368         if (case_flags != null) {\r
 369           System.arraycopy(case_flags, i, case_flags,  i + 1, out - i);\r
 370           /* Case of last character determines uppercase flag: */\r
 371           case_flags[i] = (char)(flagged(input[in - 1]) ? 0 :1);\r
 372         }\r
 373 \r
 374         System.arraycopy(output, i, output, i + 1,  (out - i));\r
 375         output[i++] = n;\r
 376       }\r
 377 \r
 378       output_length[0] = out;\r
 379       return punycode_success;\r
 380     }\r
 381 \r
 382 }\r