From e678bd4b4289e536e998057bf9a9cf415f21b74c Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sat, 20 Mar 2021 17:35:41 +0100 Subject: Add libcompat fallback implementation for fnmatch This has basically been copied over from Musl and slightly modifed. Signed-off-by: David Oberhollenzer --- COPYING.md | 9 +- configure.ac | 2 +- include/compat.h | 12 ++ lib/compat/Makemodule.am | 1 + lib/compat/fnmatch.c | 305 ++++++++++++++++++++++++++++++++++++++++++ lib/fstree/fstree_from_file.c | 2 +- licenses/musl.txt | 193 ++++++++++++++++++++++++++ 7 files changed, 520 insertions(+), 4 deletions(-) create mode 100644 lib/compat/fnmatch.c create mode 100644 licenses/musl.txt diff --git a/COPYING.md b/COPYING.md index 8a9ae04..107fabd 100644 --- a/COPYING.md +++ b/COPYING.md @@ -19,7 +19,11 @@ with the following exceptions: license). See `licenses/hash_table.txt` for details. The rest of squashfs-tools-ng is released under the terms and conditions of -the **GNU General Public License version 3 or later**. +the **GNU General Public License version 3 or later**, with the following +exceptions: + + - `lib/compat/fnmatch.c` has been copied from Musl libc, which is subject to + an MIT style license. See `liceneses/musl.txt` for details. Copies of the LGPLv3 and GPLv3 are included in `licenses/LGPLv3.txt` and `licenses/GPLv3.txt` respectively. @@ -76,7 +80,8 @@ The following may be included: distribution. - The zstd compression library. Copyright Facebook, Inc. All rights reserved. This is released under a BSD style license, included in `licenses/zstd.txt`. - + - Parts of the Musl C library. Copyright Rich Felker, et al. + This is released under an MIT style license, included in `licenses/musl.txt`. Independent of build configurations, the `libsquashfs` library contains the following 3rd party source code, directly linked into the library: diff --git a/configure.ac b/configure.ac index 95750a8..593734b 100644 --- a/configure.ac +++ b/configure.ac @@ -269,7 +269,7 @@ AC_CHECK_HEADERS([sys/xattr.h], [], []) AC_CHECK_HEADERS([sys/sysinfo.h], [], []) AC_CHECK_HEADERS([alloca.h], [], []) -AC_CHECK_FUNCS([strndup getsubopt]) +AC_CHECK_FUNCS([strndup getsubopt fnmatch]) ##### generate output ##### diff --git a/include/compat.h b/include/compat.h index 111168f..e5785d3 100644 --- a/include/compat.h +++ b/include/compat.h @@ -8,6 +8,7 @@ #define COMPAT_H #include "sqfs/predef.h" +#include "config.h" #if defined(__GNUC__) && __GNUC__ >= 5 # define SZ_ADD_OV __builtin_add_overflow @@ -188,4 +189,15 @@ int getsubopt(char **opt, char *const *keys, char **val); WCHAR *path_to_windows(const char *input); #endif +#ifdef HAVE_FNMATCH +#include +#else +#define FNM_PATHNAME 0x1 + +#define FNM_NOMATCH 1 +#define FNM_NOSYS (-1) + +int fnmatch(const char *, const char *, int); +#endif + #endif /* COMPAT_H */ diff --git a/lib/compat/Makemodule.am b/lib/compat/Makemodule.am index 4f4fc9c..6c3c2b4 100644 --- a/lib/compat/Makemodule.am +++ b/lib/compat/Makemodule.am @@ -3,5 +3,6 @@ libcompat_a_SOURCES += lib/compat/strndup.c lib/compat/mockups.c libcompat_a_SOURCES += lib/compat/chdir.c include/compat.h libcompat_a_SOURCES += lib/compat/path_to_windows.c libcompat_a_SOURCES += lib/compat/w32_perror.c +libcompat_a_SOURCES += lib/compat/fnmatch.c noinst_LIBRARIES += libcompat.a diff --git a/lib/compat/fnmatch.c b/lib/compat/fnmatch.c new file mode 100644 index 0000000..ed4dde1 --- /dev/null +++ b/lib/compat/fnmatch.c @@ -0,0 +1,305 @@ +/* + * An implementation of what I call the "Sea of Stars" algorithm for + * POSIX fnmatch(). The basic idea is that we factor the pattern into + * a head component (which we match first and can reject without ever + * measuring the length of the string), an optional tail component + * (which only exists if the pattern contains at least one star), and + * an optional "sea of stars", a set of star-separated components + * between the head and tail. After the head and tail matches have + * been removed from the input string, the components in the "sea of + * stars" are matched sequentially by searching for their first + * occurrence past the end of the previous match. + * + * - Rich Felker, April 2012 + */ + +#include "compat.h" + +#include +#include + +#ifndef HAVE_FNMATCH +#define END 0 +#define UNMATCHABLE -2 +#define BRACKET -3 +#define QUESTION -4 +#define STAR -5 + +static int str_next(const char *str, size_t n, size_t *step) +{ + if (!n) { + *step = 0; + return 0; + } + if (str[0] >= 128U) { + wchar_t wc; + int k = mbtowc(&wc, str, n); + if (k<0) { + *step = 1; + return -1; + } + *step = k; + return wc; + } + *step = 1; + return str[0]; +} + +static int pat_next(const char *pat, size_t m, size_t *step) +{ + int esc = 0; + if (!m || !*pat) { + *step = 0; + return END; + } + *step = 1; + if (pat[0]=='\\' && pat[1]) { + *step = 2; + pat++; + esc = 1; + goto escaped; + } + if (pat[0]=='[') { + size_t k = 1; + if (k= 128U) { + wchar_t wc; + int k = mbtowc(&wc, pat, m); + if (k<0) { + *step = 0; + return UNMATCHABLE; + } + *step = k + esc; + return wc; + } + return pat[0]; +} + +static int match_bracket(const char *p, int k, int kfold) +{ + wchar_t wc; + int inv = 0; + p++; + if (*p=='^' || *p=='!') { + inv = 1; + p++; + } + if (*p==']') { + if (k==']') return !inv; + p++; + } else if (*p=='-') { + if (k=='-') return !inv; + p++; + } + wc = p[-1]; + for (; *p != ']'; p++) { + if (p[0]=='-' && p[1]!=']') { + wchar_t wc2; + int l = mbtowc(&wc2, p+1, 4); + if (l < 0) return 0; + if (wc <= wc2) + if ((unsigned)k-wc <= wc2-wc || + (unsigned)kfold-wc <= wc2-wc) + return !inv; + p += l-1; + continue; + } + if (p[0]=='[' && (p[1]==':' || p[1]=='.' || p[1]=='=')) { + const char *p0 = p+2; + int z = p[1]; + p+=3; + while (p[-1]!=z || p[0]!=']') p++; + if (z == ':' && p-1-p0 < 16) { + char buf[16]; + memcpy(buf, p0, p-1-p0); + buf[p-1-p0] = 0; + if (iswctype(k, wctype(buf)) || + iswctype(kfold, wctype(buf))) + return !inv; + } + continue; + } + if (*p < 128U) { + wc = (unsigned char)*p; + } else { + int l = mbtowc(&wc, p, 4); + if (l < 0) return 0; + p += l-1; + } + if (wc==k || wc==kfold) return !inv; + } + return inv; +} + +static int fnmatch_internal(const char *pat, size_t m, const char *str, size_t n) +{ + const char *p, *ptail, *endpat; + const char *s, *stail, *endstr; + size_t pinc, sinc, tailcnt=0; + int c, k, kfold; + + for (;;) { + switch ((c = pat_next(pat, m, &pinc))) { + case UNMATCHABLE: + return FNM_NOMATCH; + case STAR: + pat++; + m--; + break; + default: + k = str_next(str, n, &sinc); + if (k <= 0) + return (c==END) ? 0 : FNM_NOMATCH; + str += sinc; + n -= sinc; + kfold = k; + if (c == BRACKET) { + if (!match_bracket(pat, k, kfold)) + return FNM_NOMATCH; + } else if (c != QUESTION && k != c && kfold != c) { + return FNM_NOMATCH; + } + pat+=pinc; + m-=pinc; + continue; + } + break; + } + + /* Compute real pat length if it was initially unknown/-1 */ + m = strnlen(pat, m); + endpat = pat + m; + + /* Find the last * in pat and count chars needed after it */ + for (p=ptail=pat; pstr && tailcnt; tailcnt--) { + if (s[-1] < 128U || MB_CUR_MAX==1) s--; + else while ((unsigned char)*--s-0x80U<0x40 && s>str); + } + if (tailcnt) return FNM_NOMATCH; + stail = s; + + /* Check that the pat and str tails match */ + p = ptail; + for (;;) { + c = pat_next(p, endpat-p, &pinc); + p += pinc; + if ((k = str_next(s, endstr-s, &sinc)) <= 0) { + if (c != END) return FNM_NOMATCH; + break; + } + s += sinc; + kfold = k; + if (c == BRACKET) { + if (!match_bracket(p-pinc, k, kfold)) + return FNM_NOMATCH; + } else if (c != QUESTION && k != c && kfold != c) { + return FNM_NOMATCH; + } + } + + /* We're all done with the tails now, so throw them out */ + endstr = stail; + endpat = ptail; + + /* Match pattern components until there are none left */ + while (pat 0) str += sinc; + else for (str++; str_next(str, endstr-str, &sinc)<0; str++); + } + + return 0; +} + +int fnmatch(const char *pat, const char *str, int flags) +{ + const char *s, *p; + size_t inc; + int c; + if (flags & FNM_PATHNAME) for (;;) { + for (s=str; *s && *s!='/'; s++); + for (p=pat; (c=pat_next(p, -1, &inc))!=END && c!='/'; p+=inc); + if (c!=*s) + return FNM_NOMATCH; + if (fnmatch_internal(pat, p-pat, str, s-str)) + return FNM_NOMATCH; + if (!c) return 0; + str = s+1; + pat = p+inc; + } + return fnmatch_internal(pat, -1, str, -1); +} +#endif /* HAVE_FNMATCH */ diff --git a/lib/fstree/fstree_from_file.c b/lib/fstree/fstree_from_file.c index 9a34b36..dd7ca22 100644 --- a/lib/fstree/fstree_from_file.c +++ b/lib/fstree/fstree_from_file.c @@ -8,8 +8,8 @@ #include "fstree.h" #include "fstream.h" +#include "compat.h" -#include #include #include #include diff --git a/licenses/musl.txt b/licenses/musl.txt new file mode 100644 index 0000000..c1628e9 --- /dev/null +++ b/licenses/musl.txt @@ -0,0 +1,193 @@ +musl as a whole is licensed under the following standard MIT license: + +---------------------------------------------------------------------- +Copyright © 2005-2020 Rich Felker, et al. + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +---------------------------------------------------------------------- + +Authors/contributors include: + +A. Wilcox +Ada Worcester +Alex Dowad +Alex Suykov +Alexander Monakov +Andre McCurdy +Andrew Kelley +Anthony G. Basile +Aric Belsito +Arvid Picciani +Bartosz Brachaczek +Benjamin Peterson +Bobby Bingham +Boris Brezillon +Brent Cook +Chris Spiegel +Clément Vasseur +Daniel Micay +Daniel Sabogal +Daurnimator +David Carlier +David Edelsohn +Denys Vlasenko +Dmitry Ivanov +Dmitry V. Levin +Drew DeVault +Emil Renner Berthing +Fangrui Song +Felix Fietkau +Felix Janda +Gianluca Anzolin +Hauke Mehrtens +He X +Hiltjo Posthuma +Isaac Dunham +Jaydeep Patil +Jens Gustedt +Jeremy Huntwork +Jo-Philipp Wich +Joakim Sindholt +John Spencer +Julien Ramseier +Justin Cormack +Kaarle Ritvanen +Khem Raj +Kylie McClain +Leah Neukirchen +Luca Barbato +Luka Perkov +M Farkas-Dyck (Strake) +Mahesh Bodapati +Markus Wichmann +Masanori Ogino +Michael Clark +Michael Forney +Mikhail Kremnyov +Natanael Copa +Nicholas J. Kain +orc +Pascal Cuoq +Patrick Oppenlander +Petr Hosek +Petr Skocik +Pierre Carrier +Reini Urban +Rich Felker +Richard Pennington +Ryan Fairfax +Samuel Holland +Segev Finer +Shiz +sin +Solar Designer +Stefan Kristiansson +Stefan O'Rear +Szabolcs Nagy +Timo Teräs +Trutz Behn +Valentin Ochs +Will Dietz +William Haddon +William Pitcock + +Portions of this software are derived from third-party works licensed +under terms compatible with the above MIT license: + +The TRE regular expression implementation (src/regex/reg* and +src/regex/tre*) is Copyright © 2001-2008 Ville Laurikari and licensed +under a 2-clause BSD license (license text in the source files). The +included version has been heavily modified by Rich Felker in 2012, in +the interests of size, simplicity, and namespace cleanliness. + +Much of the math library code (src/math/* and src/complex/*) is +Copyright © 1993,2004 Sun Microsystems or +Copyright © 2003-2011 David Schultz or +Copyright © 2003-2009 Steven G. Kargl or +Copyright © 2003-2009 Bruce D. Evans or +Copyright © 2008 Stephen L. Moshier or +Copyright © 2017-2018 Arm Limited +and labelled as such in comments in the individual source files. All +have been licensed under extremely permissive terms. + +The ARM memcpy code (src/string/arm/memcpy.S) is Copyright © 2008 +The Android Open Source Project and is licensed under a two-clause BSD +license. It was taken from Bionic libc, used on Android. + +The AArch64 memcpy and memset code (src/string/aarch64/*) are +Copyright © 1999-2019, Arm Limited. + +The implementation of DES for crypt (src/crypt/crypt_des.c) is +Copyright © 1994 David Burren. It is licensed under a BSD license. + +The implementation of blowfish crypt (src/crypt/crypt_blowfish.c) was +originally written by Solar Designer and placed into the public +domain. The code also comes with a fallback permissive license for use +in jurisdictions that may not recognize the public domain. + +The smoothsort implementation (src/stdlib/qsort.c) is Copyright © 2011 +Valentin Ochs and is licensed under an MIT-style license. + +The x86_64 port was written by Nicholas J. Kain and is licensed under +the standard MIT terms. + +The mips and microblaze ports were originally written by Richard +Pennington for use in the ellcc project. The original code was adapted +by Rich Felker for build system and code conventions during upstream +integration. It is licensed under the standard MIT terms. + +The mips64 port was contributed by Imagination Technologies and is +licensed under the standard MIT terms. + +The powerpc port was also originally written by Richard Pennington, +and later supplemented and integrated by John Spencer. It is licensed +under the standard MIT terms. + +All other files which have no copyright comments are original works +produced specifically for use as part of this library, written either +by Rich Felker, the main author of the library, or by one or more +contibutors listed above. Details on authorship of individual files +can be found in the git version control history of the project. The +omission of copyright and license comments in each file is in the +interest of source tree size. + +In addition, permission is hereby granted for all public header files +(include/* and arch/*/bits/*) and crt files intended to be linked into +applications (crt/*, ldso/dlstart.c, and arch/*/crt_arch.h) to omit +the copyright notice and permission notice otherwise required by the +license, and to use these files without any requirement of +attribution. These files include substantial contributions from: + +Bobby Bingham +John Spencer +Nicholas J. Kain +Rich Felker +Richard Pennington +Stefan Kristiansson +Szabolcs Nagy + +all of whom have explicitly granted such permission. + +This file previously contained text expressing a belief that most of +the files covered by the above exception were sufficiently trivial not +to be subject to copyright, resulting in confusion over whether it +negated the permissions granted in the license. In the spirit of +permissive licensing, and of not having licensing issues being an +obstacle to adoption, that text has been removed. -- cgit v1.2.3