/* qf - quickly find strings in files */

#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define MAX(a,b) ((a)>(b)?(a):(b))

size_t occ[UCHAR_MAX+1];
unsigned char *needle = NULL;
size_t nlen = 0;

/* basically ripped from wikipedia -- Boyer-Moore-Horspool */
const unsigned char *memmem_bmh (const unsigned char *haystack, size_t hlen) {
    size_t hpos, npos;

    /* sanitise */
    if (nlen > hlen || nlen <= 0 || !haystack || !needle) return NULL;

    /* search */
    hpos = nlen - 1;
    while (hpos < hlen) {
        npos = nlen - 1;
        while (haystack[hpos] == needle[npos]) {
            if (npos == 0) return haystack + hpos;
            hpos --;
            npos --;
        }
        /* skip ahead based on current unmatched byte */
        hpos += MAX (nlen - npos, occ[haystack[hpos]]);
    }
    return NULL;
}

int main (int argc, char **argv) {
    unsigned char *haystack, *result;
    char *filename;
    int i, j, fd, ret;
    struct stat sb;
    
    if (argc < 3) {
        printf ("Usage: %s search files...\n", argv[0]);   
        exit (2);
    }
    needle = (unsigned char*) argv[1];
    nlen = strlen ((char*) needle);

    /* preprocess needle */
    for (i=0; i<UCHAR_MAX+1; ++i) occ[i] = nlen;
    for (i=0, j=nlen; i<nlen; ++i) occ[needle[i]] = --j;

    /* search each file */
    for (i=2; i<argc; ++i) {
        filename = argv[i];

        fd = open (filename, O_RDONLY, 0);
        if (fd < 0) { perror (filename); continue; }
        
        ret = fstat (fd, &sb);
        if (ret < 0) { perror ("fstat"); exit (2); }

        haystack = (unsigned char*) mmap (0, sb.st_size, PROT_READ, 0, fd, 0);
        /* mmap is fucking weird -- returns -1 on error instead of NULL */
        if ((void*) haystack == (void*) -1) { perror ("mmap"); exit (2); }

        result = memmem_bmh (haystack, sb.st_size);

        if (result) {
            write (STDOUT_FILENO, filename, strlen (filename));
            write (STDOUT_FILENO, "\n", 1);
        }

        ret = munmap (haystack, sb.st_size);
        if (ret < 0) { perror ("munmap"); exit (2); }

        ret = close (fd);
        if (ret < 0) { perror ("close"); exit (2); }
    }
    return 0;
}