In-place safe decompression

Patent metadata

Field	Value
Publication number	US-10768861-B1
Application number	US-201916287837-A
Country	US
Kind code	B1
Filing date	Feb 27, 2019
Priority date	Feb 27, 2019
Publication date	Sep 8, 2020
Grant date	Sep 8, 2020

Abstract

A method for providing in-place safe decompression of a data stream includes utilizing a stored offset to allocate a memory space for a decompression operation. The stored offset represents a maximum offset by which a write pointer position of an output stream exceeds a read pointer position for a corresponding input stream during in-place decompression of the compressed data stream.

First claim

What is claimed is:

1. A method comprising:
processing an instruction to decompress a compressed data stream stored in association with an in-place safe (IPS) offset, the IPS offset representing a maximum offset by which a write pointer position of an output stream exceeds a read pointer position for a corresponding input stream during in-place decompression of the compressed data stream;
allocating a memory space for storing the input stream and the output stream during the in-place decompression of the compressed data stream, the memory space having a size selected based on the IPS offset and a size of the output stream; and
decompressing the compressed data stream in-place within the allocated memory space.

2. The method of claim 1 , wherein the size of the allocated memory space is equal to a sum of the IPS offset and the size of the output stream.

3. The method of claim 1 , wherein the IPS offset further represents the maximum offset by which the write pointer position of the output stream exceeds the read pointer position for the input stream when a write pointer for the output stream is initialized at a zero value and read pointer for the input stream is initialized at a value equal to a difference between a length of the output stream and a length of the input stream.

4. The method of claim 1 , further comprising:
reading the data of the compressed data stream sequentially into a continuous end portion of the allocated memory space, the continuous end portion corresponding with an end portion of the allocated memory space.

5. The method of claim 1 , wherein a last byte in the compressed data stream is stored in a last physical block in the allocated memory space.

6. The method of claim 1 , wherein decompressing the compressed data stream in-place further comprises sequentially writing values of the output stream starting at a first data block in the allocated memory space.

7. The method of claim 1 , wherein the memory space is a continuous sequence of sequential physical blocks.

8. A system comprising:
memory; and
an in-place safe (IPS) offset determination tool stored in the memory that:
tracks locations of a read pointer and a writer pointer while decompressing a compressed data stream; and
identifies, based on the tracked locations, an IPS offset representing a maximum offset by which a position of the write pointer exceeds a position of the read pointer;

a file generator stored in the memory that stores the compressed data stream in association with a location of IPS offset; and
a file reader stored in the memory that allocates a memory space for decompression of the compressed data stream, the memory space having a size based on the IPS offset.

9. The system of claim 8 , wherein the size of the memory space is equal to a sum of the IPS offset and a size of a decompressed data stream saved in association with the compressed data stream.

10. The system of claim 8 , wherein the memory space is a continuous sequence of sequential physical blocks.

11. The system of claim 8 , wherein the IPS offset determination tool tracks locations of the read pointer and the write pointer by:
initializing a write pointer to a zero index equal;
initializing a read pointer to an index equal to a difference between an expected length of a decompressed data stream and a length of the compressed data stream;
updating the read pointer with each byte of data that is read from the compressed data stream; and
updating the write pointer with each byte of data that is written to the decompressed data stream.

12. The system of claim 8 , wherein the IPS offset and the compressed data stream are stored in same data file.

13. The system of claim 12 , wherein the file reader is stored along with the data file and selectively executable to for download by a user device.

14. One or more memory devices storing processor-readable instructions for executing a computer process comprising:
processing an instruction to decompress a compressed data stream stored in association with an in-place safe (IPS) offset, the IPS offset representing a maximum offset by which a write pointer position of an output stream exceeds a read pointer position for a corresponding input stream during in-place decompression of the compressed data stream;
allocating a memory space for storing the input stream and the output stream during the in-place decompression of the compressed data stream, the memory space having a size selected based on the IPS offset and a size of the output stream; and
decompressing the compressed data stream in-place within the allocated memory space.

15. The one or more memory devices of claim 14 , wherein the size of the allocated memory space is equal to a sum of the IPS offset and the size of the output stream.

16. The one or more memory devices of claim 14 , wherein the IPS offset further represents the maximum offset by which the write pointer position of the output stream exceeds the read pointer position for the input stream when a write pointer for the output stream is initialized at a zero value and read pointer for the input stream is initialized at a value equal to a difference between a length of the output stream and a length of the input stream.

17. The one or more memory devices of claim 14 , wherein the computer process further comprises:
reading the data of the compressed data stream sequentially into a continuous end portion of the allocated memory space, the continuous end portion corresponding with an end portion of the allocated memory space.

18. The one or more memory devices of claim 14 , wherein a last byte in the compressed data stream is stored in a last physical block in the allocated memory space.

19. The one or more memory devices of claim 14 , wherein decompressing the compressed data stream in-place further comprises sequentially writing values of the output stream starting at a first data block in the allocated memory space.

20. The one or more memory devices of claim 14 , wherein the memory space is a continuous sequence of sequential physical blocks.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Huang Xin
• Gladding Derek E
• Nyczkowski Bartosz T
• Sterling Michael

Classifications

• G06F3/0673

  Single storage device · CPC title

• H03M7/6005

  Decoder aspects · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• H03M7/6058 Primary

  Saving memory space in the encoder or decoder · CPC title

• G06F16/1744

  using compression, e.g. sparse files · CPC title