Technologies for efficiently compressing data with run detection

1. A compute device comprising:

one or more processors; and

a memory having stored therein a plurality of instructions that, when executed by the one or more processors, cause the compute device to:

produce a hash as a function of a symbol at a present position in an input stream and a predefined number of symbols after the present position in the input stream, wherein the symbol is indicative of a start of a string of symbols in the input stream;

determine whether the symbol at the present position is part of a run, wherein a run defines a string of one or more repeated symbols in the input stream;

obtain, from a hash table, a chain of pointers to previous positions in the input stream associated with the hash;

determine, as a function of whether the symbol is part of a run and to identify a matched string, a number of strings referenced by the chain of pointers to compare to the string associated with the present position in the input stream; and

output, in response to an identification of a matched string, a reference to the matched string in a set of compressed output data.

2. The compute device of claim 1 , wherein to determine whether the symbol at the present position is part of a run comprises to:

compare the symbol at the present position to a predefined number of other contiguous symbols in the input stream; and

determine whether the symbol at the present position is part of a string of one or more contiguous repeated symbols.

3. The compute device of claim 1 , wherein the plurality of instructions, when executed, further cause the compute device to set, in response to a determination that the symbol at the present position is part of a run, a run status bit associated with the present position in the input stream to a value indicative that the symbol is part of a run.

4. The compute device of claim 1 , wherein the plurality of instructions, when executed, further cause the compute device to set, in response to a determination that the symbol at the present position is not part of a run, a run status bit associated with the present position in the input stream to a value indicative that that the symbol is not part of a run.

5. The compute device of claim 1 , wherein to determine whether the symbol at the present position is part of a run comprises to:

compare the symbol at the present position to a predefined number of other contiguous symbols in the input stream; and

determine whether the symbol at the present position is part of a repeated sequence of two or more different symbols.

6. The compute device of claim 1 , wherein to determine, as a function of whether the symbol is part of a run, a number of strings referenced by the chain of pointers to compare to the string associated with the present position comprises to determine, in response to a determination that the symbol is part of a run, to compare one string referenced by the chain of pointers to the string associated with the present position.

7. The compute device of claim 1 , wherein to determine, as a function of whether the symbol is part of a run, a number of strings referenced by the chain of pointers to compare to the string associated with the present position comprises to determine, in response to a determination that the symbol is not part of a run, to compare more than one string referenced by the chain of pointers to the string associated with the present position.

8. The compute device of claim 1 , wherein the plurality of instructions, when executed, further cause the compute device to add, in response to a determination that the symbol at the present position is part of a run, the symbols in the run, a start position of the run, and a length of the run to a run table.

9. The compute device of claim 8 , wherein the plurality of instructions, when executed, further cause the compute device to evict an entry from the run table as a function of the start position and length of the run associated with the symbol at the present position and the start position and length of another run indicated in the run table.

10. The compute device of claim 1 , wherein to output a reference to a matched string comprises to determine whether to output, as a function of the lengths and positions of one or more stored runs and the run at the present position, whether to output a reference to one of the previously stored runs or a reference to a local run.

11. The compute device of claim 1 , wherein to determine the number of strings referenced by the chain of pointers to compare comprises to determine the number of strings to compare further as a function of a percentage of runs detected in the input stream.

12. The compute device of claim 11 , wherein to determine the number of strings to compare comprises to adjust the number of strings in inverse proportion to a change in the percentage of runs detected in the input stream.

13. One or more non-transitory machine-readable storage media comprising a plurality of instructions stored thereon that, when executed by a compute device cause the compute device to:

produce a hash as a function of a symbol at a present position in an input stream and a predefined number of symbols after the present position in the input stream, wherein the symbol is indicative of a start of a string of symbols in the input stream;

determine whether the symbol at the present position is part of a run, wherein a run defines a string of one or more repeated symbols in the input stream;

obtain, from a hash table, a chain of pointers to previous positions in the input stream associated with the hash;

determine, as a function of whether the symbol is part of a run and to identify a matched string, a number of strings referenced by the chain of pointers to compare to the string associated with the present position in the input stream; and

output, in response to an identification of a matched string, a reference to the matched string in a set of compressed output data.

14. The one or more non-transitory machine-readable storage media of claim 13 , wherein to determine whether the symbol at the present position is part of a run comprises to:

compare the symbol at the present position to a predefined number of other contiguous symbols in the input stream; and

determine whether the symbol at the present position is part of a string of one or more contiguous repeated symbols.

15. The one or more non-transitory machine-readable storage media of claim 13 , wherein the plurality of instructions, when executed, further cause the compute device to set, in response to a determination that the symbol at the present position is part of a run, a run status bit associated with the present position in the input stream to a value indicative that the symbol is part of a run.

16. The one or more non-transitory machine-readable storage media of claim 13 , wherein the plurality of instructions, when executed, further cause the compute device to set, in response to a determination that the symbol at the present position is not part of a run, a run status bit associated with the present position in the input stream to a value indicative that that the symbol is not part of a run.

17. The one or more non-transitory machine-readable storage media of claim 13 , wherein to determine whether the symbol at the present position is part of a run comprises to:

compare the symbol at the present position to a predefined number of other contiguous symbols in the input stream; and

determine whether the symbol at the present position is part of a repeated sequence of two or more different symbols.

18. The one or more non-transitory machine-readable storage media of claim 13 , wherein to determine, as a function of whether the symbol is part of a run, a number of strings referenced by the chain of pointers to compare to the string associated with the present position comprises to determine, in response to a determination that the symbol is part of a run, to compare one string referenced by the chain of pointers to the string associated with the present position.

19. The one or more non-transitory machine-readable storage media of claim 13 , wherein to determine, as a function of whether the symbol is part of a run, a number of strings referenced by the chain of pointers to compare to the string associated with the present position comprises to determine, in response to a determination that the symbol is not part of a run, to compare more than one string referenced by the chain of pointers to the string associated with the present position.

20. The one or more non-transitory machine-readable storage media of claim 13 , wherein the plurality of instructions, when executed, further cause the compute device to add, in response to a determination that the symbol at the present position is part of a run, the symbols in the run, a start position of the run, and a length of the run to a run table.

21. The one or more non-transitory machine-readable storage media of claim 20 , wherein the plurality of instructions, when executed, further cause the compute device to evict an entry from the run table as a function of the start position and length of the run associated with the symbol at the present position and the start position and length of another run indicated in the run table.

22. The one or more non-transitory machine-readable storage media of claim 13 , wherein to output a reference to a matched string comprises to determine whether to output, as a function of the lengths and positions of one or more stored runs and the run at the present position, whether to output a reference to one of the previously stored runs or a reference to a local run.

23. The one or more non-transitory machine-readable storage media of claim 13 , wherein to determine the number of strings referenced by the chain of pointers to compare comprises to determine the number of strings to compare further as a function of a percentage of runs detected in the input stream.

24. A method for compressing data with run detection, the method comprising:

producing, by a compute device, a hash as a function of a symbol at a present position in an input stream and a predefined number of symbols after the present position in the input stream, wherein the symbol is indicative of a start of a string of symbols in the input stream;

determining, by the compute device, whether the symbol at the present position is part of a run, wherein a run defines a string of one or more repeated symbols in the input stream;

obtaining, by the compute device and from a hash table, a chain of pointers to previous positions in the input stream associated with the hash;

determining, by the compute device and as a function of whether the symbol is part of a run and to identify a matched string, a number of strings referenced by the chain of pointers to compare to the string associated with the present position in the input stream; and

outputting, by the compute device and in response to an identification of a matched string, a reference to the matched string in a set of compressed output data.

25. The method of claim 24 , wherein determining whether the symbol at the present position is part of a run comprises:

comparing the symbol at the present position to a predefined number of other contiguous symbols in the input stream; and

determining whether the symbol at the present position is part of a string of one or more contiguous repeated symbols.