lib/efi_loader/efi_unicode_collation.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * EFI Unicode collation protocol
   4  *
   5  * Copyright (c) 2018 Heinrich Schuchardt <xypron.glpk@gmx.de>
   6  */
   7
   8 #include <common.h>
   9 #include <charset.h>
  10 #include <cp1250.h>
  11 #include <cp437.h>
  12 #include <efi_loader.h>
  13
  14 /* Characters that may not be used in FAT 8.3 file names */
  15 static const char illegal[] = "+,<=>:;\"/\\|?*[]\x7f";
  16
  17 /*
  18  * EDK2 assumes codepage 1250 when creating FAT 8.3 file names.
  19  * Linux defaults to codepage 437 for FAT 8.3 file names.
  20  */
  21 #if CONFIG_FAT_DEFAULT_CODEPAGE == 1250
  22 /* Unicode code points for code page 1250 characters 0x80 - 0xff */
  23 static const u16 codepage[] = CP1250;
  24 #else
  25 /* Unicode code points for code page 437 characters 0x80 - 0xff */
  26 static const u16 codepage[] = CP437;
  27 #endif
  28
  29 /* GUID of the EFI_UNICODE_COLLATION_PROTOCOL2 */
  30 const efi_guid_t efi_guid_unicode_collation_protocol2 =
  31         EFI_UNICODE_COLLATION_PROTOCOL2_GUID;
  32
  33 /**
  34  * efi_stri_coll() - compare utf-16 strings case-insenitively
  35  *
  36  * @this:       unicode collation protocol instance
  37  * @s1:         first string
  38  * @s2:         second string
  39  *
  40  * This function implements the StriColl() service of the
  41  * EFI_UNICODE_COLLATION_PROTOCOL.
  42  *
  43  * See the Unified Extensible Firmware Interface (UEFI) specification for
  44  * details.
  45  *
  46  * TODO:
  47  * The implementation does not follow the Unicode collation algorithm.
  48  * For ASCII characters it results in the same sort order as EDK2.
  49  * We could use table UNICODE_CAPITALIZATION_TABLE for better results.
  50  *
  51  * Return:      0: s1 == s2, > 0: s1 > s2, < 0: s1 < s2
  52  */
  53 static efi_intn_t EFIAPI efi_stri_coll(
  54                 struct efi_unicode_collation_protocol *this, u16 *s1, u16 *s2)
  55 {
  56         s32 c1, c2;
  57         efi_intn_t ret = 0;
  58
  59         EFI_ENTRY("%p, %ls, %ls", this, s1, s2);
  60         for (; *s1 | *s2; ++s1, ++s2) {
  61                 c1 = utf_to_upper(*s1);
  62                 c2 = utf_to_upper(*s2);
  63                 if (c1 < c2) {
  64                         ret = -1;
  65                         goto out;
  66                 } else if (c1 > c2) {
  67                         ret = 1;
  68                         goto out;
  69                 }
  70         }
  71 out:
  72         EFI_EXIT(EFI_SUCCESS);
  73         return ret;
  74 }
  75
  76 /**
  77  * next_lower() - get next codepoint converted to lower case
  78  *
  79  * @string:     pointer to u16 string, on return advanced by one codepoint
  80  * Return:      first codepoint of string converted to lower case
  81  */
  82 static s32 next_lower(const u16 **string)
  83 {
  84         return utf_to_lower(utf16_get(string));
  85 }
  86
  87 /**
  88  * metai_match() - compare utf-16 string with a pattern string case-insenitively
  89  *
  90  * @string:     string to compare
  91  * @pattern:    pattern string
  92  *
  93  * The pattern string may use these:
  94  *      - * matches >= 0 characters
  95  *      - ? matches 1 character
  96  *      - [<char1><char2>...<charN>] match any character in the set
  97  *      - [<char1>-<char2>] matches any character in the range
  98  *
  99  * This function is called my efi_metai_match().
 100  *
 101  * For '*' pattern searches this function calls itself recursively.
 102  * Performance-wise this is suboptimal, especially for multiple '*' wildcards.
 103  * But it results in simple code.
 104  *
 105  * Return:      true if the string is matched.
 106  */
 107 static bool metai_match(const u16 *string, const u16 *pattern)
 108 {
 109         s32 first, s, p;
 110
 111         for (; *string && *pattern;) {
 112                 const u16 *string_old = string;
 113
 114                 s = next_lower(&string);
 115                 p = next_lower(&pattern);
 116
 117                 switch (p) {
 118                 case '*':
 119                         /* Match 0 or more characters */
 120                         for (;; s = next_lower(&string)) {
 121                                 if (metai_match(string_old, pattern))
 122                                         return true;
 123                                 if (!s)
 124                                         return false;
 125                                 string_old = string;
 126                         }
 127                 case '?':
 128                         /* Match any one character */
 129                         break;
 130                 case '[':
 131                         /* Match any character in the set */
 132                         p = next_lower(&pattern);
 133                         first = p;
 134                         if (first == ']')
 135                                 /* Empty set */
 136                                 return false;
 137                         p = next_lower(&pattern);
 138                         if (p == '-') {
 139                                 /* Range */
 140                                 p = next_lower(&pattern);
 141                                 if (s < first || s > p)
 142                                         return false;
 143                                 p = next_lower(&pattern);
 144                                 if (p != ']')
 145                                         return false;
 146                         } else {
 147                                 /* Set */
 148                                 bool hit = false;
 149
 150                                 if (s == first)
 151                                         hit = true;
 152                                 for (; p && p != ']';
 153                                      p = next_lower(&pattern)) {
 154                                         if (p == s)
 155                                                 hit = true;
 156                                 }
 157                                 if (!hit || p != ']')
 158                                         return false;
 159                         }
 160                         break;
 161                 default:
 162                         /* Match one character */
 163                         if (p != s)
 164                                 return false;
 165                 }
 166         }
 167         if (!*pattern && !*string)
 168                 return true;
 169         return false;
 170 }
 171
 172 /**
 173  * efi_metai_match() - compare utf-16 string with a pattern string
 174  *                     case-insenitively
 175  *
 176  * @this:       unicode collation protocol instance
 177  * @s:          string to compare
 178  * @p:          pattern string
 179  *
 180  * The pattern string may use these:
 181  *      - * matches >= 0 characters
 182  *      - ? matches 1 character
 183  *      - [<char1><char2>...<charN>] match any character in the set
 184  *      - [<char1>-<char2>] matches any character in the range
 185  *
 186  * This function implements the MetaMatch() service of the
 187  * EFI_UNICODE_COLLATION_PROTOCOL.
 188  *
 189  * Return:      true if the string is matched.
 190  */
 191 static bool EFIAPI efi_metai_match(struct efi_unicode_collation_protocol *this,
 192                                    const u16 *string, const u16 *pattern)
 193 {
 194         bool ret;
 195
 196         EFI_ENTRY("%p, %ls, %ls", this, string, pattern);
 197         ret =  metai_match(string, pattern);
 198         EFI_EXIT(EFI_SUCCESS);
 199         return ret;
 200 }
 201
 202 /**
 203  * efi_str_lwr() - convert to lower case
 204  *
 205  * @this:       unicode collation protocol instance
 206  * @string:     string to convert
 207  * @p:          pattern string
 208  *
 209  * The conversion is done in place. As long as upper and lower letters use the
 210  * same number of words this does not pose a problem.
 211  *
 212  * This function implements the StrLwr() service of the
 213  * EFI_UNICODE_COLLATION_PROTOCOL.
 214  */
 215 static void EFIAPI efi_str_lwr(struct efi_unicode_collation_protocol *this,
 216                                u16 *string)
 217 {
 218         EFI_ENTRY("%p, %ls", this, string);
 219         for (; *string; ++string)
 220                 *string = utf_to_lower(*string);
 221         EFI_EXIT(EFI_SUCCESS);
 222 }
 223
 224 /**
 225  * efi_str_upr() - convert to upper case
 226  *
 227  * @this:       unicode collation protocol instance
 228  * @string:     string to convert
 229  * @p:          pattern string
 230  *
 231  * The conversion is done in place. As long as upper and lower letters use the
 232  * same number of words this does not pose a problem.
 233  *
 234  * This function implements the StrUpr() service of the
 235  * EFI_UNICODE_COLLATION_PROTOCOL.
 236  */
 237 static void EFIAPI efi_str_upr(struct efi_unicode_collation_protocol *this,
 238                                u16 *string)
 239 {
 240         EFI_ENTRY("%p, %ls", this, string);
 241         for (; *string; ++string)
 242                 *string = utf_to_upper(*string);
 243         EFI_EXIT(EFI_SUCCESS);
 244 }
 245
 246 /**
 247  * efi_fat_to_str() - convert an 8.3 file name from an OEM codepage to Unicode
 248  *
 249  * @this:       unicode collation protocol instance
 250  * @fat_size:   size of the string to convert
 251  * @fat:        string to convert
 252  * @string:     converted string
 253  *
 254  * This function implements the FatToStr() service of the
 255  * EFI_UNICODE_COLLATION_PROTOCOL.
 256  */
 257 static void EFIAPI efi_fat_to_str(struct efi_unicode_collation_protocol *this,
 258                                   efi_uintn_t fat_size, char *fat, u16 *string)
 259 {
 260         efi_uintn_t i;
 261         u16 c;
 262
 263         EFI_ENTRY("%p, %zu, %s, %p", this, fat_size, fat, string);
 264         for (i = 0; i < fat_size; ++i) {
 265                 c = (unsigned char)fat[i];
 266                 if (c > 0x80)
 267                         c = codepage[i - 0x80];
 268                 string[i] = c;
 269                 if (!c)
 270                         break;
 271         }
 272         string[i] = 0;
 273         EFI_EXIT(EFI_SUCCESS);
 274 }
 275
 276 /**
 277  * efi_fat_to_str() - convert a utf-16 string to legal characters for a FAT
 278  *                    file name in an OEM code page
 279  *
 280  * @this:       unicode collation protocol instance
 281  * @string:     Unicode string to convert
 282  * @fat_size:   size of the target buffer
 283  * @fat:        converted string
 284  *
 285  * This function implements the StrToFat() service of the
 286  * EFI_UNICODE_COLLATION_PROTOCOL.
 287  *
 288  * Return:      true if an illegal character was substituted by '_'.
 289  */
 290 static bool EFIAPI efi_str_to_fat(struct efi_unicode_collation_protocol *this,
 291                                   const u16 *string, efi_uintn_t fat_size,
 292                                   char *fat)
 293 {
 294         efi_uintn_t i;
 295         s32 c;
 296         bool ret = false;
 297
 298         EFI_ENTRY("%p, %ls, %zu, %p", this, string, fat_size, fat);
 299         for (i = 0; i < fat_size;) {
 300                 c = utf16_get(&string);
 301                 switch (c) {
 302                 /* Ignore period and space */
 303                 case '.':
 304                 case ' ':
 305                         continue;
 306                 case 0:
 307                         break;
 308                 }
 309                 c = utf_to_upper(c);
 310                 if (c >= 0x80) {
 311                         int j;
 312
 313                         /* Look for codepage translation */
 314                         for (j = 0; j < 0x80; ++j) {
 315                                 if (c == codepage[j]) {
 316                                         c = j + 0x80;
 317                                         break;
 318                                 }
 319                         }
 320                         if (j >= 0x80) {
 321                                 c = '_';
 322                                 ret = true;
 323                         }
 324                 } else if (c && (c < 0x20 || strchr(illegal, c))) {
 325                         c = '_';
 326                         ret = true;
 327                 }
 328
 329                 fat[i] = c;
 330                 if (!c)
 331                         break;
 332                 ++i;
 333         }
 334         EFI_EXIT(EFI_SUCCESS);
 335         return ret;
 336 }
 337
 338 const struct efi_unicode_collation_protocol efi_unicode_collation_protocol2 = {
 339         .stri_coll = efi_stri_coll,
 340         .metai_match = efi_metai_match,
 341         .str_lwr = efi_str_lwr,
 342         .str_upr = efi_str_upr,
 343         .fat_to_str = efi_fat_to_str,
 344         .str_to_fat = efi_str_to_fat,
 345         .supported_languages = "en",
 346 };
 347
 348 /*
 349  * In EFI 1.10 a version of the Unicode collation protocol using ISO 639-2
 350  * language codes existed. This protocol is not part of the UEFI specification
 351  * any longer. Unfortunately it is required to run the UEFI Self Certification
 352  * Test (SCT) II, version 2.6, 2017. So we implement it here for the sole
 353  * purpose of running the SCT. It can be removed when a compliant SCT is
 354  * available.
 355  */
 356 #if CONFIG_IS_ENABLED(EFI_UNICODE_COLLATION_PROTOCOL)
 357
 358 /* GUID of the EFI_UNICODE_COLLATION_PROTOCOL */
 359 const efi_guid_t efi_guid_unicode_collation_protocol =
 360         EFI_UNICODE_COLLATION_PROTOCOL_GUID;
 361
 362 const struct efi_unicode_collation_protocol efi_unicode_collation_protocol = {
 363         .stri_coll = efi_stri_coll,
 364         .metai_match = efi_metai_match,
 365         .str_lwr = efi_str_lwr,
 366         .str_upr = efi_str_upr,
 367         .fat_to_str = efi_fat_to_str,
 368         .str_to_fat = efi_str_to_fat,
 369         /* ISO 639-2 language code */
 370         .supported_languages = "eng",
 371 };
 372
 373 #endif