System and method for differential compression of data from a plurality of binary sources

A machine implementable method for forming a compressed differentially encoded image of a version file as derived from a base file, said image being defined over a set of file building operations (ADD, COPY, END), descriptors, and address pointers and utilizing the version and base files comprising the steps of:

• (a) recursively forming a progressively increasing hash function first signature set of the base file in a predetermined serial order or direction and recursively forming a progressively increasing hash function second signature set of the version file in said predetermined serial order or direction;
• (b) comparing each signature in the second set contemporaneous with its generation with the signatures in the first set contemporaneous with their generation;
• (c) upon a comparison match of signatures and verification of contents, encoding a difference file ad seriatim as a portion of the version file contents up to the point of the comparison match from the later of either the start of the version file or the last comparison match, followed by a COPY command, length attribute, and pointer to the base file location of the instant matching contents;
• and
• (d) repeating steps (a)-(c) starting from the end of the matching contents in the respective base and version files until exhaustion of the respective base and version files.

A machine implementable method for forming a compressed differentially encoded image of a version file as derived from a base file, said image being defined over a set of file building operations (ADD, COPY, END), descriptors, and address pointers and utilizing the version and base files comprising the steps of:

• (a) recursively scanning the base file using a window of m bytes length including shifting the window in the same direction k<m bytes/recursion, forming a hash function signature of the window contents for each recursion of the base file, and recording said base file signature in a buffer;
• (b) recursively scanning the version file using a window of m bytes length including shifting the window in the same direction k<m bytes/recursion, forming a hash function signature of the window contents for each recursion of the version file, and comparing each hash function signature as generated from the version file with the buffer stored signatures of the base file;
• (c) upon a comparison match of signatures and verification of contents, encoding a difference file ad seriatim as an ADD command plus version file contents from the later of either the start of the version file or the last comparison match up to the point of the instant comparison match, followed by a COPY command, length attribute, and pointer to the base file location of the matching contents;
• and
• (d) repeating steps (b) and (c) until the version file scan is exhausted.

A machine implementable method for forming a compressed differentially encoded image of a version file as derived from a base file, said image being defined over a set of file building operations (ADD, COPY, END), descriptors, and address pointers and utilizing the version and base files comprising the steps of:

• (a) recursively scanning the base file and version file respectively in time overlapped relation in a predetermined serial order or direction using respective windows of m bytes granularity and k<m bytes alignment starting from predetermined locations in the respective files, forming a hash function signature of the window contents for each recursion of the respective files, and comparing the signatures of the version file with the signatures of the base file;
• (b) upon a comparison match of signatures and verification of contents, encoding a difference file ad seriatim as an ADD command plus version file contents up to the point of the instant comparison match from the later of either the starting point or the last comparison match, followed by a COPY command, length of the matching contents, and pointer to the base file location of the instant matching contents;
• and
• (c) repeating steps (a)-(b) starting from the end of the matching contents in the respective base and version files until exhaustion of the respective base and version files.

An apparatus for forming a compressed differentially encoded image of a version file as derived from a base file, said image being defined over a set of file building operations (ADD, COPY, END), descriptors, and address pointers and utilizing the version and base files comprising:

• first and second shift registers of m-bytes in length for respectively storing a portion of the base file and version file;
• first circuits coupling the first register for recursively scanning the base file by shifting the base file in the first register in the same direction k<m bytes/recursion, said first circuits including an arrangement for forming a hash function signature of the first register contents for each recursion of the base file, and for recording said base file signature in a buffer;
• second circuits coupling the second register for recursively scanning the version file by shifting the version file in the second register in the same direction k<m bytes/recursion, said second circuits including the arrangement for forming a hash function signature of the window contents for each recursion of the version file, and third circuits for comparing each hash function signature as generated from the version file with the buffer stored signatures of the base file;
• and
• fourth circuits coupling the first and second registers, the first, second, and third circuits and responsive to a comparison match of signatures and verification of contents for encoding a difference file ad seriatim as an ADD command plus version file contents up to the point of the instant comparison match from the later of either starting point of the last comparison match, followed by a COPY command, length of the matching contents, and pointer to the base file location of the instant matching contents, and invoking the next recursion of steps (b) and (c) until the version file scan is exhausted.

An article of manufacture comprising a machine readable memory having stored therein a plurality of processor executable control program steps for forming a compressed differentially encoded image of a version file derived from a base file, said image being defined over a set of file building operations (ADD, COPY, END), descriptors, and address pointers and utilizing the version and base files, said control program steps include:

• (a) a control program step for recursively scanning the base file using a window of m bytes length including shifting the window in the same direction k<m bytes/recursion and forming a hash function signature of the window contents for each recursion of the base file, and recording said base file signature in a buffer;
• (b) a control program step for recursively scanning the version file using a window of m bytes length including shifting the window in the same direction k<m bytes/recursion forming a hash function signature of the window contents for each recursion of the version file, and comparing each hash function signature as generated from the version file with the buffer stored signatures of the base file;
• and
• (c) a control program step upon a comparison match of signatures and verification of contents for encoding a difference file ad seriatim as an ADD command plus version file contents from the later of either the start of the version file or the last comparison match up to the point of the instant comparison match, followed by a COPY command, length of the matching contents, and pointer to the base file location of the instant matching contents, and for invoking the next recursion of steps (b) and (c) until the version file scan is exhausted.