1/*
2 *******************************************************************************
3 *
4 *   Copyright (C) 2003-2005, International Business Machines
5 *   Corporation and others.  All Rights Reserved.
6 *
7 *******************************************************************************
8 *   file name:  punyref.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/*
18Disclaimer 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
30punycode.c 0.4.0 (2001-Nov-17-Sat)
31http://www.cs.berkeley.edu/~amc/idn/
32Adam M. Costello
33http://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
49enum { 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
58U_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
63static 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
75static 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
94static 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: */
103static const punycode_uint maxint = (punycode_uint) (-1);
104/* Because maxint is unsigned, -1 becomes the maximum value. */
105
106/*** Bias adaptation function ***/
107
108static 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
126enum 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
215enum 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
300U_CDECL_END
301
302#endif /* #if !UCONFIG_NO_IDNA */
303