Spelling fixes for lib/compression.
[sfrench/samba-autobuild/.git] / source3 / 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, see <http://www.gnu.org/licenses/>.
19 */
20
21 /*
22   this mangling scheme uses the following format
23
24   Annnn~n.AAA
25
26   where nnnnn is a base 36 hash, and A represents characters from the original string
27
28   The hash is taken of the leading part of the long filename, in uppercase
29
30   for simplicity, we only allow ascii characters in 8.3 names
31  */
32
33  /* hash alghorithm changed to FNV1 by idra@samba.org (Simo Sorce).
34   * see http://www.isthe.com/chongo/tech/comp/fnv/index.html for a
35   * discussion on Fowler / Noll / Vo (FNV) Hash by one of it's authors
36   */
37
38 /*
39   ===============================================================================
40   NOTE NOTE NOTE!!!
41
42   This file deliberately uses non-multibyte string functions in many places. This
43   is *not* a mistake. This code is multi-byte safe, but it gets this property
44   through some very subtle knowledge of the way multi-byte strings are encoded 
45   and the fact that this mangling algorithm only supports ascii characters in
46   8.3 names.
47
48   please don't convert this file to use the *_m() functions!!
49   ===============================================================================
50 */
51
52
53 #include "includes.h"
54 #include "smbd/globals.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 #define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag))
86
87 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
88 static const char basechars[36] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
89 #define base_forward(v) basechars[v]
90
91 /* the list of reserved dos names - all of these are illegal */
92 static const char * const reserved_names[] =
93 { "AUX", "LOCK$", "CON", "COM1", "COM2", "COM3", "COM4",
94   "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL };
95
96 /* 
97    hash a string of the specified length. The string does not need to be
98    null terminated 
99
100    this hash needs to be fast with a low collision rate (what hash doesn't?)
101 */
102 static unsigned int mangle_hash(const char *key, unsigned int length)
103 {
104         unsigned int value;
105         unsigned int   i;
106         fstring str;
107
108         /* we have to uppercase here to ensure that the mangled name
109            doesn't depend on the case of the long name. Note that this
110            is the only place where we need to use a multi-byte string
111            function */
112         length = MIN(length,sizeof(fstring)-1);
113         strncpy(str, key, length);
114         str[length] = 0;
115         strupper_m(str);
116
117         /* the length of a multi-byte string can change after a strupper_m */
118         length = strlen(str);
119
120         /* Set the initial value from the key size. */
121         for (value = FNV1_INIT, i=0; i < length; i++) {
122                 value *= (unsigned int)FNV1_PRIME;
123                 value ^= (unsigned int)(str[i]);
124         }
125
126         /* note that we force it to a 31 bit hash, to keep within the limits
127            of the 36^6 mangle space */
128         return value & ~0x80000000;  
129 }
130
131 /*
132   insert an entry into the prefix cache. The string might not be null
133   terminated */
134 static void cache_insert(const char *prefix, int length, unsigned int hash)
135 {
136         char *str = SMB_STRNDUP(prefix, length);
137
138         if (str == NULL) {
139                 return;
140         }
141
142         memcache_add(smbd_memcache(), MANGLE_HASH2_CACHE,
143                      data_blob_const(&hash, sizeof(hash)),
144                      data_blob_const(str, length+1));
145         SAFE_FREE(str);
146 }
147
148 /*
149   lookup an entry in the prefix cache. Return NULL if not found.
150 */
151 static char *cache_lookup(TALLOC_CTX *mem_ctx, unsigned int hash)
152 {
153         DATA_BLOB value;
154
155         if (!memcache_lookup(smbd_memcache(), MANGLE_HASH2_CACHE,
156                              data_blob_const(&hash, sizeof(hash)), &value)) {
157                 return NULL;
158         }
159
160         SMB_ASSERT((value.length > 0)
161                    && (value.data[value.length-1] == '\0'));
162
163         return talloc_strdup(mem_ctx, (char *)value.data);
164 }
165
166
167 /* 
168    determine if a string is possibly in a mangled format, ignoring
169    case 
170
171    In this algorithm, mangled names use only pure ascii characters (no
172    multi-byte) so we can avoid doing a UCS2 conversion 
173  */
174 static bool is_mangled_component(const char *name, size_t len)
175 {
176         unsigned int i;
177
178         M_DEBUG(10,("is_mangled_component %s (len %lu) ?\n", name, (unsigned long)len));
179
180         /* check the length */
181         if (len > 12 || len < 8)
182                 return False;
183
184         /* the best distinguishing characteristic is the ~ */
185         if (name[6] != '~')
186                 return False;
187
188         /* check extension */
189         if (len > 8) {
190                 if (name[8] != '.')
191                         return False;
192                 for (i=9; name[i] && i < len; i++) {
193                         if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
194                                 return False;
195                         }
196                 }
197         }
198         
199         /* check lead characters */
200         for (i=0;i<mangle_prefix;i++) {
201                 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
202                         return False;
203                 }
204         }
205         
206         /* check rest of hash */
207         if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
208                 return False;
209         }
210         for (i=mangle_prefix;i<6;i++) {
211                 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
212                         return False;
213                 }
214         }
215
216         M_DEBUG(10,("is_mangled_component %s (len %lu) -> yes\n", name, (unsigned long)len));
217
218         return True;
219 }
220
221
222
223 /* 
224    determine if a string is possibly in a mangled format, ignoring
225    case 
226
227    In this algorithm, mangled names use only pure ascii characters (no
228    multi-byte) so we can avoid doing a UCS2 conversion 
229
230    NOTE! This interface must be able to handle a path with unix
231    directory separators. It should return true if any component is
232    mangled
233  */
234 static bool is_mangled(const char *name, const struct share_params *parm)
235 {
236         const char *p;
237         const char *s;
238
239         M_DEBUG(10,("is_mangled %s ?\n", name));
240
241         for (s=name; (p=strchr(s, '/')); s=p+1) {
242                 if (is_mangled_component(s, PTR_DIFF(p, s))) {
243                         return True;
244                 }
245         }
246         
247         /* and the last part ... */
248         return is_mangled_component(s,strlen(s));
249 }
250
251
252 /* 
253    see if a filename is an allowable 8.3 name to return to the client.
254    Note this is not testing if this is a valid Samba mangled name, so
255    the rules are different for is_mangled.
256
257    we are only going to allow ascii characters in 8.3 names, as this
258    simplifies things greatly (it means that we know the string won't
259    get larger when converted from UNIX to DOS formats)
260 */
261
262 static char force_shortname_chars[] = " +,[];=";
263
264 static bool is_8_3(const char *name, bool check_case, bool allow_wildcards, const struct share_params *p)
265 {
266         int len, i;
267         char *dot_p;
268
269         /* as a special case, the names '.' and '..' are allowable 8.3 names */
270         if (name[0] == '.') {
271                 if (!name[1] || (name[1] == '.' && !name[2])) {
272                         return True;
273                 }
274         }
275
276         /* the simplest test is on the overall length of the
277          filename. Note that we deliberately use the ascii string
278          length (not the multi-byte one) as it is faster, and gives us
279          the result we need in this case. Using strlen_m would not
280          only be slower, it would be incorrect */
281         len = strlen(name);
282         if (len > 12)
283                 return False;
284
285         /* find the '.'. Note that once again we use the non-multibyte
286            function */
287         dot_p = strchr(name, '.');
288
289         if (!dot_p) {
290                 /* if the name doesn't contain a '.' then its length
291                    must be less than 8 */
292                 if (len > 8) {
293                         return False;
294                 }
295         } else {
296                 int prefix_len, suffix_len;
297
298                 /* if it does contain a dot then the prefix must be <=
299                    8 and the suffix <= 3 in length */
300                 prefix_len = PTR_DIFF(dot_p, name);
301                 suffix_len = len - (prefix_len+1);
302
303                 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) {
304                         return False;
305                 }
306
307                 /* a 8.3 name cannot contain more than 1 '.' */
308                 if (strchr(dot_p+1, '.')) {
309                         return False;
310                 }
311         }
312
313         /* the length are all OK. Now check to see if the characters themselves are OK */
314         for (i=0; name[i]; i++) {
315                 if (FLAG_CHECK(name[i], FLAG_ILLEGAL)) {
316                         return false;
317                 }
318                 /* note that we may allow wildcard petterns! */
319                 if (!allow_wildcards && FLAG_CHECK(name[i], FLAG_WILDCARD)) {
320                         return false;
321                 }
322                 if (((unsigned char)name[i]) > 0x7e) {
323                         return false;
324                 }
325                 if (strchr(force_shortname_chars, name[i])) {
326                         return false;
327                 }
328         }
329
330         /* it is a good 8.3 name */
331         return True;
332 }
333
334
335 /*
336   reset the mangling cache on a smb.conf reload. This only really makes sense for
337   mangling backends that have parameters in smb.conf, and as this backend doesn't
338   this is a NULL operation
339 */
340 static void mangle_reset(void)
341 {
342         /* noop */
343 }
344
345
346 /*
347   try to find a 8.3 name in the cache, and if found then
348   replace the string with the original long name.
349 */
350 static bool lookup_name_from_8_3(TALLOC_CTX *ctx,
351                         const char *name,
352                         char **pp_out, /* talloced on the given context. */
353                         const struct share_params *p)
354 {
355         unsigned int hash, multiplier;
356         unsigned int i;
357         char *prefix;
358         char extension[4];
359
360         *pp_out = NULL;
361
362         /* make sure that this is a mangled name from this cache */
363         if (!is_mangled(name, p)) {
364                 M_DEBUG(10,("lookup_name_from_8_3: %s -> not mangled\n", name));
365                 return False;
366         }
367
368         /* we need to extract the hash from the 8.3 name */
369         hash = base_reverse[(unsigned char)name[7]];
370         for (multiplier=36, i=5;i>=mangle_prefix;i--) {
371                 unsigned int v = base_reverse[(unsigned char)name[i]];
372                 hash += multiplier * v;
373                 multiplier *= 36;
374         }
375
376         /* now look in the prefix cache for that hash */
377         prefix = cache_lookup(ctx, hash);
378         if (!prefix) {
379                 M_DEBUG(10,("lookup_name_from_8_3: %s -> %08X -> not found\n",
380                                         name, hash));
381                 return False;
382         }
383
384         /* we found it - construct the full name */
385         if (name[8] == '.') {
386                 strncpy(extension, name+9, 3);
387                 extension[3] = 0;
388         } else {
389                 extension[0] = 0;
390         }
391
392         if (extension[0]) {
393                 M_DEBUG(10,("lookup_name_from_8_3: %s -> %s.%s\n",
394                                         name, prefix, extension));
395                 *pp_out = talloc_asprintf(ctx, "%s.%s", prefix, extension);
396         } else {
397                 M_DEBUG(10,("lookup_name_from_8_3: %s -> %s\n", name, prefix));
398                 *pp_out = talloc_strdup(ctx, prefix);
399         }
400
401         TALLOC_FREE(prefix);
402
403         if (!*pp_out) {
404                 M_DEBUG(0,("talloc_fail"));
405                 return False;
406         }
407
408         return True;
409 }
410
411 /*
412   look for a DOS reserved name
413 */
414 static bool is_reserved_name(const char *name)
415 {
416         if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
417             FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
418             FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
419             FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
420                 /* a likely match, scan the lot */
421                 int i;
422                 for (i=0; reserved_names[i]; i++) {
423                         int len = strlen(reserved_names[i]);
424                         /* note that we match on COM1 as well as COM1.foo */
425                         if (strnequal(name, reserved_names[i], len) &&
426                             (name[len] == '.' || name[len] == 0)) {
427                                 return True;
428                         }
429                 }
430         }
431
432         return False;
433 }
434
435 /*
436  See if a filename is a legal long filename.
437  A filename ending in a '.' is not legal unless it's "." or "..". JRA.
438  A filename ending in ' ' is not legal either. See bug id #2769.
439 */
440
441 static bool is_legal_name(const char *name)
442 {
443         const char *dot_pos = NULL;
444         bool alldots = True;
445         size_t numdots = 0;
446
447         while (*name) {
448                 if (((unsigned int)name[0]) > 128 && (name[1] != 0)) {
449                         /* Possible start of mb character. */
450                         char mbc[2];
451                         /*
452                          * Note that if CH_UNIX is utf8 a string may be 3
453                          * bytes, but this is ok as mb utf8 characters don't
454                          * contain embedded ascii bytes. We are really checking
455                          * for mb UNIX asian characters like Japanese (SJIS) here.
456                          * JRA.
457                          */
458                         if (convert_string(CH_UNIX, CH_UTF16LE, name, 2, mbc, 2, False) == 2) {
459                                 /* Was a good mb string. */
460                                 name += 2;
461                                 continue;
462                         }
463                 }
464
465                 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
466                         return False;
467                 }
468                 if (name[0] == '.') {
469                         dot_pos = name;
470                         numdots++;
471                 } else {
472                         alldots = False;
473                 }
474                 if ((name[0] == ' ') && (name[1] == '\0')) {
475                         /* Can't end in ' ' */
476                         return False;
477                 }
478                 name++;
479         }
480
481         if (dot_pos) {
482                 if (alldots && (numdots == 1 || numdots == 2))
483                         return True; /* . or .. is a valid name */
484
485                 /* A valid long name cannot end in '.' */
486                 if (dot_pos[1] == '\0')
487                         return False;
488         }
489         return True;
490 }
491
492 static bool must_mangle(const char *name,
493                         const struct share_params *p)
494 {
495         if (is_reserved_name(name)) {
496                 return True;
497         }
498         return !is_legal_name(name);
499 }
500
501 /*
502   the main forward mapping function, which converts a long filename to 
503   a 8.3 name
504
505   if cache83 is not set then we don't cache the result
506
507 */
508 static bool hash2_name_to_8_3(const char *name,
509                         char new_name[13],
510                         bool cache83,
511                         int default_case,
512                         const struct share_params *p)
513 {
514         char *dot_p;
515         char lead_chars[7];
516         char extension[4];
517         unsigned int extension_length, i;
518         unsigned int prefix_len;
519         unsigned int hash, v;
520
521         /* reserved names are handled specially */
522         if (!is_reserved_name(name)) {
523                 /* if the name is already a valid 8.3 name then we don't need to
524                  * change anything */
525                 if (is_legal_name(name) && is_8_3(name, False, False, p)) {
526                         safe_strcpy(new_name, name, 12);
527                         return True;
528                 }
529         }
530
531         /* find the '.' if any */
532         dot_p = strrchr(name, '.');
533
534         if (dot_p) {
535                 /* if the extension contains any illegal characters or
536                    is too long or zero length then we treat it as part
537                    of the prefix */
538                 for (i=0; i<4 && dot_p[i+1]; i++) {
539                         if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) {
540                                 dot_p = NULL;
541                                 break;
542                         }
543                 }
544                 if (i == 0 || i == 4) {
545                         dot_p = NULL;
546                 }
547         }
548
549         /* the leading characters in the mangled name is taken from
550            the first characters of the name, if they are ascii otherwise
551            '_' is used
552         */
553         for (i=0;i<mangle_prefix && name[i];i++) {
554                 lead_chars[i] = name[i];
555                 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) {
556                         lead_chars[i] = '_';
557                 }
558                 lead_chars[i] = toupper_ascii(lead_chars[i]);
559         }
560         for (;i<mangle_prefix;i++) {
561                 lead_chars[i] = '_';
562         }
563
564         /* the prefix is anything up to the first dot */
565         if (dot_p) {
566                 prefix_len = PTR_DIFF(dot_p, name);
567         } else {
568                 prefix_len = strlen(name);
569         }
570
571         /* the extension of the mangled name is taken from the first 3
572            ascii chars after the dot */
573         extension_length = 0;
574         if (dot_p) {
575                 for (i=1; extension_length < 3 && dot_p[i]; i++) {
576                         char c = dot_p[i];
577                         if (FLAG_CHECK(c, FLAG_ASCII)) {
578                                 extension[extension_length++] =
579                                         toupper_ascii(c);
580                         }
581                 }
582         }
583
584         /* find the hash for this prefix */
585         v = hash = mangle_hash(name, prefix_len);
586
587         /* now form the mangled name. */
588         for (i=0;i<mangle_prefix;i++) {
589                 new_name[i] = lead_chars[i];
590         }
591         new_name[7] = base_forward(v % 36);
592         new_name[6] = '~';
593         for (i=5; i>=mangle_prefix; i--) {
594                 v = v / 36;
595                 new_name[i] = base_forward(v % 36);
596         }
597
598         /* add the extension */
599         if (extension_length) {
600                 new_name[8] = '.';
601                 memcpy(&new_name[9], extension, extension_length);
602                 new_name[9+extension_length] = 0;
603         } else {
604                 new_name[8] = 0;
605         }
606
607         if (cache83) {
608                 /* put it in the cache */
609                 cache_insert(name, prefix_len, hash);
610         }
611
612         M_DEBUG(10,("hash2_name_to_8_3: %s -> %08X -> %s (cache=%d)\n",
613                    name, hash, new_name, cache83));
614
615         return True;
616 }
617
618 /* initialise the flags table
619
620   we allow only a very restricted set of characters as 'ascii' in this
621   mangling backend. This isn't a significant problem as modern clients
622   use the 'long' filenames anyway, and those don't have these
623   restrictions.
624 */
625 static void init_tables(void)
626 {
627         int i;
628
629         memset(char_flags, 0, sizeof(char_flags));
630
631         for (i=1;i<128;i++) {
632                 if (i <= 0x1f) {
633                         /* Control characters. */
634                         char_flags[i] |= FLAG_ILLEGAL;
635                 }
636
637                 if ((i >= '0' && i <= '9') ||
638                     (i >= 'a' && i <= 'z') ||
639                     (i >= 'A' && i <= 'Z')) {
640                         char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
641                 }
642                 if (strchr("_-$~", i)) {
643                         char_flags[i] |= FLAG_ASCII;
644                 }
645
646                 if (strchr("*\\/?<>|\":", i)) {
647                         char_flags[i] |= FLAG_ILLEGAL;
648                 }
649
650                 if (strchr("*?\"<>", i)) {
651                         char_flags[i] |= FLAG_WILDCARD;
652                 }
653         }
654
655         memset(base_reverse, 0, sizeof(base_reverse));
656         for (i=0;i<36;i++) {
657                 base_reverse[(unsigned char)base_forward(i)] = i;
658         }
659
660         /* fill in the reserved names flags. These are used as a very
661            fast filter for finding possible DOS reserved filenames */
662         for (i=0; reserved_names[i]; i++) {
663                 unsigned char c1, c2, c3, c4;
664
665                 c1 = (unsigned char)reserved_names[i][0];
666                 c2 = (unsigned char)reserved_names[i][1];
667                 c3 = (unsigned char)reserved_names[i][2];
668                 c4 = (unsigned char)reserved_names[i][3];
669
670                 char_flags[c1] |= FLAG_POSSIBLE1;
671                 char_flags[c2] |= FLAG_POSSIBLE2;
672                 char_flags[c3] |= FLAG_POSSIBLE3;
673                 char_flags[c4] |= FLAG_POSSIBLE4;
674                 char_flags[tolower_ascii(c1)] |= FLAG_POSSIBLE1;
675                 char_flags[tolower_ascii(c2)] |= FLAG_POSSIBLE2;
676                 char_flags[tolower_ascii(c3)] |= FLAG_POSSIBLE3;
677                 char_flags[tolower_ascii(c4)] |= FLAG_POSSIBLE4;
678
679                 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
680         }
681 }
682
683 /*
684   the following provides the abstraction layer to make it easier
685   to drop in an alternative mangling implementation */
686 static const struct mangle_fns mangle_hash2_fns = {
687         mangle_reset,
688         is_mangled,
689         must_mangle,
690         is_8_3,
691         lookup_name_from_8_3,
692         hash2_name_to_8_3
693 };
694
695 /* return the methods for this mangling implementation */
696 const struct mangle_fns *mangle_hash2_init(void)
697 {
698         /* the mangle prefix can only be in the mange 1 to 6 */
699         mangle_prefix = lp_mangle_prefix();
700         if (mangle_prefix > 6) {
701                 mangle_prefix = 6;
702         }
703         if (mangle_prefix < 1) {
704                 mangle_prefix = 1;
705         }
706
707         init_tables();
708         mangle_reset();
709
710         return &mangle_hash2_fns;
711 }
712
713 static void posix_mangle_reset(void)
714 {;}
715
716 static bool posix_is_mangled(const char *s, const struct share_params *p)
717 {
718         return False;
719 }
720
721 static bool posix_must_mangle(const char *s, const struct share_params *p)
722 {
723         return False;
724 }
725
726 static bool posix_is_8_3(const char *fname,
727                         bool check_case,
728                         bool allow_wildcards,
729                         const struct share_params *p)
730 {
731         return False;
732 }
733
734 static bool posix_lookup_name_from_8_3(TALLOC_CTX *ctx,
735                                 const char *in,
736                                 char **out, /* talloced on the given context. */
737                                 const struct share_params *p)
738 {
739         return False;
740 }
741
742 static bool posix_name_to_8_3(const char *in,
743                                 char out[13],
744                                 bool cache83,
745                                 int default_case,
746                                 const struct share_params *p)
747 {
748         memset(out, '\0', 13);
749         return True;
750 }
751
752 /* POSIX paths backend - no mangle. */
753 static const struct mangle_fns posix_mangle_fns = {
754         posix_mangle_reset,
755         posix_is_mangled,
756         posix_must_mangle,
757         posix_is_8_3,
758         posix_lookup_name_from_8_3,
759         posix_name_to_8_3
760 };
761
762 const struct mangle_fns *posix_mangle_init(void)
763 {
764         return &posix_mangle_fns;
765 }