el muchacho Comfortably Numb |
Ouais, j'ai googlé, y'a même un petit programme en Java. Non, c'est pas ça
Tiens mange ça. J'ai enlevé une partie du commentaire d'en-tête, et je te laisse deviner ce que fait le programme.
Code :
- /*********************************************************/
- /* P. Grinspan - Tue.17th, Apr.2001 */
- /* with precious help from N.Janin */
- /*********************************************************/
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<ctype.h>
- #define MAX_FILE_SIZE (1<<20)
- #define ALPHA_SIZE (26)
- typedef unsigned long int LNG;
- char* reserved[33]={"auto","break","case","char","const","continue",
- "default","do","double","else","enum","extern","float","for","goto","if",
- "int","long","register","return","short","signed","sizeof","static",
- "struct","switch","typedef","union","unsigned","void","volatile","while",""};
- const char codes[33]="aBchkCdDbLNxfFGIilrRhgZtTSyUuvVW";
- typedef struct Group_
- { /* (starts with all of them, then refined into subgroups) */
- char label; /* Sieving character last used for this group */
- LNG counter; /* # of members; actually 0 if only 1 turned up so far */
- struct Group_* next; /* This pointer has 2 different uses (see below) */
- struct PosNode_* members; /* List of members - filled in only at the end */
- } Group;
- typedef struct PosNode_
- {
- LNG position,line;
- Group* group; /* Points to this block's group */
- struct PosNode_* next; /* 2 different uses (see below) */
- int original; /* Is the node still at its original place in the list ? */
- } PosNode;
- typedef struct state_
- {
- char spotted; /* Code of word ending at this state */
- struct state_* next[ALPHA_SIZE];
- } state;
- void* Alloc(int size)
- {
- void* p;
- if(p=malloc(size)) return p; else
- {
- printf("Out of memory !?\n" );
- exit(1);
- }
- }
- char* Translate(char c,int crunch)
- {
- static int bra=0;
- int i=0;
- char* str=Alloc(12*sizeof(char));
- if(crunch)
- if(isalpha(c))
- {
- do str=reserved[i]; while(codes[i++]!=c);
- return str;
- }
- else switch(c)
- {
- case'_': return "(id)";
- case'0': return "(num)";
- default: break;
- }
- *str=c;
- switch(c)
- {
- case'#': return "#(Preproc.)\n";
- case'\'': return "\'(char)\'";
- case'\"': return "\"(str)\"";
- case'{': ++bra; break;
- case'}': if(bra) --bra; break;
- case';': break;
- default: str[1]='\0'; return str;
- }
- str[1]='\n';
- i=1;
- while(i<=bra) str[++i]='\t';
- str[++i]='\0';
- return str;
- }
- /* Builds an automaton for string matching */
- state* FSA(void)
- {
- int j,i;
- char c;
- const char* code;
- state** current,* root=NULL;
- const char** str=reserved;
- code=codes;
- while((*str)!="" )
- {
- current=&root;
- i=0;
- do
- {
- if(!*current)
- {
- *current=Alloc(sizeof(state));
- (*current)->spotted='_';
- for(j=0;j<ALPHA_SIZE;++j) (*current)->next[j]=NULL;
- }
- if((c=(*str)[i++])=='\0') (*current)->spotted=*code;
- else current=&((*current)->next[c-'a']);
- } while(c!='\0');
- ++str;
- ++code;
- }
- return root;
- }
- char Scan(state* current,FILE* sample,int* c)
- {
- int goon=1;
- do
- if(goon)
- if(*c>'z'||*c<'a'||!(current=current->next[*c-'a'])) goon=0;
- while((*c=fgetc(sample))=='_'||isalnum(*c));
- return ((goon)?current->spotted:'_');
- }
- int ReadNext(FILE* file, LNG* line)
- {
- int c=fgetc(file);
- if(c=='\n') ++(*line);
- return c;
- }
- /* Copies the whole file into a string */
- /* and initializes the list of "interesting" blocks to contain all of them */
- char* Init(FILE* file,PosNode* root,int crunch)
- {
- PosNode* current;
- state* automat;
- LNG i=0,l=1;
- int c,c1;
- int comment,out,gotit,end,par=0,blank=crunch;
- char* s=Alloc(MAX_FILE_SIZE*sizeof(char));
- root->next=NULL;
- current=root;
- c=ReadNext(file,&l);
- automat=FSA();
- end=1;
- while(c!=EOF)
- {
- comment=gotit=0;
- if(c=='/')
- if((c1=fgetc(file))=='*')
- {
- comment=1;
- c=ReadNext(file,&l);
- do
- {
- out=1;
- if(c!='*') out=0;
- if((c=ReadNext(file,&l))!='/') out=0;
- } while(!out);
- } else gotit=1;
- if(isspace(c)) c=' ';
- if(c=='(') ++par;
- if(c==')') --par;
- if(crunch&&(c=='_'||isalpha(c)))
- {
- c1=c;
- c=Scan(automat,file,&c1);
- gotit=1;
- }
- if(crunch&&isdigit(c))
- {
- c='0';
- while(isdigit(c1=fgetc(file))) ;
- gotit=1;
- }
- if(crunch&&c=='#') do c1=ReadNext(file,&l); while(c1!='\n');
- if(strchr("\'\"",c))
- do
- {
- c1=ReadNext(file,&l);
- while(c1=='\\')
- {
- ReadNext(file,&l);
- c1=ReadNext(file,&l);
- }
- } while(c1!=c);
- if(!(comment||((blank||end)&&c==' ')))
- {
- if(end&&!par&&!strchr(" ;{}",c))
- {
- current=current->next=Alloc(sizeof(PosNode));
- current->group=NULL;
- current->line=l;
- current->position=i;
- current->original=1;
- }
- s[i++]=(char)c;
- if(i==MAX_FILE_SIZE) return NULL;
- }
- if(!(comment||crunch)) if(c==' ') blank=1; else blank=0;
- if(strchr("{:;}",c)) end=1; else if(c!=' ') end=0;
- if(gotit)
- {
- if((c=c1)=='\n') ++l;
- }
- else c=ReadNext(file,&l);
- }
- current->next=NULL;
- s[i]='\0';
- return s;
- }
- /* Deletes a "position" node and returns its follower */
- PosNode* DelPos(PosNode* junk)
- {
- PosNode* next=junk->next;
- free(junk->group);
- free(junk);
- if(next) next->original=0;
- return next;
- }
- /* Removes "blocks" beyond the end of file, */
- /* and attaches the rest to "generic" group to start with */
- void Sow(PosNode* root,signed long int i)
- {
- PosNode* next;
- Group* all;
- all=Alloc(sizeof(Group));
- all->counter=0;
- all->next=NULL;
- all->members=NULL;
- while(next=root->next)
- {
- if(i--<0) root->next=DelPos(next);
- else
- {
- next->group=all;
- ++(all->counter);
- root=next;
- }
- }
- }
- /* Attaches the node to the subgroup of *p_group */
- void Update(Group** p_group,char c)
- { /* corresponding to label c */
- Group* current,* next;
- /* First, find whether that subgroup already exists
- in the list starting at *p_group->next: */
- current=*p_group;
- while((next=current->next)&&(next->label<c)) current=next;
- if((next)&&(next->label==c)) /* if it does, adjust its counter */
- {
- if(!(next->counter)) next->counter=1;
- ++(next->counter);
- }
- else /* if not, create it */
- {
- ((Group*)current->next=Alloc(sizeof(Group)))->next=next;
- next=current->next;
- next->label=c;
- next->counter=0;
- next->members=NULL;
- }
- current=*p_group;
- *p_group=next; /* (now the node belongs to the subgroup) */
- if(!(--(current->counter))) /* Decrease "overgroup" counter; if all members dispatched */
- { /* then delete it AND unbind its subgroups */
- next=current->next;
- free(current);
- do
- {
- current=next;
- next=current->next;
- current->next=NULL;
- } while(next);
- }
- }
- void Sieve(char* digest,PosNode* root)
- {
- PosNode* current,** p_next;
- Group** p_group;
- current=root;
- while(current->next) /* For all nodes left in the list, */
- {
- p_next=&(current->next);
- p_group=&((*p_next)->group);
- if((*p_group)->counter) /* IF the group has >1 member, update node membership */
- Update(p_group,digest[(current=*p_next)->position]);
- else
- *p_next=DelPos(*p_next); /* else delete node AND its lonely 'group' */
- }
- }
- /* Collect & restructure information about final groups */
- Group* Reap(PosNode* current)
- {
- PosNode* next,** p_mem;
- Group* group,* G_root,** p_head;
- G_root=NULL;
- p_head=&G_root;
- while(current)
- {
- group=current->group;
- next=current->next;
- if(group->counter) /* IF >1 member, */
- {
- current->next=NULL;
- p_mem=&(group->members);
- while(*p_mem) p_mem=&((*p_mem)->next);
- *p_mem=current; /* add the node to member list */
- if(!(--(group->counter))) /* if the group is complete, add it to the list */
- {
- *p_head=group;
- p_head=&(group->next);
- }
- } else DelPos(current);
- current=next;
- }
- return G_root;
- }
- int main(int argc, char* argv[])
- {
- LNG size,real,step,offset;
- int isnew,crunch,same;
- char* digest,* p,c;
- PosNode* root,* member,* previous;
- Group* G_root;
- FILE* in_file;
- FILE* out_file;
- char* prog_name=(*argv);
- crunch=0;
- while(argc>1 && (*(++argv))[0]=='-')
- {
- --argc;
- p=(*argv);
- while(*(++p)) switch(*p)
- {
- case'c': crunch=1; break;
- default: printf("Sorry, option -%c not recognized\n",*p); break;
- }
- }
- if (argc<3)
- {
- printf("Not enough arguments !\n" );
- printf("Usage is %s [options] <window_size> <infilename> [<outfilename>]\n",prog_name);
- exit(1);
- }
- size=atoi(*(argv++));
- if((in_file=fopen(argv[0],"r" ))==NULL)
- {
- printf("Unable to open file %s for reading\n",argv[0]);
- exit(1);
- }
- out_file=stdout;
- if(argc>3) if(!(out_file=fopen(argv[1],"w" )))
- printf("Unable to open file %s for writing\n",argv[1]);
- root=Alloc(sizeof(PosNode));
- if(!(digest=Init(in_file,root,crunch)))
- {
- printf("File %s too big\n",argv[0]);
- exit(1);
- }
- root->next->original=0;
- Sow(root,strlen(digest)-size);
- /* fprintf(out_file,"%s\n\n",digest); */
- step=1; /* Within blocks look at positions in non-sequential order to remove coherence */
- while(step<=size) step<<=1;
- do
- {
- offset=step>>1;
- do Sieve(digest+offset-1,root); while((offset+=step)<=size);
- step>>=1;
- } while(!(step%2));
- G_root=Reap(root->next);
- previous=NULL;
- while(G_root)
- {
- member=G_root->members;
- isnew=0;
- while(member)
- {
- isnew|=!member->original;
- member=member->next;
- }
- member=G_root->members;
- if(!isnew)
- {
- G_root=G_root->next;
- continue;
- }
- same=1;
- real=size;
- while(same)
- {
- c=digest[(member=G_root->members)->position+real];
- while(member=member->next) if(c!=digest[member->position+real]) same=0;
- if(same) ++real;
- }
- member=G_root->members;
- fprintf(out_file,"-> Repetition of following (%d symbols altogether):\n",real);
- p=digest+member->position;
- do fprintf(out_file,"%s",Translate(*(p++),crunch));
- while(p<digest+member->position+real);
- fprintf(out_file,"\ndetected on lines:\n" );
- while(member)
- {
- fprintf(out_file,"%d\n",member->line);
- member=member->next;
- }
- fprintf(out_file,"\n" );
- G_root=G_root->next;
- }
- fclose(in_file);
- fclose(out_file);
- }
|
Message édité par el muchacho le 07-11-2005 à 19:55:50 ---------------
Les aéroports où il fait bon attendre, voila un topic qu'il est bien
|