Microcomputer executing compressed program and generating compressed branch addresses

Claim 3

A method according to claim 1 further comprising the steps of: determining from the data fetched in said fetching step if said compressed program data requires expansion in said expanding step; wherein, if said fetched data is determined to require expansion, then said fetched data is expanded in said expanding step; and wherein, if said fetched data is determined not to require expansion, then said fetched data is decoded in said decoding step without performing the expanding step.

Claim 4

A microcomputer comprising: program counter means for indicating an instruction address; storage means for storing compressed program data provided by compressing a program having a plurality of instructions, said storage means being connected to said program counter means; expanding means including means for fetching data from the instruction address indicated by said program counter means and means for expanding the fetched data; decoding means for decoding the expanded data from said expanding means; execution means for executing operations in response to the decoding of the expanded data by the decoding means; execution sequence determining means coupled to said decoding means for determining whether the decoding by said decoding means indicates a change in instruction execution sequence; address generation means including a compressed address translation table for generating a branch address indicating a destination address within said compressed program data by extracting a compressed branch address corresponding to the branch address included in said fetched data from the compressed address translation table; and setting means for setting the address generated by said address generation means in said program counter means in response to an indication of a change in the instruction execution sequence, and for incrementing the instruction address in said program counter means in response to an indication of no change in the instruction execution sequence.

Claim 5

A microcomputer comprising: program counter means for indicating an instruction address; storage means for storing compressed program data provided by compressing a program having a plurality of instructions, said storage means being connected to said program counter means; expanding means including means for fetching data from the instruction address indicated by said program counter means and means for expanding the fetched data; decoding means for decoding the expanded data from said expanding means; execution means for executing operations in response to the decoding of the expanded data by the decoding means; execution sequence determining means coupled to said decoding means for determining whether the decoding by said decoding means indicates a change in instruction execution sequence; address generation means including a compressed address translation table for generating a branch address indicating a destination address within said compressed program data by extracting a compressed branch address corresponding to the branch address included in said fetched data from the compressed address translation table; and setting means for setting the address generated by said address generation means in said program counter means in response to an indication of a change in the instruction execution sequence, and for incrementing the instruction address in said program counter means in response to an indication of no change in the instruction execution sequence.

Claim 6

A microcomputer according to claim 3, wherein said expanding means comprises: determining means for determining if said expansion of the fetched data is necessary; wherein, if said expansion is determined to be necessary, then the data expanding means expands said fetched data; and wherein, if said expansion is determined to be unnecessary, then said fetched data is supplied to said decoding means without expansion.

Claim 7

A microcomputer according to claim 4, wherein said data expanding means comprises: a translation rule table containing expanded data corresponding to fetched data from the stored compressed program data; and first searching means for searching said translation rule table to determine if expansion is necessary for the fetched data.

Claim 8

A microcomputer according to claim 5, wherein said address generation means comprises: the compressed address translation table containing a branch destination instruction address in program data before compression and a corresponding branch destination instruction address in the program data after compression; and second searching means for searching said compressed address translation table based on the branch destination instruction address before compression wherein the corresponding branch destination instruction address after compression is generated by the address generation means.

Claim 9

A microcomputer according to claim 5, wherein said expansion is performed by assigning a data string having a relatively high frequency of occurrence in the program data before compression to a predetermined byte of data of the compressed program data.

Claim 10

A microcomputer according to claim 3, wherein said expanding means comprises: determining means for determining if said expansion of said fetched data is necessary; wherein, if said expansion is determined to be necessary, then the data expanding means expands said fetched data; and wherein, if said expansion is determined to be unnecessary, then said fetched data is supplied to said decoding means without expansion.

Claim 11

A microcomputer according to claim 8, wherein said data expanding means further comprises: a translation rule table containing expanded data corresponding to fetched data from the stored compressed data program; and first searching means for searching said translation rule table to determine if expansion is necessary for the fetched data.

Claim 12

A microcomputer according to claim 3, wherein said address generation means comprises: the compressed address translation table containing a branch destination instruction address in program data before compression and a corresponding branch destination instruction address in program data after compression; and second searching means for searching said compressed address translation table based on the branch destination instruction address before compression wherein the corresponding branch destination instruction address after compression is generated by the address generation means.

Claim 13

A microcomputer according to claim 3 further comprising a semiconductor substrate on which said microcomputer is disposed.

Claim 14

A microcomputer according to claim 9 further comprising a semiconductor substrate on which said microcomputer is disposed.

Claim 15

A microcomputer according to claim 10 further comprising a semiconductor substrate on which said microcomputer is disposed.

Claim 16

In a microcomputer for use with a memory which stores a compressed program which has been provided by compressing a program having a plurality of instructions, the microcomputer comprising: a program counter generating an address by an increment operation, the generated address indicating an address of the compressed program; a data expander expanding data of the compressed program indicated by the address generated by the program counter; an instruction decoder decoding the expanded data and generating an output; an execution unit executing an operation in accordance with the output of the instruction decoder; an instruction determination unit, responsive to the output of the instruction decoder, determining whether the operation to be executed by the execution unit includes a branch operation; an address generation unit including a compressed address translation table and generating destination address data for indicating a destination in the compressed program by extracting compressed branch address data from the compressed address translation table if the instruction determination unit has determined that the operation to be executed by the execution unit includes the branch operation; and a setting unit setting the generated destination address data to the program counter if the instruction determination unit has determined that the operation to be executed by the execution unit includes a branch operation, wherein data from the destination in the compressed program indicated by the destination address data is expanded by the data expander and executed by the execution unit.

Claim 17

In a microcomputer for use with a memory which stores a compressed program which has been provided by compressing a program having a plurality of instructions, the microcomputer comprising: a program counter generating an address by an increment operation, the generated address indicating an address of the compressed program; a data expander expanding data of the compressed program indicated by the address generated by the program counter; an instruction decoder decoding the expanded data and generating an output; an execution unit executing an operation in accordance with the output of the instruction decoder; an instruction determination unit, responsive to the output of the instruction decoder, determining whether the operation to be executed by the execution unit includes a branch operation; an address generation unit including a compressed address translation table and generating destination address data for indicating a destination in the compressed program by extracting compressed branch address data from the compressed address translation table if the instruction determination unit has determined that the operation to be executed by the execution unit includes the branch operation; and a setting unit setting the generated destination address data to the program counter if the instruction determination unit has determined that the operation to be executed by the execution unit includes a branch operation, wherein data from the destination in the compressed program indicated by the destination address data is expanded by the data expander and executed by the execution unit.

Claim 18

A microcomputer according to claim 14, wherein the memory and the microcomputer are formed on a single chip.

Claim 19

A microcomputer according to claim 14, wherein the address generation unit includes: the compressed address translation table including a plurality of destination data for indicating destination addresses for branch operations in the program before being compressed and a plurality of destination address data corresponding to the plurality of destination data and which indicate destination addresses in the compressed program; and a compressed address translation table search unit which searches the plurality of destination data to find destination data if the instruction determination unit has determined that the operation to be executed by the execution unit includes a branch operation.

Claim 20

A microcomputer according to claim 16, wherein the data expander comprises: a data determination unit determining whether expansion is required of the data of the compressed program indicated by the address generated by the program counter; and a selecting unit which provides the data of the compressed program indicated by the address generated by the program counter to the instruction decoder without expansion if expansion of the data is not required and which provides the expanded data to the instruction decoder if expansion of the data is required.

Claim 21

A microcomputer according to claim 17, wherein the memory is a read-only memory.

Claim 22

A microcomputer according to claim 15, wherein the memory is a read-only memory.

Claim 23

A microcomputer executing a compressed program of instructions addressable by addresses, the instructions of the compressed program addressable by addresses, the compressed program generated by compressing an initial program of instructions, comprising: a program counter storing an address indicating an instruction of the compressed program; a memory storing instructions of the compressed program; an instruction expander coupled to the memory, the instruction expander sequentially receiving and selectively expanding the instructions of the compressed program and generating instructions corresponding to the initial program; an instruction decoder decoding instructions from the instruction expander and generating an output; an execution unit executing the instructions from the instruction expander in response to the instruction decoder output; an address translator including a compressed address translation table and generating the compressed branch addresses indicating addresses in the compressed program by extracting a compressed branch from the compressed address translation table, wherein, in response to an output which is provided from the instruction decoder and which indicates a change in sequence of the compressed program, the address translator stores in the program counter the compressed branch address in the compressed program so that an instruction at the address indicated by the compressed branch address can be executed in response to the change in sequence of the compressed program.

Claim 24

A microcomputer executing a compressed program of instructions addressable by addresses, the instructions of the compressed program addressable by addresses, the compressed program generated by compressing an initial program of instructions, comprising: a program counter storing an address indicating an instruction of the compressed program; a memory storing instructions of the compressed program; an instruction expander coupled to the memory, the instruction expander sequentially receiving and selectively expanding the instructions of the compressed program and generating instructions corresponding to the initial program; an instruction decoder decoding instructions from the instruction expander and generating an output; an execution unit executing the instructions from the instruction expander in response to the instruction decoder output; an address translator including a compressed address translation table and generating the compressed branch addresses indicating addresses in the compressed program by extracting a compressed branch from the compressed address translation table, wherein, in response to an output which is provided from the instruction decoder and which indicates a change in sequence of the compressed program, the address translator stores in the program counter the compressed branch address in the compressed program so that an instruction at the address indicated by the compressed branch address can be executed in response to the change in sequence of the compressed program.

Claim 25

The microcomputer of claim 20, wherein the instruction expander comprises an instruction translation table containing instructions of the compressed program and corresponding instructions of the initial program, wherein, in response to an instruction from the compressed program, a corresponding instruction of the initial program is provided to the instruction decoder.

Claim 26

The microcomputer of claim 21, wherein the compressed address translation table contains addresses of instructions of the compressed program and corresponding addresses of the initial program, wherein the addresses of the compressed program comprise addresses of instructions for which an output of the instruction decoder indicate a change in sequence of the compressed program.

Claim 27

The microcomputer of claim 20, wherein the microcomputer is implemented on a semiconductor substrate.

Claim 28

The microcomputer of claim 21, wherein the instruction translation table contains instructions of the initial program having a high frequency of occurrence, wherein instructions of the initial program having a high frequency of occurrence are compressed in the compressed program.

Claim 29

In a microcomputer for use with a memory which stores a program which has been compressed, the microcomputer comprising: a program counter generating an address of the compressed program; a data expander selectively expanding data of the compressed program indicated by the address generated by the program counter; an instruction decoder decoding the expanded data and generating an output; an execution unit executing an operation in accordance with the output of the instruction decoder; an instruction determination unit responsive to the output of the instruction decoder, determining whether the operation to be executed by the execution unit includes a branch operation; an address generation unit generating compressed destination address data indicating a destination in the compressed program if the instruction determination unit has determined that the operation to be executed by the execution unit includes a branch operation, wherein the address generation unit includes: a compressed address translation table including a plurality of destination data indicating destination addresses for branch operations in the program before being compressed and a plurality of compressed destination address data which correspond to the plurality of destination data and which indicate compressed destination addresses in the compressed program; and an address table search unit which searches the plurality of destination data to find compressed destination address data if the instruction determination unit has determined that the operation to be executed by the execution unit includes the branch operation; and a setting unit setting the compressed destination address data to the program counter if the instruction determination unit has determined that the operation to be executed by the execution unit includes a branch operation; wherein data indicated by the compressed destination address data in the compressed program is expanded by the data expander and executed by the execution unit.

Claim 30

In a microcomputer for use with a memory which stores a program which has been compressed, the microcomputer comprising: a program counter generating an address of the compressed program; a data expander selectively expanding data of the compressed program indicated by the address generated by the program counter; an instruction decoder decoding the expanded data and generating an output; an execution unit executing an operation in accordance with the output of the instruction decoder; an instruction determination unit responsive to the output of the instruction decoder, determining whether the operation to be executed by the execution unit includes a branch operation; an address generation unit generating compressed destination address data indicating a destination in the compressed program if the instruction determination unit has determined that the operation to be executed by the execution unit includes a branch operation, wherein the address generation unit includes: a compressed address translation table including a plurality of destination data indicating destination addresses for branch operations in the program before being compressed and a plurality of compressed destination address data which correspond to the plurality of destination data and which indicate compressed destination addresses in the compressed program; and an address table search unit which searches the plurality of destination data to find compressed destination address data if the instruction determination unit has determined that the operation to be executed by the execution unit includes the branch operation; and a setting unit setting the compressed destination address data to the program counter if the instruction determination unit has determined that the operation to be executed by the execution unit includes a branch operation; wherein data indicated by the compressed destination address data in the compressed program is expanded by the data expander and executed by the execution unit.

Claim 31

A microcomputer according to claim 25, wherein the memory comprises read-only memory.

Claim 32

A microcomputer according to claim 25, wherein the microcomputer and the read-only memory are formed on a single chip.