[PATCH 10/17] string: Improve generic memchr

[Adhemerval Zanella Netto]

On 19/09/22 18:59, Noah Goldstein wrote:
> On Mon, Sep 19, 2022 at 12:17 PM Adhemerval Zanella Netto
> <adhemerval.zanella@linaro.org> wrote:
>>
>>
>>
>> On 03/09/22 00:47, Noah Goldstein wrote:
>>
>>>>
>>>> -  longword_ptr = (const longword *) char_ptr;
>>>> +  /* Compute the address of the word containing the last byte. */
>>>> +  const op_t *lword = word_containing (lbyte);
>>>>
>>>> -  /* All these elucidatory comments refer to 4-byte longwords,
>>>> -     but the theory applies equally well to any size longwords.  */
>>>> +  /* Read the first word, but munge it so that bytes before the array
>>>> +     will not match goal.  */
>>>> +  const op_t * word_ptr = word_containing (s);
>>>> +  op_t word = (*word_ptr | before_mask) ^ (repeated_c & before_mask);
>>>
>>> Why do you xor with repeated_c & before_mask here?
>>>
>>> Doesn't the has_eq(word, repeated_c) do that?
>>
>> For the case of c_in being 0xff, since for this case or with before_mask
>> will make has_eq to return early.  The test-memchr does not trigger it,
>> but test-memccpy does fail without the XOR.
> 
> I see. Since a match in the first several bytes is fairly common
> maybe it would be better to special case the first iteration and just do
> 
> has_eq(word, repeated_c) >> (CHAR_BIT * (addr % sizeof(addr)).
> The result can just be added to `s` if there is a match.

I think you mean something like:

  has_eq (word >> (CHAR_BIT * (s % sizeof(op_t)), repeated_c) 

Since has_eq returns _Bool.  However in this case we will need to shift
the repeated_c as well, and it will bleed endianess definition (the shift
direction) on generic implementation.  On both cases not sure if this will
be a gain.

Maybe we can also parametrize the first check:

  static inline _Bool
  has_eq_first (op_t *word, const op_t *word_ptr, op_t repeated_c, 
                op_t before_mask)
  {
    *word = (*word_ptr | before_mask) ^ (repeated_c & before_mask);
    return has_eq (*word, repeated_c);
  } 

  [...]

  op_t word;
  if (!has_eq_first (&word, word_ptr, repeated_c, before_mask))
    {
      do
        {
          if (word_ptr == lword)
            return NULL;
          word = *++word_ptr;
        }
      while (!has_eq (word, repeated_c));
    }

If the architecture has a better strategy to check.  But I also not sure
if this would indeed yield any improvement in the end.