WO1994019768A1

WO1994019768A1 - Compressed bios system

Info

Publication number: WO1994019768A1
Application number: PCT/US1994/001558
Authority: WO
Inventors: Dan Kikinis
Original assignee: Oakleigh Systems, Inc.
Priority date: 1993-02-19
Filing date: 1994-02-10
Publication date: 1994-09-01
Also published as: EP0685093A1; EP0685093A4; JPH08509826A

Abstract

A means of providing a BIOS routine from an EPROM to RAM in a general purpose computer, where the BIOS routine is greater in number of lines of code than the line capacity of the EPROM is provided. The BIOS routine is stored in EPROM in three portions (11). A first portion (13) is uncompressed, and loadable and operable by the CPU of the computer to initialize RAM. A second portion (17) is compressed by one of a number of schemes. A third portion (15) is a decompression utility loadable and operable by the computer CPU to decompress the compressed portion from EPROM and copy the resulting code to RAM, resulting in a BIOS in RAM.

Description

COMPRESSED BIOS SYSTEM

Field of the Invention

The present invention is in the area of general- purpose computer systems, and pertains more particularly to basic input/output (BIOS) systems for providing instruction sets for initializing such computer systems on startup, reset, or configuration.

Background of the Invention

As is well known in the art, a computer system, to be of any use, must comprise all the computer hardware, such as the CPU, memory devices, communication buses, and so forth. There must also be instruction sets (programs/software) for the CPU to follow to accomplish tasks. The programmed information (application software) is typically stored on an internal or peripheral memory device to be accessed by the CPU as needed.

To be able to operate peripheral devices to access application software and data, and to load and run programs, a computer must have certain minimal operational capability not dependent on application programs. This operational capability comes from an instruction set that is usually permanently recorded and "read only", termed the basic input/output (BIOS) system. The BIOS is accessed when a computer is powered up (booted) or rebooted, to initialize and test circuits and peripherals, and the routines stored in BIOS are also accessed in operation to provide basic operating characteristics in response to commands generated from applications.

There are many good texts and references addressing BIOS systems and particularly the BIOS systems for IBM compatible machines. One such useful reference, covering BIOS in general, is The inn Rosch Hardware Bible published by Simon and Schuster, Inc. of New York city, Φ 1989 by inn L. Rosch. The section of BIOS characteristics from page 159 through 176 is pertinent and incorporated herein by reference.

Most BIOS implementations in general purpose computers are implemented in single chip erasable programmable non-volatile (EPROM) memory devices resident on a "motherboard" in the computer. There are other suitable non-volatile memory devices, however, which have been or may be used, including but not limited to EEPROM devices, "Flash Card" memories known in the art, masked ROM devices, CMOS RAM with a battery backup, and magnetic bubble memory.

As with other integrated circuits, EPROMs (and other non-volatile memories) have been developed over the years to be smaller, less expensive (per unit storage capacity), faster, and capacity has been improved. One of the first EPROMs, the Intel 1702, has a capacity of 256 bytes. Newer EPROMS have capacities as high as 512 kilobytes, and there is no physical barrier to higher capacities. Larger units are, however, more expensive, and as capacities increase, higher pin count contributes to higher costs for connection and so forth.

The problem is, that increasing power and capability of general purpose computers requires more extensive BIOS systems, which in turn require larger and faster (and more expensive) EPROM chips. What is needed is a means to extend BIOS code without larger capacity EPROMs.

Summary of the Invention

A firmware device according to a preferred embodiment of the invention provides a BIOS routine for α general-purpose computer having a CPU microprocessor, comprising a programmable non-volatiJe memory device, and a BIOS routine stored on the programmable non-volatile memory device. The BIOS routine has a compressed portion, an uncompressed portion operable by the CPU to initialize random access memory in the general-purpose computer, and a decompression utility code operable by the CPU to load the compressed portion, decompress it, and copy the decompressed code to the random access memory. In a preferred embodiment the programmable memory device is an EPROM device.

In a particular compression scheme compression is accomplished by a substituting a two line token for a longer sequence, where the longer sequence is a sequence often repeated in the BIOS. The value of the first line is a flag to the decompression routine that the next line is to be used to correlate to the longer sequence and copy that longer sequence in decompression.

In the invention a general-purpose computer is provided having a compressed BIOS according to the invention, and a method of compressing a BIOS routine for storage on an EPROM is provided as well, following the token scheme.

The invention provides a need for storing a BIOS routine and loading and operating the routine, from an EPROM that has a lesser line capacity than the lines of code in the BIOS routine. This lowers the cost of BIOS for computers in general, and provides for more extensive BIOS routines without correspondingly larger EPROMs.

Brief Description of the Drawings

Fig. 1 is a diagrammatical representation of a partially compressed BIOS according to an embodiment of the invention.

Fig. 2 is a flow chart showing the operation of a computer from startup following a BIOS routine according to the present invention.

Fig. 3 is a diagrammatical representation of a token decompression scheme according to an embodiment of the invention.

Description of the Preferred Embodiments

In most BIOS systems for general purpose computers, the BIOS is stored in an EPROM device as described in the background section above. Upon power up the BIOS initializes the system, doing basic tasks like accessing and checking the operation of on-board random-access memory RAM, and typically, somewhere during the initialization, at least a part of the BIOS code is copied (the BIOS copies itself) into a portion of the on-board RAM.

The portion of RAM reserved for BIOS code in a computer is generally termed "shadow" RAM. The term shadow RAM is also used in the industry for a particular hardware type of memory device wherein each volatile memory cell has a connected non-volatile (EPROM-type) cell. These are more properly called NVRAM devices, and are not what is meant in this description by shadow RAM. Shadow RAM for the purpose of this disclosure is simply that portion of RAM reserved for a copy of part or all of the BIOS code.

In typical general-purpose computers, as soon as the system receives power, the BIOS tests and initializes system RAM, then copies (shadows) itself from the EPROM to the RAM. The BIOS continues to run in RAM. The purpose of shadowing the BIOS in RAM is to give the CPU microprocessor much faster access to the BIOS code than it would have by accessing the EPROM every time a BIOS code sequence is needed in continuing operations.

The present invention comprises a means of compressing at least a significant portion of the BIOS code, storing all of the BIOS code, including the compressed portion, in EPROM, and releasing the compressed code on powerup, so all of the code is available for the computer to use. Also on powerup, the entire code is shadowed to RAM.

Fig. 1 is a diagrammatical representation of a compressed BIOS 11 according to the present invention. There are three different portions of the code. Portion 13 is code to perform all operations to initialize and test the system RAM, and make it ready for use, and is a familiar portion of conventional BIOS routines. This portion in some applications needs to perform such functions as initializing and testing a memory controller and cache controllers and cache memory. Portion 15 is a decompression utility. Portion 17 represents the balance of the BIOS code in compressed form. It will be apparent to those with skill in the art that there are a number of compression schemes and related decompression routines that might be used.

Fig. 2 is a flow chart showing the operation of a computer from startup following a BIOS routine according to the present invention. From powerup signal 19, which is typically derived from the act of closing the power on switch, operation goes to initialization operation 21, during which system RAM is initialized. In operation 21, the system runs portion 13 of Fig. 1.

Next, decompression utility 15 (Fig. 1) is accessed and run in operation 23. The decompression utility processes the balance of the BIOS code (compressed), translates it into operable code, and shadows it to system RAM. Although such decompression utilities are available, the code pointing to the compressed portion of the BIOS, and that which causes the decompressed code to be shadowed to RAM is not a part of a conventional decompression routine. These commands are added to the BIOS of the invention.

After the BIOS is shadowed operation continues (25) from the BIOS in system RAM. All remaining BIOS processes, including testing and initializing the remainder of the computer subsystems are accomplished in this operating portion.

One means by which the BIOS code may be compressed is based on the fact that BIOS routines, as is common in most other coded instruction sets, make use of frequently repeated code sequences. EPROMs used for BIOS are typically byte-wide devices, that is, the device can store "words" of 8 bits. A sixteen bit word requires, then, two lines of BIOS code.

In this embodiment frequently repeated code sequences are replaced in the compressed portion of the BIOS with a token. The token in this embodiment is a two byte code in which the first byte is a flag to the decompression utility that the following byte is a pointer. The pointer portion is an entry to a table which is a part of the decompression utility, and points to the specific, oft repeated, code sequence. In a simple such system, the table might have but one entry.

As an example, a frequently repeated code sequence in a BIOS might be a "call keyboard" sequence, which for the purpose of this example, may be eight lines of code. The token could be two lines of code in which the first line is the binary representation of the hexadecimal "FF". In this scheme, hex FF is a flag indicating that the following byte is a pointer. The pointer, then, can be any value representable by a digital byte, that is any one of 256 values. The requirement is simply that the decompression utility associate the pointer with the oft- repeated BIOS code sequence, and substitute that sequence in decompression and copying the BIOS code to RAM. In this scheme an oft-repeated code sequence need be stored only once in the BIOS portion that is the decompression utility.

Fig. 3 is a diagrammatical representation of the token decompression scheme described above. After the BIOS according to the embodiment of the invention has initialized and tested the RAM, the decompression utility is booted, and begins to read the compressed portion of the BIOS at Start 27. At 29 the decompression utility loads the first/next byte from the compressed portion of the EPROM BIOS. If this byte is hex FF (31), it is recognized as a token, and control goes to 33, where the system reads the byte following the token flag. This byte is always a pointer to a code sequence.

At 35 the system associates the pointer byte with the code sequence from a preprogrammed table and loads the associated sequence. At 37 the system copies the n lines of code pointed by the pointer byte to the next n lines in shadow RAM. Control then goes to decision point 39 and determines if the last loaded byte from compressed BIOS was the last byte. If so, control jumps to a predetermined entry point in the decompressed shadow RAM, and the BIOS routine continues. If not, control goes back to 29 and the next line of compressed code is loaded.

At decision point 31, if the hex value is not FF, the code line loaded from compressed BIOS is copied directly into the next line in shadow BIOS.

It will be apparent to those with skill in the art that there are many alterations in detail that might be made without departing from the spirit and scope of the invention. For example, there are many non-volatile memories in which a compressed BIOS may be stored, retrieved, and decompressed, and several of these have been listed above. The fact of compressing the routines in the BIOS, including a loadable decompression routine, extends the capacity of any such finite non-volatile memory devices and hence the size of a BIOS routine that may be stored thereon.

It is also true that there are a truly large number of compression schemes that might be employed to compress a portion of the BIOS. The invention should not be limited by the specific code relationship determined to compress the BIOS code. The invention is to be limited by the following claims:

Claims

What is claimed is:

1. A device for providing a BIOS routine for a general- purpose computer having a CPU microprocessor, comprising: a programmable non-volatile memory unit; and a BIOS routine stored on said programmable non¬ volatile memory unit; said BIOS routine comprising a compressed portion, an uncompressed portion operable by said CPU to prepare random access memory for use in said general-purpose computer, and a decompression utility code operable by said CPU to load said compressed portion, decompress it, and copy the decompressed code to the random access memory.

2. A device as in claim 1 wherein said programmable non¬ volatile memory unit is one of an EPROM, an EEPROM, a flash card memory unit, a masked ROM unit, a CMOS memory unit with a battery, and a magnetic bubble memory unit.

3. A device as in claim 1 wherein said compressed portion is compressed by having a token code representing a repeated code sequence, said repeated code sequence being longer than said token code, said token code identifiable by said CPU running said decompression utility code to replace said token with said repeated code sequence during decompression.

4. A general-purpose computer comprising: a CPU microprocessor for managing operation of said general-purpose computer; random access memory (RAM) for storing operable routines and data in operation of said general-purpose computer; a programmable non-volatile memory device upon which is stored a BIOS routine having a compressed portion, an uncompressed portion, and a decompression utility; said uncompressed portion operable by said CPU for preparing said RAM for use, and said decompression utility operable by said CPU for decompressing said compressed portion and copying the resulting decompressed code to the RAM.

5. A general-purpose computer as in claim 4 wherein said programmable, read-only memory device is one of an EPROM, an EEPROM, a flash card memory unit, a masked ROM unit, a CMOS memory unit with a battery, and a magnetic bubble memory unit.

6. A general-purpose computer as in claim 4 wherein said compressed portion is compressed by having a token code representing a repeated code sequence, said repeated code sequence being longer than said token code, said token code identifiable by said CPU running said decompression utility code to replace said token with said repeated code sequence during decompression.

7. A method for storing a BIOS routine having N lines of code on a non-volatile memory device having n lines capacity, N being greater than n, comprising the steps of: storing a first code sequence as an uncompressed portion, said first code sequence being operable by a CPU to prepare on-board RAM for use; storing a second code sequence as a compressed portion, said second code sequence when uncompressed being operable by the CPU to perform BIOS functions; and storing a third code sequence as a decompression utility, said third code sequence being operable by said CPU to decompress said second code sequence and copy the resulting decompressed code to the on-board RAM.

8. The method of claim 7 wherein said compressed portion is compressed by having a token code representing a repeated code sequence, said repeated code sequence being longer than said token code, said token code identifiable by said CPU running said decompression utility code to replace said token with said repeated code sequence during decompression.

9. A method for providing a RAM-resident BIOS routine on start-up in a predesignated portion of RAM in a general- purpose computer having a CPU microprocessor, comprising the steps of: loading a first code sequence for initializing RAM to the CPU from a non-volatile storage unit and operating the first code sequence to prepare the RAM for use; loading a second code sequence for decompressing code to the CPU from the non-volatile storage unit and operating the second code sequence to load a third compressed code sequence from the non-volatile storage, decompressing the third code sequence and copying the resulting decompressed code to said predesignated portion of RAM.

10. The method of claim 9 wherein said compressed portion is compressed by having a token code representing a repeated code sequence, said repeated code sequence being longer than said token code, said token code identifiable by said CPU running said decompression utility code to replace said token with said repeated code sequence during decompression.

11. A method of decompressing a compressed portion of code from a non-volatile memory unit and copying the resulting decompressed code beginning at a designated position in RAM in a general-purpose computer having a CPU, comprising the steps of: copying code one line at a time in order from said EPROM to said RAM when the value of the one line does not match a flag value; loading a next line and copying to next positions in RAM a multiple-line code sequence associated in a table with the value of said next line when said one line matches a flag value; checking after each copy to RAM if the most recently loaded line of code is the last line in the non-volatile memory unit, and if so diverting control to said designated position in RAM.