00001 #include "bmtree.h"
00002 #include <string.h>
00003 #include "bits.h"
00004 #include <stdio.h>
00005 #include <stdlib.h>
00006 #ifdef _SOLARIS_
00007 #include <strings.h>
00008 #endif
00009 #include <ctype.h>
00010
00011
00012
00013
00014 extern GlobalVars Globals;
00015
00016
00017
00018
00019 int InitTree(BMTree* tree, char IgnoreCase){
00020
00021 #ifdef DEBUGPATH
00022 printf("In InitTree\n");
00023 #endif
00024
00025 bzero(tree, sizeof(BMTree));
00026
00027 return TRUE;
00028 }
00029
00030
00031
00032
00033 int AddToTreeSorted(BMTree* Tree, char* String, int Len, int RuleID){
00034 int i;
00035 BNode** this;
00036 BNode** last;
00037 int count;
00038
00039 #ifdef DEBUGPATH
00040 printf("In AddToTree\n");
00041 #endif
00042
00043 if (Len==0) return FALSE;
00044
00045 #ifdef DEBUGBUILD
00046 printf("Adding %s to tree\n",String);
00047 #endif
00048
00049 SetBit(Tree->TreeDependMask, Globals.NumRules, RuleID, 1);
00050
00051 this=&Tree->TreeHead;
00052 last=this;
00053 for (i=0;i<Len;i++){
00054 printf("This letter is a %c\n",String[i]);
00055 count=0;
00056 while (*this){
00057 printf("Comparing %c vs %c\n",String[i], (*this)->byte);
00058 if ( (*this)->byte > String[i]){
00059 #ifdef DEBUGBUILD
00060 printf("%c goes before %c\n", String[i], (*this)->byte);
00061 #endif
00062 (*last)->NextPeer=calloc(sizeof(BNode),1);
00063 last=&(*last)->NextPeer;
00064 (*last)->NextPeer=(*this);
00065
00066 (*last)->byte=String[i];
00067 this=&(*last)->Child;
00068 break;
00069 }
00070 last=this;
00071 this=&(*this)->NextPeer;
00072 printf("Next\n");
00073 count++;
00074 if (count>6) exit(0);
00075 }
00076
00077 if (!(*this)){
00078 #ifdef DEBUGBUILD
00079 printf("There are no children. Adding a child \"%c\"\n", String[i]);
00080 #endif
00081 (*this)=calloc(sizeof(BNode),1);
00082 (*this)->byte=String[i];
00083 last=this;
00084 this=&(*this)->Child;
00085 continue;
00086 }
00087
00088 }
00089
00090
00091 printf("This is the end\n");
00092 (*last)->IsTerminal=TRUE;
00093 (*last)->TerminalRuleID=RuleID;
00094
00095 return TRUE;
00096 }
00097
00098
00099
00100
00101 int AddToTree(BMTree* Tree, char* String, int Len, int RuleID){
00102 int i;
00103 BNode* this;
00104 BNode** that;
00105 char HexMode;
00106 char NextChar;
00107 char HexChar[3];
00108 int HexCount;
00109
00110 #ifdef DEBUGPATH
00111 printf("In AddToTree\n");
00112 #endif
00113
00114 if (Len==0) return FALSE;
00115
00116 #ifdef DEBUGBUILD
00117 printf("Adding %s to tree\n",String);
00118 #endif
00119
00120 SetBit(Tree->TreeDependMask, Globals.NumRules, RuleID, 1);
00121
00122 that=&Tree->TreeHead;
00123 HexMode=FALSE;
00124 for (i=0;i<Len;i++){
00125 if (HexMode){
00126 NextChar=String[i];
00127
00128
00129 if (NextChar=='|'){
00130 HexMode=FALSE;
00131 continue;
00132 }
00133
00134
00135 if (NextChar==' ') continue;
00136
00137 HexChar[HexCount]=NextChar;
00138 HexCount++;
00139 if (HexCount==2){
00140 NextChar=strtoul(HexChar, NULL, 16);
00141 HexCount=0;
00142 #ifdef DEBUG
00143 printf("Hex processed as %02x\n",HexChar);
00144 #endif
00145 }else{
00146 continue;
00147 }
00148 }else{
00149
00150 if (Tree->IgnoreCase){
00151 NextChar=tolower(String[i]);
00152 }else{
00153 NextChar=String[i];
00154 }
00155
00156
00157 if (NextChar=='|'){
00158 if (String[i+1]=='|'){
00159
00160 NextChar='|';
00161 i++;
00162 }else{
00163 HexMode=TRUE;
00164 HexCount=0;
00165 continue;
00166 }
00167 }
00168 }
00169
00170 #ifdef DEBUGBUILD
00171 if ((*that) && (*that)->IsTerminal) printf("Terminal Node\n");
00172 #endif
00173 if (!*that){
00174 #ifdef DEBUGBUILD
00175 printf("Allocating a new child node for %c (%i)\n",NextChar, NextChar);
00176 #endif
00177 (*that)=calloc(sizeof(BNode),1);
00178 (*that)->byte=NextChar;
00179 this=(*that);
00180 that=&(*that)->Child;
00181 }else{
00182 while (*that){
00183 if ( (*that)->byte==NextChar){
00184 #ifdef DEBUGBUILD
00185 printf("Already had a \"%c\"\n",NextChar);
00186 #endif
00187 break;
00188 }else{
00189 #ifdef DEBUGBUILD
00190 printf("Wasn't that one \"%c\"\n", (*that)->byte);
00191 #endif
00192 that=&(*that)->NextPeer;
00193 }
00194 }
00195
00196 if (!(*that)){
00197 #ifdef DEBUGBUILD
00198 printf("Allocating a new peer node for %c (%i)\n",NextChar, NextChar);
00199 #endif
00200 (*that)=calloc(sizeof(BNode),1);
00201 (*that)->byte=NextChar;
00202 this=(*that);
00203 }
00204
00205
00206 if (i==Len-1) break;
00207
00208 that=&(*that)->Child;
00209 this=(*that);
00210 }
00211 }
00212 #ifdef DEBUGBUILD
00213 printf("this is \"%c\"\n",this->byte);
00214 #endif
00215 this->IsTerminal=TRUE;
00216 this->TerminalRuleID=RuleID;
00217
00218 return TRUE;
00219 }
00220
00221
00222
00223
00224
00225
00226 int MatchStringTree(BMTree* Tree, unsigned char* PacketRuleBits, char* Packet, int Plen){
00227 register int i;
00228 register int j;
00229 BNode* this;
00230 unsigned char LocalDepend[MAX_RULES/8];
00231 unsigned char ThisChar;
00232
00233 #ifdef DEBUGPATH
00234 printf("In MatchStringTree\n");
00235 #endif
00236
00237 memcpy(LocalDepend, Tree->TreeDependMask, MAX_RULES/8);
00238
00239 for (i=0;i<Plen;i++){
00240 j=0;
00241 this=Tree->TreeHead;
00242 while (this){
00243 if ( (j+i+1)>Plen){
00244 #ifdef DEBUG
00245 printf("I ran off the edge of the packet\n");
00246 #endif
00247 break;
00248 }
00249 if (Tree->IgnoreCase){
00250 ThisChar=tolower(Packet[j+i]);
00251 }else{
00252 ThisChar=Packet[j+i];
00253 }
00254 if (ThisChar==this->byte){
00255 if (this->IsTerminal){
00256 #ifdef DEBUG
00257 printf("Rule %i matches\n",this->TerminalRuleID);
00258 #endif
00259 SetBit(LocalDepend, Globals.NumRules, this->TerminalRuleID, 0);
00260 }
00261 this=this->Child;
00262 j++;
00263 }else{
00264 this=this->NextPeer;
00265 }
00266 }
00267 }
00268
00269 NotAndBitFields(PacketRuleBits, LocalDepend, PacketRuleBits, Globals.NumRules);
00270
00271 return TRUE;
00272 }
00273
00274
00275
00276
00277 void FreeTree(BMTree* tree){
00278 }
