Add libcompat fallback implementation for fnmatch

This has basically been copied over from Musl and slightly modifed.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

7 files changed, 520 insertions, 4 deletions

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 <fnmatch.h>
+#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 <string.h>
+#include <stdlib.h>
+
+#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<m) if (pat[k] == '^' || pat[k] == '!') k++;
+		if (k<m) if (pat[k] == ']') k++;
+		for (; k<m && pat[k] && pat[k]!=']'; k++) {
+			if (k+1<m && pat[k+1] && pat[k]=='[' && (pat[k+1]==':' || pat[k+1]=='.' || pat[k+1]=='=')) {
+				int z = pat[k+1];
+				k+=2;
+				if (k<m && pat[k]) k++;
+				while (k<m && pat[k] && (pat[k-1]!=z || pat[k]!=']')) k++;
+				if (k==m || !pat[k]) break;
+			}
+		}
+		if (k==m || !pat[k]) {
+			*step = 1;
+			return '[';
+		}
+		*step = k+1;
+		return BRACKET;
+	}
+	if (pat[0] == '*')
+		return STAR;
+	if (pat[0] == '?')
+		return QUESTION;
+escaped:
+	if (pat[0] >= 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; p<endpat; p+=pinc) {
+		switch (pat_next(p, endpat-p, &pinc)) {
+		case UNMATCHABLE:
+			return FNM_NOMATCH;
+		case STAR:
+			tailcnt=0;
+			ptail = p+1;
+			break;
+		default:
+			tailcnt++;
+			break;
+		}
+	}
+
+	/* Past this point we need not check for UNMATCHABLE in pat,
+	 * because all of pat has already been parsed once. */
+
+	/* Compute real str length if it was initially unknown/-1 */
+	n = strnlen(str, n);
+	endstr = str + n;
+	if (n < tailcnt) return FNM_NOMATCH;
+
+	/* Find the final tailcnt chars of str, accounting for UTF-8.
+	 * On illegal sequences we may get it wrong, but in that case
+	 * we necessarily have a matching failure anyway. */
+	for (s=endstr; s>str && 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<endpat) {
+		p = pat;
+		s = str;
+		for (;;) {
+			c = pat_next(p, endpat-p, &pinc);
+			p += pinc;
+			/* Encountering * completes/commits a component */
+			if (c == STAR) {
+				pat = p;
+				str = s;
+				break;
+			}
+			k = str_next(s, endstr-s, &sinc);
+			if (!k)
+				return FNM_NOMATCH;
+			kfold = k;
+			if (c == BRACKET) {
+				if (!match_bracket(p-pinc, k, kfold))
+					break;
+			} else if (c != QUESTION && k != c && kfold != c) {
+				break;
+			}
+			s += sinc;
+		}
+		if (c == STAR) continue;
+		/* If we failed, advance str, by 1 char if it's a valid
+		 * char, or past all invalid bytes otherwise. */
+		k = str_next(str, endstr-str, &sinc);
+		if (k > 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 <fnmatch.h>
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
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.