Parallel string processor and method for a minicomputer

• US 5,073,864 A
• Filed: 02/12/1990
• Issued: 12/17/1991
• Est. Priority Date: 02/10/1987
• Status: Expired due to Fees

• Current Assignee: Davin Computer Corporation
• Original Assignee: Davin Computer Corporation
• Inventors: Methvin, David H., Un, Chong S.
• Primary Examiner(s): Shaw, Dale M.
• Application Number:
  US07/478,844
• Time in Patent Office: 673 Days
• Field of Search: 340/146.2, 364/715.09-715.11
• US Class Current: 708/212
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06F 7/74 Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders with shifting G06F5/01
• CPC Class Codes: G06F 9/30018 Bit or string instructions

Abstract

A processor is disclosed for use in a computer system for comparing a number of bytes simultaneously in order to locate a control character in a string of data. The processor includes a register for holding the data bytes, a register for storing the control characters, a comparison circuit for simultaneously comparing the bytes of the first register with the bytes of the second register, and a circuit for generating indicator bits when a match has been found between the two registers. Microcode instructions cause the system to branch to a predetermined memory location when the control character has been located and to branch to a second predetermined memory location when no control character is found in the data string. The parallel string processor includes a circuit which finds the indicator bits generated from the circuit which have a predetermined characteristic and thus identifies the position of a particular byte (e.g., control character) in the data word that has the selected predetermined characteristic. A number of different operations can be performed based upon the output of the circuit to accomplish in one instruction operations that previously required a large number of instruments.

Claims

1. A parallel byte string processor that finds the location of matching bytes in first and second data words, each data word having a predetermined number of data bytes, said parallel byte processor comprising:

a first circuit that performs an exclusive-OR operation on said first and second data words on a byte-by-byte basis, and provides an output bit corresponding to each byte of said first data word, each said output bit having first and second logic levels such that an output bit has said first logic level when the corresponding byte in said first data word matches the corresponding byte in said second data word and has said second logic level when the corresponding byte in said first data word does not match the corresponding byte in said second data word; and

a second circuit that receives said output bits from said first circuit, said second circuit providing a digital output value that identifies the location of an output bit from said first circuit that has a predetermined positional characteristic with respect to the other output bits from said first circuit, said identified bit indicating the location of a byte in said first data word that has a selected matching or non-matching characteristic with respect to the byte in the corresponding location of said second data word.

2. The parallel byte processor as defined in claim 1, wherein said second circuit comprises a programmable read only memory.

3. The parallel byte processor as defined in claim 1, further including means to perform a multi-way conditional branch upon identifying the most significant byte of said first data word that matches the corresponding byte of said second data word.

4. The parallel byte processor as defined in claim 1, further including means to perform a multi-way conditional branch upon identifying the most significant byte of said first data word that does not match the corresponding byte of said second data word.

5. The parallel byte processor as defined in claim 1, further including means to clear the byte positions in said first data word from the location of the most significant byte of said first data word that matches the corresponding byte of said second data word to the least significant byte of said first data word.

6. The parallel byte processor as defined in claim 1, further including means to clear the byte positions of said first data word from the most significant byte of said first data word up to the location of the most significant byte of said first data word that matches the corresponding byte of said second data word.

7. The parallel byte processor as defined in claim 1, further including means to clear the most significant byte of said first data word that matches the corresponding byte of said second data word.

8. The parallel byte processor as defined in claim 1, further including means to clear the byte positions of said first data word from the location of the most significant byte of said first data word that does not match the corresponding byte of said second data word to the least significant byte of said first data word.

9. The parallel byte processor as defined in claim 1, further including means to clear the byte positions of said first data word from the most significant byte of said first data word up to the location of the most significant byte of said first data word that does not match the corresponding byte of said second data word.

10. The parallel byte processor as defined in claim 1, further including means to clear the most significant byte of said first data word that does not match the corresponding byte of said second data word.

11. The parallel byte processor as defined in claim 1, further including means to clear the output bit from said first circuit corresponding to the location of the most significant byte of said first data word that matches the corresponding byte of said second data word.

12. The parallel byte processor as defined in claim 1, further including means to clear the output bit from said first circuit corresponding to the location of the most significant byte of said first data word that does not match the corresponding byte of said second data word.

13. A parallel byte string processor that finds the location of matching bytes in first and second data words, each data word having a predetermined number of data bytes, said parallel byte processor comprising:

a first circuit that performs an exclusive-OR operation on said first and second data words on a byte-by-byte basis, and provides an output bit corresponding to each byte of said first data word, each said output bit having first and second logic levels such that an output bit has said first logic level when the corresponding byte in said first data word matches the corresponding byte in said second data word and has said second logic level when the corresponding byte in said first data word does not match the corresponding byte in said second data word; and

a second circuit that receives said output bits from said first circuit, said second circuit providing a digital output value that identifies the location of an output bit from said first circuit that has a predetermined positional characteristic with respect to the other output bits from said first circuit which is the location of the most significant bit of said output bits having said first logic level, thus identifying the most significant byte of said first data word that matches the corresponding byte of said second data word.

14. A parallel byte string processor that finds the location of matching bytes in first and second data words, each data word having a predetermined number of data bytes, said parallel byte processor comprising:

a first circuit that performs an exclusive-OR operation on said first and second data words on a byte-by-byte basis, and provides an output bit corresponding to each byte of said first data word, each said output bit having first and second logic levels such that an output bit has said first logic level when the corresponding byte in said first data word matches the corresponding byte in said second data word and has said second logic level when the corresponding byte in said first data word does not match the corresponding byte in said second data word; and

a second circuit that receives said output bits from said first circuit, said second circuit providing a digital output value that identifies the location of an output bit from said first circuit that has a predetermined positional characteristic with respect to the other output bits from said first circuit which is the location of the most significant bit of said output bits having said second logic level, thus identifying the most significant byte of said first data word that does not match the corresponding byte of said second data word.

15. A parallel byte string processor that finds the location of matching bytes in first and second data words, each data word having a predetermined number of data bytes, said parallel byte processor comprising:

a first circuit that performs an exclusive-OR operation on said first and second data words on a byte-by-byte basis, and provides an output bit corresponding to each byte of said first data word, each said output bit having first and second logic levels such that an output bit has said first logic level when the corresponding byte in said first data word matches the corresponding byte in said second data word and has said second logic level when the corresponding byte in said first data word does not match the corresponding byte in said second data word; and

a second circuit that receives said output bits from said first circuit, said second circuit providing a digital output value that identifies the location of an output bit from said first circuit that has a predetermined positional characteristic with respect to the other output bits from said first circuit which is the location of the most significant bit of said output bits having said first logic level that is less significant than a bit of said output bits having said second logic level, thus identifying the most significant byte of said first data word that does not match the corresponding byte of said second data word that is less significant than a byte of said first data word that matches the corresponding byte of said second data word.

16. A parallel byte string processor that finds the location of matching bytes in first and second data words, each data word having a predetermined number of data bytes, said parallel byte processor comprising:

a first circuit that performs an exclusive-OR operation on said first and second data words on a byte-by-byte basis, and provides an output bit corresponding to each byte of said first data word, each said output bit having first and second logic levels such that an output bit has said first logic level when the corresponding byte in said first data word matches the corresponding byte in said second data word and has said second logic level when the corresponding byte in said first data word does not match the corresponding byte in said second data word; and

a second circuit that receives said output bits from said first circuit, said second circuit providing a digital output value that identifies the location of an output bit from said first circuit that has a predetermined positional characteristic with respect to the other output bits from said first circuit which is the location of the most significant bit of said output bits having said second logic level that is less significant than a bit of said output bits having said first logic level, thus identifying the most significant byte of said first data word that matches the corresponding byte of said second data word that is less significant than a byte of said first data word that does not match the corresponding byte of said second data word.

17. A parallel byte string processor that finds the location of matching bytes in first and second data words, each data word having a predetermined number of data bytes, said parallel byte processor comprising:

a first circuit that performs an exclusive-OR operation on said first and second data words on a byte-by-byte basis, and provides an output bit corresponding to each byte of said first data word, each said output bit having first and second logic levels such that an output bit has said first logic level when the corresponding byte in said first data word matches the corresponding byte in said second data word and has said second logic level when the corresponding byte in said first data word does not match the corresponding byte in said second data word; and

a second circuit that receives said output bits from said first circuit, said second circuit providing a digital output value that identifies the location of an output bit from said first circuit that has a predetermined positional characteristic with respect to the other output bits from said first circuit, said identified bit indicating the location of a byte in said first data word that has a selected matching or non-matching characteristic with respect to the byte in the corresponding location of said second data word wherein said bit having said characteristic is the first of at least two adjacent bits having said characteristic.

18. A parallel byte string processor that finds the location of matching bytes in first and second data words, each data word having a predetermined number of data bytes, wherein said second data word comprises a plurality of identical bytes, said parallel byte processor comprising:

a first circuit that performs an exclusive-OR operation on said first and second data words on a byte-by-byte basis, and provides an output bit corresponding to each byte of said first data word, each said output bit having first and second logic levels such that an output bit has said first logic level when the corresponding byte in said first data word matches the corresponding byte in said second data word and has said second logic level when the corresponding byte in said first data word does not match the corresponding byte in said second data word; and

a second circuit that receives said output bits from said first circuit, said second circuit providing a digital output value that identifies the location of an output bit from said first circuit that has a predetermined positional characteristic with respect to the other output bits from said first circuit, said identified bit indicating the location of a byte in said first data word that has a selected matching or non-matching characteristic with respect to the byte in the corresponding location of said second data word; and

a replication circuit, said replication circuit receiving a single byte input and generating said predetermined number of bytes as outputs, each of said predetermined number of bytes being identical to said input byte.

19. A parallel byte string processor that performs a data manipulation operation on each of the bytes of a first multiple-byte data word having data of unknown content in said bytes and that finds the location of a byte in said first multiple-byte data word having a selected content characteristic and a selected positional characteristic with respect to other bytes in said first multiple-bytes data word, comprising:

a first circuit that provides an output signal for each byte of said first multiple-byte data word, wherein for each byte, the respective output signal has a first logic level when the byte has said selected content characteristic and has a second logic level when the byte does not have said selected content characteristic; and

a second circuit that receives the output signals from said first circuit, said second circuit providing a digital output value that identifies the location of an output signal from said first circuit that has a selected one of said first and second logic levels and that corresponds to a byte in said first multiple-byte data word having said selected positional characteristic.

20. The parallel byte processor as defined in claim 19, further including means to perform a multi-way conditional branch upon identifying the most significant byte of said first multiple-byte data word having said selected content characteristic.

21. The parallel byte processor as defined in claim 19, further including means to perform a multi-way conditional branch upon identifying the most significant byte of said first multiple-byte data word not having said selected content characteristic.

22. The parallel byte processor as defined in claim 19, further including means to clear the byte positions in said first multiple-byte data word from the location of the most significant byte of said first multiple-byte data word having said selected content characteristic to the least significant byte of said first multiple-byte data word.

23. The parallel byte processor as defined in claim 19, further including means to clear the byte positions of said first multiple-byte data word from the most significant byte of said first multiple-byte data word up to the location of the most significant byte of said first multiple-byte data word having said selected content characteristic.

24. The parallel byte processor as defined in claim 19, further including means to clear the most significant byte of said first multiple-byte data word having said selected content characteristic.

25. The parallel byte processor as defined in claim 19, further including means to clear the byte positions of said first multiple-type data word from the location of the most significant byte of said first multiple-byte data word not having said selected content characteristic to the least significant byte of said first multiple-byte data word.

26. The parallel byte processor as defined in claim 19, further including means to clear the byte positions of said first multiple-byte data word from the most significant byte of said first multiple-byte data word up to the location of the most significant byte of said first multiple-byte data work not having said selected content characteristic.

27. The parallel byte processor as defined in claim 19, further including means to clear the most significant byte of said first multiple-byte data word not having said selected content characteristic.

28. The parallel byte processor as defined in claim 19, further including means to clear the output bit from said first circuit corresponding to the location of the most significant byte of said first multiple-byte data word having said selected content characteristic.

29. The parallel byte processor as defined in claim 19, further including means to clear the output bit from said first circuit corresponding to the location of the most significant byte of said first multiple-byte data word not having said selected content characteristic.

30. A parallel byte string processor that performs a data manipulation operation on each of the bytes of a first multiple-byte data word and that finds the location of a byte in said first data word having a selected content characteristic and a selected positional characteristic with respect to other bytes in said first data word, comprising:

a first circuit that provides an output signal for each byte of said first data word, wherein for each byte, the respective output signal has a first logic level when the byte has said selected content characteristic and has a second logic level when the byte does not have said selected content characteristic; and

a second circuit that receives the output signals from said first circuit, said second circuit providing a digital output value that identifies the location of an output signal from said first circuit that has a selected one of said first and second logic levels and that corresponds to a byte in said first data word having said selected positional characteristic, and wherein said selected content characteristic of a byte in said first data word is equal to the corresponding byte of said second data word.

31. A parallel byte string processor that performs a data manipulation operation on each of the bytes of a first multiple-byte data word and that finds the location of a byte in said first data word having a selected content characteristic and a selected positional characteristic with respect to other bytes in said first data word, comprising:

a first circuit that provides an output signal for each byte of said first data word, wherein for each byte, the respective output signal has a first logic level when the byte has said selected content characteristic and has a second logic level when the byte does not have said selected content characteristic; and

a second circuit that receives the output signals from said first circuit, said second circuit providing a digital output value that identifies the location of an output signal from said first circuit that has a selected one of said first and second logic levels and that corresponds to a byte in said first data word having said selected positional characteristic, wherein said selected positional characteristic is the most significant byte having said selected content characteristic.

32. A parallel byte string processor that performs a data manipulation operation on each of the bytes of a first multiple-byte data word and that finds the location of a byte in said first data word having a selected content characteristic and a selected positional characteristic with respect to other bytes in said first data word, comprising:

a first circuit that provides an output signal for each byte of said first data word, wherein for each byte, the respective output signal has a first logic level when the byte has said selected content characteristic and has a second logic level when the byte does not have said selected content characteristic; and

a second circuit that receives the output signals from said first circuit, said second circuit providing a digital output value that identifies the location of an output signal from said first circuit that has a selected one of said first and second logic levels and that corresponds to a byte in said first data word having said selected positional characteristic, wherein said selected positional characteristic is the most significant byte not having said selected content characteristic.

33. A parallel byte string processor that performs a data manipulation operation on each of the bytes of a first multiple-byte data word and that finds the location of a byte in said first data word having a selected content characteristic and a selected positional characteristic with respect to other bytes in said first data word, comprising:

a first circuit that provides an output signal for each byte of said first data word, wherein for each byte, the respective output signal has a first logic level when the byte has said selected content characteristic and has a second logic level when the byte does not have said selected content characteristic; and

a second circuit that receives the output signals from said first circuit, said second circuit providing a digital output value that identifies the location of an output signal from said first circuit that has a selected one of said first and second logic levels and that corresponds to a byte in said first data word having said selected positional characteristic, wherein said selected positional characteristic is the most significant byte having said selected content characteristic that is less significant than the most significant byte not having said selected content characteristic.

34. A parallel byte string processor that performs a data manipulation operation on each of the bytes of a first multiple-byte data word and that finds the location of a byte in said first data word having a selected content characteristic and a selected positional characteristic with respect to other bytes in said first data word, comprising:

a first circuit that provides an output signal for each byte of said first data word, wherein for each byte, the respective output signal has a first logic level when the byte has said selected content characteristic and has a second logic level when the byte does not have said selected content characteristic; and

a second circuit that receives the output signals from said first circuit, said second circuit providing a digital output value that identifies the location of an output signal from said first circuit that has a selected one of said first and second logic levels and that corresponds to a byte in said first data word having said selected positional characteristic, wherein said selected positional characteristic is the most significant byte not having said selected content characteristic that is less significant than the most significant byte having said selected content characteristic.