Electronic device network providing streaming updates

• US 7,548,986 B1
• Filed: 03/17/2004
• Issued: 06/16/2009
• Est. Priority Date: 03/17/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Yang, Xuguang
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): RICHARDSON, THOMAS W
• Application Number:
  US10/802,191
• Time in Patent Office: 1,917 Days
• Field of Search: 709/231
• US Class Current: 709/231
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416

Abstract

Discloses herein is wireless electronic device network employing a stream processing generator to generate updates in electronic devices capable of updating firmware and/or software contained therein. The stream processing generator may only use a small buffer of content for buffering information when transforming an original file into a new file. The stream processing generator is adapted to read a portion of in a file or a portion of a stream of content during processing and may fetch small blocks of data at a time and generate the difference information corresponding thereto.

Claims

1. A generator of difference information, the generator comprising:

at least one hardware computer processor that receives a first stream of information, the first stream comprising a plurality of first bytes of data, and

a second stream of information, the second stream comprising a plurality of second bytes of data;

an array storing operations for tree-based encoding of the first and second streams of information; and

wherein the generator simultaneously traverses the first and second streams of information, analyzes the plurality of first and second bytes of data encountered in the first and second streams of information, determines difference information between the first and second streams of information, and outputs the difference information between the first and second streams of information including a differencing instructions set comprising a hierarchical tree map and a plurality of operators represented by variable length codes based on frequency of occurrence of the associated operations.

2. The generator according to claim 1, wherein the differencing instruction set comprises at least one operation selected from a match operation, an insert operation, a delete operation, and a replace operation.

3. The generator according to claim 1, further comprising an encoder providing tree-based encoding, the encoder employing a block-based hierarchical representation, and the encoder segmenting blocks during encoding.

4. The generator according to claim 3, wherein the encoder employs variable length encoding techniques for operators in a set of operations, the encoder employing tree-based variable sized blocks, and wherein the generator computes a cumulative address offset.

28. The generator according to claim 3, wherein the block based hierarchical representation employs a hierarchy of at least three levels for encoding a block of N operations, the hierarchy comprising a top level wherein each node of the top level encodes N bytes, a second level wherein each node of the second level encodes N/4 bytes, and a third level wherein each node of the third level encodes N/16 bytes.

5. An electronic device network adapted to dispense streaming updates to at least one of a plurality of electronic devices, the updates for updating one of firmware and software, the electronic device network comprising:

a generator generating streaming updates, the generator processing at least one of a plurality of blocks of content, the at least one of a plurality of blocks of content comprising a stream of bytes, the generator processing the at least one of a plurality of blocks of content until reaching an end of the stream of bytes, the generator comprising an encoder employing a tree-based hierarchy for encoding a block of operations, and wherein the generator outputs difference information including a differencing instruction set comprising a hierarchical tree map and a plurality of operators represented by variable length codes based on frequency of occurrence of the associated operations;

a server communicatively coupled to the at least one of a plurality of electronic devices, the server disseminating the streaming updates to the at least one of a plurality of electronic devices; and

a hardware computer processor in the at least one of a plurality of electronic devices for processing the streaming updates received from the server.

6. The electronic device network according to claim 5, wherein the generator employs an array to store operations used to transform a first stream of information into a second stream of information, the generator processing the first stream and the second stream in a byte-by-byte fashion to generate streaming updates, and each byte is one of a text character and a binary value of at least one of the first and second streams.

7. The electronic device network according to claim 5, wherein the generator maintains a transform array wherein a minimum weight is assigned to a set of operations, the minimum weight being computed by employing an edit distance computation in management of an operational array.

8. The electronic device network according to claim 7, wherein the set of operations comprises at least one of a replace operation, a match operation, an insert operation, and a delete operation.

9. The electronic device network according to claim 5, wherein the tree-based hierarchy employed by the encoder comprises at least three levels for encoding a block of N operations, the hierarchy comprising a top level wherein each node of the top level encodes N bytes, a second level wherein each node of the second level encodes N/4 bytes, and a third level wherein each node of the third level encodes N/16 bytes.

10. The electronic device network according to claim 9, wherein the encoder assigns a minimum weight, wherein the minimum weight is computed by employing appropriate weights in management of a transform array.

11. The electronic device network according to claim 10, wherein the encoder assigns numeric values to each operation in the set of operations, wherein non-zero values are assigned to replace operators and insert operators, and zero is assigned to match operators.

12. The electronic device network according to claim 5, wherein the electronic device network is one of a wired and a wireless network.

13. The electronic device network according to claim 5, wherein the streaming updates comprise a difference output for two streams comprising one of binary data and text data, the difference output comprising a tree map comprising operational codes for operations comprising at least of a replace operation, a match operation, a delete operation, and an insert operation, and data characters associated with at least one of the insert operation and the replace operation.

14. The electronic device network according to claim 5, wherein a first stream of information and a second stream of information are processed by the generator, and wherein an operational array is computed in the generator by consuming each of the streams in small chunks, wherein a small chunk comprises one of a 64-byte block of information, a 16-byte block of information, and a 4-byte block of information.

15. The electronic device network according to claim 14, wherein each small chunk of each of the streams is used to define a portion of the operation array, wherein after encoding an operation in an encoder, the encoder reorients to a corresponding point in each of the streams to start additional encoding of a next small chunk.

16. The electronic device network according to claim 5, wherein the electronic device comprises at least one of a plurality of mobile electronic devices, and wherein the plurality of mobile electronic devices comprise at least one of a mobile cellular phone handset, a personal digital assistant, a pager, a multimedia device, and a camera.

17. A method of generating streaming updates by converting a first stream of information into a second stream of information for updating an electronic device, the method comprising:

identifying the first and second streams of information;

accessing the first and second streams of information;

retrieving one block of content at a time from each of the first and the second streams of information;

determining a transform operation,

executing the transform operation,

computing an output from the transform operation; and

creating a hierarchical tree-based transform output from operators determined in the transform, wherein the hierarchical tree-based transform output comprises at least three levels for encoding a block of N operations, the hierarchy comprising a top level wherein each node of the top level encodes N bytes, a second level wherein each node of the second level encodes N/4 bytes, and a third level wherein each node of the third level encodes N/16 bytes,

wherein the method is enacted by a hardware computer processor.

18. The method according to claim 17, further comprising:

encoding the hierarchical tree-based transform output employing at least one of variable length encoding and fixed length encoding; and

outputting difference information into at least one memory structure.

19. The method according to claim 18, further comprising:

determining whether additional blocks of content are to be processed by evaluating the first and second streams of information;

retrieving an additional block of content from each of the first and the second streams of information upon determining that additional blocks of content are to be encoded; and

continuing encoding until reaching an end of a stream of blocks of content to be encoded.

20. The method according to claim 19, further comprising:

compressing difference information output; and

packaging the difference information output into an update.

21. The method according to claim 17, further comprising:

buffering content from the first stream of information and the second stream information to determine the difference information; and

encoding the difference information before outputting the difference information.

22. The method according to claim 17, wherein the update facilitates conversion of the first stream of information into the second stream of information, wherein retrieving blocks of content from the second stream of information is performed at a fixed pace using a fixed block size, and wherein retrieving blocks of content from the first stream of information is performed at a variable pace using a variable block size, wherein a reference to the second stream of information is maintained and a cumulative offset is computed.

23. The method according to claim 17, wherein a look-ahead operation is executed as part of retrieving blocks of content, the look-ahead operation employing data from the first and second streams of information to compute an operation array.

24. The method according to claim 17, wherein a longest common sub-string technique is employed prior to determining a transform operation.

25. The method according to claim 17, wherein encoding a node and sub-nodes in a way indicating an impossible difference is employed as an escape sequence during encoding.

26. The method according to claim 25, wherein a combination of the escape sequence, a type field of two bits, and a length representing a repetition of data associated with the type field is employed by to encode long strings of complete matches between the first and second streams of information.

27. The method according to claim 17, wherein the electronic device comprises at least one of a plurality of mobile electronic devices, and wherein the plurality of mobile electronic devices comprise at least one of a mobile cellular phone handset, a personal digital assistant, a pager, a multimedia device, and a camera.