              TABLE 1                                                     ______________________________________                                            P    11x                                                                  P'.sub.sub                                                                     111                                                                  P'.sub.sup                                                                     1xx                                                                  P'.sub.ind                                                                     1x1                                                                  P'.sub.exc                                                                     0xx                                                          ______________________________________

By exploiting the known relationships among the various patterns, the number of comparisons in a pattern matching exercise can be greatly reduced. For example, in a scenario where there are 9 patterns having 16 words per pattern, there need only be 9+16=25 comparisons in the average worst case comparison scenario. However, where the patterns are independent of each other, the absolute worst case comparison scenario, although far less common, still requires 9*16=144 comparisons.

Pattern Relationship Analysis Details--FIG. 4

FIG. 4 illustrates the operational details of the pattern relationship analysis steps 400 in flow diagram form. The pattern relationship analysis steps 400 begin atstep 408 and are the details ofstep 225 from FIG. 2. Atstep 415, P1 and P2 are set to the pattern bits for word W of the patterns P and P' respectively. Similarly, M1 and M2 are set to the mask bits that correspond to the patterns P and P' respectively. The remainingsteps 420 through 460 identify the type of relationship that exists between the present patterns P and P' and that relationship is cataloged and stored in a memory for future use in the code generating steps disclosed in the text accompanying FIGS. 5-6.

Note that each bit in a pattern P has a corresponding bit in a mask M due to the difficulty in representing any one of three pattern states with a single bit. In theory, there are three states that are represented by a given pattern bit that include a 1, 0, and x, where x represents a "don't care" bit. However in practice because any bit by itself can only be either a 1 or a 0, representing a "don't care" state requires a mask bit that corresponds to each pattern bit. Thus, referring to a three bit pattern as "one, one, don't care", requires viewing the first three bits of the pattern "111 " and the first three bits of the corresponding mask "110" where a 0 mask bit represents a "don't care" pattern bit position and a 1 mask bit represents a "care" or "as stated" pattern bit position. In other words, in the above example it does not matter if the third bit in the pattern "111" is a 1 or a 0 because the third bit in the mask "110" indicates that the third pattern bit can be ignored as a "don't care."

If it is determined atdecision step 420 that the result of ANDing P1, M1 and M2 does not equal the result of ANDing P2, M1 and M2, then pattern P is a mutually exclusive relationship with pattern P' and processing continues atstep 468. Alternatively if it is determined atdecision step 420 that the result of ANDing P1 and M1 does equal the result of ANDing P2 and M2, then processing continues atstep 428.

If it is determined atdecision step 428 that M1 is equal to M2, then pattern P is an identical relationship to the pattern P' and processing continues atstep 468. Alternatively, if it is determined at decisions step 428 that M1 is not equal to M2, then processing continues atstep 440.

If it is determined atdecision step 440 that the result of ANDing M1 and M2 is equal to M2 itself, then pattern P is a subset relationship of P' and processing continues atstep 468. Alternatively, if it is determined atdecision step 440 that the result of ANDing M1 and M2 is not equal to M1 itself, then processing continues atstep 450.

If it is determined atdecision step 450 that the result of ANDing M1 and M2 is equal to M1 itself, then pattern P is a superset relationship of P' and processing continues atstep 468. Alternatively, if it is determined atdecision step 450 that the result of ANDing M1 and M2 is not equal to M2 itself, then processing continues atstep 460. If processing reachesstep 460 then the relationship between pattern P and pattern P' is an independent relationship and processing continues atstep 468.

Generating Pattern Matching Code--FIGS. 5-6

FIG. 5 illustrates an operational overview of thecode generating steps 500 in flow diagram form. Thecode generating steps 500 dynamically generate operational machine code that can be run as the improved pattern matching feature for theprotocol analyzing system 130. Key to the generated code is that it embodies the most advantageous characteristics of the pattern relationships previously identified. Specifically, the resulting generated code is a custom designed function or subroutine that takes full advantage of the pattern relationships toward an end of minimizing the number of comparisons that are required at pattern matching run time between input frame data and any one pattern.

For example, the generated code is ideally based on pattern relationships such that comparing a pattern P1 to any set of input data immediately includes or rules out the need to compare some number of subsequent related patterns P2-P3. Ruling out unnecessary pattern and input data comparisons is most effectively realized if pattern P1 is a pattern that has no subsets. That is, if P1 is a subset of P2, and P2 is a subset of P3, then ruling out P1 as a match with a given input data by definition rules out P2 and P3. Similarly, a match with P1 means that at least P2 must then be compared and so on. However, each comparison is on a word by word basis between a pattern and an input data. This means that the best pattern to use for matching with a given word of input data may change from one word to the next depending on the pattern relationships that exist for each word in each pattern. Using this approach, the greatest number of matches that are required on the average is the sum of the number of patterns and the number of words per pattern. Alternatively, if P1, P2 and P3 are patterns with no supersets, then the generated code is constructed to continue comparing each word of each pattern until no match is found which could be a worst case scenario.

Thecode generating steps 500 begin atstep 508 and are the details ofstep 256 from FIG. 2. Atstep 515, variable Pset represents the set of patterns for which code will be generated, and W represents the present word number of the input data to be tested, which starts atword 0 the first word, and proceeds through to MAX_-- WORDS. The variable Return_-- Addr represents the address or symbolic address to which the run-time function will return when it exits.

If it is determined atdecision step 521 that the set Pset is an empty set, then the program instruction GOTO Return_-- Addr is generated atstep 528 and the code generating process is complete atstep 570. Alternatively, if it is determined atdecision step 521 that the set Pset is not an empty set, then processing continues atstep 535. Atstep 535, the operational variables are set that are required for a successful call to the compare code generating steps of FIG. 6. The variable P is set to a pattern P in Pset that has no subset patterns. The variable P_ind represents the set of patterns in Pset that are independent of P. The variable Psucc_-- matches represents the patterns in Pset that are identical to or are supersets of P, and these are the set of patterns that may match the input data that matches P itself. The variable Psucc₁₃ rules_-- out represents the patterns in Pset that are exclusive of P, and these are the patterns that cannot match the input data if the input data matches P. The variable Pfail_-- matches represents the patterns in Pset that are exclusive to or are supersets of P, and are the set of patterns that may match the input data it the input data does not match P. The variable Pfail_-- rules_-- out represents the patterns in Pset that are identical to P, and these are the set of patterns that cannot match the input data if the input data does not match P. And finally, the variable Fail_-- code_-- Loc represents the location where code will be generated if the input data does not match P, and the variable Indep_-- Code_-- Loc represents the location of program code where independent patterns are handled. Atstep 540, the above identified variables are included in a call to the compare code generating steps that are detailed in FIG. 6.

If it is determined atdecision step 542 that the present word number index W is equal to the maximum number of words in a pattern MAX_-- WORDS, then this is the last word on which a comparison is performed so a branch program instruction is generated to GOTO Return_-- Loc atstep 550 and processing continues atstep 560. Alternatively, if it is determined atdecision step 542 that the present word number index W is not equal to the maximum number of words in a pattern MAX_-- WORDS, then subsequent comparisons can occur so processing continues to step 556.

Steps

556, 560, and 566 are recursive calls thecode generating steps 500 to continue generating code for special case situations. Atstep 556, thecode generating steps 500 are recursively called to generate code to test the next word of input data against the set, for the set of patterns represented by the variable Psucc_-- matches. Similarly, atstep 560 thecode generating steps 500 are recursively called to generate code for the set of patterns represented by the variable Pfail_-- matches. And finally, atstep 566 thecode generating steps 500 are recursively called to generate code for the set of patterns represented by the variable P_ind. When processing is complete from all recursive calls to thecode generating steps 500, processing continues atstep 570. FIG. 6 illustrates details of the comparisoncode generating steps 600 in flow diagram form. The comparisoncode generating steps 600 begin atstep 608 and are the details ofstep 540 from FIG. 5. Note that depending on the programming language and detail of the program code being generated, one or more program language instructions may be generated for any of the following steps.

Atstep 615, a program instruction is generated to load word W of the input frame data into a register or memory location so that the data can be compared to a pattern. Atstep 621, a program instruction is generated to perform an AND of the word W of the mask of pattern P against the corresponding word of the input data, to mask off any "don't care" bits.

Atstep 628, a program instruction is generated to compare word W of pattern P with word W of the input frame data. Atstep 635, a program instruction is generated for the condition where result of the pattern and data comparison is not equal or otherwise failed to match, so that the patterns in the set Pfail_-- rules_-- out are eliminated from the set of patterns that must be subsequently compared to the input frame data. Atstep 648, a program instruction is generated to branch to Fail_-- Code_-- Loc if the result of the pattern and data comparison is not equal or otherwise failed to match.

Atstep 655, an AND program instruction is generated to eliminate the patterns in the set Psucc_-- rules_-- out because pattern P was a match therefore none of the set Psucc_-- rules_-- out can match. Processing continues atstep 660.

The overall logic of the pattern matching code that is generated by the steps in FIGS. 5-6 can be summarized in the following manner for each comparison that is done to compare a word of input frame data with a word of pattern P. Once a comparison is complete, if there is a match then all patterns exclusive to P deleted because they are not needed for future comparisons and comparisons of remaining patterns will continue. Alternatively, if there is not a match, then all patterns identical to P are deleted because they are not needed for future comparisons and comparisons of remaining patterns independent of P will continue.

Note that the ideal pattern to use in the comparisons is a pattern P that has no subsets so that the maximum number of comparisons required to compare input data to a given pattern is at most the sum of the number of patterns and the number of words in each pattern, assuming no independent patterns exist. Further, additional efficiencies can be built into preparing to execute the code generated code by the present invention. One efficiency includes the application of a mask to its pattern prior to run-time to identify or eliminate pattern bits that are "don't care" bits. Another efficiency includes identifying words of a pattern that contain all don't care bits because it is not necessary to compare such a word to anything because a match will always result.

Finally, the code generated by the present invention is an unrolled recursive call tree, and branches are used in the code rather than subroutine calls where ever possible to enhance run-time performance of the generated code. The choice to generate the unrolled recursive call tree code during pattern configuration is a performance optimization. An alternative implementation could choose to use run-time recursion, accepting whatever performance penalties occur. Such an alternative run-time recursive function would look similar to the function disclosed in the pseudo-code example below. The functions in the pseudo-code example that include no_-- subsets, supersets, exclusive, identical, and independent, are called by the recursive function used to generate the pattern relationship database that was constructed during the pattern relationship analysis steps disclosed in the text accompanying FIG. 2.

______________________________________                                    Pseudo-Code Example                                                       ______________________________________                                    matching.sub.-- patterns                                                  find.sub.-- pattern.sub.-- matches (input, patterns, wordnum)             /*                                                                        * Parameters:                                                             *   input - input data to be matched against patterns                     *   patterns - set of patterns to test against input                      *   wordnum - word to start matching against [0                           .MAX.sub.-- PATTERN.sub.-- WORDS]                                         * Return value:                                                           *   Those patterns in `patterns` matching `input` from `wordnum` on.      */                                                                        if ( emptyset (patterns) )                                                /* No patterns to test for matches */                                     return patterns;                                                          if ( wordnum >= MAX.sub.-- PATTERN.sub.-- WORDS )                         /* All words of patterns matched, no more words */                        return patterns                                                           P = member.sub.-- of (patterns) && no.sub.-- subsets (P, patterns)        if ( matches (input, P, wordnum))                                         /* P matches => all its supersets also match */                           matching.sub.-- patterns =                                                find.sub.-- pattern.sub.-- matches (input, identical (P) OR supersets     (P),wordnum+1))                                                           else                                                                      /* P doesn't match, exclusive and supersets may match */                  matching.sub.-- patterns =                                                find.sub.-- pattern.sub.-- matches(input, superset(P) OR exclusive(P),    wordnum)                                                                  /* Look for matches of independent patterns */                            matching.sub.-- patterns |= find.sub.-- pattern.sub.-- matches   (input, independent(P),                                                   wordnum)                                                                  return matching.sub.-- patterns;                                          }                                                                         ______________________________________

Working Example--FIG. 7

FIG. 7 illustrates a Venn diagram 700 of pattern relationships for purposes of a working example of the code generating system for improved pattern matching of the present invention. The Venn diagram 700 includes the universe of allinput frame data 710, and threepatterns P1 720,P2 730, andP3 740.Pattern P1 720 is a superset ofP2 730, or conversely,P2 730 is a subset ofP1 720. In either case,pattern P3 740 is exclusive of both patterns P1 and P2. For purposes of example only, assume that the patterns for P1, P2, and P3 are those illustrated in Table 2.

              TABLE 2                                                     ______________________________________                                    P1 = 1xxxx                                                                P2 = 11xxx                                                                P3 = 0xxxx                                                                ______________________________________

Assuming for example purposes that the pattern relationship analysis is complete so that the relationships are known as stated above, the pattern relationship analysis of FIGS. 2 and 4 would look like the following in terms of a notation of Pn.w where n is the pattern number and w is the word index number within the pattern. For the present example the word number is 0 due to the minimal length of the present example for simplicity purposes. The results of the relationship analysis are stored in a cleared memory and more specifically can be stored as a database of relationships.

Step 1--Analyze Pattern Relationships

a. Compare P1.0 with P2.0 and record relationship that P2.0 is a subset of P1.0.

b. Compare P1.0 with P3.0 and record relationship that P3.0 is exclusive of P1.0.

c. Compare P2.0 with P3.0 and record relationship that P3.0 is exclusive of P2.0.

Executing the code generating steps disclosed in the text accompanying FIGS. 5-6 would look like the following the patterns listed in Table 2 and based on the previously identified pattern relationships as discussed instep 1 above.

Step 2--Generate Code

a. Call Generate_-- Code with a Pset of (P1, P2, P3) and word=0.

b. Find a pattern in Pset having no subsets, starting with P1.

P2 is a subset of P1 so P1 is no good.

Next look at P2.

P2 has no subsets so P2 is chosen as the starting pattern.

c. Set Pind to the empty set, since P2 has no independent patterns.

Set Psucc_-- matches to (P1, P2).

Set Psucc_-- rules out to (P3).

Set Pfail_-- matches to (P1, P3)

(i.e. if P2 fails to match then P1 or P3 may still match)

Set Pfail_-- rules_-- out to (P2).

d. Call Generate_-- Compare_-- Code.

Generate a load instruction for the 1st word of input data.

Generate an AND instruction to mask off all "don't care" bits in P2

Generate a COMPARE instruction to compare the masked input data with the patterns bits for P2.

Generate an ANDNE instruction to remove P2 from the set of matching patterns if the COMPARE result is not equal (NE).

Generate a BNE instruction to branch to the code executed when P2 does not match.

Generate an AND instruction to delete P3 from the set of matching patterns since P2 matched and P3 is exclusive of P2).

e. Does W==MAXWORDS?

YES==>Generate a GOTO Return_-- Loc which is the location of the caller of the pattern match function.

f. Call Generate_-- Code recursively to generate code for the case where P2 does not match the input data.

Pset is set to Pfail_-- matches (P1, P3).

W=0.

g. Find another pattern in Pset with no subsets, starting with P1.

P1 has no subset in Pset.

h. Pind is set to the empty set since P1 has no independent patterns.

Set Psucc_-- matches to (P1).

Set Psucc_-- rules_-- out to (P3).

Set Pfail_-- matches to (P3).

Set Pfail_-- rules_-- out to (P1).

i. Call Generate_-- Compare_-- Code.

Generate a LOAD instruction for the 1st word of input data.

Generate an AND instruction to mask off all "don't care" bits in P1.

Generate a COMPARE instruction to compare the masked input data with the pattern bits for P1.

Generate an ANDNE instruction to remove P1 from the set of matching patterns if the COMPARE result is not equal (NE).

Generate a BNE instruction to branch to the code to execute when P1 does not match.

Generate an AND instruction to delete P3 from the set of matching patterns.

j. Does W==MAXWORDS?

YES==>Generate a GOTO Return_-- Loc.

k. Call Generate_-- Code recursively to generate code for the case where P1 does not match.

Pset is Pfail_-- matches (P3).

W=0.

l. Find a pattern in Pset with no subsets, starting with P3.

P3.0 has no subset in Pset.

m. Pind is set to the empty set, since P3 has no independent patterns.

Set Psucc_-- matches to (P3).

Set Psucc_-- rules_-- out to the empty set.

Set Pfail_-- matches to the empty set.

Set Pfail_-- rules_-- out to (P3).

n. Call Generate_-- Compare_-- Code.

Generate a LOAD instruction for the 1st word of input data.

Generate an AND instruction to mask off all "don't care" bits in P3.

Generate a COMPARE instruction to compare the masked input data with the pattern bits for P3.

Generate an ANDNE instruction to remove P3 from the set of matching patterns if the COMPARE result is not equal (NE).

Since the set of patterns to look for when P3 does not match is the empty set, no BNE or AND instruction is generated.

o. Does W==MAXWORDS?

YES==>Generate a GOTO Return_-- Loc.

p. Call Generate_-- Code for Pind, which is the empty set, until all code is generated.

q. The recursive calls start to return, no additional code is generated because each return includes an empty set for Pind.

Summary

The code generating system for improved pattern matching of the present invention includes the analysis of patterns to determine pattern relationships therebetween, and the dynamic generating of pattern matching code based on the known relationships so that the number of comparisons between input frame data and patterns is minimized. Although specific embodiments of the present invention are disclosed herein, it is expected that persons skilled in the art can and will design alternative code generating systems for improved pattern matching that are within the scope of the following claims either literally or under the Doctrine of Equivalents.