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 # Load compatibility decompositions on demand if they are needed.
  35 global $utfCompatibilityDecomp;
  36 $utfCompatibilityDecomp = NULL;
  37
  38 define( 'UNICODE_HANGUL_FIRST', 0xac00 );
  39 define( 'UNICODE_HANGUL_LAST',  0xd7a3 );
  40
  41 define( 'UNICODE_HANGUL_LBASE', 0x1100 );
  42 define( 'UNICODE_HANGUL_VBASE', 0x1161 );
  43 define( 'UNICODE_HANGUL_TBASE', 0x11a7 );
  44
  45 define( 'UNICODE_HANGUL_LCOUNT', 19 );
  46 define( 'UNICODE_HANGUL_VCOUNT', 21 );
  47 define( 'UNICODE_HANGUL_TCOUNT', 28 );
  48 define( 'UNICODE_HANGUL_NCOUNT', UNICODE_HANGUL_VCOUNT * UNICODE_HANGUL_TCOUNT );
  49
  50 define( 'UNICODE_HANGUL_LEND', UNICODE_HANGUL_LBASE + UNICODE_HANGUL_LCOUNT - 1 );
  51 define( 'UNICODE_HANGUL_VEND', UNICODE_HANGUL_VBASE + UNICODE_HANGUL_VCOUNT - 1 );
  52 define( 'UNICODE_HANGUL_TEND', UNICODE_HANGUL_TBASE + UNICODE_HANGUL_TCOUNT - 1 );
  53
  54 define( 'UTF8_HANGUL_FIRST', codepointToUtf8( UNICODE_HANGUL_FIRST ) );
  55 define( 'UTF8_HANGUL_LAST', codepointToUtf8( UNICODE_HANGUL_LAST ) );
  56
  57 define( 'UTF8_HANGUL_LBASE', codepointToUtf8( UNICODE_HANGUL_LBASE ) );
  58 define( 'UTF8_HANGUL_VBASE', codepointToUtf8( UNICODE_HANGUL_VBASE ) );
  59 define( 'UTF8_HANGUL_TBASE', codepointToUtf8( UNICODE_HANGUL_TBASE ) );
  60
  61 define( 'UTF8_HANGUL_LEND', codepointToUtf8( UNICODE_HANGUL_LEND ) );
  62 define( 'UTF8_HANGUL_VEND', codepointToUtf8( UNICODE_HANGUL_VEND ) );
  63 define( 'UTF8_HANGUL_TEND', codepointToUtf8( UNICODE_HANGUL_TEND ) );
  64
  65 class UtfNormal {
  66         # These functions try to skip the conversion if it won't be necessary.
  67         # An all ASCII string for instance doesn't need conversion.
  68         function toNFC( $string ) {
  69                 if( UtfNormal::quickIsNFC( $string ) )
  70                         return $string;
  71                 else
  72                         return UtfNormal::NFC( $string );
  73         }
  74
  75         function toNFD( $string ) {
  76                 if( preg_match( '/[\x80-\xff]/', $string ) )
  77                         return UtfNormal::NFD( $string );
  78                 else
  79                         return $string;
  80         }
  81
  82         function toNFKC( $string ) {
  83                 if( preg_match( '/[\x80-\xff]/', $string ) )
  84                         return UtfNormal::NFKC( $string );
  85                 else
  86                         return $string;
  87         }
  88
  89         function toNFKD( $string ) {
  90                 if( preg_match( '/[\x80-\xff]/', $string ) )
  91                         return UtfNormal::NFKD( $string );
  92                 else
  93                         return $string;
  94         }
  95
  96
  97         function quickIsNFC( $string ) {
  98                 # ASCII is always valid NFC!
  99                 if( !preg_match( '/[\x80-\xff]/', $string ) ) return true;
 100
 101                 global $utfCheckNFC, $utfCombiningClass;
 102                 $len = strlen( $string );
 103                 for( $i = 0; $i < $len; $i++ ) {
 104                         $c = $string{$i};
 105                         $n = ord( $c );
 106                         if( $n < 0x80 ) {
 107                                 continue;
 108                         } elseif( $n >= 0xf0 ) {
 109                                 $c = substr( $string, $i, 4 );
 110                                 $i += 3;
 111                         } elseif( $n >= 0xe0 ) {
 112                                 $c = substr( $string, $i, 3 );
 113                                 $i += 2;
 114                         } elseif( $n >= 0xc0 ) {
 115                                 $c = substr( $string, $i, 2 );
 116                                 $i++;
 117                         }
 118                         if( isset( $utfCheckNFC[$c] ) ) {
 119                                 # If it's NO or MAYBE, bail and do the slow check.
 120                                 return false;
 121                         }
 122                         if( isset( $utfCombiningClass[$c] ) ) {
 123                                 # Combining character? We might have to do sorting, at least.
 124                                 return false;
 125                         }
 126                 }
 127                 return true;
 128         }
 129
 130         # These take a string and run the normalization on them, without
 131         # checking for validity or any optimization etc. Input must be
 132         # VALID UTF-8!
 133         function NFC( $string ) {
 134                 return $out = UtfNormal::fastCompose( UtfNormal::NFD( $string ) );
 135         }
 136
 137         function NFD( $string ) {
 138                 global $utfCanonicalDecomp;
 139                 return UtfNormal::fastCombiningSort(
 140                         UtfNormal::fastDecompose( $string, $utfCanonicalDecomp ) );
 141         }
 142
 143         function NFKC( $string ) {
 144                 return UtfNormal::fastCompose( UtfNormal::NFKD( $string ) );
 145         }
 146
 147         function NFKD( $string ) {
 148                 global $utfCompatibilityDecomp;
 149                 if( !isset( $utfCompatibilityDecomp ) ) {
 150                         require_once( 'UtfNormalDataK.inc' );
 151                 }
 152                 return UtfNormal::fastCombiningSort(
 153                         UtfNormal::fastDecompose( $string, $utfCompatibilityDecomp ) );
 154         }
 155
 156
 157         /* Private */
 158         # Perform decomposition of a UTF-8 string into either D or KD form
 159         # (depending on which decomposition map is passed to us).
 160         # Input is assumed to be *valid* UTF-8. Invalid code will break.
 161         function fastDecompose( &$string, &$map ) {
 162                 $len = strlen( $string );
 163                 $out = '';
 164                 for( $i = 0; $i < $len; $i++ ) {
 165                         $c = $string{$i};
 166                         $n = ord( $c );
 167                         if( $n < 0x80 ) {
 168                                 # ASCII chars never decompose
 169                                 # THEY ARE IMMORTAL
 170                                 $out .= $c;
 171                                 continue;
 172                         } elseif( $n >= 0xf0 ) {
 173                                 $c = substr( $string, $i, 4 );
 174                                 $i += 3;
 175                         } elseif( $n >= 0xe0 ) {
 176                                 $c = substr( $string, $i, 3 );
 177                                 $i += 2;
 178                         } elseif( $n >= 0xc0 ) {
 179                                 $c = substr( $string, $i, 2 );
 180                                 $i++;
 181                         }
 182                         if( isset( $map[$c] ) ) {
 183                                 $out .= $map[$c];
 184                         } else {
 185                                 if( $c >= UTF8_HANGUL_FIRST && $c <= UTF8_HANGUL_LAST ) {
 186                                         $out .= UtfNormal::decomposeHangul( $c );
 187                                 } else {
 188                                         $out .= $c;
 189                                 }
 190                         }
 191                 }
 192                 return $out;
 193         }
 194
 195         function decomposeHangul( $c ) {
 196                 $codepoint = utf8ToCodepoint( $c );
 197                 $index = $codepoint - UNICODE_HANGUL_FIRST;
 198                 $l = IntVal( $index / UNICODE_HANGUL_NCOUNT );
 199                 $v = IntVal( ($index % UNICODE_HANGUL_NCOUNT) / UNICODE_HANGUL_TCOUNT);
 200                 $t = $index % UNICODE_HANGUL_TCOUNT;
 201                 $out = codepointToUtf8( $l + UNICODE_HANGUL_LBASE );
 202                 $out .= codepointToUtf8( $v + UNICODE_HANGUL_VBASE );
 203                 if( $t ) $out .= codepointToUtf8( $t + UNICODE_HANGUL_TBASE );
 204                 return $out;
 205         }
 206
 207         # Sorts combining characters into canonical order. This is the
 208         # final step in creating decomposed normal forms D and KD.
 209         function fastCombiningSort( $string ) {
 210                 global $utfCombiningClass;
 211                 $replacedCount = 1;
 212                 while( $replacedCount > 0 ) {
 213                         $replacedCount = 0;
 214                         $len = strlen( $string );
 215                         $out = '';
 216                         $lastClass = -1;
 217                         $lastChar = '';
 218                         for( $i = 0; $i < $len; $i++ ) {
 219                                 $c = $string{$i};
 220                                 $n = ord( $c );
 221                                 if( $n >= 0xf0 ) {
 222                                         $c = substr( $string, $i, 4 );
 223                                         $i += 3;
 224                                 } elseif( $n >= 0xe0 ) {
 225                                         $c = substr( $string, $i, 3 );
 226                                         $i += 2;
 227                                 } elseif( $n >= 0xc0 ) {
 228                                         $c = substr( $string, $i, 2 );
 229                                         $i++;
 230                                 }
 231                                 $class = isset( $utfCombiningClass[$c] ) ? $utfCombiningClass[$c] : 0;
 232                                 if( $lastClass == -1 ) {
 233                                         # First one
 234                                         $lastChar = $c;
 235                                         $lastClass = $class;
 236                                 } elseif( $lastClass > $class && $class > 0 ) {
 237                                         # Swap -- put this one on the stack
 238                                         $out .= $c;
 239                                         $replacedCount++;
 240                                 } else {
 241                                         $out .= $lastChar;
 242                                         $lastChar = $c;
 243                                         $lastClass = $class;
 244                                 }
 245                         }
 246                         $out .= $lastChar;
 247                         $string = $out;
 248                 }
 249                 return $string;
 250         }
 251
 252         # Produces canonically composed sequences, i.e. normal form C or KC.
 253         # Input must be valid UTF-8 in sorted normal form D or KD.
 254         function fastCompose( $string ) {
 255                 global $utfCanonicalComp, $utfCombiningClass;
 256                 $len = strlen( $string );
 257                 $out = '';
 258                 $lastClass = -1;
 259                 $startChar = '';
 260                 $combining = '';
 261                 for( $i = 0; $i < $len; $i++ ) {
 262                         $c = $string{$i};
 263                         $n = ord( $c );
 264                         if( $n >= 0xf0 ) {
 265                                 $c = substr( $string, $i, 4 );
 266                                 $i += 3;
 267                         } elseif( $n >= 0xe0 ) {
 268                                 $c = substr( $string, $i, 3 );
 269                                 $i += 2;
 270                         } elseif( $n >= 0xc0 ) {
 271                                 $c = substr( $string, $i, 2 );
 272                                 $i++;
 273                         }
 274                         $class = isset( $utfCombiningClass[$c] ) ? $utfCombiningClass[$c] : 0;
 275                         $pair = $startChar . $c;
 276                         if( empty( $utfCombiningClass[$c] ) ) {
 277                                 # New start char
 278                                 if( $lastClass == 0 && isset( $utfCanonicalComp[$pair] ) ) {
 279                                         $startChar = $utfCanonicalComp[$pair];
 280                                 } elseif( $lastClass == 0 &&
 281                                           $c >= UTF8_HANGUL_VBASE &&
 282                                           $c <= UTF8_HANGUL_VEND &&
 283                                           $startChar >= UTF8_HANGUL_LBASE &&
 284                                           $startChar <= UTF8_HANGUL_LEND ) {
 285                                         $lIndex = utf8ToCodepoint( $startChar ) - UNICODE_HANGUL_LBASE;
 286                                         $vIndex = utf8ToCodepoint( $c ) - UNICODE_HANGUL_VBASE;
 287                                         $hangulPoint = UNICODE_HANGUL_FIRST +
 288                                                 UNICODE_HANGUL_TCOUNT *
 289                                                 (UNICODE_HANGUL_VCOUNT * $lIndex + $vIndex);
 290                                         $startChar = codepointToUtf8( $hangulPoint );
 291                                 } elseif( $lastClass == 0 &&
 292                                           $c >= UTF8_HANGUL_TBASE &&
 293                                           $c <= UTF8_HANGUL_TEND &&
 294                                           $startChar >= UTF8_HANGUL_FIRST &&
 295                                           $startChar <= UTF8_HANGUL_LAST ) {
 296                                         $tIndex = utf8ToCodepoint( $c ) - UNICODE_HANGUL_TBASE;
 297                                         $hangulPoint = utf8ToCodepoint( $startChar ) + $tIndex;
 298                                         $startChar = codepointToUtf8( $hangulPoint );
 299                                 } else {
 300                                         $out .= $startChar;
 301                                         $out .= $combining;
 302                                         $startChar = $c;
 303                                         $combining = '';
 304                                 }
 305                         } else {
 306                                 # A combining char; see what we can do with it
 307                                 if( !empty( $startChar ) &&
 308                                         $lastClass < $class &&
 309                                         $class > 0 &&
 310                                         isset( $utfCanonicalComp[$pair] ) ) {
 311                                         $startChar = $utfCanonicalComp[$pair];
 312                                         $class = 0;
 313                                 } else {
 314                                         $combining .= $c;
 315                                 }
 316                         }
 317                         $lastClass = $class;
 318                 }
 319                 $out .= $startChar . $combining;
 320                 return $out;
 321         }
 322
 323         # This is just used for the benchmark, comparing how long it takes to
 324         # interate through a string without really doing anything of substance.
 325         function placebo( $string ) {
 326                 $len = strlen( $string );
 327                 $out = '';
 328                 for( $i = 0; $i < $len; $i++ ) {
 329                         $out .= $string{$i};
 330                 }
 331                 return $out;
 332         }
 333 }
 334
 335 ?>