lookup.c

   1 /*
   2         lookup.c (02.09.09)
   3         exFAT file system implementation library.
   4
   5         Free exFAT implementation.
   6         Copyright (C) 2010-2018  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_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 + 1, 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(&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 + 1, 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 }