diff options
| -rw-r--r-- | ChangeLog | 11 | ||||
| -rw-r--r-- | elf/Makefile | 2 | ||||
| -rw-r--r-- | elf/dl-load.c | 295 | ||||
| -rw-r--r-- | elf/ldsodefs.h | 13 | ||||
| -rw-r--r-- | elf/link.h | 4 | ||||
| -rw-r--r-- | elf/rtld.c | 6 | ||||
| -rw-r--r-- | include/mntent.h | 1 | ||||
| -rw-r--r-- | sysdeps/generic/dl-sysdep.c | 153 |
8 files changed, 245 insertions, 240 deletions
@@ -1,3 +1,14 @@ +1998-03-31 18:11 Ulrich Drepper <drepper@cygnus.com> + + * include/mntent.h: New file. + + * elf/Makefile (trusted-dirs.h): Append slash to filename. + * elf/dl-load.c: Rewrite search path handling. + * elf/ldsodefs.h (struct r_search_path_elem): Change for rewrite. + * elf/rtld.c (process_envvars): Recognize LD_HWCAP_MASK. + * sysdeps/generic/dl-sysdep.h (_dl_important_hwcap): New function. + * elf/ldsodefs.h: Add prototype. + 1998-03-30 Ulrich Drepper <drepper@cygnus.com> * nss/nsswitch.c (__nss_lookup): Adjust comment. diff --git a/elf/Makefile b/elf/Makefile index 106e863..70b0c6a 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -141,7 +141,7 @@ $(objpfx)trusted-dirs.h: Makefile $(..)Makeconfig $(make-target-directory) (for dir in `echo "$(default-rpath) $(user-defined-trusted-dirs)" | \ sed 's/:/ /g'`; do \ - echo " \"$$dir\","; \ + echo " \"$$dir/\","; \ done;) > $@T mv -f $@T $@ $(objpfx)rtldtbl.h: Makefile $(..)Makeconfig genrtldtbl.awk diff --git a/elf/dl-load.c b/elf/dl-load.c index 212b223..7d3ff0c 100644 --- a/elf/dl-load.c +++ b/elf/dl-load.c @@ -100,6 +100,11 @@ extern size_t _dl_platformlen; binaries. */ static struct r_search_path_elem **fake_path_list; +/* List of the hardware capabilities we might end up using. */ +static const struct r_strlenpair *capstr; +static size_t ncapstr; +static size_t max_capstrlen; + /* Local version of `strdup' function. */ static inline char * @@ -119,6 +124,7 @@ local_strdup (const char *s) be freed if the shared object already has this name. Returns false if the object already had this name. */ static int +internal_function add_name_to_object (struct link_map *l, char *name) { struct libname_list *lnp, *lastp; @@ -156,9 +162,11 @@ add_name_to_object (struct link_map *l, char *name) return 1; } +/* All known directories in sorted order. */ +static struct r_search_path_elem *all_dirs; -/* Implement cache for search path lookup. */ -#include "rtldtbl.h" +/* Standard search directories. */ +static struct r_search_path_elem **rtld_search_dirs; static size_t max_dirnamelen; @@ -173,6 +181,11 @@ fillin_rpath (char *rpath, struct r_search_path_elem **result, const char *sep, { struct r_search_path_elem *dirp; size_t len = strlen (cp); + + /* `strsep' can pass an empty string. */ + if (len == 0) + continue; + /* Remove trailing slashes. */ while (len > 1 && cp[len - 1] == '/') --len; @@ -187,7 +200,8 @@ fillin_rpath (char *rpath, struct r_search_path_elem **result, const char *sep, continue; while (*trun != NULL - && (memcmp (*trun, cp, len) != 0 || (*trun)[len] != '\0')) + && (memcmp (*trun, cp, len) != 0 + || ((*trun)[len] != '/' && (*trun)[len + 1] != '\0'))) ++trun; if (*trun == NULL) @@ -201,12 +215,12 @@ fillin_rpath (char *rpath, struct r_search_path_elem **result, const char *sep, /* See if this directory is already known. */ for (dirp = all_dirs; dirp != NULL; dirp = dirp->next) - if (dirp->dirnamelen == len && strcmp (cp, dirp->dirname) == 0) + if (dirp->dirnamelen == len && memcmp (cp, dirp->dirname, len) == 0) break; if (dirp != NULL) { - /* It is available, see whether it's in our own list. */ + /* It is available, see whether it's on our own list. */ size_t cnt; for (cnt = 0; cnt < nelems; ++cnt) if (result[cnt] == dirp) @@ -217,57 +231,30 @@ fillin_rpath (char *rpath, struct r_search_path_elem **result, const char *sep, } else { + size_t cnt; + /* It's a new directory. Create an entry and add it. */ - dirp = (struct r_search_path_elem *) malloc (sizeof (*dirp)); + dirp = (struct r_search_path_elem *) + malloc (sizeof (*dirp) + ncapstr * sizeof (enum r_dir_status)); if (dirp == NULL) _dl_signal_error (ENOMEM, NULL, "cannot create cache for search path"); + dirp->dirname = cp; dirp->dirnamelen = len; + + if (len > max_dirnamelen) + max_dirnamelen = len; + /* We have to make sure all the relative directories are never ignored. The current directory might change and all our saved information would be void. */ - dirp->dirstatus = cp[0] != '/' ? existing : unknown; - - /* Add the name of the machine dependent directory if a machine - is defined. */ - if (_dl_platform != NULL) - { - char *tmp; - - dirp->machdirnamelen = len + _dl_platformlen + 1; - tmp = (char *) malloc (len + _dl_platformlen + 2); - if (tmp == NULL) - _dl_signal_error (ENOMEM, NULL, - "cannot create cache for search path"); - dirp->dirname = tmp; - tmp = __mempcpy (tmp, cp, len); - tmp = __mempcpy (tmp, _dl_platform, _dl_platformlen); - *tmp++ = '/'; - *tmp = '\0'; - - dirp->machdirstatus = dirp->dirstatus; - - if (max_dirnamelen < dirp->machdirnamelen) - max_dirnamelen = dirp->machdirnamelen; - } + if (cp[0] != '/') + for (cnt = 0; cnt < ncapstr; ++cnt) + dirp->status[cnt] = existing; else - { - char *tmp; - - dirp->machdirnamelen = len; - dirp->machdirstatus = nonexisting; - - tmp = (char *) malloc (len + 1); - if (tmp == NULL) - _dl_signal_error (ENOMEM, NULL, - "cannot create cache for search path"); - dirp->dirname = tmp; - *((char *) __mempcpy (tmp, cp, len)) = '\0'; - - if (max_dirnamelen < dirp->dirnamelen) - max_dirnamelen = dirp->dirnamelen; - } + for (cnt = 0; cnt < ncapstr; ++cnt) + dirp->status[cnt] = unknown; dirp->what = what; dirp->where = where; @@ -288,6 +275,7 @@ fillin_rpath (char *rpath, struct r_search_path_elem **result, const char *sep, static struct r_search_path_elem ** +internal_function decompose_rpath (const char *rpath, size_t additional_room, const char *what, const char *where) { @@ -317,13 +305,14 @@ decompose_rpath (const char *rpath, size_t additional_room, void _dl_init_paths (const char *llp) { - static const char *trusted_dirs[] = + static const char *system_dirs[] = { #include "trusted-dirs.h" NULL }; - - struct r_search_path_elem **pelem; + const char **strp; + struct r_search_path_elem *pelem, **aelem; + size_t round_size; /* We have in `search_path' the information about the RPATH of the dynamic loader. Now fill in the information about the applications @@ -331,10 +320,6 @@ _dl_init_paths (const char *llp) variable. */ struct link_map *l; - /* Names of important hardware capabilities. */ - char **hwcap_names; - size_t nhwcap_names; - /* Number of elements in the library path. */ size_t nllp; @@ -352,8 +337,47 @@ _dl_init_paths (const char *llp) nllp = 0; /* Get the capabilities. */ - hwcap_names = _dl_important_hwcaps (&nhwcap_names, - _dl_platform, _dl_platformlen); + capstr = _dl_important_hwcaps (_dl_platform, _dl_platformlen, + &ncapstr, &max_capstrlen); + + /* First set up the rest of the default search directory entries. */ + aelem = rtld_search_dirs = (struct r_search_path_elem **) + malloc ((ncapstr + 1) * sizeof (struct r_search_path_elem *)); + + round_size = ((2 * sizeof (struct r_search_path_elem) - 1 + + ncapstr * sizeof (enum r_dir_status)) + / sizeof (struct r_search_path_elem)); + + rtld_search_dirs[0] = (struct r_search_path_elem *) + malloc ((sizeof (system_dirs) / sizeof (system_dirs[0]) - 1) + * round_size * sizeof (struct r_search_path_elem)); + if (rtld_search_dirs[0] == NULL) + _dl_signal_error (ENOMEM, NULL, "cannot create cache for search path"); + + pelem = all_dirs= rtld_search_dirs[0]; + for (strp = system_dirs; *strp != NULL; ++strp, pelem += round_size) + { + size_t cnt; + + *aelem++ = pelem; + + pelem->next = *(strp + 1) == NULL ? NULL : (pelem + round_size); + + pelem->what = "system search path"; + pelem->where = NULL; + + pelem->dirnamelen = strlen (pelem->dirname = *strp); + if (pelem->dirnamelen > max_dirnamelen) + max_dirnamelen = pelem->dirnamelen; + + if (pelem->dirname[0] != '/') + for (cnt = 0; cnt < ncapstr; ++cnt) + pelem->status[cnt] = existing; + else + for (cnt = 0; cnt < ncapstr; ++cnt) + pelem->status[cnt] = unknown; + } + *aelem = NULL; l = _dl_loaded; if (l != NULL) @@ -391,7 +415,7 @@ _dl_init_paths (const char *llp) if (nllp > 0) { - char *copy = strdupa (llp); + char *copy = local_strdup (llp); /* Decompose the LD_LIBRARY_PATH and fill in the result. First search for the next place to enter elements. */ @@ -402,7 +426,7 @@ _dl_init_paths (const char *llp) /* We need to take care that the LD_LIBRARY_PATH environment variable can contain a semicolon. */ (void) fillin_rpath (copy, result, ":;", - __libc_enable_secure ? trusted_dirs : NULL, + __libc_enable_secure ? system_dirs : NULL, "LD_LIBRARY_PATH", NULL); } } @@ -424,50 +448,10 @@ _dl_init_paths (const char *llp) "cannot create cache for search path"); (void) fillin_rpath (local_strdup (llp), fake_path_list, ":;", - __libc_enable_secure ? trusted_dirs : NULL, + __libc_enable_secure ? system_dirs : NULL, "LD_LIBRARY_PATH", NULL); } } - - /* Now set up the rest of the rtld_search_dirs. */ - for (pelem = rtld_search_dirs; *pelem != NULL; ++pelem) - { - struct r_search_path_elem *relem = *pelem; - - if (_dl_platform != NULL) - { - char *tmp, *orig; - - relem->machdirnamelen = relem->dirnamelen + _dl_platformlen + 1; - tmp = (char *) malloc (relem->machdirnamelen + 1); - if (tmp == NULL) - _dl_signal_error (ENOMEM, NULL, - "cannot create cache for search path"); - - orig = tmp; - tmp = __mempcpy (tmp, relem->dirname, relem->dirnamelen); - tmp = __mempcpy (tmp, _dl_platform, _dl_platformlen); - *tmp++ = '/'; - *tmp = '\0'; - relem->dirname = orig; - - relem->machdirstatus = unknown; - - if (max_dirnamelen < relem->machdirnamelen) - max_dirnamelen = relem->machdirnamelen; - } - else - { - relem->machdirnamelen = relem->dirnamelen; - relem->machdirstatus = nonexisting; - - if (max_dirnamelen < relem->dirnamelen) - max_dirnamelen = relem->dirnamelen; - } - - relem->what = "system search path"; - relem->where = NULL; - } } @@ -844,26 +828,26 @@ static void print_search_path (struct r_search_path_elem **list, const char *what, const char *name) { + char buf[max_dirnamelen + max_capstrlen]; + char *endp; int first = 1; _dl_debug_message (1, " search path=", NULL); while (*list != NULL && (*list)->what == what) /* Yes, ==. */ { - char *buf = strdupa ((*list)->dirname); + char *endp = __mempcpy (buf, (*list)->dirname, (*list)->dirnamelen); + size_t cnt; + + for (cnt = 0; cnt < ncapstr; ++cnt) + if ((*list)->status[cnt] != nonexisting) + { + char *cp = __mempcpy (endp, capstr[cnt].str, capstr[cnt].len); + cp[-1] = '\0'; + _dl_debug_message (0, first ? "" : ":", buf, NULL); + first = 0; + } - if ((*list)->machdirstatus != nonexisting) - { - buf[(*list)->machdirnamelen - 1] = '\0'; - _dl_debug_message (0, first ? "" : ":", buf, NULL); - first = 0; - } - if ((*list)->dirstatus != nonexisting) - { - buf[(*list)->dirnamelen - 1] = '\0'; - _dl_debug_message (0, first ? "" : ":", buf, NULL); - first = 0; - } ++list; } @@ -893,11 +877,12 @@ open_path (const char *name, size_t namelen, int preloaded, return -1; } - buf = __alloca (max_dirnamelen + namelen); + buf = __alloca (max_dirnamelen + max_capstrlen + namelen + 1); do { struct r_search_path_elem *this_dir = *dirs; size_t buflen = 0; + size_t cnt; /* If we are debugging the search for libraries print the path now if it hasn't happened now. */ @@ -907,95 +892,43 @@ open_path (const char *name, size_t namelen, int preloaded, print_search_path (dirs, current_what, this_dir->where); } - if (this_dir->machdirstatus != nonexisting) + for (cnt = 0; fd == -1 && cnt < ncapstr; ++cnt) { - /* Construct the pathname to try. */ - buflen = ((char *) __mempcpy (__mempcpy (buf, this_dir->dirname, - this_dir->machdirnamelen), - name, namelen) - - buf); + /* Skip this directory if we know it does not exist. */ + if (this_dir->status[cnt] == nonexisting) + continue; - /* Print name we try if this is wanted. */ + buflen = + ((char *) __mempcpy (__mempcpy (__mempcpy (buf, this_dir->dirname, + this_dir->dirnamelen), + capstr[cnt].str, capstr[cnt].len), + name, namelen) + - buf); + + /* Print name we try if this is wanted. */ if (_dl_debug_libs) _dl_debug_message (1, " trying file=", buf, "\n", NULL); fd = __open (buf, O_RDONLY); - if (this_dir->machdirstatus == unknown) + if (this_dir->status[cnt] == unknown) if (fd != -1) - this_dir->machdirstatus = existing; + this_dir->status[cnt] = existing; else { /* We failed to open machine dependent library. Let's test whether there is any directory at all. */ struct stat st; - buf[this_dir->machdirnamelen - 1] = '\0'; + buf[this_dir->dirnamelen + capstr[cnt].len] = '\0'; if (__xstat (_STAT_VER, buf, &st) != 0 || ! S_ISDIR (st.st_mode)) /* The directory does not exist ot it is no directory. */ - this_dir->machdirstatus = nonexisting; + this_dir->status[cnt] = nonexisting; else - this_dir->machdirstatus = existing; + this_dir->status[cnt] = existing; } - if (fd != -1 && preloaded && __libc_enable_secure) - { - /* This is an extra security effort to make sure nobody can - preload broken shared objects which are in the trusted - directories and so exploit the bugs. */ - struct stat st; - - if (__fxstat (_STAT_VER, fd, &st) != 0 - || (st.st_mode & S_ISUID) == 0) - { - /* The shared object cannot be tested for being SUID - or this bit is not set. In this case we must not - use this object. */ - __close (fd); - fd = -1; - /* We simply ignore the file, signal this by setting - the error value which would have been set by `open'. */ - errno = ENOENT; - } - } - } - else - errno = ENOENT; - if (fd == -1 && errno == ENOENT && this_dir->dirstatus != nonexisting) - { - /* Construct the pathname to try. */ - buflen = ((char *) __mempcpy (__mempcpy (buf, this_dir->dirname, - this_dir->dirnamelen), - name, namelen) - - buf); - - /* Print name we try if this is wanted. */ - if (_dl_debug_libs) - _dl_debug_message (1, " trying file=", buf, "\n", NULL); - - fd = __open (buf, O_RDONLY); - if (this_dir->dirstatus == unknown) - if (fd != -1) - this_dir->dirstatus = existing; - else - /* We failed to open library. Let's test whether there - is any directory at all. */ - if (this_dir->dirnamelen <= 1) - this_dir->dirstatus = existing; - else - { - struct stat st; - - buf[this_dir->dirnamelen - 1] = '\0'; - - if (__xstat (_STAT_VER, buf, &st) != 0 - || ! S_ISDIR (st.st_mode)) - /* The directory does not exist ot it is no directory. */ - this_dir->dirstatus = nonexisting; - else - this_dir->dirstatus = existing; - } if (fd != -1 && preloaded && __libc_enable_secure) { /* This is an extra security effort to make sure nobody can diff --git a/elf/ldsodefs.h b/elf/ldsodefs.h index 578e085..86f23bf 100644 --- a/elf/ldsodefs.h +++ b/elf/ldsodefs.h @@ -60,9 +60,12 @@ struct r_search_path_elem const char *what; const char *where; + /* Basename for this search path element. The string must end with + a slash character. */ const char *dirname; + size_t dirnamelen; - enum r_dir_status exists[0]; + enum r_dir_status status[0]; }; struct r_strlenpair @@ -137,6 +140,9 @@ extern int _dl_debug_files; /* Expect cache ID. */ extern int _dl_correct_cache_id; +/* Mask for important hardware capabilities we honour. */ +extern unsigned long int _dl_hwcap_mask; + /* File deccriptor to write debug messages to. */ extern int _dl_debug_fd; @@ -386,7 +392,10 @@ extern void _dl_show_auxv (void); extern char *_dl_next_ld_env_entry (char ***position); /* Return an array with the names of the important hardware capabilities. */ -extern char **_dl_important_hwcap (size_t *sz); +extern const struct r_strlenpair *_dl_important_hwcaps (const char *platform, + size_t paltform_len, + size_t *sz, + size_t *max_capstrlen); __END_DECLS @@ -156,10 +156,6 @@ struct link_map /* Collected information about own RPATH directories. */ struct r_search_path_elem **l_rpath_dirs; - /* Directory names composed from capability names. */ - struct r_strlenpair *l_capstrs; - size_t l_ncapstrs; - /* Collected results of relocation while profiling. */ ElfW(Addr) *l_reloc_result; @@ -1112,6 +1112,12 @@ process_envvars (enum mode *modep, int *lazyp) _dl_show_auxv (); break; + case 10: + /* mask for the important hardware capabilities. */ + if (memcmp (&envline[3], "HWCAP_MASK", 10) == 0) + _dl_hwcap_mask = strtoul (&envline[14], NULL, 0); + break; + case 12: /* Where to place the profiling data file. */ if (memcmp (&envline[3], "DEBUG_OUTPUT", 12) == 0) diff --git a/include/mntent.h b/include/mntent.h new file mode 100644 index 0000000..87a6fb9 --- /dev/null +++ b/include/mntent.h @@ -0,0 +1 @@ +#include <misc/mntent.h> diff --git a/sysdeps/generic/dl-sysdep.c b/sysdeps/generic/dl-sysdep.c index a113c14..25a3dd2 100644 --- a/sysdeps/generic/dl-sysdep.c +++ b/sysdeps/generic/dl-sysdep.c @@ -18,7 +18,10 @@ Boston, MA 02111-1307, USA. */ #include <elf.h> +#include <errno.h> #include <fcntl.h> +#include <stdlib.h> +#include <string.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> @@ -45,7 +48,8 @@ int __libc_enable_secure; int __libc_multiple_libcs; /* Defining this here avoids the inclusion of init-first. */ static ElfW(auxv_t) *_dl_auxv; -static unsigned long hwcap; +static unsigned long int hwcap; +unsigned long int _dl_hwcap_mask = HWCAP_IMPORTANT; #ifndef DL_FIND_ARG_COMPONENTS @@ -273,18 +277,21 @@ _dl_next_ld_env_entry (char ***position) /* Return an array of useful/necessary hardware capability names. */ const struct r_strlenpair * -_dl_important_hwcaps (const char *platform, size_t platform_len, size_t *sz) +_dl_important_hwcaps (const char *platform, size_t platform_len, size_t *sz, + size_t *max_capstrlen) { /* Determine how many important bits are set. */ - unsigned long int important = hwcap & HWCAP_IMPORTANT; + unsigned long int mask = _dl_hwcap_mask; size_t cnt = platform != NULL; size_t n, m; size_t total; struct r_strlenpair *temp; struct r_strlenpair *result; + struct r_strlenpair *rp; + char *cp; - for (n = 0; (~((1UL << n) - 1) & important) != 0; ++n) - if ((important & (1UL << n)) != 0) + for (n = 0; (~((1UL << n) - 1) & mask) != 0; ++n) + if ((mask & (1UL << n)) != 0) ++cnt; if (cnt == 0) @@ -298,22 +305,23 @@ _dl_important_hwcaps (const char *platform, size_t platform_len, size_t *sz) _dl_signal_error (ENOMEM, NULL, "cannot create capability list"); } - result[0]->str = (char *) result; /* Does not really matter. */ - result[0]->len = 0; + result[0].str = (char *) result; /* Does not really matter. */ + result[0].len = 0; *sz = 1; - return &only_base; + return result; } /* Create temporary data structure to generate result table. */ temp = (struct r_strlenpair *) alloca (cnt * sizeof (*temp)); m = 0; - for (n = 0; (~((1UL << n) - 1) & important) != 0; ++n) - if ((important & (1UL << n)) != 0) + for (n = 0; mask != 0; ++n) + if ((mask & (1UL << n)) != 0) { temp[m].str = _dl_hwcap_string (n); temp[m].len = strlen (temp[m].str); - ++m + mask ^= 1UL << n; + ++m; } if (platform != NULL) { @@ -322,36 +330,37 @@ _dl_important_hwcaps (const char *platform, size_t platform_len, size_t *sz) ++m; } + /* Determine the total size of all strings together. */ if (cnt == 1) + total = temp[0].len; + else { - result = (struct r_strlenpair *) malloc (2 * sizeof (*result) - + temp[0].len + 1); - if (result == NULL) - goto no_memory; - - result[0].str = (char *) (result + 1); - result[0].len = len; - result[1].str = (char *) (result + 1); - result[1].len = 0; - result[0].str[0] = '/'; - memcpy (&result[0].str[1], temp[0].str, temp[0].len); - *sz = 2; - - return result; + total = (1 << (cnt - 2)) * (temp[0].len = temp[cnt - 1].len + 2); + for (n = 1; n + 1 < cnt; ++n) + total += (1 << (cnt - 3)) * (temp[n].len + 1); } - /* Determine the total size of all strings together. */ - total = cnt * (temp[0].len + temp[cnt - 1].len + 2); - for (n = 1; n + 1 < cnt; ++n) - total += 2 * (temp[n].len + 1); - /* The result structure: we use a very compressed way to store the various combinations of capability names. */ - result = (struct r_strlenpair *) malloc (1 << (cnt - 2) * sizeof (*result) - + total); + *sz = 1 << cnt; + result = (struct r_strlenpair *) malloc (*sz * sizeof (*result) + total); if (result == NULL) goto no_memory; + if (cnt == 1) + { + result[0].str = (char *) (result + *sz); + result[0].len = temp[0].len + 1; + result[1].str = (char *) (result + *sz); + result[1].len = 0; + cp = __mempcpy ((char *) (result + *sz), temp[0].str, temp[0].len); + *cp = '/'; + *sz = 2; + *max_capstrlen = result[0].len; + + return result; + } + /* Fill in the information. This follows the following scheme (indeces from TEMP for four strings): entry #0: 0, 1, 2, 3 binary: 1111 @@ -360,35 +369,75 @@ _dl_important_hwcaps (const char *platform, size_t platform_len, size_t *sz) #3: 0, 3 1001 This allows to represent all possible combinations of capability names in the string. First generate the strings. */ - n = 1 << cnt; - cp = result[0].str = (char *) (result + 1 << (cnt - 2)); - do - { + result[1].str = result[0].str = cp = (char *) (result + *sz); #define add(idx) \ - cp = __mempcpy (__mempcpy (cp, "/", 1), temp[idx].str, temp[idx].len) + cp = __mempcpy (__mempcpy (cp, temp[idx].str, temp[idx].len), "/", 1); + if (cnt == 2) + { + add (1); + add (0); + } + else + { + n = 1 << cnt; + do + { + n -= 2; - n -= 2; + /* We always add the last string. */ + add (cnt - 1); - /* We always add the last string. */ - add (cnt - 1); + /* Add the strings which have the bit set in N. */ + for (m = cnt - 2; m > 0; --m) + if ((n & (1 << m)) != 0) + add (m); - /* Add the strings which have the bit set in N. */ - for (m = cnt - 2; cnt > 0; --cnt) - if ((n & (1 << m)) != 0) - add (m); + /* Always add the first string. */ + add (0); + } + while (n != 0); + } +#undef add - /* Always add the first string. */ - add (0); + /* Now we are ready to install the string pointers and length. */ + for (n = 0; n < (1 << cnt); ++n) + result[n].len = 0; + n = cnt; + do + { + size_t mask = 1 << --n; + + rp = result; + for (m = 1 << cnt; m > 0; ++rp) + if ((--m & mask) != 0) + rp->len += temp[n].len + 1; } while (n != 0); - /* Now we are ready to install the string pointers and length. - The first string contains all strings. */ - result[0].len = 0; - for (n = 0; n < cnt; ++n) - result[0].len += temp[n].len; + /* The first half of the strings all include the first string. */ + n = (1 << cnt) - 2; + rp = &result[2]; + while (n != (1 << (cnt - 1))) + { + if ((n & 1) != 0) + rp[0].str = rp[-2].str + rp[-2].len; + else + rp[0].str = rp[-1].str; + ++rp; + --n; + } + + /* The second have starts right after the first part of the string of + corresponding entry in the first half. */ + do + { + rp[0].str = rp[-(1 << (cnt - 1))].str + temp[cnt - 1].len + 1; + ++rp; + } + while (--n != 0); - I KNOW THIS DOES NOT YET WORK --drepper + /* The maximum string length. */ + *max_capstrlen = result[0].len; return result; } |