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.

This includes the bug fix from 52d4a4d.

[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

(cherry picked from commit 474408bb7933f0383a0da2b01e717bfe683ae77c)
(cherry picked from commit 52d4a4d4e0dedc72bc33082a3f84c2d0fd6f2cbb)

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
rG84266fb897e6: Add deprecation notices to publickey(5) tools
Branches
Unknown
Tags
Unknown