Data processor with trie traversal instruction set extension

• US 6,175,915 B1
• Filed: 11/06/1998
• Issued: 01/16/2001
• Est. Priority Date: 08/11/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bahr, Raymond G., Cashman, John D., Ye, Wei, Riley, Paul M., Osler, Bruce P.
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US09/187,619
• Time in Patent Office: 802 Days
• Field of Search: 709/232, 709/236, 709/247, 712/300, 712/227, 712/209, 712/36, 712/42, 704/500-504, 341/50, 382/240, 379/93.08, 717/11
• US Class Current: 712/227
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A programmable data communications device is provided to process multiple streams of data according to multiple protocols. The device is equipped with a co-processor including multiple, programmable processors allowing data to be operated on by multiple protocols. The programmable processors within the co-processor include extended instruction sets including instructions providing the operations of zero stuffing, CRC computation, partial compare, conditional move, and trie traversal. These instructions allow the processor(s) of the co-processor to more efficiently execute programs implementing data communications protocols. Since each processor is programmable, protocols standards which change may be accommodated. A network device equipped with the co-processor can handle multiple simultaneous streams of data and can implement multiple protocols on each data stream. The protocols can execute within the co-processor either independently of each other, or in conjunction with each other.

Claims

1. A programmable multiple-protocol processor comprising:

an input receiving a first input data, a second input data, a third input data and a partial subtraction and conditional move instruction from a central computer;

a logic unit coupled to the input, the logic unit including activatible partial subtraction and conditional move circuitry which is activated upon receipt of the partial subtraction and conditional instruction and which performs a comparison between the first input data and the third input data, if the comparison results in the first input data being equal to the third input data then a down traversal state is set, if the comparison results in the first input data being greater than the third input data then the second input data is copied into a predefined location and no state is set, if the comparison results in the first input data being less than the third input data then an insertion state is set and the first input data is inserted into a trie data structure;

an output coupled to the logic unit, the output outputting the third input data in a predefined location, storing the first input data into the trie data structure and maintaining the down traversal state and the insertion state information; and

wherein the processor can be reprogrammed by the central computer to execute a different instruction.

2. The processor of claim 1 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform compression on the data.

3. The processor of claim 1 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform decompression on the data.

4. The processor of claim 1 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform encryption on the data.

5. The processor of claim 1 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform decryption on the data.

6. An apparatus comprising a computer readable medium having a partial subtraction and conditional move instruction recorded thereon.

7. A method of processing data in a processor comprising the steps of:

receiving a first input data, a second input data, a third input data and a partial subtraction and conditional move instruction at a logic unit;

activating a partial subtraction and conditional move circuitry upon receipt of the partial subtraction and conditional instruction;

comparing the first input data and the third input data;

if the comparison results in the first input data being equal to the third input data setting a down traversal state;

if the comparison results in the first input data being greater than the third input data then coupling the second input data into a predefined location and no state is set;

if the comparison results in the first input data being less than the third input data then setting an insertion state and inserting the first input data into a trie data structure;

outputting the third input data in the predefined location, storing the first input data into the trie data structure and maintaining the down traversal state and the insertion state information; and

reprogramming the processor to execute a different instruction.

8. The method of claim 7 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform compression on the data.

9. The method of claim 7 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform decompression on the data.

10. The method of claim 7 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform encryption on the data.

11. The method of claim 7 wherein the partial subtraction and conditional move instruction executes on the logic unit as part of a protocol to perform decryption on the data.