Signature serialization

• US 20040244012A1
• Filed: 05/28/2003
• Published: 12/02/2004
• Est. Priority Date: 05/28/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Massarenti, Davide
• Granted Patent: US 7,404,186 B2
• Time in Patent Office: Days
• US Class Current: 719/319
• CPC Class Codes: G06F 9/4493 Object persistence

Abstract

One or more electronically-accessible media including electronically-executable instructions that direct an apparatus to perform actions including: inserting a type signature tag into a serialized binary blob to serialize an object, the type signature tag including a type signature based on an object type of the object; and transmitting the serialized binary blob. An arrangement including: a signature table having multiple entries, each respective entry of the multiple entries associating a respective object type with a respective type signature, each respective type signature created responsive to a structural representation of the respective object type associated therewith. An apparatus including: one or more media having electronically-executable instructions; and one or more processors capable of executing the electronically-executable instructions to perform actions including: receiving a serialized binary blob; and deserializing an object by extracting a type signature from the serialized binary blob, the type signature derivable from an object type of the object.

Claims

1. One or more electronically-accessible media comprising electronically-executable instructions that, when executed, direct an electronic apparatus to perform actions comprising:

inserting a type signature tag into a serialized binary blob to serialize an object, the type signature tag including a type signature based on an object type of the object; and

transmitting the serialized binary blob.

2. The one or more electronically-accessible media as recited in claim 1, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature using a hashing algorithm.

3. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 2, wherein the action of creating comprises the action of:

applying a hashing function that comprises a cyclic redundancy code with 32 bits (CRC

     32).

4. The one or more electronically-accessible media as recited in claim 1, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature responsive to a type name of the object type.

5. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 4, wherein the action of creating comprises the action of:

converting the type name of the object type to numerals using Unicode Transformation Format-8 (UTF-8).

6. The one or more electronically-accessible media as recited in claim 1, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature responsive to a prefix corresponding to a value field of the object type.

7. The one or more electronically-accessible media as recited in claim 1, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature responsive to a type name of a predecessor object type of the object type.

8. The one or more electronically-accessible media as recited in claim 1, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

inserting a prefix for a field into the serialized binary blob to serialize the object, the prefix corresponding to a particular element type of the field; and

inserting, after the prefix, information from the field.

9. The one or more electronically-accessible media as recited in claim 1, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

determining that a type of a field is atomic; and

responsive to the determining, inserting information from the field into the serialized binary blob to serialize the object without inserting a prefix corresponding to the type.

10. The one or more electronically-accessible media as recited in claim 1, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

receiving a clarification request that includes another type signature;

accessing a signature table using the another type signature;

ascertaining, responsive to the accessing, a structural representation of another object type that is associated with the another type signature; and

transmitting, responsive to the receiving, the structural representation of the another object type.

11. An apparatus comprising:

one or more media, the one or more media including electronically-executable instructions; and

one or more processors, the one or more processors capable of executing the electronically-executable instructions to perform actions comprising;

serializing an object by inserting a type signature into a serialized binary blob, the type signature created responsive to an object type of the object; and

transmitting the serialized binary blob.

12. The apparatus as recited in claim 11, wherein the type signature is further created responsive to a structural representation of the object type of the object.

13. The apparatus as recited in claim 11, wherein the action of transmitting comprises the action of:

transmitting the serialized binary blob over a communications channel from an originating entity.

14. The apparatus as recited in claim 11, wherein the action of serializing comprises the action of:

serializing a plurality of objects of a graph of objects by inserting a respective type signature into the serialized binary blob for each respective object of the plurality of objects, each respective type signature created responsive to each respective object type of each respective object of the plurality of objects.

15. The apparatus as recited in claim 11, wherein the one or more processors are capable of executing the electronically-executable instructions to perform a further action comprising:

serializing another object by inserting an index into the serialized binary blob, the index indicating a location of the object in a duplicate table, the another object referencing the object.

16. The apparatus as recited in claim 11, wherein the one or more processors are capable of executing the electronically-executable instructions to perform further actions comprising:

accessing a signature table using the object type of the object; and

ascertaining the type signature, which is associated with the object type, from the accessing.

17. The apparatus as recited in claim 11, wherein the one or more processors are capable of executing the electronically-executable instructions to perform a further action comprising:

providing an explanation of another object type responsive to a received clarification inquiry that includes another type signature, the another type signature associated with the another object type.

18. An apparatus comprising:

a signature table having a plurality of entries, each respective entry of the plurality of entries associating a respective object type with a respective type signature, each respective type signature created responsive to the associated respective object type; and

a serializer that is capable of serializing a graph of objects using the signature table.

19. The apparatus as recited in claim 18, wherein the graph of objects includes multidimensional linkages between and/or among objects of the graph of objects;

and wherein the serializer is adapted to transform the graph of objects into a serialized bit stream.

20. The apparatus as recited in claim 18, wherein the serializer is adapted to access the signature table using a particular object type of a particular object being serialized and to thereby ascertain a particular type signature that is associated with the particular object type.

21. The apparatus as recited in claim 20, wherein the serializer is further adapted to insert the particular type signature into a serialized bit stream.

22. The apparatus as recited in claim 18, wherein the serializer is adapted to recursively serialize objects of the graph of objects when the objects are referenced by other objects of the graph of objects.

23. The apparatus as recited in claim 18, wherein the serializer is adapted to omit prefixes for objects of object types that are implied by their relative position in a serialized bit stream produced by the serializer.

24. One or more electronically-accessible media comprising electronically-executable instructions that, when executed, direct an electronic apparatus to perform actions comprising:

determining whether at least one node remains on a list of nodes to process;

if it is determined in the determining action that at least one node remains on the list of nodes to process,

extracting a next node from the list of nodes to process;

emitting a type signature for the next node;

emitting at least one field from the next node; and

queuing at least one object reference from the next node onto the list of nodes to process; and

repeating from the determining.

25. The one or more electronically-accessible media as recited in claim 24, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

adding a root of a graph of objects to the list of nodes to process.

26. The one or more electronically-accessible media as recited in claim 25, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

if it is determined in the determining action that at least one node does not remain on the list of nodes to process,

transmitting a serialized binary blob that includes a serialization of the graph of objects.

27. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 24, wherein the type signature is associated with an object type of an object that comprises the next node.

28. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 27, wherein the type signature is created responsive to a structural representation of the associated object type.

29. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 24, wherein the action of emitting a type signature comprises the action of:

inserting the type signature into a serialized binary blob.

30. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 24, wherein the action of emitting at least one field comprises the action of:

inserting a prefix of a predetermined bit length that corresponds to a type of the at least one field into a serialized binary blob.

31. An arrangement for serializing a graph of objects, the arrangement comprising:

creation means for creating a signature table from a type system; and

serialization means for serializing the graph of objects using the signature table to produce a serialized binary blob.

32. The arrangement as recited in claim 31, wherein the signature table comprises data structure means for providing a type signature that is associated with an object type of an object of the graph of objects.

33. An arrangement comprising:

a signature table having a plurality of entries, each respective entry of the plurality of entries associating a respective object type with a respective type signature, each respective type signature created responsive to a structural representation of the respective object type associated therewith.

34. The arrangement as recited in claim 33, wherein each respective type signature is further created responsive to the structural representation of the respective object type associated therewith using a hashing algorithm.

35. The arrangement as recited in claim 33, wherein each respective type signature is created further responsive to a type name of the respective object type that is associated therewith.

36. The arrangement as recited in claim 33, wherein each respective type signature is created further responsive to a type name of a predecessor object type of the respective object type that is associated therewith.

37. The arrangement as recited in claim 33, wherein the arrangement comprises at least one of (i) one or more media and (ii) an electronic device.

38. The arrangement as recited in claim 37, wherein the one or more media comprise at least one storage medium and/or at least one transmission medium.

39. The arrangement as recited in claim 33, wherein the signature table comprises a signature table data structure.

40. One or more electronically-accessible media comprising electronically-executable instructions that, when executed, direct an electronic apparatus to perform actions comprising:

creating a type signature based on a structural representation of an object type; and

storing the type signature in association with the object type in a signature table.

41. The one or more electronically-accessible media as recited in claim 40, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform at least one further action selected from the group comprising:

using the signature table to serialize a graph of objects to produce a serialized binary blob; and

using the signature table to deserialize a received serialized binary blob to produce a new graph of objects.

42. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 40, wherein the structural representation of the object type includes one or more of a type name, a value field, and a referenced object type;

and

wherein the action of creating comprises the action of;

creating the type signature based on at least one of the type name, a prefix corresponding to the value field, and the referenced object type of the object type.

43. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 42, wherein the action of creating further comprises the action of:

creating the type signature using a hashing function.

44. One or more electronically-accessible media comprising electronically-executable instructions that, when executed, direct an electronic apparatus to perform actions comprising:

receiving a serialized binary blob; and

extracting a type signature tag from the serialized binary blob to deserialize an object, the type signature tag including a type signature based on an object type of the object.

45. The one or more electronically-accessible media as recited in claim 44, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature using a hashing algorithm.

46. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 45, wherein the action of creating comprises the action of:

applying a hashing function that comprises a cyclic redundancy code with 32 bits (CRC

     32).

47. The one or more electronically-accessible media as recited in claim 44, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature responsive to a type name of the object type.

48. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 47, wherein the action of creating comprises the action of:

converting the type name of the object type to numerals using Unicode Transformation Format-8 (UTF-8).

49. The one or more electronically-accessible media as recited in claim 44, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature responsive to a prefix corresponding to a value field of the object type.

50. The one or more electronically-accessible media as recited in claim 44, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

creating the type signature responsive to a type name of a predecessor object type of the object type.

51. The one or more electronically-accessible media as recited in claim 44, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

extracting a prefix for a field from the serialized binary blob to deserialize the object, the prefix corresponding to a particular element type of the field; and

extracting, after the prefix, information for the field.

52. The one or more electronically-accessible media as recited in claim 44, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

determining that a type of a field is expected to be atomic from a structural representation of the object type; and

responsive to the determining, extracting information for the field from the serialized binary blob to deserialize the object without extracting a prefix corresponding to the type.

53. The one or more electronically-accessible media as recited in claim 44, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

accessing a signature table with reference to a received type signature;

determining, responsive to the accessing, that the received type signature is not associated with any object type in the signature table;

transmitting a clarification request that includes the received type signature; and

receiving, after the transmitting, the structural representation of a particular object type, the received type signature created based on the particular object type.

54. An apparatus comprising:

one or more media, the one or more media including electronically-executable instructions; and

one or more processors, the one or more processors capable of executing the electronically-executable instructions to perform actions comprising;

receiving a serialized binary blob; and

deserializing an object by extracting a type signature from the serialized binary blob, the type signature derivable from an object type of the object.

55. The apparatus as recited in claim 54, wherein the type signature is further derivable from a structural representation of the object type of the object.

56. The apparatus as recited in claim 54, wherein the action of receiving comprises the action of:

receiving the serialized binary blob via a communications channel at a destination entity.

57. The apparatus as recited in claim 54, wherein the action of deserializing comprises the action of:

deserializing a plurality of objects to produce a new graph of objects by extracting a respective type signature from the serialized binary blob for each respective object of the plurality of objects, each respective type signature derivable from each respective object type of each respective object of the plurality of objects.

58. The apparatus as recited in claim 54, wherein the one or more processors are capable of executing the electronically-executable instructions to perform a further action comprising:

deserializing another object by extracting an index from the serialized binary blob, the index indicating a location of the object in a duplicate table, the another object referencing the object.

59. The apparatus as recited in claim 54, wherein the one or more processors are capable of executing the electronically-executable instructions to perform further actions comprising:

accessing a signature table using the type signature; and

ascertaining the object type, which is associated with the type signature, from the accessing.

60. The apparatus as recited in claim 54, wherein the one or more processors are capable of executing the electronically-executable instructions to perform a further action comprising:

receiving a definition of another object type responsive to a transmitted clarification inquiry that specified another type signature, the another type signature associated with the another object type.

61. An apparatus comprising:

a signature table having a plurality of entries, each respective entry of the plurality of entries associating a respective object type with a respective type signature, each respective type signature created responsive to the associated respective object type; and

a deserializer that is capable of deserializing a serialized bit stream using the signature table.

62. The apparatus as recited in claim 61, wherein the deserializer is adapted to transform the serialized bit stream into a new graph of objects;

and wherein the new graph of objects includes multidimensional linkages between and/or among objects of the new graph of objects.

63. The apparatus as recited in claim 61, wherein the deserializer is adapted to access the signature table using a particular type signature of a particular object being deserialized and to thereby ascertain a particular object type that is associated with the particular type signature.

64. The apparatus as recited in claim 63, wherein the deserializer is further adapted to extract the particular type signature from the serialized bit stream.

65. The apparatus as recited in claim 61, wherein the deserializer is adapted to recursively deserialize objects of the serialized bit stream when the objects reference other objects in the serialized bit stream.

66. The apparatus as recited in claim 61, wherein the deserializer is adapted to extract information of objects without extracting prefixes for the objects of object types that are implied by their relative position in the serialized bit stream.

67. One or more electronically-accessible media comprising electronically-executable instructions that, when executed, direct an electronic apparatus to perform actions comprising:

extracting a next type signature from a serialized bit stream;

looking up the next type signature to ascertain an object type;

determining whether the next type signature is valid;

if it is determined in the determining action that the next type signature is valid,

extracting at least one field; and

tracking one or more object references.

68. The one or more electronically-accessible media as recited in claim 67, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

preparing an empty graph of objects to fill in.

69. The one or more electronically-accessible media as recited in claim 68, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising:

after the extracting at least one field, filling in the empty graph of objects.

70. The one or more electronically-accessible media as recited in claim 67, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

determining whether an end of the serialized bit stream has been reached;

if it is determined in the determining action that the end of the serialized bit stream has not been reached,

repeating from the extracting.

71. The one or more electronically-accessible media as recited in claim 67, wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform further actions comprising:

determining whether an end of the serialized bit stream has been reached;

if it is determined in the determining action that the end of the serialized bit stream has been reached,

completing deserialization to produce a new graph of objects.

72. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 67, wherein the action of looking up the next type signature comprises the action of:

attempting to access a signature table using the next type signature to ascertain the object type that is associated therewith.

73. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 67, wherein the action of determining whether the next type signature is valid comprises the action of:

determining whether the next type signature is located during the action of looking up; and

the actions performed further comprise;

if it is determined in the determining action that the next type signature is not located during the action of looking up,

determining whether the next type signature is extracted from an optional field during the extracting a next type signature action,

if so, skipping the optional field; and

if not, aborting deserialization of the serialized bit stream.

74. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 67, wherein the next type signature is derivable from a structural representation of the ascertained object type.

75. The one or more electronically-accessible media comprising the electronically-executable instructions that, when executed, direct an electronic apparatus to perform the actions as recited in claim 67, wherein the action of extracting at least one field comprises the action of:

extracting a prefix of a predetermined bit length that corresponds to a type of the at least one field from the serialized bit stream.

76. An arrangement for deserializing a serialized binary blob, the arrangement comprising:

creation means for creating a signature table from a type system; and

deserialization means for deserializing the serialized binary blob using the signature table to produce a new graph of objects.

77. The arrangement as recited in claim 76, wherein the signature table comprises data structure means for providing an object type that is associated with a type signature extracted from the serialized binary blob by the deserialization means.

78. One or more electronically-accessible media comprising electronically-executable instructions for serializing a graph of objects that, when executed, direct an electronic apparatus to perform actions comprising:

inserting a prefix into a serialized binary blob, the prefix corresponding to a field of an object of the group of objects and indicating that the field of the object is optional; and

inserting an indication of a length of a substream into the serialized binary blob, the substream comprising a serialization of content of the field of the object.

79. The one or more electronically-accessible media as recited in claim 78, wherein the indication of the length of the substream is inserted into the serialized binary blob after the prefix;

and

wherein the electronically-executable instructions, when executed, direct an electronic apparatus to perform a further action comprising;

inserting the substream into the serialized binary blob after the indication of the length of the substream.

80. An apparatus comprising:

one or more media, the one or more media including electronically-executable instructions; and

one or more processors, the one or more processors capable of executing the electronically-executable instructions to perform actions comprising;

determining that a received type signature is unknown, the received type signature corresponding to a field of an object;

determining whether the field of the object comprises an optional field;

if the field is determined to comprise an optional field, skipping the field of the object.

81. The apparatus as recited in claim 80, wherein the apparatus comprises a portable electronic device.

82. The apparatus as recited in claim 80, wherein:

if the field is determined to not comprise an optional field,

aborting a deserialization procedure for a serialized binary blob that includes the object.

83. The apparatus as recited in claim 80, wherein the action of determining that a received type signature is unknown comprises the action of:

determining that the received type signature is not present in a signature table, the signature table associating a plurality of respective type signatures with a plurality of respective object types.

84. The apparatus as recited in claim 80, wherein the action of determining whether the field of the object comprises an optional field comprises the action of:

inspecting an optional flag corresponding to the field of the object with reference to a structural representation of an object type of the object.

85. The apparatus as recited in claim 80, wherein the action of determining whether the field of the object comprises an optional field comprises the action of.

inspecting a prefix extracted from a serialized binary blob, the prefix corresponding to the field of the object.

86. The apparatus as recited in claim 80, wherein the action of skipping the field of the object comprises the action of:

skipping a substream of a serialized binary blob, a length of the substream indicated by an indicator extracted from the serialized binary blob.

87. An electronically-implemented protocol for forward-version compatibility with serialization/deserialization, the protocol comprising:

a first version of an object, the first version of the object including at least one field that is flagged as optional;

the at least one field of the first version of the object marked for future expansion for use by an originating entity in a serialization procedure; and

a second version of the object, the second version of the object including content for the at least one field;

the at least one field of the second version of the object skippable by a destination entity in a deserialization procedure in accordance with the optional flagging of the at least one field of the first version of the object.

88. The electronically-implemented protocol for forward-version compatibility with serialization/deserialization as recited in claim 87, wherein the protocol is implemented by at least one of an originating entity and a destination entity.

89. The electronically-implemented protocol for forward-version compatibility with serialization/deserialization as recited in claim 87, wherein the protocol is implemented with at least one of (i) one or more transmission media and (ii) one or more storage media.

90. An electronically-implemented schema for serialization and/or deserialization, the schema comprising:

an attribute for serializing a graph of objects, the attribute comprising at least one serialization hint that reduces the number of bits used to serialize one or more objects of the graph of objects.

91. The electronically-implemented schema for serialization and/or deserialization as recited in claim 90, wherein the attribute flags one or more fields for one or more object types in a given type system.

92. The electronically-implemented schema for serialization and/or deserialization as recited in claim 90, wherein the at least one serialization hint is selected from the group comprising a bit packed serialization hint, a range bias serialization hint, a scale serialization hint, an array size serialization hint, a fixed type serialization hint, and a pointer-never-null serialization hint.

93. An apparatus comprising:

one or more media, the one or more media including electronically-executable instructions; and

one or more processors, the one or more processors capable of executing the electronically-executable instructions to perform actions comprising;

serializing an object of a graph of objects with a reduced bit count for a serialized bit stream in accordance with at least one serialization hint; and

transmitting the serialized bit stream.

94. The apparatus as recited in claim 93, wherein the at least one serialization hint is selected from the group comprising a bit packed serialization hint, a range bias serialization hint, a scale serialization hint, an array size serialization hint, a fixed type serialization hint, and a pointer-never-null serialization hint.

95. One or more electronically-accessible media comprising electronically-executable instructions for deserializing a serialized bit stream that, when executed, direct an electronic apparatus to perform actions comprising:

receiving a serialized bit stream; and

deserializing an object by inferring an interpretation of information extracted from the serialized bit stream in accordance with at least one serialization hint.

96. The one or more electronically-accessible media as recited in claim 95, wherein the at least one serialization hint is selected from the group comprising a bit packed serialization hint, a range bias serialization hint, a scale serialization hint, an array size serialization hint, a fixed type serialization hint, and a pointer-never-null serialization hint.