Methods and systems for updating content including a compressed version

• US 8,418,167 B2
• Filed: 10/06/2006
• Issued: 04/09/2013
• Est. Priority Date: 10/06/2005
• Status: Active Grant

• Current Assignee: Red Bend Limited (Samsung Electronics Co. Ltd.)
• Original Assignee: Red Bend Limited (Samsung Electronics Co. Ltd.)
• Inventors: Meller, Evyatar, Peleg, Sharon
• Primary Examiner(s): Kang, Insun
• Application Number:
  US11/543,996
• Publication Number:
  US 20070083571A1
• Time in Patent Office: 2,377 Days
• Field of Search: None
• US Class Current: 717/169
• CPC Class Codes: G06F 8/654 using techniques specially adapted for alterable solid state memories, e.g. for EEPROM or flash memories
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

An original version of content is in-place updated to an updated version in a non-volatile storage device including blocks, by obtaining an update package, copying the original version to volatile memory, and updating the original version to provide an uncompressed updated version. The methods may also include compressing the uncompressed updated version so as to independently or interdependently compress each amount of uncompressed updated content and writing the compressed updated version in place of the original version in the storage device. Each of the independently compressed amounts may be written to a separate storage blocks.

Claims

1. A method for in-place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the method comprising:

obtaining an update package;

copying said original version or part thereof to a volatile memory;

updating, in accordance with said update package, said original version or part thereof to provide an uncompressed updated version or part thereof in the volatile memory;

compressing said uncompressed updated version or part thereof by independently compressing virtual blocks of uncompressed updated content such that all content of a virtual block when compressed, is substantially equal in size to and fits into one storage block; and

writing said compressed updated version or part thereof in place of said original version or part thereof in said non-volatile storage device, each independently compressed virtual block being written to a separate storage block.

2. The method of claim 1, wherein said original version is compressed, said copying said original version or part thereof including:

decompressing at least part of said original version or part thereof.

3. The method of claim 2, wherein said compressed original version using a different compression algorithm or compression ratio than said compressed updated version.

4. The method of claim 1, wherein at least part of the content of each one of n (n>

1) blocks of the original version is modified in the updated version, and wherein said updating and said writing include performing m block storage operations, each block storage operation including writing content to a block in the non-volatile storage device;

the block storage operations include update block storage operations storing updated content of the updated version in the non-volatile storage device, the updated content is generated in accordance with at least the update package;

wherein 2<

=m<

2n.

5. The method of claim 1, wherein at least part of the content of each one of n (n>

1) blocks of the original version is modified in the updated version, and wherein said updating and said writing include performing block storage operations, each block storage operation including writing content to a block in the non-volatile storage device, and wherein the block storage operations include also at least one backup block storage operation wherein each backup block storage operation includes storing protected content in a non-volatile protection buffer.

6. The method of claim 5, wherein said update package includes transforming commands, each having a source segment and a target segment, and wherein said protected content includes data associated with a transforming command.

7. The method of claim 5, wherein during said writing said volatile memory is erased, further comprising:

copying remaining said original version of content or part thereof from said storage device to the volatile memory;

updating said remaining said original version of content or part thereof, including retrieving at least some of said protected content which is required for said updating;

compressing said updated remaining content or part thereof so as to independently compress virtual blocks of uncompressed updated original content; and

writing said updated remaining content or part thereof in place of said at least part of said original remaining content in said storage device wherein each said independently compressed virtual block is written to a separate storage block.

8. The method of claim 5, wherein

the update package is associated with an update sequence, and wherein

the size of the protected content in said non-volatile protection buffer depends on said update sequence;

said size is smaller than an arbitrary size of a protected content that depends on an arbitrary update sequence associated with the update package;

said arbitrary update sequence is selected arbitrarily from among all possible update sequences which can be associated with said update package.

9. The method of claim 5, wherein

the update package is associated with an update sequence, and wherein

the size of the protected content in said non-volatile protection buffer depends on said update sequence;

said size is smallest size among sizes of protected content that depend on any update sequence of all possible update sequences which can be associated with the update package.

10. The method of claim 1, wherein said update package includes data for delineating said virtual blocks of uncompressed updated version of content.

11. The method of claim 10, wherein one of said virtual blocks is updated, compressed and written prior to updating, compressing and writing another of said virtual blocks.

12. The method of claim 1, wherein said original version is entirely updated and then compressed prior to writing said compressed updated version to said storage device.

13. A method for generating an update package for in place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the method comprising:

decompressing into virtual blocks any of said original and updated versions which comprise separate storage blocks for each independently compressed content;

determining if any data of said original version will be required for at least one transforming command, wherein said at least one transforming command uses content of said origin version to generate updated content; and

if any data of said original version is determined to be required for at least one transforming command, simulating protection by storing a copy of said determined data required for performing transforming commands in a protection buffer, so that said copy of said determined data of said original version exists upon updating said original version and modifying said determined data.

14. The method of claim 13, further comprising:

storing virtual block delineation for any of said original version and updated version in said update package.

15. The method of claim 13, wherein the update package is associated with an update sequence for updating said storage blocks, and wherein

the total size of data relating to transforming commands which require protection depends on said update sequence;

said size is smaller than an arbitrary size of a protected content that depends on an arbitrary update sequence associated with the update package;

said arbitrary update sequence is selected arbitrarily from among all possible update sequences which can be associated with said update package.

16. The method of claim 13, wherein if said protection buffer is not sufficient, protecting in the update package data required for performing transforming commands is protected in the update package.

17. The method of claim 13, wherein a transforming command includes a source segment and a target segment.

18. A method for in-place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the method comprising:

obtaining an update package including transforming commands that use content of said original version to generate updated content;

copying said original version to a volatile memory, wherein if said original version includes content in more than one storage block which was compressed interdependently, then said copying includes decompressing said original version into the volatile memory and protecting at least some content which is required for decompressing said original version;

updating the original version to provide an uncompressed updated version; and

copying said updated version back to the non-volatile storage device in place of the original version wherein if said updated version is to be stored compressed where blocks are compressed interdependently, then said copying includes protecting at least some content which is required for decompressing said updated version and compressing interdependently updated blocks;

wherein at least one of said original version and said updated version includes content in more than one storage block which was compressed interdependently.

19. The method of claim 18, wherein said protected content includes actual content in a version which is unrelated to compression.

20. The method of claim 18, wherein said protected content includes content added to a version relating to compression.

21. The method of claim 18, wherein said protected content includes data required for decompression of a block of a version which is virtually associated with an immediately preceding block of said version.

22. The method of claim 18, wherein the update package is associated with an update sequence for updating said storage blocks, and wherein said protected content which is required for decompression of a storage block containing updated content is associated with another storage block containing updated content which is updated later than said storage block according to said update sequence.

23. The method of claim 18, wherein the update package is associated with an update sequence for updating said storage blocks and wherein said protected content which is required for decompression of a storage block containing original version of content is associated with another storage block containing original version of content which is updated earlier than said storage block according to said update sequence.

24. The method of claim 18, wherein at least part of the content of each one of n (n>

1) blocks of the original version is modified in the updated version, and wherein said copying, compressing, and writing include performing m block storage operations, each block storage operation including writing content to a block in the non-volatile storage device;

the block storage operations include update block storage operations storing updated content of the updated version in the non-volatile storage device, the updated content is generated in accordance with at least the update package;

wherein 2<

=m<

2n.

25. The method of claim 18, wherein during said writing said volatile memory is erased, further comprising:

copying remaining original content from said non-volatile storage device to the volatile memory, wherein if said remaining original content is stored compressed in said non-volatile storage device, said copying includes decompressing said remaining original content;

updating said remaining original content;

copying updated content from said non-volatile storage device to the volatile memory, wherein if said updated content is stored compressed in said non-volatile storage device said copying includes decompressing said updated content; and

using said protected content when decompressing any of said remaining original content or said updated content.

26. The method of claim 18, wherein said original version was compressed using a different compression algorithm or compression ratio than used to compress said updated version.

27. The method of claim 18, wherein one of said original version and said updated version includes separate storage blocks for each independently compressed content.

28. A method for generating an update package for in place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the method comprising:

obtaining uncompressed old and uncompressed new versions of content;

obtaining dependencies between storage blocks of any of old and new versions resulting from (i) any of a plurality of transforming commands that use content of said original version to generate updated content and (ii) decompression of one or both versions; and

if any data of said original version is determined to be required for any of the plurality of transforming commands, simulating protection in a protection buffer by storing a copy of said determined data of said original version required for performing any of the plurality transforming commands and decompressing one or both versions.

29. The method of claim 28, wherein if said protection buffer is not sufficient, protecting in the update package data required for performing any of transforming commands and decompressing one or both versions.

30. The method of claim 28, further comprising:

storing virtual block delineation and decompression records for any of said uncompressed old and uncompressed new versions in said update package.

31. The method of claim 28, wherein the update package is associated with an update sequence for updating said storage blocks, and wherein the total size of data requiring protection depends on said update sequence;

said size is smaller than an arbitrary size of a protected content that depends on an arbitrary update sequence associated with the update package;

said arbitrary update sequence is selected arbitrarily from among all possible update sequences which can be associated with said update package.

32. The method of claim 28, wherein said data required for decompression includes actual content in a version which is unrelated to compression.

33. The method of claim 28, wherein said data required for decompression includes content added to a version relating to compression.

34. The method of claim 28, wherein said data required for decompression includes data required for decompression of a block of a version which is virtually associated with an immediately previous block of said version.

35. An apparatus for in-place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, comprising:

a volatile memory;

a receiver configured to obtain an update package including transforming commands that use content of said original version to generate updated content;

an update module configured to (i) copy said original version in said non-volatile storage device to said volatile memory and (ii) update said original version to provide said updated content; and

a compression module configured to compress said updated version by;

(i) interdependently compressing uncompressed virtual blocks of said updated version, each of which corresponding to more than one storage block in said non-volatile storage device, protecting at least some content of said original version determined to be required for at least one transforming command, and by storing a copy of said determined data in a protection buffer, or

(ii) independently compressing each virtual block of uncompressed updated content such that all content of a virtual block, when compressed, is substantially equal in size to and fits into one storage block, wherein

said update module is also configured to write said compressed updated version in place of said original version in said non-volatile storage device.

36. An apparatus for generating an update package for in place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, comprising:

a decompression module configured to determine a correspondence between each storage block and an uncompressed virtual block and to determine decompression dependencies between blocks or configured to determine a correspondence between each storage block and an uncompressed virtual block which, when independently compressed, (i) substantially equals a size of and fits into one storage block;

a processor for (i) generating an update package and (ii) if any data of said original version is determined to be required for performing any one of a plurality of transforming commands, simulating protection by storing a copy of said determined data in a protection buffer, such that said copy of said determined data of said original version exists upon updating said determined data.

37. A computer program product comprising a non-transitory computer useable medium having computer readable program code embodied therein for in-place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the computer program product including a computer readable program code for causing the computer to:

obtain an update package;

copy said original version or part thereof to a volatile memory;

update said original version or part thereof to provide an uncompressed updated version including virtual blocks;

compress said uncompressed updated version by independently compressing each virtual block of uncompressed updated content such that all content of a virtual block when compressed, is substantially equal in size to and fits into one storage block; and

write said compressed updated version in place of said original version or part thereof in said non-volatile storage device, each independently compressed virtual block being written to a separate storage block.

38. A computer program product comprising a non-transitory computer useable medium having computer readable program code embodied therein for generating an update package for in place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the computer program product including computer readable program code for causing the computer to:

decompress into virtual blocks any of said original and updated versions which comprise separate storage blocks for each independently compressed content;

determine if any data of said original version is required for at least one transforming command; and

if any data is determined to be required for at least one transforming command, simulating protection in a protection buffer by storing a copy of said determined data so that said copy of said determined data of said original version exists upon updating said original version.

39. The computer program product of claim 38, wherein a transforming command includes a source segment and a target segment.

40. A computer program product comprising a non-transitory computer useable medium having computer readable program code embodied therein for in-place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the computer program product comprising computer readable program code for causing the computer to:

obtain an update package including transforming commands that uses content of said original version to generate updated content;

copy said original version to a volatile memory, wherein if said original version includes content in more than one storage block which was compressed interdependently, then said copying includes decompressing said original version into the volatile memory and protecting at least some content which is required for decompressing said original version;

computer readable program code for causing the computer to update the original version to provide an uncompressed updated version; and

computer readable program code for causing the computer to copy said updated version back to the non-volatile storage device in place of the original version wherein if said updated version is to be stored compressed where blocks are compressed interdependently, then said copying includes protecting at least some content which is required for decompressing said updated version and compressing interdependently updated blocks;

wherein at least one of said original version and said updated version includes content in more than one storage block which was compressed interdependently.

41. A computer program product comprising a non-transitory computer useable medium having computer readable program code embodied therein for generating an update package for in place updating of an original version of content stored in a non-volatile storage device with storage blocks to yield an updated version of content, the computer program product comprising computer readable program code for causing the computer to:

obtain uncompressed old and uncompressed new versions of content;

obtain dependencies between storage blocks of any of old and new versions resulting from (i) any of a plurality of transforming commands that uses content of said original version to generate updated content and (ii) decompression of one or both versions; and

if any data of said original version is determined to be required for any of the plurality of transforming commands, simulating protection by storing, in a protection buffer, a copy of said determined data of said original version required for performing any of the plurality of transforming commands, so that said copy of said determined data of said original version exists upon updating said original version.