1 | /* Basic zero byte detection. Generic C version. |
2 | Copyright (C) 2023-2024 Free Software Foundation, Inc. |
3 | This file is part of the GNU C Library. |
4 | |
5 | The GNU C Library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | The GNU C Library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, see |
17 | <http://www.gnu.org/licenses/>. */ |
18 | |
19 | #ifndef _STRING_FZA_H |
20 | #define _STRING_FZA_H 1 |
21 | |
22 | #include <string-misc.h> |
23 | #include <string-optype.h> |
24 | |
25 | /* The function return a byte mask. */ |
26 | typedef op_t find_t; |
27 | |
28 | /* This function returns non-zero if any byte in X is zero. |
29 | More specifically, at least one bit set within the least significant |
30 | byte that was zero; other bytes within the word are indeterminate. */ |
31 | static __always_inline find_t |
32 | find_zero_low (op_t x) |
33 | { |
34 | /* This expression comes from |
35 | https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord |
36 | Subtracting 1 sets 0x80 in a byte that was 0; anding ~x clears |
37 | 0x80 in a byte that was >= 128; anding 0x80 isolates that test bit. */ |
38 | op_t lsb = repeat_bytes (c_in: 0x01); |
39 | op_t msb = repeat_bytes (c_in: 0x80); |
40 | return (x - lsb) & ~x & msb; |
41 | } |
42 | |
43 | /* This function returns at least one bit set within every byte of X that |
44 | is zero. The result is exact in that, unlike find_zero_low, all bytes |
45 | are determinate. This is usually used for finding the index of the |
46 | most significant byte that was zero. */ |
47 | static __always_inline find_t |
48 | find_zero_all (op_t x) |
49 | { |
50 | /* For each byte, find not-zero by |
51 | (0) And 0x7f so that we cannot carry between bytes, |
52 | (1) Add 0x7f so that non-zero carries into 0x80, |
53 | (2) Or in the original byte (which might have had 0x80 set). |
54 | Then invert and mask such that 0x80 is set iff that byte was zero. */ |
55 | op_t m = repeat_bytes (c_in: 0x7f); |
56 | return ~(((x & m) + m) | x | m); |
57 | } |
58 | |
59 | /* With similar caveats, identify bytes that are equal between X1 and X2. */ |
60 | static __always_inline find_t |
61 | find_eq_low (op_t x1, op_t x2) |
62 | { |
63 | return find_zero_low (x: x1 ^ x2); |
64 | } |
65 | |
66 | static __always_inline find_t |
67 | find_eq_all (op_t x1, op_t x2) |
68 | { |
69 | return find_zero_all (x: x1 ^ x2); |
70 | } |
71 | |
72 | /* With similar caveats, identify zero bytes in X1 and bytes that are |
73 | equal between in X1 and X2. */ |
74 | static __always_inline find_t |
75 | find_zero_eq_low (op_t x1, op_t x2) |
76 | { |
77 | return find_zero_low (x: x1) | find_zero_low (x: x1 ^ x2); |
78 | } |
79 | |
80 | static __always_inline find_t |
81 | find_zero_eq_all (op_t x1, op_t x2) |
82 | { |
83 | return find_zero_all (x: x1) | find_zero_all (x: x1 ^ x2); |
84 | } |
85 | |
86 | /* With similar caveats, identify zero bytes in X1 and bytes that are |
87 | not equal between in X1 and X2. */ |
88 | static __always_inline find_t |
89 | find_zero_ne_all (op_t x1, op_t x2) |
90 | { |
91 | op_t m = repeat_bytes (c_in: 0x7f); |
92 | op_t eq = x1 ^ x2; |
93 | op_t nz1 = ((x1 & m) + m) | x1; |
94 | op_t ne2 = ((eq & m) + m) | eq; |
95 | return (ne2 | ~nz1) & ~m; |
96 | } |
97 | |
98 | #endif /* _STRING_FZA_H */ |
99 | |