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-2015  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         if (a >= ef->upcase_chars || b >= ef->upcase_chars)
  65                 return (int) a - (int) b;
  66
  67         return (int) le16_to_cpu(ef->upcase[a]) - (int) le16_to_cpu(ef->upcase[b]);
  68 }
  69
  70 static int compare_name(struct exfat* ef, const le16_t* a, const le16_t* b)
  71 {
  72         while (le16_to_cpu(*a) && le16_to_cpu(*b))
  73         {
  74                 int rc = compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b));
  75                 if (rc != 0)
  76                         return rc;
  77                 a++;
  78                 b++;
  79         }
  80         return compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b));
  81 }
  82
  83 static int lookup_name(struct exfat* ef, struct exfat_node* parent,
  84                 struct exfat_node** node, const char* name, size_t n)
  85 {
  86         struct exfat_iterator it;
  87         le16_t buffer[EXFAT_NAME_MAX + 1];
  88         int rc;
  89
  90         *node = NULL;
  91
  92         rc = utf8_to_utf16(buffer, name, EXFAT_NAME_MAX, n);
  93         if (rc != 0)
  94                 return rc;
  95
  96         rc = exfat_opendir(ef, parent, &it);
  97         if (rc != 0)
  98                 return rc;
  99         while ((*node = exfat_readdir(ef, &it)))
 100         {
 101                 if (compare_name(ef, buffer, (*node)->name) == 0)
 102                 {
 103                         exfat_closedir(ef, &it);
 104                         return 0;
 105                 }
 106                 exfat_put_node(ef, *node);
 107         }
 108         exfat_closedir(ef, &it);
 109         return -ENOENT;
 110 }
 111
 112 static size_t get_comp(const char* path, const char** comp)
 113 {
 114         const char* end;
 115
 116         *comp = path + strspn(path, "/");                               /* skip leading slashes */
 117         end = strchr(*comp, '/');
 118         if (end == NULL)
 119                 return strlen(*comp);
 120         else
 121                 return end - *comp;
 122 }
 123
 124 int exfat_lookup(struct exfat* ef, struct exfat_node** node,
 125                 const char* path)
 126 {
 127         struct exfat_node* parent;
 128         const char* p;
 129         size_t n;
 130         int rc;
 131
 132         /* start from the root directory */
 133         parent = *node = exfat_get_node(ef->root);
 134         for (p = path; (n = get_comp(p, &p)); p += n)
 135         {
 136                 if (n == 1 && *p == '.')                                /* skip "." component */
 137                         continue;
 138                 rc = lookup_name(ef, parent, node, p, n);
 139                 if (rc != 0)
 140                 {
 141                         exfat_put_node(ef, parent);
 142                         return rc;
 143                 }
 144                 exfat_put_node(ef, parent);
 145                 parent = *node;
 146         }
 147         return 0;
 148 }
 149
 150 static bool is_last_comp(const char* comp, size_t length)
 151 {
 152         const char* p = comp + length;
 153
 154         return get_comp(p, &p) == 0;
 155 }
 156
 157 static bool is_allowed(const char* comp, size_t length)
 158 {
 159         size_t i;
 160
 161         for (i = 0; i < length; i++)
 162                 switch (comp[i])
 163                 {
 164                 case 0x01 ... 0x1f:
 165                 case '/':
 166                 case '\\':
 167                 case ':':
 168                 case '*':
 169                 case '?':
 170                 case '"':
 171                 case '<':
 172                 case '>':
 173                 case '|':
 174                         return false;
 175                 }
 176         return true;
 177 }
 178
 179 int exfat_split(struct exfat* ef, struct exfat_node** parent,
 180                 struct exfat_node** node, le16_t* name, const char* path)
 181 {
 182         const char* p;
 183         size_t n;
 184         int rc;
 185
 186         memset(name, 0, (EXFAT_NAME_MAX + 1) * sizeof(le16_t));
 187         *parent = *node = exfat_get_node(ef->root);
 188         for (p = path; (n = get_comp(p, &p)); p += n)
 189         {
 190                 if (n == 1 && *p == '.')
 191                         continue;
 192                 if (is_last_comp(p, n))
 193                 {
 194                         if (!is_allowed(p, n))
 195                         {
 196                                 /* contains characters that are not allowed */
 197                                 exfat_put_node(ef, *parent);
 198                                 return -ENOENT;
 199                         }
 200                         rc = utf8_to_utf16(name, p, EXFAT_NAME_MAX, n);
 201                         if (rc != 0)
 202                         {
 203                                 exfat_put_node(ef, *parent);
 204                                 return rc;
 205                         }
 206
 207                         rc = lookup_name(ef, *parent, node, p, n);
 208                         if (rc != 0 && rc != -ENOENT)
 209                         {
 210                                 exfat_put_node(ef, *parent);
 211                                 return rc;
 212                         }
 213                         return 0;
 214                 }
 215                 rc = lookup_name(ef, *parent, node, p, n);
 216                 if (rc != 0)
 217                 {
 218                         exfat_put_node(ef, *parent);
 219                         return rc;
 220                 }
 221                 exfat_put_node(ef, *parent);
 222                 *parent = *node;
 223         }
 224         exfat_bug("impossible");
 225 }