libexfat/lookup.c

   1 /*
   2         lookup.c (02.09.09)
   3         exFAT file system implementation library.
   4
   5         Copyright (C) 2009, 2010  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         return strcspn(comp, "/\\:*?\"<>|") >= length;
 158 }
 159
 160 int exfat_split(struct exfat* ef, struct exfat_node** parent,
 161                 struct exfat_node** node, le16_t* name, const char* path)
 162 {
 163         const char* p;
 164         size_t n;
 165         int rc;
 166
 167         *parent = *node = exfat_get_node(ef->root);
 168         for (p = path; (n = get_comp(p, &p)); p += n)
 169         {
 170                 if (n == 1 && *p == '.')
 171                         continue;
 172                 if (is_last_comp(p, n))
 173                 {
 174                         if (!is_allowed(p, n))
 175                         {
 176                                 /* contains characters that are not allowed */
 177                                 exfat_put_node(ef, *parent);
 178                                 return -ENOENT;
 179                         }
 180                         rc = utf8_to_utf16(name, p, EXFAT_NAME_MAX, n);
 181                         if (rc != 0)
 182                         {
 183                                 exfat_put_node(ef, *parent);
 184                                 return rc;
 185                         }
 186
 187                         rc = lookup_name(ef, *parent, node, p, n);
 188                         if (rc != 0 && rc != -ENOENT)
 189                         {
 190                                 exfat_put_node(ef, *parent);
 191                                 return rc;
 192                         }
 193                         return 0;
 194                 }
 195                 rc = lookup_name(ef, *parent, node, p, n);
 196                 if (rc != 0)
 197                 {
 198                         exfat_put_node(ef, *parent);
 199                         return rc;
 200                 }
 201                 exfat_put_node(ef, *parent);
 202                 *parent = *node;
 203         }
 204         exfat_bug("impossible");
 205 }