[PATCH 0/3] string: import strverscmp_improved from systemd

[PATCH 0/3] string: import strverscmp_improved from systemd

[Ahmad Fatoum]

The Boot Loader specification now references the UAPI group's version
format specification[1] on how blspec entries should be sorted.

In preparation of aligning barebox entry sorting with the specification,
import systemd's strverscmp_improved as strverscmp and add some tests
for it.

The changes to bootloader spec sorting need some more testing and will
follow separately.

Ahmad Fatoum (3):
  include: sync min/max definitions with Linux
  include: minmax.h: implement compare3 helper
  string: import strverscmp_improved from systemd

 include/linux/const.h  |   9 ++
 include/linux/kernel.h | 123 +--------------------------
 include/linux/minmax.h | 189 +++++++++++++++++++++++++++++++++++++++++
 include/string.h       |   2 +
 lib/Kconfig            |   9 +-
 lib/Makefile           |   1 +
 lib/strverscmp.c       | 165 +++++++++++++++++++++++++++++++++++
 test/self/Kconfig      |   6 ++
 test/self/Makefile     |   1 +
 test/self/string.c     | 175 ++++++++++++++++++++++++++++++++++++++
 10 files changed, 557 insertions(+), 123 deletions(-)
 create mode 100644 include/linux/minmax.h
 create mode 100644 lib/strverscmp.c
 create mode 100644 test/self/string.c

-- 
2.38.5

[PATCH 1/3] include: sync min/max definitions with Linux

[Ahmad Fatoum]

By syncing to Linux, min/max and friends now return constant expressions
if possible, which makes them suitable for use as non-VLA array length.

Signed-off-by: Ahmad Fatoum <ahmad@a3f.at>
---
 include/linux/const.h  |   9 +++
 include/linux/kernel.h | 123 +-----------------------------
 include/linux/minmax.h | 169 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 179 insertions(+), 122 deletions(-)
 create mode 100644 include/linux/minmax.h

diff --git a/include/linux/const.h b/include/linux/const.h
index 07f886d27155..0acddd3a0ed6 100644
--- a/include/linux/const.h
+++ b/include/linux/const.h
@@ -26,4 +26,13 @@
 #define _BITUL(x)	(_AC(1,UL) << (x))
 #define _BITULL(x)	(_AC(1,ULL) << (x))
 
+
+/*
+ * This returns a constant expression while determining if an argument is
+ * a constant expression, most importantly without evaluating the argument.
+ * Glory to Martin Uecker <Martin.Uecker@med.uni-goettingen.de>
+ */
+#define __is_constexpr(x) \
+	(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))
+
 #endif /* !(_LINUX_CONST_H) */
diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 0eb7bd21fe93..bf820de22ca7 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -8,6 +8,7 @@
 #include <linux/limits.h>
 #include <linux/math64.h>
 #include <linux/container_of.h>
+#include <linux/minmax.h>
 
 #define ALIGN(x, a)		__ALIGN_MASK(x, (typeof(x))(a) - 1)
 #define ALIGN_DOWN(x, a)	ALIGN((x) - ((a) - 1), (a))
@@ -88,121 +89,6 @@ extern long simple_strtol(const char *,char **,unsigned int);
 extern unsigned long long simple_strtoull(const char *,char **,unsigned int);
 extern long long simple_strtoll(const char *,char **,unsigned int);
 
-/*
- * min()/max()/clamp() macros that also do
- * strict type-checking.. See the
- * "unnecessary" pointer comparison.
- */
-#define min(x, y) ({				\
-	typeof(x) _min1 = (x);			\
-	typeof(y) _min2 = (y);			\
-	(void) (&_min1 == &_min2);		\
-	_min1 < _min2 ? _min1 : _min2; })
-
-#define max(x, y) ({				\
-	typeof(x) _max1 = (x);			\
-	typeof(y) _max2 = (y);			\
-	(void) (&_max1 == &_max2);		\
-	_max1 > _max2 ? _max1 : _max2; })
-
-#define min3(x, y, z) ({			\
-	typeof(x) _min1 = (x);			\
-	typeof(y) _min2 = (y);			\
-	typeof(z) _min3 = (z);			\
-	(void) (&_min1 == &_min2);		\
-	(void) (&_min1 == &_min3);		\
-	_min1 < _min2 ? (_min1 < _min3 ? _min1 : _min3) :	\
-		(_min2 < _min3 ? _min2 : _min3); })
-
-#define max3(x, y, z) ({			\
-	typeof(x) _max1 = (x);			\
-	typeof(y) _max2 = (y);			\
-	typeof(z) _max3 = (z);			\
-	(void) (&_max1 == &_max2);		\
-	(void) (&_max1 == &_max3);		\
-	_max1 > _max2 ? (_max1 > _max3 ? _max1 : _max3) :	\
-		(_max2 > _max3 ? _max2 : _max3); })
-
-/**
- * min_not_zero - return the minimum that is _not_ zero, unless both are zero
- * @x: value1
- * @y: value2
- */
-#define min_not_zero(x, y) ({			\
-	typeof(x) __x = (x);			\
-	typeof(y) __y = (y);			\
-	__x == 0 ? __y : ((__y == 0) ? __x : min(__x, __y)); })
-
-/**
- * clamp - return a value clamped to a given range with strict typechecking
- * @val: current value
- * @min: minimum allowable value
- * @max: maximum allowable value
- *
- * This macro does strict typechecking of min/max to make sure they are of the
- * same type as val.  See the unnecessary pointer comparisons.
- */
-#define clamp(val, min, max) ({			\
-	typeof(val) __val = (val);		\
-	typeof(min) __min = (min);		\
-	typeof(max) __max = (max);		\
-	(void) (&__val == &__min);		\
-	(void) (&__val == &__max);		\
-	__val = __val < __min ? __min: __val;	\
-	__val > __max ? __max: __val; })
-
-/*
- * ..and if you can't take the strict
- * types, you can specify one yourself.
- *
- * Or not use min/max/clamp at all, of course.
- */
-#define min_t(type, x, y) ({			\
-	type __min1 = (x);			\
-	type __min2 = (y);			\
-	__min1 < __min2 ? __min1: __min2; })
-
-#define max_t(type, x, y) ({			\
-	type __max1 = (x);			\
-	type __max2 = (y);			\
-	__max1 > __max2 ? __max1: __max2; })
-
-/**
- * clamp_t - return a value clamped to a given range using a given type
- * @type: the type of variable to use
- * @val: current value
- * @min: minimum allowable value
- * @max: maximum allowable value
- *
- * This macro does no typechecking and uses temporary variables of type
- * 'type' to make all the comparisons.
- */
-#define clamp_t(type, val, min, max) ({		\
-	type __val = (val);			\
-	type __min = (min);			\
-	type __max = (max);			\
-	__val = __val < __min ? __min: __val;	\
-	__val > __max ? __max: __val; })
-
-/**
- * clamp_val - return a value clamped to a given range using val's type
- * @val: current value
- * @min: minimum allowable value
- * @max: maximum allowable value
- *
- * This macro does no typechecking and uses temporary variables of whatever
- * type the input argument 'val' is.  This is useful when val is an unsigned
- * type and min and max are literals that will otherwise be assigned a signed
- * integer type.
- */
-#define clamp_val(val, min, max) ({		\
-	typeof(val) __val = (val);		\
-	typeof(val) __min = (min);		\
-	typeof(val) __max = (max);		\
-	__val = __val < __min ? __min: __val;	\
-	__val > __max ? __max: __val; })
-
-
 /* The `const' in roundup() prevents gcc-3.3 from calling __divdi3 */
 #define roundup(x, y) (					\
 {							\
@@ -257,13 +143,6 @@ extern int hex_to_bin(char ch);
 extern int __must_check hex2bin(u8 *dst, const char *src, size_t count);
 extern char *bin2hex(char *dst, const void *src, size_t count);
 
-/*
- * swap - swap value of @a and @b
- */
-#define swap(a, b) \
-	do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
-
-
 /* Internal, do not use. */
 int __must_check _kstrtoul(const char *s, unsigned int base, unsigned long *res);
 int __must_check _kstrtol(const char *s, unsigned int base, long *res);
diff --git a/include/linux/minmax.h b/include/linux/minmax.h
new file mode 100644
index 000000000000..396df1121bff
--- /dev/null
+++ b/include/linux/minmax.h
@@ -0,0 +1,169 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _LINUX_MINMAX_H
+#define _LINUX_MINMAX_H
+
+#include <linux/const.h>
+
+/*
+ * min()/max()/clamp() macros must accomplish three things:
+ *
+ * - avoid multiple evaluations of the arguments (so side-effects like
+ *   "x++" happen only once) when non-constant.
+ * - perform strict type-checking (to generate warnings instead of
+ *   nasty runtime surprises). See the "unnecessary" pointer comparison
+ *   in __typecheck().
+ * - retain result as a constant expressions when called with only
+ *   constant expressions (to avoid tripping VLA warnings in stack
+ *   allocation usage).
+ */
+#define __typecheck(x, y) \
+	(!!(sizeof((typeof(x) *)1 == (typeof(y) *)1)))
+
+#define __no_side_effects(x, y) \
+		(__is_constexpr(x) && __is_constexpr(y))
+
+#define __safe_cmp(x, y) \
+		(__typecheck(x, y) && __no_side_effects(x, y))
+
+#define __cmp(x, y, op)	((x) op (y) ? (x) : (y))
+
+#define __cmp_once(x, y, unique_x, unique_y, op) ({	\
+		typeof(x) unique_x = (x);		\
+		typeof(y) unique_y = (y);		\
+		__cmp(unique_x, unique_y, op); })
+
+#define __careful_cmp(x, y, op) \
+	__builtin_choose_expr(__safe_cmp(x, y), \
+		__cmp(x, y, op), \
+		__cmp_once(x, y, __UNIQUE_ID(__x), __UNIQUE_ID(__y), op))
+
+#define __clamp(val, lo, hi)	\
+	((val) >= (hi) ? (hi) : ((val) <= (lo) ? (lo) : (val)))
+
+#define __clamp_once(val, lo, hi, unique_val, unique_lo, unique_hi) ({	\
+		typeof(val) unique_val = (val);				\
+		typeof(lo) unique_lo = (lo);				\
+		typeof(hi) unique_hi = (hi);				\
+		__clamp(unique_val, unique_lo, unique_hi); })
+
+#define __clamp_input_check(lo, hi)					\
+        (BUILD_BUG_ON_ZERO(__builtin_choose_expr(			\
+                __is_constexpr((lo) > (hi)), (lo) > (hi), false)))
+
+#define __careful_clamp(val, lo, hi) ({					\
+	__clamp_input_check(lo, hi) +					\
+	__builtin_choose_expr(__typecheck(val, lo) && __typecheck(val, hi) && \
+			      __typecheck(hi, lo) && __is_constexpr(val) && \
+			      __is_constexpr(lo) && __is_constexpr(hi),	\
+		__clamp(val, lo, hi),					\
+		__clamp_once(val, lo, hi, __UNIQUE_ID(__val),		\
+			     __UNIQUE_ID(__lo), __UNIQUE_ID(__hi))); })
+
+/**
+ * min - return minimum of two values of the same or compatible types
+ * @x: first value
+ * @y: second value
+ */
+#define min(x, y)	__careful_cmp(x, y, <)
+
+/**
+ * max - return maximum of two values of the same or compatible types
+ * @x: first value
+ * @y: second value
+ */
+#define max(x, y)	__careful_cmp(x, y, >)
+
+/**
+ * min3 - return minimum of three values
+ * @x: first value
+ * @y: second value
+ * @z: third value
+ */
+#define min3(x, y, z) min((typeof(x))min(x, y), z)
+
+/**
+ * max3 - return maximum of three values
+ * @x: first value
+ * @y: second value
+ * @z: third value
+ */
+#define max3(x, y, z) max((typeof(x))max(x, y), z)
+
+/**
+ * min_not_zero - return the minimum that is _not_ zero, unless both are zero
+ * @x: value1
+ * @y: value2
+ */
+#define min_not_zero(x, y) ({			\
+	typeof(x) __x = (x);			\
+	typeof(y) __y = (y);			\
+	__x == 0 ? __y : ((__y == 0) ? __x : min(__x, __y)); })
+
+/**
+ * clamp - return a value clamped to a given range with strict typechecking
+ * @val: current value
+ * @lo: lowest allowable value
+ * @hi: highest allowable value
+ *
+ * This macro does strict typechecking of @lo/@hi to make sure they are of the
+ * same type as @val.  See the unnecessary pointer comparisons.
+ */
+#define clamp(val, lo, hi) __careful_clamp(val, lo, hi)
+
+/*
+ * ..and if you can't take the strict
+ * types, you can specify one yourself.
+ *
+ * Or not use min/max/clamp at all, of course.
+ */
+
+/**
+ * min_t - return minimum of two values, using the specified type
+ * @type: data type to use
+ * @x: first value
+ * @y: second value
+ */
+#define min_t(type, x, y)	__careful_cmp((type)(x), (type)(y), <)
+
+/**
+ * max_t - return maximum of two values, using the specified type
+ * @type: data type to use
+ * @x: first value
+ * @y: second value
+ */
+#define max_t(type, x, y)	__careful_cmp((type)(x), (type)(y), >)
+
+/**
+ * clamp_t - return a value clamped to a given range using a given type
+ * @type: the type of variable to use
+ * @val: current value
+ * @lo: minimum allowable value
+ * @hi: maximum allowable value
+ *
+ * This macro does no typechecking and uses temporary variables of type
+ * @type to make all the comparisons.
+ */
+#define clamp_t(type, val, lo, hi) __careful_clamp((type)(val), (type)(lo), (type)(hi))
+
+/**
+ * clamp_val - return a value clamped to a given range using val's type
+ * @val: current value
+ * @lo: minimum allowable value
+ * @hi: maximum allowable value
+ *
+ * This macro does no typechecking and uses temporary variables of whatever
+ * type the input argument @val is.  This is useful when @val is an unsigned
+ * type and @lo and @hi are literals that will otherwise be assigned a signed
+ * integer type.
+ */
+#define clamp_val(val, lo, hi) clamp_t(typeof(val), val, lo, hi)
+
+/**
+ * swap - swap values of @a and @b
+ * @a: first value
+ * @b: second value
+ */
+#define swap(a, b) \
+	do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
+
+#endif	/* _LINUX_MINMAX_H */
-- 
2.38.5

[PATCH 2/3] include: minmax.h: implement compare3 helper

[Ahmad Fatoum]

Define the macro for use in comparison functions. The macro has the same
semantics as systemd's CMP() macro with the difference that it returns
constant expressions if possible.

Signed-off-by: Ahmad Fatoum <ahmad@a3f.at>
---
 include/linux/minmax.h | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/include/linux/minmax.h b/include/linux/minmax.h
index 396df1121bff..9b6ddad7b3f6 100644
--- a/include/linux/minmax.h
+++ b/include/linux/minmax.h
@@ -166,4 +166,24 @@
 #define swap(a, b) \
 	do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
 
+
+#define __compare3(x, y)	((x) < (y) ? -1 : (x) > (y) ? 1 : 0)
+
+#define __compare3_once(x, y, unique_x, unique_y) ({	\
+		typeof(x) unique_x = (x);		\
+		typeof(y) unique_y = (y);		\
+		__compare3(unique_x, unique_y); })
+
+/**
+ * compare3 - 3-way comparison of @x and @y
+ * @x: first value
+ * @y: second value
+ *
+ * returns -1 if x < y, 0 if x == y and 1 if x > y
+ */
+#define compare3(x, y) \
+	__builtin_choose_expr(__safe_cmp(x, y), \
+		__compare3(x, y), \
+		__compare3_once(x, y, __UNIQUE_ID(__x), __UNIQUE_ID(__y)))
+
 #endif	/* _LINUX_MINMAX_H */
-- 
2.38.5

[PATCH 3/3] string: import strverscmp_improved from systemd

[Ahmad Fatoum]

The Boot Loader specification now references the UAPI group's version
format specification[1] on how blspec entries should be sorted.

In preparation of aligning barebox entry sorting with the specification,
import systemd's strverscmp_improved as strverscmp and add some tests
for it.

The selftest is called string.c, because it indirectly tests some string
mangling function and in anticipation of adding more string tests in the
future.

[1]: https://uapi-group.org/specifications/specs/version_format_specification/#examples

Signed-off-by: Ahmad Fatoum <ahmad@a3f.at>
---
 include/string.h   |   2 +
 lib/Kconfig        |   9 ++-
 lib/Makefile       |   1 +
 lib/strverscmp.c   | 165 ++++++++++++++++++++++++++++++++++++++++++
 test/self/Kconfig  |   6 ++
 test/self/Makefile |   1 +
 test/self/string.c | 175 +++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 358 insertions(+), 1 deletion(-)
 create mode 100644 lib/strverscmp.c
 create mode 100644 test/self/string.c

diff --git a/include/string.h b/include/string.h
index 499f2ec03c02..43911b75762f 100644
--- a/include/string.h
+++ b/include/string.h
@@ -18,4 +18,6 @@ void *__nokasan_default_memcpy(void * dest,const void *src,size_t count);
 
 char *parse_assignment(char *str);
 
+int strverscmp(const char *a, const char *b);
+
 #endif /* __STRING_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index b8bc9d63d4f0..84d2a2573625 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -107,7 +107,7 @@ config IMAGE_SPARSE
 	bool
 
 config STMP_DEVICE
-	bool "STMP device support" if COMPILE_TEST
+	bool "STMP device support"
 
 config FSL_QE_FIRMWARE
 	select CRC32
@@ -167,6 +167,13 @@ config PROGRESS_NOTIFIER
 	  This is selected by boards that register a notifier to visualize
 	  progress, like blinking a LED during an update.
 
+config VERSION_CMP
+	bool "version comparison utilities" if COMPILE_TEST
+	help
+	  This is selected by code that needs to compare versions
+	  in a manner compatible with
+	    https://uapi-group.org/specifications/specs/version_format_specification
+
 config PRINTF_UUID
 	bool
 	default y if PRINTF_FULL
diff --git a/lib/Makefile b/lib/Makefile
index 38478625423b..185e6221fdd2 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -6,6 +6,7 @@ obj-pbl-y		+= ctype.o
 obj-y			+= rbtree.o
 obj-y			+= display_options.o
 obj-y			+= string.o
+obj-$(CONFIG_VERSION_CMP)	+= strverscmp.o
 obj-y			+= strtox.o
 obj-y			+= kstrtox.o
 obj-y			+= vsprintf.o
diff --git a/lib/strverscmp.c b/lib/strverscmp.c
new file mode 100644
index 000000000000..da2d284918e0
--- /dev/null
+++ b/lib/strverscmp.c
@@ -0,0 +1,165 @@
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Code taken from systemd src/fundamental/string-util-fundamental.c
+ * NOTE: Semantics differ from glibc strverscmp (e.g. handling of ~rc1)
+ */
+
+#include <string.h>
+#include <linux/ctype.h>
+#include <linux/export.h>
+
+static bool is_valid_version_char(char a)
+{
+        return isdigit(a) || isalpha(a) || a == '~' ||
+		a == '-' || a == '^' || a == '.';
+}
+
+int strverscmp(const char *a, const char *b)
+{
+        /* This function is similar to strverscmp(3), but it treats '-' and '.' as separators.
+         *
+         * The logic is based on rpm's rpmvercmp(), but unlike rpmvercmp(), it distiguishes e.g.
+         * '123a' and '123.a', with '123a' being newer.
+         *
+         * It allows direct comparison of strings which contain both a version and a release; e.g.
+         * '247.2-3.1.fc33.x86_64' or '5.11.0-0.rc5.20210128git76c057c84d28.137.fc34'.
+         *
+         * The input string is split into segments. Each segment is numeric or alphabetic, and may be
+         * prefixed with the following:
+         *  '~' : used for pre-releases, a segment prefixed with this is the oldest,
+         *  '-' : used for the separator between version and release,
+         *  '^' : used for patched releases, a segment with this is newer than one with '-'.
+         *  '.' : used for point releases.
+         * Note that no prefix segment is the newest. All non-supported characters are dropped, and
+         * handled as a separator of segments, e.g., '123_a' is equivalent to '123a'.
+         *
+         * By using this, version strings can be sorted like following:
+         *  (older) 122.1
+         *     ^    123~rc1-1
+         *     |    123
+         *     |    123-a
+         *     |    123-a.1
+         *     |    123-1
+         *     |    123-1.1
+         *     |    123^post1
+         *     |    123.a-1
+         *     |    123.1-1
+         *     v    123a-1
+         *  (newer) 124-1
+         */
+
+        a = a ?: "";
+        b = b ?: "";
+
+        for (;;) {
+                const char *aa, *bb;
+                int r;
+
+                /* Drop leading invalid characters. */
+                while (*a != '\0' && !is_valid_version_char(*a))
+                        a++;
+                while (*b != '\0' && !is_valid_version_char(*b))
+                        b++;
+
+                /* Handle '~'. Used for pre-releases, e.g. 123~rc1, or 4.5~alpha1 */
+                if (*a == '~' || *b == '~') {
+                        /* The string prefixed with '~' is older. */
+                        r = compare3(*a != '~', *b != '~');
+                        if (r != 0)
+                                return r;
+
+                        /* Now both strings are prefixed with '~'. Compare remaining strings. */
+                        a++;
+                        b++;
+                }
+
+                /* If at least one string reaches the end, then longer is newer.
+                 * Note that except for '~' prefixed segments, a string which has more segments is newer.
+                 * So, this check must be after the '~' check. */
+                if (*a == '\0' || *b == '\0')
+                        return compare3(*a, *b);
+
+                /* Handle '-', which separates version and release, e.g 123.4-3.1.fc33.x86_64 */
+                if (*a == '-' || *b == '-') {
+                        /* The string prefixed with '-' is older (e.g., 123-9 vs 123.1-1) */
+                        r = compare3(*a != '-', *b != '-');
+                        if (r != 0)
+                                return r;
+
+                        a++;
+                        b++;
+                }
+
+                /* Handle '^'. Used for patched release. */
+                if (*a == '^' || *b == '^') {
+                        r = compare3(*a != '^', *b != '^');
+                        if (r != 0)
+                                return r;
+
+                        a++;
+                        b++;
+                }
+
+                /* Handle '.'. Used for point releases. */
+                if (*a == '.' || *b == '.') {
+                        r = compare3(*a != '.', *b != '.');
+                        if (r != 0)
+                                return r;
+
+                        a++;
+                        b++;
+                }
+
+                if (isdigit(*a) || isdigit(*b)) {
+                        /* Find the leading numeric segments. One may be an empty string. So,
+                         * numeric segments are always newer than alpha segments. */
+                        for (aa = a; isdigit(*aa); aa++)
+                                ;
+                        for (bb = b; isdigit(*bb); bb++)
+                                ;
+
+                        /* Check if one of the strings was empty, but the other not. */
+                        r = compare3(a != aa, b != bb);
+                        if (r != 0)
+                                return r;
+
+                        /* Skip leading '0', to make 00123 equivalent to 123. */
+                        while (*a == '0')
+                                a++;
+                        while (*b == '0')
+                                b++;
+
+                        /* To compare numeric segments without parsing their values, first compare the
+                         * lengths of the segments. Eg. 12345 vs 123, longer is newer. */
+                        r = compare3(aa - a, bb - b);
+                        if (r != 0)
+                                return r;
+
+                        /* Then, compare them as strings. */
+                        r = compare3(strncmp(a, b, aa - a), 0);
+                        if (r != 0)
+                                return r;
+                } else {
+                        /* Find the leading non-numeric segments. */
+                        for (aa = a; isalpha(*aa); aa++)
+                                ;
+                        for (bb = b; isalpha(*bb); bb++)
+                                ;
+
+                        /* Note that the segments are usually not NUL-terminated. */
+                        r = compare3(strncmp(a, b, min(aa - a, bb - b)), 0);
+                        if (r != 0)
+                                return r;
+
+                        /* Longer is newer, e.g. abc vs abcde. */
+                        r = compare3(aa - a, bb - b);
+                        if (r != 0)
+                                return r;
+                }
+
+                /* The current segments are equivalent. Let's move to the next one. */
+                a = aa;
+                b = bb;
+        }
+}
+EXPORT_SYMBOL(strverscmp);
diff --git a/test/self/Kconfig b/test/self/Kconfig
index 1d6d8ab53a8d..d1ca6a701df3 100644
--- a/test/self/Kconfig
+++ b/test/self/Kconfig
@@ -38,6 +38,8 @@ config SELFTEST_ENABLE_ALL
 	imply SELFTEST_JSON
 	imply SELFTEST_DIGEST
 	imply SELFTEST_MMU
+	imply SELFTEST_REGULATOR
+	imply SELFTEST_STRING
 	help
 	  Selects all self-tests compatible with current configuration
 
@@ -81,4 +83,8 @@ config SELFTEST_DIGEST
 	depends on DIGEST
 	select PRINTF_HEXSTR
 
+config SELFTEST_STRING
+	bool "String library selftest"
+	select VERSION_CMP
+
 endif
diff --git a/test/self/Makefile b/test/self/Makefile
index 269de2e10e88..a66f34671e5a 100644
--- a/test/self/Makefile
+++ b/test/self/Makefile
@@ -11,6 +11,7 @@ obj-$(CONFIG_SELFTEST_FS_RAMFS) += ramfs.o
 obj-$(CONFIG_SELFTEST_JSON) += json.o
 obj-$(CONFIG_SELFTEST_DIGEST) += digest.o
 obj-$(CONFIG_SELFTEST_MMU) += mmu.o
+obj-$(CONFIG_SELFTEST_STRING) += string.o
 
 clean-files := *.dtb *.dtb.S .*.dtc .*.pre .*.dts *.dtb.z
 clean-files += *.dtbo *.dtbo.S .*.dtso
diff --git a/test/self/string.c b/test/self/string.c
new file mode 100644
index 000000000000..f03a7410cd64
--- /dev/null
+++ b/test/self/string.c
@@ -0,0 +1,175 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <common.h>
+#include <bselftest.h>
+#include <string.h>
+
+BSELFTEST_GLOBALS();
+
+static const char *strverscmp_expect_str(int expect)
+{
+	switch (expect) {
+	case -1: return "<";
+	case  0: return "==";
+	case  1: return ">";
+	default: return "?!";
+	}
+}
+
+static int strverscmp_assert_one(const char *lhs, const char *rhs, int expect)
+{
+	int actual;
+
+	total_tests++;
+
+	actual = strverscmp(lhs, rhs);
+	if (actual != expect) {
+		failed_tests++;
+		printf("(%s %s %s), but (%s %s %s) expected\n",
+		       lhs, strverscmp_expect_str(actual), rhs,
+		       lhs, strverscmp_expect_str(expect), rhs);
+	}
+
+	return actual;
+}
+
+static int __strverscmp_assert(char *expr)
+{
+	const char *token, *tokens[3];
+	int expect = -42;
+	int i = 0;
+
+	while ((token = strsep_unescaped(&expr, " "))) {
+		if (i == 3) {
+			pr_err("invalid expression\n");
+			return -EILSEQ;
+		}
+
+		tokens[i++] = token;
+	}
+
+	if (!strcmp(tokens[1], "<"))
+	    expect = -1;
+	else if (!strcmp(tokens[1], "=="))
+	    expect = 0;
+	else if (!strcmp(tokens[1], ">"))
+	    expect = 1;
+
+	return strverscmp_assert_one(tokens[0], tokens[2], expect);
+}
+
+#define strverscmp_assert(expr) ({ \
+	char __expr_mut[] = expr; \
+	__strverscmp_assert(__expr_mut); \
+})
+
+static void test_strverscmp_spec_examples(void)
+{
+	/*
+	 * Taken from specification at
+	 * https://uapi-group.org/specifications/specs/version_format_specification/#examples
+	 */
+	strverscmp_assert("11 == 11");
+	strverscmp_assert("systemd-123 == systemd-123");
+	strverscmp_assert("bar-123 < foo-123");
+	strverscmp_assert("123a > 123");
+	strverscmp_assert("123.a > 123");
+	strverscmp_assert("123.a < 123.b");
+	strverscmp_assert("123a > 123.a");
+	strverscmp_assert("11α == 11β");
+	strverscmp_assert("A < a");
+	strverscmp_assert_one("", "0", -1);
+	strverscmp_assert("0. > 0");
+	strverscmp_assert("0.0 > 0");
+	strverscmp_assert("0 > ~");
+	strverscmp_assert_one("", "~", 1);
+	strverscmp_assert("1_ == 1");
+	strverscmp_assert("_1 == 1");
+	strverscmp_assert("1_ < 1.2");
+	strverscmp_assert("1_2_3 > 1.3.3");
+	strverscmp_assert("1+ == 1");
+	strverscmp_assert("+1 == 1");
+	strverscmp_assert("1+ < 1.2");
+	strverscmp_assert("1+2+3 > 1.3.3");
+}
+
+static void test_strverscmp_one(const char *newer, const char *older)
+{
+        strverscmp_assert_one(newer, newer,  0);
+        strverscmp_assert_one(newer, older,  1);
+        strverscmp_assert_one(older, newer, -1);
+        strverscmp_assert_one(older, older,  0);
+}
+
+static void test_strverscmp_spec_systemd(void)
+{
+	/*
+	 * Taken from systemd tests at
+	 * 87b7d9b6ff23ec10b66bf53efeabf16ad85d7ad8
+	 */
+        static const char * const versions[] = {
+                "~1", "", "ab", "abb", "abc", "0001", "002", "12", "122", "122.9",
+                "123~rc1", "123", "123-a", "123-a.1", "123-a1", "123-a1.1", "123-3",
+                "123-3.1", "123^patch1", "123^1", "123.a-1" "123.1-1", "123a-1", "124",
+                NULL,
+        };
+        const char * const *p, * const *q;
+
+	for (p = versions; *p; p++)
+		for (q = p + 1; *q; q++)
+                        test_strverscmp_one(*q, *p);
+
+        test_strverscmp_one("123.45-67.89", "123.45-67.88");
+        test_strverscmp_one("123.45-67.89a", "123.45-67.89");
+        test_strverscmp_one("123.45-67.89", "123.45-67.ab");
+        test_strverscmp_one("123.45-67.89", "123.45-67.9");
+        test_strverscmp_one("123.45-67.89", "123.45-67");
+        test_strverscmp_one("123.45-67.89", "123.45-66.89");
+        test_strverscmp_one("123.45-67.89", "123.45-9.99");
+        test_strverscmp_one("123.45-67.89", "123.42-99.99");
+        test_strverscmp_one("123.45-67.89", "123-99.99");
+
+        /* '~' : pre-releases */
+        test_strverscmp_one("123.45-67.89", "123~rc1-99.99");
+        test_strverscmp_one("123-45.67.89", "123~rc1-99.99");
+        test_strverscmp_one("123~rc2-67.89", "123~rc1-99.99");
+        test_strverscmp_one("123^aa2-67.89", "123~rc1-99.99");
+        test_strverscmp_one("123aa2-67.89", "123~rc1-99.99");
+
+        /* '-' : separator between version and release. */
+        test_strverscmp_one("123.45-67.89", "123-99.99");
+        test_strverscmp_one("123^aa2-67.89", "123-99.99");
+        test_strverscmp_one("123aa2-67.89", "123-99.99");
+
+        /* '^' : patch releases */
+        test_strverscmp_one("123.45-67.89", "123^45-67.89");
+        test_strverscmp_one("123^aa2-67.89", "123^aa1-99.99");
+        test_strverscmp_one("123aa2-67.89", "123^aa2-67.89");
+
+        /* '.' : point release */
+        test_strverscmp_one("123aa2-67.89", "123.aa2-67.89");
+        test_strverscmp_one("123.ab2-67.89", "123.aa2-67.89");
+
+        /* invalid characters */
+        strverscmp_assert_one("123_aa2-67.89", "123aa+2-67.89", 0);
+}
+
+static void test_strverscmp(void)
+{
+	test_strverscmp_spec_examples();
+	test_strverscmp_spec_systemd();
+
+	/* and now some corner cases */
+	strverscmp_assert_one(NULL, NULL, 0);
+	strverscmp_assert_one(NULL, "", 0);
+	strverscmp_assert_one("", NULL, 0);
+	strverscmp_assert_one("", "", 0);
+}
+
+static void test_string(void)
+{
+	test_strverscmp();
+}
+bselftest(parser, test_string);
-- 
2.38.5

Re: [PATCH 0/3] string: import strverscmp_improved from systemd

[Sascha Hauer]

On Wed, May 31, 2023 at 08:28:50AM +0200, Ahmad Fatoum wrote:
> The Boot Loader specification now references the UAPI group's version
> format specification[1] on how blspec entries should be sorted.
> 
> In preparation of aligning barebox entry sorting with the specification,
> import systemd's strverscmp_improved as strverscmp and add some tests
> for it.
> 
> The changes to bootloader spec sorting need some more testing and will
> follow separately.
> 
> Ahmad Fatoum (3):
>   include: sync min/max definitions with Linux
>   include: minmax.h: implement compare3 helper
>   string: import strverscmp_improved from systemd

Applied, thanks

Sascha

> 
>  include/linux/const.h  |   9 ++
>  include/linux/kernel.h | 123 +--------------------------
>  include/linux/minmax.h | 189 +++++++++++++++++++++++++++++++++++++++++
>  include/string.h       |   2 +
>  lib/Kconfig            |   9 +-
>  lib/Makefile           |   1 +
>  lib/strverscmp.c       | 165 +++++++++++++++++++++++++++++++++++
>  test/self/Kconfig      |   6 ++
>  test/self/Makefile     |   1 +
>  test/self/string.c     | 175 ++++++++++++++++++++++++++++++++++++++
>  10 files changed, 557 insertions(+), 123 deletions(-)
>  create mode 100644 include/linux/minmax.h
>  create mode 100644 lib/strverscmp.c
>  create mode 100644 test/self/string.c
> 
> -- 
> 2.38.5
> 
> 
> 

-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |