Re: speed up verifying UTF-8

On 03/06/2021 17:33, Greg Stark wrote:
>> 3. It's probably cheaper perform the HAS_ZERO check just once on (half1
> | half2). We have to compute (half1 | half2) anyway.
>
> Wouldn't you have to check (half1 & half2) ?

Ah, you're right of course. But & is not quite right either, it will
give false positives. That's ok from a correctness point of view here,
because we then fall back to checking byte by byte, but I don't think
it's a good tradeoff.

I think this works, however:

/* Verify a chunk of bytes for valid ASCII including a zero-byte check. */
static inline int
check_ascii(const unsigned char *s, int len)
{
uint64 half1,
half2,
highbits_set;
uint64 x1,
x2;
uint64 x;

if (len >= 2 * sizeof(uint64))
{
memcpy(&half1, s, sizeof(uint64));
memcpy(&half2, s + sizeof(uint64), sizeof(uint64));

/* Check if any bytes in this chunk have the high bit set. */
highbits_set = ((half1 | half2) & UINT64CONST(0x8080808080808080));
if (highbits_set)
return 0;

/*
* Check if there are any zero bytes in this chunk.
*
* First, add 0x7f to each byte. This sets the high bit in each byte,
* unless it was a zero. We already checked that none of the bytes had
* the high bit set previously, so the max value each byte can have
* after the addition is 0x7f + 0x7f = 0xfe, and we don't need to
* worry about carrying over to the next byte.
*/
x1 = half1 + UINT64CONST(0x7f7f7f7f7f7f7f7f);
x2 = half2 + UINT64CONST(0x7f7f7f7f7f7f7f7f);

/* then check that the high bit is set in each byte. */
x = (x1 | x2);
x &= UINT64CONST(0x8080808080808080);
if (x != UINT64CONST(0x8080808080808080))
return 0;

return 2 * sizeof(uint64);
}
else
return 0;
}

- Heikki