5e211af6d99dce676351e109d0d30637c6bc4c1c
[openssl.git] / crypto / punycode.c
1 /*
2  * Copyright 2019-2020 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <stddef.h>
11 #include <string.h>
12 #include <stdio.h>
13 #include <openssl/e_os2.h>
14 #include "crypto/punycode.h"
15
16 static const unsigned int base = 36;
17 static const unsigned int tmin = 1;
18 static const unsigned int tmax = 26;
19 static const unsigned int skew = 38;
20 static const unsigned int damp = 700;
21 static const unsigned int initial_bias = 72;
22 static const unsigned int initial_n = 0x80;
23 static const unsigned int maxint = 0xFFFFFFFF;
24 static const char delimiter = '-';
25
26 #define LABEL_BUF_SIZE 512
27
28 /*-
29  * Pseudocode:
30  *
31  * function adapt(delta,numpoints,firsttime):
32  *  if firsttime then let delta = delta div damp
33  *  else let delta = delta div 2
34  *  let delta = delta + (delta div numpoints)
35  *  let k = 0
36  *  while delta > ((base - tmin) * tmax) div 2 do begin
37  *    let delta = delta div (base - tmin)
38  *    let k = k + base
39  *  end
40  *  return k + (((base - tmin + 1) * delta) div (delta + skew))
41  */
42
43 static int adapt(unsigned int delta, unsigned int numpoints,
44                  unsigned int firsttime)
45 {
46     unsigned int k = 0;
47
48     delta = (firsttime) ? delta / damp : delta / 2;
49     delta = delta + delta / numpoints;
50
51     while (delta > ((base - tmin) * tmax) / 2) {
52         delta = delta / (base - tmin);
53         k = k + base;
54     }
55
56     return k + (((base - tmin + 1) * delta) / (delta + skew));
57 }
58
59 static ossl_inline int is_basic(unsigned int a)
60 {
61     return (a < 0x80) ? 1 : 0;
62 }
63
64 /*-
65  * code points    digit-values
66  * ------------   ----------------------
67  * 41..5A (A-Z) =  0 to 25, respectively
68  * 61..7A (a-z) =  0 to 25, respectively
69  * 30..39 (0-9) = 26 to 35, respectively
70  */
71 static ossl_inline int digit_decoded(const unsigned char a)
72 {
73     if (a >= 0x41 && a <= 0x5A)
74         return a - 0x41;
75
76     if (a >= 0x61 && a <= 0x7A)
77         return a - 0x61;
78
79     if (a >= 0x30 && a <= 0x39)
80         return a - 0x30 + 26;
81
82     return -1;
83 }
84
85 /*-
86  * Pseudocode:
87  *
88  * function ossl_punycode_decode
89  *  let n = initial_n
90  *  let i = 0
91  *  let bias = initial_bias
92  *  let output = an empty string indexed from 0
93  *  consume all code points before the last delimiter (if there is one)
94  *    and copy them to output, fail on any non-basic code point
95  *  if more than zero code points were consumed then consume one more
96  *    (which will be the last delimiter)
97  *  while the input is not exhausted do begin
98  *    let oldi = i
99  *    let w = 1
100  *    for k = base to infinity in steps of base do begin
101  *      consume a code point, or fail if there was none to consume
102  *      let digit = the code point's digit-value, fail if it has none
103  *      let i = i + digit * w, fail on overflow
104  *      let t = tmin if k <= bias {+ tmin}, or
105  *              tmax if k >= bias + tmax, or k - bias otherwise
106  *      if digit < t then break
107  *      let w = w * (base - t), fail on overflow
108  *    end
109  *    let bias = adapt(i - oldi, length(output) + 1, test oldi is 0?)
110  *    let n = n + i div (length(output) + 1), fail on overflow
111  *    let i = i mod (length(output) + 1)
112  *    {if n is a basic code point then fail}
113  *    insert n into output at position i
114  *    increment i
115  *  end
116  */
117
118 int ossl_punycode_decode(const char *pEncoded, const size_t enc_len,
119                          unsigned int *pDecoded, unsigned int *pout_length)
120 {
121     unsigned int n = initial_n;
122     unsigned int i = 0;
123     unsigned int bias = initial_bias;
124     size_t processed_in = 0, written_out = 0;
125     unsigned int max_out = *pout_length;
126
127     unsigned int basic_count = 0;
128     unsigned int loop;
129
130     for (loop = 0; loop < enc_len; loop++) {
131         if (pEncoded[loop] == delimiter)
132             basic_count = loop;
133     }
134
135     if (basic_count > 0) {
136         if (basic_count > max_out)
137             return 0;
138
139         for (loop = 0; loop < basic_count; loop++) {
140             if (is_basic(pEncoded[loop]) == 0)
141                 return 0;
142
143             pDecoded[loop] = pEncoded[loop];
144             written_out++;
145         }
146         processed_in = basic_count + 1;
147     }
148
149     for (loop = processed_in; loop < enc_len;) {
150         unsigned int oldi = i;
151         unsigned int w = 1;
152         unsigned int k, t;
153         int digit;
154
155         for (k = base;; k += base) {
156             if (loop >= enc_len)
157                 return 0;
158
159             digit = digit_decoded(pEncoded[loop]);
160             loop++;
161
162             if (digit < 0)
163                 return 0;
164             if ((unsigned int)digit > (maxint - i) / w)
165                 return 0;
166
167             i = i + digit * w;
168             t = (k <= bias) ? tmin : (k >= bias + tmax) ? tmax : k - bias;
169
170             if ((unsigned int)digit < t)
171                 break;
172
173             if (w > maxint / (base - t))
174                 return 0;
175             w = w * (base - t);
176         }
177
178         bias = adapt(i - oldi, written_out + 1, (oldi == 0));
179         if (i / (written_out + 1) > maxint - n)
180             return 0;
181         n = n + i / (written_out + 1);
182         i %= (written_out + 1);
183
184         if (written_out >= max_out)
185             return 0;
186
187         memmove(pDecoded + i + 1, pDecoded + i,
188                 (written_out - i) * sizeof *pDecoded);
189         pDecoded[i] = n;
190         i++;
191         written_out++;
192     }
193
194     *pout_length = written_out;
195     return 1;
196 }
197
198 /*
199  * Encode a code point using UTF-8
200  * return number of bytes on success, 0 on failure
201  * (also produces U+FFFD, which uses 3 bytes on failure)
202  */
203 static int codepoint2utf8(unsigned char *out, unsigned long utf)
204 {
205     if (utf <= 0x7F) {
206         /* Plain ASCII */
207         out[0] = (unsigned char)utf;
208         out[1] = 0;
209         return 1;
210     } else if (utf <= 0x07FF) {
211         /* 2-byte unicode */
212         out[0] = (unsigned char)(((utf >> 6) & 0x1F) | 0xC0);
213         out[1] = (unsigned char)(((utf >> 0) & 0x3F) | 0x80);
214         out[2] = 0;
215         return 2;
216     } else if (utf <= 0xFFFF) {
217         /* 3-byte unicode */
218         out[0] = (unsigned char)(((utf >> 12) & 0x0F) | 0xE0);
219         out[1] = (unsigned char)(((utf >> 6) & 0x3F) | 0x80);
220         out[2] = (unsigned char)(((utf >> 0) & 0x3F) | 0x80);
221         out[3] = 0;
222         return 3;
223     } else if (utf <= 0x10FFFF) {
224         /* 4-byte unicode */
225         out[0] = (unsigned char)(((utf >> 18) & 0x07) | 0xF0);
226         out[1] = (unsigned char)(((utf >> 12) & 0x3F) | 0x80);
227         out[2] = (unsigned char)(((utf >> 6) & 0x3F) | 0x80);
228         out[3] = (unsigned char)(((utf >> 0) & 0x3F) | 0x80);
229         out[4] = 0;
230         return 4;
231     } else {
232         /* error - use replacement character */
233         out[0] = (unsigned char)0xEF;
234         out[1] = (unsigned char)0xBF;
235         out[2] = (unsigned char)0xBD;
236         out[3] = 0;
237         return 0;
238     }
239 }
240
241 /*-
242  * Return values:
243  * 1 - ok, *outlen contains valid buf length
244  * 0 - ok but buf was too short, *outlen contains valid buf length
245  * -1 - bad string passed
246  */
247
248 int ossl_a2ulabel(const char *in, char *out, size_t *outlen)
249 {
250     /*-
251      * Domain name has some parts consisting of ASCII chars joined with dot.
252      * If a part is shorter than 5 chars, it becomes U-label as is.
253      * If it does not start with xn--,    it becomes U-label as is.
254      * Otherwise we try to decode it.
255      */
256     char *outptr = out;
257     const char *inptr = in;
258     size_t size = 0;
259     int result = 1;
260
261     unsigned int buf[LABEL_BUF_SIZE];      /* It's a hostname */
262     if (out == NULL)
263         result = 0;
264
265     while (1) {
266         char *tmpptr = strchr(inptr, '.');
267         size_t delta = (tmpptr) ? (size_t)(tmpptr - inptr) : strlen(inptr);
268
269         if (strncmp(inptr, "xn--", 4) != 0) {
270             size += delta + 1;
271
272             if (size >= *outlen - 1)
273                 result = 0;
274
275             if (result > 0) {
276                 memcpy(outptr, inptr, delta + 1);
277                 outptr += delta + 1;
278             }
279         } else {
280             unsigned int bufsize = LABEL_BUF_SIZE;
281             unsigned int i;
282
283             if (ossl_punycode_decode(inptr + 4, delta - 4, buf, &bufsize) <= 0)
284                 return -1;
285
286             for (i = 0; i < bufsize; i++) {
287                 unsigned char seed[6];
288                 size_t utfsize = codepoint2utf8(seed, buf[i]);
289                 if (utfsize == 0)
290                     return -1;
291
292                 size += utfsize;
293                 if (size >= *outlen - 1)
294                     result = 0;
295
296                 if (result > 0) {
297                     memcpy(outptr, seed, utfsize);
298                     outptr += utfsize;
299                 }
300             }
301
302             if (tmpptr != NULL) {
303                 *outptr = '.';
304                 outptr++;
305                 size++;
306                 if (size >= *outlen - 1)
307                     result = 0;
308             }
309         }
310
311         if (tmpptr == NULL)
312             break;
313
314         inptr = tmpptr + 1;
315     }
316
317     return result;
318 }
319
320 /*-
321  * a MUST be A-label
322  * u MUST be U-label
323  * Returns 0 if compared values are equal
324  * 1 if not
325  * -1 in case of errors
326  */
327
328 int ossl_a2ucompare(const char *a, const char *u)
329 {
330     char a_ulabel[LABEL_BUF_SIZE];
331     size_t a_size = sizeof(a_ulabel);
332
333     if (ossl_a2ulabel(a, a_ulabel, &a_size) <= 0) {
334         return -1;
335     }
336
337     return (strcmp(a_ulabel, u) == 0) ? 0 : 1;
338 }