30b64108df127d8b112de346fa019cf1e51b36d7
[sven/exfat-utils.git] / libexfat / lookup.c
1 /*
2         lookup.c (02.09.09)
3         exFAT file system implementation library.
4
5         Free exFAT implementation.
6         Copyright (C) 2010-2016  Andrew Nayenko
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 along
19         with this program; if not, write to the Free Software Foundation, Inc.,
20         51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 */
22
23 #include "exfat.h"
24 #include <string.h>
25 #include <errno.h>
26 #include <inttypes.h>
27
28 int exfat_opendir(struct exfat* ef, struct exfat_node* dir,
29                 struct exfat_iterator* it)
30 {
31         int rc;
32
33         exfat_get_node(dir);
34         it->parent = dir;
35         it->current = NULL;
36         rc = exfat_cache_directory(ef, dir);
37         if (rc != 0)
38                 exfat_put_node(ef, dir);
39         return rc;
40 }
41
42 void exfat_closedir(struct exfat* ef, struct exfat_iterator* it)
43 {
44         exfat_put_node(ef, it->parent);
45         it->parent = NULL;
46         it->current = NULL;
47 }
48
49 struct exfat_node* exfat_readdir(struct exfat* ef, struct exfat_iterator* it)
50 {
51         if (it->current == NULL)
52                 it->current = it->parent->child;
53         else
54                 it->current = it->current->next;
55
56         if (it->current != NULL)
57                 return exfat_get_node(it->current);
58         else
59                 return NULL;
60 }
61
62 static int compare_char(struct exfat* ef, uint16_t a, uint16_t b)
63 {
64         return (int) ef->upcase[a] - (int) ef->upcase[b];
65 }
66
67 static int compare_name(struct exfat* ef, const le16_t* a, const le16_t* b)
68 {
69         while (le16_to_cpu(*a) && le16_to_cpu(*b))
70         {
71                 int rc = compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b));
72                 if (rc != 0)
73                         return rc;
74                 a++;
75                 b++;
76         }
77         return compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b));
78 }
79
80 static int lookup_name(struct exfat* ef, struct exfat_node* parent,
81                 struct exfat_node** node, const char* name, size_t n)
82 {
83         struct exfat_iterator it;
84         le16_t buffer[EXFAT_NAME_MAX + 1];
85         int rc;
86
87         *node = NULL;
88
89         rc = utf8_to_utf16(buffer, name, EXFAT_NAME_MAX, n);
90         if (rc != 0)
91                 return rc;
92
93         rc = exfat_opendir(ef, parent, &it);
94         if (rc != 0)
95                 return rc;
96         while ((*node = exfat_readdir(ef, &it)))
97         {
98                 if (compare_name(ef, buffer, (*node)->name) == 0)
99                 {
100                         exfat_closedir(ef, &it);
101                         return 0;
102                 }
103                 exfat_put_node(ef, *node);
104         }
105         exfat_closedir(ef, &it);
106         return -ENOENT;
107 }
108
109 static size_t get_comp(const char* path, const char** comp)
110 {
111         const char* end;
112
113         *comp = path + strspn(path, "/");                               /* skip leading slashes */
114         end = strchr(*comp, '/');
115         if (end == NULL)
116                 return strlen(*comp);
117         else
118                 return end - *comp;
119 }
120
121 int exfat_lookup(struct exfat* ef, struct exfat_node** node,
122                 const char* path)
123 {
124         struct exfat_node* parent;
125         const char* p;
126         size_t n;
127         int rc;
128
129         /* start from the root directory */
130         parent = *node = exfat_get_node(ef->root);
131         for (p = path; (n = get_comp(p, &p)); p += n)
132         {
133                 if (n == 1 && *p == '.')                                /* skip "." component */
134                         continue;
135                 rc = lookup_name(ef, parent, node, p, n);
136                 if (rc != 0)
137                 {
138                         exfat_put_node(ef, parent);
139                         return rc;
140                 }
141                 exfat_put_node(ef, parent);
142                 parent = *node;
143         }
144         return 0;
145 }
146
147 static bool is_last_comp(const char* comp, size_t length)
148 {
149         const char* p = comp + length;
150
151         return get_comp(p, &p) == 0;
152 }
153
154 static bool is_allowed(const char* comp, size_t length)
155 {
156         size_t i;
157
158         for (i = 0; i < length; i++)
159                 switch (comp[i])
160                 {
161                 case 0x01 ... 0x1f:
162                 case '/':
163                 case '\\':
164                 case ':':
165                 case '*':
166                 case '?':
167                 case '"':
168                 case '<':
169                 case '>':
170                 case '|':
171                         return false;
172                 }
173         return true;
174 }
175
176 int exfat_split(struct exfat* ef, struct exfat_node** parent,
177                 struct exfat_node** node, le16_t* name, const char* path)
178 {
179         const char* p;
180         size_t n;
181         int rc;
182
183         memset(name, 0, (EXFAT_NAME_MAX + 1) * sizeof(le16_t));
184         *parent = *node = exfat_get_node(ef->root);
185         for (p = path; (n = get_comp(p, &p)); p += n)
186         {
187                 if (n == 1 && *p == '.')
188                         continue;
189                 if (is_last_comp(p, n))
190                 {
191                         if (!is_allowed(p, n))
192                         {
193                                 /* contains characters that are not allowed */
194                                 exfat_put_node(ef, *parent);
195                                 return -ENOENT;
196                         }
197                         rc = utf8_to_utf16(name, p, EXFAT_NAME_MAX, n);
198                         if (rc != 0)
199                         {
200                                 exfat_put_node(ef, *parent);
201                                 return rc;
202                         }
203
204                         rc = lookup_name(ef, *parent, node, p, n);
205                         if (rc != 0 && rc != -ENOENT)
206                         {
207                                 exfat_put_node(ef, *parent);
208                                 return rc;
209                         }
210                         return 0;
211                 }
212                 rc = lookup_name(ef, *parent, node, p, n);
213                 if (rc != 0)
214                 {
215                         exfat_put_node(ef, *parent);
216                         return rc;
217                 }
218                 exfat_put_node(ef, *parent);
219                 *parent = *node;
220         }
221         exfat_bug("impossible");
222 }