[alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Takashi Sakamoto]

Hi,

This patchset is a fix for bug issued in the message thread[1].

In this development period, alsa-lib got new API as implementation for
one of comparison algorithms to a pair of control element IDs. However,
it has several issues.

At first, the name, 'snd_ctl_elem_id_compare()', is inappropriate since it
implements one of comparison algorithms. The name itself implies the
algorithm is single and unique for control element ID. However, the
target structure, 'struct snd_ctl_elem_id', is hybrid and compound one.
We can not find such single and unique comparison algorithm for it.

Secondary, it subtracts a pair of values in fields of 'unsigned int' type
in storage size of the type. It brings integer overflow.

Tertiary, it has simple bug to compare subdevice field in the same structure.


Essentially, equality is different from comparison. In a point of programming,
implementation for comparison algorithm can have more overhead than
implementation for equality. In this meaning, it's better to add different API
for them.

This patchset adds new API below:

 * for equality
   * snd_ctl_elem_id_equal_by_numid()
   * snd_ctl_elem_id_equal_by_tuple()
 * for each comparison algorithm
   * snd_ctl_elem_id_compare_by_numid()
   * snd_ctl_elem_id_compare_by_tuple_arithmetic()

I've got bothered to decide the name of API for the case to use tuples.
Here I use the word, 'tuple', which comes from documentation of alsa-lib[2].

Furthermore, this patchset adds test program for them since equality and
comparison are quite basic method to operate data. It's better to have no
bug.

Finally, the issued API, 'snd_ctl_elem_id_compare()' is dropped. After
merging the patchset, I'm going to post additional patch to alsa-utils to
fix issued line[3].

[1] https://mailman.alsa-project.org/pipermail/alsa-devel/2021-March/181738.html
[2] https://github.com/alsa-project/alsa-lib/blob/master/src/control/control.c#L80
[3] https://github.com/alsa-project/alsa-utils/blob/master/alsactl/clean.c#L55

Regards

Takashi Sakamoto (6):
  test: ctl-elem-id: add test program for future APIs relevant to
    control element ID
  ctl: add API to check equality between a pair of control element IDs
    by numid
  ctl: add API to check equality between a pair of control element IDs
    by tuple
  ctl: add API to compare a pair of control element IDs by numid
  ctl: add API to compare a pair of control element IDs by one of
    algorithms according to tuple
  ctl: drop deprecated API to compare a pair of control element IDs

 include/control.h      |   5 +-
 src/control/control.c  | 135 ++++++++++++++----
 test/lsb/Makefile.am   |   6 +-
 test/lsb/ctl-elem-id.c | 301 +++++++++++++++++++++++++++++++++++++++++
 4 files changed, 418 insertions(+), 29 deletions(-)
 create mode 100644 test/lsb/ctl-elem-id.c

-- 
2.27.0

[alsa-lib][PATCH 1/6] test: ctl-elem-id: add test program for future APIs relevant to control element ID

[Takashi Sakamoto]

Some APIs are planned to add for equality check and comparison of a pair
of control element IDs. The equality check and comparison are quite
basic methods to operate data, thus it's preferable not to include any
bug.

This commit adds skeleton of test program for the APIs.

Signed-off-by: Takashi Sakamoto <o-takashi@sakamocchi.jp>
---
 test/lsb/Makefile.am   |  6 +++--
 test/lsb/ctl-elem-id.c | 61 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 65 insertions(+), 2 deletions(-)
 create mode 100644 test/lsb/ctl-elem-id.c

diff --git a/test/lsb/Makefile.am b/test/lsb/Makefile.am
index ceb4d715..7d5f754d 100644
--- a/test/lsb/Makefile.am
+++ b/test/lsb/Makefile.am
@@ -1,5 +1,7 @@
-TESTS  = config
-TESTS += midi_event
+TESTS = \
+	config \
+	midi_event \
+	ctl-elem-id
 check_PROGRAMS = $(TESTS)
 noinst_HEADERS = test.h
 
diff --git a/test/lsb/ctl-elem-id.c b/test/lsb/ctl-elem-id.c
new file mode 100644
index 00000000..ae416698
--- /dev/null
+++ b/test/lsb/ctl-elem-id.c
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+//
+// ctl-elem-id.c - a test program for equality and some comparison algorithms
+// for control element ID structure.
+//
+// Copyright (c) 2021 Takashi Sakamoto
+//
+// Licensed under the terms of the GNU General Public License, version 2.
+
+#include <stdlib.h>
+#include <stdint.h>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+
+#include <unistd.h>
+
+#include "../include/asoundlib.h"
+
+int main()
+{
+	void (*entries[])(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r) = {
+	};
+	int count = sizeof(entries) / sizeof(*entries);
+	int fd;
+	uint8_t *buf;
+	int i;
+
+	fd = open("/dev/urandom", O_RDONLY);
+	if (fd < 0)
+		return EXIT_FAILURE;
+
+	buf = calloc(snd_ctl_elem_id_sizeof(), 2);
+	if (buf == NULL)
+		goto error_urandom;
+
+	for (i = 0; i < count; ++i) {
+		snd_ctl_elem_id_t *l, *r;
+		ssize_t len;
+randomize:
+		len = read(fd, buf, snd_ctl_elem_id_sizeof() * 2);
+		if (len < 0)
+			goto error_memory;
+		l = (snd_ctl_elem_id_t *)buf;
+		r = (snd_ctl_elem_id_t *)(buf + snd_ctl_elem_id_sizeof());
+		if (!memcmp(l, r, snd_ctl_elem_id_sizeof()))
+			goto randomize;
+
+		entries[i](l, r);
+	}
+
+	free(buf);
+
+	return EXIT_SUCCESS;
+error_memory:
+	free(buf);
+error_urandom:
+	close(fd);
+	return EXIT_FAILURE;
+}
-- 
2.27.0

[alsa-lib][PATCH 2/6] ctl: add API to check equality between a pair of control element IDs by numid

[Takashi Sakamoto]

The structure for control element ID is hybrid. It has two ways to check
equality; e.g. equality of numid field, and equality of the other fields.
Just checking equality according to numid field, current alsa-lib take
userspace applications to call snd_ctl_elem_id_get_numid() twice. It's
better to add optimized version of the equality check.

This commit adds API to check equality of numid field for a pair of control
element IDs.

Signed-off-by: Takashi Sakamoto <o-takashi@sakamocchi.jp>
---
 include/control.h      |  1 +
 src/control/control.c  | 19 ++++++++++++++++
 test/lsb/ctl-elem-id.c | 50 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 70 insertions(+)

diff --git a/include/control.h b/include/control.h
index 40ac2e97..260d7f30 100644
--- a/include/control.h
+++ b/include/control.h
@@ -424,6 +424,7 @@ int snd_ctl_elem_id_malloc(snd_ctl_elem_id_t **ptr);
 void snd_ctl_elem_id_free(snd_ctl_elem_id_t *obj);
 void snd_ctl_elem_id_clear(snd_ctl_elem_id_t *obj);
 void snd_ctl_elem_id_copy(snd_ctl_elem_id_t *dst, const snd_ctl_elem_id_t *src);
+int snd_ctl_elem_id_equal_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_compare(snd_ctl_elem_id_t *id1, const snd_ctl_elem_id_t *id2);
 unsigned int snd_ctl_elem_id_get_numid(const snd_ctl_elem_id_t *obj);
 snd_ctl_elem_iface_t snd_ctl_elem_id_get_interface(const snd_ctl_elem_id_t *obj);
diff --git a/src/control/control.c b/src/control/control.c
index 197d4f52..6d1eda15 100644
--- a/src/control/control.c
+++ b/src/control/control.c
@@ -83,6 +83,8 @@ the same (driver updates can change it, but in practice this is
 rare). The numid can change on each boot. In case of an USB sound
 card, the numid can also change when it is reconnected.
 
+For equality check between a pair of #snd_ctl_elem_id_t according to the numid,
+snd_ctl_elem_id_equal_by_numid() is available.
 
 \section element_lists Element Lists
 
@@ -1818,6 +1820,23 @@ void snd_ctl_elem_id_copy(snd_ctl_elem_id_t *dst, const snd_ctl_elem_id_t *src)
 	*dst = *src;
 }
 
+/**
+ * \brief check equality between two arguments according to numid.
+ * \param l opaque pointer to element ID structure.
+ * \param r opaque pointer to another element ID structure.
+ * \retval zero if they equal, else zero.
+ *
+ * The structure underlying #snd_ctl_elem_id_t is hybrid one. It has two ways to
+ * check equality. The API implements one of the ways, according to the value of
+ * numid field.
+ */
+int snd_ctl_elem_id_equal_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	assert(l && r);
+
+	return l->numid == r->numid;
+}
+
 /**
  * \brief compare one #snd_ctl_elem_id_t to another
  * \param id1 pointer to first id
diff --git a/test/lsb/ctl-elem-id.c b/test/lsb/ctl-elem-id.c
index ae416698..f499b268 100644
--- a/test/lsb/ctl-elem-id.c
+++ b/test/lsb/ctl-elem-id.c
@@ -18,9 +18,59 @@
 
 #include "../include/asoundlib.h"
 
+static void set_elem_id_by_tuple(snd_ctl_elem_id_t *elem_id,
+				 snd_ctl_elem_iface_t iface,
+				 unsigned int device_id,
+				 unsigned int subdevice_id,
+				 const char *name,
+				 unsigned int index)
+{
+	snd_ctl_elem_id_set_interface(elem_id, iface);
+	snd_ctl_elem_id_set_device(elem_id, device_id);
+	snd_ctl_elem_id_set_subdevice(elem_id, subdevice_id);
+	snd_ctl_elem_id_set_name(elem_id, name);
+	snd_ctl_elem_id_set_index(elem_id, index);
+}
+
+// Case 0.0. The same value of numid field should result in true positive.
+static void equality_by_numid_0(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 33);
+	snd_ctl_elem_id_set_numid(r, 33);
+	assert(snd_ctl_elem_id_equal_by_numid(l, r));
+}
+
+// Case 0.1. The different value of numid field should result in false positive.
+static void equality_by_numid_1(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 333);
+	snd_ctl_elem_id_set_numid(r, 444);
+	assert(!snd_ctl_elem_id_equal_by_numid(l, r));
+}
+
+// Case 0.2. The same tuple should result in false positive.
+static void equality_by_numid_2(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_CARD, 0, 1, "something", 2);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_CARD, 0, 1, "something", 2);
+	assert(!snd_ctl_elem_id_equal_by_numid(l, r));
+}
+
+// Case 0.3. The tuple should result in false positive.
+static void equality_by_numid_3(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_CARD, 300, 400, "something", 500);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_MIXER, 600, 700, "something", 800);
+	assert(!snd_ctl_elem_id_equal_by_numid(l, r));
+}
+
 int main()
 {
 	void (*entries[])(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r) = {
+		equality_by_numid_0,
+		equality_by_numid_1,
+		equality_by_numid_2,
+		equality_by_numid_3,
 	};
 	int count = sizeof(entries) / sizeof(*entries);
 	int fd;
-- 
2.27.0

[alsa-lib][PATCH 3/6] ctl: add API to check equality between a pair of control element IDs by tuple

[Takashi Sakamoto]

The structure for control element ID is hybrid. It has two ways to check
equality; e.g. equality of fields except for numid. Just checking equality
according to the fields, current alsa-lib take userspace applications to call
functions referring to the fields several times. It's better to add optimized
version of the equality check.

This commit adds API to check the equality of fields for a pair of control
element IDs.

Signed-off-by: Takashi Sakamoto <o-takashi@sakamocchi.jp>
---
 include/control.h      |  1 +
 src/control/control.c  | 26 +++++++++++++++++++++++++-
 test/lsb/ctl-elem-id.c | 36 ++++++++++++++++++++++++++++++++++++
 3 files changed, 62 insertions(+), 1 deletion(-)

diff --git a/include/control.h b/include/control.h
index 260d7f30..8aca67e6 100644
--- a/include/control.h
+++ b/include/control.h
@@ -425,6 +425,7 @@ void snd_ctl_elem_id_free(snd_ctl_elem_id_t *obj);
 void snd_ctl_elem_id_clear(snd_ctl_elem_id_t *obj);
 void snd_ctl_elem_id_copy(snd_ctl_elem_id_t *dst, const snd_ctl_elem_id_t *src);
 int snd_ctl_elem_id_equal_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
+int snd_ctl_elem_id_equal_by_tuple(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_compare(snd_ctl_elem_id_t *id1, const snd_ctl_elem_id_t *id2);
 unsigned int snd_ctl_elem_id_get_numid(const snd_ctl_elem_id_t *obj);
 snd_ctl_elem_iface_t snd_ctl_elem_id_get_interface(const snd_ctl_elem_id_t *obj);
diff --git a/src/control/control.c b/src/control/control.c
index 6d1eda15..93f8f93d 100644
--- a/src/control/control.c
+++ b/src/control/control.c
@@ -84,7 +84,9 @@ rare). The numid can change on each boot. In case of an USB sound
 card, the numid can also change when it is reconnected.
 
 For equality check between a pair of #snd_ctl_elem_id_t according to the numid,
-snd_ctl_elem_id_equal_by_numid() is available.
+snd_ctl_elem_id_equal_by_numid() is available. For equality check between a pair
+of #snd_ctl_elem_id_t according to the tuple, snd_ctl_elem_id_equal_by_tuple()
+is available.
 
 \section element_lists Element Lists
 
@@ -1837,6 +1839,28 @@ int snd_ctl_elem_id_equal_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
 	return l->numid == r->numid;
 }
 
+/**
+ * \brief check equality between two arguments according to iface, device,
+ *	  subdevice, name, and index fields.
+ * \param l opaque pointer to element ID structure.
+ * \param r opaque pointer to another element ID structure.
+ * \retval zero if they equal, else zero.
+ *
+ * The structure underlying #snd_ctl_elem_id_t is hybrid one. It has two ways to
+ * check equality. The API implements one of the ways, according to the values
+ * of iface, device, subdevice, name, and index fields.
+ */
+int snd_ctl_elem_id_equal_by_tuple(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	assert(l && r);
+
+	return (l->iface == r->iface) &&
+	       (l->device == r->device) &&
+	       (l->subdevice == r->subdevice) &&
+	       !strcmp((const char *)l->name, (const char *)r->name) &&
+	       (l->index == r->index);
+}
+
 /**
  * \brief compare one #snd_ctl_elem_id_t to another
  * \param id1 pointer to first id
diff --git a/test/lsb/ctl-elem-id.c b/test/lsb/ctl-elem-id.c
index f499b268..39060a8e 100644
--- a/test/lsb/ctl-elem-id.c
+++ b/test/lsb/ctl-elem-id.c
@@ -64,6 +64,38 @@ static void equality_by_numid_3(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
 	assert(!snd_ctl_elem_id_equal_by_numid(l, r));
 }
 
+// Case 1.0. The same tuple should result in true positive.
+static void equality_by_tuple_0(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_CARD, 1000, 1010, "something", 1020);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_CARD, 1000, 1010, "something", 1020);
+	assert(snd_ctl_elem_id_equal_by_tuple(l, r));
+}
+
+// Case 1.1. The different conpounds should result in true positive.
+static void equality_by_tuple_1(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_CARD, 1030, 1040, "something", 1050);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_MIXER, 1031, 1042, "something", 1053);
+	assert(!snd_ctl_elem_id_equal_by_tuple(l, r));
+}
+
+// Case 1.2. The same value of numid field should result in false positive.
+static void equality_by_tuple_2(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 0xfeedc0de);
+	snd_ctl_elem_id_set_numid(r, 0xfeedc0de);
+	assert(!snd_ctl_elem_id_equal_by_tuple(l, r));
+}
+
+// Case 1.3. The different value of numid field should result in false positive.
+static void equality_by_tuple_3(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 0xfeedc0de);
+	snd_ctl_elem_id_set_numid(r, 0xdeadbeef);
+	assert(!snd_ctl_elem_id_equal_by_tuple(l, r));
+}
+
 int main()
 {
 	void (*entries[])(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r) = {
@@ -71,6 +103,10 @@ int main()
 		equality_by_numid_1,
 		equality_by_numid_2,
 		equality_by_numid_3,
+		equality_by_tuple_0,
+		equality_by_tuple_1,
+		equality_by_tuple_2,
+		equality_by_tuple_3,
 	};
 	int count = sizeof(entries) / sizeof(*entries);
 	int fd;
-- 
2.27.0

[alsa-lib][PATCH 4/6] ctl: add API to compare a pair of control element IDs by numid

[Takashi Sakamoto]

The structure for control element ID is compound one. It means that it's
not possible to decide single algorithm to find order of a pair of
control element IDs. For convenience of application developers, it's better
to produce API to decide the order by useful algorithm.

This commit adds API for one of comparison algorithms. The value of
numid field is used for the comparison. I note that the structure includes
some 'unsigned integer' type of fields. The subtraction of the fields
brings integer overflow as long as the calculation is done in the same
storage size of the type itself.

Signed-off-by: Takashi Sakamoto <o-takashi@sakamocchi.jp>
---
 include/control.h      |  1 +
 src/control/control.c  | 32 +++++++++++++++++++++++++++++++
 test/lsb/ctl-elem-id.c | 43 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 76 insertions(+)

diff --git a/include/control.h b/include/control.h
index 8aca67e6..36953423 100644
--- a/include/control.h
+++ b/include/control.h
@@ -426,6 +426,7 @@ void snd_ctl_elem_id_clear(snd_ctl_elem_id_t *obj);
 void snd_ctl_elem_id_copy(snd_ctl_elem_id_t *dst, const snd_ctl_elem_id_t *src);
 int snd_ctl_elem_id_equal_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_equal_by_tuple(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
+int snd_ctl_elem_id_compare_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_compare(snd_ctl_elem_id_t *id1, const snd_ctl_elem_id_t *id2);
 unsigned int snd_ctl_elem_id_get_numid(const snd_ctl_elem_id_t *obj);
 snd_ctl_elem_iface_t snd_ctl_elem_id_get_interface(const snd_ctl_elem_id_t *obj);
diff --git a/src/control/control.c b/src/control/control.c
index 93f8f93d..00009614 100644
--- a/src/control/control.c
+++ b/src/control/control.c
@@ -88,6 +88,10 @@ snd_ctl_elem_id_equal_by_numid() is available. For equality check between a pair
 of #snd_ctl_elem_id_t according to the tuple, snd_ctl_elem_id_equal_by_tuple()
 is available.
 
+Many algorithms can be defined to find ordered pair of #snd_ctl_elem_id_t.
+For one of the comparison algorithms according to the numid,
+snd_ctl_elem_id_compare_by_numid() is available.
+
 \section element_lists Element Lists
 
 An element list can be used to obtain a list of all elements of the
@@ -1861,6 +1865,34 @@ int snd_ctl_elem_id_equal_by_tuple(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
 	       (l->index == r->index);
 }
 
+static int compare_unsigned_integer(unsigned int l, unsigned int r)
+{
+	if (l == r)
+		return 0;
+	else if (l < r)
+		return -1;
+	else
+		return 1;
+}
+
+/**
+ * \brief compare two arguments as orderd items by algorithm according to numid.
+ * \param l opaque pointer to element ID structure.
+ * \param r opaque pointer to another element ID structure.
+ * \retval positive if left is greater than right, negative if left is less
+ *	   than right, zero if they equal.
+ *
+ * The structure underlying #snd_ctl_elem_id_t is compound one. The
+ * comparison algorithm for it is not single and unique. The API implements
+ * one of comparison algorithms, according to the value of numid field.
+ */
+int snd_ctl_elem_id_compare_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	assert(l && r);
+
+	return compare_unsigned_integer(l->numid, r->numid);
+}
+
 /**
  * \brief compare one #snd_ctl_elem_id_t to another
  * \param id1 pointer to first id
diff --git a/test/lsb/ctl-elem-id.c b/test/lsb/ctl-elem-id.c
index 39060a8e..670ec252 100644
--- a/test/lsb/ctl-elem-id.c
+++ b/test/lsb/ctl-elem-id.c
@@ -16,6 +16,8 @@
 
 #include <unistd.h>
 
+#include <limits.h>
+
 #include "../include/asoundlib.h"
 
 static void set_elem_id_by_tuple(snd_ctl_elem_id_t *elem_id,
@@ -96,6 +98,43 @@ static void equality_by_tuple_3(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
 	assert(!snd_ctl_elem_id_equal_by_tuple(l, r));
 }
 
+// Case 2.0. The left object with less value in numid field than right object
+//	     should result in negative value.
+static void comparison_by_numid_0(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 0xdeadbeef);
+	snd_ctl_elem_id_set_numid(r, 0xfeedc0de);
+	assert(snd_ctl_elem_id_compare_by_numid(l, r) < 0);
+}
+
+// Case 2.1. The left object with the same value in numid field as right object
+//	     should result in zero.
+static void comparison_by_numid_1(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 0xfeedc0de);
+	snd_ctl_elem_id_set_numid(r, 0xfeedc0de);
+	assert(snd_ctl_elem_id_compare_by_numid(l, r) == 0);
+}
+
+// Case 2.2. The left object with greater value in numid field than right object
+//	     should result in positive.
+static void comparison_by_numid_2(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 0xfeedc0de);
+	snd_ctl_elem_id_set_numid(r, 0xdeadbeef);
+	assert(snd_ctl_elem_id_compare_by_numid(l, r) > 0);
+}
+
+// Case 2.3. The left object with lesser value in numid field than right object
+//	     should result in negative. The subtraction shoud be calculated in
+//	     storage larger than the storage of 'unsigned int'.
+static void comparison_by_numid_3(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	snd_ctl_elem_id_set_numid(l, 0);
+	snd_ctl_elem_id_set_numid(r, UINT_MAX);
+	assert(snd_ctl_elem_id_compare_by_numid(l, r) < 0);
+}
+
 int main()
 {
 	void (*entries[])(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r) = {
@@ -107,6 +146,10 @@ int main()
 		equality_by_tuple_1,
 		equality_by_tuple_2,
 		equality_by_tuple_3,
+		comparison_by_numid_0,
+		comparison_by_numid_1,
+		comparison_by_numid_2,
+		comparison_by_numid_3,
 	};
 	int count = sizeof(entries) / sizeof(*entries);
 	int fd;
-- 
2.27.0

[alsa-lib][PATCH 5/6] ctl: add API to compare a pair of control element IDs by one of algorithms according to tuple

[Takashi Sakamoto]

The structure for control element ID is compound one. It means that it's
not possible to decide single algorithm to find order of a pair of
control element IDs. For convenience of application developers, it's better
to produce API to decide the order by useful algorithm.

This commit adds API for one of comparison algorithms. The fields except
for numid are used for the algorithm. The iface, device, subdevice,
name, and index fields are compared in the order, by arithmetic way. I note
that the structure includes some 'unsigned integer' type of fields. The
subtraction of the fields brings integer overflow as long as the
calculation is done in the same storage size of the type itself.

Signed-off-by: Takashi Sakamoto <o-takashi@sakamocchi.jp>
---
 include/control.h      |   1 +
 src/control/control.c  |  45 ++++++++++++++++-
 test/lsb/ctl-elem-id.c | 111 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 156 insertions(+), 1 deletion(-)

diff --git a/include/control.h b/include/control.h
index 36953423..1b2cc0c6 100644
--- a/include/control.h
+++ b/include/control.h
@@ -427,6 +427,7 @@ void snd_ctl_elem_id_copy(snd_ctl_elem_id_t *dst, const snd_ctl_elem_id_t *src);
 int snd_ctl_elem_id_equal_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_equal_by_tuple(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_compare_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
+int snd_ctl_elem_id_compare_by_tuple_arithmetic(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_compare(snd_ctl_elem_id_t *id1, const snd_ctl_elem_id_t *id2);
 unsigned int snd_ctl_elem_id_get_numid(const snd_ctl_elem_id_t *obj);
 snd_ctl_elem_iface_t snd_ctl_elem_id_get_interface(const snd_ctl_elem_id_t *obj);
diff --git a/src/control/control.c b/src/control/control.c
index 00009614..fbc6aeb7 100644
--- a/src/control/control.c
+++ b/src/control/control.c
@@ -90,7 +90,9 @@ is available.
 
 Many algorithms can be defined to find ordered pair of #snd_ctl_elem_id_t.
 For one of the comparison algorithms according to the numid,
-snd_ctl_elem_id_compare_by_numid() is available.
+snd_ctl_elem_id_compare_by_numid() is available. For one of the comparison
+algorithms according to the tuple, snd_ctl_elem_id_compare_by_tuple_arithmetic()
+is available. They are useful for qsort(3).
 
 \section element_lists Element Lists
 
@@ -1893,6 +1895,47 @@ int snd_ctl_elem_id_compare_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
 	return compare_unsigned_integer(l->numid, r->numid);
 }
 
+/**
+ * \brief compare two arguments as ordered pair by one of algorithms according
+ *	  to iface, device, subdevice, name, index fields.
+ * \param l opaque pointer to element ID structure.
+ * \param r opaque pointer to another element ID structure.
+ * \retval positive if left is greater than right, negative if left is less
+ *	   than right, zero if they equal.
+ *
+ * The structure underlying #snd_ctl_elem_id_t is compound one. The comparison
+ * algorithm for it is not single and unique. The API implements one of
+ * algorithm to find order in a pair of control element IDs, according to the
+ * values of iface, device, subdevice, name, and index fields, by below logic:
+ *
+ *  - find order in iface field by this order; card, hwdep, mixer, pcm, rawmidi,
+ *    timer, and sequencer.
+ *  - find order in device field by arithmetic comparison of its value.
+ *  - find order in subdevice field by arithmetic comparison of its value.
+ *  - find order in name field by using unsigned characters, implemented in strcmp(3).
+ *  - find order in index field by arithmetic comparison of its value.
+ */
+int snd_ctl_elem_id_compare_by_tuple_arithmetic(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	int res;
+
+	assert(l && r);
+
+	res = l->iface - r->iface;
+	if (res != 0)
+		return res;
+	res = compare_unsigned_integer(l->device, r->device);
+	if (res != 0)
+		return res;
+	res = compare_unsigned_integer(l->subdevice, r->subdevice);
+	if (res != 0)
+		return res;
+	res = strcmp((const char *)l->name, (const char *)r->name);
+	if (res != 0)
+		return res;
+	return compare_unsigned_integer(l->index, r->index);
+}
+
 /**
  * \brief compare one #snd_ctl_elem_id_t to another
  * \param id1 pointer to first id
diff --git a/test/lsb/ctl-elem-id.c b/test/lsb/ctl-elem-id.c
index 670ec252..02eb24fc 100644
--- a/test/lsb/ctl-elem-id.c
+++ b/test/lsb/ctl-elem-id.c
@@ -135,6 +135,106 @@ static void comparison_by_numid_3(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
 	assert(snd_ctl_elem_id_compare_by_numid(l, r) < 0);
 }
 
+// Case 3.0. The left object with lesser entry in iface field than right object
+//	     should result in negative.
+static void comparison_by_tuple_arithmetic_0(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_CARD, 0, 1, "A", 2);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_HWDEP, 0, 1, "A", 2);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) < 0);
+}
+
+// Case 3.1. The left object with greater entry in iface field than right object
+//	     should result in positive.
+static void comparison_by_tuple_arithmetic_1(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_SEQUENCER, 3, 4, "B", 5);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_TIMER, 3, 4, "B", 5);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) > 0);
+}
+
+// Case 3.2. The left object with lesser value in device field than right object
+//	     should result in negative.
+static void comparison_by_tuple_arithmetic_2(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_CARD, 1, 7, "C", 8);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_CARD, 6, 7, "C", 8);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) < 0);
+}
+
+
+// Case 3.3. The left object with greater value in device field than right object
+//	     should result in positive.
+static void comparison_by_tuple_arithmetic_3(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_HWDEP, 9, 10, "D", 11);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_HWDEP, 1, 10, "D", 11);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) > 0);
+}
+
+// Case 3.3. The left object with lesser value in subdevice field than right object
+//	     should result in negative.
+static void comparison_by_tuple_arithmetic_4(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_MIXER, 12, 1, "E", 14);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_MIXER, 12, 13, "E", 14);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) < 0);
+}
+
+// Case 3.4. The left object with greater value in subdevice field than right object
+//	     should result in positive.
+static void comparison_by_tuple_arithmetic_5(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_PCM, 15, 16, "F", 17);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_PCM, 15, 1, "F", 17);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) > 0);
+}
+
+// Case 3.5. The left object with name beginning lesser character in name field
+//	     than right object should result in negative.
+static void comparison_by_tuple_arithmetic_6(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_RAWMIDI, 18, 19, "A", 20);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_RAWMIDI, 18, 19, "H", 20);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) < 0);
+}
+
+// Case 3.6. The left object with name beginning greater character in name field
+//	     than right object should result in positive.
+static void comparison_by_tuple_arithmetic_7(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_TIMER, 21, 22, "I", 23);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_TIMER, 21, 22, "A", 23);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) > 0);
+}
+
+// Case 3.7. The left object with lesser value in index field than right object
+//	     should result in negative.
+static void comparison_by_tuple_arithmetic_8(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_SEQUENCER, 24, 25, "J", 1);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_SEQUENCER, 24, 25, "J", 26);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) < 0);
+}
+
+// Case 3.8. The left object with greater value in index field than right object
+//	     should result in positive.
+static void comparison_by_tuple_arithmetic_9(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_CARD, 27, 28, "K", 29);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_CARD, 27, 28, "K", 1);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) > 0);
+}
+
+// Case 3.9. The left object with the same values in iface, device, subdevice,
+//	     name, and index fields as right object should result in zero.
+static void comparison_by_tuple_arithmetic_10(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r)
+{
+	set_elem_id_by_tuple(l, SND_CTL_ELEM_IFACE_HWDEP, 30, 31, "L", 32);
+	set_elem_id_by_tuple(r, SND_CTL_ELEM_IFACE_HWDEP, 30, 31, "L", 32);
+	assert(snd_ctl_elem_id_compare_by_tuple_arithmetic(l, r) == 0);
+}
+
 int main()
 {
 	void (*entries[])(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r) = {
@@ -150,6 +250,17 @@ int main()
 		comparison_by_numid_1,
 		comparison_by_numid_2,
 		comparison_by_numid_3,
+		comparison_by_tuple_arithmetic_0,
+		comparison_by_tuple_arithmetic_1,
+		comparison_by_tuple_arithmetic_2,
+		comparison_by_tuple_arithmetic_3,
+		comparison_by_tuple_arithmetic_4,
+		comparison_by_tuple_arithmetic_5,
+		comparison_by_tuple_arithmetic_6,
+		comparison_by_tuple_arithmetic_7,
+		comparison_by_tuple_arithmetic_8,
+		comparison_by_tuple_arithmetic_9,
+		comparison_by_tuple_arithmetic_10,
 	};
 	int count = sizeof(entries) / sizeof(*entries);
 	int fd;
-- 
2.27.0

[alsa-lib][PATCH 6/6] ctl: drop deprecated API to compare a pair of control element IDs

[Takashi Sakamoto]

A commit 2cfe6addaef6 ("control: add snd_ctl_elem_id_compare()
function") adds 'snd_ctl_elem_id_compare()' API, however the
implementation has several bugs.

At first, the name is not inappropriate since it implements one of
comparison algorithms. The name itself implies the algorithm is single
and unique for control element ID.

Secondary, it subtracts a pair of values in fields of 'unsigned int' type
in storage size of the type. It brings integer overflow.

Tertiary, it compares subdevice field in the same structure.

Fortunately, the issued API is not public in any release. An alternative
API, 'snd_ctl_elem_id_compare_by_name_arithmetic()', is already added with
enough tests. This commit drops the issued API.

Signed-off-by: Takashi Sakamoto <o-takashi@sakamocchi.jp>
---
 include/control.h     |  1 -
 src/control/control.c | 35 -----------------------------------
 2 files changed, 36 deletions(-)

diff --git a/include/control.h b/include/control.h
index 1b2cc0c6..3975f4b7 100644
--- a/include/control.h
+++ b/include/control.h
@@ -428,7 +428,6 @@ int snd_ctl_elem_id_equal_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_equal_by_tuple(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_compare_by_numid(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
 int snd_ctl_elem_id_compare_by_tuple_arithmetic(snd_ctl_elem_id_t *l, snd_ctl_elem_id_t *r);
-int snd_ctl_elem_id_compare(snd_ctl_elem_id_t *id1, const snd_ctl_elem_id_t *id2);
 unsigned int snd_ctl_elem_id_get_numid(const snd_ctl_elem_id_t *obj);
 snd_ctl_elem_iface_t snd_ctl_elem_id_get_interface(const snd_ctl_elem_id_t *obj);
 unsigned int snd_ctl_elem_id_get_device(const snd_ctl_elem_id_t *obj);
diff --git a/src/control/control.c b/src/control/control.c
index fbc6aeb7..1d83cb6a 100644
--- a/src/control/control.c
+++ b/src/control/control.c
@@ -1936,41 +1936,6 @@ int snd_ctl_elem_id_compare_by_tuple_arithmetic(snd_ctl_elem_id_t *l, snd_ctl_el
 	return compare_unsigned_integer(l->index, r->index);
 }
 
-/**
- * \brief compare one #snd_ctl_elem_id_t to another
- * \param id1 pointer to first id
- * \param id2 pointer to second id
- * \retval zero when values are identical, other value on a difference (like strcmp)
- *
- * This comparison ignores the numid part. The numid comparison can be easily
- * implemented using snd_ctl_elem_id_get_numid() calls.
- *
- * The identifier fields are compared in this order: interface, device,
- * subdevice, name, index.
- *
- * The return value can be used for sorting like qsort(). It gives persistent
- * results.
- */
-int snd_ctl_elem_id_compare(snd_ctl_elem_id_t *id1, const snd_ctl_elem_id_t *id2)
-{
-	int d;
-
-	assert(id1 && id2);
-	d = id1->iface - id2->iface;
-	if (d != 0)
-		return d;
-	d = id1->device - id2->device;
-	if (d != 0)
-		return d;
-	d = id2->subdevice - id2->subdevice;
-	if (d != 0)
-		return d;
-	d = strcmp((const char *)id1->name, (const char *)id2->name);
-	if (d != 0)
-		return d;
-	return id1->index - id2->index;
-}
-
 /**
  * \brief Get numeric identifier from a CTL element identifier
  * \param obj CTL element identifier
-- 
2.27.0

Re: [alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Jaroslav Kysela]

Dne 18. 03. 21 v 11:30 Takashi Sakamoto napsal(a):
> Hi,
> 
> This patchset is a fix for bug issued in the message thread[1].
> 
> In this development period, alsa-lib got new API as implementation for
> one of comparison algorithms to a pair of control element IDs. However,
> it has several issues.
> 
> At first, the name, 'snd_ctl_elem_id_compare()', is inappropriate since it
> implements one of comparison algorithms. The name itself implies the
> algorithm is single and unique for control element ID. However, the
> target structure, 'struct snd_ctl_elem_id', is hybrid and compound one.
> We can not find such single and unique comparison algorithm for it.
> 
> Secondary, it subtracts a pair of values in fields of 'unsigned int' type
> in storage size of the type. It brings integer overflow.

I don't think that this extra handling is really required. The unsigned /
signed conversions are well known and the overflow results with a negative
signed value. Why add more branches to the instruction chain?

> Tertiary, it has simple bug to compare subdevice field in the same structure.

Good catch.

> Essentially, equality is different from comparison. In a point of programming,

Yes, but in this case, there's no benefit to have things separated. Add inline
functions if you like to create application helpers which may be replaced by
the functions in the future. If we really need a super CPU optimized equality
check functions, we can add them later. The full compare functions must return
zero, if the values are equal.

I prefer minimal API changes here.

> implementation for comparison algorithm can have more overhead than
> implementation for equality. In this meaning, it's better to add different API
> for them.
> 
> This patchset adds new API below:
> 
>  * for equality
>    * snd_ctl_elem_id_equal_by_numid()
>    * snd_ctl_elem_id_equal_by_tuple()
>  * for each comparison algorithm
>    * snd_ctl_elem_id_compare_by_numid()
>    * snd_ctl_elem_id_compare_by_tuple_arithmetic()
>
> I've got bothered to decide the name of API for the case to use tuples.
> Here I use the word, 'tuple', which comes from documentation of alsa-lib[2].

The tuple naming is a bit new and I would prefer fields or so here. The ID is
represented by the number or group of fields. Also arithmetic suffix makes the
function name longer. The new function may use other name (if any will be
implemented later).

Also, I don't like l and r argument naming. We should follow strcmp() and
don't try to invent something new here.

Also my old function should be just renamed. No add + remove is necessary for
the modifications of the touched code.

Resume:

1) rename snd_ctl_elem_id_compare() to snd_ctl_elem_id_compare_fields()
2) add snd_ctl_elem_id_compare_by_numid()

.. optionally ...

3) add snd_ctl_elem_id_equal_by_numid() - as inline using compare fcn
4) add snd_ctl_elem_id_equal_by_fields() - also inline

					Jaroslav

-- 
Jaroslav Kysela <perex@perex.cz>
Linux Sound Maintainer; ALSA Project; Red Hat, Inc.

Re: [alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Takashi Sakamoto]

On Thu, Mar 18, 2021 at 12:42:30PM +0100, Jaroslav Kysela wrote:
> Dne 18. 03. 21 v 11:30 Takashi Sakamoto napsal(a):
> > Hi,
> > 
> > This patchset is a fix for bug issued in the message thread[1].
> > 
> > In this development period, alsa-lib got new API as implementation for
> > one of comparison algorithms to a pair of control element IDs. However,
> > it has several issues.
> > 
> > At first, the name, 'snd_ctl_elem_id_compare()', is inappropriate since it
> > implements one of comparison algorithms. The name itself implies the
> > algorithm is single and unique for control element ID. However, the
> > target structure, 'struct snd_ctl_elem_id', is hybrid and compound one.
> > We can not find such single and unique comparison algorithm for it.
> > 
> > Secondary, it subtracts a pair of values in fields of 'unsigned int' type
> > in storage size of the type. It brings integer overflow.
> 
> I don't think that this extra handling is really required. The unsigned /
> signed conversions are well known and the overflow results with a negative
> signed value. Why add more branches to the instruction chain?
 
For this kind of question, it's preferable to write actual test:

```
int main()
{
  snd_ctl_elem_id_t *l, *r;

  snd_ctl_elem_id_alloca(&l);
  snd_ctl_elem_id_alloca(&r);

  snd_ctl_elem_id_set_device(l, 0);
  snd_ctl_elem_id_set_device(r, UINT_MAX);

  assert(snd_ctl_elem_id_compare(l, r) < 0);

  return 0;
}
```

The assertion hits. For conversion detail:

```
$ cat test1.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main()
{
	unsigned int a, b;
	int diff;

	a = 0;
	b = 10;
	diff = a - b;
	printf("%08x\n", diff);

	a = 0;
	b = UINT_MAX;
	diff = a - b;
	printf("%08x\n", diff);

	return EXIT_SUCCESS;
}
```

The above test results in 0x00000001 for -UINT_MAX case under x386/x86_64,
like:

```
$ gcc -m32 -o ./test1 ./test1.c ; ./test1
fffffff6
00000001
$ gcc -m64 -o ./test1 ./test1.c ; ./test1
fffffff6
00000001
```

We can see integer overflow in both machine architectures due to
calculation under 32 bit storage.

Well, let us prepare 64 bit storage for both of minuend and subtrahend
to get negative value in 64 bit storage. In the case, narrower conversion
to 32 bit integer is unavoidable since it's assigned to integer value
returned from the function in your implementation. In the case, converted
value is _not_ negative according to assignment rule in C language
specification.

```
$ cat test2.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main()
{
	unsigned int a, b;
	long long diff;
	int ret;

	a = 0;
	b = UINT_MAX;

	// Calculate under 64 bit storage, then assign to 64 bit storage.
	diff = (long long)a - (long long)b;
	printf("%016llx\n", diff);

	// Narrower conversion occurs now.
	ret = (int)diff;
	printf("%08x\n", ret);

	return EXIT_SUCCESS;
}
$ gcc -m32 -o ./test2 ./test2.c ; ./test2
ffffffff00000001
00000001
$ gcc -m64 -o ./test2 ./test2.c ; ./test2
ffffffff00000001
00000001
```

We can see easy example in the clause of 'Assignment operators' in the
specification. This is the reason to use condition branches in the patchset.

> > Tertiary, it has simple bug to compare subdevice field in the same structure.
> 
> Good catch.
> 
> > Essentially, equality is different from comparison. In a point of programming,
> 
> Yes, but in this case, there's no benefit to have things separated. Add inline
> functions if you like to create application helpers which may be replaced by
> the functions in the future. If we really need a super CPU optimized equality
> check functions, we can add them later. The full compare functions must return
> zero, if the values are equal.
> 
> I prefer minimal API changes here.

Any comparison algorithm for the structure needs 64 bit storage and narrowing
conversion to 32 bit integer for return value in the case to use no condition
branches. Apparently, equality check and comparison has different overhead in
their implementations. We need two set of functions for them in both points of
semantics and optimization.

Our ancestor has already considered for the issue similar to the above,
then make theory to distinguish comparison from equality check. It's
better behaviour to respect the theory against own implementation.

> > implementation for comparison algorithm can have more overhead than
> > implementation for equality. In this meaning, it's better to add different API
> > for them.
> > 
> > This patchset adds new API below:
> > 
> >  * for equality
> >    * snd_ctl_elem_id_equal_by_numid()
> >    * snd_ctl_elem_id_equal_by_tuple()
> >  * for each comparison algorithm
> >    * snd_ctl_elem_id_compare_by_numid()
> >    * snd_ctl_elem_id_compare_by_tuple_arithmetic()
> >
> > I've got bothered to decide the name of API for the case to use tuples.
> > Here I use the word, 'tuple', which comes from documentation of alsa-lib[2].
> 
> The tuple naming is a bit new and I would prefer fields or so here. The ID is
> represented by the number or group of fields. Also arithmetic suffix makes the
> function name longer. The new function may use other name (if any will be
> implemented later).
> 
> Also, I don't like l and r argument naming. We should follow strcmp() and
> don't try to invent something new here.
> 
> Also my old function should be just renamed. No add + remove is necessary for
> the modifications of the touched code.
> 
> Resume:
> 
> 1) rename snd_ctl_elem_id_compare() to snd_ctl_elem_id_compare_fields()
> 2) add snd_ctl_elem_id_compare_by_numid()
> 
> .. optionally ...
> 
> 3) add snd_ctl_elem_id_equal_by_numid() - as inline using compare fcn
> 4) add snd_ctl_elem_id_equal_by_fields() - also inline

As I described, your old implementation is not acceptable just by renaming.
Although the idea of inline definitions is itself preferable. I suspect whether
inline definition for your comparison algorithm is really less overhead than
function call.

Anyway I'll post revised version of patchset later.


Thanks

Takashi Sakamoto

Re: [alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Takashi Sakamoto]

On Fri, Mar 19, 2021 at 01:37:15AM +0900, Takashi Sakamoto wrote:
> As I described, your old implementation is not acceptable just by renaming.
> Although the idea of inline definitions is itself preferable. I suspect whether
> inline definition for your comparison algorithm is really less overhead than
> function call.
> 
> Anyway I'll post revised version of patchset later.

Oops. These APIs have arguments with opaque pointers. In the case,
inline definition is not available since the layout of structure underlying
the pointer is not available for userspace applications. Thus the rest of
issue is whether to use 'tuple' or 'fields' in the name of new API.

In my opinion, 'fields' is generic expression and could give impression to
application developers that it includes numid field as well. On the other
hand, 'tuple' is weak expression somehow and the developers easily find
its meaning in alsa-lib documentation (see line 80). When considering about
helpfulness to developers, 'tuple' seems to be better than 'fields'.


Thanks

Takashi Sakamoto

Re: [alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Jaroslav Kysela]

Dne 18. 03. 21 v 17:37 Takashi Sakamoto napsal(a):
> On Thu, Mar 18, 2021 at 12:42:30PM +0100, Jaroslav Kysela wrote:
>> Dne 18. 03. 21 v 11:30 Takashi Sakamoto napsal(a):
>>> Hi,
>>>
>>> This patchset is a fix for bug issued in the message thread[1].
>>>
>>> In this development period, alsa-lib got new API as implementation for
>>> one of comparison algorithms to a pair of control element IDs. However,
>>> it has several issues.
>>>
>>> At first, the name, 'snd_ctl_elem_id_compare()', is inappropriate since it
>>> implements one of comparison algorithms. The name itself implies the
>>> algorithm is single and unique for control element ID. However, the
>>> target structure, 'struct snd_ctl_elem_id', is hybrid and compound one.
>>> We can not find such single and unique comparison algorithm for it.
>>>
>>> Secondary, it subtracts a pair of values in fields of 'unsigned int' type
>>> in storage size of the type. It brings integer overflow.
>>
>> I don't think that this extra handling is really required. The unsigned /
>> signed conversions are well known and the overflow results with a negative
>> signed value. Why add more branches to the instruction chain?
>  
> For this kind of question, it's preferable to write actual test:
> 
> ```
> int main()
> {
>   snd_ctl_elem_id_t *l, *r;
> 
>   snd_ctl_elem_id_alloca(&l);
>   snd_ctl_elem_id_alloca(&r);
> 
>   snd_ctl_elem_id_set_device(l, 0);
>   snd_ctl_elem_id_set_device(r, UINT_MAX);
> 
>   assert(snd_ctl_elem_id_compare(l, r) < 0);
> 
>   return 0;
> }
> ```
> 
> The assertion hits. For conversion detail:
> 
> ```
> $ cat test1.c
> #include <stdio.h>
> #include <stdlib.h>
> #include <limits.h>
> 
> int main()
> {
> 	unsigned int a, b;
> 	int diff;
> 
> 	a = 0;
> 	b = 10;
> 	diff = a - b;
> 	printf("%08x\n", diff);
> 
> 	a = 0;
> 	b = UINT_MAX;
> 	diff = a - b;
> 	printf("%08x\n", diff);
> 
> 	return EXIT_SUCCESS;
> }
> ```
> 
> The above test results in 0x00000001 for -UINT_MAX case under x386/x86_64,
> like:
> 
> ```
> $ gcc -m32 -o ./test1 ./test1.c ; ./test1
> fffffff6
> 00000001
> $ gcc -m64 -o ./test1 ./test1.c ; ./test1
> fffffff6
> 00000001
> ```
> 
> We can see integer overflow in both machine architectures due to
> calculation under 32 bit storage.
> 
> Well, let us prepare 64 bit storage for both of minuend and subtrahend
> to get negative value in 64 bit storage. In the case, narrower conversion
> to 32 bit integer is unavoidable since it's assigned to integer value
> returned from the function in your implementation. In the case, converted
> value is _not_ negative according to assignment rule in C language
> specification.
> 
> ```
> $ cat test2.c
> #include <stdio.h>
> #include <stdlib.h>
> #include <limits.h>
> 
> int main()
> {
> 	unsigned int a, b;
> 	long long diff;
> 	int ret;
> 
> 	a = 0;
> 	b = UINT_MAX;
> 
> 	// Calculate under 64 bit storage, then assign to 64 bit storage.
> 	diff = (long long)a - (long long)b;
> 	printf("%016llx\n", diff);
> 
> 	// Narrower conversion occurs now.
> 	ret = (int)diff;
> 	printf("%08x\n", ret);
> 
> 	return EXIT_SUCCESS;
> }
> $ gcc -m32 -o ./test2 ./test2.c ; ./test2
> ffffffff00000001
> 00000001
> $ gcc -m64 -o ./test2 ./test2.c ; ./test2
> ffffffff00000001
> 00000001
> ```
> 
> We can see easy example in the clause of 'Assignment operators' in the
> specification. This is the reason to use condition branches in the patchset.

The point is that none of the compared unsigned fields is really above the
31-bit range, so you're trying to resolve an academical problem instead to add
the debug checks (asserts) if the input values are in the acceptable range.
Only the numid functions require this.

					Jaroslav

-- 
Jaroslav Kysela <perex@perex.cz>
Linux Sound Maintainer; ALSA Project; Red Hat, Inc.

Re: [alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Jaroslav Kysela]

Dne 18. 03. 21 v 17:56 Takashi Sakamoto napsal(a):
> On Fri, Mar 19, 2021 at 01:37:15AM +0900, Takashi Sakamoto wrote:
>> As I described, your old implementation is not acceptable just by renaming.
>> Although the idea of inline definitions is itself preferable. I suspect whether
>> inline definition for your comparison algorithm is really less overhead than
>> function call.
>>
>> Anyway I'll post revised version of patchset later.
> 
> Oops. These APIs have arguments with opaque pointers. In the case,
> inline definition is not available since the layout of structure underlying
> the pointer is not available for userspace applications. Thus the rest of
> issue is whether to use 'tuple' or 'fields' in the name of new API.
> 
> In my opinion, 'fields' is generic expression and could give impression to
> application developers that it includes numid field as well. On the other
> hand, 'tuple' is weak expression somehow and the developers easily find
> its meaning in alsa-lib documentation (see line 80). When considering about
> helpfulness to developers, 'tuple' seems to be better than 'fields'.

With this logic, we can just create snd_ctl_id_compare1, snd_ctl_id_compare2
functions to force developers to go to the docs.

Perhaps, snd_ctl_id_compare_full() may be better. Tuple is a generic set of
fields, so there's no change. Again, I don't expect to add other comparison
functions soon.

					Jaroslav

-- 
Jaroslav Kysela <perex@perex.cz>
Linux Sound Maintainer; ALSA Project; Red Hat, Inc.

Re: [alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Takashi Sakamoto]

Hi Jaroslav,

Sorry to be my late reply but I have some private troubles (to search my
domestic cat back to the street several days ago.).

On Thu, Mar 18, 2021 at 06:04:36PM +0100, Jaroslav Kysela wrote:
> Dne 18. 03. 21 v 17:37 Takashi Sakamoto napsal(a):
> > On Thu, Mar 18, 2021 at 12:42:30PM +0100, Jaroslav Kysela wrote:
> >> Dne 18. 03. 21 v 11:30 Takashi Sakamoto napsal(a):
> >>> Hi,
> >>>
> >>> This patchset is a fix for bug issued in the message thread[1].
> >>>
> >>> In this development period, alsa-lib got new API as implementation for
> >>> one of comparison algorithms to a pair of control element IDs. However,
> >>> it has several issues.
> >>>
> >>> At first, the name, 'snd_ctl_elem_id_compare()', is inappropriate since it
> >>> implements one of comparison algorithms. The name itself implies the
> >>> algorithm is single and unique for control element ID. However, the
> >>> target structure, 'struct snd_ctl_elem_id', is hybrid and compound one.
> >>> We can not find such single and unique comparison algorithm for it.
> >>>
> >>> Secondary, it subtracts a pair of values in fields of 'unsigned int' type
> >>> in storage size of the type. It brings integer overflow.
> >>
> >> I don't think that this extra handling is really required. The unsigned /
> >> signed conversions are well known and the overflow results with a negative
> >> signed value. Why add more branches to the instruction chain?
> >  
> > For this kind of question, it's preferable to write actual test:
> > 
> > ```
> > int main()
> > {
> >   snd_ctl_elem_id_t *l, *r;
> > 
> >   snd_ctl_elem_id_alloca(&l);
> >   snd_ctl_elem_id_alloca(&r);
> > 
> >   snd_ctl_elem_id_set_device(l, 0);
> >   snd_ctl_elem_id_set_device(r, UINT_MAX);
> > 
> >   assert(snd_ctl_elem_id_compare(l, r) < 0);
> > 
> >   return 0;
> > }
> > ```
> > 
> > The assertion hits. For conversion detail:
> > 
> > ```
> > $ cat test1.c
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <limits.h>
> > 
> > int main()
> > {
> > 	unsigned int a, b;
> > 	int diff;
> > 
> > 	a = 0;
> > 	b = 10;
> > 	diff = a - b;
> > 	printf("%08x\n", diff);
> > 
> > 	a = 0;
> > 	b = UINT_MAX;
> > 	diff = a - b;
> > 	printf("%08x\n", diff);
> > 
> > 	return EXIT_SUCCESS;
> > }
> > ```
> > 
> > The above test results in 0x00000001 for -UINT_MAX case under x386/x86_64,
> > like:
> > 
> > ```
> > $ gcc -m32 -o ./test1 ./test1.c ; ./test1
> > fffffff6
> > 00000001
> > $ gcc -m64 -o ./test1 ./test1.c ; ./test1
> > fffffff6
> > 00000001
> > ```
> > 
> > We can see integer overflow in both machine architectures due to
> > calculation under 32 bit storage.
> > 
> > Well, let us prepare 64 bit storage for both of minuend and subtrahend
> > to get negative value in 64 bit storage. In the case, narrower conversion
> > to 32 bit integer is unavoidable since it's assigned to integer value
> > returned from the function in your implementation. In the case, converted
> > value is _not_ negative according to assignment rule in C language
> > specification.
> > 
> > ```
> > $ cat test2.c
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <limits.h>
> > 
> > int main()
> > {
> > 	unsigned int a, b;
> > 	long long diff;
> > 	int ret;
> > 
> > 	a = 0;
> > 	b = UINT_MAX;
> > 
> > 	// Calculate under 64 bit storage, then assign to 64 bit storage.
> > 	diff = (long long)a - (long long)b;
> > 	printf("%016llx\n", diff);
> > 
> > 	// Narrower conversion occurs now.
> > 	ret = (int)diff;
> > 	printf("%08x\n", ret);
> > 
> > 	return EXIT_SUCCESS;
> > }
> > $ gcc -m32 -o ./test2 ./test2.c ; ./test2
> > ffffffff00000001
> > 00000001
> > $ gcc -m64 -o ./test2 ./test2.c ; ./test2
> > ffffffff00000001
> > 00000001
> > ```
> > 
> > We can see easy example in the clause of 'Assignment operators' in the
> > specification. This is the reason to use condition branches in the patchset.
> 
> The point is that none of the compared unsigned fields is really above the
> 31-bit range, so you're trying to resolve an academical problem instead to add
> the debug checks (asserts) if the input values are in the acceptable range.
> Only the numid functions require this.

Hm. I think you have the assumption to 'device' and 'subdevice' fields.

If the value of these fields directly derived from any fields
systematically which Linux kernel or middleware of ALSA kernel stuffs
maintains with 'int' type, it would be valid. However, the decision to
assign specific value to these fields is left to driver developer, by
declaring 'struct snd_kcontrol_new'[1] in driver code. We wouldn't see such
code that the developer construct 'pseudo' device and subdevice to deliver
specific information to userspace, it could be.

(once I've investigated to use this design to ALSA firewire stack.)

Additionally, alsa-lib has plug-in framework to have several backend which
works beyond the most of API calls[2]. The 'hw' plugin is one of them,
which directly communicate to ALSA control core via system calls.
Developers and users have some opportunities to implement and use the
other backend, then they are free from your assumption. In this point,
any assumption to 'index' field is not better as well.

Of course, you can insist the above topics are not practical, something
belongs to domains of academical or logical. However, I put safety in the
first place, to avoid bugs which expectedly appears in future. I'd like
you to take enough care of downstream user's demands.

Well, if code revising is not acceptable to you, it's better to add
any assertion to check range of value as you mentioned as well as good
documentation. In this case, your function is not generic one and should
be renamed that it works conditionally. 'snd_ctl_elem_id_compare()' is not
acceptable.


[1] include/sound/control.h
https://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound.git/tree/include/sound/control.h?h=for-next#n41
[2] External Control Plugin SDK
https://www.alsa-project.org/alsa-doc/alsa-lib/ctl_external_plugins.html


Regards

Takashi Sakamoto

Re: [alsa-lib][PATCH 0/6] add API of equality and comparison for a pair of control element IDs

[Takashi Sakamoto]

Hi Jaroslav,

On Thu, Mar 18, 2021 at 06:17:54PM +0100, Jaroslav Kysela wrote:
> Dne 18. 03. 21 v 17:56 Takashi Sakamoto napsal(a):
> > On Fri, Mar 19, 2021 at 01:37:15AM +0900, Takashi Sakamoto wrote:
> >> As I described, your old implementation is not acceptable just by renaming.
> >> Although the idea of inline definitions is itself preferable. I suspect whether
> >> inline definition for your comparison algorithm is really less overhead than
> >> function call.
> >>
> >> Anyway I'll post revised version of patchset later.
> > 
> > Oops. These APIs have arguments with opaque pointers. In the case,
> > inline definition is not available since the layout of structure underlying
> > the pointer is not available for userspace applications. Thus the rest of
> > issue is whether to use 'tuple' or 'fields' in the name of new API.
> > 
> > In my opinion, 'fields' is generic expression and could give impression to
> > application developers that it includes numid field as well. On the other
> > hand, 'tuple' is weak expression somehow and the developers easily find
> > its meaning in alsa-lib documentation (see line 80). When considering about
> > helpfulness to developers, 'tuple' seems to be better than 'fields'.
> 
> With this logic, we can just create snd_ctl_id_compare1, snd_ctl_id_compare2
> functions to force developers to go to the docs.

It's not better since it's against common convention for name of
exposed API. When you work for internal helper function which is not
exposed, it's acceptable. At least, I have never seen such functions
in alsa-lib.

> Perhaps, snd_ctl_id_compare_full() may be better. Tuple is a generic set of
> fields, so there's no change.

As I described, the usage of 'tuple' in the context is in documentation.
In this case, it's not so bad idea and acceptable I think. At least,
it's better than the word 'full' since your comparison algorithm is not
based on full fields by ignoring numid field.

> Again, I don't expect to add other comparison functions soon.

I'd like you to explain about your rejection to add comparison function
according to numid as well as your view of the comparison algorithm as
being exclusive, single, unique than the others when we have many
comparison algorithms for fields of the tuple.


Regards

Takashi Sakamoto