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