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

Generated by: LCOV version 1.9