# US 12,119,844 B2 · Method and device for fast lossless compression > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,119,844 B2 - Document ID: US12119844B2 - Status: Granted - Kind: B2 - Application number: 17/917,938 - Filed: 2020-04-14 - Published: 2023-05-04 - Granted: 2024-10-15 - Earliest claimed: 2020-04-14 - Assignees: Max-Planck-Gesellschaft zur Forderung der Wissenschaften e.V. - Applicants: Max-Planck-Gesellschaft Zur FöRderung Der Wissenschaften E.V. - Inventors: Ramin Marx - Web page: https://patentgrep.com/patent/US12119844B2 ## CPC - H03M 7/3066: {by means of a mask or a bit-map} - H03M 7/6011: {Encoder aspects} - H03M 7/6023: {Parallelization} - H03M 7/3068: {Precoding preceding compression, e.g. Burrows-Wheeler transformation} - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract A computer-implemented method for compressing digital data includes obtaining a sequence of digital data values; mapping the sequence of digital data values to a sequence of code words having non-uniform bit lengths; packing the sequence of code words into a sequence of storage words having uniform bit length and corresponding to a fixed-size piece of data handled as a unit by the instruction set or the hardware of a processor; and outputting the sequence of storage words together with a first bitmask indicating the bit length of each code word, wherein in the method is implemented using special purpose vector instructions. ## Claims ### Claim 1 A computer-implemented method for fast lossless compression of digital data values, the method comprising: obtaining a sequence of digital data values; selecting bit lengths of code words, based on the sequence of digital data values, wherein the bit lengths of the code words are non-uniform; mapping the sequence of digital data values to a sequence of code words, each code word having one of the selected bit lengths; packing the sequence of code words into a sequence of storage words having uniform bit length and corresponding to a fixed-size piece of data handled as a unit by the instruction set or the hardware of a processor; and outputting the sequence of storage words, together with a first bitmask indicating the bit length of each code word, characterized in that the method is implemented using special-purpose vector instructions. ### Claim 2 (depends on 1) The method of claim 1, wherein the selection is made by comparing storage space requirements resulting from different code word bit lengths or code word bit length combinations. ### Claim 3 (depends on 1, 2) The method of claim 1 or 2, wherein the selection is made using a binary search. ### Claim 4 (depends on 1, 2) The method of claim 1 or 2, wherein the bit lengths are selected from the following bit lengths or bit length combinations: 0, 1, 2, 3, 4, 2/5, 5, 3/6, 6, 4/8, 8, 6/12, 12, 6/16, 8/16, 16. ### Claim 5 (depends on 1, 2) The method of claim 1 or 2, wherein the code words have non-uniform bit lengths. ### Claim 6 (depends on 5) The method of claim 5, wherein the code words have exactly two different bit lengths. ### Claim 7 (depends on 6) The method of claim 6, wherein the two different bit lengths of the code words are one of the following combinations: 2/5 bits, 3/6 bits, 4/8 bits, 6/12 bits, 6/16 bits, or 8/16 bits. ### Claim 8 (depends on 1, 2) The method of claim 1 or 2, wherein the bit lengths of the code words are at least two of 4, 6, 8, and 16 bits. ### Claim 9 (depends on 1, 2) The method of claim 1 or 2, wherein the step of packing the sequence of code words includes first packing a sequence of L1 bits of each code word into the storage words, where L1 corresponds to the smallest bit length of the code words, and then packing the remaining bits of the code words having a bit length larger than L1 into the remaining storage words. ### Claim 10 (depends on 9) The method of claim 9, wherein packing the remaining bits of the code words having a bit length larger than L1 comprises first packing a sequence of L2-L1 bits of each remaining code word into the remaining storage words, wherein L2 corresponds to the second smallest bit length of the code words, and then packing the remaining bits of the code words having a bit length larger than L2 into the then remaining storage words. ### Claim 11 (depends on 1, 2) The method of claim 1 or 2, wherein only the absolute values of the digital data values are mapped to code words. ### Claim 12 (depends on 11) The method of claim 11, further comprising the step of outputting information indicating, for each digital data value, its sign, preferably in the form of a second bitmask. ### Claim 13 (depends on 1, 2) The method of claim 1 or 2, wherein the step of obtaining the digital data values comprises: receiving a block of original digital data; and transforming the block of original digital data in order to obtain the digital data values. ### Claim 14 (depends on 13) The method of claim 13, wherein the transformation approximates the original data values in the block and outputs residual values, the residual values representing differences between the original data values and their approximations. ### Claim 15 (depends on 13) The method of claim 13, wherein the block of original digital data is transformed using a wavelet transform. ### Claim 16 (depends on 15) The method of claim 15, wherein the wavelet transform is a morphological wavelet transform. ### Claim 17 (depends on 15) The method of claim 15, wherein the wavelet transform is an iterated wavelet transform. ### Claim 18 (depends on 17) The method of claim 17, wherein the wavelet transform is iterated 4 times. ### Claim 19 (depends on 1, 2) The method of claim 1 or 2, implemented using AVX2 instructions.