arch/tile/lib/memchr_32.c

   1 /*
   2  * Copyright 2010 Tilera Corporation. All Rights Reserved.
   3  *
   4  *   This program is free software; you can redistribute it and/or
   5  *   modify it under the terms of the GNU General Public License
   6  *   as published by the Free Software Foundation, version 2.
   7  *
   8  *   This program is distributed in the hope that it will be useful, but
   9  *   WITHOUT ANY WARRANTY; without even the implied warranty of
  10  *   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, GOOD TITLE or
  11  *   NON INFRINGEMENT.  See the GNU General Public License for
  12  *   more details.
  13  */
  14
  15 #include <linux/types.h>
  16 #include <linux/string.h>
  17 #include <linux/module.h>
  18
  19 void *memchr(const void *s, int c, size_t n)
  20 {
  21         /* Get an aligned pointer. */
  22         const uintptr_t s_int = (uintptr_t) s;
  23         const uint32_t *p = (const uint32_t *)(s_int & -4);
  24
  25         /* Create four copies of the byte for which we are looking. */
  26         const uint32_t goal = 0x01010101 * (uint8_t) c;
  27
  28         /* Read the first word, but munge it so that bytes before the array
  29          * will not match goal.
  30          *
  31          * Note that this shift count expression works because we know
  32          * shift counts are taken mod 32.
  33          */
  34         const uint32_t before_mask = (1 << (s_int << 3)) - 1;
  35         uint32_t v = (*p | before_mask) ^ (goal & before_mask);
  36
  37         /* Compute the address of the last byte. */
  38         const char *const last_byte_ptr = (const char *)s + n - 1;
  39
  40         /* Compute the address of the word containing the last byte. */
  41         const uint32_t *const last_word_ptr =
  42             (const uint32_t *)((uintptr_t) last_byte_ptr & -4);
  43
  44         uint32_t bits;
  45         char *ret;
  46
  47         if (__builtin_expect(n == 0, 0)) {
  48                 /* Don't dereference any memory if the array is empty. */
  49                 return NULL;
  50         }
  51
  52         while ((bits = __insn_seqb(v, goal)) == 0) {
  53                 if (__builtin_expect(p == last_word_ptr, 0)) {
  54                         /* We already read the last word in the array,
  55                          * so give up.
  56                          */
  57                         return NULL;
  58                 }
  59                 v = *++p;
  60         }
  61
  62         /* We found a match, but it might be in a byte past the end
  63          * of the array.
  64          */
  65         ret = ((char *)p) + (__insn_ctz(bits) >> 3);
  66         return (ret <= last_byte_ptr) ? ret : NULL;
  67 }
  68 EXPORT_SYMBOL(memchr);