# US 11,113,054 B2 · Efficient hardware instructions for single instruction multiple data processors: fast fixed-length value compression

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

- Number: US 11,113,054 B2
- Document ID: US11113054B2
- Status: Granted
- Kind: B2
- Application number: 15/211,418
- Filed: 2016-07-15
- Published: 2017-03-02
- Granted: 2021-09-07
- Earliest claimed: 2015-08-27
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Shasank K. Chavan; Phumpong Watanaprakornkul; Victor Chen
- Web page: https://patentgrep.com/patent/US11113054B2

## CPC

- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/30018: {Bit or string instructions}
- G06F 9/30032: {Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE}
- G06F 9/30038: {using a mask}
- G06F 9/3004: {to perform operations on memory}
- G06F 9/30043: {LOAD or STORE instructions; Clear instruction}
- G06F 15/8053: {Vector processors}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and apparatuses for determining set-membership using Single Instruction Multiple Data (“SIMD”) architecture are presented herein. Specifically, methods and apparatuses are discussed for compressing or packing, in parallel, multiple fixed-length values into a stream of multiple variable-length values using SIMD architecture.

## Claims

### Claim 1

One or more non-transitory, computer-readable media storing one or more instructions that, when executed by one or more processors, cause producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
wherein the one or more instructions, when executed by the one or more processors, cause:
storing, in a third register, the plurality of fixed-length values into the vector of variable-length values, wherein storing the vector of variable-length values in the third register is based on the vector of lengths, wherein each variable-length value in the vector of variable-length values is unpadded, and wherein a pointer specifies a memory address of the vector of variable length values stored in the third register;
determining, based on the vector of lengths, a particular key in an offset lookup table;
determining that a particular offset is indexed in the offset lookup table by the particular key;
updating the pointer based on the particular offset.

### Claim 2 (depends on 1)

The one or more non-transitory, computer-readable media of claim 1, wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

### Claim 3 (depends on 1)

The one or more non-transitory, computer-readable media of claim 1, wherein a first length in the vector of lengths is different than a second length in the vector of lengths.

### Claim 4 (depends on 1)

The one or more non-transitory, computer-readable media of claim 1, wherein the one or more instructions, when executed by the one or more processors, cause:
generating a scatter-mask based on the vector of lengths;
storing, in a series of SIMD subregisters of a fourth register, the scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the scatter-mask stored in the fourth register.

### Claim 5 (depends on 1)

The one or more non-transitory, computer-readable media of claim 1, wherein a scatter-mask lookup table stores a plurality of scatter-masks, wherein each scatter-mask in the scatter-mask lookup table is indexed by a unique key;
wherein the one or more instructions, when executed by the one or more processors, cause:
determining, based on the vector of lengths, a particular key in the scatter-mask lookup table;
determining that a particular scatter-mask is indexed by the particular key;
storing, in a series of SIMD subregisters of a fourth register, the particular scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the particular scatter-mask stored in the fourth register.

### Claim 6 (depends on 1)

The one or more non-transitory, computer-readable media of claim 1, wherein the one or more instructions, when executed by the one or more processors, cause:
generating a shuffle-mask based on the vector of lengths;
storing, in a series of SIMD subregisters of a fourth register, the shuffle-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the shuffle-mask stored in the fourth register.

### Claim 7 (depends on 1)

The one or more non-transitory, computer-readable media of claim 1, wherein a shuffle-mask lookup table stores a plurality of shuffle-masks, wherein each shuffle-mask in the shuffle-mask lookup table is indexed by a unique key;
wherein the one or more instructions, when executed by the one or more processors cause:
determining, based on the vector of lengths, a particular key in the shuffle-mask lookup table;
determining that a particular shuffle-mask is indexed by the particular key;
storing, in a series of SIMD subregisters of a fourth register, the particular shuffle-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the particular shuffle-mask stored in the fourth register.

### Claim 8

A method for producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
the method comprising:
storing, in a third register, the plurality of fixed-length values into the vector of variable-length values, wherein storing the vector of variable-length values in the third register is based on the vector of lengths, wherein each variable-length value in the vector of variable-length values is unpadded, and wherein a pointer specifies a memory address of the vector of variable length values stored in the third register;
determining, based on the vector of lengths, a particular key in an offset lookup table;
determining that a particular offset is indexed in the offset lookup table by the particular key;
updating the pointer based on the particular offset.

### Claim 9 (depends on 8)

The method of claim 8, wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

### Claim 10 (depends on 8)

The method of claim 8, wherein a first length in the vector of lengths is different than a second length in the vector of lengths.

### Claim 11 (depends on 8)

The method of claim 8, the method further comprising:
generating a scatter-mask based on the vector of lengths;
storing, in a series of SIMD subregisters of a fourth register, the scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the scatter-mask stored in the fourth register.

### Claim 12 (depends on 8)

The method of claim 8, wherein a scatter-mask lookup table stores a plurality of scatter-masks, wherein each scatter-mask in the scatter-mask lookup table is indexed by a unique key;
wherein the method further comprising:
determining, based on the vector of lengths, a particular key in the scatter-mask lookup table;
determining that a particular scatter-mask is indexed by the particular key;
storing, in a series of SIMD subregisters of a fourth register, the particular scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the particular scatter-mask stored in the fourth register.

### Claim 13 (depends on 8)

The method of claim 8, wherein the method further comprising:
generating a shuffle-mask based on the vector of lengths;
storing, in a series of SIMD subregisters of a fourth register, the shuffle-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the shuffle-mask stored in the fourth register.

### Claim 14 (depends on 8)

The method of claim 8, wherein a shuffle-mask lookup table stores a plurality of shuffle-masks, wherein each shuffle-mask in the shuffle-mask lookup table is indexed by a unique key;
wherein the method further comprising:
determining, based on the vector of lengths, a particular key in the shuffle-mask lookup table;
determining that a particular shuffle-mask is indexed by the particular key;
storing, in a series of SIMD subregisters of a fourth register, the particular shuffle-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the particular shuffle-mask stored in the fourth register.

### Claim 15

One or more non-transitory, computer-readable media storing one or more instructions that, when executed by one or more processors, cause producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
wherein a scatter-mask lookup table stores a plurality of scatter-masks;
wherein the one or more instructions, when executed by the one or more processors, cause:
determining, based on the vector of lengths, a particular key in the scatter-mask lookup table;
determining that the particular key indexes a particular scatter-mask;
storing, in a third register and based on the particular scatter-mask, the plurality of fixed-length values into the vector of variable-length values, wherein each variable-length value in the vector of variable-length values is unpadded.

### Claim 16 (depends on 15)

The one or more non-transitory, computer-readable media of claim 15, wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

### Claim 17 (depends on 15)

The one or more non-transitory, computer-readable media of claim 15, wherein the one or more instructions, when executed by the one or more processors, cause:
storing, in a series of SIMD subregisters of a fourth register, the particular scatter-mask;
storing, in the third register and based on the particular scatter-mask stored in the fourth register, the plurality of fixed-length values into the vector of variable-length values.

### Claim 18 (depends on 15)

The one or more non-transitory, computer-readable media of claim 15, wherein the one or more instructions, when executed by the one or more processors, cause:
storing the vector of variable-length values in the third register at an address specified by a pointer;
determining an offset based on each length in the vector of lengths;
updating the pointer based on the offset.

### Claim 19 (depends on 15)

The one or more non-transitory, computer-readable media of claim 15, wherein the one or more instructions, when executed by the one or more processors, cause generating, based on the vector of lengths, each scatter-mask stored in the scatter-mask lookup table.

### Claim 20

A method for producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
wherein a scatter-mask lookup table stores a plurality of scatter-masks;
the method comprising:
determining, based on the vector of lengths, a particular key in the scatter-mask lookup table;
determining that the particular key indexes a particular scatter-mask;
storing, in a third register and based on the particular scatter-mask, the plurality of fixed-length values into the vector of variable-length values, wherein each variable-length value in the vector of variable-length values is unpadded.

### Claim 21 (depends on 20)

The method of claim 20, wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

### Claim 22 (depends on 20)

The method of claim 20, further comprising:
storing, in a series of SIMD subregisters of a fourth register, the particular scatter-mask;
storing, in the third register and based on the particular scatter-mask stored in the fourth register, the plurality of fixed-length values into the vector of variable-length values.

### Claim 23 (depends on 20)

The method of claim 20, further comprising:
storing the vector of variable-length values in the third register at an address specified by a pointer;
determining an offset based on each length in the vector of lengths;
updating the pointer based on the offset.

### Claim 24 (depends on 20)

The method of claim 20, further comprising generating, based on the vector of lengths, each scatter-mask stored in the scatter-mask lookup table.

### Claim 25

One or more non-transitory, computer-readable media storing one or more instructions that, when executed by one or more processors, cause producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
wherein a shuffle-mask lookup table stores a plurality of shuffle-masks;
wherein the one or more instructions, when executed by the one or more processors, cause:
determining, based on the vector of lengths, a particular key in the shuffle-mask lookup table;
determining that the particular key indexes a particular shuffle-mask;
storing, in a third register and based on the particular shuffle-mask, the plurality of fixed-length values into the vector of variable-length values, wherein each variable-length value in the vector of variable-length values is unpadded.

### Claim 26 (depends on 25)

The one or more non-transitory, computer-readable media of claim 25, wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

### Claim 27 (depends on 25)

The one or more non-transitory, computer-readable media of claim 25, wherein the one or more instructions, when executed by the one or more processors, cause:
storing, in a series of SIMD subregisters of a fourth register, the particular shuffle-mask;
storing, in the third register and based on the particular shuffle-mask stored in the fourth register, the plurality of fixed-length values into the vector of variable-length values.

### Claim 28 (depends on 25)

The one or more non-transitory, computer-readable media of claim 25, wherein the one or more instructions, when executed by the one or more processors, cause:
storing the vector of variable-length values in the third register at an address specified by a pointer;
determining an offset based on each length in the vector of lengths;
updating the pointer based on the offset.

### Claim 29 (depends on 25)

The one or more non-transitory, computer-readable media of claim 25, wherein the one or more instructions, when executed by the one or more processors, cause generating, based on the vector of lengths, each shuffle-mask stored in the shuffle-mask lookup table.

### Claim 30

A method for producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
wherein a shuffle-mask lookup table stores a plurality of shuffle-masks;
the method comprising:
determining, based on the vector of lengths, a particular key in the shuffle-mask lookup table;
determining that the particular key indexes a particular shuffle-mask;
storing, in a third register and based on the particular shuffle-mask, the plurality of fixed-length values into the vector of variable-length values, wherein each variable-length value in the vector of variable-length values is unpadded.

### Claim 31 (depends on 30)

The method of claim 30, wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

### Claim 32 (depends on 30)

The method of claim 30, further comprising:
storing, in a series of SIMD subregisters of a fourth register, the particular shuffle-mask;
storing, in the third register and based on the particular shuffle-mask stored in the fourth register, the plurality of fixed-length values into the vector of variable-length values.

### Claim 33 (depends on 30)

The method of claim 30, further comprising:
storing the vector of variable-length values in the third register at an address specified by a pointer;
determining an offset based on each length in the vector of lengths;
updating the pointer based on the offset.

### Claim 34 (depends on 30)

The method of claim 30, further comprising generating, based on the vector of lengths, each shuffle-mask stored in the shuffle-mask lookup table.