[v12,03/31] Add string vectorized find and detection functions
Checks
| Context |
Check |
Description |
| dj/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
Commit Message
This patch adds generic string find and detection meant to be used in
generic vectorized string implementation. The idea is to decompose the
basic string operation so each architecture can reimplement if it
provides any specialized hardware instruction.
The 'string-misc.h' provides miscellaneous functions:
- extractbyte: extracts the byte from an specific index.
- repeat_bytes: setup an word by replicate the argument on each byte.
The 'string-fza.h' provides zero byte detection functions:
- find_zero_low, find_zero_all, find_eq_low, find_eq_all,
find_zero_eq_low, find_zero_eq_all, find_zero_ne_low,
and find_zero_ne_all
The 'string-fzb.h' provides boolean zero byte detection functions:
- has_zero: determine if any byte within a word is zero.
- has_eq: determine byte equality between two words.
- has_zero_eq: determine if any byte within a word is zero along with
byte equality between two words.
The 'string-fzi.h' provides positions for string-fza.h results:
- index_first: return index of first zero byte within a word.
- index_last: return index of first byte different between two words.
The 'string-fzc.h' provides a combined version of fza and fzi:
- index_first_zero_eq: return index of first zero byte within a word or
first byte different between two words.
- index_first_zero_ne: return index of first zero byte within a word or
first byte equal between two words.
- index_last_zero: return index of last zero byte within a word.
- index_last_eq: return index of last byte different between two words.
The 'string-shift.h' provides a way to mask off parts of a work based on
some alignmnet (to handle unaligned arguments):
- shift_find, shift_find_last.
Co-authored-by: Richard Henderson <richard.henderson@linaro.org>
---
sysdeps/generic/string-fza.h | 104 +++++++++++++++++++++++++++++++++
sysdeps/generic/string-fzb.h | 49 ++++++++++++++++
sysdeps/generic/string-fzc.h | 83 ++++++++++++++++++++++++++
sysdeps/generic/string-fzi.h | 71 ++++++++++++++++++++++
sysdeps/generic/string-misc.h | 45 ++++++++++++++
sysdeps/generic/string-shift.h | 52 +++++++++++++++++
6 files changed, 404 insertions(+)
create mode 100644 sysdeps/generic/string-fza.h
create mode 100644 sysdeps/generic/string-fzb.h
create mode 100644 sysdeps/generic/string-fzc.h
create mode 100644 sysdeps/generic/string-fzi.h
create mode 100644 sysdeps/generic/string-misc.h
create mode 100644 sysdeps/generic/string-shift.h
Comments
On 2/2/23 08:11, Adhemerval Zanella wrote:
> +/* With similar caveats, identify zero bytes in X1 and bytes that are
> + not equal between in X1 and X2. */
> +static __always_inline find_t
> +find_zero_ne_low (op_t x1, op_t x2)
> +{
> + return (~find_zero_eq_low (x1, x2)) + 1;
> +}
This is no longer used, and suspected buggy. Duh, I now see why it's buggy -- it's
inverting both zero comparison and eq comparison -- we wanted to invert only eq.
Let's remove this rather than attempting to fix. I suspect it'll work out very similar to
our existing find_zero_ne_all().
> +/* Similarly, but perform the search for byte equality between X1 and X2. */
> +static __always_inline unsigned int
> +index_first_zero (op_t x1, op_t x2)
> +{
> + if (__BYTE_ORDER == __LITTLE_ENDIAN)
> + x1 = find_zero_low (x1, x2);
> + else
> + x1 = find_zero_all (x1, x2);
> + return index_first (x1);
> +}
...
> +/* Similarly, but search for the last zero within X. */
> +static __always_inline unsigned int
> +index_last_zero (op_t x)
> +{
> + return index_last (find_zero_all (x));
> +}
Why did this lose the __BYTE_ORDER test? It should be the inverse of index_first_zero.
> +static __always_inline unsigned int
> +index_last_eq (op_t x1, op_t x2)
> +{
> + return index_last_zero (x1 ^ x2);
> +}
Similarly.
r~
On 02/02/23 21:24, Richard Henderson wrote:
> On 2/2/23 08:11, Adhemerval Zanella wrote:
>> +/* With similar caveats, identify zero bytes in X1 and bytes that are
>> + not equal between in X1 and X2. */
>> +static __always_inline find_t
>> +find_zero_ne_low (op_t x1, op_t x2)
>> +{
>> + return (~find_zero_eq_low (x1, x2)) + 1;
>> +}
>
> This is no longer used, and suspected buggy. Duh, I now see why it's buggy -- it's inverting both zero comparison and eq comparison -- we wanted to invert only eq.
>
> Let's remove this rather than attempting to fix. I suspect it'll work out very similar to our existing find_zero_ne_all().
Ack, we haven't see any issue because it not really use anywhere.
>
>
>> +/* Similarly, but perform the search for byte equality between X1 and X2. */
>> +static __always_inline unsigned int
>> +index_first_zero (op_t x1, op_t x2)
>> +{
>> + if (__BYTE_ORDER == __LITTLE_ENDIAN)
>> + x1 = find_zero_low (x1, x2);
>> + else
>> + x1 = find_zero_all (x1, x2);
>> + return index_first (x1);
>> +}
> ...
>> +/* Similarly, but search for the last zero within X. */
>> +static __always_inline unsigned int
>> +index_last_zero (op_t x)
>> +{
>> + return index_last (find_zero_all (x));
>> +}
>
> Why did this lose the __BYTE_ORDER test? It should be the inverse of index_first_zero.
I think because find_zero_all works for both LE and BE. But we can optimize it
slight for BE:
static __always_inline unsigned int
index_last_zero (op_t x)
{
if (__BYTE_ORDER == __LITTLE_ENDIAN)
x = find_zero_all (x);
else
x = find_zero_low (x);
return index_last (x);
}
>
>
>> +static __always_inline unsigned int
>> +index_last_eq (op_t x1, op_t x2)
>> +{
>> + return index_last_zero (x1 ^ x2);
>> +}
I think it should not be required with index_last_zero using __BYTE_ORDER
test as above.
On 03/02/23 09:39, Adhemerval Zanella Netto wrote:
>
>
> On 02/02/23 21:24, Richard Henderson wrote:
>> On 2/2/23 08:11, Adhemerval Zanella wrote:
>>> +/* With similar caveats, identify zero bytes in X1 and bytes that are
>>> + not equal between in X1 and X2. */
>>> +static __always_inline find_t
>>> +find_zero_ne_low (op_t x1, op_t x2)
>>> +{
>>> + return (~find_zero_eq_low (x1, x2)) + 1;
>>> +}
>>
>> This is no longer used, and suspected buggy. Duh, I now see why it's buggy -- it's inverting both zero comparison and eq comparison -- we wanted to invert only eq.
>>
>> Let's remove this rather than attempting to fix. I suspect it'll work out very similar to our existing find_zero_ne_all().
>
> Ack, we haven't see any issue because it not really use anywhere.
>
>>
>>
>>> +/* Similarly, but perform the search for byte equality between X1 and X2. */
>>> +static __always_inline unsigned int
>>> +index_first_zero (op_t x1, op_t x2)
>>> +{
>>> + if (__BYTE_ORDER == __LITTLE_ENDIAN)
>>> + x1 = find_zero_low (x1, x2);
>>> + else
>>> + x1 = find_zero_all (x1, x2);
>>> + return index_first (x1);
>>> +}
>> ...
>>> +/* Similarly, but search for the last zero within X. */
>>> +static __always_inline unsigned int
>>> +index_last_zero (op_t x)
>>> +{
>>> + return index_last (find_zero_all (x));
>>> +}
>>
>> Why did this lose the __BYTE_ORDER test? It should be the inverse of index_first_zero.
>
> I think because find_zero_all works for both LE and BE. But we can optimize it
> slight for BE:
>
> static __always_inline unsigned int
> index_last_zero (op_t x)
> {
> if (__BYTE_ORDER == __LITTLE_ENDIAN)
> x = find_zero_all (x);
> else
> x = find_zero_low (x);
> return index_last (x);
> }
>
>
>>
>>
>>> +static __always_inline unsigned int
>>> +index_last_eq (op_t x1, op_t x2)
>>> +{
>>> + return index_last_zero (x1 ^ x2);
>>> +}
>
> I think it should not be required with index_last_zero using __BYTE_ORDER
> test as above.
I will send only this patch to avoid resend all the thread that is already
reviewed.
---
[PATCH 03/31] Add string vectorized find and detection functions
This patch adds generic string find and detection meant to be used in
generic vectorized string implementation. The idea is to decompose the
basic string operation so each architecture can reimplement if it
provides any specialized hardware instruction.
The 'string-misc.h' provides miscellaneous functions:
- extractbyte: extracts the byte from an specific index.
- repeat_bytes: setup an word by replicate the argument on each byte.
The 'string-fza.h' provides zero byte detection functions:
- find_zero_low, find_zero_all, find_eq_low, find_eq_all,
find_zero_eq_low, find_zero_eq_all, and find_zero_ne_all
The 'string-fzb.h' provides boolean zero byte detection functions:
- has_zero: determine if any byte within a word is zero.
- has_eq: determine byte equality between two words.
- has_zero_eq: determine if any byte within a word is zero along with
byte equality between two words.
The 'string-fzi.h' provides positions for string-fza.h results:
- index_first: return index of first zero byte within a word.
- index_last: return index of first byte different between two words.
The 'string-fzc.h' provides a combined version of fza and fzi:
- index_first_zero_eq: return index of first zero byte within a word or
first byte different between two words.
- index_first_zero_ne: return index of first zero byte within a word or
first byte equal between two words.
- index_last_zero: return index of last zero byte within a word.
- index_last_eq: return index of last byte different between two words.
The 'string-shift.h' provides a way to mask off parts of a work based on
some alignmnet (to handle unaligned arguments):
- shift_find, shift_find_last.
Co-authored-by: Richard Henderson <richard.henderson@linaro.org>
---
sysdeps/generic/string-fza.h | 98 ++++++++++++++++++++++++++++++++++
sysdeps/generic/string-fzb.h | 49 +++++++++++++++++
sysdeps/generic/string-fzc.h | 87 ++++++++++++++++++++++++++++++
sysdeps/generic/string-fzi.h | 71 ++++++++++++++++++++++++
sysdeps/generic/string-misc.h | 45 ++++++++++++++++
sysdeps/generic/string-shift.h | 52 ++++++++++++++++++
6 files changed, 402 insertions(+)
create mode 100644 sysdeps/generic/string-fza.h
create mode 100644 sysdeps/generic/string-fzb.h
create mode 100644 sysdeps/generic/string-fzc.h
create mode 100644 sysdeps/generic/string-fzi.h
create mode 100644 sysdeps/generic/string-misc.h
create mode 100644 sysdeps/generic/string-shift.h
diff --git a/sysdeps/generic/string-fza.h b/sysdeps/generic/string-fza.h
new file mode 100644
index 0000000000..69ee04d750
--- /dev/null
+++ b/sysdeps/generic/string-fza.h
@@ -0,0 +1,98 @@
+/* Basic zero byte detection. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZA_H
+#define _STRING_FZA_H 1
+
+#include <string-misc.h>
+#include <string-optype.h>
+
+/* The function return a byte mask. */
+typedef op_t find_t;
+
+/* This function returns non-zero if any byte in X is zero.
+ More specifically, at least one bit set within the least significant
+ byte that was zero; other bytes within the word are indeterminate. */
+static __always_inline find_t
+find_zero_low (op_t x)
+{
+ /* This expression comes from
+ https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
+ Subtracting 1 sets 0x80 in a byte that was 0; anding ~x clears
+ 0x80 in a byte that was >= 128; anding 0x80 isolates that test bit. */
+ op_t lsb = repeat_bytes (0x01);
+ op_t msb = repeat_bytes (0x80);
+ return (x - lsb) & ~x & msb;
+}
+
+/* This function returns at least one bit set within every byte of X that
+ is zero. The result is exact in that, unlike find_zero_low, all bytes
+ are determinate. This is usually used for finding the index of the
+ most significant byte that was zero. */
+static __always_inline find_t
+find_zero_all (op_t x)
+{
+ /* For each byte, find not-zero by
+ (0) And 0x7f so that we cannot carry between bytes,
+ (1) Add 0x7f so that non-zero carries into 0x80,
+ (2) Or in the original byte (which might have had 0x80 set).
+ Then invert and mask such that 0x80 is set iff that byte was zero. */
+ op_t m = repeat_bytes (0x7f);
+ return ~(((x & m) + m) | x | m);
+}
+
+/* With similar caveats, identify bytes that are equal between X1 and X2. */
+static __always_inline find_t
+find_eq_low (op_t x1, op_t x2)
+{
+ return find_zero_low (x1 ^ x2);
+}
+
+static __always_inline find_t
+find_eq_all (op_t x1, op_t x2)
+{
+ return find_zero_all (x1 ^ x2);
+}
+
+/* With similar caveats, identify zero bytes in X1 and bytes that are
+ equal between in X1 and X2. */
+static __always_inline find_t
+find_zero_eq_low (op_t x1, op_t x2)
+{
+ return find_zero_low (x1) | find_zero_low (x1 ^ x2);
+}
+
+static __always_inline find_t
+find_zero_eq_all (op_t x1, op_t x2)
+{
+ return find_zero_all (x1) | find_zero_all (x1 ^ x2);
+}
+
+/* With similar caveats, identify zero bytes in X1 and bytes that are
+ not equal between in X1 and X2. */
+static __always_inline find_t
+find_zero_ne_all (op_t x1, op_t x2)
+{
+ op_t m = repeat_bytes (0x7f);
+ op_t eq = x1 ^ x2;
+ op_t nz1 = ((x1 & m) + m) | x1;
+ op_t ne2 = ((eq & m) + m) | eq;
+ return (ne2 | ~nz1) & ~m;
+}
+
+#endif /* _STRING_FZA_H */
diff --git a/sysdeps/generic/string-fzb.h b/sysdeps/generic/string-fzb.h
new file mode 100644
index 0000000000..42de500d67
--- /dev/null
+++ b/sysdeps/generic/string-fzb.h
@@ -0,0 +1,49 @@
+/* Zero byte detection, boolean. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZB_H
+#define _STRING_FZB_H 1
+
+#include <endian.h>
+#include <string-fza.h>
+
+/* Determine if any byte within X is zero. This is a pure boolean test. */
+
+static __always_inline _Bool
+has_zero (op_t x)
+{
+ return find_zero_low (x) != 0;
+}
+
+/* Likewise, but for byte equality between X1 and X2. */
+
+static __always_inline _Bool
+has_eq (op_t x1, op_t x2)
+{
+ return find_eq_low (x1, x2) != 0;
+}
+
+/* Likewise, but for zeros in X1 and equal bytes between X1 and X2. */
+
+static __always_inline _Bool
+has_zero_eq (op_t x1, op_t x2)
+{
+ return find_zero_eq_low (x1, x2);
+}
+
+#endif /* _STRING_FZB_H */
diff --git a/sysdeps/generic/string-fzc.h b/sysdeps/generic/string-fzc.h
new file mode 100644
index 0000000000..ae2f9640ab
--- /dev/null
+++ b/sysdeps/generic/string-fzc.h
@@ -0,0 +1,87 @@
+/* Zero byte detection; indexes. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZC_H
+#define _STRING_FZC_H 1
+
+#include <endian.h>
+#include <string-fza.h>
+#include <string-fzi.h>
+
+
+/* Given a word X that is known to contain a zero byte, return the index of
+ the first such within the word in memory order. */
+static __always_inline unsigned int
+index_first_zero (op_t x)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ x = find_zero_low (x);
+ else
+ x = find_zero_all (x);
+ return index_first (x);
+}
+
+/* Similarly, but perform the search for byte equality between X1 and X2. */
+static __always_inline unsigned int
+index_first_eq (op_t x1, op_t x2)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ x1 = find_eq_low (x1, x2);
+ else
+ x1 = find_eq_all (x1, x2);
+ return index_first (x1);
+}
+
+/* Similarly, but perform the search for zero within X1 or equality between
+ X1 and X2. */
+static __always_inline unsigned int
+index_first_zero_eq (op_t x1, op_t x2)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ x1 = find_zero_eq_low (x1, x2);
+ else
+ x1 = find_zero_eq_all (x1, x2);
+ return index_first (x1);
+}
+
+/* Similarly, but perform the search for zero within X1 or inequality between
+ X1 and X2. */
+static __always_inline unsigned int
+index_first_zero_ne (op_t x1, op_t x2)
+{
+ return index_first (find_zero_ne_all (x1, x2));
+}
+
+/* Similarly, but search for the last zero within X. */
+static __always_inline unsigned int
+index_last_zero (op_t x)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ x = find_zero_all (x);
+ else
+ x = find_zero_low (x);
+ return index_last (x);
+}
+
+static __always_inline unsigned int
+index_last_eq (op_t x1, op_t x2)
+{
+ return index_last_zero (x1 ^ x2);
+}
+
+#endif /* STRING_FZC_H */
diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h
new file mode 100644
index 0000000000..2deecefc23
--- /dev/null
+++ b/sysdeps/generic/string-fzi.h
@@ -0,0 +1,71 @@
+/* Zero byte detection; indexes. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZI_H
+#define _STRING_FZI_H 1
+
+#include <limits.h>
+#include <endian.h>
+#include <string-fza.h>
+
+static __always_inline int
+clz (find_t c)
+{
+ if (sizeof (find_t) == sizeof (unsigned long))
+ return __builtin_clzl (c);
+ else
+ return __builtin_clzll (c);
+}
+
+static __always_inline int
+ctz (find_t c)
+{
+ if (sizeof (find_t) == sizeof (unsigned long))
+ return __builtin_ctzl (c);
+ else
+ return __builtin_ctzll (c);
+}
+
+/* A subroutine for the index_zero functions. Given a test word C, return
+ the (memory order) index of the first byte (in memory order) that is
+ non-zero. */
+static __always_inline unsigned int
+index_first (find_t c)
+{
+ int r;
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ r = ctz (c);
+ else
+ r = clz (c);
+ return r / CHAR_BIT;
+}
+
+/* Similarly, but return the (memory order) index of the last byte that is
+ non-zero. */
+static __always_inline unsigned int
+index_last (find_t c)
+{
+ int r;
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ r = clz (c);
+ else
+ r = ctz (c);
+ return sizeof (find_t) - 1 - (r / CHAR_BIT);
+}
+
+#endif /* STRING_FZI_H */
diff --git a/sysdeps/generic/string-misc.h b/sysdeps/generic/string-misc.h
new file mode 100644
index 0000000000..a119646957
--- /dev/null
+++ b/sysdeps/generic/string-misc.h
@@ -0,0 +1,45 @@
+/* Miscellaneous functions used in string implementations. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_MISC_H
+#define _STRING_MISC_H 1
+
+#include <limits.h>
+#include <endian.h>
+#include <string-optype.h>
+
+/* Extract the byte at index IDX from word X, with index 0 being the
+ least significant byte. */
+static __always_inline unsigned char
+extractbyte (op_t x, unsigned int idx)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ return x >> (idx * CHAR_BIT);
+ else
+ return x >> (sizeof (x) - 1 - idx) * CHAR_BIT;
+}
+
+/* Setup an word with each byte being c_in. For instance, on a 64 bits
+ machine with input as 0xce the functions returns 0xcececececececece. */
+static __always_inline op_t
+repeat_bytes (unsigned char c_in)
+{
+ return ((op_t)-1 / 0xff) * c_in;
+}
+
+#endif /* _STRING_MISC_H */
diff --git a/sysdeps/generic/string-shift.h b/sysdeps/generic/string-shift.h
new file mode 100644
index 0000000000..9491e8b580
--- /dev/null
+++ b/sysdeps/generic/string-shift.h
@@ -0,0 +1,52 @@
+/* Shift unaligned word read Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_SHIFT_H
+#define _STRING_SHIFT_H 1
+
+#include <endian.h>
+#include <limits.h>
+#include <stdint.h>
+#include <string-fza.h>
+
+/* Return the mask WORD shifted based on S_INT address value, to ignore
+ values not presented in the aligned word read. */
+static __always_inline find_t
+shift_find (find_t word, uintptr_t s)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ return word >> (CHAR_BIT * (s % sizeof (op_t)));
+ else
+ return word << (CHAR_BIT * (s % sizeof (op_t)));
+}
+
+/* Mask off the bits defined for the S alignment value, or return WORD if
+ S is 0. */
+static __always_inline find_t
+shift_find_last (find_t word, uintptr_t s)
+{
+ s = s % sizeof (op_t);
+ if (s == 0)
+ return word;
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ return word & ~(((op_t)-1) << (s * CHAR_BIT));
+ else
+ return word & ~(((op_t)-1) >> (s * CHAR_BIT));
+}
+
+#endif /* _STRING_SHIFT_H */
On 2/3/23 03:40, Adhemerval Zanella Netto wrote:
> I will send only this patch to avoid resend all the thread that is already
> reviewed.
>
> ---
>
> [PATCH 03/31] Add string vectorized find and detection functions
>
> This patch adds generic string find and detection meant to be used in
> generic vectorized string implementation. The idea is to decompose the
> basic string operation so each architecture can reimplement if it
> provides any specialized hardware instruction.
Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
r~
>
> The 'string-misc.h' provides miscellaneous functions:
>
> - extractbyte: extracts the byte from an specific index.
> - repeat_bytes: setup an word by replicate the argument on each byte.
>
> The 'string-fza.h' provides zero byte detection functions:
>
> - find_zero_low, find_zero_all, find_eq_low, find_eq_all,
> find_zero_eq_low, find_zero_eq_all, and find_zero_ne_all
>
> The 'string-fzb.h' provides boolean zero byte detection functions:
>
> - has_zero: determine if any byte within a word is zero.
> - has_eq: determine byte equality between two words.
> - has_zero_eq: determine if any byte within a word is zero along with
> byte equality between two words.
>
> The 'string-fzi.h' provides positions for string-fza.h results:
>
> - index_first: return index of first zero byte within a word.
> - index_last: return index of first byte different between two words.
>
> The 'string-fzc.h' provides a combined version of fza and fzi:
>
> - index_first_zero_eq: return index of first zero byte within a word or
> first byte different between two words.
> - index_first_zero_ne: return index of first zero byte within a word or
> first byte equal between two words.
> - index_last_zero: return index of last zero byte within a word.
> - index_last_eq: return index of last byte different between two words.
>
> The 'string-shift.h' provides a way to mask off parts of a work based on
> some alignmnet (to handle unaligned arguments):
>
> - shift_find, shift_find_last.
>
> Co-authored-by: Richard Henderson <richard.henderson@linaro.org>
new file mode 100644
@@ -0,0 +1,104 @@
+/* Basic zero byte detection. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZA_H
+#define _STRING_FZA_H 1
+
+#include <string-misc.h>
+#include <string-optype.h>
+
+/* The function return a byte mask. */
+typedef op_t find_t;
+
+/* This function returns non-zero if any byte in X is zero.
+ More specifically, at least one bit set within the least significant
+ byte that was zero; other bytes within the word are indeterminate. */
+static __always_inline find_t
+find_zero_low (op_t x)
+{
+ /* This expression comes from
+ https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
+ Subtracting 1 sets 0x80 in a byte that was 0; anding ~x clears
+ 0x80 in a byte that was >= 128; anding 0x80 isolates that test bit. */
+ op_t lsb = repeat_bytes (0x01);
+ op_t msb = repeat_bytes (0x80);
+ return (x - lsb) & ~x & msb;
+}
+
+/* This function returns at least one bit set within every byte of X that
+ is zero. The result is exact in that, unlike find_zero_low, all bytes
+ are determinate. This is usually used for finding the index of the
+ most significant byte that was zero. */
+static __always_inline find_t
+find_zero_all (op_t x)
+{
+ /* For each byte, find not-zero by
+ (0) And 0x7f so that we cannot carry between bytes,
+ (1) Add 0x7f so that non-zero carries into 0x80,
+ (2) Or in the original byte (which might have had 0x80 set).
+ Then invert and mask such that 0x80 is set iff that byte was zero. */
+ op_t m = repeat_bytes (0x7f);
+ return ~(((x & m) + m) | x | m);
+}
+
+/* With similar caveats, identify bytes that are equal between X1 and X2. */
+static __always_inline find_t
+find_eq_low (op_t x1, op_t x2)
+{
+ return find_zero_low (x1 ^ x2);
+}
+
+static __always_inline find_t
+find_eq_all (op_t x1, op_t x2)
+{
+ return find_zero_all (x1 ^ x2);
+}
+
+/* With similar caveats, identify zero bytes in X1 and bytes that are
+ equal between in X1 and X2. */
+static __always_inline find_t
+find_zero_eq_low (op_t x1, op_t x2)
+{
+ return find_zero_low (x1) | find_zero_low (x1 ^ x2);
+}
+
+static __always_inline find_t
+find_zero_eq_all (op_t x1, op_t x2)
+{
+ return find_zero_all (x1) | find_zero_all (x1 ^ x2);
+}
+
+/* With similar caveats, identify zero bytes in X1 and bytes that are
+ not equal between in X1 and X2. */
+static __always_inline find_t
+find_zero_ne_low (op_t x1, op_t x2)
+{
+ return (~find_zero_eq_low (x1, x2)) + 1;
+}
+
+static __always_inline find_t
+find_zero_ne_all (op_t x1, op_t x2)
+{
+ op_t m = repeat_bytes (0x7f);
+ op_t eq = x1 ^ x2;
+ op_t nz1 = ((x1 & m) + m) | x1;
+ op_t ne2 = ((eq & m) + m) | eq;
+ return (ne2 | ~nz1) & ~m;
+}
+
+#endif /* _STRING_FZA_H */
new file mode 100644
@@ -0,0 +1,49 @@
+/* Zero byte detection, boolean. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZB_H
+#define _STRING_FZB_H 1
+
+#include <endian.h>
+#include <string-fza.h>
+
+/* Determine if any byte within X is zero. This is a pure boolean test. */
+
+static __always_inline _Bool
+has_zero (op_t x)
+{
+ return find_zero_low (x) != 0;
+}
+
+/* Likewise, but for byte equality between X1 and X2. */
+
+static __always_inline _Bool
+has_eq (op_t x1, op_t x2)
+{
+ return find_eq_low (x1, x2) != 0;
+}
+
+/* Likewise, but for zeros in X1 and equal bytes between X1 and X2. */
+
+static __always_inline _Bool
+has_zero_eq (op_t x1, op_t x2)
+{
+ return find_zero_eq_low (x1, x2);
+}
+
+#endif /* _STRING_FZB_H */
new file mode 100644
@@ -0,0 +1,83 @@
+/* Zero byte detection; indexes. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZC_H
+#define _STRING_FZC_H 1
+
+#include <endian.h>
+#include <string-fza.h>
+#include <string-fzi.h>
+
+
+/* Given a word X that is known to contain a zero byte, return the index of
+ the first such within the word in memory order. */
+static __always_inline unsigned int
+index_first_zero (op_t x)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ x = find_zero_low (x);
+ else
+ x = find_zero_all (x);
+ return index_first (x);
+}
+
+/* Similarly, but perform the search for byte equality between X1 and X2. */
+static __always_inline unsigned int
+index_first_eq (op_t x1, op_t x2)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ x1 = find_eq_low (x1, x2);
+ else
+ x1 = find_eq_all (x1, x2);
+ return index_first (x1);
+}
+
+/* Similarly, but perform the search for zero within X1 or equality between
+ X1 and X2. */
+static __always_inline unsigned int
+index_first_zero_eq (op_t x1, op_t x2)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ x1 = find_zero_eq_low (x1, x2);
+ else
+ x1 = find_zero_eq_all (x1, x2);
+ return index_first (x1);
+}
+
+/* Similarly, but perform the search for zero within X1 or inequality between
+ X1 and X2. */
+static __always_inline unsigned int
+index_first_zero_ne (op_t x1, op_t x2)
+{
+ return index_first (find_zero_ne_all (x1, x2));
+}
+
+/* Similarly, but search for the last zero within X. */
+static __always_inline unsigned int
+index_last_zero (op_t x)
+{
+ return index_last (find_zero_all (x));
+}
+
+static __always_inline unsigned int
+index_last_eq (op_t x1, op_t x2)
+{
+ return index_last_zero (x1 ^ x2);
+}
+
+#endif /* STRING_FZC_H */
new file mode 100644
@@ -0,0 +1,71 @@
+/* Zero byte detection; indexes. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_FZI_H
+#define _STRING_FZI_H 1
+
+#include <limits.h>
+#include <endian.h>
+#include <string-fza.h>
+
+static __always_inline int
+clz (find_t c)
+{
+ if (sizeof (find_t) == sizeof (unsigned long))
+ return __builtin_clzl (c);
+ else
+ return __builtin_clzll (c);
+}
+
+static __always_inline int
+ctz (find_t c)
+{
+ if (sizeof (find_t) == sizeof (unsigned long))
+ return __builtin_ctzl (c);
+ else
+ return __builtin_ctzll (c);
+}
+
+/* A subroutine for the index_zero functions. Given a test word C, return
+ the (memory order) index of the first byte (in memory order) that is
+ non-zero. */
+static __always_inline unsigned int
+index_first (find_t c)
+{
+ int r;
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ r = ctz (c);
+ else
+ r = clz (c);
+ return r / CHAR_BIT;
+}
+
+/* Similarly, but return the (memory order) index of the last byte that is
+ non-zero. */
+static __always_inline unsigned int
+index_last (find_t c)
+{
+ int r;
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ r = clz (c);
+ else
+ r = ctz (c);
+ return sizeof (find_t) - 1 - (r / CHAR_BIT);
+}
+
+#endif /* STRING_FZI_H */
new file mode 100644
@@ -0,0 +1,45 @@
+/* Miscellaneous functions used in string implementations. Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_MISC_H
+#define _STRING_MISC_H 1
+
+#include <limits.h>
+#include <endian.h>
+#include <string-optype.h>
+
+/* Extract the byte at index IDX from word X, with index 0 being the
+ least significant byte. */
+static __always_inline unsigned char
+extractbyte (op_t x, unsigned int idx)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ return x >> (idx * CHAR_BIT);
+ else
+ return x >> (sizeof (x) - 1 - idx) * CHAR_BIT;
+}
+
+/* Setup an word with each byte being c_in. For instance, on a 64 bits
+ machine with input as 0xce the functions returns 0xcececececececece. */
+static __always_inline op_t
+repeat_bytes (unsigned char c_in)
+{
+ return ((op_t)-1 / 0xff) * c_in;
+}
+
+#endif /* _STRING_MISC_H */
new file mode 100644
@@ -0,0 +1,52 @@
+/* Shift unaligned word read Generic C version.
+ Copyright (C) 2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _STRING_SHIFT_H
+#define _STRING_SHIFT_H 1
+
+#include <endian.h>
+#include <limits.h>
+#include <stdint.h>
+#include <string-fza.h>
+
+/* Return the mask WORD shifted based on S_INT address value, to ignore
+ values not presented in the aligned word read. */
+static __always_inline find_t
+shift_find (find_t word, uintptr_t s)
+{
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ return word >> (CHAR_BIT * (s % sizeof (op_t)));
+ else
+ return word << (CHAR_BIT * (s % sizeof (op_t)));
+}
+
+/* Mask off the bits defined for the S alignment value, or return WORD if
+ S is 0. */
+static __always_inline find_t
+shift_find_last (find_t word, uintptr_t s)
+{
+ s = s % sizeof (op_t);
+ if (s == 0)
+ return word;
+ if (__BYTE_ORDER == __LITTLE_ENDIAN)
+ return word & ~(((op_t)-1) << (s * CHAR_BIT));
+ else
+ return word & ~(((op_t)-1) >> (s * CHAR_BIT));
+}
+
+#endif /* _STRING_SHIFT_H */