1  /* Basic zero byte detection.  Generic C version.
       2     Copyright (C) 2023 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 (0x01);
      39    op_t msb = repeat_bytes (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 (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 (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 (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 (x1) | find_zero_low (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 (x1) | find_zero_all (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 (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 */