linux-kernel - [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20210824133351.88179-2-andriy.shevchenko@linux.intel.com>
Date:   Tue, 24 Aug 2021 16:33:50 +0300
From:   Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
To:     Mauro Carvalho Chehab <mchehab+huawei@...nel.org>,
        Sakari Ailus <sakari.ailus@...ux.intel.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        linux-media@...r.kernel.org, linux-kernel@...r.kernel.org
Cc:     Yong Zhi <yong.zhi@...el.com>, Bingbu Cao <bingbu.cao@...el.com>,
        Dan Scally <djrscally@...il.com>,
        Tianshu Qiu <tian.shu.qiu@...el.com>,
        Mauro Carvalho Chehab <mchehab@...nel.org>
Subject: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements

In some cases we want to circular shift an array of elements.
Introduce rotate() helper for that.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
---
 include/linux/sort.h |  3 +++
 lib/sort.c           | 61 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 64 insertions(+)

diff --git a/include/linux/sort.h b/include/linux/sort.h
index b5898725fe9d..c881acb12ffc 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -13,4 +13,7 @@ void sort(void *base, size_t num, size_t size,
 	  cmp_func_t cmp_func,
 	  swap_func_t swap_func);
 
+void rotate(void *base, size_t num, size_t size, size_t by,
+	    swap_func_t swap_func);
+
 #endif
diff --git a/lib/sort.c b/lib/sort.c
index d9b2f5b73620..b9243f8db34b 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -14,6 +14,7 @@
 
 #include <linux/types.h>
 #include <linux/export.h>
+#include <linux/minmax.h>
 #include <linux/sort.h>
 
 /**
@@ -275,3 +276,63 @@ void sort(void *base, size_t num, size_t size,
 	return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func);
 }
 EXPORT_SYMBOL(sort);
+
+/**
+ * rotate - rotate an array of elements by a number of elements
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @size: size of each element
+ * @by: number of elements to rotate by
+ * @swap_func: pointer to swap function or NULL
+ *
+ * Helper function to advance all the elements of a circular buffer by
+ * @by positions.
+ */
+void rotate(void *base, size_t num, size_t size, size_t by,
+	    swap_func_t swap_func)
+{
+	struct {
+		size_t begin, end;
+	} arr[2] = {
+		{ .begin = 0, .end = by - 1 },
+		{ .begin = by, .end = num - 1 },
+	};
+
+	swap_func = choose_swap_func(swap_func, base, size);
+
+#define CHUNK_SIZE(a) ((a)->end - (a)->begin + 1)
+
+	/* Loop as long as we have out-of-place entries */
+	while (CHUNK_SIZE(&arr[0]) && CHUNK_SIZE(&arr[1])) {
+		size_t size0, i;
+
+		/*
+		 * Find the number of entries that can be arranged on this
+		 * iteration.
+		 */
+		size0 = min(CHUNK_SIZE(&arr[0]), CHUNK_SIZE(&arr[1]));
+
+		/* Swap the entries in two parts of the array */
+		for (i = 0; i < size0; i++) {
+			void *a = base + size * (arr[0].begin + i);
+			void *b = base + size * (arr[1].begin + i);
+
+			do_swap(a, b, size, swap_func);
+		}
+
+		if (CHUNK_SIZE(&arr[0]) > CHUNK_SIZE(&arr[1])) {
+			/* The end of the first array remains unarranged */
+			arr[0].begin += size0;
+		} else {
+			/*
+			 * The first array is fully arranged so we proceed
+			 * handling the next one.
+			 */
+			arr[0].begin = arr[1].begin;
+			arr[0].end = arr[1].begin + size0 - 1;
+			arr[1].begin += size0;
+		}
+	}
+#undef CHUNK_SIZE
+}
+EXPORT_SYMBOL(rotate);
-- 
2.32.0