"Fossies" - the Fresh Open Source Software Archive

Member "xorriso-1.5.4/libisofs/ecma119_tree.c" (30 Jan 2021, 38699 Bytes) of package /linux/misc/xorriso-1.5.4.pl02.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ecma119_tree.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 1.5.2_vs_1.5.4.

    1 /*
    2  * Copyright (c) 2007 Vreixo Formoso
    3  * Copyright (c) 2009 - 2016 Thomas Schmitt
    4  *
    5  * This file is part of the libisofs project; you can redistribute it and/or
    6  * modify it under the terms of the GNU General Public License version 2 
    7  * or later as published by the Free Software Foundation. 
    8  * See COPYING file for details.
    9  */
   10 
   11 #ifdef HAVE_CONFIG_H
   12 #include "../config.h"
   13 #endif
   14 
   15 /* Must be before ecma119.h because of eventual Libisofs_with_rrip_rR */
   16 #include "libisofs.h"
   17 
   18 #include "ecma119_tree.h"
   19 #include "ecma119.h"
   20 #include "node.h"
   21 #include "util.h"
   22 #include "filesrc.h"
   23 #include "messages.h"
   24 #include "image.h"
   25 #include "stream.h"
   26 #include "eltorito.h"
   27 
   28 #include <stdlib.h>
   29 #include <string.h>
   30 #include <stdio.h>
   31 
   32 /* @param flag   bit0=  Do not issue error messages
   33 */
   34 int iso_get_ecma119_name(IsoWriteOpts *opts, char *input_charset, int imgid,
   35                          char *node_name, enum IsoNodeType node_type,
   36                          char **name, int flag)
   37 {
   38     int ret, relaxed, free_ascii_name = 0, force_dots = 0;
   39     char *ascii_name;
   40     char *isoname = NULL;
   41 
   42     if (node_name == NULL) {
   43         /* it is not necessarily an error, it can be the root */
   44         return ISO_SUCCESS;
   45     }
   46 
   47     if (opts->untranslated_name_len > 0) {
   48         ascii_name = node_name;
   49         ret = 1;
   50     } else {
   51         ret = str2ascii(input_charset, node_name, &ascii_name);
   52         free_ascii_name = 1;
   53     }
   54     if (ret < 0) {
   55         if (!(flag & 512))
   56             iso_msg_submit(imgid, ret, 0,
   57                            "Cannot convert name '%s' to ASCII", node_name);
   58         return ret;
   59     }
   60 
   61     if (opts->allow_full_ascii) {
   62         relaxed = 2;
   63     } else {
   64         relaxed = (int)opts->allow_lowercase;
   65     }
   66     if (opts->allow_7bit_ascii)
   67         relaxed |= 4;
   68     if (node_type == LIBISO_DIR && !(opts->allow_dir_id_ext)) {
   69         if (opts->untranslated_name_len > 0) {
   70             if (strlen(ascii_name) > opts->untranslated_name_len) {
   71 needs_transl:;
   72                 if (!(flag & 512))
   73                     iso_msg_submit(imgid, ISO_NAME_NEEDS_TRANSL, 0,
   74               "File name too long (%d > %d) for untranslated recording:  '%s'",
   75                           strlen(ascii_name), opts->untranslated_name_len,
   76                           ascii_name);
   77                 return ISO_NAME_NEEDS_TRANSL;
   78             }
   79             isoname = strdup(ascii_name);
   80         } else if (opts->max_37_char_filenames) {
   81             isoname = iso_r_dirid(ascii_name, 37, relaxed);
   82         } else if (opts->iso_level == 1) {
   83 
   84 #ifdef Libisofs_old_ecma119_nameS
   85 
   86             if (relaxed) {
   87                 isoname = iso_r_dirid(ascii_name, 8, relaxed);
   88             } else {
   89                 isoname = iso_1_dirid(ascii_name, 0);
   90             }
   91 
   92 #else /* Libisofs_old_ecma119_nameS */
   93 
   94             isoname = iso_1_dirid(ascii_name, relaxed);
   95 
   96 #endif /* ! Libisofs_old_ecma119_nameS */
   97 
   98 
   99         } else {
  100             if (relaxed) {
  101                 isoname = iso_r_dirid(ascii_name, 31, relaxed);
  102             } else {
  103                 isoname = iso_2_dirid(ascii_name);
  104             }
  105         }
  106     } else {
  107         force_dots = !((opts->no_force_dots & 1) ||
  108                        node_type == LIBISO_DIR);
  109         if (opts->untranslated_name_len > 0) {
  110             if (strlen(ascii_name) > opts->untranslated_name_len)
  111                 goto needs_transl;
  112             isoname = strdup(ascii_name);
  113         } else if (opts->max_37_char_filenames) {
  114             isoname = iso_r_fileid(ascii_name, 36, relaxed, force_dots);
  115         } else if (opts->iso_level == 1) {
  116 
  117 #ifdef Libisofs_old_ecma119_nameS
  118 
  119             int max_len;
  120 
  121             if (relaxed) {
  122                 if (strchr(ascii_name, '.') == NULL)
  123                     max_len = 8;
  124                 else
  125                     max_len = 11;
  126                 isoname = iso_r_fileid(ascii_name, max_len, relaxed,
  127                                        force_dots);
  128             } else {
  129                 isoname = iso_1_fileid(ascii_name, 0, force_dots);
  130             }
  131 
  132 #else /* Libisofs_old_ecma119_nameS */
  133 
  134             isoname = iso_1_fileid(ascii_name, relaxed, force_dots);
  135 
  136 #endif /* ! Libisofs_old_ecma119_nameS */
  137 
  138         } else {
  139             if (relaxed || !force_dots) {
  140                 isoname = iso_r_fileid(ascii_name, 30, relaxed, force_dots);
  141             } else {
  142                 isoname = iso_2_fileid(ascii_name);
  143             }
  144         }
  145     }
  146     if (free_ascii_name)
  147         free(ascii_name);
  148     if (isoname != NULL) {
  149         *name = isoname;
  150         return ISO_SUCCESS;
  151     } else {
  152         /*
  153          * only possible if mem error, as check for empty names is done
  154          * in public tree
  155          */
  156         return ISO_OUT_OF_MEM;
  157     }
  158 }
  159 
  160 static
  161 int get_iso_name(Ecma119Image *img, IsoNode *iso, char **name)
  162 {
  163     int ret;
  164 
  165     ret = iso_get_ecma119_name(img->opts, img->input_charset, img->image->id,
  166                                iso->name, iso->type, name, 0);
  167     return ret;
  168 }
  169 
  170 int ecma119_is_dedicated_reloc_dir(Ecma119Image *img, Ecma119Node *node)
  171 {
  172     if (img->rr_reloc_node == node &&
  173         node != img->root && node != img->partition_root &&
  174         (img->opts->rr_reloc_flags & 2))
  175         return 1;
  176     return 0;
  177 }
  178 
  179 static
  180 int create_ecma119_node(Ecma119Image *img, IsoNode *iso, Ecma119Node **node)
  181 {
  182     Ecma119Node *ecma;
  183 
  184     ecma = calloc(1, sizeof(Ecma119Node));
  185     if (ecma == NULL) {
  186         return ISO_OUT_OF_MEM;
  187     }
  188 
  189     ecma->node = iso;
  190     iso_node_ref(iso);
  191     ecma->nlink = 1;
  192     *node = ecma;
  193     return ISO_SUCCESS;
  194 }
  195 
  196 /**
  197  * Create a new ECMA-119 node representing a directory from a iso directory
  198  * node.
  199  */
  200 static
  201 int create_dir(Ecma119Image *img, IsoDir *iso, Ecma119Node **node)
  202 {
  203     int ret;
  204     Ecma119Node **children = NULL;
  205     struct ecma119_dir_info *dir_info;
  206 
  207     if (iso->nchildren > 0) {
  208         children = calloc(1, sizeof(void*) * iso->nchildren);
  209         if (children == NULL)
  210             return ISO_OUT_OF_MEM;
  211     }
  212 
  213     dir_info = calloc(1, sizeof(struct ecma119_dir_info));
  214     if (dir_info == NULL) {
  215         if (children != NULL)
  216             free(children);
  217         return ISO_OUT_OF_MEM;
  218     }
  219 
  220     ret = create_ecma119_node(img, (IsoNode*)iso, node);
  221     if (ret < 0) {
  222         if (children != NULL)
  223             free(children);
  224         free(dir_info);
  225         return ret;
  226     }
  227     (*node)->type = ECMA119_DIR;
  228     (*node)->info.dir = dir_info;
  229     (*node)->info.dir->nchildren = 0;
  230     (*node)->info.dir->children = children;
  231     return ISO_SUCCESS;
  232 }
  233 
  234 
  235 static
  236 int create_file_src(Ecma119Image *img, IsoFile *iso, IsoFileSrc **src)
  237 {
  238     int ret;
  239     off_t size;
  240 
  241     size = iso_stream_get_size(iso->stream);
  242     if (size > (off_t)MAX_ISO_FILE_SECTION_SIZE && img->opts->iso_level != 3) {
  243         char *ipath = iso_tree_get_node_path(ISO_NODE(iso));
  244         iso_msg_submit(img->image->id, ISO_FILE_TOO_BIG, 0,
  245                               "File \"%s\" cannot be added to image because "
  246                               "its size is 4 GiB or larger", ipath);
  247         free(ipath);
  248         return ISO_FILE_TOO_BIG;
  249     }
  250     ret = iso_file_src_create(img, iso, src);
  251     if (ret < 0) {
  252         return ret;
  253     }
  254     return 0;
  255 }
  256 
  257 
  258 /**
  259  * Create a new ECMA-119 node representing a regular file from a iso file
  260  * node.
  261  */
  262 static
  263 int create_file(Ecma119Image *img, IsoFile *iso, Ecma119Node **node)
  264 {
  265     int ret;
  266     IsoFileSrc *src;
  267 
  268     ret = create_file_src(img, iso, &src);
  269     if (ret < 0) {
  270         return ret;
  271     }
  272 
  273     ret = create_ecma119_node(img, (IsoNode*)iso, node);
  274     if (ret < 0) {
  275         /*
  276          * the src doesn't need to be freed, it is free together with
  277          * the Ecma119Image
  278          */
  279         return ret;
  280     }
  281     (*node)->type = ECMA119_FILE;
  282     (*node)->info.file = src;
  283 
  284     return ret;
  285 }
  286 
  287 /**
  288  * Create a new ECMA-119 node representing a regular file from an El-Torito
  289  * boot catalog
  290  */
  291 static
  292 int create_boot_cat(Ecma119Image *img, IsoBoot *iso, Ecma119Node **node)
  293 {
  294     int ret;
  295     IsoFileSrc *src;
  296 
  297     ret = el_torito_catalog_file_src_create(img, &src);
  298     if (ret < 0) {
  299         return ret;
  300     }
  301 
  302     ret = create_ecma119_node(img, (IsoNode*)iso, node);
  303     if (ret < 0) {
  304         /*
  305          * the src doesn't need to be freed, it is free together with
  306          * the Ecma119Image
  307          */
  308         return ret;
  309     }
  310     (*node)->type = ECMA119_FILE;
  311     (*node)->info.file = src;
  312 
  313     return ret;
  314 }
  315 
  316 /**
  317  * Create a new ECMA-119 node representing a symbolic link from a iso symlink
  318  * node.
  319  */
  320 static
  321 int create_symlink(Ecma119Image *img, IsoSymlink *iso, Ecma119Node **node)
  322 {
  323     int ret;
  324 
  325     ret = create_ecma119_node(img, (IsoNode*)iso, node);
  326     if (ret < 0) {
  327         return ret;
  328     }
  329     (*node)->type = ECMA119_SYMLINK;
  330     return ISO_SUCCESS;
  331 }
  332 
  333 /**
  334  * Create a new ECMA-119 node representing a special file.
  335  */
  336 static
  337 int create_special(Ecma119Image *img, IsoSpecial *iso, Ecma119Node **node)
  338 {
  339     int ret;
  340 
  341     ret = create_ecma119_node(img, (IsoNode*)iso, node);
  342     if (ret < 0) {
  343         return ret;
  344     }
  345     (*node)->type = ECMA119_SPECIAL;
  346     return ISO_SUCCESS;
  347 }
  348 
  349 void ecma119_node_free(Ecma119Node *node)
  350 {
  351     if (node == NULL) {
  352         return;
  353     }
  354     if (node->type == ECMA119_DIR) {
  355         size_t i;
  356         for (i = 0; i < node->info.dir->nchildren; i++) {
  357             ecma119_node_free(node->info.dir->children[i]);
  358         }
  359         if (node->info.dir->children != NULL)
  360             free(node->info.dir->children);
  361         free(node->info.dir);
  362     }
  363     free(node->iso_name);
  364     iso_node_unref(node->node);
  365     free(node);
  366 }
  367 
  368 
  369 static
  370 int add_to_hidden_list(Ecma119Image *image, IsoFileSrc *src)
  371 {
  372     int ret;
  373     struct iso_filesrc_list_item *item;
  374 
  375     LIBISO_ALLOC_MEM(item, struct iso_filesrc_list_item, 1);
  376     item->src = src;
  377     item->next = image->ecma119_hidden_list;
  378     image->ecma119_hidden_list = item;
  379     ret = ISO_SUCCESS;
  380 ex:
  381     return ret;
  382 }
  383 
  384 
  385 int iso_filesrc_list_destroy(struct iso_filesrc_list_item **start_item)
  386 {
  387     struct iso_filesrc_list_item *item, *next;
  388 
  389     for (item = *start_item; item != NULL; item = next) {
  390         next = item->next;
  391         LIBISO_FREE_MEM(item);
  392     }
  393     return ISO_SUCCESS;
  394 }
  395  
  396 
  397 /**
  398  * @param flag
  399  *      bit0= iso is in a hidden directory. Thus hide it.
  400  * @return
  401  *      1 success, 0 node ignored,  < 0 error
  402  *
  403  */
  404 static
  405 int create_tree(Ecma119Image *image, IsoNode *iso, Ecma119Node **tree,
  406                 int depth, int pathlen, int flag)
  407 {
  408     int ret, hidden;
  409     Ecma119Node *node = NULL;
  410     int max_path;
  411     char *iso_name= NULL, *ipath = NULL;
  412     IsoFileSrc *src = NULL;
  413     IsoWriteOpts *opts;
  414 
  415     if (image == NULL || iso == NULL || tree == NULL) {
  416         return ISO_NULL_POINTER;
  417     }
  418     opts = image->opts;
  419     *tree = NULL;
  420 
  421     hidden = flag & 1;
  422     if (iso->hidden & LIBISO_HIDE_ON_RR) {
  423         hidden = 1;
  424         if (!((iso->hidden & LIBISO_HIDE_BUT_WRITE) ||
  425               iso->type == LIBISO_BOOT)) {
  426             return 0; /* file will be ignored */
  427         }
  428     }
  429 
  430     if (hidden) {
  431         max_path= pathlen;
  432     } else {
  433         ret = get_iso_name(image, iso, &iso_name);
  434         if (ret < 0) {
  435             iso_name = NULL; /* invalid, do not free */
  436             goto ex;
  437         }
  438         max_path = pathlen + 1 + (iso_name ? strlen(iso_name) : 0);
  439         if (!opts->rockridge) {
  440             if ((iso->type == LIBISO_DIR && depth > 8) &&
  441                 !opts->allow_deep_paths) {
  442                 ipath = iso_tree_get_node_path(iso);
  443                 ret = iso_msg_submit(image->image->id, ISO_FILE_IMGPATH_WRONG,
  444                                      0, "File \"%s\" can't be added, "
  445                                      "because directory depth "
  446                                      "is greater than 8.", ipath);
  447                 goto ex;
  448             } else if (max_path > 255 && !opts->allow_longer_paths) {
  449                 ipath = iso_tree_get_node_path(iso);
  450                 ret = iso_msg_submit(image->image->id, ISO_FILE_IMGPATH_WRONG,
  451                                      0, "File \"%s\" can't be added, "
  452                                      "because path length "
  453                                      "is greater than 255 characters", ipath);
  454                 goto ex;
  455             }
  456         }
  457     }
  458 
  459     switch (iso->type) {
  460     case LIBISO_FILE:
  461         if (hidden) {
  462             ret = create_file_src(image, (IsoFile *) iso, &src);
  463             if (ret <= 0)
  464                 goto ex;
  465             ret = add_to_hidden_list(image, src); 
  466         } else {
  467             ret = create_file(image, (IsoFile*)iso, &node);
  468         }
  469         break;
  470     case LIBISO_SYMLINK:
  471         if (hidden) {
  472             ret = 0; /* Hidden means non-existing */
  473             goto ex;
  474         }
  475         if (opts->rockridge) {
  476             ret = create_symlink(image, (IsoSymlink*)iso, &node);
  477         } else {
  478             /* symlinks are only supported when RR is enabled */
  479             char *ipath = iso_tree_get_node_path(iso);
  480             ret = iso_msg_submit(image->image->id, ISO_FILE_IGNORED, 0,
  481                 "File \"%s\" ignored. Symlinks need RockRidge extensions.",
  482                 ipath);
  483             free(ipath);
  484         }
  485         break;
  486     case LIBISO_SPECIAL:
  487         if (hidden) {
  488             ret = 0; /* Hidden means non-existing */
  489             goto ex;
  490         }
  491         if (opts->rockridge) {
  492             ret = create_special(image, (IsoSpecial*)iso, &node);
  493         } else {
  494             /* special files are only supported when RR is enabled */
  495             char *ipath = iso_tree_get_node_path(iso);
  496             ret = iso_msg_submit(image->image->id, ISO_FILE_IGNORED, 0,
  497                 "File \"%s\" ignored. Special files need RockRidge extensions.",
  498                 ipath);
  499             free(ipath);
  500         }
  501         break;
  502     case LIBISO_BOOT:
  503         if (image->eltorito) {
  504             if (hidden) {
  505                 ret = el_torito_catalog_file_src_create(image, &src);
  506                 if (ret <= 0)
  507                     goto ex;
  508                 ret = add_to_hidden_list(image, src); 
  509             } else {
  510                 ret = create_boot_cat(image, (IsoBoot*)iso, &node);
  511             }
  512         } else {
  513             /* log and ignore */
  514             ret = iso_msg_submit(image->image->id, ISO_FILE_IGNORED, 0,
  515                 "El-Torito catalog found on a image without El-Torito.");
  516         }
  517         break;
  518     case LIBISO_DIR:
  519         {
  520             IsoNode *pos;
  521             IsoDir *dir = (IsoDir*)iso;
  522 
  523             if (!hidden) {
  524                 ret = create_dir(image, dir, &node);
  525                 if (ret < 0) {
  526                     goto ex;
  527                 }
  528                 if (depth == 1) { /* root is default */
  529                     image->rr_reloc_node = node;
  530                 } else if (depth == 2) {
  531                     /* Directories in root may be used as relocation dir */
  532                     if (opts->rr_reloc_dir != NULL)
  533                         if (opts->rr_reloc_dir[0] != 0 &&
  534                             strcmp(iso->name, opts->rr_reloc_dir) == 0)
  535                             image->rr_reloc_node = node;
  536                 }
  537             }
  538             ret = ISO_SUCCESS;
  539             pos = dir->children;
  540             while (pos) {
  541                 int cret;
  542                 Ecma119Node *child;
  543                 cret = create_tree(image, pos, &child, depth + 1, max_path,
  544                                    !!hidden);
  545                 if (cret < 0) {
  546                     /* error */
  547                     ret = cret;
  548                     break;
  549                 } else if (cret == ISO_SUCCESS && !hidden) {
  550                     /* add child to this node */
  551                     int nchildren = node->info.dir->nchildren++;
  552                     node->info.dir->children[nchildren] = child;
  553                     child->parent = node;
  554                 }
  555                 pos = pos->next;
  556             }
  557         }
  558         break;
  559     default:
  560         /* should never happen */
  561         ret = ISO_ASSERT_FAILURE;
  562         goto ex;
  563     }
  564     if (ret <= 0) {
  565         goto ex;
  566     }
  567     if (!hidden) {
  568         node->iso_name = iso_name;
  569         iso_name = NULL; /* now owned by node, do not free */
  570         *tree = node;
  571         node = NULL;     /* now owned by caller, do not free */
  572     }
  573     ret = ISO_SUCCESS;
  574 ex:
  575     if (iso_name != NULL)
  576         free(iso_name);
  577     if (ipath != NULL)
  578         free(ipath);
  579     if (node != NULL)
  580         ecma119_node_free(node);
  581     if (hidden && ret == ISO_SUCCESS)
  582         ret = 0;
  583     /* The sources of hidden files are now owned by the rb-tree */
  584     return ret;
  585 }
  586 
  587 /**
  588  * Compare the iso name of two ECMA-119 nodes
  589  */
  590 static
  591 int cmp_node_name(const void *f1, const void *f2)
  592 {
  593     Ecma119Node *f = *((Ecma119Node**)f1);
  594     Ecma119Node *g = *((Ecma119Node**)f2);
  595     return strcmp(f->iso_name, g->iso_name);
  596 }
  597 
  598 /**
  599  * Sorts a the children of each directory in the ECMA-119 tree represented
  600  * by \p root, according to the order specified in ECMA-119, section 9.3.
  601  */
  602 static
  603 void sort_tree(Ecma119Node *root)
  604 {
  605     size_t i;
  606 
  607     if (root->info.dir->children == NULL)
  608         return;
  609     qsort(root->info.dir->children, root->info.dir->nchildren, sizeof(void*),
  610           cmp_node_name);
  611     for (i = 0; i < root->info.dir->nchildren; i++) {
  612         if (root->info.dir->children[i]->type == ECMA119_DIR)
  613             sort_tree(root->info.dir->children[i]);
  614     }
  615 }
  616 
  617 /**
  618  * Ensures that the ISO name of each children of the given dir is unique,
  619  * changing some of them if needed.
  620  * It also ensures that resulting filename is always <= than given
  621  * max_name_len, including extension. If needed, the extension will be reduced,
  622  * but never under 3 characters.
  623  */
  624 static
  625 int mangle_single_dir(Ecma119Image *img, Ecma119Node *dir, int max_file_len,
  626                       int max_dir_len)
  627 {
  628     int ret;
  629     int i, nchildren;
  630     Ecma119Node **children;
  631     IsoHTable *table;
  632     int need_sort = 0;
  633 
  634     nchildren = dir->info.dir->nchildren;
  635     children = dir->info.dir->children;
  636 
  637     if (nchildren <= 0)
  638         return ISO_SUCCESS; /* nothing to do */
  639 
  640     /* a hash table will temporary hold the names, for fast searching */
  641     ret = iso_htable_create((nchildren * 100) / 80, iso_str_hash,
  642                             (compare_function_t)strcmp, &table);
  643     if (ret < 0) {
  644         return ret;
  645     }
  646     for (i = 0; i < nchildren; ++i) {
  647         char *name = children[i]->iso_name;
  648         ret = iso_htable_add(table, name, name);
  649         if (ret < 0) {
  650             goto mangle_cleanup;
  651         }
  652     }
  653 
  654     for (i = 0; i < nchildren; ++i) {
  655         char *name, *ext;
  656         char full_name[40];
  657         const int full_max_len = 40 - 1;
  658         int max; /* computed max len for name, without extension */
  659         int j = i;
  660         int digits = 1; /* characters to change per name */
  661 
  662         /* first, find all child with same name */
  663         while (j + 1 < nchildren && !cmp_node_name(children + i, children + j
  664                 + 1)) {
  665             ++j;
  666         }
  667         if (j == i) {
  668             /* name is unique */
  669             continue;
  670         }
  671 
  672         if (img->opts->untranslated_name_len) {
  673             /* This should not happen because no two IsoNode names should be
  674                identical and only unaltered IsoNode names should be seen here.
  675                Thus the Ema119Node names should be unique.
  676             */
  677             iso_msg_submit(img->image->id, ISO_NAME_NEEDS_TRANSL, 0,
  678                            "ECMA-119 file name collision: '%s'",
  679                            children[i]->iso_name);
  680             ret = ISO_NAME_NEEDS_TRANSL;
  681             goto mangle_cleanup;
  682         }
  683 
  684         /*
  685          * A max of 7 characters is good enough, it allows handling up to
  686          * 9,999,999 files with same name. We can increment this to
  687          * max_name_len, but the int_pow() function must then be modified
  688          * to return a bigger integer.
  689          */
  690         while (digits < 8) {
  691             int ok, k;
  692             char *dot;
  693             int change = 0; /* number to be written */
  694 
  695             /* copy name to buffer */
  696             strncpy(full_name, children[i]->iso_name, full_max_len);
  697             full_name[full_max_len] = 0;
  698 
  699             /* compute name and extension */
  700             dot = strrchr(full_name, '.');
  701             if (dot != NULL &&
  702                 (children[i]->type != ECMA119_DIR ||
  703                  img->opts->allow_dir_id_ext)) {
  704 
  705                 /*
  706                  * File (normally not dir) with extension
  707                  * Note that we don't need to check for placeholders, as
  708                  * tree reparent happens later, so no placeholders can be
  709                  * here at this time.
  710                  */
  711                 int extlen;
  712                 full_name[dot - full_name] = '\0';
  713                 name = full_name;
  714                 ext = dot + 1;
  715 
  716                 /*
  717                  * For iso level 1 we force ext len to be 3, as name
  718                  * can't grow on the extension space
  719                  */
  720                 extlen = (max_file_len == 12) ? 3 : strlen(ext);
  721                 max = max_file_len - extlen - 1 - digits;
  722                 if (max <= 0) {
  723                     /* this can happen if extension is too long */
  724                     if (extlen + max > 3) {
  725                         /*
  726                          * reduce extension len, to give name an extra char
  727                          * note that max is negative or 0
  728                          */
  729                         extlen = extlen + max - 1;
  730                         ext[extlen] = '\0';
  731                         max = max_file_len - extlen - 1 - digits;
  732                     } else {
  733                         /*
  734                          * error, we don't support extensions < 3
  735                          * This can't happen with current limit of digits.
  736                          */
  737                         ret = ISO_ERROR;
  738                         goto mangle_cleanup;
  739                     }
  740                 }
  741                 /* ok, reduce name by digits */
  742                 if (name + max < dot) {
  743                     name[max] = '\0';
  744                 }
  745             } else {
  746                 /* Directory (normally), or file without extension */
  747                 if (children[i]->type == ECMA119_DIR) {
  748                     max = max_dir_len - digits;
  749                     dot = NULL; /* dots (normally) have no meaning in dirs */
  750                 } else {
  751                     max = max_file_len - digits;
  752                 }
  753                 name = full_name;
  754                 if ((size_t) max < strlen(name)) {
  755                     name[max] = '\0';
  756                 }
  757                 /* let ext be an empty string */
  758                 ext = name + strlen(name);
  759             }
  760 
  761             ok = 1;
  762             /* change name of each file */
  763             for (k = i; k <= j; ++k) {
  764                 char tmp[40];
  765                 char fmt[16];
  766                 if (dot != NULL) {
  767                     sprintf(fmt, "%%s%%0%dd.%%s", digits);
  768                 } else {
  769                     sprintf(fmt, "%%s%%0%dd%%s", digits);
  770                 }
  771                 while (1) {
  772                     sprintf(tmp, fmt, name, change, ext);
  773                     ++change;
  774                     if (change > int_pow(10, digits)) {
  775                         ok = 0;
  776                         break;
  777                     }
  778                     if (!iso_htable_get(table, tmp, NULL)) {
  779                         /* the name is unique, so it can be used */
  780                         break;
  781                     }
  782                 }
  783                 if (ok) {
  784                     char *new = strdup(tmp);
  785                     if (new == NULL) {
  786                         ret = ISO_OUT_OF_MEM;
  787                         goto mangle_cleanup;
  788                     }
  789 
  790 #ifdef Libisofs_extra_verbose_debuG
  791                     iso_msg_debug(img->image->id, "\"%s\" renamed to \"%s\"",
  792                                   children[k]->iso_name, new);
  793 #endif
  794 
  795                     iso_htable_remove_ptr(table, children[k]->iso_name, NULL);
  796                     free(children[k]->iso_name);
  797                     children[k]->iso_name = new;
  798                     iso_htable_add(table, new, new);
  799 
  800                     /*
  801                      * if we change a name we need to sort again children
  802                      * at the end
  803                      */
  804                     need_sort = 1;
  805                 } else {
  806                     /* we need to increment digits */
  807                     break;
  808                 }
  809             }
  810             if (ok) {
  811                 break;
  812             } else {
  813                 ++digits;
  814             }
  815         }
  816         if (digits == 8) {
  817             ret = ISO_MANGLE_TOO_MUCH_FILES;
  818             goto mangle_cleanup;
  819         }
  820         i = j;
  821     }
  822 
  823     /*
  824      * If needed, sort again the files inside dir
  825      */
  826     if (need_sort) {
  827         qsort(children, nchildren, sizeof(void*), cmp_node_name);
  828     }
  829 
  830     ret = ISO_SUCCESS;
  831 
  832 mangle_cleanup : ;
  833     iso_htable_destroy(table, NULL);
  834     return ret;
  835 }
  836 
  837 static
  838 int mangle_dir(Ecma119Image *img, Ecma119Node *dir, int max_file_len,
  839                int max_dir_len)
  840 {
  841     int ret;
  842     size_t i;
  843 
  844     ret = mangle_single_dir(img, dir, max_file_len, max_dir_len);
  845     if (ret < 0) {
  846         return ret;
  847     }
  848 
  849     /* recurse */
  850     for (i = 0; i < dir->info.dir->nchildren; ++i) {
  851         if (dir->info.dir->children[i]->type == ECMA119_DIR) {
  852             ret = mangle_dir(img, dir->info.dir->children[i], max_file_len,
  853                              max_dir_len);
  854             if (ret < 0) {
  855                 /* error */
  856                 return ret;
  857             }
  858         }
  859     }
  860     return ISO_SUCCESS;
  861 }
  862 
  863 static
  864 int mangle_tree(Ecma119Image *img, Ecma119Node *dir, int recurse)
  865 {
  866     int max_file, max_dir;
  867     Ecma119Node *root;
  868 
  869     if (img->opts->untranslated_name_len > 0) {
  870         max_file = max_dir = img->opts->untranslated_name_len;
  871     } else if (img->opts->max_37_char_filenames) {
  872         max_file = max_dir = 37;
  873     } else if (img->opts->iso_level == 1) {
  874         max_file = 12; /* 8 + 3 + 1 */
  875         max_dir = 8;
  876     } else {
  877         max_file = max_dir = 31;
  878     }
  879     if (dir != NULL) {
  880         root = dir;
  881     } else if (img->eff_partition_offset > 0) {
  882         root = img->partition_root;
  883     } else {
  884         root = img->root;
  885     }
  886     if (recurse) {
  887         return mangle_dir(img, root, max_file, max_dir);
  888     } else {
  889         return mangle_single_dir(img, root, max_file, max_dir);
  890     }
  891 }
  892 
  893 /**
  894  * Create a new ECMA-119 node representing a placeholder for a relocated
  895  * dir.
  896  *
  897  * See IEEE P1282, section 4.1.5 for details
  898  */
  899 static
  900 int create_placeholder(Ecma119Node *parent, Ecma119Node *real,
  901                        Ecma119Node **node)
  902 {
  903     Ecma119Node *ret;
  904 
  905     ret = calloc(1, sizeof(Ecma119Node));
  906     if (ret == NULL) {
  907         return ISO_OUT_OF_MEM;
  908     }
  909 
  910     /*
  911      * TODO
  912      * If real is a dir, while placeholder is a file, ISO name restricctions
  913      * are different, what to do?
  914      */
  915     ret->iso_name = strdup(real->iso_name);
  916     if (ret->iso_name == NULL) {
  917         free(ret);
  918         return ISO_OUT_OF_MEM;
  919     }
  920 
  921     /* take a ref to the IsoNode */
  922     ret->node = real->node;
  923     iso_node_ref(real->node);
  924     ret->parent = parent;
  925     ret->type = ECMA119_PLACEHOLDER;
  926     ret->info.real_me = real;
  927     ret->ino = real->ino;
  928     ret->nlink = real->nlink;
  929 
  930     *node = ret;
  931     return ISO_SUCCESS;
  932 }
  933 
  934 static
  935 size_t max_child_name_len(Ecma119Node *dir)
  936 {
  937     size_t ret = 0, i;
  938     for (i = 0; i < dir->info.dir->nchildren; i++) {
  939         size_t len = strlen(dir->info.dir->children[i]->iso_name);
  940         ret = MAX(ret, len);
  941     }
  942     return ret;
  943 }
  944 
  945 /**
  946  * Relocates a directory, as specified in Rock Ridge Specification
  947  * (see IEEE P1282, section 4.1.5). This is needed when the number of levels
  948  * on a directory hierarchy exceeds 8, or the length of a path is higher
  949  * than 255 characters, as specified in ECMA-119, section 6.8.2.1
  950  */
  951 static
  952 int reparent(Ecma119Node *child, Ecma119Node *parent)
  953 {
  954     int ret;
  955     size_t i;
  956     Ecma119Node *placeholder;
  957 
  958     /* replace the child in the original parent with a placeholder */
  959     for (i = 0; i < child->parent->info.dir->nchildren; i++) {
  960         if (child->parent->info.dir->children[i] == child) {
  961             ret = create_placeholder(child->parent, child, &placeholder);
  962             if (ret < 0) {
  963                 return ret;
  964             }
  965             child->parent->info.dir->children[i] = placeholder;
  966             break;
  967         }
  968     }
  969 
  970     /* just for debug, this should never happen... */
  971     if (i == child->parent->info.dir->nchildren) {
  972         return ISO_ASSERT_FAILURE;
  973     }
  974 
  975     /* keep track of the real parent */
  976     child->info.dir->real_parent = child->parent;
  977 
  978     /* add the child to its new parent */
  979     child->parent = parent;
  980     parent->info.dir->nchildren++;
  981     parent->info.dir->children = realloc(parent->info.dir->children,
  982                                  sizeof(void*) * parent->info.dir->nchildren);
  983     parent->info.dir->children[parent->info.dir->nchildren - 1] = child;
  984     return ISO_SUCCESS;
  985 }
  986 
  987 /**
  988  * Reorder the tree, if necessary, to ensure that
  989  *  - the depth is at most 8
  990  *  - each path length is at most 255 characters
  991  * This restriction is imposed by ECMA-119 specification (ECMA-119, 6.8.2.1).
  992  *
  993  * @param dir
  994  *      Dir we are currently processing
  995  * @param level
  996  *      Level of the directory in the hierarchy
  997  * @param pathlen
  998  *      Length of the path until dir, including it
  999  * @return
 1000  *      1 success, < 0 error
 1001  */
 1002 static
 1003 int reorder_tree(Ecma119Image *img, Ecma119Node *dir,
 1004                  int dir_level, int dir_pathlen)
 1005 {
 1006     int ret, level, pathlen, newpathlen;
 1007     size_t max_path, i;
 1008     Ecma119Node *reloc, *child;
 1009 
 1010     /* might change by relocation */
 1011     level = dir_level;
 1012     pathlen = dir_pathlen;
 1013 
 1014     max_path = pathlen + 1 + max_child_name_len(dir);
 1015 
 1016     if (level > 8 || max_path > 255) {
 1017         reloc = img->rr_reloc_node;
 1018         if (reloc == NULL) {
 1019             if (img->eff_partition_offset > 0) {
 1020                 reloc = img->partition_root;
 1021             } else {
 1022                 reloc = img->root;
 1023             }
 1024         }
 1025         ret = reparent(dir, reloc);
 1026         if (ret < 0) {
 1027             return ret;
 1028         }
 1029 
 1030         if (reloc == img->root || reloc == img->partition_root) {
 1031             /*
 1032              * we are appended to the root's children now, so there is no
 1033              * need to recurse (the root will hit us again)
 1034              */
 1035             return ISO_SUCCESS;
 1036         }
 1037 
 1038         /* dir is now the relocated Ecma119Node */
 1039         pathlen = 37 + 1; /* The dir name might get longer by mangling */
 1040         level = 2;
 1041         if (img->opts->rr_reloc_dir != NULL) {
 1042             pathlen += strlen(img->rr_reloc_node->iso_name) + 1;
 1043             if(img->opts->rr_reloc_dir[0] != 0)
 1044               level = 3;
 1045         }
 1046     }
 1047 
 1048     if (ecma119_is_dedicated_reloc_dir(img, (Ecma119Node *) dir))
 1049         return ISO_SUCCESS;
 1050 
 1051     for (i = 0; i < dir->info.dir->nchildren; i++) {
 1052         child = dir->info.dir->children[i];
 1053         if (child->type == ECMA119_DIR) {
 1054             newpathlen = pathlen + 1 + strlen(child->iso_name);
 1055             ret = reorder_tree(img, child, level + 1, newpathlen);
 1056             if (ret < 0)
 1057                 return ret;
 1058         }
 1059     }
 1060     return ISO_SUCCESS;
 1061 }
 1062 
 1063 /*
 1064  * @param flag
 1065  *     bit0= recursion
 1066  *     bit1= count nodes rather than fill them into *nodes
 1067  * @return
 1068  *     <0 error
 1069  *     bit0= saw ino == 0
 1070  *     bit1= saw ino != 0
 1071  */
 1072 static
 1073 int make_node_array(Ecma119Image *img, Ecma119Node *dir,
 1074                     Ecma119Node **nodes, size_t nodes_size, size_t *node_count,
 1075                     int flag)
 1076 {
 1077     int ret, result = 0;
 1078     size_t i;
 1079     Ecma119Node *child;
 1080 
 1081     if (!(flag & 1)) {
 1082         *node_count = 0;
 1083         if (!(flag & 2)) {
 1084             /* Register the tree root node */
 1085             if (*node_count >= nodes_size) {
 1086                 iso_msg_submit(img->image->id, ISO_ASSERT_FAILURE, 0,
 1087                          "Programming error: Overflow of hardlink sort array");
 1088                 return ISO_ASSERT_FAILURE;
 1089             }
 1090             nodes[*node_count] = dir;
 1091         }
 1092         result|= (dir->ino == 0 ? 1 : 2);
 1093         (*node_count)++;
 1094     }
 1095         
 1096     for (i = 0; i < dir->info.dir->nchildren; i++) {
 1097         child = dir->info.dir->children[i];
 1098         if (!(flag & 2)) {
 1099             if (*node_count >= nodes_size) {
 1100                 iso_msg_submit(img->image->id, ISO_ASSERT_FAILURE, 0,
 1101                          "Programming error: Overflow of hardlink sort array");
 1102                 return ISO_ASSERT_FAILURE;
 1103             }
 1104             nodes[*node_count] = child;
 1105         }
 1106         result|= (child->ino == 0 ? 1 : 2);
 1107         (*node_count)++;
 1108 
 1109         if (child->type == ECMA119_DIR) {
 1110             ret = make_node_array(img, child,
 1111                                   nodes, nodes_size, node_count, flag | 1);
 1112             if (ret < 0)
 1113                 return ret;
 1114         }
 1115     }
 1116     return result;
 1117 }
 1118 
 1119 /*
 1120  * @param flag
 1121  *     bit0= compare stat properties and attributes 
 1122  *     bit1= treat all nodes with image ino == 0 as unique
 1123  */
 1124 static
 1125 int ecma119_node_cmp_flag(const void *v1, const void *v2, int flag)
 1126 {
 1127     int ret;
 1128     Ecma119Node *n1, *n2;
 1129 
 1130     n1 = *((Ecma119Node **) v1);
 1131     n2 = *((Ecma119Node **) v2);
 1132     if (n1 == n2)
 1133         return 0;
 1134 
 1135     ret = iso_node_cmp_flag(n1->node, n2->node, flag & (1 | 2));
 1136     return ret;
 1137 }
 1138 
 1139 static 
 1140 int ecma119_node_cmp_hard(const void *v1, const void *v2)
 1141 {
 1142     return ecma119_node_cmp_flag(v1, v2, 1);
 1143 }   
 1144 
 1145 static 
 1146 int ecma119_node_cmp_nohard(const void *v1, const void *v2)
 1147 {
 1148     return ecma119_node_cmp_flag(v1, v2, 1 | 2);
 1149 }   
 1150 
 1151 static
 1152 int family_set_ino(Ecma119Image *img, Ecma119Node **nodes, size_t family_start,
 1153                    size_t next_family, ino_t img_ino, ino_t prev_ino, int flag)
 1154 {
 1155     size_t i;
 1156 
 1157     if (img_ino != 0) {
 1158         /* Check whether this is the same img_ino as in the previous
 1159            family (e.g. by property divergence of imported hardlink).
 1160         */
 1161         if (img_ino == prev_ino)
 1162             img_ino = 0;
 1163 
 1164     /* Accept only if it is within the 32 bit range. */
 1165         if (((uint64_t) img_ino) > 0xffffffff)
 1166             img_ino = 0;
 1167 
 1168     }
 1169     if (img_ino == 0) {
 1170         img_ino = img_give_ino_number(img->image, 0);
 1171     }
 1172     for (i = family_start; i < next_family; i++) {
 1173         nodes[i]->ino = img_ino;
 1174         nodes[i]->nlink = next_family - family_start;
 1175     }
 1176     return 1;
 1177 }
 1178 
 1179 static
 1180 int match_hardlinks(Ecma119Image *img, Ecma119Node *dir, int flag)
 1181 {
 1182     int ret;
 1183     size_t nodes_size = 0, node_count = 0, i, family_start;
 1184     Ecma119Node **nodes = NULL;
 1185     unsigned int fs_id;
 1186     dev_t dev_id;
 1187     ino_t img_ino = 0, prev_ino = 0;
 1188 
 1189     ret = make_node_array(img, dir, nodes, nodes_size, &node_count, 2);
 1190     if (ret < 0)
 1191         return ret;
 1192     nodes_size = node_count;
 1193     nodes = (Ecma119Node **) calloc(sizeof(Ecma119Node *), nodes_size);
 1194     if (nodes == NULL)
 1195         return ISO_OUT_OF_MEM;
 1196     ret = make_node_array(img, dir, nodes, nodes_size, &node_count, 0);
 1197     if (ret < 0)
 1198         goto ex;
 1199 
 1200     /* Sort according to id tuples, IsoFileSrc identity, properties, xattr. */
 1201     if (img->opts->hardlinks)
 1202         qsort(nodes, node_count, sizeof(Ecma119Node *), ecma119_node_cmp_hard);
 1203     else
 1204         qsort(nodes, node_count, sizeof(Ecma119Node *),
 1205               ecma119_node_cmp_nohard);
 1206 
 1207     /* Hand out image inode numbers to all Ecma119Node.ino == 0 .
 1208        Same sorting rank gets same inode number.
 1209        Split those image inode number families where the sort criterion
 1210        differs.
 1211     */
 1212     iso_node_get_id(nodes[0]->node, &fs_id, &dev_id, &img_ino, 1);
 1213     family_start = 0;
 1214     for (i = 1; i < node_count; i++) {
 1215         if (nodes[i]->type != ECMA119_DIR &&
 1216             ecma119_node_cmp_hard(nodes + (i - 1), nodes + i) == 0) {
 1217             /* Still in same ino family */
 1218             if (img_ino == 0) { /* Just in case any member knows its img_ino */
 1219                 iso_node_get_id(nodes[0]->node, &fs_id, &dev_id, &img_ino, 1);
 1220             }
 1221     continue;
 1222         }
 1223         family_set_ino(img, nodes, family_start, i, img_ino, prev_ino, 0);
 1224         prev_ino = img_ino;
 1225         iso_node_get_id(nodes[i]->node, &fs_id, &dev_id, &img_ino, 1);
 1226         family_start = i;
 1227     }
 1228     family_set_ino(img, nodes, family_start, i, img_ino, prev_ino, 0);
 1229 
 1230     ret = ISO_SUCCESS;
 1231 ex:;
 1232     if (nodes != NULL)
 1233         free((char *) nodes);
 1234     return ret;
 1235 }
 1236 
 1237 int ecma119_tree_create(Ecma119Image *img)
 1238 {
 1239     int ret;
 1240     Ecma119Node *root;
 1241 
 1242     ret = create_tree(img, (IsoNode*)img->image->root, &root, 1, 0, 0);
 1243     if (ret <= 0) {
 1244         if (ret == 0) {
 1245             /* unexpected error, root ignored!! This can't happen */
 1246             ret = ISO_ASSERT_FAILURE;
 1247         }
 1248         return ret;
 1249     }
 1250     if (img->eff_partition_offset > 0) {
 1251         img->partition_root = root;
 1252     } else {
 1253         img->root = root;
 1254     }
 1255 
 1256     iso_msg_debug(img->image->id, "Matching hardlinks...");
 1257     ret = match_hardlinks(img, root, 0);
 1258     if (ret < 0) {
 1259         return ret;
 1260     }
 1261 
 1262     iso_msg_debug(img->image->id, "Sorting the low level tree...");
 1263     sort_tree(root);
 1264 
 1265     iso_msg_debug(img->image->id, "Mangling names...");
 1266     ret = mangle_tree(img, NULL, 1);
 1267     if (ret < 0) {
 1268         return ret;
 1269     }
 1270 
 1271     if (img->opts->rockridge && !img->opts->allow_deep_paths) {
 1272 
 1273         /* Relocate deep directories, according to RRIP, 4.1.5 */
 1274         ret = reorder_tree(img, root, 1, 0);
 1275         if (ret < 0) {
 1276             return ret;
 1277         }
 1278 
 1279         /*
 1280          * and we need to remangle the root directory, as the function
 1281          * above could insert new directories into the relocation directory.
 1282          * Note that recurse = 0, as we don't need to recurse.
 1283          */
 1284         ret = mangle_tree(img, img->rr_reloc_node, 0);
 1285         if (ret < 0) {
 1286             return ret;
 1287         }
 1288     }
 1289 
 1290     return ISO_SUCCESS;
 1291 }
 1292 
 1293 /**
 1294  * Search the tree for a certain IsoNode and return its owning Ecma119Node
 1295  * or NULL.
 1296  */
 1297 static
 1298 Ecma119Node *search_iso_node(Ecma119Node *root, IsoNode *node)
 1299 {
 1300     size_t i;
 1301     Ecma119Node *res = NULL;
 1302 
 1303     if (root->node == node)
 1304         return root;
 1305     for (i = 0; i < root->info.dir->nchildren && res == NULL; i++) {
 1306         if (root->info.dir->children[i]->type == ECMA119_DIR)
 1307             res = search_iso_node(root->info.dir->children[i], node);
 1308         else if (root->info.dir->children[i]->node == node)
 1309             res = root->info.dir->children[i];
 1310     }
 1311     return res;
 1312 }
 1313 
 1314 
 1315 Ecma119Node *ecma119_search_iso_node(Ecma119Image *img, IsoNode *node)
 1316 {
 1317     Ecma119Node *res = NULL;
 1318 
 1319     if (img->root != NULL)
 1320         res = search_iso_node(img->root, node);
 1321     return res;
 1322 }
 1323