r23432: Remove superfluous comment.
[Samba/bb.git] / source3 / smbd / mangle_hash2.c
bloba39f49ec796b3409a8adb6fd6453c51bff89ad0d
1 /*
2 Unix SMB/CIFS implementation.
3 new hash based name mangling implementation
4 Copyright (C) Andrew Tridgell 2002
5 Copyright (C) Simo Sorce 2002
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 this mangling scheme uses the following format
25 Annnn~n.AAA
27 where nnnnn is a base 36 hash, and A represents characters from the original string
29 The hash is taken of the leading part of the long filename, in uppercase
31 for simplicity, we only allow ascii characters in 8.3 names
34 /* hash alghorithm changed to FNV1 by idra@samba.org (Simo Sorce).
35 * see http://www.isthe.com/chongo/tech/comp/fnv/index.html for a
36 * discussion on Fowler / Noll / Vo (FNV) Hash by one of it's authors
40 ===============================================================================
41 NOTE NOTE NOTE!!!
43 This file deliberately uses non-multibyte string functions in many places. This
44 is *not* a mistake. This code is multi-byte safe, but it gets this property
45 through some very subtle knowledge of the way multi-byte strings are encoded
46 and the fact that this mangling algorithm only supports ascii characters in
47 8.3 names.
49 please don't convert this file to use the *_m() functions!!
50 ===============================================================================
54 #include "includes.h"
56 #if 1
57 #define M_DEBUG(level, x) DEBUG(level, x)
58 #else
59 #define M_DEBUG(level, x)
60 #endif
62 /* these flags are used to mark characters in as having particular
63 properties */
64 #define FLAG_BASECHAR 1
65 #define FLAG_ASCII 2
66 #define FLAG_ILLEGAL 4
67 #define FLAG_WILDCARD 8
69 /* the "possible" flags are used as a fast way to find possible DOS
70 reserved filenames */
71 #define FLAG_POSSIBLE1 16
72 #define FLAG_POSSIBLE2 32
73 #define FLAG_POSSIBLE3 64
74 #define FLAG_POSSIBLE4 128
76 /* by default have a max of 4096 entries in the cache. */
77 #ifndef MANGLE_CACHE_SIZE
78 #define MANGLE_CACHE_SIZE 4096
79 #endif
81 #define FNV1_PRIME 0x01000193
82 /*the following number is a fnv1 of the string: idra@samba.org 2002 */
83 #define FNV1_INIT 0xa6b93095
85 /* these tables are used to provide fast tests for characters */
86 static unsigned char char_flags[256];
88 #define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag))
91 this determines how many characters are used from the original filename
92 in the 8.3 mangled name. A larger value leads to a weaker hash and more collisions.
93 The largest possible value is 6.
95 static unsigned mangle_prefix;
97 /* we will use a very simple direct mapped prefix cache. The big
98 advantage of this cache structure is speed and low memory usage
100 The cache is indexed by the low-order bits of the hash, and confirmed by
101 hashing the resulting cache entry to match the known hash
103 static char **prefix_cache;
104 static unsigned int *prefix_cache_hashes;
106 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
107 static const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
108 static unsigned char base_reverse[256];
109 #define base_forward(v) basechars[v]
111 /* the list of reserved dos names - all of these are illegal */
112 static const char *reserved_names[] =
113 { "AUX", "LOCK$", "CON", "COM1", "COM2", "COM3", "COM4",
114 "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL };
117 hash a string of the specified length. The string does not need to be
118 null terminated
120 this hash needs to be fast with a low collision rate (what hash doesn't?)
122 static unsigned int mangle_hash(const char *key, unsigned int length)
124 unsigned int value;
125 unsigned int i;
126 fstring str;
128 /* we have to uppercase here to ensure that the mangled name
129 doesn't depend on the case of the long name. Note that this
130 is the only place where we need to use a multi-byte string
131 function */
132 length = MIN(length,sizeof(fstring)-1);
133 strncpy(str, key, length);
134 str[length] = 0;
135 strupper_m(str);
137 /* the length of a multi-byte string can change after a strupper_m */
138 length = strlen(str);
140 /* Set the initial value from the key size. */
141 for (value = FNV1_INIT, i=0; i < length; i++) {
142 value *= (unsigned int)FNV1_PRIME;
143 value ^= (unsigned int)(str[i]);
146 /* note that we force it to a 31 bit hash, to keep within the limits
147 of the 36^6 mangle space */
148 return value & ~0x80000000;
152 initialise (ie. allocate) the prefix cache
154 static BOOL cache_init(void)
156 if (prefix_cache) {
157 return True;
160 prefix_cache = SMB_CALLOC_ARRAY(char *,MANGLE_CACHE_SIZE);
161 if (!prefix_cache) {
162 return False;
165 prefix_cache_hashes = SMB_CALLOC_ARRAY(unsigned int, MANGLE_CACHE_SIZE);
166 if (!prefix_cache_hashes) {
167 return False;
170 return True;
174 insert an entry into the prefix cache. The string might not be null
175 terminated */
176 static void cache_insert(const char *prefix, int length, unsigned int hash)
178 int i = hash % MANGLE_CACHE_SIZE;
180 if (prefix_cache[i]) {
181 free(prefix_cache[i]);
184 prefix_cache[i] = SMB_STRNDUP(prefix, length);
185 prefix_cache_hashes[i] = hash;
189 lookup an entry in the prefix cache. Return NULL if not found.
191 static const char *cache_lookup(unsigned int hash)
193 int i = hash % MANGLE_CACHE_SIZE;
195 if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) {
196 return NULL;
199 /* yep, it matched */
200 return prefix_cache[i];
205 determine if a string is possibly in a mangled format, ignoring
206 case
208 In this algorithm, mangled names use only pure ascii characters (no
209 multi-byte) so we can avoid doing a UCS2 conversion
211 static BOOL is_mangled_component(const char *name, size_t len)
213 unsigned int i;
215 M_DEBUG(10,("is_mangled_component %s (len %lu) ?\n", name, (unsigned long)len));
217 /* check the length */
218 if (len > 12 || len < 8)
219 return False;
221 /* the best distinguishing characteristic is the ~ */
222 if (name[6] != '~')
223 return False;
225 /* check extension */
226 if (len > 8) {
227 if (name[8] != '.')
228 return False;
229 for (i=9; name[i] && i < len; i++) {
230 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
231 return False;
236 /* check lead characters */
237 for (i=0;i<mangle_prefix;i++) {
238 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
239 return False;
243 /* check rest of hash */
244 if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
245 return False;
247 for (i=mangle_prefix;i<6;i++) {
248 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
249 return False;
253 M_DEBUG(10,("is_mangled_component %s (len %lu) -> yes\n", name, (unsigned long)len));
255 return True;
261 determine if a string is possibly in a mangled format, ignoring
262 case
264 In this algorithm, mangled names use only pure ascii characters (no
265 multi-byte) so we can avoid doing a UCS2 conversion
267 NOTE! This interface must be able to handle a path with unix
268 directory separators. It should return true if any component is
269 mangled
271 static BOOL is_mangled(const char *name, const struct share_params *parm)
273 const char *p;
274 const char *s;
276 M_DEBUG(10,("is_mangled %s ?\n", name));
278 for (s=name; (p=strchr(s, '/')); s=p+1) {
279 if (is_mangled_component(s, PTR_DIFF(p, s))) {
280 return True;
284 /* and the last part ... */
285 return is_mangled_component(s,strlen(s));
290 see if a filename is an allowable 8.3 name.
292 we are only going to allow ascii characters in 8.3 names, as this
293 simplifies things greatly (it means that we know the string won't
294 get larger when converted from UNIX to DOS formats)
296 static BOOL is_8_3(const char *name, BOOL check_case, BOOL allow_wildcards, const struct share_params *p)
298 int len, i;
299 char *dot_p;
301 /* as a special case, the names '.' and '..' are allowable 8.3 names */
302 if (name[0] == '.') {
303 if (!name[1] || (name[1] == '.' && !name[2])) {
304 return True;
308 /* the simplest test is on the overall length of the
309 filename. Note that we deliberately use the ascii string
310 length (not the multi-byte one) as it is faster, and gives us
311 the result we need in this case. Using strlen_m would not
312 only be slower, it would be incorrect */
313 len = strlen(name);
314 if (len > 12)
315 return False;
317 /* find the '.'. Note that once again we use the non-multibyte
318 function */
319 dot_p = strchr(name, '.');
321 if (!dot_p) {
322 /* if the name doesn't contain a '.' then its length
323 must be less than 8 */
324 if (len > 8) {
325 return False;
327 } else {
328 int prefix_len, suffix_len;
330 /* if it does contain a dot then the prefix must be <=
331 8 and the suffix <= 3 in length */
332 prefix_len = PTR_DIFF(dot_p, name);
333 suffix_len = len - (prefix_len+1);
335 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) {
336 return False;
339 /* a 8.3 name cannot contain more than 1 '.' */
340 if (strchr(dot_p+1, '.')) {
341 return False;
345 /* the length are all OK. Now check to see if the characters themselves are OK */
346 for (i=0; name[i]; i++) {
347 /* note that we may allow wildcard petterns! */
348 if (!FLAG_CHECK(name[i], FLAG_ASCII|(allow_wildcards ? FLAG_WILDCARD : 0)) && name[i] != '.') {
349 return False;
353 /* it is a good 8.3 name */
354 return True;
359 reset the mangling cache on a smb.conf reload. This only really makes sense for
360 mangling backends that have parameters in smb.conf, and as this backend doesn't
361 this is a NULL operation
363 static void mangle_reset(void)
365 /* noop */
370 try to find a 8.3 name in the cache, and if found then
371 replace the string with the original long name.
373 static BOOL check_cache(char *name, size_t maxlen, const struct share_params *p)
375 unsigned int hash, multiplier;
376 unsigned int i;
377 const char *prefix;
378 char extension[4];
380 /* make sure that this is a mangled name from this cache */
381 if (!is_mangled(name, p)) {
382 M_DEBUG(10,("check_cache: %s -> not mangled\n", name));
383 return False;
386 /* we need to extract the hash from the 8.3 name */
387 hash = base_reverse[(unsigned char)name[7]];
388 for (multiplier=36, i=5;i>=mangle_prefix;i--) {
389 unsigned int v = base_reverse[(unsigned char)name[i]];
390 hash += multiplier * v;
391 multiplier *= 36;
394 /* now look in the prefix cache for that hash */
395 prefix = cache_lookup(hash);
396 if (!prefix) {
397 M_DEBUG(10,("check_cache: %s -> %08X -> not found\n", name, hash));
398 return False;
401 /* we found it - construct the full name */
402 if (name[8] == '.') {
403 strncpy(extension, name+9, 3);
404 extension[3] = 0;
405 } else {
406 extension[0] = 0;
409 if (extension[0]) {
410 M_DEBUG(10,("check_cache: %s -> %s.%s\n", name, prefix, extension));
411 slprintf(name, maxlen, "%s.%s", prefix, extension);
412 } else {
413 M_DEBUG(10,("check_cache: %s -> %s\n", name, prefix));
414 safe_strcpy(name, prefix, maxlen);
417 return True;
422 look for a DOS reserved name
424 static BOOL is_reserved_name(const char *name)
426 if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
427 FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
428 FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
429 FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
430 /* a likely match, scan the lot */
431 int i;
432 for (i=0; reserved_names[i]; i++) {
433 int len = strlen(reserved_names[i]);
434 /* note that we match on COM1 as well as COM1.foo */
435 if (strnequal(name, reserved_names[i], len) &&
436 (name[len] == '.' || name[len] == 0)) {
437 return True;
442 return False;
446 See if a filename is a legal long filename.
447 A filename ending in a '.' is not legal unless it's "." or "..". JRA.
448 A filename ending in ' ' is not legal either. See bug id #2769.
451 static BOOL is_legal_name(const char *name)
453 const char *dot_pos = NULL;
454 BOOL alldots = True;
455 size_t numdots = 0;
457 while (*name) {
458 if (((unsigned int)name[0]) > 128 && (name[1] != 0)) {
459 /* Possible start of mb character. */
460 char mbc[2];
462 * Note that if CH_UNIX is utf8 a string may be 3
463 * bytes, but this is ok as mb utf8 characters don't
464 * contain embedded ascii bytes. We are really checking
465 * for mb UNIX asian characters like Japanese (SJIS) here.
466 * JRA.
468 if (convert_string(CH_UNIX, CH_UTF16LE, name, 2, mbc, 2, False) == 2) {
469 /* Was a good mb string. */
470 name += 2;
471 continue;
475 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
476 return False;
478 if (name[0] == '.') {
479 dot_pos = name;
480 numdots++;
481 } else {
482 alldots = False;
484 if ((name[0] == ' ') && (name[1] == '\0')) {
485 /* Can't end in ' ' */
486 return False;
488 name++;
491 if (dot_pos) {
492 if (alldots && (numdots == 1 || numdots == 2))
493 return True; /* . or .. is a valid name */
495 /* A valid long name cannot end in '.' */
496 if (dot_pos[1] == '\0')
497 return False;
499 return True;
503 the main forward mapping function, which converts a long filename to
504 a 8.3 name
506 if need83 is not set then we only do the mangling if the name is illegal
507 as a long name
509 if cache83 is not set then we don't cache the result
511 the name parameter must be able to hold 13 bytes
513 static void name_map(fstring name, BOOL need83, BOOL cache83, int default_case, const struct share_params *p)
515 char *dot_p;
516 char lead_chars[7];
517 char extension[4];
518 unsigned int extension_length, i;
519 unsigned int prefix_len;
520 unsigned int hash, v;
521 char new_name[13];
523 /* reserved names are handled specially */
524 if (!is_reserved_name(name)) {
525 /* if the name is already a valid 8.3 name then we don't need to
526 do anything */
527 if (is_8_3(name, False, False, p)) {
528 return;
531 /* if the caller doesn't strictly need 8.3 then just check for illegal
532 filenames */
533 if (!need83 && is_legal_name(name)) {
534 return;
538 /* find the '.' if any */
539 dot_p = strrchr(name, '.');
541 if (dot_p) {
542 /* if the extension contains any illegal characters or
543 is too long or zero length then we treat it as part
544 of the prefix */
545 for (i=0; i<4 && dot_p[i+1]; i++) {
546 if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) {
547 dot_p = NULL;
548 break;
551 if (i == 0 || i == 4) dot_p = NULL;
554 /* the leading characters in the mangled name is taken from
555 the first characters of the name, if they are ascii otherwise
556 '_' is used
558 for (i=0;i<mangle_prefix && name[i];i++) {
559 lead_chars[i] = name[i];
560 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) {
561 lead_chars[i] = '_';
563 lead_chars[i] = toupper_ascii(lead_chars[i]);
565 for (;i<mangle_prefix;i++) {
566 lead_chars[i] = '_';
569 /* the prefix is anything up to the first dot */
570 if (dot_p) {
571 prefix_len = PTR_DIFF(dot_p, name);
572 } else {
573 prefix_len = strlen(name);
576 /* the extension of the mangled name is taken from the first 3
577 ascii chars after the dot */
578 extension_length = 0;
579 if (dot_p) {
580 for (i=1; extension_length < 3 && dot_p[i]; i++) {
581 char c = dot_p[i];
582 if (FLAG_CHECK(c, FLAG_ASCII)) {
583 extension[extension_length++] = toupper_ascii(c);
588 /* find the hash for this prefix */
589 v = hash = mangle_hash(name, prefix_len);
591 /* now form the mangled name. */
592 for (i=0;i<mangle_prefix;i++) {
593 new_name[i] = lead_chars[i];
595 new_name[7] = base_forward(v % 36);
596 new_name[6] = '~';
597 for (i=5; i>=mangle_prefix; i--) {
598 v = v / 36;
599 new_name[i] = base_forward(v % 36);
602 /* add the extension */
603 if (extension_length) {
604 new_name[8] = '.';
605 memcpy(&new_name[9], extension, extension_length);
606 new_name[9+extension_length] = 0;
607 } else {
608 new_name[8] = 0;
611 if (cache83) {
612 /* put it in the cache */
613 cache_insert(name, prefix_len, hash);
616 M_DEBUG(10,("name_map: %s -> %08X -> %s (cache=%d)\n",
617 name, hash, new_name, cache83));
619 /* and overwrite the old name */
620 fstrcpy(name, new_name);
622 /* all done, we've managed to mangle it */
626 /* initialise the flags table
628 we allow only a very restricted set of characters as 'ascii' in this
629 mangling backend. This isn't a significant problem as modern clients
630 use the 'long' filenames anyway, and those don't have these
631 restrictions.
633 static void init_tables(void)
635 int i;
637 memset(char_flags, 0, sizeof(char_flags));
639 for (i=1;i<128;i++) {
640 if (i <= 0x1f) {
641 /* Control characters. */
642 char_flags[i] |= FLAG_ILLEGAL;
645 if ((i >= '0' && i <= '9') ||
646 (i >= 'a' && i <= 'z') ||
647 (i >= 'A' && i <= 'Z')) {
648 char_flags[i] |= (FLAG_ASCII | FLAG_BASECHAR);
650 if (strchr("_-$~", i)) {
651 char_flags[i] |= FLAG_ASCII;
654 if (strchr("*\\/?<>|\":", i)) {
655 char_flags[i] |= FLAG_ILLEGAL;
658 if (strchr("*?\"<>", i)) {
659 char_flags[i] |= FLAG_WILDCARD;
663 memset(base_reverse, 0, sizeof(base_reverse));
664 for (i=0;i<36;i++) {
665 base_reverse[(unsigned char)base_forward(i)] = i;
668 /* fill in the reserved names flags. These are used as a very
669 fast filter for finding possible DOS reserved filenames */
670 for (i=0; reserved_names[i]; i++) {
671 unsigned char c1, c2, c3, c4;
673 c1 = (unsigned char)reserved_names[i][0];
674 c2 = (unsigned char)reserved_names[i][1];
675 c3 = (unsigned char)reserved_names[i][2];
676 c4 = (unsigned char)reserved_names[i][3];
678 char_flags[c1] |= FLAG_POSSIBLE1;
679 char_flags[c2] |= FLAG_POSSIBLE2;
680 char_flags[c3] |= FLAG_POSSIBLE3;
681 char_flags[c4] |= FLAG_POSSIBLE4;
682 char_flags[tolower_ascii(c1)] |= FLAG_POSSIBLE1;
683 char_flags[tolower_ascii(c2)] |= FLAG_POSSIBLE2;
684 char_flags[tolower_ascii(c3)] |= FLAG_POSSIBLE3;
685 char_flags[tolower_ascii(c4)] |= FLAG_POSSIBLE4;
687 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
692 the following provides the abstraction layer to make it easier
693 to drop in an alternative mangling implementation */
694 static struct mangle_fns mangle_fns = {
695 mangle_reset,
696 is_mangled,
697 is_8_3,
698 check_cache,
699 name_map
702 /* return the methods for this mangling implementation */
703 struct mangle_fns *mangle_hash2_init(void)
705 /* the mangle prefix can only be in the mange 1 to 6 */
706 mangle_prefix = lp_mangle_prefix();
707 if (mangle_prefix > 6) {
708 mangle_prefix = 6;
710 if (mangle_prefix < 1) {
711 mangle_prefix = 1;
714 init_tables();
715 mangle_reset();
717 if (!cache_init()) {
718 return NULL;
721 return &mangle_fns;
724 static void posix_mangle_reset(void)
727 static BOOL posix_is_mangled(const char *s, const struct share_params *p)
729 return False;
732 static BOOL posix_is_8_3(const char *fname, BOOL check_case, BOOL allow_wildcards, const struct share_params *p)
734 return False;
737 static BOOL posix_check_cache( char *s, size_t maxlen, const struct share_params *p )
739 return False;
742 static void posix_name_map(char *OutName, BOOL need83, BOOL cache83, int default_case, const struct share_params *p)
744 if (need83) {
745 memset(OutName, '\0', 13);
749 /* POSIX paths backend - no mangle. */
750 static struct mangle_fns posix_mangle_fns = {
751 posix_mangle_reset,
752 posix_is_mangled,
753 posix_is_8_3,
754 posix_check_cache,
755 posix_name_map
758 struct mangle_fns *posix_mangle_init(void)
760 return &posix_mangle_fns;