includes/normal/UtfNormal.php

   1 <?php
   2 # Copyright (C) 2004 Brion Vibber <brion@pobox.com>
   3 # http://www.mediawiki.org/
   4 #
   5 # This program is free software; you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation; either version 2 of the License, or
   8 # (at your option) any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful,
  11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13 # GNU General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU General Public License along
  16 # with this program; if not, write to the Free Software Foundation, Inc.,
  17 # 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 # http://www.gnu.org/copyleft/gpl.html
  19
  20 # Unicode normalization routines for working with UTF-8 strings.
  21 # Currently assumes that input strings are valid UTF-8!
  22 #
  23 # Not as fast as I'd like, but should be usable for most purposes.
  24 # UtfNormal::toNFC() will bail early if given ASCII text or text
  25 # it can quickly deterimine is already normalized.
  26 #
  27 # All functions can be called static.
  28 #
  29 # See description of forms at http://www.unicode.org/reports/tr15/
  30
  31 require_once 'UtfNormalUtil.php';
  32 require_once 'UtfNormalData.inc';
  33
  34 define( 'UNICODE_HANGUL_FIRST', 0xac00 );
  35 define( 'UNICODE_HANGUL_LAST',  0xd7a3 );
  36
  37 define( 'UNICODE_HANGUL_LBASE', 0x1100 );
  38 define( 'UNICODE_HANGUL_VBASE', 0x1161 );
  39 define( 'UNICODE_HANGUL_TBASE', 0x11a7 );
  40
  41 define( 'UNICODE_HANGUL_LCOUNT', 19 );
  42 define( 'UNICODE_HANGUL_VCOUNT', 21 );
  43 define( 'UNICODE_HANGUL_TCOUNT', 28 );
  44 define( 'UNICODE_HANGUL_NCOUNT', UNICODE_HANGUL_VCOUNT * UNICODE_HANGUL_TCOUNT );
  45
  46 define( 'UNICODE_HANGUL_LEND', UNICODE_HANGUL_LBASE + UNICODE_HANGUL_LCOUNT - 1 );
  47 define( 'UNICODE_HANGUL_VEND', UNICODE_HANGUL_VBASE + UNICODE_HANGUL_VCOUNT - 1 );
  48 define( 'UNICODE_HANGUL_TEND', UNICODE_HANGUL_TBASE + UNICODE_HANGUL_TCOUNT - 1 );
  49
  50 define( 'UTF8_HANGUL_FIRST', codepointToUtf8( UNICODE_HANGUL_FIRST ) );
  51 define( 'UTF8_HANGUL_LAST', codepointToUtf8( UNICODE_HANGUL_LAST ) );
  52
  53 define( 'UTF8_HANGUL_LBASE', codepointToUtf8( UNICODE_HANGUL_LBASE ) );
  54 define( 'UTF8_HANGUL_VBASE', codepointToUtf8( UNICODE_HANGUL_VBASE ) );
  55 define( 'UTF8_HANGUL_TBASE', codepointToUtf8( UNICODE_HANGUL_TBASE ) );
  56
  57 define( 'UTF8_HANGUL_LEND', codepointToUtf8( UNICODE_HANGUL_LEND ) );
  58 define( 'UTF8_HANGUL_VEND', codepointToUtf8( UNICODE_HANGUL_VEND ) );
  59 define( 'UTF8_HANGUL_TEND', codepointToUtf8( UNICODE_HANGUL_TEND ) );
  60
  61 class UtfNormal {
  62         # These functions try to skip the conversion if it won't be necessary.
  63         # An all ASCII string for instance doesn't need conversion.
  64         function toNFC( $string ) {
  65                 if( UtfNormal::quickIsNFC( $string ) )
  66                         return $string;
  67                 else
  68                         return UtfNormal::NFC( $string );
  69         }
  70
  71         function toNFD( $string ) {
  72                 if( preg_match( '/[\x80-\xff]/', $string ) )
  73                         return UtfNormal::NFD( $string );
  74                 else
  75                         return $string;
  76         }
  77
  78         function toNFKC( $string ) {
  79                 if( preg_match( '/[\x80-\xff]/', $string ) )
  80                         return UtfNormal::NFKC( $string );
  81                 else
  82                         return $string;
  83         }
  84
  85         function toNFKD( $string ) {
  86                 if( preg_match( '/[\x80-\xff]/', $string ) )
  87                         return UtfNormal::NFKD( $string );
  88                 else
  89                         return $string;
  90         }
  91
  92
  93         function quickIsNFC( $string ) {
  94                 # ASCII is always valid NFC!
  95                 if( !preg_match( '/[\x80-\xff]/', $string ) ) return true;
  96
  97                 global $utfCheckNFC, $utfCombiningClass;
  98                 $len = strlen( $string );
  99                 for( $i = 0; $i < $len; $i++ ) {
 100                         $c = $string{$i};
 101                         $n = ord( $c );
 102                         if( $n < 0x80 ) {
 103                                 continue;
 104                         } elseif( $n >= 0xf0 ) {
 105                                 $c = substr( $string, $i, 4 );
 106                                 $i += 3;
 107                         } elseif( $n >= 0xe0 ) {
 108                                 $c = substr( $string, $i, 3 );
 109                                 $i += 2;
 110                         } elseif( $n >= 0xc0 ) {
 111                                 $c = substr( $string, $i, 2 );
 112                                 $i++;
 113                         }
 114                         if( isset( $utfCheckNFC[$c] ) ) {
 115                                 # If it's NO or MAYBE, bail and do the slow check.
 116                                 return false;
 117                         }
 118                         if( isset( $utfCombiningClass[$c] ) ) {
 119                                 # Combining character? We might have to do sorting, at least.
 120                                 return false;
 121                         }
 122                 }
 123                 return true;
 124         }
 125
 126         # These take a string and run the normalization on them, without
 127         # checking for validity or any optimization etc. Input must be
 128         # VALID UTF-8!
 129         function NFC( $string ) {
 130                 return $out = UtfNormal::fastCompose( UtfNormal::NFD( $string ) );
 131         }
 132
 133         function NFD( $string ) {
 134                 global $utfCanonicalDecomp;
 135                 return UtfNormal::fastCombiningSort(
 136                         UtfNormal::fastDecompose( $string, $utfCanonicalDecomp ) );
 137         }
 138
 139         function NFKC( $string ) {
 140                 return UtfNormal::fastCompose( UtfNormal::NFKD( $string ) );
 141         }
 142
 143         function NFKD( $string ) {
 144                 global $utfCompatibilityDecomp;
 145                 return UtfNormal::fastCombiningSort(
 146                         UtfNormal::fastDecompose( $string, $utfCompatibilityDecomp ) );
 147         }
 148
 149
 150         /* Private */
 151         # Perform decomposition of a UTF-8 string into either D or KD form
 152         # (depending on which decomposition map is passed to us).
 153         # Input is assumed to be *valid* UTF-8. Invalid code will break.
 154         function fastDecompose( &$string, &$map ) {
 155                 $len = strlen( $string );
 156                 $out = '';
 157                 for( $i = 0; $i < $len; $i++ ) {
 158                         $c = $string{$i};
 159                         $n = ord( $c );
 160                         if( $n < 0x80 ) {
 161                                 # ASCII chars never decompose
 162                                 # THEY ARE IMMORTAL
 163                                 $out .= $c;
 164                                 continue;
 165                         } elseif( $n >= 0xf0 ) {
 166                                 $c = substr( $string, $i, 4 );
 167                                 $i += 3;
 168                         } elseif( $n >= 0xe0 ) {
 169                                 $c = substr( $string, $i, 3 );
 170                                 $i += 2;
 171                         } elseif( $n >= 0xc0 ) {
 172                                 $c = substr( $string, $i, 2 );
 173                                 $i++;
 174                         }
 175                         if( isset( $map[$c] ) ) {
 176                                 $out .= $map[$c];
 177                         } else {
 178                                 if( $c >= UTF8_HANGUL_FIRST && $c <= UTF8_HANGUL_LAST ) {
 179                                         $out .= UtfNormal::decomposeHangul( $c );
 180                                 } else {
 181                                         $out .= $c;
 182                                 }
 183                         }
 184                 }
 185                 return $out;
 186         }
 187
 188         function decomposeHangul( $c ) {
 189                 $codepoint = utf8ToCodepoint( $c );
 190                 $index = $codepoint - UNICODE_HANGUL_FIRST;
 191                 $l = IntVal( $index / UNICODE_HANGUL_NCOUNT );
 192                 $v = IntVal( ($index % UNICODE_HANGUL_NCOUNT) / UNICODE_HANGUL_TCOUNT);
 193                 $t = $index % UNICODE_HANGUL_TCOUNT;
 194                 $out = codepointToUtf8( $l + UNICODE_HANGUL_LBASE );
 195                 $out .= codepointToUtf8( $v + UNICODE_HANGUL_VBASE );
 196                 if( $t ) $out .= codepointToUtf8( $t + UNICODE_HANGUL_TBASE );
 197                 return $out;
 198         }
 199
 200         # Sorts combining characters into canonical order. This is the
 201         # final step in creating decomposed normal forms D and KD.
 202         function fastCombiningSort( $string ) {
 203                 global $utfCombiningClass;
 204                 $replacedCount = 1;
 205                 while( $replacedCount > 0 ) {
 206                         $replacedCount = 0;
 207                         $len = strlen( $string );
 208                         $out = '';
 209                         $lastClass = -1;
 210                         $lastChar = '';
 211                         for( $i = 0; $i < $len; $i++ ) {
 212                                 $c = $string{$i};
 213                                 $n = ord( $c );
 214                                 if( $n >= 0xf0 ) {
 215                                         $c = substr( $string, $i, 4 );
 216                                         $i += 3;
 217                                 } elseif( $n >= 0xe0 ) {
 218                                         $c = substr( $string, $i, 3 );
 219                                         $i += 2;
 220                                 } elseif( $n >= 0xc0 ) {
 221                                         $c = substr( $string, $i, 2 );
 222                                         $i++;
 223                                 }
 224                                 $class = isset( $utfCombiningClass[$c] ) ? $utfCombiningClass[$c] : 0;
 225                                 if( $lastClass == -1 ) {
 226                                         # First one
 227                                         $lastChar = $c;
 228                                         $lastClass = $class;
 229                                 } elseif( $lastClass > $class && $class > 0 ) {
 230                                         # Swap -- put this one on the stack
 231                                         $out .= $c;
 232                                         $replacedCount++;
 233                                 } else {
 234                                         $out .= $lastChar;
 235                                         $lastChar = $c;
 236                                         $lastClass = $class;
 237                                 }
 238                         }
 239                         $out .= $lastChar;
 240                         $string = $out;
 241                 }
 242                 return $string;
 243         }
 244
 245         # Produces canonically composed sequences, i.e. normal form C or KC.
 246         # Input must be valid UTF-8 in sorted normal form D or KD.
 247         function fastCompose( $string ) {
 248                 global $utfCanonicalComp, $utfCombiningClass;
 249                 $len = strlen( $string );
 250                 $out = '';
 251                 $lastClass = -1;
 252                 $startChar = '';
 253                 $combining = '';
 254                 for( $i = 0; $i < $len; $i++ ) {
 255                         $c = $string{$i};
 256                         $n = ord( $c );
 257                         if( $n >= 0xf0 ) {
 258                                 $c = substr( $string, $i, 4 );
 259                                 $i += 3;
 260                         } elseif( $n >= 0xe0 ) {
 261                                 $c = substr( $string, $i, 3 );
 262                                 $i += 2;
 263                         } elseif( $n >= 0xc0 ) {
 264                                 $c = substr( $string, $i, 2 );
 265                                 $i++;
 266                         }
 267                         $class = isset( $utfCombiningClass[$c] ) ? $utfCombiningClass[$c] : 0;
 268                         $pair = $startChar . $c;
 269                         if( empty( $utfCombiningClass[$c] ) ) {
 270                                 # New start char
 271                                 if( $lastClass == 0 && isset( $utfCanonicalComp[$pair] ) ) {
 272                                         $startChar = $utfCanonicalComp[$pair];
 273                                 } elseif( $lastClass == 0 &&
 274                                           $c >= UTF8_HANGUL_VBASE &&
 275                                           $c <= UTF8_HANGUL_VEND &&
 276                                           $startChar >= UTF8_HANGUL_LBASE &&
 277                                           $startChar <= UTF8_HANGUL_LEND ) {
 278                                         $lIndex = utf8ToCodepoint( $startChar ) - UNICODE_HANGUL_LBASE;
 279                                         $vIndex = utf8ToCodepoint( $c ) - UNICODE_HANGUL_VBASE;
 280                                         $hangulPoint = UNICODE_HANGUL_FIRST +
 281                                                 UNICODE_HANGUL_TCOUNT *
 282                                                 (UNICODE_HANGUL_VCOUNT * $lIndex + $vIndex);
 283                                         $startChar = codepointToUtf8( $hangulPoint );
 284                                 } elseif( $lastClass == 0 &&
 285                                           $c >= UTF8_HANGUL_TBASE &&
 286                                           $c <= UTF8_HANGUL_TEND &&
 287                                           $startChar >= UTF8_HANGUL_FIRST &&
 288                                           $startChar <= UTF8_HANGUL_LAST ) {
 289                                         $tIndex = utf8ToCodepoint( $c ) - UNICODE_HANGUL_TBASE;
 290                                         $hangulPoint = utf8ToCodepoint( $startChar ) + $tIndex;
 291                                         $startChar = codepointToUtf8( $hangulPoint );
 292                                 } else {
 293                                         $out .= $startChar;
 294                                         $out .= $combining;
 295                                         $startChar = $c;
 296                                         $combining = '';
 297                                 }
 298                         } else {
 299                                 # A combining char; see what we can do with it
 300                                 if( !empty( $startChar ) &&
 301                                         $lastClass < $class &&
 302                                         $class > 0 &&
 303                                         isset( $utfCanonicalComp[$pair] ) ) {
 304                                         $startChar = $utfCanonicalComp[$pair];
 305                                         $class = 0;
 306                                 } else {
 307                                         $combining .= $c;
 308                                 }
 309                         }
 310                         $lastClass = $class;
 311                 }
 312                 $out .= $startChar . $combining;
 313                 return $out;
 314         }
 315
 316         # This is just used for the benchmark, comparing how long it takes to
 317         # interate through a string without really doing anything of substance.
 318         function placebo( $string ) {
 319                 $len = strlen( $string );
 320                 $out = '';
 321                 for( $i = 0; $i < $len; $i++ ) {
 322                         $out .= $string{$i};
 323                 }
 324                 return $out;
 325         }
 326 }
 327
 328 ?>