📜 The approach

We need to:

• Compare against '0' and '1' (or other characters) and report if there's neither of them
• Reverse the order of characters
• Convert byte mask or wchar_t to bit mask
• Handle bitset and string odd length tails
• Handle too short and too long string properly

It is implemented as follows:

• We compare against '1' vector to get byte or wchar_t mask. We xor the input with '0' vector, and check if anything not masked in the resulting byte mask is zero. This way we both validate, and have the mask.
• If we have longer string than bitset, we don't do further steps than byte or wchar_t mask, as we only need to validate,
• To both reverse the order, and convert wchar_t mask to byte mask we use (v)pshufb (..._shuffle_epi8). The AVX2 version is not cross-lane, and additional cross-lane instruction is somewhat expensive, so we fix up that with bits, rather than now.
• (v)pmovmskb is the instruction that does byte mask to bit mask conversion, it is emitted by ..._movemask_epi8 intrinsic.
• Now we do rotations to fix up the missing AVX2 cross-lane reordering
• Then put that to bitset. We assume padding, even if bitset length is smaller.
• Repeat until string ends
• Write zeros to remaining portion of bitset, if there's something left

⚠️ Padding assumption

To avoid unnecessary complication, and have a bit better performance, an assumption was made that bitset has at least a multiple of 2 padding on SSE4.2 code path, and at lest a multiple of 4 padding on AVX2 code path.

For large bitset we have units of uint64_t, and it is not reasonable to have unit less than native integer size, and AVX2 code path has the threshold of 256, since it is not efficient on smaller sizes.

For small bitset we have units of uint32_t, but there's a vNext comment to consider smaller units. But we have a threshold on the whole vectorization as 16 bits, so 8 or less bits bitset that could potentially be less that 2 bytes, would not vectorize.

⚖️ Threshold selection

According to my benchmarks, the vectorized approach benefits for 16 bits, but doesn't for 8 bits. I tried 12, and it seems in favor of non-vectorization. Let it be round up to 16 then.

📏 String length

There are overloads with implicit and explicit length.

For implicit length the non-vectorized implementation calls strlen/wcslen (via character traits).

Hypothetically, vectorized implementation could determine length during conversion. We don't do that here, because:

• This cannot be done ASAN-friendly, see Remove attempt on unsized find vectorization... #4486
• Even if it was possible, this adds complication to already not very simple algorithm

Unfortunately, this causes implicit length overload to benefit much less from vectorization.

⏱️ Benchmark results