Remotely repairing files by hierarchical and segmented cyclic redundancy checks

• US 20070168708A1
• Filed: 12/22/2005
• Published: 07/19/2007
• Est. Priority Date: 12/22/2005
• Status: Active Grant

• Current Assignee: Daybreak Game Company, LLC (Enad Global 7 AB)
• Original Assignee: Sony Online Entertainment LLC (Enad Global 7 AB)
• Inventors: McCuller, Patrick
• Granted Patent: US 7,546,492 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00

Abstract

A method, comprising: recursively generating a sequence of sections of check codes of a local corrupted file to produce a local repair file; selectively retrieving at least one part of a remote repair file and at least one part of a remote original file, based on differences between at least one part of the local repair file and the at least one part of a remote repair file, to identify at least one corrupted part of the local corrupted file; and replacing the at least one corrupted part of the local corrupted file with the at least one part of the remote original file.

Claims

1. A method, comprising:

recursively generating a sequence of sections of check codes of a local corrupted file to produce a local repair file;

selectively retrieving at least one part of a remote repair file and at least one part of a remote original file, based on differences between at least one part of said local repair file and said at least one part of a remote repair file, to identify at least one corrupted part of said local corrupted file; and

replacing said at least one corrupted part of said local corrupted file with said at least one part of said remote original file.

2. The method of claim 1, further comprising

recursively generating a sequence of sections of check codes of said remote original file to produce said remote repair file.

3. The method of claim 2, further comprising

concatenating said sequence of sections of check codes of said remote original file to produce said remote repair file.

4. The method of claim 1, wherein said recursively generating a sequence of sections of check codes of said local corrupted file includes:

first hashing a first number of bytes in said local corrupted file to produce a check code having a second number of bytes, wherein said second number is less than said first number; and

repeating said first hashing until said local corrupted file has been entirely hashed to produce a first plurality of check codes.

5. The method of claim 4, wherein said check code includes a cyclic redundancy check (CRC) code.

6. The method of claim 4, further comprising

first concatenating said first plurality of check codes in the order in which they are produced to form a particular section of said sequence of sections of check codes of said local corrupted file.

7. The method of claim 6, wherein said particular section is a first generated remote check code section.

8. The method of claim 6, further comprising:

second hashing said first number of bytes in said particular section to produce a check code having said second number of bytes; and

repeating said second hashing until said particular section has been entirely hashed to produce a second plurality of check codes.

9. The method of claim 8, further comprising second concatenating said second plurality of check codes in the order in which they are produced to form another section of said sequence of sections of check codes of said local corrupted file.

10. The method of claim 9, wherein said another section of said sequence of sections is a last generated remote check code section in a time sequence.

11. The method of claim 9, further comprising

moving to a previously generated section in a time sequence and designating said previously generated section as said particular section;

and

repeating said second hashing, said second concatenating, and said moving until the length of said another section is less than a threshold.

12. The method of claim 11, wherein said threshold is 2000 bytes.

13. The method of claim 1, wherein said sequence of sections of check codes of a local corrupted file includes a section of last generated local check codes in a time sequence.

14. The method of claim 13, wherein said selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes

retrieving a section of last generated remote check codes in a time sequence of recursively-generated sections of check codes of a remote original file.

15. The method of claim 14, wherein said selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes

comparing said section of last generated remote check codes to said section of last generated local check codes.

16. The method of claim 15, wherein said selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes

marking check codes in said section of last generated local check codes that differ from said section of last generated remote check codes.

17. The method of claim 16, wherein said selectively retrieving parts of a remote repair file and a remote original file includes

moving to previously generated sections of said time sequence of sections of check codes of a local corrupted file and said time sequence of sections of check codes of said remote original file;

designating said previously generated sections as said last generated local check codes and said last generated remote check codes, respectively; and

repeating said retrieving, said comparing, said marking, said moving, and said designating until said previously generated remote check code section in said time sequence of sections of check codes of said remote original file is a first generated remote check code section in said time sequence of sections of check codes of said remote original file.

18. The method of claim 17, wherein said selectively retrieving parts of a remote repair file and a remote original file includes

downloading at least one part of said remote original file corresponding to said marked codes,

if said previous remote check code section is a first generated remote check code section in said time sequence of sections of check codes of said remote original file.

19. The method of claim 1, further comprising

using said local repair file and said remote repair file to locate a first corrupted part of said local corrupted file in a physical sequence from the beginning of said local corrupted file when the size of said local corrupted file does not match the size of said remote original file.

20. The method of claim 19, further comprising

resynchronizing said local corrupted file and said remote original file starting from said located first corrupted part of said local corrupted file.

21. The method of claim 20, wherein said resynchronizing includes

replacing missing data and/or dropping added data between a last correct part before said first corrupted part and a resynchronized point.

22. The method of claim 21, further comprising

moving forward from said located first corrupted part one byte at a time by assuming that a current part of check codes is correct;

and

comparing said byte of said current part of said local corrupted file to a byte in said remote original file corresponding to said located first corrupted part of said local corrupted file.

23. The method of claim 22, further comprising

discarding erroneously added bytes between said last correct part and a newly encountered part of said local corrupted file when said newly encountered part is encountered in said moving and comparing.

24. The method of claim 22, further comprising

making a note that at least one intervening block is dropped when said current part matches a block physically further along than a next physical block.

25. A system, comprising:

a first check code generator to recursively generate a sequence of sections of check codes of a local corrupted file to produce a local repair file;

a corruption identifier to selectively retrieve at least one part of a remote repair file and at least one part of a remote original file, based on differences between at least one part of said local repair file and said at least one part of a remote repair file, to identify at least one corrupted part of said local corrupted file; and

a replacing unit to replace said at least one corrupted part of said local corrupted file with said at least one part of said remote original file.

26. The system of claim 25, further comprising

a second check code generator to recursively generate a sequence of sections of check codes of said remote original file to produce said remote repair file.

27. The system of claim 26, further comprising

a concatenating unit to concatenate said sequence of sections of check codes of said remote original file to produce said remote repair file.

28. The system of claim 25, wherein said first check code generator includes:

a first hashing unit to hash a first number of bytes in said local corrupted file to produce a check code having a second number of bytes, wherein said second number is less than said first number,

said first hashing unit to repeat said hashing until said local corrupted file has been entirely hashed to produce a first plurality of check codes.

29. The system of claim 28, wherein said check code includes a cyclic redundancy check (CRC) code.

30. The system of claim 28, further comprising

a first concatenating unit to concatenate said first plurality of check codes in the order in which they are produced to form a particular section of said sequence of sections of check codes of said local corrupted file.

31. The system of claim 30, wherein said particular section is a first generated remote check code section.

32. The system of claim 30, further comprising:

a second hashing unit to hash said first number of bytes in said particular section to produce a check code having said second number of bytes,

wherein said second hashing unit repeats to hash said first number of bytes until said particular section has been entirely hashed to produce a second plurality of check codes.

33. The system of claim 32, further comprising

a second concatenating unit to concatenate said second plurality of check codes in the order in which they are produced to form another section of said sequence of sections of check codes of said local corrupted file.

34. The system of claim 33, wherein said another section of said sequence of sections is a last generated remote check code section in a time sequence.

35. The system of claim 33, further comprising

a looping unit to move to a previously generated section in a time sequence and designating said previously generated section as said particular section, and to repeat the operations of said second hashing unit, said second concatenating unit, and said looping unit until the length of said another section is less than a threshold.

36. The system of claim 35, wherein said threshold is 2000 bytes.

37. The system of claim 25, wherein said sequence of sections of check codes of a local corrupted file includes a section of last generated local check codes in a time sequence.

38. The system of claim 37, wherein said corruption identifier includes

a retriever to retrieve a section of last generated remote check codes in a time sequence of recursively-generated sections of check codes of a remote original file.

39. The system of claim 38, wherein said corruption identifier includes

a comparator to compare said section of last generated remote check codes to said section of last generated local check codes.

40. The system of claim 39, wherein said corruption identifier includes

a marking unit to mark check codes in said section of last generated local check codes that differ from said section of last generated remote check codes.

41. The system of claim 40, wherein said corruption identifier includes

a second looping unit to move to previously generated sections of said time sequence of sections of check codes of a local corrupted file and said time sequence of sections of check codes of said remote original file;

and

a designating unit to designate said previously generated sections as said last generated local check codes and said last generated remote check codes, respectively, and to repeat the operations of said retrieving, said comparing, said marking, said moving, and said designating until said previously generated remote check code section in said time sequence of sections of check codes of said remote original file is a first generated remote check code section in said time sequence of sections of check codes of said remote original file.

42. The system of claim 41, wherein said corruption identifier includes

a downloading unit to download at least one part of said remote original file corresponding to said marked codes, if said previous remote check code section is a first generated remote check code section in said time sequence of sections of check codes of said remote original file.

43. The system of claim 25, further comprising

a locator to use said local repair file and said remote repair file to locate a first corrupted part of said local corrupted file in a physical sequence from the beginning of said local corrupted file when the size of said local corrupted file does not match the size of said remote original file.

44. The system of claim 43, further comprising

a resynchronizing unit to resynchronize said local corrupted file and said remote original file starting from said located first corrupted part of said local corrupted file.

45. The system of claim 44, wherein said resynchronizing unit includes

a unit to replace missing data and/or drop added data between a last correct part before said first corrupted part and a resynchronized point.

46. The system of claim 45, further comprising

a third looping unit to move forward from said located first corrupted part one byte at a time by assuming that a current part of check codes is correct;

and

a comparing unit to compare said byte of said current part of said local corrupted file to a byte in said remote original file corresponding to said located first corrupted part of said local corrupted file.

47. The system of claim 46, further comprising

a discarding unit to discard erroneously added bytes between said last correct part and a newly encountered part of said local corrupted file when said newly encountered part is encountered in said moving and comparing.

48. The system of claim 46, further comprising

a noting unit to make a note that at least one intervening block is dropped when said current part matches a block physically further along than a next physical block.

49. A computer program, stored in a tangible storage medium, for repairing a local corrupted file, the program comprising executable instructions that cause a computer to:

recursively generating a sequence of sections of check codes of a local corrupted file to produce a local repair file;

selectively retrieving at least one part of a remote repair file and at least one part of a remote original file, based on differences between at least one part of said local repair file and said at least one part of a remote repair file, to identify at least one corrupted part of said local corrupted file; and

replacing said at least one corrupted part of said local corrupted file with said at least one part of said remote original file.

50. The computer program of claim 49, further comprising executable instructions that cause a computer to

recursively generate a sequence of sections of check codes of said remote original file to produce said remote repair file.

51. The computer program of claim 50, further comprising executable instructions that cause a computer to

concatenate said sequence of sections of check codes of said remote original file to produce said remote repair file.

52. The computer program of claim 49, wherein executable instructions that cause a computer to recursively generate a sequence of sections of check codes of said local corrupted file includes executable instructions that cause a computer to:

first hash a first number of bytes in said local corrupted file to produce a check code having a second number of bytes, wherein said second number is less than said first number; and

repeat said first hashing until said local corrupted file has been entirely hashed to produce a first plurality of check codes.

53. The computer program of claim 52, further comprising executable instructions that cause a computer to

first concatenate said first plurality of check codes in the order in which they are produced to form a particular section of said sequence of sections of check codes of said local corrupted file.

54. The computer program of claim 53, further comprising executable instructions that cause a computer to

second hash said first number of bytes in said particular section to produce a check code having said second number of bytes;

and

repeat said second hashing until said particular section has been entirely hashed to produce a second plurality of check codes.

55. The computer program of claim 54, further comprising executable instructions that cause a computer to

second concatenate said second plurality of check codes in the order in which they are produced to form another section of said sequence of sections of check codes of said local corrupted file.

56. The computer program of claim 55, further comprising executable instructions that cause a computer to

move to a previously generated section in a time sequence and designating said previously generated section as said particular section;

and

repeat said second hashing, said second concatenating, and said moving until the length of said another section is less than a threshold.

57. The computer program of claim 49, wherein said sequence of sections of check codes of a local corrupted file includes a section of last generated local check codes in a time sequence.

58. The computer program of claim 57, wherein executable instructions that cause a computer to selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes executable instructions that cause a computer to:

retrieve a section of last generated remote check codes in a time sequence of recursively-generated sections of check codes of a remote original file.

59. The computer program of claim 58, wherein executable instructions that cause a computer to selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes executable instructions that cause a computer to:

compare said section of last generated remote check codes to said section of last generated local check codes.

60. The computer program of claim 59, wherein executable instructions that cause a computer to selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes executable instructions that cause a computer to:

mark check codes in said section of last generated local check codes that differ from said section of last generated remote check codes.

61. The computer program of claim 60, wherein executable instructions that cause a computer to selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes executable instructions that cause a computer to:

move to previously generated sections of said time sequence of sections of check codes of a local corrupted file and said time sequence of sections of check codes of said remote original file;

designate said previously generated sections as said last generated local check codes and said last generated remote check codes, respectively; and

repeat said retrieving, said comparing, said marking, said moving, and said designating until said previously generated remote check code section in said time sequence of sections of check codes of said remote original file is a first generated remote check code section in said time sequence of sections of check codes of said remote original file.

62. The computer program of claim 61, wherein executable instructions that cause a computer to selectively retrieving at least one part of a remote repair file and at least one part of a remote original file includes executable instructions that cause a computer to:

download at least one part of said remote original file corresponding to said marked codes, if said previous remote check code section is a first generated remote check code section in said time sequence of sections of check codes of said remote original file.

63. The computer program of claim 49, further comprising executable instructions that cause a computer to

use said local repair file and said remote repair file to locate a first corrupted part of said local corrupted file in a physical sequence from the beginning of said local corrupted file when the size of said local corrupted file does not match the size of said remote original file.

64. The computer program of claim 63, further comprising executable instructions that cause a computer to

resynchronize said local corrupted file and said remote original file starting from said located first corrupted part of said local corrupted file.

65. The computer program of claim 64, wherein executable instructions that cause a computer to resynchronize said local corrupted file and said remote original file includes executable instructions that cause a computer to:

replace missing data and/or dropping added data between a last correct part before said first corrupted part and a resynchronized point.

66. The computer program of claim 65, further comprising executable instructions that cause a computer to

move forward from said located first corrupted part one byte at a time by assuming that a current part of check codes is correct;

and

compare said byte of said current part of said local corrupted file to a byte in said remote original file corresponding to said located first corrupted part of said local corrupted file.

67. The computer program of claim 66, further comprising executable instructions that cause a computer to

discard erroneously added bytes between said last correct part and a newly encountered part of said local corrupted file when said newly encountered part is encountered in said moving and comparing.

68. The computer program of claim 66, further comprising executable instructions that cause a computer to

make a note that at least one intervening block is dropped when said current part matches a block physically further along than a next physical block.

69. An apparatus, comprising:

means for recursively generating a sequence of sections of check codes of a local corrupted file to produce a local repair file;

means for selectively retrieving at least one part of a remote repair file and at least one part of a remote original file, based on differences between at least one part of said local repair file and said at least one part of a remote repair file, to identify at least one corrupted part of said local corrupted file; and

means for replacing said at least one corrupted part of said local corrupted file with said at least one part of said remote original file.