/* search.c - Common functions used by all programs/modules
*
* (c) Tiago Alves Macambira, 2003
*
* $Id: search.c,v 1.2 2003/08/04 03:09:43 tmacam Exp $
*
* Parts of this code are base on the work of Brian "Beej" Hall
* See http://www.ecst.csuchico.edu/~beej/guide/net
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

#include "search.h"


#define ALPHABET_SIZE 256
#define ERROR	-1
#define NOT_FOUND ERROR
#define MAX_LINE_SIZE 1024
#define MAX_ERRORS 8			/* Numero máximo de erros permitidos*/
#define PROG_NAME "slave"

unsigned long int masklist[ALPHABET_SIZE];
size_t pattern_len;


void shiftand_preprocess_pattern(const unsigned char* pattern)
{
        int i = 0;

        pattern_len  = strlen(pattern);
        for (i = 0; i < ALPHABET_SIZE; i++){
                masklist[i] = 0;
        }
        for (i = 0; i < pattern_len; i++){
                masklist[pattern[i]] |= 1<< (pattern_len -1 - i);
        }

}


int shiftand_exato_find(const unsigned char* text, int bogus )
{
        int text_len = 0;
        int i = 0;              /* Posição do cursor  em texto */
        unsigned long int R = 0;/* O registrador... */
        unsigned long int initial_state = 0;    /* Guarda a mascara para o estad
o inicial */

        text_len = strlen(text);
        if (pattern_len > text_len){
                return ERROR;
        }

        initial_state = 1 << (pattern_len -1);

        while (i < text_len){
                R=((R>>1)|initial_state) & masklist[text[i]];
                if (R&1){
                        return i - (pattern_len - 1);
                }
                i++;
        }
        return NOT_FOUND;
}


int shiftand_aprox_find(const unsigned char* text, unsigned int k)
{
	int text_len = 0;
	int i = 0;		/* Posição do cursor  em texto */
	int j = 0;
	unsigned long int R[MAX_ERRORS+1];	/* Os registradores... */
	unsigned long int initial_state = 0;	/* Guarda a mascara para o estado inicial */
	unsigned long int Rold, Rnew;
	
        text_len = strlen(text);
        if (pattern_len > text_len){
		return ERROR;
	}

	if (k == 0){
		return shiftand_exato_find(text,0);
	} 
	
	initial_state = 1 << (pattern_len -1);

	/* Set-up registers */
	R[0] = 0x0;
	R[1] = 0x1 << (pattern_len -1);
	for (j = 2; j <= k; j++){
		R[j] = ( R[j-1] |(R[j-1]>>1));
	}
	
	/* A procura propriamente dita*/
	while (i < text_len){
		Rold = R[0];
		Rnew = ((Rold>>1)|initial_state) & masklist[text[i]];
		R[0] = Rnew;

		for (j = 1; j <= k ; j++){
			Rnew = (R[j]>>1 & masklist[text[i]])|Rold|((Rold|Rnew)>>1)|initial_state;
			Rold = R[j];
			R[j] = Rnew;
		}
		
		if (Rnew&1){
			return i;
		}
		i++; 
	}
	return NOT_FOUND;
}



unsigned long do_search_request(slave_request *request, int* erro)
{
	FILE *from = NULL;
        unsigned char line[MAX_LINE_SIZE];	
	unsigned long int matches_found;
	
	/* Inicialização */
	*erro=0;
	matches_found = 0;
	
	/* Abre arquivo para leitura */
	from = fopen(request->filename,"r");
        if (from == NULL) {
                fprintf (stderr,
                        "slave: Não pude abrir o arquivo '%s': %s\n",
                         request->filename, strerror (errno));
                goto oops;
        }

	/* Preprocessa o padrão */
        shiftand_preprocess_pattern(request->pattern);

	/* vamos procurar por ocorrências... */
        while(!feof(from)){
                if ( fgets (line,MAX_LINE_SIZE,from) == NULL ){
                        /* getline não é ANSI */
                        /*EOF ou erro*/
                        break;
                }

                if (shiftand_aprox_find(line,request->approx_k) >= 0 ){
			matches_found++;
                };
        }
        fclose(from);
	
	/* desaloca TUDO! */
	
	/* Retorna o resultado... */
	return matches_found;
	
oops:	/* Ah! Quem mandou C não ter excessões... */
	/* No mais, ta cheio disso no kernel do linux... */
	*erro = -1;
	return 0;
}