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.
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.
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.
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/>. */
20 #define _STRING_FZA_H 1
22 #include <string-misc.h>
23 #include <string-optype.h>
25 /* The function return a byte mask. */
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
)
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 (0x01);
39 op_t msb
= repeat_bytes (0x80);
40 return (x
- lsb
) & ~x
& msb
;
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
)
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 (0x7f);
56 return ~(((x
& m
) + m
) | x
| m
);
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
)
63 return find_zero_low (x1
^ x2
);
66 static __always_inline find_t
67 find_eq_all (op_t x1
, op_t x2
)
69 return find_zero_all (x1
^ x2
);
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
)
77 return find_zero_low (x1
) | find_zero_low (x1
^ x2
);
80 static __always_inline find_t
81 find_zero_eq_all (op_t x1
, op_t x2
)
83 return find_zero_all (x1
) | find_zero_all (x1
^ x2
);
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
)
91 op_t m
= repeat_bytes (0x7f);
93 op_t nz1
= ((x1
& m
) + m
) | x1
;
94 op_t ne2
= ((eq
& m
) + m
) | eq
;
95 return (ne2
| ~nz1
) & ~m
;
98 #endif /* _STRING_FZA_H */