 |
Claims  |
|
|
What is claimed is:
1. In a peripheral unit that converts an input data flow to a page-arranged
output, said peripheral unit including random access memory with allocated
memory space for storing only a portion of said page-arranged output, a
processor and control memory containing a plurality of data compression
procedures, each said procedure exhibiting a speed of compression
performance characteristic, a method for compressing portions of said
input data flow for storage in said random access memory, said method
comprising the steps of:
allocating portions of said input data flow for storage in said random
access memory;
determining when an insufficient amount of said random access memory is
available for allocation to said input data flow portions;
employing a first data compression procedure upon a said input data flow
portion to produce a compressed data portion, said first data compression
procedure generally accomplishing data compression in less time than other
data compression procedures available in said peripheral unit;
testing a compression level of said compressed data portion against a
compression threshold to determine if said compression level exceeds said
threshold, and if not, employing another data compression procedure and
repeating said testing in relation to a threshold, whereby a compression
procedure is found that enables the compression level of said input data
flow portion to exceed a said threshold and is employed to compress said
data flow portion.
2. The method as recited in claim 1 wherein said data compression
procedures comprise ones which compress data in a lossless manner and at
least another which compresses data in a lossy manner, data compressed in
a lossless manner being decompressible with no loss of data and data
compressed in a lossy manner being decompressible only with loss of data,
a said lossless compression procedure being employed first before said
lossy compression procedure.
3. The method as recited in claim 2 wherein one said lossless compression
procedure is a Lempel/Ziv/Welch (LZW) compression procedure, said
procedure building a table of received data strings and assigning a code
to each said string, the method further comprising:
limiting the number of string entries in said table to less than a maximum
required to obtain optimum data compression, so as to limit a code length
required to identify a said string, thereby enabling compression and
decompression actions to occur at a faster rate.
4. The method as recited in claim 1 wherein subsequent to said allocating
step but prior to said determining step, the method comprises an
additional step of:
determining if any said data portion exceeds a predetermined data size, and
if so, further determining if allocatable memory remaining within said
random access memory is less than a predetermined level, and if both
determinations are affirmative, subjecting said data portion to data
compression.
5. The method as recited in claim 4 wherein said data compression is
accomplished by use of a lossless compression procedure.
6. The method as recited in claim 5 further comprising the steps of:
storing said data portion in random access memory after it has been data
compressed; and
adjusting said predetermined level by subtracting therefrom memory space
taken by said stored data portion.
7. The method as recited in claim 1 wherein said peripheral unit includes a
print engine that, when operative, runs at a constant speed, said method
comprising the additional steps of:
calculating a complexity factor for data portions within a page and
determining if said complexity factor indicates that too great a time will
be required to convert said data portions to a raster video format in
relation to said print engine speed; and
upon such a determination, subjecting at least one data portion to
immediate conversion to a raster video format and performing data
compression thereon.
8. The method as recited in claim 7, wherein if at any time subsequent to
said conversion and compression of said one data portion, it is determined
that remaining data portions can be acted upon without causing a memory
out indication, said remaining data portions are converted to raster video
without compression.
9. The method of claim 1 wherein a said image data includes font data, the
method comprising the further step of:
automatically applying a lossless compression technique to said font data
if a font represented by said font is at least equal in size to a
predetermined level.
10. The method of claim 9 wherein, if said font size is not equal to said
predetermined level, applying said lossless compression technique only in
the event random access memory for storing said image data is insufficient
in capacity.
11. A method for data compressing a raster pixel image, comprising the
steps of:
a. performing run-length encoding for data segments in an initial raster
row of said image and outputting, for each run of a data segment in said
row, a run length command indicating a run count and an identification of
the run data segment; and
b. for data segments in a subsequent row of said image, comparing whether
said data segments are the same as or different from data segments in an
immediately previous raster row; and
c. issuing commands which identify for said subsequent raster row, which of
said data segments exhibit said "same" condition and further indicate said
different said data segments.
12. The method as recited in claim 11 wherein step(b) further identifies a
presence of a run of data segments in a said subsequent raster row and
outputs a run command comprising a count and an identity of the data
segment that is repeated in said run.
13. The method as recited in claim 12 wherein said further identification
of a run of a data segment only occurs after a different data segment is
determined and before a same data segment is next detected.
14. The method as recited in claim 13 wherein run length encoding may span
from raster row to raster row until a said run ends.
15. The method as recited in claim 11 wherein said command issued in step c
includes a count of the number of same data segments, followed by a count
of and an identity of different data segments that follow said same data
segments.
16. The method as recited in claim 11 further comprising the step of:
eliminating any commands issued for a raster row if said row is found to be
identical to an immediately adjacent row; and
issuing a repeat row command that causes said immediately adjacent row to
be repeated.
17. The method as recited in claim 11, further comprising the steps of:
inserting an end of row command when a run of zeros is sensed at an end of
a row; and
upon decompression, padding with zeros any row that ends prior to a
predetermined row length.
18. A method for data compressing a raster-arranged pixel image, comprising
the steps of:
a. providing a first table of data segment patterns indicative of an image
comprised of clustered bit patterns and of an image comprised of dispersed
bit patterns;
b. comparing data segments of an image to said data segment patterns in
said first table to determine a classification of said image, said
classification comprising clustered or dispersed;
c. compressing said image by reducing each n.times.n bit block of said
pixel image to an n-bit data segment and accompanying said compressed
image by a classification indicator; and
d. decompressing said image by employing said n-bit data segment to access
a stored n.times.n pixel matrix from a pair of matrix tables in accordance
with said classification indicator, one said tables including
n.times.n-bit images classified as clustered and another said table
including n.times.n-bit images classified as dispersed, each said table
addresses in accordance with said n-bit data segment.
19. The method as recited in claim 18 wherein said image is classified as
either clustered or dispersed by assigning a first value to any data
segment of said image that matches a clustered data segment pattern in
said first table and assigning a second value to any data segment that
matches a dispersed data segment pattern in said first table, said
classification determined by combining said first and second values and
comparing said combined values to a threshold.
20. The method as recited in claim 19 wherein said first values are
positive numbers and said second values are negative numbers, said
threshold being a neutral value therebetween.
21. In a peripheral unit for converting an input data flow to a
page--arranged output, said peripheral unit having insufficient random
access memory allocated to store an entire video raster image of said page
arranged output, a method for converting said input data flow to a page
intermediate form that includes a plurality of image strips that make up
said page arranged output, each image strip including image processing
commands that enable subsequent conversion of each said image strip to a
raster video form, said method comprising:
a. establishing a threshold value of data segments in an image strip;
b. determining (1) if a number of data segments in an image strip exceeds
said threshold value, and (2) if remaining memory in said random access
memory is less than a predetermined level and if said determinations 1 and
2 are affirmative;
c. converting said image strip immediately to raster video and attempting a
compression thereof;
d. storing in said random access memory, compressed raster video that
results from step c;
e. adjusting said threshold value to a smaller value to account for
remaining random access memory in said random access memory; and
f. repeating steps a-e for remaining image strip of said page.
22. The method as recited in claim 21 wherein step (c) employs a
compression action that examines blocks of raster data and performs
compression actions that take into account both vertical and horizontal
data redundancies in each said block of raster data.
23. The method as recited in claim 22 wherein said compression action
comprises the steps of:
providing output commands which indicate vertical redundancies existing
between succeeding rows of a block of raster data and further providing
commands indicative of horizontal data redundancy occurring in a said row.
24. A method as in claim 21 where the strip complexity can be empirically
determined by measurement with a system timer, and this result used to
ascertain whether to pre-rasterized the strip when the complexity
prediction is within the uncertain complexity window.
25. In a peripheral unit that converts an input data flow to a
page-arranged output, said data flow including data describing an image, a
said image comprised of a set of subimages, each subimage further
comprised of a video raster bit map and a descriptor having a field that
identifies where said video raster bit map is stored, a method for
compressing data representing a said image and subimages, comprising:
selecting a group of descriptors that represent a subset of said set of
subimages;
attempting to compress, through the use of a first compression technique,
the video raster bit map associated with each said selected descriptor;
comparing against a threshold, a level of compression of said subset of
subimages achieved through said compression attempt and if said threshold
is at least equalled, employing said first compression technique to data
compress all subimages comprising said image.
26. The method as recited in claim 25 wherein each said descriptor has
fields reserved for indicating facts regarding an associated video raster
bit map, said method further comprising:
employing a second compression technique upon said subset of subimages in
the event said level of compression is not equalled and again comparing an
achieved level of compression against a threshold and employing said
second compression technique for all subimages of said image in the event
said threshold is at least equaled.
27. The method as recited in claim 26 wherein said facts in each said
descriptor are employed during decompression of said image, said facts
indicating the method of compression employed to compress said video
raster bit maps.
28. The method as recited in claim 27 wherein at least said first
compression method is lossless.
29. The method as recited in claim 28 wherein said peripheral unit includes
random access-memory (RAM) whose capacity is insufficient to store an
entire page of said page-arranged output, said method comprising the
further steps of:
determining, subsequent to application of a said compression technique,
whether sufficient space is available in said RAM to store a compressed
image and, if not; applying a lossy compression technique to said
subimages.
30. The method as recited in claim 29 wherein, as part of said lossy
compression technique, said image is classified as either dispersed or
clustered by comparison of video raster bit maps of at least some said
subset of subimages to a table of entries that define bit patterns
comprising clustered and dispersed bit arrangements, said classification
employed during decompression of said lossy compressed image.
31. The method as recited in claim 29, wherein said lossy compression
technique is employed for said image only if a prior applied lossless
compression technique did not exceed a level of compression of said image
that is available from said lossy technique. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF THE INVENTION
This invention relates to page printers, and more particularly, to a page
printer having data compression facilities to accommodate a buffer memory
size that is less than that required for a full page of printer data.
BACKGROUND OF THE INVENTION
Prior art page printers typically capture an entire page before any image
is placed on paper. In such printers, formatting is either performed on
the host computer (with large volumes of rasterized data being shipped to
the printer), or on a formatter within the printer, Since a laser print
"engine" operates at a constant speed, if new rasterized data is not
available at a rate that keeps up with the engines's operation, a print
"overrun" occurs and the page is not printable.
To prevent print overruns, a variety of techniques are in use. In one, a
full raster bit map of an entire page is stored so that the print
mechanism always has rasterized data awaiting action. At 300 dots per inch
resolution, this technique requires approximately a megabyte of raster
memory for each page. At 600 dots per inch, four megabytes of memory are
required. Additionally, because laser printers achieve their rated speeds
by pipelining of raster data, additional raster memory is needed to run
the printer at its rated speed. Otherwise, composition of a following page
cannot begin until a prior page has been ejected to the printer's output
tray. To maintain the cost of laser printers at a low level, substantial
efforts have been directed to reducing the amount of required raster
memory.
One technique for memory reduction involves the construction of a page
description. The page description is built in two steps: during
formatting, data received from a host computer is converted into a list of
simple commands, called display commands, that describe what must be
printed. The second step prepares the display command list for printing
and entails a parsing of the display commands and a rendering of the
described objects into a raster bit map. This procedure requires a full
page raster bit map memory because the same memory is used for succeeding
pages.
To reduce the amount of required memory, the display command list procedure
has been modified by sorting display commands according to their vertical
position on a page. The page is then divided into sections called page
strips or "page intermediate", and each page strip is passed,
sequentially, to the print engine for printing. When display commands
within a page strip are rendered into rasterized data at a fast enough
pace, the same memory used to store a first page strip can be reused for a
subsequent page strip further down the page (once the first page strip has
been transferred to paper).
The Laser Jet III Laser Printer, manufactured by the Assignee of this
application, employs a display command list algorithm and utilizes three
raster buffers. The first buffer is reused on the fourth strip of a page;
the second buffer is reused on the fifth strip, etc. For an eight page per
minute printer, little time is left between the finishing of strip one and
the time when strip four will be required by the print mechanism. If the
strip is not delivered in time, a "print overrun" occurs and the page is
incorrectly printed.
In U.S. patent application Ser. No. 07/701,235, entitled "Method and
Apparatus For Preventing Print Overruns", assigned to the same Assignee as
this application, a page printer determines total rasterization execution
time for all display commands in each strip. If a strip's rasterization
execution time exceeds a predetermined value, the strip is prerasterized,
so as to reduce the time required during subsequent transfer of data to
the print mechanism. The disclosure of the aforesaid patent application is
incorporated herein by reference.
Most recently, 600 dot per inch resolution printers have been introduced to
the marketplace. Such printers handle not only text but also line art and
various types of images. To minimize the amount of memory required in such
printers, data compression techniques are employed. For instance, run
length data compression is used by host processors in the process of data
transfer to the printer. In a run length encoding scheme, data that
repeats is encoded by indicating the identity of the data and the run
length of the repeat. Run length compression is successful when used with
text and line art. When used with image data, however, such a compression
scheme is much less satisfactory.
Certain types of images are classified as either "ordered dither" or "error
diffused". An ordered dither image (also called "clustered") is a
half-tone image that includes half-tone grey representations throughout
the page. Such images generally reflect substantial data redundancy and
lend themselves to lossless techniques of data encoding (e.g. run length).
Error diffused images (also called "dispersed"), by contrast, exhibit
little redundancy in their data and require different methods of
compression. As a result, the use of a single data compression scheme in a
page printer no longer enables such a printer to handle image data--while
still maintaining a minimal amount of on-board raster memory.
In additional to run-length encoding, the prior art is replete with other
data compression schemes. For instance, in U.S. Pat. No. 4,558,302 to
Welch, the well known Lempel/Ziv/Welch (LZW) data compression technique is
described. That procedure compresses an input data stream by storing, in a
string table, strings of characters encountered in an input data stream. A
"compressor" searches the input stream to determine the longest match to a
stored string. As the compressor encounters more and more strings, it
becomes "smarter" and enables succeedingly longer runs of characters to be
compressed. Each match of an input string of characters to a stored table
string causes a code to be transmitted to a receiver, where an identical
string table resides that enables a decoding of the transmission.
Run length data compression on printer raster scan lines is described by
Spivey in "Data Compression Technique for APA Printer (Change Block
Skipping)" and "Hybrid Data Compression Technique for Change Block
Skipping in an APA Printer", IBM Technical Disclosure Bulletin, vol. 23,
No. 12, May 1981, pages 5464-5470. Spivey's procedure compares a current
scan line to a corresponding scan line in a previous image and outputs
codes in dependence upon the concurrence or lack of concurrence
therebetween. Spivey also describes a hybrid technique which employs the
aforesaid method in combination with run-length encoding.
Accordingly, it is an object of this invention to provide a page printer
that includes a system for data compression and is adaptive in response to
characteristics of received data.
It is another object of this invention to provide a page printer that
employs a system that intelligently selects a data compression technique
so as to enable efficient use of a limited amount of on-board memory.
It is yet another object of this invention to provide a page printer with a
system for data compression, which system is selectively called upon when
on-board memory is in a state where printing cannot continue unless data
compression occurs.
It is still another object of this invention to provide improved data
compression techniques for use in a page printer.
SUMMARY OF THE INVENTION
A peripheral unit converts an input data flow to page-arranged outputs and
includes a random access memory capacity that is insufficient in size to
accommodate an entire page of raster data. The peripheral unit also
includes a processor and a control memory that holds a plurality of data
compression procedures, each procedure exhibiting a different performance
characteristic. The peripheral unit performs a method for compressing
portions of the input data flow that includes the steps of: allocating the
random access memory to portions of the input data flow; determining when
an insufficient amount of random access memory is available for such
allocation; employing a first data compression procedure on the input data
flow portions to produce a compressed data portion; testing the compressed
data portion to determine if a level of compression has been achieved that
exceeds a threshold and, if not, employing succeeding data compression
procedures and repeating the test for each procedure against a threshold,
whereby the compression procedure that first enables a threshold level of
compression to be achieved is the compression procedure employed to
compress the data flow portion. Improved compression methods and
techniques for handling input data flows with both integral and
independent image descriptors are also described.
DESCRIPTION OF THE DRAWINGS
FIG. 1 is a high level block diagram of a peripheral unit that is adapted
to carry out the invention.
FIG. 2 is a global flow diagram illustrating the overall procedure of the
invention hereof.
FIG. 3 is a high level flow diagram illustrating the procedure for strip
video pre-generation.
FIGS. 4 and 5 are a high level flow diagram of a high speed data
compression technique, termed mode-m, that is employed herewith.
FIG. 6 is a high level flow diagram illustrating the Lempel/Ziv/Welch data
compression procedure.
FIG. 7 is a high level flow diagram illustrating a Lossy compression
procedure.
FIG. 8 is a high level flow diagram illustrating the procedure employed to
determine whether an image is clustered or dispersed.
FIGS. 9 and 10 illustrate decompression matrices employed in accordance
with findings of the procedure of FIG. 8.
FIGS. 11a and 11b are high level flow diagrams illustrating the procedure
following by the system of FIG. 1 in determining which compression
procedure to employ in a memory out or low circumstance.
FIGS. 12a , 12band 12c illustrate a high level flow diagram for the
procedure followed when "page intermediate" actions have been completed
and it is found that a page is too complex.
FIG. 13 illustrates a descriptor that accompanies a bit map subimage in a
second version of the invention.
FIG. 14 shows a flow diagram of the procedure followed by the second
version of the invention in determining which compression procedure to
employ.
FIG. 15 is a diagram of a page that indicates where a "memory out"
indication occurs in response to the printing of a large point size font.
FIG. 16 is a flow diagram illustrating when compression is applied to a
received-font.
DETAILED DESCRIPTION OF THE INVENTION
Hereafter, the invention will be described in the context of a laser
printer, however it should be understood that other peripheral units such
as plotters, facsimile units, etc. can also make use of the procedures
contemplated by the invention hereof.
PRINTER SYSTEM
In FIG. 1, printer 10 includes a processor 12, print engine 14, and an
input/output (I/O) port 16, all connected by a bus 18. Print engine 14
comprises a laser printer which, when operated, runs at a constant speed
and must be provided with video raster print data at a rate that keeps up
with its operation. A random access memory (RAM) 20 and a read only memory
(ROM) 22 are also connected to bus 18 and contain all of the procedures
necessary to assure that available RAM 20 is most efficiently used, and
that print engine 14 has data awaiting printing--so as to avoid print
overruns.
Printer 10, in this example, is a page printer and receives image data from
a host processor via I/O 16. The amount of memory in RAM 20 that is
available to store the received image data is substantially less than that
required to contain an entire video raster bit-map image of a page. The
size of RAM 20 is constrained so as to enable printer 10 to be marketed at
the lowest competitive price.
Image data from the host processor is received via I/O module 16 and read
into RAM 20. The image data may take one of several forms. It may include
subimages wherein descriptors are contiguous with each subimage and are
processed along with each subimage. When such image data is received, it
is the image data itself that is examined to determine whether data
compression is required or not. In a second version of the invention,
subimage descriptors are received separately from (but linked to) the
actual subimage data. In the second version, data within the descriptor
and other image-specific data is employed to assist in determining which
(if any) of a series of data compression techniques should be applied to
the subimage data.
In both versions of the invention, when printer 10 receives image data, it
is parsed and commands and data are processed to derive raster graphics
data that is stored in RAM 20. At such time, subimages are created. Next,
the subimages contained in the raster graphics data base are linked into
an intermediate page representation ("page intermediate"). Page
intermediate is a means of representing an entire page of information in a
format that is easily convertible to video, while consuming as little
memory as possible. Page intermediate actions essentially divide a page
into a plurality of strips, each strip including a prescribed number of
"instruction buckets". Each strip is allocated a height (e.g., 128 dots)
and contains a pointer to a chain of instruction buckets (e.g. each bucket
being 256 bytes in size), each "bucket" containing instructions which
define how raster video should be created for the strip. Subimages (and
other intermediate objects) that span more than one strip have an
instruction for each strip in which they are resident.
In the conversion of the raster graphics data to page intermediate, it may
become evident that the contents of a strip exceed a threshold that is
based upon the size of the strip's video buffer. It also may occur that
after conversion of a plurality of strips, insufficient memory remains to
complete the page intermediate conversion. Further, after conversion of an
entire page it may become clear that the page is too complex to be stored
within the available RAM. In all of the above cases, the system hereof
performs data compression actions in an attempt to overcome the memory
limitations. In each case, one of a plurality of compression techniques is
chosen, in dependence upon the examination of variables then in existence.
In such manner, an informed choice of a compression procedure is made so
as to enable a most rapid and effective use of available RAM.
Hereafter, three methods of data compression will be described, and it is
to be understood that the choice of which data compression method to use
is dependent upon the performance characteristics desired from the printer
mechanism. For highest speed compression, a procedure entitled mode-m
(where m means multi-dimension changes) compresses a raster image data
block on a run-length basis applied to raster scan rows and on the basis
of changes from row to row. Mode-m is an extremely fast method of data
compression (and decompression), but is not effective to compress certain
types of image data. Mode-m is a "lossless" compression technique (no
image data is lost during the compression technique that cannot be
recovered upon decompression).
A further lossless compression technique, which is slower in action than
mode-m, but is more effective with certain types of image data is a
modified Lempel/Ziv/Welch (LZW) procedure. A third "lossy" compression
procedure is employed which typically guarantees a compression ratio of at
least 4:1, but results in the loss of some image data that cannot be
recovered upon decompression.
Returning to FIG. 1, the subroutines employed in the data conversion and
compression procedures are listed in RAM 20 and ROM 22. RAM 20 includes a
memory area 24 allocated for the user; an area 26 allocated to the storage
of raster images; an area 28 for compressed images, an area 30 for page
intermediate data storage, and an area 32 allocated to the storage of
variables used with the procedures to be described hereinafter.
ROM 22 contains subroutines that carry out LZW compression (34), mode M
compression (36) and lossy compression (38). ROM 22 further also contains
an area 40 storing a procedure for carrying out "strip video
pre-generation" (SVPG); an area 42 with a procedure for carrying out
"adaptive compressed page protection" (ACPP); an area 44 that contains
lossy dither tables which enable, upon decompression, a lossy decompressed
image to more effectively represent the original (notwithstanding a loss
of data), and an area 46 which contains a procedure for performing data
compression using one or more compression procedures found in areas 34, 36
and 38.
During the operation of the procedure which carries out mode m compression,
a plurality of counters 50, 52 and 54 are employed to enable tracking of
certain compression counts. The operation of such counters will be
considered below.
GLOBAL FLOW DIAGRAM
Turning to FIG. 2, a global flow diagram illustrates actions taken by
printer 10 during the course of the generation of a page. Initially, data
is received from a host processor (box 70) and is subjected to
preprocessing to derive raster graphics subimages. The subimages are then
employed to build the page intermediate strips of the image data (box 72).
As above mentioned, this procedure comprises the allocation of graphics
subimages to page strips, each strip composed of instruction buckets, each
of a predetermined size, and possibly containing sub-image instructions of
a predetermined size. Printer 10 also preallocates area 30 of RAM 20 to
hold the raster video bit maps that result from conversion of strips of
page intermediate (generally three). Thus, while printer 10 may divide a
page into 10 or more strips, RAM 20 is only capable of holding raster
video bit maps which result from three strips of page intermediate.
Once each page intermediate strip is completed, printer 10 converts
instructions within each strip into raster video bit map data and stores
the data in RAM area 26 which is subdivided (in this example) into three
raster buffer areas. When all three buffer areas (RAM area 26) are full,
print engine 14 is started and raster video information stored therein is
fed thereto under control of processor 12. While raster video data is
being read into print engine 14, the process of converting page
intermediate into strip buffer video continues, using buffer areas for
which data transfer to print engine 14 has been completed.
In the process of building page intermediate, it may occur that the number
of instructions is too large for a strip (decision box 74). If so, the
raster graphics portion found to be too large is immediately converted to
a video raster data and compressed using a lossless compression technique,
e.g. mode-m (box 76). Further details regarding this procedure will be
described below with respect to FIG. 3.
During the construction of page intermediate, track is kept of the amount
of strip raster buffer area 26 that is available. If it is determined
(decision box 78) that remaining strip raster buffer area is either "low"
or "out", the procedure branches to determine whether graphics image data
referred to by the page intermediate instructions can be data compressed
to free-up additional memory. Thus, the procedure moves to choose a
compression technique (box 80). Initially, mode-m lossless compression is
tried (box 82) and if it causes removal of the memory out or low
condition, the procedure exits and continues building page intermediate
(box 72). In general, if the memory out or low condition remains, a
lossless LZW compression procedure is employed (box 84) and the memory
out/low test is repeated. Here again, if the memory out/low indication
remains, a lossy compression procedure (box 86) is tried and, again, the
results are tested to determine if the memory out or low condition has
been removed. If the memory out or low condition continues, the page
cannot be printed. However, in most cases, the lossy compression technique
will remove a memory out or low condition, as it usually achieves a 4:1
data compression.
Once page intermediate strip processing is complete (decision box 90), the
page intermediate data is parsed to estimate the time it will take to
render it into video raster bit map data. If the estimated time is longer
than print engine 14 allows, adaptive compressed page protection (ACPP) is
implemented and a "page too complex" indication is issued (decision box
92). Under such a condition, strips of the page intermediate exhibiting a
high level of complexity are processed in order down the page and are
converted to raster and placed in a temporary buffer. Then, compression
techniques are employed on the raster data strips in an attempt to remove
the "page too complex" indication and to fit the converted strips in
available RAM.
Once each of the strips has been converted and compressed (if possible), an
attempt is made to find storage for them in RAM 20. Since the complexity
of compressed objects is generally much lower than the maximum complexity
allowed by print engine 14, a page prints without a print overrun.
STRIP VIDEO PRE-GENERATION
Turning now to FIG. 3, procedures employed during strip video
pre-generation (as shown in boxes 74, 76 in FIG. 2) will be described.
When a page is opened, a page intermediate size threshold for each strip
is set (box 100). The threshold is set in units of buckets, with a bucket
being the smallest allocated unit of page intermediate storage. In this
example, it is assumed that a bucket is approximately 256 bytes long.
Buckets are linked together, if needed, to store a strip's page
intermediate data. The bucket threshold is calculated by dividing the
amount of available printer memory by the product of the number of strips
on a page times the number of bytes per bucket. Assuming an available
memory of approximately 800,000 bytes, the threshold is set at
approximately 125 buckets and each strip's threshold is initialized to
that value.
Next, page intermediate processing commences (box 72) to create page
intermediate data structures. If at any time during the process of
converting raster graphics to page intermediate, it is determined that the
number of instruction buckets for a strip exceeds the previously set
threshold, that strip may need to be immediately converted to raster and
compressed to conserve printer memory. Thus, decision box 102 provides a
yes output when the threshold is exceeded. Then, it is determined if the
remaining RAM for strip raster bit maps is less than the space required
for two strips (decision box 104). If the answer is no, page intermediate
construction continues. If however the answer is yes (insufficient RAM
left to hold two strips), the strip that exceeds the threshold has its
page intermediate data immediately converted to raster video data (box
106).
The condition indicated in decision box 104 avoids converting strips to
raster video data when there is sufficient memory to store more page
intermediate without the conversion. Thus, pages which do not need video
pregeneration do not have to pay a time penalty just because a few strips
upon the page are very large (and the rest are small).
Once the "too large" strip is converted to raster video, an attempt is made
to compress the strip's data using mode-m compression (box 108), to be
described below. If the strip video data compressed as a result of the
mode-m compression action (decision box 110) the compressed strip is used
(box 112). If the strip did not compress, the uncompressed strip is
employed (box 114). It should be noted that under certain circumstances,
compression techniques result in expansion of strip data. In such a
circumstance, the uncompressed strip data is employed in lieu of the
expanded strip data.
Next, an attempt is made to allocate space for the strip raster video in
RAM 20 (box 116). If contiguous memory space is available (decision box
118), the strip is stored in the memory space (box 120); whereas if a
contiguous space in memory is not found and sufficient fragmented memory
space is available (decision box 119), the strip is stored in linked
memory fragments within RAM 20 (box 122). If there is either insufficient
contiguous or fragmented memory space, a "memory out" occurs and printing
of the page continues (box 121) so that whatever can be printed is
printed.
Once a strip is stored in memory, a new bucket threshold for the strip is
established, based upon current memory conditions (box 124). This
threshold is calculated similarly to the initial threshold, with the
exception that the number of buckets that the just converted strip
consumed is subtracted. Thus, the new threshold is equal to the old
threshold value (adjusted for changes in amount of available RAM) less the
size of the converted video raster strip, divided by the number of bytes
per bucket. This adjustment of the threshold causes it to become smaller
as strips are converted and less memory becomes available. Once the new
threshold is set (box 124), the building of page intermediate continues
(box 72).
The procedure shown in FIG. 3 occurs in advance of any indication of either
a memory out or memory low. It | | |
