/* { dg-do run { target { sysconf && mmap } } } */
/* { dg-options "-O2 -minline-all-stringops" } */

#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#ifndef MAP_ANON
#define MAP_ANON 0
#endif
#ifndef MAP_FAILED
#define MAP_FAILED ((void *)-1)
#endif

uint8_t shift[256];

static size_t
__attribute__ ((noclone, noinline))
hash2(const unsigned char *p)
{
  return (((size_t)(p)[0] - ((size_t)(p)[-1] << 3)) % sizeof (shift));
}

char *
simple_strstr (const char *haystack, const char *needle)
{
  const unsigned char *hs = (const unsigned char *) haystack;
  const unsigned char *ne = (const unsigned char *) needle;
  size_t ne_len = strlen ((const char*)ne);
  size_t hs_len = strnlen ((const char*)hs, ne_len | 512);

  if (hs_len < ne_len)
    return NULL;

  if (memcmp (hs, ne, ne_len) == 0)
    return (char *) hs;

  const unsigned char *end = hs + hs_len - ne_len;
  size_t tmp, shift1;
  size_t m1 = ne_len - 1;
  size_t offset = 0;

  memset (shift, 0, sizeof (shift));
  for (int i = 1; i < m1; i++)
    shift[hash2 (ne + i)] = i;
  shift1 = m1 - shift[hash2 (ne + m1)];
  shift[hash2 (ne + m1)] = m1;

  while (1)
    {
      if (__builtin_expect (hs > end, 0))
	{
	  end += strnlen ((const char*)end + m1 + 1, 2048);
	  if (hs > end)
	    return NULL;
	}

      do
	{
	  hs += m1;
	  tmp = shift[hash2 (hs)];
	}
      while (tmp == 0 && hs <= end);

      hs -= tmp;
      if (tmp < m1)
	continue;

      if (m1 < 15 || memcmp (hs + offset, ne + offset, 8) == 0)
	{
	  if (memcmp (hs, ne, m1) == 0)
	    return (void *) hs;

	  offset = (offset >= 8 ? offset : m1) - 8;
	}

      hs += shift1;
    }
}

static int
check_result (const char *s1, const char *s2,
	      char *exp_result)
{
  char *result = simple_strstr (s1, s2);
  if (result != exp_result)
    return -1;

  return 0;
}

void
__attribute__ ((noclone, noinline))
check1 (void)
{
  const char s1[] =
    "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD_C3_A7_20_EF_BF_BD";
  const char s2[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
  char *exp_result;

  exp_result = simple_strstr (s1, s2);
  if (check_result (s1, s2, exp_result) != 0)
    abort ();
}

int
main (void)
{
  unsigned char *buf1, *buf2;
  size_t page_size = 2 * sysconf(_SC_PAGESIZE);
  buf1 = mmap (0, (1 + 1) * page_size, PROT_READ | PROT_WRITE,
	       MAP_PRIVATE | MAP_ANON, -1, 0);
  if (buf1 == MAP_FAILED)
    return -1;
  if (mprotect (buf1 + 1 * page_size, page_size, PROT_NONE))
    return -1;
  buf2 = mmap (0, 2 * page_size, PROT_READ | PROT_WRITE,
	       MAP_PRIVATE | MAP_ANON, -1, 0);
  if (buf2 == MAP_FAILED)
    return -1;
  if (mprotect (buf2 + page_size, page_size, PROT_NONE))
    return -1;

  memset (buf1, 0xa5, 1 * page_size);
  memset (buf2, 0x5a, page_size);

  check1 ();
  return 0;
}