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