# US 2014/0208068 A1 · Data compression and decompression using simd instructions

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0208068 A1
- Document ID: US20140208068A1
- Status: Published application
- Kind: A1
- Application number: 13/747,342
- Filed: 2013-01-22
- Published: 2014-07-24
- Earliest claimed: 2013-01-22
- Assignees: Samplify Systems, Inc.
- Inventors: ALBERT W. WEGENER
- Web page: https://patentgrep.com/patent/US20140208068A1

## CPC

- G06F 9/3887: {controlled by a single instruction for multiple data lanes [SIMD]}
- G06F 7/38: Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F 9/3001: {Arithmetic instructions}
- G06F 9/30025: {Format conversion instructions, e.g. Floating-Point to Integer, decimal conversion}
- G06F 9/30032: {Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/30038: {using a mask}
- G06F 9/38873: {Iterative single instructions for multiple data lanes [SIMD]}
- H03M 7/24: Conversion to or from floating-point codes
- H03M 7/3059: {Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression}
- H03M 7/6005: {Decoder aspects}
- H03M 13/27: using interleaving techniques
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- 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

Compression and decompression of numerical data utilizing single instruction, multiple data (SIMD) instructions is described. The numerical data includes integer and floating-point samples. Compression supports three encoding modes: lossless, fixed-rate, and fixed-quality. SIMD instructions for compression operations may include attenuation, derivative calculations, bit packing to form compressed packets, header generation for the packets, and packed array output operations. SIMD instructions for decompression may include packed array input operations, header recovery, decoder control, bit unpacking, integration, and amplification. Compression and decompression may be implemented in a microprocessor, digital signal processor, field-programmable gate array, application-specific integrated circuit, system-on-chip, or graphics processor, using SIMD instructions. Compression and decompression of numerical data can reduce memory, networking, and storage bottlenecks. This abstract does not limit the scope of the invention as described in the claims.

## Claims

### Claim 1

A computer system, comprising:
a data processor and memory accessible by the data processor, the memory storing computer programs executable by the data processor, including at least one application program and a set of functions to implement operations to perform compression of data samples from a data set, the at least one application program and the set of functions including single instruction multiple data (SIMD) instructions for at least a portion of the operations to be executed by the data processor, the data processor including a set of registers;
a first register of the register set to store a plurality of operands corresponding to an encoding group of data samples;
an exponent register of the register set, the data processor responsive to a SIMD instruction for operations to determine a maximum exponent value of the plurality of operands in the first register and to store the maximum exponent value in the exponent register;
interleaver logic to interleave bits of the operands in the first register to produce a plurality of nibbles to store in a second register of the register set, wherein the interleaver logic maps the bits to a given nibble based on a place value of the bits in respective operands;
a third register of the register set, the data processor responsive to a SIMD instruction for operations to select a subset of nibbles from the plurality of nibbles in the second register to store in the third register, wherein a number of nibbles for the subset is based on the maximum exponent value, wherein the subset of nibbles includes interleaved mantissa bits of the operands; and
logic to pack the interleaved mantissa bits of the subset of nibbles from the third register to a compressed data packet, wherein the packed interleaved mantissa bits represent compressed data for the encoding group of data samples.

### Claim 2 (depends on 1)

The system of claim 1, wherein the operations further include operations to encode the maximum exponent value to generate an exponent token for the encoding group and to pack the exponent token in the compressed data packet.

### Claim 3 (depends on 2)

The system of claim 2, further comprising a second exponent register of the register set to store a previous maximum exponent value, wherein the operations further include operations to calculate a difference between the maximum exponent value and the previous maximum exponent value to form an exponent difference and to encode the exponent difference to generate the exponent token.

### Claim 4 (depends on 3)

The system of claim 3, further comprising exponent difference registers to store the exponent difference and a previous exponent difference, wherein the operations further include operations to encode the exponent difference and the previous exponent difference to generate the exponent token.

### Claim 5 (depends on 1)

The system of claim 1, wherein the plurality of operands stored in the first register comprises a plurality of data samples for the encoding group from the data set.

### Claim 6 (depends on 1)

The system of claim 1, further comprising:
an input register of the register set to store a plurality of data samples from the data set for the encoding group; and
a first derivative register of the register set, the data processor responsive to a SIMD instruction for operations to calculate derivatives of the plurality of data samples from the input register and to store the plurality of first derivate samples in the first derivative register.

### Claim 7 (depends on 6)

The system of claim 6, wherein the operations include operations to select the input register or the first derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

### Claim 8 (depends on 6)

The system of claim 6, wherein the first derivative register provides the plurality of operands for the first register.

### Claim 9 (depends on 6)

The system of claim 6, wherein the operations further include an operation to attenuate the plurality of data samples in accordance with an attenuation factor to produce a plurality of attenuated samples and to store the plurality of attenuated samples in the input register.

### Claim 10 (depends on 6)

The system of claim 6, further comprising:
a second derivative register of the register set, the data processor responsive to a SIMD instruction for operations to calculate derivatives of the plurality of first derivative samples from the first derivative register and to store the plurality of second derivate samples in the second derivative register.

### Claim 11 (depends on 10)

The system of claim 10, wherein the operations further include an operation to select the input register, the first derivative register or the second derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

### Claim 12 (depends on 1)

The system of claim 1, wherein the operands in the first register have a floating-point data format, wherein the operations to select the subset of nibbles provide the number of consecutive nibbles beginning with a most significant nibble of the second register for the subset.

### Claim 13 (depends on 1)

The system of claim 1, wherein the operands in the first register have an integer data format, wherein the operations to select the subset of nibbles provide the number of consecutive nibbles beginning with a least significant nibble of the second register for the subset.

### Claim 14 (depends on 1)

The system of claim 1, wherein a number of operands in the first register is four.

### Claim 15 (depends on 14)

The system of claim 14, wherein the interleaver logic maps the bits having a particular place value in the four operands to a particular nibble in the plurality of nibbles.

### Claim 16

A computer system, comprising:
a data processor and memory accessible by the data processor, the memory storing computer programs executable by the data processor, including at least one application program and a set of functions that implement operations to perform decompression of compressed data in a compressed data packet stored in the memory, the at least one application program and the set of functions including single instruction multiple data (SIMD) instructions for at least a portion of the operations to be executed by the data processor, the compressed data including exponent tokens and packed interleaved mantissa bits for a plurality of encoding groups, the data processor including a set of registers;
a decode bit register of the register set, the data processor responsive to a SIMD instruction for operations to transfer a plurality of compressed data bits from the compressed data packet to the decode bit register;
a first exponent register of the register set, the data processor responsive to a SIMD instruction for operations to extract and decode an exponent token from the decode bit register to produce at least one decoded exponent value to store in the first exponent register, wherein each decoded exponent value corresponds to a particular encoding group;
a packed mantissa register of the register set, the data processor responsive to a SIMD instruction for operations to transfer a portion of the compressed data bits from the decode bit register to the packed mantissa register, the portion including packed interleaved mantissa bits corresponding to the particular encoding group;
a staging register of the register set, the data processor responsive to a SIMD instruction for operations to transfer a subset of nibbles from the packed mantissa register to a first subset of nibbles in the staging register in accordance with the decoded exponent value for the particular encoding group and to insert fill values into a second subset of nibbles in the staging register, wherein the decoded exponent value indicates a number of nibbles of interleaved mantissa bits in the subset from the packed mantissa register to form the first subset in the staging register; and
deinterleaver logic to deinterleave bits of the nibbles in the staging register to produce a plurality of operands to store in a first register, wherein the deinterleaver logic maps the bits of a given nibble based on a place value of the bits in respective operands, wherein the operands have a data format used by the data processor.

### Claim 17 (depends on 16)

The system of claim 16, wherein the data format of the operands is an integer data format, wherein a location for the first subset of nibbles starts at a least significant nibble location in the staging register and the fill values are sign extension bits for the second subset of nibbles in the staging register.

### Claim 18 (depends on 16)

The system of claim 16, wherein the data format of the operands is a floating-point data format, wherein a location for the first subset of nibbles starts at a most significant nibble location in the staging register and the fill values are zero values for the second subset of nibbles in the staging register.

### Claim 19 (depends on 16)

The system of claim 16, wherein a parameter indicates that the plurality of operands in the first register represent a plurality of decompressed samples corresponding to the particular encoding group.

### Claim 20 (depends on 16)

The system of claim 16, wherein a parameter indicates that the plurality of operands in the first register represent a plurality of derivative samples, further comprising:
a second register of the register set, the data processor responsive to a SIMD instruction for operations to perform first or higher order integration of the operands of the first register to form a plurality of samples for the second register, wherein the parameter indicates an integral order for the integration, wherein the plurality of samples in the second register represent a plurality of decompressed samples corresponding to the particular encoding group.

### Claim 21 (depends on 20)

The system of claim 20, further comprising an amplification factor, the data processor responsive to a SIMD instruction to multiply the plurality of samples in the second register by the amplification factor.

### Claim 22

A method for data compression using a data processor, the method comprising steps of:
storing a plurality of operands corresponding to an encoding group of data samples in a first register of a register set of the data processor;
determining a maximum exponent value of the plurality of operands in the first register;
interleaving bits of the operands in the first register to produce a plurality of nibbles to store in a second register of the register set, wherein the interleaving maps the bits to a given nibble based on a place value of the bits in respective operands;
selecting a subset of nibbles from the plurality of nibbles in the second register to store in a third register of the register set, wherein a number of nibbles for the subset is based on the maximum exponent value, wherein the subset of nibbles includes interleaved mantissa bits of the operands; and
packing the interleaved mantissa bits of the subset of nibbles from the third register to a compressed data packet, wherein the packed interleaved mantissa bits represent compressed data for the encoding group of data samples, wherein the data processor responds to at least one single instruction multiple data (SIMD) instruction to perform at least one of the steps.

### Claim 23 (depends on 22)

The method of claim 22, further comprising:
encoding the maximum exponent value to generate an exponent token for the encoding group; and
packing the exponent token in the compressed data packet.

### Claim 24 (depends on 23)

The method of claim 23, further comprising:
calculating a difference between the maximum exponent value and a previous maximum exponent value to form an exponent difference; and
encoding the exponent difference to generate the exponent token.

### Claim 25 (depends on 24)

The method of claim 24, further comprising:
encoding the exponent difference and a previous exponent difference to generate the exponent token.

### Claim 26 (depends on 22)

The method of claim 22, wherein the plurality of operands stored in the first register comprises a plurality of data samples for the encoding group from the data set.

### Claim 27 (depends on 22)

The method of claim 22, further comprising:
storing a plurality of data samples from the data set for the encoding group in an input register of the register set; and
calculating derivatives of the plurality of data samples from the input register to form first derivative samples for a first derivative register of the register set.

### Claim 28 (depends on 27)

The method of claim 27, further comprising selecting the input register or the first derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

### Claim 29 (depends on 27)

The method of claim 27, wherein the first derivative register provides the plurality of operands for the first register.

### Claim 30 (depends on 27)

The method of claim 27, further comprising:
attenuating the plurality of data samples in accordance with an attenuation factor to produce a plurality of attenuated samples; and
storing the plurality of attenuated samples in the input register.

### Claim 31 (depends on 27)

The method of claim 27, further comprising calculating derivatives of the plurality of first derivative samples from the first derivative register to form a plurality of second derivative samples for a second derivative register of the register set.

### Claim 32 (depends on 31)

The method of claim 31, further comprising selecting the input register, the first derivative register or the second derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

### Claim 33 (depends on 22)

The method of claim 22, wherein the operands in the first register have a floating-point data format, the selecting a subset of nibbles to provide the number of consecutive nibbles beginning with a most significant nibble of the second register for the subset.

### Claim 34 (depends on 22)

The method of claim 22, wherein the operands in the first register have an integer data format, the selecting a subset of nibbles to provide the number of consecutive nibbles beginning with the least significant nibble of the second register for the subset.

### Claim 35 (depends on 22)

The method of claim 22, wherein a number of operands in the first register is four.

### Claim 36 (depends on 35)

The method of claim 35, wherein the interleaving maps the bits having a particular place value in the four operands to a particular nibble in the plurality of nibbles.

### Claim 37

A method of decompressing compressed data using a data processor, the method comprising steps of:
transferring a plurality of compressed data bits from a compressed data packet to a decode bit register of a register set of the data processor, the compressed data including exponent tokens and packed interleaved mantissa bits for a plurality of encoding groups in the compressed data packet;
decoding an exponent token from the decode bit register to produce at least one decoded exponent value, wherein each decoded exponent value corresponds to a particular encoding group;
transferring a portion of the compressed data bits from the decode bit register to the packed mantissa register, the portion including packed interleaved mantissa bits corresponding to the particular encoding group;
transferring a subset of nibbles from the packed mantissa register to a first subset of nibbles in a staging register of the register set, wherein the decoded exponent value for the particular encoding group indicates a number of nibbles of interleaved mantissa bits in the subset from the packed mantissa register to form the first subset in the staging register;
inserting fill values into a second subset of nibbles in the staging register; and
deinterleaving bits of the nibbles in the staging register to produce a plurality of operands to store in a first register of the register set by mapping the bits of a given nibble based on a place value of the bits in respective operands, wherein the operands have a data format used by the data processor, wherein the data processor responds to at least one single instruction multiple data (SIMD) instruction to perform at least one of the steps.

### Claim 38 (depends on 37)

The method of claim 37, wherein the data format of the operands is an integer data format, wherein a location for the first subset of nibbles starts at a least significant nibble location in the staging register and the fill values are sign extension bits for the second subset of nibbles in the staging register.

### Claim 39 (depends on 37)

The method of claim 37, wherein the data format of the operands is a floating-point data format, wherein a location for the first subset of nibbles starts at a most significant nibble location in the staging register and the fill values are zero values for the second subset of nibbles in the staging register.

### Claim 40 (depends on 37)

The method of claim 37, wherein a parameter indicates that the plurality of operands in the first register represent a plurality of decompressed samples corresponding to the particular encoding group.

### Claim 41 (depends on 37)

The method of claim 37, wherein a parameter indicates that the plurality of operands in the first register represent a plurality of derivative samples, the method further comprising:
calculating first or higher order integration of the operands of the first register to form a plurality of samples for a second register of the register set, wherein the parameter indicates an integral order for the integration, wherein the plurality of samples in the second register represent a plurality of decompressed samples corresponding to the particular encoding group.

### Claim 42 (depends on 41)

The method of claim 41, further comprising multiplying the plurality of samples in the second register by an amplification factor.

### Claim 43

An article of manufacture, comprising:
a memory readable by a data processor, the memory storing instructions executable by the data processor, including single instruction multiple data (SIMD) instructions for at least a portion of operations for data compression to be executed by the data processor, the operations to store a plurality of operands corresponding to an encoding group of data samples in a first register of a register set of the data processor, to determine a maximum exponent value of the plurality of operands in the first register, to interleave bits of the operands in the first register to produce a plurality of nibbles to store in a second register of the register set, the bits to be mapped to a given nibble based on a place value of the bits in respective operands, to select a subset of nibbles from the plurality of nibbles in the second register to store in a third register of the register set, wherein a number of nibbles for the subset is based on the maximum exponent value, the subset of nibbles to contain interleaved mantissa bits of the operands, and to pack the interleaved mantissa bits of the subset of nibbles from the third register to a compressed data packet, wherein the packed interleaved mantissa bits represent compressed data for the encoding group of data samples.

### Claim 44 (depends on 43)

The article of manufacture of claim 43, wherein the operations further include operations to encode the maximum exponent value to generate an exponent token for the encoding group and to pack the exponent token in the compressed data packet.

### Claim 45 (depends on 44)

The article of manufacture of claim 44, wherein the operations further include operations to calculate a difference between the maximum exponent value and a previous maximum exponent value to form an exponent difference and to encode the exponent difference to generate the exponent token.

### Claim 46 (depends on 45)

The article of manufacture of claim 45, wherein the operations further include operations to encode the exponent difference and a previous exponent difference to generate the exponent token.

### Claim 47 (depends on 43)

The article of manufacture of claim 43, wherein the operations further include an operation to store a plurality of data samples for the encoding group from the data set in the first register to provide the plurality of operands.

### Claim 48 (depends on 43)

The article of manufacture of claim 43, wherein the operations further include operations to store a plurality of data samples from the data set for the encoding group in an input register of the register set and to calculate derivatives of the plurality of data samples from the input register to form first derivative samples for a first derivative register of the register set.

### Claim 49 (depends on 48)

The article of manufacture of claim 48, wherein the operations further include operations to select the input register or the first derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

### Claim 50 (depends on 48)

The article of manufacture of claim 48, wherein the operations further include operations for the first derivative register to provide the plurality of operands for the first register.

### Claim 51 (depends on 48)

The article of manufacture of claim 48, wherein the operations further include operations to attenuate the plurality of data samples in accordance with an attenuation factor to produce a plurality of attenuated samples and to store the plurality of attenuated samples in the input register.

### Claim 52 (depends on 48)

The article of manufacture of claim 48, wherein the operations further include operations to calculate derivatives of the plurality of first derivative samples from the first derivative register to form a plurality of second derivative samples for a second derivative register of the register set.

### Claim 53 (depends on 52)

The article of manufacture of claim 52, wherein the operations further include operations to select the input register, the first derivative register or the second derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

### Claim 54 (depends on 43)

The article of manufacture of claim 43, wherein the operations to select the subset of nibbles provide the number of consecutive nibbles beginning with a most significant nibble of the second register for the subset when the operands in the first register have a floating-point data format.

### Claim 55 (depends on 43)

The article of manufacture of claim 43, wherein the operations to select a subset of nibbles provide the number of consecutive nibbles beginning with the least significant nibble of the second register for the subset when the operands in the first register have an integer data format.

### Claim 56

A article of manufacture, comprising:
a memory readable by a data processor, the memory storing instructions executable by the data processor, including single instruction multiple data (SIMD) instructions for at least a portion of operations for decompression of compressed data to be executed by the data processor, the operations to transfer a plurality of compressed data bits from a compressed data packet to a decode bit register of a register set of the data processor, the compressed data to include exponent tokens and packed interleaved mantissa bits for a plurality of encoding groups in the compressed data packet, to decode an exponent token from the decode bit register to produce at least one decoded exponent value corresponding to a particular encoding group, to transfer a portion of the compressed data bits from the decode bit register to the packed mantissa register, the portion to include packed interleaved mantissa bits corresponding to the particular encoding group, to transfer a subset of nibbles from the packed mantissa register to a first subset of nibbles in a staging register of the register set, the decoded exponent value for the particular encoding group to indicate a number of nibbles of interleaved mantissa bits in the subset from the packed mantissa register to form the first subset in the staging register, to insert fill values into a second subset of nibbles in the staging register, and to deinterleave bits of the nibbles in the staging register to produce a plurality of operands to store in a first register of the register set, the bits of a given nibble to be mapped to respective operands based on a place value of the bits in the respective operands, the operands to have a data format used by the data processor.

### Claim 57 (depends on 56)

The article of manufacture of claim 56, wherein for an integer data format of the operands, a location for the first subset of nibbles starts at a least significant nibble location in the staging register and the fill values are sign extension bits for the second subset of nibbles in the staging register.

### Claim 58 (depends on 56)

The article of manufacture of claim 56, wherein for a floating-point data format of the operands, a location for the first subset of nibbles starts at a most significant nibble location in the staging register and the fill values are zero values for the second subset of nibbles in the staging register.

### Claim 59 (depends on 56)

The article of manufacture of claim 56, wherein the instructions include a parameter to indicate that the plurality of operands in the first register represent a plurality of decompressed samples corresponding to the particular encoding group.

### Claim 60 (depends on 56)

The article of manufacture of claim 56, wherein the instructions include a parameter to indicate that the plurality of operands in the first register represent a plurality of derivative samples, wherein the operations further include operations to calculate first or higher order integration of the operands of the first register to form a plurality of samples for a second register of the register set, wherein the parameter indicates an integral order for the integration, wherein the plurality of samples in the second register represent a plurality of decompressed samples corresponding to the particular encoding group.

### Claim 61 (depends on 56)

The article of manufacture of claim 56, wherein the operations further include operations to multiply the plurality of samples.
