Patent ID: 8909897

Claim:
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.