r23779: Change from v2 or later to v3 or later.
[kai/samba.git] / source / smbd / mangle_hash2.c
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
6    
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 3 of the License, or
10    (at your option) any later version.
11    
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.
16    
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.
20 */
21
22 /*
23   this mangling scheme uses the following format
24
25   Annnn~n.AAA
26
27   where nnnnn is a base 36 hash, and A represents characters from the original string
28
29   The hash is taken of the leading part of the long filename, in uppercase
30
31   for simplicity, we only allow ascii characters in 8.3 names
32  */
33
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
37   */
38
39 /*
40   ===============================================================================
41   NOTE NOTE NOTE!!!
42
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.
48
49   please don't convert this file to use the *_m() functions!!
50   ===============================================================================
51 */
52
53
54 #include "includes.h"
55
56 #if 1
57 #define M_DEBUG(level, x) DEBUG(level, x)
58 #else
59 #define M_DEBUG(level, x)
60 #endif
61
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
68
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
75
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
80
81 #define FNV1_PRIME 0x01000193
82 /*the following number is a fnv1 of the string: idra@samba.org 2002 */
83 #define FNV1_INIT  0xa6b93095
84
85 /* these tables are used to provide fast tests for characters */
86 static unsigned char char_flags[256];
87
88 #define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag))
89
90 /*
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.
94 */
95 static unsigned mangle_prefix;
96
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 
99
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
102 */
103 static char **prefix_cache;
104 static unsigned int *prefix_cache_hashes;
105
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]
110
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 };
115
116 /* 
117    hash a string of the specified length. The string does not need to be
118    null terminated 
119
120    this hash needs to be fast with a low collision rate (what hash doesn't?)
121 */
122 static unsigned int mangle_hash(const char *key, unsigned int length)
123 {
124         unsigned int value;
125         unsigned int   i;
126         fstring str;
127
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);
136
137         /* the length of a multi-byte string can change after a strupper_m */
138         length = strlen(str);
139
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]);
144         }
145
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;  
149 }
150
151 /* 
152    initialise (ie. allocate) the prefix cache
153  */
154 static BOOL cache_init(void)
155 {
156         if (prefix_cache) {
157                 return True;
158         }
159
160         prefix_cache = SMB_CALLOC_ARRAY(char *,MANGLE_CACHE_SIZE);
161         if (!prefix_cache) {
162                 return False;
163         }
164
165         prefix_cache_hashes = SMB_CALLOC_ARRAY(unsigned int, MANGLE_CACHE_SIZE);
166         if (!prefix_cache_hashes) {
167                 return False;
168         }
169
170         return True;
171 }
172
173 /*
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)
177 {
178         int i = hash % MANGLE_CACHE_SIZE;
179
180         if (prefix_cache[i]) {
181                 free(prefix_cache[i]);
182         }
183
184         prefix_cache[i] = SMB_STRNDUP(prefix, length);
185         prefix_cache_hashes[i] = hash;
186 }
187
188 /*
189   lookup an entry in the prefix cache. Return NULL if not found.
190 */
191 static const char *cache_lookup(unsigned int hash)
192 {
193         int i = hash % MANGLE_CACHE_SIZE;
194
195         if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) {
196                 return NULL;
197         }
198
199         /* yep, it matched */
200         return prefix_cache[i];
201 }
202
203
204 /* 
205    determine if a string is possibly in a mangled format, ignoring
206    case 
207
208    In this algorithm, mangled names use only pure ascii characters (no
209    multi-byte) so we can avoid doing a UCS2 conversion 
210  */
211 static BOOL is_mangled_component(const char *name, size_t len)
212 {
213         unsigned int i;
214
215         M_DEBUG(10,("is_mangled_component %s (len %lu) ?\n", name, (unsigned long)len));
216
217         /* check the length */
218         if (len > 12 || len < 8)
219                 return False;
220
221         /* the best distinguishing characteristic is the ~ */
222         if (name[6] != '~')
223                 return False;
224
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;
232                         }
233                 }
234         }
235         
236         /* check lead characters */
237         for (i=0;i<mangle_prefix;i++) {
238                 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
239                         return False;
240                 }
241         }
242         
243         /* check rest of hash */
244         if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
245                 return False;
246         }
247         for (i=mangle_prefix;i<6;i++) {
248                 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
249                         return False;
250                 }
251         }
252
253         M_DEBUG(10,("is_mangled_component %s (len %lu) -> yes\n", name, (unsigned long)len));
254
255         return True;
256 }
257
258
259
260 /* 
261    determine if a string is possibly in a mangled format, ignoring
262    case 
263
264    In this algorithm, mangled names use only pure ascii characters (no
265    multi-byte) so we can avoid doing a UCS2 conversion 
266
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
270  */
271 static BOOL is_mangled(const char *name, const struct share_params *parm)
272 {
273         const char *p;
274         const char *s;
275
276         M_DEBUG(10,("is_mangled %s ?\n", name));
277
278         for (s=name; (p=strchr(s, '/')); s=p+1) {
279                 if (is_mangled_component(s, PTR_DIFF(p, s))) {
280                         return True;
281                 }
282         }
283         
284         /* and the last part ... */
285         return is_mangled_component(s,strlen(s));
286 }
287
288
289 /* 
290    see if a filename is an allowable 8.3 name.
291
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)
295 */
296 static BOOL is_8_3(const char *name, BOOL check_case, BOOL allow_wildcards, const struct share_params *p)
297 {
298         int len, i;
299         char *dot_p;
300
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;
305                 }
306         }
307
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;
316
317         /* find the '.'. Note that once again we use the non-multibyte
318            function */
319         dot_p = strchr(name, '.');
320
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;
326                 }
327         } else {
328                 int prefix_len, suffix_len;
329
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);
334
335                 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) {
336                         return False;
337                 }
338
339                 /* a 8.3 name cannot contain more than 1 '.' */
340                 if (strchr(dot_p+1, '.')) {
341                         return False;
342                 }
343         }
344
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;
350                 }
351         }
352
353         /* it is a good 8.3 name */
354         return True;
355 }
356
357
358 /*
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
362 */
363 static void mangle_reset(void)
364 {
365         /* noop */
366 }
367
368
369 /*
370   try to find a 8.3 name in the cache, and if found then
371   replace the string with the original long name. 
372 */
373 static BOOL check_cache(char *name, size_t maxlen, const struct share_params *p)
374 {
375         unsigned int hash, multiplier;
376         unsigned int i;
377         const char *prefix;
378         char extension[4];
379
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;
384         }
385
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;
392         }
393
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;
399         }
400
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;
407         }
408
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);
415         }
416
417         return True;
418 }
419
420
421 /*
422   look for a DOS reserved name
423 */
424 static BOOL is_reserved_name(const char *name)
425 {
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;
438                         }
439                 }
440         }
441
442         return False;
443 }
444
445 /*
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.
449 */
450
451 static BOOL is_legal_name(const char *name)
452 {
453         const char *dot_pos = NULL;
454         BOOL alldots = True;
455         size_t numdots = 0;
456
457         while (*name) {
458                 if (((unsigned int)name[0]) > 128 && (name[1] != 0)) {
459                         /* Possible start of mb character. */
460                         char mbc[2];
461                         /*
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.
467                          */
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;
472                         }
473                 }
474
475                 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
476                         return False;
477                 }
478                 if (name[0] == '.') {
479                         dot_pos = name;
480                         numdots++;
481                 } else {
482                         alldots = False;
483                 }
484                 if ((name[0] == ' ') && (name[1] == '\0')) {
485                         /* Can't end in ' ' */
486                         return False;
487                 }
488                 name++;
489         }
490
491         if (dot_pos) {
492                 if (alldots && (numdots == 1 || numdots == 2))
493                         return True; /* . or .. is a valid name */
494
495                 /* A valid long name cannot end in '.' */
496                 if (dot_pos[1] == '\0')
497                         return False;
498         }
499         return True;
500 }
501
502 /*
503   the main forward mapping function, which converts a long filename to 
504   a 8.3 name
505
506   if need83 is not set then we only do the mangling if the name is illegal
507   as a long name
508
509   if cache83 is not set then we don't cache the result
510
511   the name parameter must be able to hold 13 bytes
512 */
513 static void name_map(fstring name, BOOL need83, BOOL cache83, int default_case, const struct share_params *p)
514 {
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];
522
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;
529                 }
530
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;
535                 }
536         }
537
538         /* find the '.' if any */
539         dot_p = strrchr(name, '.');
540
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;
549                         }
550                 }
551                 if (i == 0 || i == 4) dot_p = NULL;
552         }
553
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
557         */
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] = '_';
562                 }
563                 lead_chars[i] = toupper_ascii(lead_chars[i]);
564         }
565         for (;i<mangle_prefix;i++) {
566                 lead_chars[i] = '_';
567         }
568
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);
574         }
575
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);
584                         }
585                 }
586         }
587            
588         /* find the hash for this prefix */
589         v = hash = mangle_hash(name, prefix_len);
590
591         /* now form the mangled name. */
592         for (i=0;i<mangle_prefix;i++) {
593                 new_name[i] = lead_chars[i];
594         }
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);
600         }
601
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;
609         }
610
611         if (cache83) {
612                 /* put it in the cache */
613                 cache_insert(name, prefix_len, hash);
614         }
615
616         M_DEBUG(10,("name_map: %s -> %08X -> %s (cache=%d)\n", 
617                    name, hash, new_name, cache83));
618
619         /* and overwrite the old name */
620         fstrcpy(name, new_name);
621
622         /* all done, we've managed to mangle it */
623 }
624
625
626 /* initialise the flags table 
627
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. 
632 */
633 static void init_tables(void)
634 {
635         int i;
636
637         memset(char_flags, 0, sizeof(char_flags));
638
639         for (i=1;i<128;i++) {
640                 if (i <= 0x1f) {
641                         /* Control characters. */
642                         char_flags[i] |= FLAG_ILLEGAL;
643                 }
644
645                 if ((i >= '0' && i <= '9') || 
646                     (i >= 'a' && i <= 'z') || 
647                     (i >= 'A' && i <= 'Z')) {
648                         char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
649                 }
650                 if (strchr("_-$~", i)) {
651                         char_flags[i] |= FLAG_ASCII;
652                 }
653
654                 if (strchr("*\\/?<>|\":", i)) {
655                         char_flags[i] |= FLAG_ILLEGAL;
656                 }
657
658                 if (strchr("*?\"<>", i)) {
659                         char_flags[i] |= FLAG_WILDCARD;
660                 }
661         }
662
663         memset(base_reverse, 0, sizeof(base_reverse));
664         for (i=0;i<36;i++) {
665                 base_reverse[(unsigned char)base_forward(i)] = i;
666         }       
667
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;
672
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];
677
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;
686
687                 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
688         }
689 }
690
691 /*
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
700 };
701
702 /* return the methods for this mangling implementation */
703 struct mangle_fns *mangle_hash2_init(void)
704 {
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;
709         }
710         if (mangle_prefix < 1) {
711                 mangle_prefix = 1;
712         }
713
714         init_tables();
715         mangle_reset();
716
717         if (!cache_init()) {
718                 return NULL;
719         }
720
721         return &mangle_fns;
722 }
723
724 static void posix_mangle_reset(void)
725 {;}
726
727 static BOOL posix_is_mangled(const char *s, const struct share_params *p)
728 {
729         return False;
730 }
731
732 static BOOL posix_is_8_3(const char *fname, BOOL check_case, BOOL allow_wildcards, const struct share_params *p)
733 {
734         return False;
735 }
736
737 static BOOL posix_check_cache( char *s, size_t maxlen, const struct share_params *p )
738 {
739         return False;
740 }
741
742 static void posix_name_map(char *OutName, BOOL need83, BOOL cache83, int default_case, const struct share_params *p)
743 {
744         if (need83) {
745                 memset(OutName, '\0', 13);
746         }
747 }
748
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
756 };
757
758 struct mangle_fns *posix_mangle_init(void)
759 {
760         return &posix_mangle_fns;
761 }