/* fgrep --- grep using Boyer-Moore pattern matcher */

/*
 * All the wrapper code (argument and file handling, printing, etc.) by
 * Arnold Robbins, gatech!arnold
 *
 * Boyer-Moore pattern matching, coded by Roy Mongiovi, gatech!gitpyr!roy
 * and edited some by Arnold Robbins.
 *
 * No warranty of suitability for any purpose, either expressed
 * or implied, is made.
 *
 * VERSION HISTORY
 * ~~~~~~~~~~~~~~~
 * 14 Sep 92    DJW     Removed special wildcard handling code in preference
 *                      of that in the standard C68 library.
 */

#include <std.h>
#include <stdio.h>
#include <ctype.h>
#include <qdos.h>

#define MAXPATS 10             /* (arbitrary maximum number of patterns */
#define MAXLINE (256 + 1)

/*
 * command line options
 */

WORD Allbut = FALSE;             /* print lines that don't match pattern */
WORD Exact = FALSE;              /* only print lines that match exactly */
WORD Countlines = FALSE;         /* only print a count of matching lines */
WORD Listnames = FALSE;          /* only list file names that match */
WORD Numberlines = FALSE;        /* print relative line number */
WORD Silent = FALSE;             /* don't print anything, just exit */
WORD Monocase = FALSE;           /* ignore case distinctions */

/*
 * variables
 */

long Curline = 0;               /* current file input line */
long Lines_matched = 0;         /* how many lines matched the pattern */

WORD Lotsafiles = FALSE;         /* are there more than one file? */
WORD Pat_length[MAXPATS];        /* length of pattern */
WORD Line_length = 0;            /* length of line */
WORD Couldnt_open_files = FALSE; /* one or more files could not be opened */
WORD Exit_val = 0;               /* return code status */
WORD Curpat = 0;                 /* current pattern comparing against */
WORD Numpats = 0;                /* total number of patterns */

char Inbuf[MAXLINE];            /* input buffer */
#ifdef QDOS
#include <qdos.h>
char (*Pattern)[MAXLINE];
char _prog_name[] = "fgrep v1.2b";
int  (*_cmdwildcard)() = cmdexpand;
void (*_consetup)() = consetup_title;
char flistbuf[4L*1024L];
UBYTE (*D1)[128], (*D2)[128], (*F)[128];
#else
char Pattern[MAXPATS][MAXLINE]; /* pattern to be matched; init = NULs */
UBYTE D1[MAXPATS][128];
UBYTE D2[MAXPATS][128];
UBYTE F[MAXPATS][128];
#endif
char *Program = NULL;           /* program name */

static WORD _Argc;                       /* make argc and argv global */
static char **_Argv;

void process(), parse_args(), mapdown(), usage(), patfromfile(), setpats();
static char *index();
static void initialize();

        char *index();

main (argc, argv)
int argc;
char **argv;
{
        WORD i, j, n;
        int err;
        char *p;

        Program = argv[0];
        _Argc = argc;
        _Argv = argv;

#ifdef QDOS
		/* Allocate the neccessary arrays Pattern[10][257], D1[10][128],
			D2[10][128], F[10][128] - from QDOS, fail if cannot */

		p = (char *)mt_alchp( 6410, &err, -1 );
		if( !p || (err < 6410))
			{
			fputs( "Cannot allocate memory for fgrep arrays\n", stderr);
			exit( ERR_OM );
			}

		Pattern = (char (*)[MAXLINE]) p;
		D1 = (char (*)[128]) ( p + 2570 );
		D2 = (char (*)[128]) ( p + 2570 + 1280);
		F = (char (*)[128]) ( p + 2570 + 2*1280 );

#endif
        parse_args ();          /* deal with command line */

        if (Pattern[0][0] == '\0')      /* not from -f or -e */
        {
                if (_Argv[0] == NULL)    /* no string given */
                        usage ();
                setpats (_Argv[0]);
                _Argc--;
                _Argv++;
        }

        for (Curpat = 0; Curpat <= Numpats; Curpat++)
        {
                if (Monocase)
                        mapdown (Pattern[Curpat]);

                Pat_length[Curpat] = strlen (Pattern[Curpat]);
                initialize ();          /* set up necessary tables */
        }

        Lotsafiles = (_Argc > 1 );

        if (_Argc == 0)          /* search stdin */
                process ("-");
        else
                for (i = 0; _Argv[i] != NULL; i++)
                        process ( _Argv[i] );

                if (! Silent && Countlines)
                printf ("%ld\n", Lines_matched);

        else if (Lines_matched == 0)
                exit (0);
        else if (Couldnt_open_files)
                exit (ERR_NO);
        return (exit (0));
}


/* process --- start doing the work on each file */

VOID process (infile)
char *infile;
{
        FILE *fp;
        WORD c;
        WORD success;
        long prev_lines_matched = Lines_matched;        /* save count */

        Curline = 0;    /* reset for each file */

        if (infile[0] == '-' && infile[1] == '\0')
                fp = stdin;
        else if ((fp = fopen (infile, "r")) == NULL)
        {
                Couldnt_open_files = TRUE;
                filerror (infile);
                return;
        }

        while (fgets (Inbuf, sizeof Inbuf, fp) != NULL)
        {
                Curline++;
                if (Monocase)
                        mapdown (Inbuf);
                Line_length = strlen (Inbuf);

                /* first, throw away rest of a truncated input line */
                if (Inbuf[Line_length - 1] != '\n')
						{
						do						
							c = getc( fp );
                        while (c != '\n' && c >= 0);
						if( c < 0)
							break;
						}
                else
                        Inbuf[--Line_length] = '\0';
                        /* newline is there, nuke it */

                for (Curpat = 0; Curpat <= Numpats; Curpat++)
                {
                        if (success = match ())
                                Lines_matched++;
                        /* do any necessary output */
                        if (! Silent && ! Countlines && ! Listnames &&
                                ((success != FALSE) ^ (Allbut != FALSE)))
                                /* either success, or Allbut, but not both,
                                   and not neither */
                        {
                                if (Lotsafiles)
                                        printf ("%s: ", infile);
                                if (Numberlines)
                                        printf ("%ld: ", Curline);
                                printf ("%s\n", Inbuf);
                        }
                }
        }

        fclose (fp);
        if (! Silent && Listnames && prev_lines_matched < Lines_matched)
                printf ("%s\n", infile);
}

/* parse_args --- check out command line arguments */

void parse_args ()
{
        register WORD j;

        if (_Argc == 1)
                usage ();

        for (_Argc--, _Argv++; _Argv[0] != NULL && _Argv[0][0] == '-'; _Argc--, _Argv++)
        {
                WORD cheat = FALSE;

                for (j = 1; _Argv[0][j] != '\0'; j++)
                {
                        switch (_Argv[0][j]) {
                        case 'c':
                                Countlines = TRUE;
                                break;

                        case 'e':
                                strcpy (Pattern[0], _Argv[1]);
                                Pattern[0][sizeof Pattern[0] - 1] = '\0';
                                cheat = TRUE;
                                continue;

                        case 'f':
                                patfromfile (_Argv[1]);
                                cheat = TRUE;
                                continue;

                        case 'i':
                        case 'y':
                                Monocase = TRUE;
                                break;

                        case 'l':
                                Listnames = TRUE;
                                break;

                        case 'n':
                                Numberlines = TRUE;
                                break;

                        case 's':
                                Silent = TRUE;
                                break;

                        case 'v':
                                Allbut = TRUE;
                                break;

                        case 'x':
                                Exact = TRUE;
                                break;

                        default:
                                usage ();
                                break;
                        }
                }
                if (cheat)
                {
                        cheat = FALSE;
                        _Argc--;
                        _Argv++;
                        /* boy is this stuff a kludge! */
                }
        }

        /* check for argument conflicts */
        if (
                (Silent &&
                        (Allbut || Exact || Countlines || Listnames ||
                                Numberlines))
                ||
                (Allbut && Exact)
                ||
                (Countlines && Listnames)
        )
        {
                fprintf (stderr, "%s: argument conflict -- see the man page\n",
                        Program);
                usage ();       /* will exit */
        }
}

/* mapdown --- remove case distinctions in a string */

void mapdown (str)
register char *str;
{
        register WORD i;

        for (i = 0; str[i] != '\0'; i++)
                if (isupper (str[i]))
                        str[i] = tolower (str[i]);
}

/* usage --- print usage message and die */

void usage ()
{
        fprintf (stdout, "\nusage: fgrep [-vxclnisef] [string] [files]\n");
        exit (2);
}

/* index --- do index by hand so it'll work on any Unix */

static char *index (str, c)
char *str, c;
{
        for (; *str; str++)
                if (*str == c)
                        return (str);
        
        return (NULL);
}

/* patfromfile --- retrieve the pattern from the named file */

void patfromfile (infile)
char *infile;
{
        register WORD i, j;
        register FILE *fp;
        register WORD c;

        if ((fp = fopen (infile, "r")) == NULL ||
                        (c = getc (fp)) == EOF)
        {
                filerror (infile);        /* be like standard grep */
                exit (2);
        }
        else
                ungetc (c, fp);

        for (i = 0; fgets (Pattern[i], MAXLINE, fp) != NULL; i++)
        {
                if (i >= 120)
                {
                        fprintf (stderr, "%s: Only %d strings allowed\n",
                                Program, MAXPATS);
                        exit (2);
                }
                j = strlen (Pattern[i]);
                if (Pattern[i][j - 1] == '\n')
                        Pattern[i][--j] = '\0';
        }
        Numpats = i - 1;

        fclose (fp);
}

/* setpats --- set up the patterns from a string */

void setpats (str)
register char *str;
{
        register WORD i, j;

        while (*str == '\n' || *str == '\r')
                str++;

        for (i = j = 0; *str; str++)
        {
                if (*str == '\n')
                {
                        Pattern[i][j] = '\0';
                        j = 0;
                        i++;
                }
                else
                        Pattern[i][j++] = *str;
        }
        Numpats = i;
}

/* begin magic stuff for Boyer-Moore pattern matching */

static void initialize ()
{
    WORD i, t, plc = Pat_length[Curpat];
    UBYTE *d1c = D1[Curpat], *d2c = D2[Curpat], *fc = F[Curpat];
    char *pc = Pattern[Curpat];

        for (i = 0; i < 128; i++)
                d1c[i] = plc;
        
        for (i = 0; i < plc; i++)
                d1c[((WORD)pc[i])&0x7F] = plc - i - 1;

        for (i = 0; i < plc; i++)
                d2c[i] = (plc << 1) - i - 1;
        
        for (i = (t = plc) - 1; i >= 0; i--, t--)
                for (fc[i] = t; t < plc && pc[i] != pc[t]; t = fc[t])
                        if (plc - i - 1 < d2c[t])
                                d2c[t] = plc - i - 1;

        for (i = 0; i <= t; i++)
                if (plc + t - i < d2c[i])
                        d2c[i] = plc + t - i;
}

/* match --- do Boyer-Moore pattern search on input buffer */

match ()
{
        register WORD i, j, plc = Pat_length[Curpat], tmp;
		register UBYTE *d1p, *d2p;
		register char *pp = Pattern[Curpat];

        if (Exact && plc != Line_length)
                return FALSE;

        i = plc - 1;

        while (i < Line_length)
        {
                j = plc - 1;
                while (j >= 0)
                {
                        if (Inbuf[i] == pp[j])
                                i--, j--;
                        else
                                break;
                }

                if (j < 0)
                {
                        /* found a match */
                        return TRUE;
                        /*
                         * note: if we were going to seach for further matches
                         * on the input line, we would do this:
                         *
                         * i += Pat_length[Curpat] + 1;
                         *
                         * which shifts right by Pat_length[Curpat] + 1 places
                         */
                }
                else
                {
						d1p = D1[Curpat];
						d2p = D2[Curpat];
						tmp = Inbuf[i] & 0x7F;
                        if( d1p[tmp] >= d2p[j])
                                j = d1p[tmp];
                        else
                                j = d2p[j];
                        i += j;
                        /* shift right by j places */
                }
        }

        return FALSE;
}

int filerror( name )
char *name;
{
	fprintf( stderr, "Can't open file %s\n", name);
}