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. */
26typedef 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. */
31static __always_inline find_t
32find_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. */
47static __always_inline find_t
48find_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. */
60static __always_inline find_t
61find_eq_low (op_t x1, op_t x2)
62{
63 return find_zero_low (x: x1 ^ x2);
64}
65
66static __always_inline find_t
67find_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. */
74static __always_inline find_t
75find_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
80static __always_inline find_t
81find_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. */
88static __always_inline find_t
89find_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

source code of glibc/sysdeps/generic/string-fza.h