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