 |
Claims  |
|
|
We claim:
1. A method of storing a bit image in a memory of a laser printer that
contains the memory, an interpreter/rasterizer, and a print engine, the
method comprising:
receiving a stream of page description language codes into the printer;
converting said page description language codes into a bit image by
interpreting the page description language codes in the
interpreter/rasterizer;
compressing said bit image into a compressed bit image whereby storage of
said compressed bit image requires less memory space than storage of the
bit image, yet said compressed bit image retains all of the information
contained in the bit image whereby an identical copy of said bit image is
extractable from said compressed bit image, the step of compressing the
bit image further comprising the steps of:
initially compressing portions of the bit image using a first compression
algorithm;
after said compressing using said first compression algorithm, determining
if said compressed bit image that said
first compression algorithm yields has a compression ratio above a
predetermined limit; and
if determined that said compressed bit image that said first compression
algorithm yielded does not have a compression ratio greater than said
predetermined limit, compressing said portions of the bit image using a
second compression algorithm, wherein said second compression algorithm is
computationally more complex than said first compression algorithm but
said compressed portions of the bit image yielded by said second
compression algorithm is smaller than said compressed bit image yielded by
said first compression algorithm;
storing said compressed bit image into a specified portion of the memory;
decompressing said compressed bit image whereby said decompressed bit image
is identical to the bit image that was initially compressed; and
sending said decompressed bit image to the print engine.
2. A method of storing a bit image in a memory of a laser printer that
contains the memory, an interpreter/rasterizer, and a print engine, the
method comprising:
receiving a stream of page description language codes into the printer;
converting said page description language codes into a bit image by
interpreting the page description language codes in the
interpreter/rasterizer;
compressing said bit image into a compressed bit image whereby storage of
said compressed bit image requires less memory
compressing said bit image into a compressed bit image whereby storage of
said compressed bit image requires less memory space than storage of the
bit image, yet said compressed bit image retains all of the information
contained in the bit image whereby an identical copy of said bit image is
extractable from said compressed bit image, the step of compressing the
bit image further comprising the steps of:
initially compressing portions of said bit image using a first compression
algorithm;
after said compressing using said first compression algorithm, determining
if said compressed bit image that said first compression algorithm yields
has a compression ratio above a predetermined limit; and
if determined that said compressed bit image that said first compression
algorithm yielded does not have a compression ratio greater than said
predetermined limit, compressing subsequent portions of the bit image
using a second compression algorithm, wherein said second compression
algorithm is computationally more complex then said first compression
algorithm but said compressed subsequent portions of the bit image yielded
by said second compression algorithm are smaller then would be compressed
subsequent portions of said bit image if said subsequent portions of said
bit image were compressed by said first compression algorithm;
storing said compressed bit image into a specified portion of the memory;
decompressing said compressed bit image whereby said decompressed bit image
is identical to the bit image that was initially compressed; and
sending said decompressed bit image to the print engine.
3. A method of storing a bit image in a memory of a laser printer that
contains the memory, an interpreter/rasterizer, and a print engine, the
method comprising:
receiving a stream of page description language codes into the printer;
converting said page description language codes into a bit image by
interpreting the page description language codes in the
interpreter/rasterizer;
compressing said bit image into a compressed bit image whereby storage of
said compressed bit image requires less memory space than storage of the
bit image, yet said compressed bit image retains all of the information
contained in the bit image whereby an identical copy of said bit image is
extractable from said compressed bit image;
storing said compressed bit image into a specified portion of the memory;
decompressing said compressed bit image whereby said decompressed bit image
is identical to the bit image that was initially compressed; and
sending said decompressed bit image to the print engine,
wherein the step of compressing said bit image comprises the step of using
a Lempel-Ziv algorithm to compress said bit image,
wherein said Lempel-Ziv algorithm maintains a maximum copy count variable,
wherein said Lempel-Ziv algorithm initializes said maximum copy count
variable to a first predetermined value, and when said Lempel-Ziv
algorithm attempts to compress data within a predetermined number of bytes
from the end of the bit image, said Lempel-Ziv algorithm reduces the value
of said maximum copy count variable.
4. A method of storing a bit image in a memory of a laser printer that
contains the memory, an interpreter/rasterizer, and a print engine, the
method comprising:
compressing a portion of a bit image stored in a source block of memory
into a compressed bit image and storing said compressed bit image into a
first destination block of memory, stopping said compressing when either
all of said bit image has been compressed or said first destination block
of memory is full, whereby storage of said compressed bit image requires
less memory space than storage of the bit image, yet said compressed bit
image retains all of the information contained in the bit image whereby an
identical copy of the bit image is extractable from said compressed bit
image: and
if said first destination block of memory is full, requesting a second
destination block of memory, and then performing said compressing step to
compress to said second destination block of memory instead of said first
destination block of memory; and
repeating until the bit image in said source block is fully compressed,
wherein said requesting said second destination block of memory comprises
the steps of:
determining the desired size of said second destination block of memory by
use of the equation
m=(s2.div.(s1+d1))
where
m is the desired size of said second destination block of memory
s1 is the size of that portion of said source block of memory that was
compressed to said first destination block of memory
d1 is the size of said first destination block of memory
s2 is the size of that portion of said source block of memory that was not
compressed to said first destination block of memory; and
requesting said second destination block of memory of size m.
5. A laser printer comprising:
memory;
means for converting page description language codes into a bit image by
interpreting the page description language codes;
a print engine;
means for receiving a stream of page description language codes into the
printer and providing them to said means for converting;
means for compressing the bit image developed by said means for converting
into a compressed bit image whereby storage of said compressed bit image
requires less memory space than storage of the bit image, yet said
compressed bit image retains all of the information contained in the bit
image whereby an identical copy of the bit image is extractable from said
compressed bit image, said means for compressing further comprising:
means for initially compressing portions of the bit image using a first
compression algorithm;
means for determining if said compressed bit image that said first
compression algorithm yields has a compression ratio above a predetermined
limit; and
means for compressing said portions of the bit image using a second
compression algorithm if said compressed bit image that said first
compression algorithm yields does not have a compression ratio above a
predetermined limit, wherein said second compression algorithm is
computationally more complex than said first compression algorithm but
said compressed portions of the bit image yielded by said second
compression algorithm is smaller than said compressed bit image yielded by
said first compression algorithm;
means for storing said compressed bit image into a specified portion of the
memory;
means for decompressing said compressed bit image whereby the decompressed
bit image is identical to the bit image that was initially compressed; and
means for sending said decompressed bit image to said print engine.
6. A laser printer comprising:
memory;
means for converting page description language codes into a bit image by
interpreting the page description language codes;
a print engine;
means for receiving a stream of page description language codes into the
printer and providing them to said means for converting;
means for compressing the bit image developed by said means for converting
into a compressed bit image whereby storage of said compressed bit image
requires less memory space than storage of the bit image, yet said
compressed bit image retains all of the information contained in the bit
image whereby an identical copy of the bit image is extractable from said
compressed bit image, said means for compressing further comprising:
means for initially compressing portions of said bit image using a first
compression algorithm;
means for determining if said compressed bit image that said first
compression algorithm yields has a compression ratio above a predetermined
limit; and
means for compressing subsequent portions of the bit image using a second
compression algorithm if said compressed bit image that said first
compression algorithm yielded does not have a compression ratio greater
than said predetermined limit, wherein said second compression algorithm
is computationally more complex then said first compression algorithm but
said compressed subsequent portions of the bit image yielded by said
second compression algorithm are smaller then would be compressed
subsequent portions of said bit image if said subsequent portions of said
bit image were compressed by said first compression algorithm;
means for storing said compressed bit image into a specified portion of the
memory;
means for decompressing said compressed bit image whereby the decompressed
bit image is identical to the bit image that was initially compressed; and
means for sending said decompressed bit image to said print engine.
7. A laser printer comprising:
memory;
means for converting page description language codes into a bit image by
interpreting the page description language codes;
a print engine;
means for receiving a stream of page description language codes into the
printer and providing them to said means for converting;
means for compressing the bit image developed by said means for converting
into a compressed bit image whereby storage of said compressed bit image
requires less memory space than storage of the bit image, yet said
compressed bit image retains all of the information contained in the bit
image whereby an identical copy of the bit image is extractable from said
compressed bit image, said means for compressing further comprising:
means for using a Lempel-Ziv algorithm to compress said bit image in which
said Lempel-Ziv algorithm maintains a maximum copy count variable, wherein
said Lempel-Ziv algorithm comprises:
means for initializing said maximum copy count variable to a first
predetermined value and for reducing the value of said maximum copy count
variable when said Lempel-Ziv algorithm attempts to compress data within a
predetermined number of bytes from the end of the bit image;
means for storing said compressed bit image into a specified portion of the
memory;
means for decompressing said compressed bit image whereby the decompressed
bit image is identical to the bit image that was initially compressed; and
means for sending said decompressed bit image to said print engine. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention pertains to computer data compression technology and
computer printer technology. More specifically, this invention pertains to
the addition of margin white space to and then compression of bit map
images in a printer, and storing the compressed images in bands of memory
for later use by the printer.
2. Description of the Related Art
Technology associated with printers and printing has ridden the tide of the
rapid advances of computer technology in general. From the days of the
daisy wheel and the nine pin dot matrix printers, we have now come to an
era of affordable laser, ink jet, and even color high resolution printing.
As the resolutions and corresponding print qualities have risen
dramatically, so have the amounts of memory required to drive these
printers. Multi-megabyte memory configurations are becoming more common as
the resolutions rise.
For example, in monochrome laser printing an image is typically rendered at
300 dots per inch, requiring nearly one megabyte of random access memory
for a letter size page. This same image rendered at 600 dots per inch
results in a four-fold increase in the required memory, or approximately
four megabytes. Higher resolution is not the only cause of increasing
memory demands. Color or gray scale images typically require 2 to 32 bits
of information for each pixel of the rendered bit image. A letter sized
image rendered at 600 dots per inch using 32 bits of color information
would require not four megabytes of memory but rather 128 megabytes of
memory. The cost of more memory is passed to the consumer either in the
initial price of the product or as the cost of an optional memory upgrade.
One development in the field of high resolution printing has involved the
transmission of images from the host computer to the printer itself. The
transmission of an entire page in a discrete bit image, or rasterized,
format created two serious problems as resolutions rose. First, the
printer and the host computer were often linked by a relatively slow
serial data path, and the transmission of an entire page in rasterized, or
bit image, form could lead to unacceptably slow transmission times because
of this bottleneck. Second, as resolutions increased and more memory was
required to hold an entire rasterized page, it became inefficient to
generate that rasterized page in the memory of the host computer itself.
Many host computers did not even contain one megabyte of memory, and as
that is the amount of memory typically needed for a letter size page, such
rasterization was not feasible.
Partially in response to these problems, page description languages were
developed. Page description languages describe pages as a group of
graphical and textural objects rather than as bit images. For example, a
circle might be represented by a data structure giving a center location
and a radius. This object oriented approach can lead to far more efficient
representation of graphical and textual data. The memory needed to store a
bit image is a function of the page size, pixel density, and number of
bits of information per pixel. Memory requirements for a set of page
description language commands describing a page, on the other hand, are
typically proportional to the complexity of the page itself. A very simple
page requires few commands and correspondingly little memory to store,
while a more complex page requires more memory. For all but the most
complex pages, the amount of memory required to store the associated page
description language commands is typically less than the amount required
to store the corresponding rasterized page image.
The lower memory requirements led to shorter transmission times to the
printer. Page description languages also facilitated page generation "on
the fly" rather than storing all of the page at one time. This in turn
required less memory usage by the host computer. Once the command to
generate a circle had been sent, for example, it need not be stored in the
host computer memory but could instead be discarded.
An application program can easily create page description language output
as all it need do is generate the required "commands" in that language.
Then, that page description language text is transmitted to the printer,
where an interpreter/rasterizer interprets the codes of the page
description language text and rasterizes the page represented by those
codes into a bit image. In other words, the interpreter/rasterizer
translates the page description language codes into a bit image of the
page. That bit image is then stored in the printer memory rather than the
host computer memory.
Page description languages further allow for a single software interface to
be used with a variety of hardware platforms. A printer's resolution may
be lower or higher, the page size may be larger or smaller, but this can
all be handled in the implementation of the interpreter/rasterizer that
converts the page description language code to a bit image. Thus, the host
computer need not know the specifics of the hardware that the
interpreter/rasterizer drives.
These page description languages are very well known and include Postscript
and Postscript Level 2 by Adobe Systems Incorporated and PCL 5. The
interpreter/rasterizer is typically run on its own microprocessor; for
example, the 68000 series by Motorola, Inc. or the Am29000 series by
Advanced Micro Devices, Inc., can execute the programmed
interpreter/rasterizer.
In practice, an application program or the system software of a host
computer generates the page description language code for a page and then
transmits that code to the printer. There, the software in the
interpreter/rasterizer interprets the page description language code,
converting the code into a bit image for printing by the print engine. The
interpreter/rasterizer will have an associated random access memory of
arbitrary size for use as storage for the rasterized bit image, for
working memory, for storing subsequent pages, for storing font images, or
for other typical memory uses of an interpreter/rasterizer. Typically, the
rasterized image will be stored in bands, with multiple bands per page,
which can be retrieved for transmission to the print engine and discarded
when no longer needed.
Some page description languages do provide for compression of the page
description language code itself. Before transmission, the code is
compressed using one of a number of well known compression algorithms, and
then when received by the printer that code is decompressed. This allows
for shorter transmission times, as less data is being transmitted to
convey the same amount of information.
Data compression techniques are very well known in the computing field. For
example, a class of algorithms known as Lempel-Ziv 77, or LZ77, is widely
used for adaptive lossless data compression. Another class known as LZ78
is now more commonly used, but the LZ77 class has unique features that
make it particularly suitable to some applications. These algorithms are
well known in the art, and a good overview is provided in Ross N.
Williams, An Extremely Fast Ziv-Lempel Data Compression Algorithm, DCC '91
Data Compression Conference 362 (James A. Storer & John H. Reif eds.,
1991).
In the past, Lempel-Ziv 77 algorithms have had drawbacks that led to
inefficiency. For example, those algorithms typically stopped compressing
towards the end of a source block. Further, those algorithms typically did
not initialize the hash table they used that pointed to data that had been
previously compressed. This caused a loss of speed and efficiency when
first compressing the data.
The interpreter/rasterizer's use of its random access memory is one area of
printer technology ripe for improvement. While page description languages
have been invaluable in the generation and transmission of pages, the
interpreter/rasterizer must still generate and store a rasterized image of
a page in its own memory. As seen above, the memory requirements for a
full rasterized page can be enormous.
Developers have used various techniques to reduce these memory requirements
within the printer itself. For example, very high end laser printers use a
start/stop technique in which they reduce their memory requirements by
printing a small section of the page, stopping the print process while the
next section of the page is rasterized into memory, and then restarting
the print process, repeating these steps until done. These machines
typically print at very high resolutions and are quite complex
mechanically. In a technique used by PCL 5, the page description language
codes are sequenced such that those commands pertaining to the top of the
page are placed in the beginning of the source code file and those
pertaining to the bottom of the page are placed at the end. The printer is
then started and the printer processor that renders the bit map image a
band at a time "races" the print engine, or the part of the printer that
does the actual printing, by attempting to interpret the codes and render
the image at least as fast as the print engine can print the rendered
image. This technique, however, usually fails on complex pages, and the
user must install more memory to print anything but very simple images.
One area in which current printers lose efficiency in their use of their
internal memories is in the storage of margin white space. Printers
typically store the white space representing the left and right margins on
a page even when the logical margin is larger than the physical margin
required by the print engine. This is in part because of how an
interpreter/rasterizer transmits data to the print engine. The print
engine typically expects the interpreter/rasterizer to transmit a full
scan line of data to the print engine. A scan line is simply the memory
representation of one row of the printed bit image. This scan line,
however, is physically typically of a fixed number of bits, that number
being set by the requirements of the print engine. Logically, however, an
interpreter/rasterizer need only store the scan line data up to the
beginning of the right margin white space. This follows from the manner in
which print engines physically function; when the print engine receives
nothing, it leaves the corresponding bit white. Thus, the
interpreter/rasterizer can simply send nothing to the print engine at the
end of the scan line, and therefor need not store anything.
Interpreters/rasterizers typically include any logical margin white space
at the front of each scan line. This logical margin white space, when
added to the physical margin necessitated by the print engine, forms the
full margin. As each page will have a fixed logical margin, however,
storage of this margin white space is very inefficient.
Thus, it would be desirable to improve the efficiency of the memory usage
by the interpreter/rasterizer in the printer itself. More specifically, it
would be desirable if less memory were required to store a bit image.
SUMMARY OF THE PRESENT INVENTION
A printer built according to this invention is more efficient in using its
internal memory, thus allowing the storage of more and larger rasterized
images. Such a printer achieves this greater efficiency by actually
compressing bit images after receiving page description language codes
from a host computer and rasterizing those codes but before storing the
rasterized image in the printer memory.
Further, a printer built according to this invention will typically
compress this data from bands of a full page's rasterized bit image and
then store the compressed bands in the printer memory to be retrieved and
decompressed when it is desired to print that band of the page. If the
printer's rasterizer/interpreter needs to modify a particular band, it
decompresses that compressed band into a working memory, manipulates the
data as it needs, and then recompresses that band and again stores it in
the printer memory.
When it is desired to print a band of memory, a printer according to this
invention transmits the compressed band of memory to a hardware
decompression engine, which decompresses the band and transmits the
decompressed scan lines to the print engine. This frees up the processor
running the rasterizer/interpreter to perform other functions, such as
interpreting the next page of page description language code.
Although a number of algorithms can be used to compress the bit images
stored in the printer memory, a device according to this invention
typically uses a Lempel-Ziv 77 type of algorithm. A printer built
according to this invention has improvements in that algorithm that
provide even greater efficiency and speed in compressing, decompressing,
and storing the rasterized bit image.
One way this higher efficiency is achieved is through initialization of the
hash table used by the Lempel-Ziv 77 algorithm in compressing its data.
Typically, Lempel-Ziv 77 algorithms do not initialize their hash table,
but instead determine the validity of the data pointed to in the hash
table during the compression process itself. In the Lempel-Ziv 77
algorithm of a printer built according to the invention, the hash table is
first initialized to point to the first element of uncompressed data. This
improves the speed of the algorithm in compressing the bit image data.
Further, the Lempel-Ziv 77 algorithm according to the invention is improved
in its compression towards the end of a block. Typically, Lempel-Ziv 77
algorithms copy the last portion of the block of data they compress in
uncompressed form. This is so because those algorithms typically do not
check for the end of the uncompressed block while they are actually
compressing portions of the data. In a printer built according to the
invention, the Lempel-Ziv 77 algorithm improves compression by reducing
the number of bytes of data that can be stored in any one compressed unit
when the end of the block is near.
A printer built according to the invention improves its use of memory
further by not storing in uncompressed form any left margin data
associated with the logical left margin. When compressing the data, the
printer then adds any margin white space needed. Thus, the white space is
stored only in compressed form. This white space can usually be compressed
very efficiently.
A printer built according to this invention further achieves more efficient
memory usage by dynamically switching between compression algorithms
depending upon the memory-speed trade-off. If memory requirements are
tight, then the compression routine uses a form of the Lempel-Ziv 77
algorithm that is slower but has a higher compression ratio. When memory
requirements are more relaxed, the printer according to the invention uses
a higher speed but less compression efficient form of the Lempel-Ziv 77
algorithm. Further, it inserts flags into the data produced by the
compression algorithm to indicate which algorithm should be used in
decompressing the data.
The printer according to the invention also saves memory by allowing the
use of a destination buffer for its compression algorithm that might not
be large enough to hold the compressed bit image. As it is impossible to
know beforehand the ultimate size of a compressed image one would have to
provide extra destination space to prevent an error. In a printer
according to this invention, however, if the compression algorithm
exhausts its destination block space while compressing an uncompressed
band of bit image, it simply requests more memory space from the
interpreter/rasterizer. It calculates the size of this needed memory based
upon the remaining size of bit image to compress as well as the
compression ratio it has achieved in compressing the previous uncompressed
bit image.
While this is an overview of a printer according to this invention, details
and other aspects of the invention will become apparent in the detailed
description that follows.
BRIEF DESCRIPTION OF THE DRAWINGS
A better understanding of the present invention can be obtained when the
following detailed description of the preferred embodiment is considered
in conjunction with the following drawings, in which:
FIG. 1 shows a block diagram of the logical elements of a printer
constructed according to the present invention.
FIG. 2 shows a typical memory map in a printer constructed according to the
present invention.
FIG. 3 shows the control word structure used by the Lempel-Ziv algorithms
used according to the present invention.
FIG. 4 shows the data blocks and ring buffer used to add margin white space
in a printer constructed according to the present invention.
FIG. 5 shows data structures used in compressing data under prior art
Lempel-Ziv 77 algorithms.
FIGS. 6A-6E show a flow chart of a compression routine written according to
the present invention.
FIG. 7 shows a flow chart of a decompression routine written according to
the present invention.
FIG. 8 illustrates how a routine would request additional destination space
if written according to the present invention.
FIG. 9 shows a Lempel-Ziv 77 compression algorithm hash table initialized
according to the present invention.
FIGS. 10A-10B illustrate margin white space added to an image according to
the present invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
Turning now to the drawings, FIG. 1 shows a block diagram of the major
components of a printer constructed according to the present invention.
The blocks and arrows illustrate the typical data flow in such a printer.
An interpreter/rasterizer 100 receives the page description language (PDL)
code from a host computer. The PDL could be any conventional PDL such as
Postscript Level 2 or PCL 5, or preferably both on a document by document
basis. This interpreter/rasterizer 100 typically consists of a
microprocessor running a page description language interpreter program;
this program interprets the page description language code and from that
code generates a rasterized bit image.
This rasterized bit image is then stored in a bit image memory 102. As can
be seen from the arrows, the interpreter/rasterizer 100 can also retrieve
this rasterized bit image from the bit image memory 102 if the
interpreter/rasterizer 100 needs to make changes in the rasterized bit
image. In prior printers, this rasterized bit image was simply stored in
its rasterized form. In a printer according to this invention, however,
the rasterized bit image is first compressed by a compression routine 104.
Thus, the interpreter/rasterizer 100 receives page description language
code from a host computer, converts that code into a rasterized bit image,
compresses that rasterized bit image using the compression routine 104,
and then stores the resulting bit image in the bit image memory 102.
The interpreter/rasterizer 100 may need to modify a stored bit image, and
to do so needs to decompress that stored bit image. The
interpreter/rasterizer 100 retrieves the stored bit image from the bit
image memory 102 and then decompresses that stored bit image using a
decompression routine 106. The decompression routine 106 is the
counterpart to the compression routine 104. The decompressed bit image is
appropriately modified, recompressed using the compression routine 104,
and again stored in the bit image memory 102.
The stored bit image cannot be directly printed because it is in compressed
form. So, when it is desired to print the bit image, the stored image in
the bit image memory 102 is decompressed by a hardware decompression
engine 108, which then sends the decompressed image to a print engine 110.
The hardware decompression engine 108 is typically a hardware
implementation of the software used to implement the decompression routine
106. In the preferred embodiment, the hardware decompression engine 108 is
implemented in an application specific integrated circuit. The print
engine 110 is typically a serial device, in that it takes bits of data and
serially stores those bits until it has a full page width of data, or a
scan line. Then, the print engine 110 prints that scan line as a row of
pixels. Then, of course, it prints another row of pixels, typically
storing possibly one or two scan lines ahead.
In a laser printer built according to the invention, the
interpreter/rasterizer 100 will typically be built using a microprocessor,
such as the Advanced Micro Devices Am29000. This is a 32-bit RISC
processor which can very quickly process the codes of page description
language text. Associated with this processor would typically be
associated random access memory making up the bit image memory 102, and
likely would also include a read only memory, or ROM, which contains the
software used to drive the microprocessor so that it can accomplish its
interpreter/rasterizer functions. The decompression engine 108 will
typically be a hardware ASIC, or application specific integrated circuit.
This ASIC would be used when a general purpose processor would not be able
to decompress the compressed image quickly enough for the print engine, or
could also be used to leave the general purpose process free to perform
other tasks. Finally, the print engine 110 is typically a Fuji or Canon
print engine, both of which are well known print engines using replaceable
cartridges and drums. Of course, this hardware is only illustrative, and
the invention could be exercised using a number of other hardware and
software platforms, and in fact could be exercised in hardware other than
a printer, such as facsimile and scanning technology.
Memory
The bit image memory 102 shown in FIG. 1 has been described in simplified
terms. In actual practice, the bit image memory 102 will typically contain
far more than simply the compressed stored bit image.
FIG. 2 shows how the interpreter/rasterizer 100 according to this invention
typically uses the bit image memory 102. FIG. 2 shows a map of the bit
image memory 102, which is divided into working memory 200, uncompressed
band memory 202, and compressed band memory 204. These memory areas are
not of arbitrary size or location but instead can be adjusted by the
interpreter/rasterizer 100 depending on the needs of the system and the
complexity of the current page. Further, the memory map shown in FIG. 2 is
illustrative only, and could be implemented in a variety of ways depending
on the interpreter/rasterizer 100. The working memory 200 is typically
used for a variety of purposes such as for calculations used in converting
the page description language page into a bit image and for storage of the
bit images of individual characters generated from an outline font.
Interpreter programs for page description languages typically work with the
rasterized page in bands of memory. As previously described, for example,
PCL 5 attempts to "race" the print engine by generating bands of bit image
ahead of the print engine. In a printer built according to this invention,
however, not only are the uncompressed bit images stored in bands of
memory, but also the compressed bit images. The interpreter/rasterizer 100
can then interpret the incoming PDL code one uncompressed band at a time,
and then immediately convert that uncompressed band into a compressed
band. This prevents the need for storing an entire uncompressed page in
memory before converting it to a compressed page.
Thus, in a printer according to this invention, the bit image memory 102
contains bands of both uncompressed and compressed bit image. In the bit
image memory 102, the uncompressed band memory 202 contains one or more
bands of memory for the storage of uncompressed bands 206 of rasterized
bit image. Similarly, the compressed band memory 204 contains a number of
compressed bands 208 for storage of compressed segments of rasterized bit
image. Because of the band oriented aspect of typical page description
languages, the interpreter/rasterizer 100 generates a band of uncompressed
image representing a portion, or band, of a page, and stores that as an
uncompressed band 206 in the uncompressed band memory 202. This
uncompressed band 206 typically includes an arbitrary number of scan
lines, and is not split in the middle of a scan line. Once a full
uncompressed band is generated, the interpreter/rasterizer 100 immediately
compresses that uncompressed band 206 and stores the resulting compressed
band of bit image in a compressed band 208 in the compressed band memory
204.
The bit image memory 102 typically contains a relatively large number of
compressed bands 208, for example 64 to 256 compressed bands, and
relatively few uncompressed bands 206. This memory may have only one
uncompressed band 206 but would more likely have two or more. Having more
than one uncompressed band 206 allows an uncompressed bit image to be
rendered in a first uncompressed band 206 while a second uncompressed band
206 is being compressed into a compressed band 208. Then, once the first
uncompressed band is fully rasterized, it can be compressed into a
compressed band 208 while an uncompressed bit image is built into the
second uncompressed band 206.
Each uncompressed band 206 is typically of arbitrary size, such as 500
kilobytes. Whatever the size, each uncompressed band 206 is typically made
up of an integral number of scan lines; that is, a scan line is not split
between two uncompressed bands 206. The compressed bands 208, however, of
course vary in size depending on the compression ratio achieved by the
compression routine 104. The compression ratio is defined as the size of
an uncompressed image divided by the size of its corresponding compressed
image. Because the interpreter/rasterizer 100 attempts to store as much of
a page bit image as possible in the compressed band memory 204, less
memory is needed to store a fully rasterized page using the compressed
bands 208.
The Lempel-Ziv 77 Algorithm
To better understand the advantages of the invention, it is of assistance
to be familiar with the Lempel-Ziv class of algorithms. These algorithms
are well known in the computer art, and a good overview is provided in
Ross N. Williams, An Extremely Fast ZIV-Lempel Data Compression Algorithm,
DCC '91 Data Compression Conference 362 (James A. Storer & John H. Reif
eds., 1991). The algorithm actually used in the preferred embodiment is
slightly different from the one disclosed in the article, but follows the
same principles.
As described in the Williams article, data compressed under a Lempel-Ziv
algorithm is made up of control words and literals. As shown in FIG. 3, a
24-bit byte mode control word 300 is used in the compressed data. This
byte mode control word 300 consists of an offset count 304, a literal
count 306, and a copy count 308. The literal count 306, a value between 0
and 63, specifies how many of the following bytes in the compressed code
are literals. For example, if the literal count 306 is five, then the next
five bytes of data are copied to the uncompressed destination block
directly.
The offset count 304 and copy count 308 are the fields through which actual
compression is accomplished. The copy count 304, a value between 0 and
255, indicates how many bytes of data recently written to the uncompressed
destination block ar | | |
