# US 10,120,692 B2 · Methods and apparatus for storage and translation of an entropy encoded instruction sequence to executable form > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,120,692 B2 - Document ID: US10120692B2 - Status: Granted - Kind: B2 - Application number: 13/192,916 - Filed: 2011-07-28 - Published: 2013-01-31 - Granted: 2018-11-06 - Earliest claimed: 2011-07-28 - Assignees: QUALCOMM Incorporated - Applicants: Sergei Larin; Lucian Codrescu; Anshuman Das Gupta - Inventors: Sergei Larin; Lucian Codrescu; Anshuman Das Gupta - Web page: https://patentgrep.com/patent/US10120692B2 ## CPC - G06F 9/30178: {of compressed or encrypted instructions} - G06F 9/30156: {Special purpose encoding of instructions, e.g. Gray coding} - G06F 9/3017: {Runtime instruction translation, e.g. macros} - G06F 9/3853: {of compound instructions} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method of compressing a sequence of program instructions begins by examining a program instruction stream to identify a sequence of two or more instructions that meet a parameter. The identified sequence of two or more instructions is replaced by a selected type of layout instruction which is then compressed. A method of decompressing accesses an X-index and a Y-index together as a compressed value. The compressed value is decompressed to a selected type of layout instruction which is decoded and replaced with a sequence of two or more instructions. An apparatus for decompressing includes a storage subsystem configured for storing compressed instructions, wherein a compressed instruction comprises an X-index and a Y-index. A decompressor is configured for translating an X-index and Y-index accessed from the storage subsystem to a selected type of layout instruction which is decoded and replaced with a sequence of two or more instructions. ## Claims ### Claim 1 A method of compressing a sequence of program instructions, the method comprising: identifying a sequence of instructions that includes a no operation (NOP) instruction and two function instructions, wherein each instruction of the sequence of instructions has a same number of bits; replacing the identified sequence of instructions by a selected type of layout instruction comprised with the same number of bits as one of the two function instructions, wherein the selected type of layout instruction identifies a position of each instruction in the identified sequence of instructions; and compressing the selected type of layout instruction to an X-index and a Y-index pair of compressed values. ### Claim 2 (depends on 1) The method of claim 1, wherein the identified sequence of instructions includes a sequence of two or more NOP instructions. ### Claim 3 (depends on 2) The method of claim 2, wherein the sequence of two or more NOP instructions is positioned between the two function instructions. ### Claim 4 (depends on 1) The method of claim 1, wherein the identified sequence of instructions includes a second NOP instruction. ### Claim 5 (depends on 1) The method of claim 1, wherein each function instruction of the two function instructions comprises an arithmetic logic unit instruction, a load instruction, a store instruction, or a control instruction. ### Claim 6 (depends on 1) The method of claim 1, wherein the two function instructions correspond to a pair of function instructions that has been identified in an instruction stream at least a particular number of times. ### Claim 7 (depends on 1) The method of claim 1, wherein the identified sequence of instructions includes at least four instructions. ### Claim 8 (depends on 1) The method of claim 1, wherein the identified sequence of instructions is a very long instruction word packet of three or more instructions. ### Claim 9 (depends on 1) The method of claim 1, wherein the identified sequence of instructions includes two non-contiguous NOP instructions that include the NOP instruction. ### Claim 10 (depends on 1) The method of claim 1, wherein the identified sequence of instructions includes a sequence of three NOP instructions. ### Claim 11 A method to decompress instructions, the method comprising: accessing an X-index and a Y-index together as a compressed value; decompressing the compressed value to a selected type of layout instruction comprising a defined number of bits, wherein the selected type of layout instruction identifies instructions in a packet of instructions that includes a plurality of no operation (NOP) instructions and one or more function instructions positioned between a pair of NOP instructions of the plurality of NOP instructions in the packet of instructions, wherein the selected type of layout instruction further identifies a number of occurrences of the plurality of NOP instructions and placement of each NOP instruction of the plurality of NOP instructions to an identified position in the packet of instructions; and decoding the selected type of layout instruction to replace the selected type of layout instruction with the packet of instructions, wherein each identified instruction of the packet of instructions is comprised with a same defined number of bits. ### Claim 12 (depends on 11) The method of claim 11, wherein the decompressing comprises: selecting an X pattern from an X pattern memory according to the X-index; selecting a Y pattern from a Y pattern memory according to the Y-index; and combining the X pattern with the Y pattern according to a mix mask to create the selected type of layout instruction. ### Claim 13 (depends on 11) The method of claim 11, wherein the selected type of layout instruction indicates three or more NOP instructions. ### Claim 14 (depends on 11) The method of claim 11, wherein the selected type of layout instruction indicates the packet of instructions is a combination of three or more NOP instructions and the one or more function instructions. ### Claim 15 (depends on 11) The method of claim 11, wherein the one or more function instructions include a pair of function instructions that has been identified in an instruction stream at least a particular number of times. ### Claim 16 (depends on 11) The method of claim 11 wherein the decompressing is accomplished on an instruction fetch from a memory hierarchy of a processor core. ### Claim 17 An apparatus for decompressing a compressed value representing a sequence of instructions, the apparatus comprising: a storage subsystem configured for storing compressed instructions, wherein a compressed instruction comprises an X-index and a Y-index; a decompressor configured for translating the X-index and the Y-index to a selected type of layout instruction comprising a defined number of bits, wherein the selected type of layout instruction identifies instructions in a packet of instructions that includes a plurality of no operation (NOP) instructions and one or more function instructions positioned between a pair of NOP instructions of the plurality of NOP instructions in the packet of instructions, wherein the selected type of layout instruction further identifies a number of occurrences of the plurality of NOP instructions and placement of each NOP instruction of the plurality of NOP instructions to an identified position in the packet of instructions; and a decoder configured for replacing the selected type of layout instruction with the packet of instructions, wherein each identified instruction of the packet of instructions is comprised with a same defined number of bits. ### Claim 18 (depends on 17) The apparatus of claim 17, wherein the decompressor comprises: an X pattern memory operable to store X patterns that are selected according to the X-index; a Y pattern memory operable to store Y patterns that are selected according to the Y-index; and a combiner configured for combining a selected X pattern with a selected Y pattern according to a mix mask to create the selected type of layout instruction. ### Claim 19 (depends on 17) The apparatus of claim 17, wherein the plurality of NOP instructions includes three NOP instructions. ### Claim 20 (depends on 17) The apparatus of claim 17, wherein the instructions in the packet of instructions include a combination of three NOP instructions and the one or more function instructions. ### Claim 21 (depends on 17) The apparatus of claim 17, wherein the one or more function instructions include a pair of function instructions that has been identified in an instruction stream at least a particular number of times. ### Claim 22 (depends on 17) The apparatus of claim 17, wherein the storage subsystem comprises: a level 1 instruction cache operable to store the compressed instructions. ### Claim 23 A method of compressing a sequence of program instructions, the method comprising: identifying a sequence of K instructions that includes one or more no operation (NOP) instructions and two or more function instructions, wherein each instruction of the sequence of K instructions has a same number of bits B, and K is a positive integer ≥3; replacing the identified sequence of K instructions by a selected type of layout instruction comprised with the same number of bits B, wherein the selected type of layout instruction encodes the sequence of K instructions, and wherein the selected type of layout instruction identifies a position of each instruction in the identified sequence of K instructions; and compressing the selected type of layout instruction to an X-index and a Y-index pair of compressed values that is a compressed representation of the identified sequence of K instructions. ### Claim 24 (depends on 23) The method of claim 23, wherein the selected type of layout instruction solely represents the sequence of K instructions. ### Claim 25 An apparatus for decompressing a compressed value representing a sequence of instructions, the apparatus comprising: means for storing compressed instructions, wherein a compressed instruction comprises an X-index and a Y-index; means for translating the X-index and the Y-index to a selected type of layout instruction comprising a defined number of bits, wherein the selected type of layout instruction identifies instructions in a packet of instructions that includes a plurality of no operation (NOP) instructions and one or more function instructions positioned between a pair of NOP instructions of the plurality of NOP instructions in the packet of instructions, wherein the selected type of layout instruction further identifies a number of occurrences of the plurality of NOP instructions and placement of each NOP instruction of the plurality of NOP instructions to an identified position in the packet of instructions; and means for replacing the selected type of layout instruction with the packet of the instructions, wherein each identified instruction of the packet of instructions is comprised with a same defined number of bits. ### Claim 26 A computer readable non-transitory medium encoded with computer readable program data and code which, when executed by a processor, causes the processor to perform operations comprising: identifying a sequence of instructions that includes a no operation (NOP) instruction and two function instructions, wherein each instruction of the sequence of instructions has a same number of bits; replacing the identified sequence of instructions by a selected type of layout instruction comprised with the same number of bits as one of the two function instructions, wherein the selected type of layout instruction identifies a position of each instruction in the identified sequence of instructions; and compressing the selected type of layout instruction to an X-index and a Y-index pair of compressed values.