Method for generating a delta for compressed data

摘要

A translation table has entries that each include a share bit and a delta bit, with pointers that point to a memory block that includes reuse bits. The share bit is set to indicate a translation table entry is sharing its memory block with another translation table entry. In addition, a translation table entry may include a private delta in the form of a pointer that references a memory fragment in the memory block that is not shared with other translation table entries, wherein the private delta references previously-stored content. When a translation table has a private delta, its delta bit is set. The private delta is generated by analyzing a data buffer for content that is similar to previously-stored content.

主权项

1. A method for performing compression on data stored in a memory that includes a plurality of memory blocks, the method comprising the steps of:
providing a translation table having a plurality of translation table entries, each translation table entry having a share bit, a delta bit and a plurality of pointers that each point to a memory fragment in a memory block in the memory, wherein the share bit is set on a first translation table entry when the first translation table entry includes at least one pointer that points to a memory fragment in the memory block that is shared with a second translation table entry and the delta bit on the first translation table entry is set when the first translation table entry includes the at least one pointer that points to the memory fragment in the memory block that is shared with the second translation table entry and when the first translation table entry includes at least one pointer that points to a different memory fragment in the memory block that is not shared with the second translation table entry; identifying first and second memory blocks with identical content; changing a first translation table entry corresponding to the first memory block to point to at least one memory fragment in the second memory block; releasing at least one memory fragment that was freed up when the first translation table entry was changed to point to the at least one memory fragment in the second memory block; setting the share bit of the first and second translation table entries corresponding to the first and second memory blocks; generating a private delta in the different memory fragment in the memory block that is not shared with the second translation table entry, wherein the private delta references previously-stored content; setting the delta bit on the first translation table entry when the first translation table entry includes a pointer that points to the private delta; and clearing the delta bit on the first translation table entry when the first translation table entry does not include a pointer that points to the private delta.