r3544: fixed some #include lines to make them more consistent
[kamenim/samba.git] / source4 / ntvfs / posix / pvfs_shortname.c
1 /* 
2    Unix SMB/CIFS implementation.
3
4    POSIX NTVFS backend - 8.3 name routines
5
6    Copyright (C) Andrew Tridgell 2004
7
8    This program is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2 of the License, or
11    (at your option) any later version.
12    
13    This program is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17    
18    You should have received a copy of the GNU General Public License
19    along with this program; if not, write to the Free Software
20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 */
22
23 #include "includes.h"
24 #include "vfs_posix.h"
25 #include "system/iconv.h"
26
27 /*
28   this mangling scheme uses the following format
29
30   Annnn~n.AAA
31
32   where nnnnn is a base 36 hash, and A represents characters from the original string
33
34   The hash is taken of the leading part of the long filename, in uppercase
35
36   for simplicity, we only allow ascii characters in 8.3 names
37 */
38
39  /* hash alghorithm changed to FNV1 by idra@samba.org (Simo Sorce).
40   * see http://www.isthe.com/chongo/tech/comp/fnv/index.html for a
41   * discussion on Fowler / Noll / Vo (FNV) Hash by one of it's authors
42   */
43
44 /*
45   ===============================================================================
46   NOTE NOTE NOTE!!!
47
48   This file deliberately uses non-multibyte string functions in many places. This
49   is *not* a mistake. This code is multi-byte safe, but it gets this property
50   through some very subtle knowledge of the way multi-byte strings are encoded 
51   and the fact that this mangling algorithm only supports ascii characters in
52   8.3 names.
53
54   please don't convert this file to use the *_m() functions!!
55   ===============================================================================
56 */
57
58
59 #if 1
60 #define M_DEBUG(level, x) DEBUG(level, x)
61 #else
62 #define M_DEBUG(level, x)
63 #endif
64
65 /* these flags are used to mark characters in as having particular
66    properties */
67 #define FLAG_BASECHAR 1
68 #define FLAG_ASCII 2
69 #define FLAG_ILLEGAL 4
70 #define FLAG_WILDCARD 8
71
72 /* the "possible" flags are used as a fast way to find possible DOS
73    reserved filenames */
74 #define FLAG_POSSIBLE1 16
75 #define FLAG_POSSIBLE2 32
76 #define FLAG_POSSIBLE3 64
77 #define FLAG_POSSIBLE4 128
78
79 /* by default have a max of 512 entries in the cache. */
80 #ifndef MANGLE_CACHE_SIZE
81 #define MANGLE_CACHE_SIZE 512
82 #endif
83
84 #define DEFAULT_MANGLE_PREFIX 4
85
86 #define FNV1_PRIME 0x01000193
87 /*the following number is a fnv1 of the string: idra@samba.org 2002 */
88 #define FNV1_INIT  0xa6b93095
89
90 #define MANGLE_BASECHARS "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
91
92 #define FLAG_CHECK(c, flag) (ctx->char_flags[(uint8_t)(c)] & (flag))
93
94 static const char *reserved_names[] = 
95 { "AUX", "CON", "COM1", "COM2", "COM3", "COM4",
96   "LPT1", "LPT2", "LPT3", "NUL", "PRN", NULL };
97
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 uint32_t mangle_hash(struct pvfs_mangle_context *ctx,
106                             const char *key, size_t length)
107 {
108         uint32_t value = FNV1_INIT;
109         codepoint_t c;
110         size_t c_size;
111
112         while (*key && length--) {
113                 c = next_codepoint(key, &c_size);
114                 c = toupper_w(c);
115                 value *= (uint32_t)FNV1_PRIME;
116                 value ^= (uint32_t)c;
117                 key += c_size;
118         }
119
120         return (value % ctx->mangle_modulus);
121 }
122
123 /*
124   insert an entry into the prefix cache. The string might not be null
125   terminated */
126 static void cache_insert(struct pvfs_mangle_context *ctx,
127                          const char *prefix, int length, uint32_t hash)
128 {
129         int i = hash % MANGLE_CACHE_SIZE;
130
131         if (ctx->prefix_cache[i]) {
132                 talloc_free(ctx->prefix_cache[i]);
133         }
134
135         ctx->prefix_cache[i] = talloc_strndup(ctx->prefix_cache, prefix, length);
136         ctx->prefix_cache_hashes[i] = hash;
137 }
138
139 /*
140   lookup an entry in the prefix cache. Return NULL if not found.
141 */
142 static const char *cache_lookup(struct pvfs_mangle_context *ctx, uint32_t hash)
143 {
144         int i = hash % MANGLE_CACHE_SIZE;
145
146
147         if (!ctx->prefix_cache[i] || hash != ctx->prefix_cache_hashes[i]) {
148                 return NULL;
149         }
150
151         /* yep, it matched */
152         return ctx->prefix_cache[i];
153 }
154
155
156 /* 
157    determine if a string is possibly in a mangled format, ignoring
158    case 
159
160    In this algorithm, mangled names use only pure ascii characters (no
161    multi-byte) so we can avoid doing a UCS2 conversion 
162  */
163 static BOOL is_mangled_component(struct pvfs_mangle_context *ctx,
164                                  const char *name, size_t len)
165 {
166         unsigned int i;
167
168         M_DEBUG(10,("is_mangled_component %s (len %u) ?\n", name, (unsigned int)len));
169
170         /* check the length */
171         if (len > 12 || len < 8)
172                 return False;
173
174         /* the best distinguishing characteristic is the ~ */
175         if (name[6] != '~')
176                 return False;
177
178         /* check extension */
179         if (len > 8) {
180                 if (name[8] != '.')
181                         return False;
182                 for (i=9; name[i] && i < len; i++) {
183                         if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
184                                 return False;
185                         }
186                 }
187         }
188         
189         /* check lead characters */
190         for (i=0;i<ctx->mangle_prefix;i++) {
191                 if (! FLAG_CHECK(name[i], FLAG_ASCII)) {
192                         return False;
193                 }
194         }
195         
196         /* check rest of hash */
197         if (! FLAG_CHECK(name[7], FLAG_BASECHAR)) {
198                 return False;
199         }
200         for (i=ctx->mangle_prefix;i<6;i++) {
201                 if (! FLAG_CHECK(name[i], FLAG_BASECHAR)) {
202                         return False;
203                 }
204         }
205
206         M_DEBUG(10,("is_mangled_component %s (len %u) -> yes\n", name, (unsigned int)len));
207
208         return True;
209 }
210
211
212
213 /* 
214    determine if a string is possibly in a mangled format, ignoring
215    case 
216
217    In this algorithm, mangled names use only pure ascii characters (no
218    multi-byte) so we can avoid doing a UCS2 conversion 
219
220    NOTE! This interface must be able to handle a path with unix
221    directory separators. It should return true if any component is
222    mangled
223  */
224 static BOOL is_mangled(struct pvfs_mangle_context *ctx, const char *name)
225 {
226         const char *p;
227         const char *s;
228
229         M_DEBUG(10,("is_mangled %s ?\n", name));
230
231         for (s=name; (p=strchr(s, '/')); s=p+1) {
232                 if (is_mangled_component(ctx, s, PTR_DIFF(p, s))) {
233                         return True;
234                 }
235         }
236         
237         /* and the last part ... */
238         return is_mangled_component(ctx, s, strlen(s));
239 }
240
241
242 /* 
243    see if a filename is an allowable 8.3 name.
244
245    we are only going to allow ascii characters in 8.3 names, as this
246    simplifies things greatly (it means that we know the string won't
247    get larger when converted from UNIX to DOS formats)
248 */
249 static BOOL is_8_3(struct pvfs_mangle_context *ctx,
250                    const char *name, BOOL check_case, BOOL allow_wildcards)
251 {
252         int len, i;
253         char *dot_p;
254
255         /* as a special case, the names '.' and '..' are allowable 8.3 names */
256         if (name[0] == '.') {
257                 if (!name[1] || (name[1] == '.' && !name[2])) {
258                         return True;
259                 }
260         }
261
262         /* the simplest test is on the overall length of the
263          filename. Note that we deliberately use the ascii string
264          length (not the multi-byte one) as it is faster, and gives us
265          the result we need in this case. Using strlen_m would not
266          only be slower, it would be incorrect */
267         len = strlen(name);
268         if (len > 12)
269                 return False;
270
271         /* find the '.'. Note that once again we use the non-multibyte
272            function */
273         dot_p = strchr(name, '.');
274
275         if (!dot_p) {
276                 /* if the name doesn't contain a '.' then its length
277                    must be less than 8 */
278                 if (len > 8) {
279                         return False;
280                 }
281         } else {
282                 int prefix_len, suffix_len;
283
284                 /* if it does contain a dot then the prefix must be <=
285                    8 and the suffix <= 3 in length */
286                 prefix_len = PTR_DIFF(dot_p, name);
287                 suffix_len = len - (prefix_len+1);
288
289                 if (prefix_len > 8 || suffix_len > 3 || suffix_len == 0) {
290                         return False;
291                 }
292
293                 /* a 8.3 name cannot contain more than 1 '.' */
294                 if (strchr(dot_p+1, '.')) {
295                         return False;
296                 }
297         }
298
299         /* the length are all OK. Now check to see if the characters themselves are OK */
300         for (i=0; name[i]; i++) {
301                 /* note that we may allow wildcard petterns! */
302                 if (!FLAG_CHECK(name[i], FLAG_ASCII|(allow_wildcards ? FLAG_WILDCARD : 0)) && 
303                     name[i] != '.') {
304                         return False;
305                 }
306         }
307
308         /* it is a good 8.3 name */
309         return True;
310 }
311
312
313 /*
314   try to find a 8.3 name in the cache, and if found then
315   return the original long name. 
316 */
317 static const char *check_cache(struct pvfs_mangle_context *ctx, 
318                                const char *name)
319 {
320         uint32_t hash, multiplier;
321         unsigned int i;
322         const char *prefix;
323         char extension[4];
324
325         /* make sure that this is a mangled name from this cache */
326         if (!is_mangled(ctx, name)) {
327                 M_DEBUG(10,("check_cache: %s -> not mangled\n", name));
328                 return NULL;
329         }
330
331         /* we need to extract the hash from the 8.3 name */
332         hash = ctx->base_reverse[(unsigned char)name[7]];
333         for (multiplier=36, i=5;i>=ctx->mangle_prefix;i--) {
334                 uint32_t v = ctx->base_reverse[(unsigned char)name[i]];
335                 hash += multiplier * v;
336                 multiplier *= 36;
337         }
338
339         /* now look in the prefix cache for that hash */
340         prefix = cache_lookup(ctx, hash);
341         if (!prefix) {
342                 M_DEBUG(10,("check_cache: %s -> %08X -> not found\n", name, hash));
343                 return NULL;
344         }
345
346         /* we found it - construct the full name */
347         if (name[8] == '.') {
348                 strncpy(extension, name+9, 3);
349                 extension[3] = 0;
350         } else {
351                 extension[0] = 0;
352         }
353
354         if (extension[0]) {
355                 return talloc_asprintf(ctx, "%s.%s", prefix, extension);
356         }
357
358         return talloc_strdup(ctx, prefix);
359 }
360
361
362 /*
363   look for a DOS reserved name
364 */
365 static BOOL is_reserved_name(struct pvfs_mangle_context *ctx, const char *name)
366 {
367         if (FLAG_CHECK(name[0], FLAG_POSSIBLE1) &&
368             FLAG_CHECK(name[1], FLAG_POSSIBLE2) &&
369             FLAG_CHECK(name[2], FLAG_POSSIBLE3) &&
370             FLAG_CHECK(name[3], FLAG_POSSIBLE4)) {
371                 /* a likely match, scan the lot */
372                 int i;
373                 for (i=0; reserved_names[i]; i++) {
374                         if (strcasecmp(name, reserved_names[i]) == 0) {
375                                 return True;
376                         }
377                 }
378         }
379
380         return False;
381 }
382
383
384 /*
385  See if a filename is a legal long filename.
386  A filename ending in a '.' is not legal unless it's "." or "..". JRA.
387 */
388 static BOOL is_legal_name(struct pvfs_mangle_context *ctx, const char *name)
389 {
390         while (*name) {
391                 size_t c_size;
392                 codepoint_t c = next_codepoint(name, &c_size);
393                 if (c == INVALID_CODEPOINT) {
394                         return False;
395                 }
396                 /* all high chars are OK */
397                 if (c >= 128) {
398                         name += c_size;
399                         continue;
400                 }
401                 if (FLAG_CHECK(c, FLAG_ILLEGAL)) {
402                         return False;
403                 }
404                 name += c_size;
405         }
406
407         return True;
408 }
409
410 /*
411   the main forward mapping function, which converts a long filename to 
412   a 8.3 name
413
414   if need83 is not set then we only do the mangling if the name is illegal
415   as a long name
416
417   if cache83 is not set then we don't cache the result
418
419   return NULL if we don't need to do any conversion
420 */
421 static char *name_map(struct pvfs_mangle_context *ctx,
422                       const char *name, BOOL need83, BOOL cache83)
423 {
424         char *dot_p;
425         char lead_chars[7];
426         char extension[4];
427         unsigned int extension_length, i;
428         unsigned int prefix_len;
429         uint32_t hash, v;
430         char *new_name;
431         const char *basechars = MANGLE_BASECHARS;
432
433         /* reserved names are handled specially */
434         if (!is_reserved_name(ctx, name)) {
435                 /* if the name is already a valid 8.3 name then we don't need to 
436                    do anything */
437                 if (is_8_3(ctx, name, False, False)) {
438                         return NULL;
439                 }
440
441                 /* if the caller doesn't strictly need 8.3 then just check for illegal 
442                    filenames */
443                 if (!need83 && is_legal_name(ctx, name)) {
444                         return NULL;
445                 }
446         }
447
448         /* find the '.' if any */
449         dot_p = strrchr(name, '.');
450
451         if (dot_p) {
452                 /* if the extension contains any illegal characters or
453                    is too long or zero length then we treat it as part
454                    of the prefix */
455                 for (i=0; i<4 && dot_p[i+1]; i++) {
456                         if (! FLAG_CHECK(dot_p[i+1], FLAG_ASCII)) {
457                                 dot_p = NULL;
458                                 break;
459                         }
460                 }
461                 if (i == 0 || i == 4) dot_p = NULL;
462         }
463
464         /* the leading characters in the mangled name is taken from
465            the first characters of the name, if they are ascii otherwise
466            '_' is used
467         */
468         for (i=0;i<ctx->mangle_prefix && name[i];i++) {
469                 lead_chars[i] = name[i];
470                 if (! FLAG_CHECK(lead_chars[i], FLAG_ASCII)) {
471                         lead_chars[i] = '_';
472                 }
473                 lead_chars[i] = toupper(lead_chars[i]);
474         }
475         for (;i<ctx->mangle_prefix;i++) {
476                 lead_chars[i] = '_';
477         }
478
479         /* the prefix is anything up to the first dot */
480         if (dot_p) {
481                 prefix_len = PTR_DIFF(dot_p, name);
482         } else {
483                 prefix_len = strlen(name);
484         }
485
486         /* the extension of the mangled name is taken from the first 3
487            ascii chars after the dot */
488         extension_length = 0;
489         if (dot_p) {
490                 for (i=1; extension_length < 3 && dot_p[i]; i++) {
491                         char c = dot_p[i];
492                         if (FLAG_CHECK(c, FLAG_ASCII)) {
493                                 extension[extension_length++] = toupper(c);
494                         }
495                 }
496         }
497            
498         /* find the hash for this prefix */
499         v = hash = mangle_hash(ctx, name, prefix_len);
500
501         new_name = talloc_array_p(ctx, char, 13);
502         if (new_name == NULL) {
503                 return NULL;
504         }
505
506         /* now form the mangled name. */
507         for (i=0;i<ctx->mangle_prefix;i++) {
508                 new_name[i] = lead_chars[i];
509         }
510         new_name[7] = basechars[v % 36];
511         new_name[6] = '~';      
512         for (i=5; i>=ctx->mangle_prefix; i--) {
513                 v = v / 36;
514                 new_name[i] = basechars[v % 36];
515         }
516
517         /* add the extension */
518         if (extension_length) {
519                 new_name[8] = '.';
520                 memcpy(&new_name[9], extension, extension_length);
521                 new_name[9+extension_length] = 0;
522         } else {
523                 new_name[8] = 0;
524         }
525
526         if (cache83) {
527                 /* put it in the cache */
528                 cache_insert(ctx, name, prefix_len, hash);
529         }
530
531         M_DEBUG(10,("name_map: %s -> %08X -> %s (cache=%d)\n", 
532                    name, hash, new_name, cache83));
533
534         return new_name;
535 }
536
537
538 /* initialise the flags table 
539
540   we allow only a very restricted set of characters as 'ascii' in this
541   mangling backend. This isn't a significant problem as modern clients
542   use the 'long' filenames anyway, and those don't have these
543   restrictions. 
544 */
545 static void init_tables(struct pvfs_mangle_context *ctx)
546 {
547         const char *basechars = MANGLE_BASECHARS;
548         int i;
549         /* the list of reserved dos names - all of these are illegal */
550
551         ZERO_STRUCT(ctx->char_flags);
552
553         for (i=1;i<128;i++) {
554                 if ((i >= '0' && i <= '9') || 
555                     (i >= 'a' && i <= 'z') || 
556                     (i >= 'A' && i <= 'Z')) {
557                         ctx->char_flags[i] |=  (FLAG_ASCII | FLAG_BASECHAR);
558                 }
559                 if (strchr("_-$~", i)) {
560                         ctx->char_flags[i] |= FLAG_ASCII;
561                 }
562
563                 if (strchr("*\\/?<>|\":", i)) {
564                         ctx->char_flags[i] |= FLAG_ILLEGAL;
565                 }
566
567                 if (strchr("*?\"<>", i)) {
568                         ctx->char_flags[i] |= FLAG_WILDCARD;
569                 }
570         }
571
572         ZERO_STRUCT(ctx->base_reverse);
573         for (i=0;i<36;i++) {
574                 ctx->base_reverse[(uint8_t)basechars[i]] = i;
575         }       
576
577         /* fill in the reserved names flags. These are used as a very
578            fast filter for finding possible DOS reserved filenames */
579         for (i=0; reserved_names[i]; i++) {
580                 unsigned char c1, c2, c3, c4;
581
582                 c1 = (unsigned char)reserved_names[i][0];
583                 c2 = (unsigned char)reserved_names[i][1];
584                 c3 = (unsigned char)reserved_names[i][2];
585                 c4 = (unsigned char)reserved_names[i][3];
586
587                 ctx->char_flags[c1] |= FLAG_POSSIBLE1;
588                 ctx->char_flags[c2] |= FLAG_POSSIBLE2;
589                 ctx->char_flags[c3] |= FLAG_POSSIBLE3;
590                 ctx->char_flags[c4] |= FLAG_POSSIBLE4;
591                 ctx->char_flags[tolower(c1)] |= FLAG_POSSIBLE1;
592                 ctx->char_flags[tolower(c2)] |= FLAG_POSSIBLE2;
593                 ctx->char_flags[tolower(c3)] |= FLAG_POSSIBLE3;
594                 ctx->char_flags[tolower(c4)] |= FLAG_POSSIBLE4;
595
596                 ctx->char_flags[(unsigned char)'.'] |= FLAG_POSSIBLE4;
597         }
598
599         ctx->mangle_modulus = 1;
600         for (i=0;i<(7-ctx->mangle_prefix);i++) {
601                 ctx->mangle_modulus *= 36;
602         }
603 }
604
605 /* 
606    initialise the mangling code 
607  */
608 NTSTATUS pvfs_mangle_init(struct pvfs_state *pvfs)
609 {
610         struct pvfs_mangle_context *ctx;
611
612         ctx = talloc_p(pvfs, struct pvfs_mangle_context);
613         if (ctx == NULL) {
614                 return NT_STATUS_NO_MEMORY;
615         }
616         ctx->prefix_cache = talloc_array_p(ctx, char *, MANGLE_CACHE_SIZE);
617         if (ctx->prefix_cache == NULL) {
618                 return NT_STATUS_NO_MEMORY;
619         }
620         ctx->prefix_cache_hashes = talloc_array_p(ctx, uint32_t, MANGLE_CACHE_SIZE);
621         if (ctx->prefix_cache_hashes == NULL) {
622                 return NT_STATUS_NO_MEMORY;
623         }
624
625         memset(ctx->prefix_cache, 0, sizeof(char *)*MANGLE_CACHE_SIZE);
626         memset(ctx->prefix_cache_hashes, 0, sizeof(uint32_t)*MANGLE_CACHE_SIZE);
627
628         ctx->mangle_prefix = lp_parm_int(-1, "mangle", "prefix");
629         if (ctx->mangle_prefix < 0 || ctx->mangle_prefix > 6) {
630                 ctx->mangle_prefix = DEFAULT_MANGLE_PREFIX;
631         }
632
633         init_tables(ctx);
634
635         pvfs->mangle_ctx = ctx;
636
637         return NT_STATUS_OK;
638 }
639
640
641 /*
642   return the short name for a component of a full name
643 */
644 char *pvfs_short_name_component(struct pvfs_state *pvfs, const char *name)
645 {
646         return name_map(pvfs->mangle_ctx, name, True, True);
647 }
648
649
650 /*
651   return the short name for a given entry in a directory
652 */
653 const char *pvfs_short_name(struct pvfs_state *pvfs, TALLOC_CTX *mem_ctx, 
654                             struct pvfs_filename *name)
655 {
656         char *p = strrchr(name->full_name, '/');
657         char *ret = pvfs_short_name_component(pvfs, p+1);
658         if (ret == NULL) {
659                 return p+1;
660         }
661         talloc_steal(mem_ctx, ret);
662         return ret;
663 }
664
665 /*
666   lookup a mangled name, returning the original long name if present
667   in the cache
668 */
669 char *pvfs_mangled_lookup(struct pvfs_state *pvfs, TALLOC_CTX *mem_ctx, 
670                           const char *name)
671 {
672         const char *ret;
673         ret = check_cache(pvfs->mangle_ctx, name);
674         if (ret) {
675                 return talloc_steal(mem_ctx, ret);
676         }
677         return NULL;
678 }
679
680
681 /*
682   look for a DOS reserved name
683 */
684 BOOL pvfs_is_reserved_name(struct pvfs_state *pvfs, const char *name)
685 {
686         return is_reserved_name(pvfs->mangle_ctx, name);
687 }
688
689
690 /*
691   see if a component of a filename could be a mangled name from our
692   mangling code
693 */
694 BOOL pvfs_is_mangled_component(struct pvfs_state *pvfs, const char *name)
695 {
696         return is_mangled_component(pvfs->mangle_ctx, name, strlen(name));
697 }