HomeFreeBSD

lib/libc/amd64/string: add strcspn(3) scalar, x86-64-v2 implementation

Description

lib/libc/amd64/string: add strcspn(3) scalar, x86-64-v2 implementation

This changeset adds both a scalar and an x86-64-v2 implementation
of the strcspn(3) function to libc. A baseline implementation does not
appear to be feasible given the requirements of the function.

The scalar implementation is similar to the generic libc implementation,
but expands the bit set into a byte set to reduce latency, improving
performance. This approach could probably be backported to the generic
C version to benefit other platforms.

The x86-64-v2 implementation is built around the infamous pcmpistri
instruction. An alternative implementation based on the Muła/Langdale
algorithm [1] was prototyped, but performed worse than the pcmpistri
approach except for sets of more than 16 characters with long input
strings.

All implementations provide special cases for the empty set (reduces to
strlen as well as single-character sets (reduces to strchr). The
x86-64-v2 kernel falls back to the scalar implementation for sets of
more than 32 characters. This limit could be raised by additional
multiples of 16 through the use of additional pcmpistri code paths, but
I consider this case to be too rare to be of importance.

[1]: http://0x80.pl/articles/simd-byte-lookup.html

Sponsored by: The FreeBSD Foundation
Approved by: mjg
MFC after: 1 week
MFC to: stable/14
Differential Revision: https://reviews.freebsd.org/D41557

Details

Provenance
fuzAuthored on Aug 13 2023, 5:35 PM
Differential Revision
D41557: lib/libc/amd64/string: add strcspn(3) scalar, x86-64-v2 implementation, unit tests
Parents
rG604f6bf022ce: powerpcspe: Fix build
Branches
Unknown
Tags
Unknown