#include <stdint.h>
#include <fnmatch.h>
#include <stdio.h>
#include <string.h>
#define UINT uint32_t
#define UINTSIZE 4
typedef struct {	char tp;
} pattern;
typedef struct {	char tp;
	char chr;
} char_pattern;
typedef struct {	char tp;
	UINT chars;
} chars_pattern;
typedef struct {	char tp;
} qst_pattern;
typedef struct {	char tp;
	char chr;
	short sizerest;
} star_pattern;
typedef struct {	char tp;
} end_pattern;
typedef struct {	char tp;
} endstar_pattern;

enum PATTERNS {PATTERN_char,PATTERN_qst,PATTERN_star,PATTERN_chars,PATTERN_end,PATTERN_endstar};


#define NEXTPATTERN(type) pat->tp=PATTERN_##type;pat+=sizeof(type##_pattern);
pattern *makepattern(char *str){
  unsigned	char *s;
	pattern *pat,*ret;
	int canpack;int i,m;
	ret=pat=(pattern *) malloc(200);
	int rest=0;
	for (s=(unsigned char *)str;*s;s++) {
		if (*s!='*') rest++;
	}
	for (s=(unsigned char *)str;*s;s++) {
		switch(*s){
			case '*':
				while (*(s+1)=='?') {/* *?=?*  */
					NEXTPATTERN(qst)
					rest--;
					s++;
				}
				if (*(s+1)){
					((star_pattern*) pat)->sizerest=rest;
					((star_pattern*) pat)->chr=*(s+1);
					s++;
					NEXTPATTERN(star)
				}else{
					NEXTPATTERN(endstar)
				}
				break;
			case '?':
				NEXTPATTERN(qst)
				rest--;
				break;
			default:
				canpack=1;
				for (i=0;i<4;i++)
					if (*(s+i)=='*'||*(s+i)=='?') canpack=0;
				if (canpack){
					((chars_pattern*) pat)->chars=*((UINT*) s);
					rest-=UINTSIZE;
					s+=UINTSIZE-1;
					NEXTPATTERN(chars)
				}else{
				((char_pattern*) pat)->chr=*s;
				rest--;
				NEXTPATTERN(char)
				}
				break;
		}
			
	}
	NEXTPATTERN(end)
	return ret; 
}
#undef NEXTPATTERN
#define NEXTPATTERN(type) p+=sizeof(type##_pattern);
int fnmatch3(pattern *p,char *str,int len){
	char *s=str; int i,j; int sizerest,chars,chr;
	while (1){
		switch (p->tp){
			case PATTERN_char:
				if (*s != ((char_pattern*) p )->chr) return 1;
				NEXTPATTERN(char);
				s++;
			break;
			case PATTERN_chars:
				if ((* (UINT *)s)!=((chars_pattern*) p )->chars) return 1;
				s+=UINTSIZE;
				NEXTPATTERN(chars);
			break;
			case PATTERN_qst:
				s+=1;
				NEXTPATTERN(qst);
			break;
			case PATTERN_star:
				sizerest=((star_pattern*) p)->sizerest;
				chr=((star_pattern*) p)->chr;
				NEXTPATTERN(star);
				for (i=s-str;i<=len-sizerest ; i++ )
				{
					if (( *(str+i) == chr)
					 && !fnmatch3(p,str+i+1,len-i-1)) return 0;
				}
				return 1;
			break;
			case PATTERN_end:
				return *s;
			break;
			case PATTERN_endstar:
				return 0;
			break;
		}
	}
}
char buf[1000];
int fnmatch2(pattern *p, char *str,int flags){
	char *bu=buf;
	if (flags){
		while (*str) *bu++=tolower(*str++);
		str=buf;
	}
	return fnmatch3(p,str,strlen(str));
}
int main(){int i;
	char ptr[]="*abc*";
	pattern *p=makepattern(ptr);
	int cnt=0;
	char s1[]="abcda", s2[]="bbida",s3[]="nabcx";
	for (i=0;i<1000000;i++) {
		s1[1]++;s2[1]++;s3[1]++;
	int flags=1<<4;
#ifdef COMPARE
		cnt+=fnmatch(ptr,s1,flags)+fnmatch(ptr,s2,flags)+fnmatch(ptr,s3,flags);
#else
		cnt+=fnmatch2(p,s1,flags)+fnmatch2(p,s2,flags)+fnmatch2(p,s3,flags);
#endif
	}
	printf("%i",cnt);
}