[PATCH 1/2] string: add find_ne_all to string-fza.h

[Matt Turner]

On Thu, Aug 13, 2026 at 5:58 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
>
> Hi Matt,
>
> +static __always_inline find_t
> +find_ne_all (op_t x1, op_t x2)
> +{
> +  op_t m = repeat_bytes (0x7f);
> +  op_t ne = x1 ^ x2;
> +  return (((ne & m) + m) | ne) & ~m;
> +}
>
> That's a lot of code to do very little... In fact we don't need it if
> HAVE_BITOPTS_WORKING is set since clz/ctz work fine on (x1 ^ x2).
>
> The related find_zero_ne_all() has the same issue - we can just do
> (x1 ^ x2) | find_zero_all (x1) if HAVE_BITOPTS_WORKING.
>
> And we could remove the unnecessary code from string-fzi.h if all targets
> now have working stdc_leading_zeros/stdc_trailing_zeros.
>
> Cheers,
> Wilco

Thanks Wilco!

Done in v2, with a guard.

The !HAVE_BITOPTS_WORKING fallback can't take the raw difference: ctzb
computes the byte index as (((c & -c) >> 7) * 0x0001020304050607) >>
56, which needs the lowest set bit at bit 7 of its byte. Over the 64
possible single-bit differences it returns the wrong index for 48 of
them.

static __always_inline find_t
find_ne_all (op_t x1, op_t x2)
{
#if HAVE_BITOPTS_WORKING
  return x1 ^ x2;
#else
  op_t m = repeat_bytes (0x7f);
  op_t ne = x1 ^ x2;
  return (((ne & m) + m) | ne) & ~m;
#endif
}

string-fza.h picks up string-bitops.h for this. find_zero_ne_all gets
the same treatment as (x1 ^ x2) | find_zero_all (x1), in its own
patch.

Also applied to armv6t2 and powerpc, which use the generic
index_first. armv6t2 gains most: index_first (find_ne_all (...)) goes
from 9 instructions to 5, losing the movw/movt constant pair and the
uqsub8. powerpc saves one instruction on find_ne_all; I left its
find_zero_ne_all alone, since orc folds the complement of cmpb into
the or and the sequence comes out the same length. alpha keeps the
reduced form, its find_t being the 8-bit cmpbge mask.

riscv needed more care. Without the bitmap extensions its string-fza.h
falls back to the generic one, while its string-fzi.h defines an
index_first that tests bit 7 of each byte, which the unreduced
difference defeats. v2 adds a riscv string-bitops.h clearing
HAVE_BITOPTS_WORKING in that configuration, where the stdbit.h
routines go unused anyway.

On x86_64 index_first (find_ne_all (...)) goes from 17 instructions to 9.

Tested strspn, strcmp and strncmp for lengths 0 to 300 at every
alignment on alpha EV68, powerpc64 big-endian, 32-bit arm, aarch64 and
x86_64. I have no riscv hardware: the no-zbb pairing is pure C, so I
compiled those headers on x86_64 and ran the tests against them, while
the zbb pairing needs orc.b and is build-tested only.

Separately: HAVE_BITOPTS_WORKING=0 is already broken on powerpc and
armv6t2 without any of my changes. The fallback needs one bit per byte
at 0x80, which only the generic string-fza.h produces; cmpb gives 0xff
per byte and uqsub8 gives 0x01, so strcmp fails immediately with
either. Worth a separate fix, and it strengthens your point about
removing the fallback.


PS: Your mail client seems to break threading. It did it with these
two emails as well as in the email you sent in reply to [PATCH 11/20]
from my other series.