2 Unix SMB/CIFS implementation.
3 new hash based name mangling implementation
4 Copyright (C) Andrew Tridgell 2002
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 this mangling scheme uses the following format
26 where nnnnn is a base 36 hash, and A represents characters from the original string
28 The hash is taken of the leading part of the long filename, in uppercase
30 for simplicity, we only allow ascii characters in 8.3 names
35 ===============================================================================
38 This file deliberately uses non-multibyte string functions in many places. This
39 is *not* a mistake. This code is multi-byte safe, but it gets this property
40 through some very subtle knowledge of the way multi-byte strings are encoded
41 and the fact that this mangling algorithm only supports ascii characters in
44 please don't convert this file to use the *_m() functions!!
45 ===============================================================================
52 #define M_DEBUG(level, x) DEBUG(level, x)
54 #define M_DEBUG(level, x)
57 /* these flags are used to mark characters in as having particular
59 #define FLAG_BASECHAR 1
61 #define FLAG_ILLEGAL 4
62 #define FLAG_WILDCARD 8
64 /* the "possible" flags are used as a fast way to find possible DOS
66 #define FLAG_POSSIBLE1 16
67 #define FLAG_POSSIBLE2 32
68 #define FLAG_POSSIBLE3 64
69 #define FLAG_POSSIBLE4 128
71 /* by default have a max of 4096 entries in the cache. */
72 #ifndef MANGLE_CACHE_SIZE
73 #define MANGLE_CACHE_SIZE 4096
76 /* these tables are used to provide fast tests for characters */
77 static unsigned char char_flags[256];
79 #define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag))
81 /* we will use a very simple direct mapped prefix cache. The big
82 advantage of this cache structure is speed and low memory usage
84 The cache is indexed by the low-order bits of the hash, and confirmed by
85 hashing the resulting cache entry to match the known hash
87 static char **prefix_cache;
88 static u32 *prefix_cache_hashes;
90 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
91 const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
92 static unsigned char base_reverse[256];
93 #define base_forward(v) basechars[v]
95 /* the list of reserved dos names - all of these are illegal */
96 const char *reserved_names[] = { "AUX", "LOCK$", "CON", "COM1", "COM2", "COM3", "COM4",
97 "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL };
100 hash a string of the specified length. The string does not need to be
103 this hash needs to be fast with a low collision rate (what hash doesn't?)
105 static u32 mangle_hash(const char *key, unsigned length)
111 /* we have to uppercase here to ensure that the mangled name
112 doesn't depend on the case of the long name. Note that this
113 is the only place where we need to use a multi-byte string
115 strncpy(str, key, length);
119 /* the length of a multi-byte string can change after a strupper_m */
120 length = strlen(str);
122 /* Set the initial value from the key size. */
123 for (value = 0x238F13AF * length, i=0; i < length; i++) {
124 value = (value + (((unsigned char)str[i]) << (i*5 % 24)));
127 return (1103515243 * value + 12345);
131 initialise (ie. allocate) the prefix cache
133 static BOOL cache_init(void)
135 if (prefix_cache) return True;
137 prefix_cache = malloc(sizeof(char *) * MANGLE_CACHE_SIZE);
138 if (!prefix_cache) return False;
140 prefix_cache_hashes = malloc(sizeof(u32) * MANGLE_CACHE_SIZE);
141 if (!prefix_cache_hashes) return False;
143 memset(prefix_cache, 0, sizeof(char *) * MANGLE_CACHE_SIZE);
144 memset(prefix_cache_hashes, 0, sizeof(char *) * MANGLE_CACHE_SIZE);
149 insert an entry into the prefix cache. The string might not be null
151 static void cache_insert(const char *prefix, int length, u32 hash)
153 int i = hash % MANGLE_CACHE_SIZE;
155 if (prefix_cache[i]) {
156 free(prefix_cache[i]);
159 prefix_cache[i] = strndup(prefix, length);
160 prefix_cache_hashes[i] = hash;
164 lookup an entry in the prefix cache. Return NULL if not found.
166 static const char *cache_lookup(u32 hash)
168 int i = hash % MANGLE_CACHE_SIZE;
170 if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) {
174 /* yep, it matched */
175 return prefix_cache[i];
180 determine if a string is possibly in a mangled format, ignoring
183 In this algorithm, mangled names use only pure ascii characters (no
184 multi-byte) so we can avoid doing a UCS2 conversion
186 static BOOL is_mangled(const char *name)
190 M_DEBUG(0,("is_mangled %s\n", name));
192 /* the best distinguishing characteristic is the ~ */
193 if (name[6] != '~') return False;
195 /* check the length */
197 if (len > 12 || len < 8) return False;
199 /* check extension */
201 if (name[8] != '.') return False;
202 for (i=9; name[i]; i++) {
203 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
209 /* check first character */
210 if (! FLAG_CHECK(name[0], FLAG_ASCII)) {
214 /* check rest of hash */
215 if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
219 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
229 see if a filename is an allowable 8.3 name.
231 we are only going to allow ascii characters in 8.3 names, as this
232 simplifies things greatly (it means that we know the string won't
233 get larger when converted from UNIX to DOS formats)
235 static BOOL is_8_3(const char *name, BOOL check_case)
240 /* as a special case, the names '.' and '..' are allowable 8.3 names */
241 if (name[0] == '.') {
242 if (!name[1] || (name[1] == '.' && !name[2])) {
247 /* the simplest test is on the overall length of the
248 filename. Note that we deliberately use the ascii string
249 length (not the multi-byte one) as it is faster, and gives us
250 the result we need in this case. Using strlen_m would not
251 only be slower, it would be incorrect */
253 if (len > 12) return False;
255 /* find the '.'. Note that once again we use the non-multibyte
257 dot_p = strchr(name, '.');
260 /* if the name doesn't contain a '.' then its length
261 must be less than 8 */
266 int prefix_len, suffix_len;
268 /* if it does contain a dot then the prefix must be <=
269 8 and the suffix <= 3 in length */
270 prefix_len = PTR_DIFF(dot_p, name);
271 suffix_len = len - (prefix_len+1);
273 if (prefix_len > 8 || suffix_len > 3) {
277 /* a 8.3 name cannot contain more than 1 '.' */
278 if (strchr(dot_p+1, '.')) {
283 /* the length are all OK. Now check to see if the characters themselves are OK */
284 for (i=0; name[i]; i++) {
285 /* note that we allow wildcard petterns! */
286 if (!FLAG_CHECK(name[i], FLAG_ASCII|FLAG_WILDCARD)) {
291 /* it is a good 8.3 name */
297 reset the mangling cache on a smb.conf reload. This only really makes sense for
298 mangling backends that have parameters in smb.conf, and as this backend doesn't
299 this is a NULL operation
301 static void mangle_reset(void)
308 try to find a 8.3 name in the cache, and if found then
309 replace the string with the original long name.
311 The filename must be able to hold at least sizeof(fstring)
313 static BOOL check_cache(char *name)
315 u32 hash, multiplier;
320 /* make sure that this is a mangled name from this cache */
321 if (!is_mangled(name)) {
325 /* we need to extract the hash from the 8.3 name */
326 hash = base_reverse[(unsigned char)name[7]];
327 for (multiplier=36, i=5;i>=1;i--) {
328 u32 v = base_reverse[(unsigned char)name[i]];
329 hash += multiplier * v;
333 /* now look in the prefix cache for that hash */
334 prefix = cache_lookup(hash);
339 /* we found it - construct the full name */
340 strncpy(extension, name+9, 3);
343 M_DEBUG(0,("check_cache: %s -> %s.%s\n", name, prefix, extension));
344 slprintf(name, sizeof(fstring), "%s.%s", prefix, extension);
346 M_DEBUG(0,("check_cache: %s -> %s\n", name, prefix));
347 fstrcpy(name, prefix);
355 look for a DOS reserved name
357 static BOOL is_reserved_name(const char *name)
359 if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
360 FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
361 FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
362 FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
363 /* a likely match, scan the lot */
365 for (i=0; reserved_names[i]; i++) {
366 int len = strlen(reserved_names[i]);
367 /* note that we match on COM1 as well as COM1.foo */
368 if (strncasecmp(name, reserved_names[i], len) == 0 &&
369 (name[len] == '.' || name[len] == 0)) {
379 see if a filename is a legal long filename
381 static BOOL is_legal_name(const char *name)
384 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
394 the main forward mapping function, which converts a long filename to
397 if need83 is not set then we only do the mangling if the name is illegal
400 if cache83 is not set then we don't cache the result
402 the name parameter must be able to hold 13 bytes
404 static BOOL name_map(char *name, BOOL need83, BOOL cache83)
409 int extension_length, i;
414 /* reserved names are handled specially */
415 if (!is_reserved_name(name)) {
416 /* if the name is already a valid 8.3 name then we don't need to
418 if (is_8_3(name, False)) {
422 /* if the caller doesn't strictly need 8.3 then just check for illegal
424 if (!need83 && is_legal_name(name)) {
429 /* find the '.' if any */
430 dot_p = strchr(name, '.');
432 /* the leading character in the mangled name is taken from
433 the first character of the name, if it is ascii
434 otherwise '_' is used
437 if (! FLAG_CHECK(lead_char, FLAG_ASCII)) {
440 lead_char = toupper(lead_char);
442 /* the prefix is anything up to the first dot */
444 prefix_len = PTR_DIFF(dot_p, name);
446 prefix_len = strlen(name);
449 /* the extension of the mangled name is taken from the first 3
450 ascii chars after the dot */
451 extension_length = 0;
453 for (i=1; extension_length < 3 && dot_p[i]; i++) {
455 if (FLAG_CHECK(c, FLAG_ASCII)) {
456 extension[extension_length++] = toupper(c);
461 /* find the hash for this prefix */
462 v = hash = mangle_hash(name, prefix_len);
464 /* now form the mangled name. */
465 new_name[0] = lead_char;
466 new_name[7] = base_forward(v % 36);
468 for (i=5; i>=1; i--) {
470 new_name[i] = base_forward(v % 36);
473 /* add the extension */
474 if (extension_length) {
476 memcpy(&new_name[9], extension, extension_length);
477 new_name[9+extension_length] = 0;
483 /* put it in the cache */
484 cache_insert(name, prefix_len, hash);
487 M_DEBUG(0,("name_map: %s -> %s\n", name, new_name));
489 /* and overwrite the old name */
490 fstrcpy(name, new_name);
492 /* all done, we've managed to mangle it */
497 /* initialise the flags table
499 we allow only a very restricted set of characters as 'ascii' in this
500 mangling backend. This isn't a significant problem as modern clients
501 use the 'long' filenames anyway, and those don't have these
504 static void init_tables(void)
508 memset(char_flags, 0, sizeof(char_flags));
510 for (i=0;i<128;i++) {
511 if ((i >= '0' && i <= '9') ||
512 (i >= 'a' && i <= 'z') ||
513 (i >= 'A' && i <= 'Z')) {
514 char_flags[i] |= (FLAG_ASCII | FLAG_BASECHAR);
516 if (strchr("._-$~", i)) {
517 char_flags[i] |= FLAG_ASCII;
520 if (strchr("*\\/?<>|\":", i)) {
521 char_flags[i] |= FLAG_ILLEGAL;
524 if (strchr("*?\"<>", i)) {
525 char_flags[i] |= FLAG_WILDCARD;
529 memset(base_reverse, 0, sizeof(base_reverse));
531 base_reverse[(unsigned char)base_forward(i)] = i;
534 /* fill in the reserved names flags. These are used as a very
535 fast filter for finding possible DOS reserved filenames */
536 for (i=0; reserved_names[i]; i++) {
537 unsigned char c1, c2, c3, c4;
539 c1 = (unsigned char)reserved_names[i][0];
540 c2 = (unsigned char)reserved_names[i][1];
541 c3 = (unsigned char)reserved_names[i][2];
542 c4 = (unsigned char)reserved_names[i][3];
544 char_flags[c1] |= FLAG_POSSIBLE1;
545 char_flags[c2] |= FLAG_POSSIBLE2;
546 char_flags[c3] |= FLAG_POSSIBLE3;
547 char_flags[c4] |= FLAG_POSSIBLE4;
548 char_flags[tolower(c1)] |= FLAG_POSSIBLE1;
549 char_flags[tolower(c2)] |= FLAG_POSSIBLE2;
550 char_flags[tolower(c3)] |= FLAG_POSSIBLE3;
551 char_flags[tolower(c4)] |= FLAG_POSSIBLE4;
553 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
559 the following provides the abstraction layer to make it easier
560 to drop in an alternative mangling implementation */
561 static struct mangle_fns mangle_fns = {
569 /* return the methods for this mangling implementation */
570 struct mangle_fns *mangle_hash2_init(void)