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 file names */
15 static const char illegal[] = "<>:\"/\\|?*";
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_PROTOCOL */
30 const efi_guid_t efi_guid_unicode_collation_protocol =
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  * metai_match() - compare utf-16 string with a pattern string case-insenitively
78  *
79  * @s:		string to compare
80  * @p:		pattern string
81  *
82  * The pattern string may use these:
83  *	- * matches >= 0 characters
84  *	- ? matches 1 character
85  *	- [<char1><char2>...<charN>] match any character in the set
86  *	- [<char1>-<char2>] matches any character in the range
87  *
88  * This function is called my efi_metai_match().
89  *
90  * For '*' pattern searches this function calls itself recursively.
91  * Performance-wise this is suboptimal, especially for multiple '*' wildcards.
92  * But it results in simple code.
93  *
94  * Return:	true if the string is matched.
95  */
96 static bool metai_match(const u16 *s, const u16 *p)
97 {
98 	u16 first;
99 
100 	for (; *s && *p; ++s, ++p) {
101 		switch (*p) {
102 		case '*':
103 			/* Match 0 or more characters */
104 			++p;
105 			for (;; ++s) {
106 				if (metai_match(s, p))
107 					return true;
108 				if (!*s)
109 					return false;
110 			}
111 		case '?':
112 			/* Match any one character */
113 			break;
114 		case '[':
115 			/* Match any character in the set */
116 			++p;
117 			first = *p;
118 			if (first == ']')
119 				/* Empty set */
120 				return false;
121 			++p;
122 			if (*p == '-') {
123 				/* Range */
124 				++p;
125 				if (*s < first || *s > *p)
126 					return false;
127 				++p;
128 				if (*p != ']')
129 					return false;
130 			} else {
131 				/* Set */
132 				bool hit = false;
133 
134 				if (*s == first)
135 					hit = true;
136 				for (; *p && *p != ']'; ++p) {
137 					if (*p == *s)
138 						hit = true;
139 				}
140 				if (!hit || *p != ']')
141 					return false;
142 			}
143 			break;
144 		default:
145 			/* Match one character */
146 			if (*p != *s)
147 				return false;
148 		}
149 	}
150 	if (!*p && !*s)
151 		return true;
152 	return false;
153 }
154 
155 /**
156  * efi_metai_match() - compare utf-16 string with a pattern string
157  *		       case-insenitively
158  *
159  * @this:	unicode collation protocol instance
160  * @s:		string to compare
161  * @p:		pattern string
162  *
163  * The pattern string may use these:
164  *	- * matches >= 0 characters
165  *	- ? matches 1 character
166  *	- [<char1><char2>...<charN>] match any character in the set
167  *	- [<char1>-<char2>] matches any character in the range
168  *
169  * This function implements the MetaMatch() service of the
170  * EFI_UNICODE_COLLATION_PROTOCOL.
171  *
172  * Return:	true if the string is matched.
173  */
174 static bool EFIAPI efi_metai_match(struct efi_unicode_collation_protocol *this,
175 				   const u16 *string, const u16 *pattern)
176 {
177 	bool ret;
178 
179 	EFI_ENTRY("%p, %ls, %ls", this, string, pattern);
180 	ret =  metai_match(string, pattern);
181 	EFI_EXIT(EFI_SUCCESS);
182 	return ret;
183 }
184 
185 /**
186  * efi_str_lwr() - convert to lower case
187  *
188  * @this:	unicode collation protocol instance
189  * @string:	string to convert
190  * @p:		pattern string
191  *
192  * The conversion is done in place. As long as upper and lower letters use the
193  * same number of words this does not pose a problem.
194  *
195  * This function implements the StrLwr() service of the
196  * EFI_UNICODE_COLLATION_PROTOCOL.
197  */
198 static void EFIAPI efi_str_lwr(struct efi_unicode_collation_protocol *this,
199 			       u16 *string)
200 {
201 	EFI_ENTRY("%p, %ls", this, string);
202 	for (; *string; ++string)
203 		*string = utf_to_lower(*string);
204 	EFI_EXIT(EFI_SUCCESS);
205 }
206 
207 /**
208  * efi_str_upr() - convert to upper case
209  *
210  * @this:	unicode collation protocol instance
211  * @string:	string to convert
212  * @p:		pattern string
213  *
214  * The conversion is done in place. As long as upper and lower letters use the
215  * same number of words this does not pose a problem.
216  *
217  * This function implements the StrUpr() service of the
218  * EFI_UNICODE_COLLATION_PROTOCOL.
219  */
220 static void EFIAPI efi_str_upr(struct efi_unicode_collation_protocol *this,
221 			       u16 *string)
222 {
223 	EFI_ENTRY("%p, %ls", this, string);
224 	for (; *string; ++string)
225 		*string = utf_to_upper(*string);
226 	EFI_EXIT(EFI_SUCCESS);
227 }
228 
229 /**
230  * efi_fat_to_str() - convert an 8.3 file name from an OEM codepage to Unicode
231  *
232  * @this:	unicode collation protocol instance
233  * @fat_size:	size of the string to convert
234  * @fat:	string to convert
235  * @string:	converted string
236  *
237  * This function implements the FatToStr() service of the
238  * EFI_UNICODE_COLLATION_PROTOCOL.
239  */
240 static void EFIAPI efi_fat_to_str(struct efi_unicode_collation_protocol *this,
241 				  efi_uintn_t fat_size, char *fat, u16 *string)
242 {
243 	efi_uintn_t i;
244 	u16 c;
245 
246 	EFI_ENTRY("%p, %zu, %s, %p", this, fat_size, fat, string);
247 	for (i = 0; i < fat_size; ++i) {
248 		c = (unsigned char)fat[i];
249 		if (c > 0x80)
250 			c = codepage[i - 0x80];
251 		string[i] = c;
252 		if (!c)
253 			break;
254 	}
255 	string[i] = 0;
256 	EFI_EXIT(EFI_SUCCESS);
257 }
258 
259 /**
260  * efi_fat_to_str() - convert a utf-16 string to legal characters for a FAT
261  *                    file name in an OEM code page
262  *
263  * @this:	unicode collation protocol instance
264  * @string:	Unicode string to convert
265  * @fat_size:	size of the target buffer
266  * @fat:	converted string
267  *
268  * This function implements the StrToFat() service of the
269  * EFI_UNICODE_COLLATION_PROTOCOL.
270  *
271  * Return:	true if an illegal character was substituted by '_'.
272  */
273 static bool EFIAPI efi_str_to_fat(struct efi_unicode_collation_protocol *this,
274 				  const u16 *string, efi_uintn_t fat_size,
275 				  char *fat)
276 {
277 	efi_uintn_t i;
278 	s32 c;
279 	bool ret = false;
280 
281 	EFI_ENTRY("%p, %ls, %zu, %p", this, string, fat_size, fat);
282 	for (i = 0; i < fat_size;) {
283 		c = utf16_get(&string);
284 		switch (c) {
285 		/* Ignore period and space */
286 		case '.':
287 		case ' ':
288 			continue;
289 		case 0:
290 			break;
291 		}
292 		c = utf_to_upper(c);
293 		if (c >= 0x80) {
294 			int j;
295 
296 			/* Look for codepage translation */
297 			for (j = 0; j < 0x80; ++j) {
298 				if (c == codepage[j]) {
299 					c = j + 0x80;
300 					break;
301 				}
302 			}
303 			if (j >= 0x80) {
304 				c = '_';
305 				ret = true;
306 			}
307 		} else if (c && (c < 0x20 || strchr(illegal, c))) {
308 			c = '_';
309 			ret = true;
310 		}
311 
312 		fat[i] = c;
313 		if (!c)
314 			break;
315 		++i;
316 	}
317 	EFI_EXIT(EFI_SUCCESS);
318 	return ret;
319 }
320 
321 const struct efi_unicode_collation_protocol efi_unicode_collation_protocol = {
322 	.stri_coll = efi_stri_coll,
323 	.metai_match = efi_metai_match,
324 	.str_lwr = efi_str_lwr,
325 	.str_upr = efi_str_upr,
326 	.fat_to_str = efi_fat_to_str,
327 	.str_to_fat = efi_str_to_fat,
328 	.supported_languages = "en",
329 };
330