/*
	search routine generated by gen.
	skip=fast, match=rev (using revr), shift=d12
*/
/*
 * The authors of this software are Andrew Hume and Daniel Sunday.
 *
 * Copyright (c) 1991 by AT&T and Daniel Sunday.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 *

   Copyright (C) 2013 Embecosm Limited and University of Bristol

   Contributor: James Pallister <james.pallister@bristol.ac.uk>

   This file is part of the Bristol/Embecosm Embedded Benchmark Suite.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program. If not, see <http://www.gnu.org/licenses/>. */

#include <string.h>
#include <stdlib.h>

#ifndef	CHARTYPE
#define	CHARTYPE	unsigned char
#endif
#define	MAXPAT	256

#ifndef	TABTYPE
#define	TABTYPE	long
#endif
typedef TABTYPE Tab;

static struct
{
	int patlen;
	CHARTYPE pat[MAXPAT];
	Tab delta[256];
	int lastchar;
	Tab delta1[256];
	Tab delta2[257];
} pat;

void
prep2(CHARTYPE *base, register int m)
{
	register CHARTYPE *pe, *p;
	register int j;
	register Tab *d;
	register Tab *d2;
	register int q1, t, qp, jp, kp;
	Tab f[256], f1[256];

	pat.patlen = m;
	if(m > MAXPAT)
		abort();
	memcpy(pat.pat, base, m);
	d = pat.delta;
	for(j = 0; j < 256; j++)
		d[j] = pat.patlen;
	for(p = pat.pat, pe = p+m-1; p < pe; p++)
		d[*p] = pe-p;
	pat.lastchar = *p;
	d2 = pat.delta1;
	for(j = 0; j < 256; j++)
		d2[j] = m;
	for(j = 0; j < m; j++)
		d2[base[j]] = m-1-j;
	d2 = pat.delta2;
	for(j = 1; j < m; j++)
		d2[j] = 2*m-j;
	for(j = m, t = m+1; j > 0; j--, t--){
		f[j] = t;
		while((t <= m) && (base[t-1] != base[j-1])){
			if((m-j) < d2[t])
				d2[t] = m-j;
			t = f[t];
		}
	}
	q1 = t;
	t = m+1-q1;
	qp = 1;
	for(jp = 1, kp = 0; kp < t; jp++, kp++){
		f1[jp] = kp;
		while((kp >= 1) && (base[jp-1] != base[kp-1]))
			kp = f1[kp];
	}
	while(q1 < m){
		for(j = qp; j <= q1; j++)
			if(m+q1-j < d2[j])
				d2[j] = m+q1-j;
		qp = q1+1;
		q1 += t-f1[t];
		t = f1[t];
	}
	/*for(j=1; j<=m; j++)printf("[%d]=%d ", j, d2[j]); printf("\n");*/
	d2[0] = m+1;		/* the case where the match succeeded */
}

int
exec2(CHARTYPE *base, int n)
{
	int nmatch = 0;
	register CHARTYPE *e, *s;
	register Tab *d0 = pat.delta;
	int lastdelta;
	register CHARTYPE *p, *q;
	register CHARTYPE *prev = pat.pat+pat.patlen-1;
	register Tab *d1 = pat.delta1;
	register Tab *d2 = pat.delta2+1;
	register int k1, k2;

	lastdelta = n+pat.patlen;
	d0[pat.lastchar] = lastdelta;	/* guaranteed to break s < e loop */
	s = base+pat.patlen-1;
	e = base+n;
	while(s < e){
#ifdef	STATS
		for(;;){
			stats.jump++;
			if((s += (k = d0[*s])) >= e) break;
			stats.step[k]++;
		}
		if(s < e+pat.patlen)
			stats.step[k]++;
#else
		while((s += d0[*s]) < e)
			;
#endif
		if(s < e+pat.patlen)	/* no match */
			break;
		s -= lastdelta;
#ifdef	STATS
		stats.slow++;
#endif
#define	RH	s
		for(p = prev, q = RH; p > pat.pat; ){
#ifdef	STATS
			stats.cmp++;
#endif
			if(*--q != *--p)
				goto mismatch;
		}
		nmatch++;
	mismatch:
		k2 = d2[p-pat.pat];
		k1 = d1[*q];
		if(k2 < k1)
			k2 = k1;
		k2 = q+k2-RH;
#ifdef	STATS
		stats.step[k2]++; stats.jump++;
#endif
		s += k2;
	}
	return(nmatch);
}
