// // // This program was written by Sang Cho, associate professor at // the department of // computer science and engineering // chongju university // language used: gcc // // date of second release: August 30, 1998 (alpha version) // many fixed after release: October 9, 1998 // // // you can contact me: e-mail address: sangcho@alpha94.chongju.ac.kr // hitel id: chokhas // phone number: (0431) 229-8491 +82-431-229-8491 // // real address: Sang Cho // Computer and Information Engineering // ChongJu University // NaeDok-Dong 36 // ChongJu 360-764 // South Korea // // Copyright (C) 1997,1998,1999 by Sang Cho. // // Permission is granted to make and distribute verbatim copies of this // program provided the copyright notice and this permission notice are // preserved on all copies. // // File: main.c # include "disasm.h" #define INT_MAX 0x7FFFFFFF #define jLmax 50000 #define hMax 5120 #define hintMax 1024 #define NAMEMAX 256 #define COLSIZE 78 //FILE *d_fp; int nextMode=0; // some role in preprocessing int printMode=0; int zeroCheckMode=0; int lineno=0; int errorCount=0; int debugx=0; int debugTab[256]={0,}; char mname[NAMEMAX]; int fsize; int showDotsNum=0; DWORD debugAdd=0; DWORD debugAdd1=0; int jLc; _labels pArray[jLmax]; _labels suspicious[hMax]; // I am lazy so i will use _labes to store suspicious places... int dmc=0; DWORD dmLabels[32]; int HintCnt=0; _key_ Hints[hintMax]; // I am lazy so i will use _key_ structure to store hints... int hCnt=0; history History[hMax]; int needJump=0; DWORD needJumpNext; int needCall=0; DWORD needCallRef, needCallNext; DWORD fatalPosition; DWORD fatalReference; // ********************************************************* // ****************** main here **************************** // ********************************************************* int main(argc,argv) int argc; char **argv; { FILE *my_fp; //extern FILE *d_fp; int i, n; DWORD r; char fname[NAMEMAX]; if (argc == 2) { strcpy(fname, argv[1]); my_fp = fopen (argv[1], "rb"); if (my_fp == NULL) { fprintf (stderr,"canNOTopenFILE: %s", argv[1]); exit (0); } } else if (argc == 3) { strcpy(fname, argv[1]); strcpy(mname, argv[2]); my_fp = fopen (argv[1], "rb"); if (my_fp == NULL) { fprintf (stderr,"canNOTopenFILE: %s", argv[1]); exit (0); } readHint(); } else { fprintf (stderr,"\nusage: dis input_file_name > output_file_name"); fprintf (stderr,"\nversion 0.23 released September 12, 2001\n"); exit (0); } //d_fp = fopen ("xxxxxx.xxx", "w"); //if (d_fp == NULL) //{ // fprintf (stderr,"canNOTopenFILE: %s", "xxxxxx.xxx"); // exit (0); //} fseek (my_fp, 0L, SEEK_END); fsize = ftell (my_fp); rewind (my_fp); lpFile = (void *) calloc (fsize,1); if (lpFile == NULL) { fprintf (stderr,"canNOTallocateMEMORY"); exit (0); } printf ("Disassembly of File: %s\n\n", argv[1]); n = fread (lpFile, fsize, 1, my_fp); if (n == -1) { fprintf(stderr,"failed to read the FILE"); exit (0); } // I need to connect pedump and preprocessing. initHeaders(); pedump (argc, argv); /* put together */ //Myfinish(); tryAnyAddress(); tryPascalStrings(); //Myfinish(); printf ("\n"); //printf ("\n*************** BEGINNING OF PROCESSING ************************** \n"); fprintf (stderr,"\n*************** PREPROCESSING BEGINS ************************** \n"); showDotsNum=0; //fprintf(stderr,"entryPoint=%08X imageBase=%08X imagebaseRVA=%08X CodeOffset=%08X\n", // (int)entryPoint, (int)imageBase, (int)imagebaseRVA, CodeOffset); //fprintf(stderr,"CodeSize=%08X",CodeSize); if (entryPoint>0) resetDisassembler(imageBase+entryPoint); else resetDisassembler(imagebaseRVA); orMap(imageBase+entryPoint,0x40); EnterLabel(2048, imageBase+entryPoint, imageBase); nextMode = 1; // to say now preprocessing is started. zeroCheckMode=1; printMode = 0; //printMode= 1; while (1) { debugx=0; /*-------------*/pushTrace(1000); Disassembler(); /*-------------*/popTrace(); if (fatalError) ErrorRecover(); // I have to make sure there is no looping. // in a micro level or macro level. think BIG.... be happy.... october 27,1997 /*-------------*/pushTrace(1010); r=GetNextOne(); /*-------------*/popTrace(); /*-------------*/pushTrace(1020); resetDisassembler(r); /*-------------*/popTrace(); if (r==0) break; } if (debugAdd>0) MapSummary(); //ReportMap(); //Myfinish(); /*-----------------*/pushTrace(1030); PostProcessing1(); /*-----------------*/popTrace(); //printf ("\n*************** END OF PREPROCESSING **************************** "); if (fatalError) { //printf("\nError=%d",fatalError); fatalError=0; } if (debugAdd>0) { printf ("\n\n*************** LABELS COLLECTED ARE: source side ******************** "); printf ("\n"); sortTrees1(); printf ("\n\n*************** LABELS COLLECTED ARE: destination ******************** "); printf ("\n"); sortTrees(); } /*-----------------*/pushTrace(1040); LabelProcess(); /*-----------------*/popTrace(); //ReportMap(); //Myfinish();exit(0); printf ("\n\n+++++++++++++++++++ ASSEMBLY CODE LISTING +++++++++++++++++++"); printf ("\n//********************** Start of Code in Object CODE **************"); printf ("\nProgram Entry Point = %08X (%s File Offset:%08X)\n", (int)(imageBase+entryPoint),argv[1],CodeOffset); fprintf (stderr,"\n\n*************** LISTING BEGINS *************************** \n"); showDotsNum=0; nextMode = 0; // to say now preporcessing is finished. zeroCheckMode=0; printMode=1; resetDisassembler(imagebaseRVA); while (!GotEof) { debugx=0; /*-------------*/pushTrace(1050); Disassembler(); /*-------------*/popTrace(); if(GotEof) break; if(getOffset(cur_position)0) fprintf (stderr, "\naddL=%5d reset=%5d ErrorR=%5d eraseU=%5d totalZero=%08X", addLabelsNum, resetNum, ErrorRecoverNum, eraseUncertainNum,totZero); if (debugAdd>0) reportHistory(); printf ("\n*************** END OF LISTING ********************************** \n"); fprintf(stderr,"\n"); Myfinish(); return 1; } // ********************************************************************** // **************************end of main ******************************** // ********************************************************************** // // all the functions used in the main // // ************************************** // disassembler block starts here // ************************************** void initDisassembler() { yyfirsttime = 1; // to refresh position from the file a_loc = 0; a_loc_save = 0; i_col = 0; i_col_save = 0; i_psp = 0; GotEof =0; lineno=0; NumberOfBytesProcessed = -1; operandOveride = 0; addressOveride = 0; dmc = 0; fatalError = 0; needJump=0; needCall=0; needCallRef=0; needCallNext=0; needJumpNext=0; } int resetNum=0; DWORD lastReset=0; int resetHistogram[256]={0,}; void resetDisassembler(DWORD ref) { //int i; initDisassembler(); vCodeOffset = getOffset(ref); vCodeSize = CodeOffset-vCodeOffset+CodeSize; delta = vCodeOffset - CodeOffset; lastReset = ref; cur_position = ref; // mark start position here. /*----------*/pushTrace(1060); if (nextMode) orMap(ref, 0x20); /*----------*/popTrace(); //printf("\nresetDisassembler :%08X getByte=%02X",ref,getByteFile(ref)); //if(nextMode) //fprintf(stderr,"\nresetDisassembler :%08X getByte=%02X",ref,getByteFile(ref)); resetHistogram[getByteFile(ref)]+=1; resetNum++; } int envSave[32]; void pushEnvironment() { envSave[ 0]=yyfirsttime; envSave[ 1]=a_loc; envSave[ 2]=a_loc_save; envSave[ 3]=i_col; envSave[ 4]=i_col_save; envSave[ 5]=i_psp; envSave[ 6]=NumberOfBytesProcessed; envSave[ 7]=operandOveride; envSave[ 8]=addressOveride; envSave[ 9]=vCodeOffset; envSave[10]=vCodeSize; envSave[11]=dmc; envSave[12]=delta; envSave[13]=(int)cur_position; envSave[14]=needJump; envSave[15]=needCall; envSave[16]=GotEof; envSave[17]=(int)yyfp; envSave[18]=(int)yypmax; envSave[19]=nextMode; envSave[20]=printMode; envSave[21]=zeroCheckMode; envSave[22]=needJumpNext; } void popEnvironment() { yyfirsttime = envSave[ 0]; a_loc = envSave[ 1]; a_loc_save = envSave[ 2]; i_col = envSave[ 3]; i_col_save = envSave[ 4]; i_psp = envSave[ 5]; NumberOfBytesProcessed = envSave[ 6]; operandOveride = envSave[ 7]; addressOveride = envSave[ 8]; vCodeOffset = envSave[ 9]; vCodeSize = envSave[10]; dmc = envSave[11]; delta = envSave[12]; cur_position = (DWORD)envSave[13]; needJump = envSave[14]; needCall = envSave[15]; GotEof = envSave[16]; yyfp = (PBYTE)envSave[17]; yypmax = (PBYTE)envSave[18]; nextMode = envSave[19]; printMode = envSave[20]; zeroCheckMode = envSave[21]; needJumpNext = envSave[22]; } void showDots() { static int n=0; n++; if (n%20==0) { fprintf(stderr,"."); showDotsNum++; if (showDotsNum%COLSIZE==0) fprintf(stderr,"\n"); } } // // the engine of this program // void Disassembler() { //static BYTE bb=0x00; int tok; BYTE c; int choice; //int i; showDots(); while (!GotEof) { /*-----------*/pushTrace(1100); addressfix(); /*-----------*/popTrace(); c = getMap(cur_position); if (nextMode) { if (c==0x0E) {fatalError=256;break;} else if ((c&0x08)==0x08){needJump=1; break;} else if ((c&0x05)==0x05){needJump=1; break;} choice=0; } else { if ((c&0x0F)==0x0E) choice=1; // address else if ((c&0x0F)==0x0D) choice=6; // ward else if ((c&0x0F)==0x0F) choice=2; // byte data else if ((c&0x0F)==0x0C) choice=3; // CC block else if ((c&0x0F)==0x0B) choice=4; // Pascal String else if ((c&0x0F)==0x09) choice=5; // NULL String else choice=0; } /*------------*/pushTrace(1110); addressprint1(choice); /*------------*/popTrace(); /*------------*/pushTrace(1120); tok = instruction(choice); /*------------*/popTrace(); if (tok==0) {fatalError=-1; break;} /*------------*/pushTrace(1130); bodyprint(choice); /*------------*/popTrace(); lineno++; /*------------*/pushTrace(1140); markCodes(); /*------------*/popTrace(); if (nextMode&&needJump)break; //if (nextMode&&needCall)break; /*------------*/pushTrace(1150); if (zeroCheckMode) {checkZeros(); checkCrossing();} /*------------*/popTrace(); if (fatalError) break; } /* go round the loop */ } void Disassembler1() { //static int bb=0; int tok; BYTE c; int i, limit; if (nextMode) limit=CodeSize; else limit=48; for(i=0;i0) clearSomeBadGuy(&my_h); /*------------*/popTrace(); } else if (fatalError!=0) { //for(i=cur_position-2;i0) clearSomeBadGuy(&my_h); /*------------*/popTrace(); ErrorRecoverNum++; dmc=0; fatalError=0; } void clearSomeBadGuy(PHISTORY ph) { int i; //fprintf(stderr,"\n Clear Some Bad Guy "); for (i=0;ic_pos; if (isGoodAddress(r)&&(r0 && ref==needJumpNext) { r=ref; while((b=getByteFile(r))==0x00 && getMap(r)==0x00) {setMap(r++,0x0F);} i = getIntFile(r); if (i==-1) { setMap(r,0x0F); setMap(r+1,0x0F); setMap(r+2,0x0F); setMap(r+3,0x0F); } } b = getByteFile(ref); if (b==0) return 0; //if (ref==debugAdd)fprintf(stderr,"\nisItstartAnyWay=%08X %02X",ref,getMap(ref)),getch(); if (strchr(CodeTab,b)==NULL) return 0; if (getMap(ref)&0x0F) return 0; //if (ref==debugAdd){fprintf(stderr,"\nisItstartAnyWay=%08X 2",ref);getch();} pushEnvironment(); nextMode=0; zeroCheckMode=1; //printMode=0; resetDisassembler(ref); /*-----------*/pushTrace(1600); for(i=0;i<48;i++) { addressfix(); c = getMap(cur_position); b = getByteFile(cur_position); if (b==0x00) { for(r=ref;r=cur_position-1) {fatalError=-9; break;} } if ((c&0x08)==0x08) break; else if ((c&0x05)==0x05) break; addressprint1(0); tok = instruction(0); if (tok==0) {fatalError=-11; break;} bodyprint(0); for(j=1;j127) r-=256; r+=cur_position+2; if ((getMap(r)&0x05)==0x05) { for(t=r;t 0) { if ((getMap(i+0)==0x00) &&(getMap(i+1)==0x00) &&(getMap(i+2)==0x00) &&(getMap(i+3)==0x00)) { /*---------*/pushTrace(1700); EnterLabel(166, rr,i); /*---------*/popTrace(); } } else break; } } void tryAnyAddress() { //static int col=0; DWORD r, rmax; DWORD rmaxTab[32], rstartTab[32]; int i, j, k, n, num, c; DWORD s, e, ss; BYTE b, d; fprintf(stderr,"."); showDotsNum++; if (showDotsNum%COLSIZE==0) fprintf(stderr,"\n"); num=nSections; if (num>32) {num=32; fprintf(stderr,"\n...please increase the size...");} j=0; for (i=0;i 0) { if (AddressCheck(getIntFile(r+1)) > 0 ||AddressCheck(getIntFile(r+2)) > 0 ||AddressCheck(getIntFile(r+3)) > 0) { r++; } else { //fprintf(stderr,"\nsetAnyAddress=%08X %08X",r,getIntFile(r)); //getch(); setAnyAddress(r); r+=4; } } else { r++; } } } fprintf(stderr,"."); showDotsNum++; if (showDotsNum%COLSIZE==0) fprintf(stderr,"\n"); for(k=0;k12) return (i-r)/4; r++; } } int looksLikeMenus(DWORD ref) { DWORD i, n; for (i=ref;in-12;i--) if (getIntFile(i)==-1) break; if (i==n-12) return 0; return 1; } void showPascalString(DWORD ref) { DWORD i; int n; n = getByteFile(ref); orMap1(ref,0x07); //fprintf(stderr,"\n:%08X..pascalString..",ref); printf("\n:%08X..pascalString..",(int)ref); //for (i=ref+1;i");} else if (getByteFile(i)==0x0A) { orMap1(i,0x04); printf(" "); if (getByteFile(i+1)==0x0A) {orMap1(i+1,0x04); printf(" ");} else if (getByteFile(i+1)==0x00) {orMap1(i+1,0x04);} } else if (getByteFile(i)==0x09) { orMap1(i,0x04); printf(" "); if (getByteFile(i+1)==0x09) {orMap1(i+1,0x04); printf(" ");} else if (getByteFile(i+1)==0x00) {orMap1(i+1,0x04);} } if (getByteFile(i)==0x00) {orMap1(i,0x04);} } void markStrings(DWORD s, DWORD e) { DWORD i; BYTE b, d; /*-------------*/pushTrace(1800); i=s; while(i32) {num=32; fprintf(stderr,"\n...please increase the size...");} j=0; for (i=0;i4 || (n>2 && r8))) {showPascalString(r-1); r=r+n; l=r;} else if (c>4 && ( b==0x00 || (b==0x0A && ((d=getByteFile(i+1))==0x0A || isprint(d) || d==0x00)) || (b==0x0D && ((d=getByteFile(i+1))==0x0A)) || (b==0x09 && ((d=getByteFile(i+1))==0x09 || d==0x00)) ) ) { if(c>5||!touchAnyAddress(i-1)||looksLikeMenus(i-1)) showNullString(r); while (getMap1(i)==0x04) i++; if(getByteFile(i)==0x00) i++; r=i; l=r; } else r++; } } } void checkOneInstructionFiller(DWORD r) { /*--------------*/pushTrace(1900); if (getMap(r)==0 && getMap(r+1)==0 && getMap(r+2)!=0 && getByteFile(r)==0x8B && getByteFile(r+1)==0xC0) {setMap(r,0x05); setMap(r+1,0x04);} /*--------------*/popTrace(); return; } void changeToAddress(DWORD s, DWORD e) { } void changeToBytes(DWORD s, DWORD e) { DWORD i; for (i=s;is && (e-s)%10==0) { for(i=s;in*2)||(nz*2>n)||(n==1&&isNotGoodJump(rs))|| (n<16 &&(cBox[0xC2]+cBox[0xC3]==0) &&(getByteFile(ri)!=0xE9) &&(getByteFile(ri)!=0xE8) &&(getByteFile(ri)!=0xFF))) { // try to save partial results r=rs; while(rs && ((b=getMap(r))&0x80)==0x00 && !(b&0x40)){r--;} if(((b=getMap(r))&0x40)||(b&0x0C)==0x0C){r=re;continue;} r++; while(r 0x08 .. check it.. /*------------*/pushTrace(1960); setMap(r, 0x0F); r++; /*------------*/popTrace(); } } } // now for some real final touch,, nov.10,1997 -sangcho- // namely clear some garbage code which clings hard to byte data //fprintf(stderr, " p3"); fprintf(stderr,"."); showDotsNum++; if (showDotsNum%COLSIZE==0) fprintf(stderr,"\n"); r=s; while(rn)||(n==1&&isNotGoodJump(rs))) { r=rs; while(r0)nn++; r++; } if(nn){r=re;continue;} r=rs; /*--------------*/pushTrace(1980); while(r16) {num=16; fprintf(stderr,"\n...please increase the size...");} for (i=0;i0) { /*-------------*/pushTrace(2120); setMap(i ,0x0E); setMap(i+1,0x0E); setMap(i+2,0x0E); setMap(i+3,0x0E); /*-------------*/popTrace(); /*-------------*/pushTrace(2130); MyBtreeInsertDual(167, getIntFile(i), i); /*-------------*/popTrace(); for (i=s;i0) r++; s=r; while(rrmax) return 1; q=toFile(ref); switch(c) { case 512: case 513: case 520: case 1024: n=q?strlen(q):0; qq=q; if(n>0) while(qq0) while(qq0&&qq==q+n)||(getMap1(ref)&0x05)==0x05) { if (getMap(pos)==0) break; /*----------*/pushTrace(2300); if (getMap(pos)&0x05) orMap(pos, 0x10); /*----------*/popTrace(); } default: break; } return 1; } void labelBody1(int class, DWORD ref, DWORD pos) { int c; DWORD r, rr; BYTE b, bb; c = class; r = ref; rr= pos; //if (r==0x0100139C) fprintf(stderr,"\nTADA...TADA...c=%3d rr=%08X mr=%02X mrr=%02X", // c,rr,getMap(r),getMap(rr)); if (CodeOffset+CodeSize<=getOffset(r)) {stringCheck(c, r, rr); return;} b=getMap(r); if (b==0) return; if ((b&0x05)!=0x05 && (b&0x08)==0) return; bb=getMap(rr); if ((b==0x0F)&&(bb==0x0F)) return; switch(c) { case 1: case 2: if (bb==0) break; if (b==0x0F) break; if ((b&0x20)&&(bb&0x05)==0x05) break; /*-----------*/pushTrace(2310); if (bb&0x05) orMap(r, 0x20); /*-----------*/popTrace(); break; case 3: case 4: if (bb==0) break; if (b==0x0F) break; if (b==0x0F) break; if ((b&0x20)&&(bb&0x05)==0x05) break; /*-----------*/pushTrace(2320); if (bb&0x05) orMap(r, 0x20); /*-----------*/popTrace(); break; case 5: case 7: case 9: if (bb==0) break; if (b==0x0F) break; if ((b&0x20)&&(bb&0x05)==0x05) break; /*-----------*/pushTrace(2330); if (bb&0x05) orMap(r, 0x20); /*-----------*/popTrace(); break; case 11: case 13: case 15: case 17: if (bb==0) break; if (b==0x0F) break; if ((b&0x40)&&(bb&0x05)==0x05) break; /*-----------*/pushTrace(2340); if (bb&0x05) orMap(r, 0x60); /*-----------*/popTrace(); break; case 133: break; case 165: case 166: case 167: if (bb==0) break; if ((b&0x20)&&(bb&0x0E)==0x0E) break; /*-----------*/pushTrace(2350); if ((bb&0x0E)==0x0E) orMap(r, 0x20); /*-----------*/popTrace(); break; case 514: if (bb==0) break; if (b!=0x0E) break; /*-----------*/pushTrace(2360); orMap(r, 0x20); /*-----------*/popTrace(); break; case 516: if (bb==0) break; if (b!=0x0D) break; /*-----------*/pushTrace(2370); orMap(r, 0x20); /*-----------*/popTrace(); break; case 515: case 517: case 518: case 519: case 520: case 524: case 528: if (bb==0) break; if (b!=0x0F) break; /*-----------*/pushTrace(2372); orMap(r, 0x20); /*-----------*/popTrace(); break; case 512: case 513: case 1024: if (bb==0) break; if ((b&0x08)==0x08) {stringCheck(c, r, rr); break;} if ((b&0x05)==0x05) orMap(r,0x20); break; case 2048: /*-----------*/pushTrace(2380); orMap(r, 0xE0); /*-----------*/popTrace(); break; default: break; } } void labelPP(PNODE1 pn, DWORD pos1) { if (pn==NULL) return; labelPP(pn->left, pos1); labelBody1(pn->rclass, pos1, pn->pos2); labelPP(pn->right, pos1); } void labelBody(PNODE pn) { PNODE1 pc; if (pn->rcount>1) { pc=(PNODE1)(pn->pos2); labelPP(pc, pn->pos1); } else if (pn->rcount==1) labelBody1(pn->rclass, pn->pos1, pn->pos2); } void labelP(PNODE pn) { if (pn==NULL) return; labelP(pn->left); labelBody(pn); labelP(pn->right); } void LabelProcess() { int i, k; DWORD r, rmax; BYTE b; PNODE *ppn; _key_ y; // I need to recycle one bit of Map,.... november 16,1997 -sangcho- r=imagebaseRVA; rmax=imageBase+getRVA(CodeOffset+CodeSize-1)+1; /*----------*/pushTrace(2400); while(rimagebaseRVA) {printf("\n %08X,",(int)rr);col=1;} else col=7; } else if (b&0x40) { if (rr>0)printf("\n==%08X::%08X,",(int)r,(int)rr); else printf("\n==%08X::",(int)r); col=1; } else if (5130)printf("\n##%08X::%08X,",(int)r,(int)rr); else printf("\n##%08X::",(int)r); col=1; } else if (b&0x20) { if (rr>0)printf("\n--%08X::%08X,",(int)r,(int)rr); else printf("\n--%08X::",(int)r); col=1; } } else { if (col%7==0) printf("\n %08X,",(int)rr); else printf("%08X,",(int)rr); col++; } sr=r; } void xrefPP(PNODE1 pn, DWORD pos1) { if (pn==NULL) return; xrefPP(pn->left, pos1); xrefBody1(pn->rclass, pos1, pn->pos2); xrefPP(pn->right, pos1); } void xrefBody(PNODE pn) { PNODE1 pc; if (pn->rcount>1) { pc=(PNODE1)(pn->pos2); xrefPP(pc, pn->pos1); } else if (pn->rcount==1) xrefBody1(pn->rclass, pn->pos1, pn->pos2); } void xrefP(PNODE pn) { if (pn==NULL) return; xrefP(pn->left); xrefBody(pn); xrefP(pn->right); } void Xreference() { int i; PNODE *ppn; printf("\n\n*************** Cross Reference Listing ****************"); for (i=0; i>> THIS SHOULD'NT HAPPEN <<< fatalError=%3d :%08X ", // fatalError, cur_position);getch(); //} rmax=imageBase+getRVA(CodeOffset+CodeSize-1)+1; if (ref>imagebaseRVA) for (r=ref-1;r>imagebaseRVA;r--) { if (((b=getMap(r))==0x00)||(b&0x88)) break; //fprintf(stderr, "b=%02X ",b); } //fprintf(stderr, "b=%02X ",b); // start position to erase s = r+1; if ((b=getMap(r))==0 || (b&0x88))s=r+1; else s=r; //fprintf(stderr, "\ns==%08X ",s); r=ref; if (getMap(r)) { r++;} for (;rs) { //markStrings(s, e); //fprintf(stdout, "\n(%08X)eraseUncertain: %08X - %08X =%3d labels are deleted", // ref, s, e,n); } ph->s=s; ph->e=e; ph->l=n; //if (e>s) //fprintf(stderr, "\n(%08X)eraseUncertain: %08X - %08X =%3d labels are deleted\n", // ref, s, e, n); //ReportMap(); //exit(0); eraseUncertainNum++; if (hCntimagebaseRVA;r--) if (((b=getMap(r))==0x00)||(b&0x88)) break; // start position to erase s = r+1; r=ref; if (getMap(r)) { r++;} for (;r0x80)break; cBox[getByteFile(r)]+=1;r++;nn++; } rr=r; if ((cBox[0xC2]+cBox[0xC3]==0) && ((cBox[0x81]+cBox[0x83]+cBox[0x89]+cBox[0x8B])*100s) { //markStrings(s, e); //fprintf(stderr, "\n@(%08X)eraseUncertain1: %08X - %08X ... %3d labels are deleted\n",ref, // s,e,n); //fprintf(stdout, "\n@(%08X)eraseUncertain1: %08X - %08X ... %3d labels are deleted\n",ref, // s,e,n); } ph->s=s; ph->e=e; ph->l=n; //if(!isGoodAddress(s)) //fprintf(stderr,"\nRRR..%08X s=%08X",ref,s),getch(); if (hCnt<5012) History[hCnt++]=*ph; else {fprintf(stderr,"hCnt over");exit(0);} } void eraseCarefully(DWORD ref, PHISTORY ph) { //int i, n; _key_ k; PKEY pk; //fprintf(stdout,"\neraseCarefully::%08X=<=%08X",ref,cur_position); k.c_ref=ref; k.c_pos=-1; k.class=0; pk = searchBtree3(&k); if (pk==NULL) return; //{fprintf(stderr, " NOT FOUND ");fprintf(stdout, " NOT FOUND "); // return 1;} //fprintf(stdout," ::%08X",pk->c_pos); /*-----------*/pushTrace(2600); eraseUncertain1(pk->c_pos, ph); /*-----------*/popTrace(); } // ******************************************* // label handling functions // ******************************************* int isLabelCheckable(DWORD r) { if (getMap(r )>0) return 0; if (getMap(r+1)>0) return 0; if (getMap(r+2)>0) return 0; if (getMap(r+3)>0) return 0; return 1; } void setAddress(DWORD pos) { /*-----------*/pushTrace(2650); if(isLabelCheckable(pos)) { setMap(pos , 0x0E); setMap(pos+1, 0x0E); setMap(pos+2, 0x0E); setMap(pos+3, 0x0E); } /*-----------*/popTrace(); } void setAnyAddress(DWORD pos) { /*-----------*/pushTrace(2660); orMap1(pos ,0x30); orMap1(pos+1,0x20); orMap1(pos+2,0x20); orMap1(pos+3,0x20); /*-----------*/popTrace(); } int isItAnyAddress(DWORD pos) { if ((getMap1(pos )&0x30)!=0x30) return 0; if ((getMap1(pos+1)&0x30)!=0x20) return 0; if ((getMap1(pos+2)&0x30)!=0x20) return 0; if ((getMap1(pos+3)&0x30)!=0x20) return 0; return 1; } int touchAnyAddress(DWORD pos) { if ((getMap1(pos)&0x30)==0x20) return 1; return 0; } int isAddressBlock(DWORD pos) { DWORD i, r, rmax; r=pos-3; rmax=pos+128; while(1) { for (;r12) return 1; return 0; } } void setFirstTime(DWORD pos) { /*--------*/pushTrace(2670); if (nextMode==0) orMap1(pos,0x80); else orMap1(pos,0x40); /*--------*/popTrace(); } int isItFirstTime(DWORD pos) { BYTE b; if (nextMode==0) b=0x80; else b=0x40; if ((getMap1(pos)&b)==0x00) return 1; return 0; } void MyBtreeInsertDual(int class, DWORD ref, DWORD pos) { _key_ k; k.class = class; k.c_pos = pos; k.c_ref = ref; MyBtreeInsert(&k); k.class = -class; k.c_pos = ref; k.c_ref = pos; MyBtreeInsert(&k); // we can use this .. for erase uncertain case. } void MyBtreeDeleteDual(int class, DWORD ref, DWORD pos) { _key_ k; k.class = class; k.c_pos = pos; k.c_ref = ref; MyBtreeDelete(&k); k.class = -class; k.c_pos = ref; k.c_ref = pos; MyBtreeDelete(&k); // we can use this .. for erase uncertain case. } int BadEnter(DWORD ref, DWORD pos) { int col; BYTE b; b=getMap(ref); if (i_col>0) col=i_col; else col=i_col_save; if (pos<=ref&&ref2 && isItStartAnyWay(ref)) addLabels(ref, 256); /*----------*/popTrace(); /*----------*/pushTrace(3020); orMap(ref, 0x20); /*----------*/popTrace(); /*----------*/pushTrace(3030); orMap(pos, 0x10); /*----------*/popTrace(); break; case 11: case 15: case 2048: /*----------*/pushTrace(3040); MyBtreeInsertDual(class, ref, pos); /*----------*/popTrace(); if (BadEnter(ref,pos)) break; //need to store something here. /*----------*/pushTrace(3050); if (isItStartAnyWay(ref)) addLabels(ref, 512); /*----------*/popTrace(); /*----------*/pushTrace(3060); orMap(ref, 0x40); /*----------*/popTrace(); /*----------*/pushTrace(3070); orMap(pos, 0x10); /*----------*/popTrace(); break; case 166: case 167: // mark that address data /*----------*/pushTrace(3080); addLabels(ref,128); /*----------*/popTrace(); /*----------*/pushTrace(3090); setAddress(pos); /*----------*/popTrace(); /*----------*/pushTrace(3100); MyBtreeInsertDual(class, ref, pos); /*----------*/popTrace(); if (BadEnter(ref,pos)) break; /*----------*/pushTrace(3110); orMap(ref, 0x20); /*----------*/popTrace(); break; case 512: case 513: case 514: case 515: case 516: case 517: case 518: case 519: case 520: case 524: case 528: case 1024: /*----------*/pushTrace(3120); MyBtreeInsertDual(class, ref, pos); /*----------*/popTrace(); /*----------*/pushTrace(3130); markData(class, ref, pos); /*----------*/popTrace(); break; //-------------------------------------------------------------------// // now it is indirect address reference and we need to take some // // serious actions, namely if it is preventable than it is OK // // but if bad deed is already done we need to UNDO it. // // this requires couple of things. // // first we need to store indirect references in some convenient way // // and every time we need to check whether we touch it or not. // // second we need to store all the anchors and start positions // // so we can easily determine how much we need to UNDO. // // october 24, 1997 late night-- sang cho // //-------------------------------------------------------------------// case 5: case 9: case 13: case 17: case 133: // mark that address data // // the following code is for some special interuptive case::: // I need to check the validity of this part somehow... // if(getMap(ref)!=0x0E&&!isLabelCheckable(ref)) { if(isGoodAddress(getIntFile(ref)) && isGoodAddress(getIntFile(ref+4)) && isGoodAddress(getIntFile(ref+8))) for(i=ref;i0) { if (AddressCheck(r)) { if (BadEnter(r,ref)) break; /*---------*/pushTrace(3200); MyBtreeInsertDual(class+32, r, ref); /*---------*/popTrace(); if (class<13||170) { if (class==7 ) { /*----------*/pushTrace(3250); if (isGoodAddress(r)) addLabels(r,32); /*----------*/popTrace(); } /*--------------*/pushTrace(3260); MyBtreeInsertDual(class, r, pos); /*--------------*/popTrace(); } break; case 166: case 167: // mark that address data /*-----------*/pushTrace(3270); setAddress(pos); /*-----------*/popTrace(); /*-----------*/pushTrace(3280); MyBtreeInsertDual(class, ref, pos); /*-----------*/popTrace(); break; case 512: case 513: case 514: case 515: case 516: case 517: case 518: case 519: case 520: case 524: case 528: case 1024: /*-----------*/pushTrace(3290); MyBtreeInsertDual(class, ref, pos); /*-----------*/popTrace(); break; case 5: case 9: case 13: case 17: case 133: // mark that address data r = Get32Address(ref); if (r>0) { /*-----------*/pushTrace(3300); MyBtreeInsertDual(class, r, pos); /*-----------*/popTrace(); // I am forming chain of label references. // also new class is defined here. rr = Get32Address(r); if (rr>0) { if (class<13||class>17) { /*------------*/pushTrace(3310); if(isGoodAddress(rr)) addLabels(rr,16); /*------------*/popTrace(); } /*-----------*/pushTrace(3320); MyBtreeInsertDual(class+32, rr, r); /*-----------*/popTrace(); } } default: break; } } } void markData(int class, DWORD ref, DWORD pos) { BYTE a, b, c, d; DWORD i; /*-----------*/pushTrace(3400); switch(class) { case 512: a=getMap(ref); b=getMap(ref+1); c=getMap(ref+2); d=getMap(ref+3); if ((a==0||(a&0x08))&&(b==0||(b&0x08)) &&(c==0||(c&0x08))&&(d==0||(d&0x08))) { if (isItStartAnyWay(ref)) addLabels(ref, 1); else if(isGoodAddress(getIntFile(ref))) { setMap(ref,0x0E); setMap(ref+1,0x0E); setMap(ref+2,0x0E); setMap(ref+3,0x0E); } } break; case 513: a=getMap(ref); b=getMap(ref+1); c=getMap(ref+2); d=getMap(ref+3); if ((a==0||(a&0x08))&&(b==0||(b&0x08)) &&(c==0||(c&0x08))&&(d==0||(d&0x08))) { if(isGoodAddress(getIntFile(ref))) { setMap(ref,0x0E); setMap(ref+1,0x0E); setMap(ref+2,0x0E); setMap(ref+3,0x0E); } } break; case 514: a=getMap(ref); b=getMap(ref+1); c=getMap(ref+2); d=getMap(ref+3); if ((a==0||(a&0x08))&&(b==0||(b&0x08)) &&(c==0||(c&0x08))&&(d==0||(d&0x08))) { setMap(ref,0x0E); setMap(ref+1,0x0E); setMap(ref+2,0x0E); setMap(ref+3,0x0E); } else if (a==0x0E && b==0x0E && c==0x0E && d==0x0E); else { //fprintf(stderr, "\nmarkData error class=%3d ref=%08X pos=%08X ", // class, ref, pos); //fprintf(stderr, "%02X %02X %02X %02X ", a,b,c,d); fatalError=994; //getch(); } break; case 515: for (i=ref;i= nSections) return 0; /* return image import directory offset */ return ref - imageBase - (int)shdr[i].VirtualAddress + (int)shdr[i].PointerToRawData; } DWORD getRVA (DWORD off) { int i; if (off == 0) return 0; /* locate section containing image directory */ for(i=0;i= nSections) return 0; /* return image import directory offset */ return off - (int)shdr[i].PointerToRawData + (int)shdr[i].VirtualAddress; } DWORD Get32Address(DWORD ref) { DWORD r, off; _key_ k; PKEY pk; off = getOffset(ref); if (off < CodeOffset) { k.c_ref=ref; k.c_pos=-1; k.class=0; pk=searchBtreeX(&k); if (pk==NULL) return 0; else return ref; } if (offc_pos; if(!AddressCheck(r)) { k.c_ref=r;k.c_pos=0;k.class=0; pk=searchBtree1(&k); if(pk==NULL)return 1; else return 0; } if(getOffset(r)CodeOffset+CodeSize&&referCount(r)>0)return 0; } return 1; } PBYTE toFile(DWORD ref) { DWORD r=getOffset(ref); if(r<0) return 0; if(r>fsize) return 0; return (PBYTE)((int)r+(int)lpFile); } BYTE getByteFile(DWORD ref) { DWORD r=getOffset(ref); if(r<0) return 0; if(r>fsize-4) return 0; return *(PBYTE)((int)r+(int)lpFile); } int getIntFile(DWORD ref) { DWORD r=getOffset(ref); if(r<0) return 0; if(r>=fsize) return 0; return *(int *)((int)r+(int)lpFile); } BYTE getMap(DWORD ref) { DWORD r=getOffset(ref); if(r=CodeOffset+CodeSize) return 0; return *(PBYTE)((int)r+(int)lpMap); } void setMap(DWORD ref, BYTE c) { DWORD r=getOffset(ref); //int i; /* if(ref==debugAdd||ref==debugAdd1) { fprintf(stderr,"\nsetMap(%08X) (%02X)to %02X from c_pos=%08X f=%d ", ref, getMap(ref),c,cur_position,fatalError); for(i=0;i=CodeOffset+CodeSize) return; *(PBYTE)((int)r+(int)lpMap)=c; } void orMap(DWORD ref, BYTE c) { DWORD r=getOffset(ref); //int i; /* if(ref==debugAdd||ref==debugAdd1) { fprintf(stderr,"\norMap(%08X) to %02X from c_pos=%08X (%02X)", ref,c,cur_position, getMap(ref)); for(i=0;i=CodeOffset+CodeSize) return; *(PBYTE)((int)r+(int)lpMap)|=c; } void exMap(DWORD ref, BYTE c) { DWORD r=getOffset(ref); if(r=CodeOffset+CodeSize) return; *(PBYTE)((int)r+(int)lpMap)^=c; } BYTE getMap1(DWORD ref) { DWORD r=getOffset(ref); if(r=CodeOffset+CodeSize) return 0; return *(PBYTE)((int)r+(int)lpMap1); } void setMap1(DWORD ref, BYTE c) { DWORD r=getOffset(ref); if(r=CodeOffset+CodeSize) return; *(PBYTE)((int)r+(int)lpMap1)=c; } void orMap1(DWORD ref, BYTE c) { DWORD r=getOffset(ref); if(r=CodeOffset+CodeSize) return; *(PBYTE)((int)r+(int)lpMap1)|=c; } void exMap1(DWORD ref, BYTE c) { DWORD r=getOffset(ref); /* if(ref==debugAdd||ref==debugAdd1) { fprintf(stderr,"\nexMap1(%08X) to %02X from debugPoint=%3d c_pos=%08X", ref,c,debugPoint,cur_position); getch(); }*/ if(r=CodeOffset+CodeSize) return; *(PBYTE)((int)r+(int)lpMap1)^=c; } // // I cannot actually compute m16:m32 far address value // so I will only record m32 part of it, hope it actually works. // DWORD Get16_32Address(DWORD ref) { return Get32Address(ref); } // ************************************* // miscellaneous functions // ************************************* void Myfinish() { free ((void *)piNameBuff); free ((void *)peNameBuff); free ((void *)lpFile); free ((void *)lpMap); free ((void *)lpMap1); deleteHeaders(); //fclose(d_fp); exit(0); } /* ============================================================= I am using very strange looking data structure to store labels. There are two parts of it. 1. source part 2. destination part we have node struct { DWORD pos1 DWORD pos2 // i don't like to use union structure so i will just WORD red; WORD rclass // use type casting (node *)pos2 ... WORD rcount node* left node * right } node1 struct { DWORD pos2 short rclass node1* left node1* right } I. source part looks like this: there are fsize/256 + 1 many headers for labels. if the number of headers exceeds 64K then it is adjusted to 64K. each header is a pointer to a node and there are some nodes linked to this header. these nodes are only generated between 256 byte range of code. so the number of nodes cannot be too big. each nodes are linked in binary search tree as first integer as a key usually rcount == 1 and that is it, but if rcount > 1 then pos2 points to the second level of nodes that are linked as binary search tree fashion. when there are case jump block we can think all the addresses are used by this case jump instruction so there are many source side references. but this is not direct reference, anyway we need to store counter part of this information into destination side too. II. destination part looks like this: there are fsize/256 + 1 many headers for labels. each header is a pinter to a node and there are some nodes linked to this header. these nodes are destinations between 256 byte range of code. each node may have children nodes which are linked through down pointer.( pos2) when rcount == 1 then there are no children. if rcount > 1 then pos2 points to the second level of nodes (children nodes) ---------------------------------------------------------------------------- */ int asize; int hsize; int width; LPVOID headerS; LPVOID headerD; void initHeaders() { asize = fsize/8 + 1; hsize = fsize/256; width = 256; while(hsize>64*1024){hsize/=2;width*=2;} hsize+=1; headerS=(LPVOID)calloc(hsize*4,1); if (headerS==NULL) {fprintf(stderr,"Cannot allocate headerS"); exit(1);} headerD=(LPVOID)calloc(hsize*4,1); if (headerD==NULL) {fprintf(stderr,"Cannot allocate headerD"); exit(1);} initHeap(); } void deleteTrees1(PNODE1 pn) { if (pn==NULL) return; deleteTrees1(pn->left); deleteTrees1(pn->right); free((void *)pn); } void deleteTrees(PNODE pn) { //fprintf(stderr,"\n pn==%08X",pn);getch(); //if (pn>0) fprintf(stderr," pn->left==%08X pn->right==%08X",pn->left, pn->right); if (pn==NULL) return; deleteTrees(pn->left); deleteTrees(pn->right); if (pn->rcount>1) deleteTrees1((PNODE1)(pn->pos2)); free((void *)pn); } extern PNODE rHead; void deleteHeaders() { int i; PNODE *pps, *ppd; for (i=0; ileft, pos); if (s != NULL) return s; if (base->pos2 != 0) return base; s=searchTT1(base->right,pos); return s; } PNODE1 searchTT(PNODE1 base, DWORD pos1, DWORD pos2) { PNODE1 s; if (pos2==-1) return searchTT1(base, pos2); s = base; while (s != NULL && pos2 != s->pos2) { if (TOINT(pos2)pos2)) s = s->left; else s = s->right; } return s; } PNODE searchT(PNODE base, DWORD pos1, DWORD pos2) { PNODE s; PNODE1 r; s = base; while (s != NULL && pos1 != s->pos1) { if (TOINT(pos1)pos1)) s = s->left; else s = s->right; } if (s == NULL) return NULL; if (s->rcount==1 || pos2==0) return s; // this is dangerous place r=searchTT((PNODE1)(s->pos2), pos1, pos2); if (r == NULL) return NULL; my_node.pos1 =pos1; my_node.pos2 =r->pos2; my_node.rclass=r->rclass; my_node.rcount=1; return &my_node; } PNODE searchTree(LPVOID h, DWORD pos1, DWORD pos2) { int pos; PNODE *ppn; pos = pos1-imageBase; if (pos<0) pos=0; pos/=width; if (pos>=hsize) pos=hsize-1; ppn=(PNODE *)(h+4*pos); return searchT(*ppn, pos1, pos2); } PKEY searchBtree1(PKEY k) { PNODE t; if (k->class>0) t=searchTree(headerD, k->c_ref, k->c_pos); else t=searchTree(headerS, k->c_ref, k->c_pos); if (t==NULL) return NULL; my_key.class=t->rclass; my_key.c_ref=t->pos1; my_key.c_pos=t->pos2; return &my_key; } PKEY searchBtree3(PKEY k) { PNODE t; t=searchTree(headerD, k->c_ref, k->c_pos); if (t==NULL) return NULL; my_key.class=t->rclass; my_key.c_ref=t->pos1; my_key.c_pos=t->pos2; return &my_key; } extern PNODE headerX; PKEY searchBtreeX(PKEY k) { PNODE t; t=searchT(headerX, k->c_ref, k->c_pos); if (t==NULL) return NULL; my_key.class=t->rclass; my_key.c_ref=t->pos1; my_key.c_pos=t->pos2; return &my_key; } int referCount(DWORD ref) { PNODE t; t = searchTree(headerD, ref, 0); if (t==NULL) return 0; return t->rcount; } int referCount1(DWORD ref) { PNODE t; t = searchTree(headerS, ref, 0); if (t==NULL) return 0; return t->rcount; } int insertTree(LPVOID h, int class, DWORD pos1, DWORD pos2) { int pos; PNODE *ppn; //fprintf(stderr,"\nHERE 1 c=%3d r=%08X p=%08X",class,pos1,pos2),getch(); pos = pos1-imageBase; if (pos<0) pos=0; pos/=width; if (pos>=hsize) pos=hsize-1; ppn=(PNODE *)(h+4*pos); return insertT(ppn, class, pos1, pos2); } PNODE headerX=NULL; int MyBtreeInsertX(PKEY k) { return insertT(&headerX, k->class, k->c_ref, k->c_pos); return 1; } int MyBtreeInsert(PKEY k) { //fprintf(stderr,"\nHERE 0 c=%3d r=%08X p=%08X",k->class,k->c_ref,k->c_pos),getch(); if (k->class>0) return insertTree(headerD, k->class, k->c_ref, k->c_pos); else return insertTree(headerS, k->class, k->c_ref, k->c_pos); return 1; } int MyBtreeInsertEx(PKEY k) { //_key_ key; MyBtreeInsert(k); return 1; } int deleteTree(LPVOID h, DWORD pos1, DWORD pos2) { int pos; PNODE *ppn; pos = pos1-imageBase; if (pos<0) pos=0; pos/=width; if (pos>=hsize)pos=hsize-1; ppn=(PNODE *)(h+4*pos); return deleteT(ppn, pos1, pos2); } // i can refuse to be deleted provied that reference count is big enough. int MyBtreeDelete(PKEY k) { if (k->class>0) return deleteTree(headerD, k->c_ref, k->c_pos); else return deleteTree(headerS, k->c_ref, k->c_pos); return 1; } int sortCol=0; int sortT(PNODE1 pn, DWORD pos1) { if (pn==NULL) return 0; sortT(pn->left, pos1); printf("%4d:%08X<%08X,", pn->rclass, (int)pos1, (int)(pn->pos2)); if(sortCol++ % 4==0)printf("\n"); sortT(pn->right, pos1); return 1; } int sortTree(PNODE pn) { if (pn==NULL) return 0; sortTree(pn->left); if (pn->rcount>1) sortT((PNODE1)(pn->pos2), pn->pos1); if (pn->rcount==1){ printf("%4d:%08X<%08X,", pn->rclass, (int)(pn->pos1), (int)(pn->pos2)); if(sortCol++ % 4==0)printf("\n");} sortTree(pn->right); return 1; } int sortTrees() { int i; PNODE *ppd; for (i=0; ipos2)) child = p->left; else child = p->right; if (TOINT(pos2) < TOINT(child->pos2)) { gchild = child->left; child->left = gchild->right; gchild->right = child; } else { gchild = child->right; child->right = gchild->left; gchild->left = child; } if (p==NULL) *base = gchild; else if (TOINT(pos2) < TOINT(p->pos2)) p->left = gchild; else p->right = gchild; return gchild; } PNODE rotate(PNODE *base, PNODE p, DWORD pos1, DWORD pos2) { /* single rotation */ PNODE child, gchild; if (p==NULL) child=*base; else if (TOINT(pos1) < TOINT(p->pos1)) child = p->left; else child = p->right; if (TOINT(pos1) < TOINT(child->pos1)) { gchild = child->left; child->left = gchild->right; gchild->right = child; } else { gchild = child->right; child->right = gchild->left; gchild->left = child; } if (p==NULL) *base = gchild; else if (TOINT(pos1) < TOINT(p->pos1)) p->left = gchild; else p->right = gchild; return gchild; } int insertTT(PNODE1 *base, int class, DWORD pos1, DWORD pos2) { PNODE1 t, p, g, gg; gg = g = p = NULL; t = *base; while (t != NULL) { if (pos2 == t->pos2) return 0; if (t->left && t->right && t->left->red && t->right->red) { t->red = 1; /* color flip */ t->left->red = t->right->red = 0; if (p && p->red && g) /* rotation needed */ { g->red = 1; if (TOINT(pos2) < TOINT(g->pos2) != TOINT(pos2) < TOINT(p->pos2)) p = rotate1(base, g, pos1, pos2); /* double rotation */ t = rotate1(base, gg, pos1, pos2); t->red = 0; } (*base)->red = 0; } gg = g; g = p; p = t; if (TOINT(pos2) < TOINT(t->pos2)) t = t->left; else t = t->right; } if ((t = (PNODE1)calloc(sizeof(node1),1)) == NULL) return 0; t->pos2 = pos2; t->rclass = class; t->left = NULL; t->right = NULL; if (p==NULL) *base = t; else if (TOINT(pos2) < TOINT(p->pos2)) p->left = t; else p->right = t; t->red = 1; /* paint color */ if (p && p->red && g) /* rotation needed */ { g->red = 1; if (TOINT(pos2) < TOINT(g->pos2) != TOINT(pos2) < TOINT(p->pos2)) p = rotate1(base, g, pos1, pos2); /* double rotation */ t = rotate1(base, gg, pos1, pos2); t->red = 0; } (*base)->red = 0; return 1; } int insertSecond(PNODE t, int class, DWORD pos1, DWORD pos2) { DWORD pos; if (t->pos2==pos2) return 0; if (t->rcount==1) { pos=t->pos2; t->pos2=0; insertTT((PNODE1*)&(t->pos2), t->rclass, pos1, pos); insertTT((PNODE1*)&(t->pos2), class, pos1, pos2); t->rcount=2; return 1; } if (insertTT((PNODE1*)&(t->pos2),class,pos1,pos2)) { t->rcount += 1; return 1; } return 0; } int insertT(PNODE *base, int class, DWORD pos1, DWORD pos2) { PNODE t, p, g, gg; gg = g = p = NULL; t = *base; while (t != NULL) { if (pos1==t->pos1) return insertSecond(t, class, pos1, pos2); /* equal key */ if (t->left && t->right && t->left->red && t->right->red) { t->red = 1; /* color flip */ t->left->red = t->right->red = 0; if (p && p->red && g) /* rotation needed */ { g->red = 1; if (TOINT(pos1) < TOINT(g->pos1) != TOINT(pos1) < TOINT(p->pos1)) p = rotate(base, g, pos1, pos2); /* double rotation */ t = rotate(base, gg, pos1, pos2); t->red = 0; } (*base)->red = 0; } gg = g; g = p; p = t; if (TOINT(pos1) < TOINT(t->pos1)) t = t->left; else t = t->right; } if ((t = (PNODE)calloc(sizeof(node),1)) == NULL) return 0; t->pos1 = pos1; t->pos2 = pos2; t->rclass = class; t->rcount = 1; t->left = NULL; t->right = NULL; if (p == NULL) *base = t; else if (TOINT(pos1) < TOINT(p->pos1)) p->left = t; else p->right = t; t->red = 1; /* paint color */ if (p && p->red && g) /* rotation needed */ { g->red = 1; if (TOINT(pos1) < TOINT(g->pos1) != TOINT(pos1) < TOINT(p->pos1)) p = rotate(base, g, pos1, pos2); /* double rotation */ t = rotate(base, gg, pos1, pos2); t->red = 0; } (*base)->red = 0; return 1; } PNODE1 findSeed1(PNODE1 *base, DWORD pos1, DWORD pos2) { PNODE1 del, seed_parent, parent; seed_parent = NULL; parent = NULL; del = (*base); while (del != NULL) { if (TOINT(pos2) < TOINT(del->pos2)) { if (del->red || (del->right && del->right->red)) seed_parent = parent; parent = del; del = del->left; } else { if (del->red || (del->left && del->left->red)) seed_parent = parent; parent = del; del = del->right; } } return seed_parent; } PNODE findSeed(PNODE *base, DWORD pos1, DWORD pos2) { PNODE del, seed_parent, parent; seed_parent = NULL; parent = NULL; del = (*base); while (del != NULL) { if (TOINT(pos1) < TOINT(del->pos1)) { if (del->red || (del->right && del->right->red)) seed_parent = parent; parent = del; del = del->left; } else { if (del->red || (del->left && del->left->red)) seed_parent = parent; parent = del; del = del->right; } } return seed_parent; } void make_leaf_red1(PNODE1 *base, DWORD pos1, DWORD pos2) { PNODE1 seed_parent, seed, seed_child; seed_parent = findSeed1(base, pos1, pos2); if (seed_parent == NULL) { seed_parent = NULL; seed = *base; seed->red = 1; } else { if (seed_parent == NULL || TOINT(pos2) < TOINT(seed_parent->pos2)) seed = seed_parent->left; else seed = seed_parent->right; } if (!seed->red) /* sibling is red, reverse rotation */ { if (TOINT(pos2) < TOINT(seed->pos2)) seed_child = seed->right; else seed_child = seed->left; seed->red = 1; seed_child->red = 0; seed_parent = rotate1(base, seed_parent, pos1, seed_child->pos2); } while (seed->left && seed->right) { seed->red = 0; seed->right->red = seed->left->red = 1; if (TOINT(pos2) < TOINT(seed->pos2)) { if ((seed->right->left && seed->right->left->red) || (seed->right->right && seed->right->right->red)) { /* reverse rotation needed! */ if (seed->right->left && seed->right->left->red) { seed->right->red = 0; rotate1(base, seed, pos1, seed->right->left->pos2); } else seed->right->right->red = 0; rotate1(base, seed_parent, pos1, seed->right->pos2); } seed_parent = seed; seed = seed->left; } else { if ((seed->left->left && seed->left->left->red) || (seed->left->right && seed->left->right->red)) { if (seed->left->right && seed->left->right->red) { seed->left->red = 0; rotate1(base, seed, pos1, seed->left->right->pos2); } else seed->left->left->red = 0; rotate1(base, seed_parent, pos1, seed->left->pos2); } seed_parent = seed; seed = seed->right; } } } void make_leaf_red(PNODE *base, DWORD pos1, DWORD pos2) { PNODE seed_parent, seed, seed_child; seed_parent = findSeed(base, pos1, pos2); if (seed_parent == NULL) { seed_parent = NULL; seed = *base; seed->red = 1; } else { if (TOINT(pos1) < TOINT(seed_parent->pos1)) seed = seed_parent->left; else seed = seed_parent->right; } if (!seed->red) /* sibling is red, reverse rotation */ { if (TOINT(pos1) < TOINT(seed->pos1)) seed_child = seed->right; else seed_child = seed->left; seed->red = 1; seed_child->red = 0; seed_parent = rotate(base, seed_parent, seed_child->pos1, pos2); } while (seed->left && seed->right) { seed->red = 0; seed->right->red = seed->left->red = 1; if (TOINT(pos1) < TOINT(seed->pos1)) { if ((seed->right->left && seed->right->left->red) || (seed->right->right && seed->right->right->red)) { /* reverse rotation needed! */ if (seed->right->left && seed->right->left->red) { seed->right->red = 0; rotate(base, seed, seed->right->left->pos1, pos2); } else seed->right->right->red = 0; rotate(base, seed_parent, seed->right->pos1, pos2); } seed_parent = seed; seed = seed->left; } else { if ((seed->left->left && seed->left->left->red) || (seed->left->right && seed->left->right->red)) { if (seed->left->right && seed->left->right->red) { seed->left->red = 0; rotate(base, seed, seed->left->right->pos1, pos2); } else seed->left->left->red = 0; rotate(base, seed_parent, seed->left->pos1, pos2); } seed_parent = seed; seed = seed->right; } } } int deleteTT(PNODE1 *base, DWORD pos1, DWORD pos2) { PNODE1 parent, del, center, pcenter, son; parent = NULL; del = (*base); while (del && TOINT(pos2) < TOINT(del->pos2)) { parent = del; if (TOINT(pos2) < TOINT(del->pos2)) del = del->left; else del = del->right; } if (del == NULL) return 0; /* can't find */ if (del->pos2!=pos2)return 0; if (del->right && del->left) { pcenter = del; center = del->right; while (center->left != NULL) { pcenter = center; center = center->left; } del->pos2 =center->pos2; del->rclass=center->rclass; del = center; parent = pcenter; pos2 = del->pos2; } if (del->left || del->right) { /* one child must be red */ if (del->left) son = del->left; else son = del->right; son->red = 0; } else if (del->left == NULL && del->right == NULL) { /* leaf node */ if (!del->red) make_leaf_red1(base, pos1, del->pos2); son = NULL; } (*base)->red = 0; if (parent == NULL) *base=son; else if (TOINT(pos2) < TOINT(parent->pos2)) parent->left = son; else parent->right = son; free(del); return 1; } int deleteT(PNODE *base, DWORD pos1, DWORD pos2) { PNODE parent, del, center, pcenter, son; int i; parent = NULL; del = (*base); while (del && TOINT(pos1) < TOINT(del->pos1)) { parent = del; if ((int)pos1 < (int)(del->pos1)) del = del->left; else del = del->right; } if (del == NULL) return 0; /* can't find */ if (del->pos1!=pos1) return 0; // anyway found it if (del->rcount>1) { i=deleteTT((PNODE1*)&(del->pos2), pos1, pos2); if(i>0) del->rcount-=1; return 1; } if (del->right && del->left) { pcenter = del; center = del->right; while (center->left != NULL) { pcenter = center; center = center->left; } del->pos1 =center->pos1; del->pos2 =center->pos2; del->rclass =center->rclass; del->rcount =center->rcount; del = center; parent = pcenter; pos1 = del->pos1; pos2 = del->pos2; } if (del->left || del->right) { /* one child must be red */ if (del->left) son = del->left; else son = del->right; son->red = 0; } else if (del->left == NULL && del->right == NULL) { /* leaf node */ if (!del->red) make_leaf_red(base, del->pos1, pos2); son = NULL; } (*base)->red = 0; if (parent == NULL) *base=son; else if (TOINT(pos1) < TOINT(parent->pos1)) parent->left = son; else parent->right = son; free(del); return 1; } // Priority Queue routines int heapLTE(_labels x, _labels y) { if (x.priority < y.priority) return 1; if (x.priority > y.priority) return 0; if (x.ref >= y.ref) return 1; return 0; } int heapLT(_labels x, _labels y) { if (x.priority < y.priority) return 1; if (x.priority > y.priority) return 0; if (x.ref > y.ref) return 1; return 0; } void initHeap() { pArray[0].priority = INT_MAX; pArray[0].ref = 0; jLc = 0; } int upHeap(_labels a[], int k) { _labels v; //fprintf(stderr,"u"); v = a[k]; while(heapLTE(a[k/2],v)) { a[k] = a[k/2]; k /= 2; } a[k] = v; return k; } void downHeap(_labels a[], int n, int k) { _labels v; int i; v = a[k]; while(k <= n/2) { i = k + k; if (i < n && heapLT(a[i],a[i+1])) i++; if (heapLTE(a[i],v)) break; a[k] = a[i]; k=i; } a[k] = v; } _labels getHeap(int *n) { _labels v = pArray[1]; //fprintf(stderr,"g"); pArray[1] = pArray[(*n)--]; downHeap(pArray, *n, 1); return v; } int putHeap(int *n, int priority, DWORD ref) { int i; //fprintf(stderr,"p"); i=++(*n); pArray[i].priority = priority; pArray[i].ref = ref; return upHeap(pArray, i); } int getLabels() { _labels v; int r; while(jLc>0) { v = getHeap(&jLc); r = v.ref; if (isGoodAddress(r)) return r; } return 1; } PNODE rHead=NULL; void addRef(int c, DWORD r, DWORD p) { insertT(&rHead, c, r, p); } int countRef(DWORD r) { PNODE t; t=searchT(rHead, r, 0); if (t==NULL) return 0; return t->rcount; } int addLabelsNum=0; int addLabelsHistogram[256]={0,}; void addLabels(DWORD r, int pri) { if (!isItFirstTime(r)) return; if (r