System and method for generating identifiers for uniquely identifying object types for objects used in processing of object-oriented programs and the like

• US 5,815,709 A
• Filed: 04/23/1996
• Issued: 09/29/1998
• Est. Priority Date: 04/23/1996
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: San Microsystems Incorporated
• Inventors: Bharat, Krishna, Waldo, James H., Riggs, Roger
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Coulter, Kenneth R.
• Application Number:
  US08/636,707
• Time in Patent Office: 889 Days
• Field of Search: 395/683, 707/103
• US Class Current: 712/300
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 9/4488 Object-oriented

Abstract

A fingerprint generating system generates a fingerprint value for an object in an object-oriented programming arrangement. The object comprises a digital information stream and the fingerprint generating system generates a fixed-length fingerprint value from the digital information stream. The fingerprint generating system receives the digital information stream comprising the object and processes the digital information stream in accordance with a selected hash value generating algorithm to generate a hash value which comprises the fingerprint value. The hash value generating algorithm is selected from a class of hash value generating algorithms characterized in that:

i. in response to said input digital information stream, a digital hash value having a predetermined number of digital bits will be generated as an output;

ii. the digital hash value will be a function of the digital information stream, so that

(a) given two input streams that are identical, identical digital hash values will be generated; but

(b) given two input streams that are not identical, it is extremely unlikely that identical digital hash values will be generated; and

iii. when the object, as a "referencing object," includes a reference to another object, as a referenced object, the input digital information stream of the referencing object can include a fingerprint which had been previously generated for the referenced object, rather than a digital information stream for referenced object itself,

the digital hash value generated according to the selected hash value generating algorithm comprising the fingerprint generated by said fingerprint generating system.

Claims

1. A fingerprint generating system for use generating a fingerprint value for an object in an object-oriented programming arrangement, the object comprising a digital information stream, the fingerprint generating system comprising:

A. a receiver for receiving the digital information stream comprising the object;

B. an object fingerprint value generator for processing the digital information stream in accordance with a selected hash value generating algorithm, the hash value generating algorithm being selected from a class of hash value generating algorithms characterized in that;

i. in response to said input digital information stream, a digital hash value having a predetermined number of digital bits will be generated as an output;

ii. the digital hash value will be a function of the digital information stream, so that

(a) given two input streams that are identical, identical digital hash values will be generated;

but

(b) given two input streams that are not identical, it is extremely unlikely that identical digital hash values will be generated; and

iii. when the object, as a "referencing object," includes a reference to another object, as a referenced object, the object fingerprint value generator can process the input digital information stream of the referencing object including a referenced object fingerprint generated for the referenced object, rather than a digital information stream associated with the referenced object,

the digital output value generated according to the selected hash value generating algorithm comprising the fingerprint generated by said fingerprint generating system.

2. A fingerprint generating system as defined in claim 1 in which said hash value generating algorithm is selected from said class of hash value generating algorithms further characterized in that it is extremely unlikely that the digital input stream can be reproduced from the digital output value.

3. A fingerprint generating system as defined in claim 2 in which said object fingerprint value generator processes the digital information stream in accordance with a selected hash value generating algorithm identified as NIST SHA available from the National Institute of Science and Technology.

4. A fingerprint generating system as defined in claim 2 in which said object fingerprint value generator processes the digital information stream in accordance with a selected hash value generating algorithm identified as an RC4 Secure Hash Algorithm available from RSA, Inc.

5. A fingerprint generating system as defined in claim 2 in which said object fingerprint value generator processes the digital information stream in accordance with a selected hash value generating algorithm identified as an RC5 Secure Hash Algorithm available from RSA, Inc.

6. A fingerprint generating system as defined in claim 1 in which said object includes at least one reference to a referenced object, the object fingerprint value generator including:

A. a referenced object fingerprint availability determination element for determining whether it has a referenced object fingerprint for said referenced object, and

B. a referenced object processing element responsive to a positive determination by said referenced object fingerprint availability determination element for processing the referenced object fingerprint in accordance with the selected hash value generating algorithm.

7. A fingerprint generating system as defined in claim 6 in which said object fingerprint value generator further includes a referenced object retrieval element for retrieving a referenced object digital information stream for said referenced object in response to a negative determination by said referenced object fingerprint availability determination element, said object fingerprint value generator processing the referenced object digital information stream in accordance with a said selected hash value generating algorithm to generate said referenced object fingerprint.

8. A fingerprint generating system as defined in claim 7 in which the selected hash value generating algorithm used by said object fingerprint value generator to process the referenced object digital information stream comprises the same selected hash value generating algorithm used by the object fingerprint value generator to process the digital information stream.

9. A fingerprint generating system as defined in claim 6 in which said object includes a plurality of references each to respective ones of a plurality of referenced objects, the object fingerprint value generator further comprising a sort element for sorting said references according to a predetermined ordering, the referenced object fingerprint availability determination element and referenced object processing element operating in a series of iterations in connection with the series of references in said ordering.

10. A fingerprint generating system as defined in claim 1 in which said object comprises a plurality of elements, the fingerprint generating system further including a sort element for sorting portions of the digital information stream comprising the respective elements according to a selected sorted ordering to generate a sorted digital information stream, the object fingerprint value generator generating the digital hash value from the sorted digital information stream.

11. A fingerprint generating system as defined in claim 1 in which said object comprises a series of sections, the object fingerprint value generator sequentially processing the respective sections in series.

12. A fingerprint generating system as defined in claim 11 in which each section further comprises a plurality of elements, the fingerprint generating system further including a sort element for sorting portions of the digital information stream within each section comprising the respective elements according to a selected sorted ordering to generate a sorted digital information stream, the object fingerprint value generator generating the digital hash value from the sorted digital information stream.

13. A fingerprint generating method for use generating a fingerprint value for an object in an object-oriented program arrangement, the object comprising a digital information stream, the fingerprint generating method comprising the steps of:

A. receiving the digital information stream comprising the object;

B. processing the digital information stream in accordance with a selected hash value generating algorithm, the hash value generating algorithm being selected from a class of hash value generating algorithms characterized in that;

i. in response to said input digital information stream, a digital hash value having a predetermined number of digital bits will be generated as an output;

ii. the digital hash value will be a function of the digital information stream, so that

(a) given two input streams that are identical, identical digital hash values will be generated;

but

(b) given two input streams that are not identical, it is extremely unlikely that identical digital hash values will be generated; and

iii. when the object, as a "referencing object," includes a reference to another object, as a referenced object, the object fingerprint value generator can process the input digital information stream of the referencing object including a referenced object fingerprint generated for the referenced object, rather than a digital information stream associated with the referenced object,

the digital output value generated according to the selected hash value generating algorithm comprising the fingerprint.

14. A fingerprint generating method as defined in claim 13 in which said hash value generating algorithm is selected from said class of hash value generating algorithms further characterized in that it is extremely unlikely that the digital input stream can be reproduced from the digital output value.

15. A fingerprint generating method as defined in claim 14 in which, during said object fingerprint value generating step the digital information stream is processed in accordance with a selected hash value generating algorithm identified as NIST SHA available from the National Institute of Science and Technology.

16. A fingerprint generating method as defined in claim 14 in which, during said object fingerprint value generating step, the digital information stream is processed in accordance with a selected hash value generating algorithm identified as an RC4 Secure Hash Algorithm available from RSA, Inc.

17. A fingerprint generating method as defined in claim 14 in which, during said object fingerprint value generating step, the digital information stream is processed in accordance with a selected hash value generating algorithm identified as an RC5 Secure Hash Algorithm available from RSA, Inc.

18. A fingerprint generating method as defined in claim 13 in which said object includes at least one reference to a referenced object, the object fingerprint value generating step including the steps of:

A. determining whether a referenced object fingerprint is provided for said referenced object, and

B. responsive to a positive determination during said referenced object fingerprint availability determination step, processing the referenced object fingerprint in accordance with the selected hash value generating algorithm.

19. A fingerprint generating method as defined in claim 18 in which said object fingerprint value generation step further includes the step of retrieving a referenced object digital information stream for said referenced object in response to a negative determination by said referenced object fingerprint availability determination element, and processing the referenced object digital information stream in accordance with a said selected hash value generating algorithm to generate said referenced object fingerprint.

20. A fingerprint generating method as defined in claim 19 in which, during the selected hash value generating step, the same selected hash value generating algorithm is used to process the referenced object digital information stream as is used to process the digital information stream.

21. A fingerprint generating method as defined in claim 18 in which said object includes a plurality of references each to respective ones of a plurality of referenced objects, the object fingerprint value generation step further comprising the step of sorting said references according to a predetermined ordering, the referenced object fingerprint availability determination step and referenced object processing step being performed in a series of iterations in connection with the series of references in said ordering.

22. A fingerprint generating method as defined in claim 13 in which said object comprises a plurality of elements, the fingerprint generating method further including the step of sorting portions of the digital information stream comprising the respective elements according to a selected sorted ordering to generate a sorted digital information stream, the digital hash value being generated from the sorted digital information stream.

23. A fingerprint generating method as defined in claim 13 in which said object comprises a series of sections, the object fingerprint value generation step including the step of sequentially processing the respective sections in series.

24. A fingerprint generating method as defined in claim 23 in which each section further comprises a plurality of elements, the fingerprint generating method further including the step of sorting portions of the digital information stream within each section comprising the respective elements according to a selected sorted ordering to generate a sorted digital information stream, the digital hash value being generated from the sorted digital information stream.

25. A fingerprint generating computer program product for use in controlling a computer to generate a fingerprint value for an object in an object-oriented programming arrangement, the object comprising a digital information stream, the fingerprint generating computer program product comprising a machine-readable medium having encoded thereon:

A. receiver code devices for enabling said computer to receive the digital information stream comprising the object;

B. object fingerprint value generator code devices for enabling said computer to process the digital information stream in accordance with a selected hash value generating algorithm, the hash value generating algorithm being selected from a class of hash value generating algorithms characterized in that;

i. in response to said input digital information stream, a digital hash value having a predetermined number of digital bits will be generated as an output;

ii. the digital hash value will be a function of the digital information stream, so that

(a) given two input streams that are identical, identical digital hash values will be generated;

but

(b) given two input streams that are not identical, it is extremely unlikely that identical digital hash values will be generated; and

iii. when the object, as a "referencing object," includes a reference to another object, as a referenced object, the object fingerprint value generator can process the input digital information stream of the referencing object including a referenced object fingerprint generated for the referenced object, rather than a digital information stream associated with the referenced object,

the digital output value generated according to the selected hash value generating algorithm comprising the fingerprint generated by said fingerprint generating system.

26. A fingerprint generating computer program product as defined in claim 25 in which said hash value generating system is selected from said class of hash value generating algorithms further characterized in that it is extremely unlikely that the digital input stream can be reproduced from the digital output value.

27. A fingerprint generating computer program product as defined in claim 26 in which said object fingerprint value generator code devices enable said computer to process the digital information stream in accordance with a selected hash value generating algorithm identified as NIST SHA available from the National Institute of Science and Technology.

28. A fingerprint generating computer program product as defined in claim 26 in which said object fingerprint value generator code devices enable said computer to process the digital information stream in accordance with a selected hash value generating algorithm identified as an RC4 Secure Hash Algorithms available from RSA, Inc.

29. A fingerprint generating computer program product as defined in claim 26 in which said object fingerprint value generator code devices enable said computer to process the digital information stream in accordance with a selected hash value generating algorithm identified as an RC5 Secure Hash Algorithms available from RSA, Inc.

30. A fingerprint generating computer program product as defined in claim 25 in which said object includes at least one reference to a referenced object, the object fingerprint value generator code devices including:

A. referenced object fingerprint availability determination code devices for enabling said computer to determine whether it has a referenced object fingerprint for said referenced object, and

B. referenced object processing code devices for enabling said computer, responsive to a positive determination by said referenced object fingerprint availability determination element, to process the referenced object fingerprint in accordance with the selected hash value generating algorithm.

31. A fingerprint generating computer program product as defined in claim 30 in which said object fingerprint value generator code devices further include referenced object retrieval code devices for enabling said computer to retrieve a referenced object digital information stream for said referenced object in response to a negative determination during processing of said referenced object fingerprint availability determination code devices, said object fingerprint value generator code devices processing the referenced object digital information stream in accordance with a said selected hash value generating algorithm to generate said referenced object fingerprint.

32. A fingerprint generating computer program product as defined in claim 31 in which the selected hash value generating algorithm used by during processing of said object fingerprint value generator code devices to process the referenced object digital information stream comprises the same selected hash value generating algorithm used during processing of the object fingerprint value generator code devices to process the digital information stream.

33. A fingerprint generating computer program product as defined in claim 30 in which said object includes a plurality of references each to respective ones of a plurality of referenced objects, the object fingerprint value generator code devices further comprising a sort element for enabling said computer to sort said references according to a predetermined ordering, the referenced object fingerprint availability determination code devices and referenced object processing code devices controlling said computer to operate in a series of iterations in connection with the series of references in said ordering.

34. A fingerprint generating computer program product as defined in claim 25 in which said object comprises a plurality of elements, the fingerprint generating computer program product further including sort code devices for enabling the computer to sort portions of the digital information stream comprising the respective elements according to a selected sorted ordering to generate a sorted digital information stream, the object fingerprint value generator code devices enabling aid computer to generate the digital hash value from the sorted digital information stream.

35. A fingerprint generating computer program product as defined in claim 25 in which said object comprises a series of sections, the object fingerprint value generator code devices enabling said computer to sequentially process the respective sections in series.

36. A fingerprint generating computer program product as defined in claim 35 in which each section further comprises a plurality of elements, the fingerprint generating computer program product further including sort code devices for enabling said computer to sort portions of the digital information stream within each section comprising the respective elements according to a selected sorted ordering to generate a sorted digital information stream, the object fingerprint value generator code devices enabling the computer to generate the digital hash value from the sorted digital information stream.

37. A fingerprint generating system for use generating a fingerprint value for an object in an object-oriented programming arrangement, the object comprising a digital information stream, the fingerprint generating system comprising:

A. a computer; and

B. a control arrangement for controlling said computer, the control arrangement comprising;

i. a receiver module for enabling said computer to receive the digital information stream comprising the object;

ii. an object fingerprint value generation module for enabling said computer to processes the digital information stream in accordance with a selected hash value generating algorithm, the hash value generating algorithm being selected from a class of hash value generating algorithms characterized in that;

a. in response to said input digital information stream, a digital hash value having a predetermined number of digital bits will be generated as an output;

b. the digital hash value will be a function of the digital information stream, so that

(I) given two input streams that are identical, identical digital hash values will be generated;

but

(II) given two input streams that are not identical, it is extremely unlikely that identical digital hash values will be generated; and

c. when the object, as a "referencing object," includes a reference to another object, as a referenced object, the object fingerprint value generator can process the input digital information stream of the referencing object including a referenced object fingerprint generated for the referenced object, rather than a digital information stream associated with the referenced object,

the digital output value generated according to the selected hash value generating algorithm comprising the fingerprint generated by said fingerprint generating system.

38. A control arrangement for use in connection with a computer to facilitate generation of a fingerprint value for an object in an object-oriented programming arrangement, the object comprising a digital information stream, the control arrangement comprising:

A. a receiver module for enabling said computer to receive the digital information stream comprising the object;

B. an object fingerprint value generation module for enabling said computer to processes the digital information stream in accordance with a selected hash value generating algorithm, the hash value generating algorithm being selected from a class of hash value generating algorithms characterized in that;

i. in response to said input digital information stream, a digital hash value having a predetermined number of digital bits will be generated as an output;

ii. the digital hash value will be a function of the digital information stream, so that

(a) given two input streams that are identical, identical digital hash values will be generated;

but

(b) given two input streams that are not identical, it is extremely unlikely that identical digital hash values will be generated; and

ii. when the object, as a "referencing object," includes a reference to another object, as a referenced object, the object fingerprint value generator can process the input digital information stream of the referencing object including a referenced object fingerprint generated for the referenced object, rather than a digital information stream associated with the referenced object,

the digital output value generated according to the selected hash value generating algorithm comprising the fingerprint generated by said fingerprint generating system.

39. A system for distributing code stored on a computer readable medium and executable by a computer, the code including a plurality of modules each configured to control the computer to facilitate generation of a fingerprint value for an object in an object-oriented programming arrangement, the object comprising a digital information stream, the system comprising:

A. a receiver module for enabling said computer to receive the digital information stream comprising the object;

B. an object fingerprint value generation module for enabling said computer to processes the digital information stream in accordance with a selected hash value generating algorithm, the hash value generating algorithm being selected from a class of hash value generating algorithms characterized in that;

i. in response to said input digital information stream, a digital hash value having a predetermined number of digital bits will be generated as an output;

ii. the digital hash value will be a function of the digital information stream, so that

(a) given two input streams that are identical, identical digital hash values will be generated;

but

(b) given two input streams that are not identical, it is extremely unlikely that identical digital hash values will be generated; and

ii. when the object, as a "referencing object," includes a reference to another object, as a referenced object, the object fingerprint value generator can process the input digital information stream of the referencing object including a referenced object fingerprint generated for the referenced object, rather than a digital information stream associated with the referenced object,

the digital output value generated according to the selected hash value generating algorithm comprising the fingerprint generated by said fingerprint generating system.