LCOV - code coverage report
Current view: top level - home/jas/src/libidn2 - punycode.c (source / functions) Hit Total Coverage
Test: libidn2 Lines: 86 91 94.5 %
Date: 2013-07-24 Functions: 5 6 83.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 72 100 72.0 %

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

Generated by: LCOV version 1.9