Storage optimizing encoder and method

• US 5,732,265 A
• Filed: 11/02/1995
• Issued: 03/24/1998
• Est. Priority Date: 11/02/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dewitt, Frederick J., McGuire, Thomas D.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/552,225
• Time in Patent Office: 873 Days
• Field of Search: 395/601, 395/602, 395/616, 395/620, 395/615
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0677 Optical disk device, e.g. CD-ROM, DVD

Abstract

An encoder and method, such as for use in CD-ROM pre-mastering software, optimizes storage on a computer readable recording medium by eliminating redundant storage of identical data streams for duplicate files. The encoder and method detect whether two files have equivalent data streams, and encodes such duplicate files as a single data stream referenced by the respective directory entries of the files. In the illustrated embodiment, the encoder and method detect duplicate files based on file size and a cyclic redundancy check calculated on the file'"'"'s data stream or portion thereof.

Claims

1. A method of encoding data of a plurality of files in a data volume to optimize storage of the data volume on a computer readable recording medium, each file containing one whole file data stream, the method comprising the steps of:

detecting whether any at least two separately identified files of the data volume contain whole file data streams that are identical; and

encoding the files for storing on the computer readable recording medium according to an encoding scheme in which said files containing identical whole file data streams are encoded as a single data stream.

2. The method of claim 1 further comprising the step of:

encoding the files for storing on the computer readable recording medium according to the encoding scheme in a directory structure in which entries for said separately identified files containing identical whole file data streams each reference the single data stream.

3. The method of claim 1 wherein the step of detecting comprises the steps of:

determining a size of the whole file data stream of each file;

calculating a result value as a function of at least a portion of the whole file data stream of each file; and

searching for at least two of the files that have a same size and result value.

4. The method of claim 3 wherein the result value is a cyclic redundancy check result.

5. The method of claim 3 wherein the step of detecting further comprises the step of:

verifying that the whole file data streams of said files that have a same size and result value are identical.

6. The method of claim 5 wherein the step of verifying comprises the step of:

performing a bit-for-bit comparison of the whole file data streams of said files that have a same size and result value.

7. A method of encoding data of a plurality of files to optimize storage of the data in a data volume on a computer readable recording medium, each file containing one whole file data stream, the method comprising the steps of;

detecting whether any at least two of the files contain whole file data streams that are identical; and

encoding the files for storing on the computer readable recording medium according to an encoding scheme in which said files containing identical whole file data streams are encoded as a single data stream;

wherein the step of detecting comprises the steps of;

determining a size of the whole file data stream of each file;

calculating a first result value as a function of an initial portion of the whole file data stream of each file;

calculating a second result value as a function of the entire whole file data stream of each file; and

searching for at least two of the files that have a same size and first and second result values.

8. A method of optimizing the storage of a data volume containing whole file data streams of a plurality of files and a directory structure with entries for the files, each file containing one whole file data stream, comprising the steps of:

detecting whether the whole file data streams of any two of the files are identical;

for two files detected as having identical whole file data streams, performing the steps of;

removing one of the identical whole file data streams; and

encoding the directory entries of the two files to reference the remaining one of the identical whole file data streams.

9. The method of claim 8 wherein the step of detecting comprises the steps of:

determining a size of the whole file data stream of each file;

calculating a result value as a function of at least a portion of the whole file data stream of each file; and

searching for two of the files that have a same size and result value.

10. The method of claim 9 wherein the result value is a cyclic redundancy check result.

11. The method of claim 9 wherein the step of detecting further comprises the step of:

verifying that the whole file data streams of said files that have a same size and result value are identical.

12. The method of claim 11 wherein the step of verifying comprises the step of:

performing a bit-for-bit comparison of the whole file data streams of said files that have a same size and result value.

13. A method of optimizing the storage of a data volume containing whole file data streams of a plurality of files and a directory structure with entries for the files, each file containing one whole file data stream, comprising the steps of:

detecting whether the whole file data streams of any two of the files are identical;

for two files detected as having identical whole file data streams, performing the steps of;

(a) removing one of the identical whole file data streams; and

(b) encoding the directory entries of the two files to reference the remaining one of the identical whole file data streams;

wherein the step of detecting comprises the steps of;

determining a size of the whole file data stream of each file;

calculating a first result value as a function of an initial portion of the whole file data stream of each file;

calculating a second result value as a function of the entire whole file data stream of each file; and

searching for at least two of the files that have a same size and first

and second result values.

14. A computer readable recording medium containing a data volume encoded by a process for optimizing data storage of a plurality of files, each file containing one whole file data stream, the process comprising the steps of:

detecting whether any at least two separately identified files of the data volume contain whole file data streams that are identical; and

encoding the files in the data volume according to an encoding scheme in which said files containing identical whole file data streams are encoded as a single data stream.

15. The computer readable recording medium of claim 14 wherein the process further comprises the step of:

encoding the files for storing in the data volume according to the encoding scheme in a directory structure in which entries for said separately identified files containing identical whole file data streams each reference the single data stream.

16. The computer readable recording medium of claim 14 wherein the step of detecting comprises the steps of:

determining a size of the whole file data stream of each file;

calculating a result value as a function of at least a portion of the whole file data stream of each file; and

searching for at least two of the files that have a same size and result value.

17. The computer readable recording medium of claim 16 wherein the result value is a cyclic redundancy check result.

18. The computer readable recording medium of claim 16 wherein the step of detecting further comprises the step of:

verifying that the whole file data streams of said files that have a same size and result value are identical.

19. The computer readable recording medium of claim 18 wherein the step of verifying comprises the step of:

performing a bit-for-bit comparison of the whole file data streams of said files that have a same size and result value.

21. The computer readable recording medium of claim 14 wherein the data volume is read only.

20. A computer readable recording medium containing a data volume encoded by a process for optimizing data storage of a plurality of files, each file containing one whole file data stream, the process comprising the steps of:

detecting whether any at least two of the files contain whole file data streams that are identical; and

encoding the files in the data volume according to an encoding scheme in which said files containing identical whole file data streams are encoded as a single data stream;

wherein the step of detecting comprises the steps of;

determining a size of the whole file data stream of each file;

calculating a first result value as a function of an initial portion of the whole file data stream of each file;

calculating a second result value as a function of the entire whole file data stream of each file; and

searching for at least two of the files that have a same size and first

and second result values.

22. An encoder for optimizing storage of a plurality of files in a data volume on a computer readable recording medium, each file containing one whole file data stream, the encoder comprising:

a detector for detecting whether any at least two separately identified files of the data volume contain whole file data streams that are identical;

means responsive to detection of at least two files containing identical whole file data streams for encoding said two files as a single data stream in the data volume.

23. The encoder of claim 22 further comprising:

means responsive to detection of at least two files containing identical whole file data streams for encoding a directory structure in the data volume in which entries for said files containing identical whole file data streams each reference the single data stream.

24. The encoder of claim 23 which is a pre-mastering software application.

25. The encoder of claim 23 which is a computer operating system.

26. The encoder of claim 23 which is a computer file system.

27. The encoder of claim 23 further comprising:

a file size generator for determining a file size of each of the files;

a result value generator for calculating a result value of each of the files as a function of at least a portion of the file'"'"'s whole file data stream; and

means for searching the files to find at least two files that have a same size and result value.

28. The encoder of claim 27 further comprising:

a comparator for verifying that two files having a same size and result value have identical whole file data streams.

29. The encoder of claim 27 wherein the result value generator generates a cyclic redundancy check.

30. In a pre-mastering software application on a computer, a method of optimizing storage of a plurality of files in a data volume on a master recording medium, each file having data stream contents, the method comprising:

adding files one-by-one to the data volume;

for each file added to the data volume,

calculating a check value as a function of an initial portion of the currently added file'"'"'s data stream contents;

determining a size of the currently added file'"'"'s data stream contents;

searching in a table of the check value and size of each of the files previously added to the data volume for a potential duplicate file having a matching check value and size;

if a potential duplicate file is found, verifying via a bit-for-bit comparison that the currently added file is identical to the potential duplicate file;

if the currently added file is verified to be identical, encoding the currently added file in the data volume as a directory entry that separately identifies the currently added file from the identical file and points to a same data stream contents as a directory entry of the identical file; and

if not verified to be identical to any file previously added to the data volume, then (a) updating the table with the currently added file'"'"'s check value and size, and (b) encoding the data stream contents of the currently added file and a directory entry that separately identifies the currently added file from previously added files and points to the encoded data stream contents of the currently added file in the data volume.

31. In a pre-mastering software application on a computer, a method of optimizing storage of a plurality of files in a data volume on a master recording medium, each file having data stream contents, the method comprising:

adding files one-by-one to the data volume;

for each file added to the data volume,

calculating a first check value as a function of an initial portion of the currently added file'"'"'s data stream contents;

calculating a second check value as a function of an entirety of the currently added file'"'"'s data stream contents;

determining a size of the currently added file'"'"'s data stream contents;

searching in a table of the first and second check values and size of each of the files previously added to the data volume for a duplicate file having first and second check values and size matching those of the currently added file;

if such duplicate file is found, encoding the currently added file in the data volume as a directory entry that separately identifies the currently added file from the duplicate file and points to a same data stream contents as a directory entry of the duplicate file; and

if no duplicate file is found, then (a) updating the table with the currently added file'"'"'s check value and size, and (b) encoding the data stream contents of the currently added file and a directory entry that separately identifies the currently added file from previously added files and points to the encoded data stream contents of the currently added file in the data volume.