96ca7360b89d0d0dbd93934e6603aab896ef6f58
[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    
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.
10    
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.
15    
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.
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
34 /*
35   ===============================================================================
36   NOTE NOTE NOTE!!!
37
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
42   8.3 names.
43
44   please don't convert this file to use the *_m() functions!!
45   ===============================================================================
46 */
47
48
49 #include "includes.h"
50
51 #if 0
52 #define M_DEBUG(level, x) DEBUG(level, x)
53 #else
54 #define M_DEBUG(level, x)
55 #endif
56
57 /* these flags are used to mark characters in as having particular
58    properties */
59 #define FLAG_BASECHAR 1
60 #define FLAG_ASCII 2
61 #define FLAG_ILLEGAL 4
62 #define FLAG_WILDCARD 8
63
64 /* the "possible" flags are used as a fast way to find possible DOS
65    reserved filenames */
66 #define FLAG_POSSIBLE1 16
67 #define FLAG_POSSIBLE2 32
68 #define FLAG_POSSIBLE3 64
69 #define FLAG_POSSIBLE4 128
70
71 /* by default have a max of 4096 entries in the cache. */
72 #ifndef MANGLE_CACHE_SIZE
73 #define MANGLE_CACHE_SIZE 4096
74 #endif
75
76 /* these tables are used to provide fast tests for characters */
77 static unsigned char char_flags[256];
78
79 #define FLAG_CHECK(c, flag) (char_flags[(unsigned char)(c)] & (flag))
80
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 
83
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
86 */
87 static char **prefix_cache;
88 static u32 *prefix_cache_hashes;
89
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]
94
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 };
98
99 /* 
100    hash a string of the specified length. The string does not need to be
101    null terminated 
102
103    this hash needs to be fast with a low collision rate (what hash doesn't?)
104 */
105 static u32 mangle_hash(const char *key, unsigned length)
106 {
107         u32 value;
108         u32   i;
109         fstring str;
110
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
114            function */
115         strncpy(str, key, length);
116         str[length] = 0;
117         strupper_m(str);
118
119         /* the length of a multi-byte string can change after a strupper_m */
120         length = strlen(str);
121
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)));
125         }
126
127         /* note that we force it to a 31 bit hash, to keep within the limits
128            of the 36^6 mangle space */
129         return (1103515243 * value + 12345) & ~0x80000000;  
130 }
131
132 /* 
133    initialise (ie. allocate) the prefix cache
134  */
135 static BOOL cache_init(void)
136 {
137         if (prefix_cache) return True;
138
139         prefix_cache = malloc(sizeof(char *) * MANGLE_CACHE_SIZE);
140         if (!prefix_cache) return False;
141
142         prefix_cache_hashes = malloc(sizeof(u32) * MANGLE_CACHE_SIZE);
143         if (!prefix_cache_hashes) return False;
144
145         memset(prefix_cache, 0, sizeof(char *) * MANGLE_CACHE_SIZE);
146         memset(prefix_cache_hashes, 0, sizeof(char *) * MANGLE_CACHE_SIZE);
147         return True;
148 }
149
150 /*
151   insert an entry into the prefix cache. The string might not be null
152   terminated */
153 static void cache_insert(const char *prefix, int length, u32 hash)
154 {
155         int i = hash % MANGLE_CACHE_SIZE;
156
157         if (prefix_cache[i]) {
158                 free(prefix_cache[i]);
159         }
160
161         prefix_cache[i] = strndup(prefix, length);
162         prefix_cache_hashes[i] = hash;
163 }
164
165 /*
166   lookup an entry in the prefix cache. Return NULL if not found.
167 */
168 static const char *cache_lookup(u32 hash)
169 {
170         int i = hash % MANGLE_CACHE_SIZE;
171
172         if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) {
173                 return NULL;
174         }
175
176         /* yep, it matched */
177         return prefix_cache[i];
178 }
179
180
181 /* 
182    determine if a string is possibly in a mangled format, ignoring
183    case 
184
185    In this algorithm, mangled names use only pure ascii characters (no
186    multi-byte) so we can avoid doing a UCS2 conversion 
187 */
188 static BOOL is_mangled(const char *name)
189 {
190         int len, i;
191
192         M_DEBUG(0,("is_mangled %s ?\n", name));
193
194         /* the best distinguishing characteristic is the ~ */
195         if (name[6] != '~') return False;
196
197         /* check the length */
198         len = strlen(name);
199         if (len > 12 || len < 8) return False;
200
201         /* check extension */
202         if (len > 8) {
203                 if (name[8] != '.') return False;
204                 for (i=9; name[i]; i++) {
205                         if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
206                                 return False;
207                         }
208                 }
209         }
210         
211         /* check first character */
212         if (! FLAG_CHECK(name[0], FLAG_ASCII)) {
213                 return False;
214         }
215         
216         /* check rest of hash */
217         if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
218                 return False;
219         }
220         for (i=1;i<6;i++) {
221                 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
222                         return False;
223                 }
224         }
225
226         M_DEBUG(0,("is_mangled %s -> yes\n", name));
227
228         return True;
229 }
230
231
232 /* 
233    see if a filename is an allowable 8.3 name.
234
235    we are only going to allow ascii characters in 8.3 names, as this
236    simplifies things greatly (it means that we know the string won't
237    get larger when converted from UNIX to DOS formats)
238 */
239 static BOOL is_8_3(const char *name, BOOL check_case)
240 {
241         int len, i;
242         char *dot_p;
243
244         /* as a special case, the names '.' and '..' are allowable 8.3 names */
245         if (name[0] == '.') {
246                 if (!name[1] || (name[1] == '.' && !name[2])) {
247                         return True;
248                 }
249         }
250
251         /* the simplest test is on the overall length of the
252          filename. Note that we deliberately use the ascii string
253          length (not the multi-byte one) as it is faster, and gives us
254          the result we need in this case. Using strlen_m would not
255          only be slower, it would be incorrect */
256         len = strlen(name);
257         if (len > 12) return False;
258
259         /* find the '.'. Note that once again we use the non-multibyte
260            function */
261         dot_p = strchr(name, '.');
262
263         if (!dot_p) {
264                 /* if the name doesn't contain a '.' then its length
265                    must be less than 8 */
266                 if (len > 8) {
267                         return False;
268                 }
269         } else {
270                 int prefix_len, suffix_len;
271
272                 /* if it does contain a dot then the prefix must be <=
273                    8 and the suffix <= 3 in length */
274                 prefix_len = PTR_DIFF(dot_p, name);
275                 suffix_len = len - (prefix_len+1);
276
277                 if (prefix_len > 8 || suffix_len > 3) {
278                         return False;
279                 }
280
281                 /* a 8.3 name cannot contain more than 1 '.' */
282                 if (strchr(dot_p+1, '.')) {
283                         return False;
284                 }
285         }
286
287         /* the length are all OK. Now check to see if the characters themselves are OK */
288         for (i=0; name[i]; i++) {
289                 /* note that we allow wildcard petterns! */
290                 if (!FLAG_CHECK(name[i], FLAG_ASCII|FLAG_WILDCARD) && name[i] != '.') {
291                         return False;
292                 }
293         }
294
295         /* it is a good 8.3 name */
296         return True;
297 }
298
299
300 /*
301   reset the mangling cache on a smb.conf reload. This only really makes sense for
302   mangling backends that have parameters in smb.conf, and as this backend doesn't
303   this is a NULL operation
304 */
305 static void mangle_reset(void)
306 {
307         /* noop */
308 }
309
310
311 /*
312   try to find a 8.3 name in the cache, and if found then
313   replace the string with the original long name. 
314
315   The filename must be able to hold at least sizeof(fstring) 
316 */
317 static BOOL check_cache(char *name)
318 {
319         u32 hash, multiplier;
320         int i;
321         const char *prefix;
322         char extension[4];
323
324         /* make sure that this is a mangled name from this cache */
325         if (!is_mangled(name)) {
326                 M_DEBUG(0,("check_cache: %s -> not mangled\n", name));
327                 return False;
328         }
329
330         /* we need to extract the hash from the 8.3 name */
331         hash = base_reverse[(unsigned char)name[7]];
332         for (multiplier=36, i=5;i>=1;i--) {
333                 u32 v = base_reverse[(unsigned char)name[i]];
334                 hash += multiplier * v;
335                 multiplier *= 36;
336         }
337
338         /* now look in the prefix cache for that hash */
339         prefix = cache_lookup(hash);
340         if (!prefix) {
341                 M_DEBUG(0,("check_cache: %s -> %08X -> not found\n", name, hash));
342                 return False;
343         }
344
345         /* we found it - construct the full name */
346         strncpy(extension, name+9, 3);
347
348         if (extension[0]) {
349                 M_DEBUG(0,("check_cache: %s -> %s.%s\n", name, prefix, extension));
350                 slprintf(name, sizeof(fstring), "%s.%s", prefix, extension);
351         } else {
352                 M_DEBUG(0,("check_cache: %s -> %s\n", name, prefix));
353                 fstrcpy(name, prefix);
354         }
355
356         return True;
357 }
358
359
360 /*
361   look for a DOS reserved name
362 */
363 static BOOL is_reserved_name(const char *name)
364 {
365         if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
366             FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
367             FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
368             FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
369                 /* a likely match, scan the lot */
370                 int i;
371                 for (i=0; reserved_names[i]; i++) {
372                         int len = strlen(reserved_names[i]);
373                         /* note that we match on COM1 as well as COM1.foo */
374                         if (strncasecmp(name, reserved_names[i], len) == 0 &&
375                             (name[len] == '.' || name[len] == 0)) {
376                                 return True;
377                         }
378                 }
379         }
380
381         return False;
382 }
383
384 /*
385   see if a filename is a legal long filename
386 */
387 static BOOL is_legal_name(const char *name)
388 {
389         while (*name) {
390                 if (FLAG_CHECK(name[0], FLAG_ILLEGAL)) {
391                         return False;
392                 }
393                 name++;
394         }
395
396         return True;
397 }
398
399 /*
400   the main forward mapping function, which converts a long filename to 
401   a 8.3 name
402
403   if need83 is not set then we only do the mangling if the name is illegal
404   as a long name
405
406   if cache83 is not set then we don't cache the result
407
408   the name parameter must be able to hold 13 bytes
409 */
410 static BOOL name_map(char *name, BOOL need83, BOOL cache83)
411 {
412         char *dot_p;
413         char lead_char;
414         char extension[4];
415         int extension_length, i;
416         int prefix_len;
417         u32 hash, v;
418         char new_name[13];
419
420         /* reserved names are handled specially */
421         if (!is_reserved_name(name)) {
422                 /* if the name is already a valid 8.3 name then we don't need to 
423                    do anything */
424                 if (is_8_3(name, False)) {
425                         return True;
426                 }
427
428                 /* if the caller doesn't strictly need 8.3 then just check for illegal 
429                    filenames */
430                 if (!need83 && is_legal_name(name)) {
431                         return True;
432                 }
433         }
434
435         /* find the '.' if any */
436         dot_p = strrchr(name, '.');
437
438         /* the leading character in the mangled name is taken from
439            the first character of the name, if it is ascii 
440            otherwise '_' is used
441         */
442         lead_char = name[0];
443         if (! FLAG_CHECK(lead_char, FLAG_ASCII)) {
444                 lead_char = '_';
445         }
446         lead_char = toupper(lead_char);
447
448         /* the prefix is anything up to the first dot */
449         if (dot_p) {
450                 prefix_len = PTR_DIFF(dot_p, name);
451         } else {
452                 prefix_len = strlen(name);
453         }
454
455         /* the extension of the mangled name is taken from the first 3
456            ascii chars after the dot */
457         extension_length = 0;
458         if (dot_p) {
459                 for (i=1; extension_length < 3 && dot_p[i]; i++) {
460                         char c = dot_p[i];
461                         if (FLAG_CHECK(c, FLAG_ASCII)) {
462                                 extension[extension_length++] = toupper(c);
463                         }
464                 }
465         }
466            
467         /* find the hash for this prefix */
468         v = hash = mangle_hash(name, prefix_len);
469
470         /* now form the mangled name. */
471         new_name[0] = lead_char;
472         new_name[7] = base_forward(v % 36);
473         new_name[6] = '~';      
474         for (i=5; i>=1; i--) {
475                 v = v / 36;
476                 new_name[i] = base_forward(v % 36);
477         }
478
479         /* add the extension */
480         if (extension_length) {
481                 new_name[8] = '.';
482                 memcpy(&new_name[9], extension, extension_length);
483                 new_name[9+extension_length] = 0;
484         } else {
485                 new_name[8] = 0;
486         }
487
488         if (cache83) {
489                 /* put it in the cache */
490                 cache_insert(name, prefix_len, hash);
491         }
492
493         M_DEBUG(0,("name_map: %s -> %08X -> %s (cache=%d)\n", 
494                    name, hash, new_name, cache83));
495
496         /* and overwrite the old name */
497         fstrcpy(name, new_name);
498
499         /* all done, we've managed to mangle it */
500         return True;
501 }
502
503
504 /* initialise the flags table 
505
506   we allow only a very restricted set of characters as 'ascii' in this
507   mangling backend. This isn't a significant problem as modern clients
508   use the 'long' filenames anyway, and those don't have these
509   restrictions. 
510 */
511 static void init_tables(void)
512 {
513         int i;
514
515         memset(char_flags, 0, sizeof(char_flags));
516
517         for (i=0;i<128;i++) {
518                 if ((i >= '0' && i <= '9') || 
519                     (i >= 'a' && i <= 'z') || 
520                     (i >= 'A' && i <= 'Z')) {
521                         char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
522                 }
523                 if (strchr("_-$~", i)) {
524                         char_flags[i] |= FLAG_ASCII;
525                 }
526
527                 if (strchr("*\\/?<>|\":", i)) {
528                         char_flags[i] |= FLAG_ILLEGAL;
529                 }
530
531                 if (strchr("*?\"<>", i)) {
532                         char_flags[i] |= FLAG_WILDCARD;
533                 }
534         }
535
536         memset(base_reverse, 0, sizeof(base_reverse));
537         for (i=0;i<36;i++) {
538                 base_reverse[(unsigned char)base_forward(i)] = i;
539         }       
540
541         /* fill in the reserved names flags. These are used as a very
542            fast filter for finding possible DOS reserved filenames */
543         for (i=0; reserved_names[i]; i++) {
544                 unsigned char c1, c2, c3, c4;
545
546                 c1 = (unsigned char)reserved_names[i][0];
547                 c2 = (unsigned char)reserved_names[i][1];
548                 c3 = (unsigned char)reserved_names[i][2];
549                 c4 = (unsigned char)reserved_names[i][3];
550
551                 char_flags[c1] |= FLAG_POSSIBLE1;
552                 char_flags[c2] |= FLAG_POSSIBLE2;
553                 char_flags[c3] |= FLAG_POSSIBLE3;
554                 char_flags[c4] |= FLAG_POSSIBLE4;
555                 char_flags[tolower(c1)] |= FLAG_POSSIBLE1;
556                 char_flags[tolower(c2)] |= FLAG_POSSIBLE2;
557                 char_flags[tolower(c3)] |= FLAG_POSSIBLE3;
558                 char_flags[tolower(c4)] |= FLAG_POSSIBLE4;
559
560                 char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
561         }
562 }
563
564
565 /*
566   the following provides the abstraction layer to make it easier
567   to drop in an alternative mangling implementation */
568 static struct mangle_fns mangle_fns = {
569         is_mangled,
570         is_8_3,
571         mangle_reset,
572         check_cache,
573         name_map
574 };
575
576 /* return the methods for this mangling implementation */
577 struct mangle_fns *mangle_hash2_init(void)
578 {
579         init_tables();
580         mangle_reset();
581
582         if (!cache_init()) {
583                 return NULL;
584         }
585
586         return &mangle_fns;
587 }