NASA SBIR Phase'I Report 

p Y2 

Title: Parallel Image Compression 

Technical Topic Category: 07.04 - Signal and Information Processing 

Amount of Funding: $49,932. 

Name and Address of Proposing Firm: 

RSIC Associates 

350 Lake St. 

Belmont, MA 02178 

Principal Investigator: John H. Reif. 

Keywords: Data compression, image compression, vector quantization, 

adaptive algorithm, parallel algorithm, massively parallel processor (MPP). 

Table of Contents 

Section 1: Summary 

Section 2: Technical Foundations 

Section 3: Results 

Section 4: Simulation Code 

Section 5: MPP Code 

(BASA-CE-160758) PARALLEL IFAGE CCEPBESSION N8 8-2C 8 37 

(6SIC ASEGCiateE) 42 CSCL C9B 

Unclas 

G3/6 1 0093249 
-2- 

1. Summary 

This document reports on the research performed for SBIR Phase I funding 

of RSIC associates. This research has now been completed. We have developed a 

parallel compression algorithm for the 16,384 processor MPP machine developed 

by NASA. This algorithm has the following properties: 

0 It is on-line; that is only a single pass over the data is made. 

0 It is dynamic; no prior knowledge of the data is needed. A dictionary of 

“patterns” on which compression is based is dynamically constructed. 

0 The tradeoff between fidelity and the amount of compression achieved can 

be adjusted via a single integer parameter. As a special case, pure lossless 

compression may be specified. 

0 Because our algorithm is on-line, dynamic, and the degree of lossiness can 

be adjusted, it provides the basis for a single universal device that can be 

used for a variety of data types, including: 

0 digital images 

0 video 

0 speech 

0 text 

0 database information 

The above data types are common to many NASA missions that involve 

data acquisition and storage. 

0 It can be implemented with currrent technology to operate in real-time, 

even for extremely high-bandwidth applications; e.g., 30 frames per second 

of 512 by 512 pixels per frame video. 

0 The cost of the hardware goes down as the bandwidth of the application 

goes down. 

0 The amount of compression that is achieved for a given degree of fidelity 

on a given type of data compares favorably with existing, more specialized 

algorithms. 
-3- 

2. Technical Foundations 

The serial version of our algorithm can be viewed as a combination of online dynamic lossless text compression techniques (which employ simple learning 

strategies) and vector quantization. We start by describing these concepts. Later 

we will discuss how we combine them to form a new strategy for performing 

dynamic on-line lossy compression. Finally we will discuss our this algorithm has 

been implemented in a massively parallel fashion on the MPP. 

Lorrlesr Text Compression 

Algorithms for lossless text compression have been known since the 1950’s. During the 

past decade, algorithms that dynamically “learn” about the data and replace frequently occurring 

fragments of data by tokens have been widely studied. We shall now briefly discuss a general 

framework for dynamic lossless compression that is developed in the book by J. Storer. The basic 

idea is to maintain a dictionary of commonly occurring data fragments; this dictionary is constantly being modified by some learning heuristic. 

We use C to denote the underlying alphabet from which “characters” of data are drawn. 

For example, with text, the characters might be 7-bit ASCII codes stored one per byte whereas 

with digitally stored speech the characters might be 12-bit samples stored in two’s complement 

form. Algorithm 1 is an encoding algorithm, which reads a stream of characters over C and 

writes a stream of bits, and Algorithm 2 is a decoding algorithm, which receives a stream of bits 

and outputs a stream of characters over E. Note that for both the presentation of these algorithms and for the discussion to follow we shall use the notation ID I to denote the current 

number of entries in the local dictionary D and <D> to denote the maximum number of entries 

that D can hold. We shall refer to indices into a dictionary of strings as pointera. 

Like many dynamic compression algorithms, a key idea behind the methods we shall discuss is to have the encoder and decoder to work in lock-step to maintain identical local dictionaries (which may be dynamically changing). The encoder repeatedly finds a match between 

the incoming characters of the input stream and the dictionary, deletes these characters from the 

input stream, transmits the index of the corresponding dictionary entry, and updates the dictionary with some method that depends on the current contents of the dictionary and the match that 

was just found; if there is not enough room left in the dictionary, some deletion heuristic must be 

performed. Similarly, the decoder repeatedly receives an index, retrieves the corresponding dictionary entry as the “current match”, and then performs the same algorithm as the encoder to 

update its dictionary. 

It can be seen that left out of Algorithms 1 and 2 is the specification of the following: 

The initialication ret, INIT: A set of strings that are to be used to initialize 

the local dictionary; it must be that C is a subset of INZT and I INIT I 5 <D>. 

The match heurirtic, MH: A function that removes from the input stream a 

string t that is in D. 
-4- 

Algorithm I, Encoding Algorithm: 

(1) Initialize the local dictionary D with the set ZNlT. 

(2) repeat forever 

(a) Get the current match: 

t := MH(inputstream) 

Advance the input stream forward by I t I characters. 

Transmit pog, I D 11 bits corresponding to t . 

(b) Update the local dictionary D: 

X := UH(D) 

while X#{} and (D is not full or DH(D)#c) do begin 

Delete an element z from X. 

If z is not in D then begin 

if D is full then Delete DH(D) from D. 

Add z to D. 

end 

end 

Algorithm 2, Decoding Algorithm: 

(1) Initialize the local dictionary D by performing Step 1 of the encoding algorithm. 

(2) repeat forever 

(a) Get the current match: 

Receive pog, I D 11 bits. 

Obtain the current match t by a dictionary lookup. 

Output the characters oft. 

(b) Update the local dictionary D by performing Step 2b of the encoding algorithm. 
-5- 

The update heuristic, UH A function that takes the local dictionary D and 

returns a set of strings that should be added to the dictionary if space can be found for 

them. 

The deletion heuristic, DH: A function that takes the local dictionary D and 

either returns c (in which case there is no string that can be deleted from D) or a string of 

D that is not a member of INIT (which may legally be deleted from D). 

The choice of the above heuristics will be discussed shortly. However, for the moment let 

us consider the basic structure of Algorithms 1 and 2 that is independent of these heuristics. The 

reader should convince himself or herself that these algorithms are inverses of each other; that is, 

the input to the encoding algorithm is always the same as the output from the decoding algorithm. The key observations are: 

0 D is initialized to contain at least the characters of C (since C must be a subset of INIT) 

and these characters can never be deleted. 

0 Since D always contains C, h4H is always well defined. Hence, any input string to the 

encoding algorithm can always be encoded (at worst at a character at a time). 

0 Encoding is unique (since MH must return a unique value). 

0 The local dictionaries of the encoder and decoder must always remain identical (since Step 

2b of the decoding algorithm is identical to Step 2b of the encoding algorithm). 

The condition that INIT must include C implies that Step 1 of the encoding and decoding algorithms guarantees that each character of E is initially present in D. Furthermore, since 

DH is never allowed to return a character of E, the characters of C must always be present in D. 

This condition guarantees that Step 2a must always find a match that is at least one character 

long. Because the existence of the current match has been guaranteed by the existence of C in 

the dictionary, we say that Algorithms 1 and 2 have dictionary guaranteed progreaa. Another 

way to guarantee progress is to relax the conditions that C be a subset of INlT and DH cannot 

return a character of E, and modify Step 2a of the encoding algorithm to transmit 

Dog, I D I l+pogz I C 11 bits that represent the pointer to t and the character of C that appears 

immediately after t in the input stream (and then advance the input stream forward by I t I +I 

characters). Step 2a of the decoding algorithm is similarly modified to receive a pointer and a 

character of E. Methods that guarantee progress in this fashion have pointer guaranteed progress. A compromise betw'een dictionary guaranteed progress and pointer guaranteed progress is 

on-the-fly dictionary guaranteed progreaa. Here, we again relax the conditions that C be a subset 

of INIT and DH cannot return a character of C. Instead, we reserve one pointer value as the 

nil-pointer. Any rule for what value value is assigned to the nil-pointer suffices so long as it is 

consistent between the encoder and decoder; for convenience, we always assume that the nilpointer is I D I +1 (one more than the largest current legal pointer value); that is the nil-pointer 

starts off as 0 and increases by one each time ID I increases by one until the nil-pointer value 

reaches <D>. Hence, one entry of D is in some sense "wasted" since D can never have more 

than <D>-l entries; in practice, assuming that D is reasonably large (e.g., more than 100 entries), this waste is insignificant. Given that a null pointer is available, each time no match can 

be found, progress can be guaranteed by transmitting the null pointer (to signal to the decoder 

that a new character of C is to follow) followed by the next character of the input stream. In addition, the next character of the input stream can be added to the dictionary. On-the-fly dictionary guaranteed progress derives its name from the fact that characters of C are added to D (to 
-6- 

guarantee progress) only when they are encountered. Hence, it represents a compromise between 

dictionary and pointer guaranteed progress because unlike dictionary guaranteed progress it does 

not use space in D for characters of C that are not being used but unlike pointer guaranteed progress it does not add overhead to every pointer; overhead is only incurred the first time a character is used (or the first time the character has been used since it has last been deleted from D). 

In the limit as D becomes large, it makes little difference which of the above three 

methods are used to guarantee progress. However, for practical implementations, where D is 

bounded in size, the overhead of including I C I bits with each pointer used by pointer guaranteed 

progress can be substantial. Since for most typical applications, <D> is relatively large compared to I C I (e.g., <D > is larger that 4096 and I C I is smaller that 256), we restrict our attention for the moment to dictionary guaranteed progress, as is used by Algorithms 1 and 2. 

However, in practice, on-the-fly dictionary progress typically performs equally well; that is, the 

overhead incurred is typically insignificant so long as the size of the text being compressed is reasonably large (e.g., larger than <D>). We have not chosen to use it here because the standard 

form of dictionary guaranteed progress is “cleaner” for presentation purposes. However, and we 

will employ on-the-fly dictionary guaranteed progress when we generalize Algorithms 1 and 2 to 

lossy compression. 

If MH is taken to be the function that returns the longest prefix of the input stream that 

is in the dictionary, then Step 2a of the encoding algorithm amounts to a greedy algorithm for obtaining the current match. We shall henceforth refer to this heuristic as the greedy match heuristic. In terms of worst-case performance, significantly better compression can be achieved by incorporating some amount of look-ahead. However, little advantage is gained in practice and we 

do not address this issue further. We shall assume the greedy heuristic from this point on. 

The key idea behind dynamic dictionary methods, is to use an update heuristic that adds 

the previous match concatenated with some set of strings based on the current matcht. That is, if 

pm denotes the previous match, cm the current match, and INC is an “incrementing” function 

that maps a single string to a set of strings, then for some choice of INC: 

LIH(D) = {pm concatenated with all strings of INC(cm)} 

The following are three effective choices for INC. 

FC: The first character heuristic: INC(cm) is the first character of cm. 

ID: The identity heuristic: INC(cm) is cm. 

Ap: The all-prefizes heuristic: INC(cm) is the set of all (non-empty) prefixes of cm 

(including cm). 

Example I: Suppose that the previous match was “THE,” and the current match is 

“CAT”, where we use the underscore to denote a space. Then VD(D) h a s t h e following values for 

the update heuristics discussed above: 

FC: {“THE-C”} 

.............................. 

t Since we have defined the update function UD of Algorithms 1 and 2 as a function of D, to simplify notation, we shall always asaume that it is possible to determine from D both the previous and current match. 
-7- 

ID: {”THE-CAT”} 

AP: {”THE-C”, ”THE-CA”, ”THE-CAT”} 

In general, the FC and ID heuristics always produce exactly one string whereas the AP heuristic 

always produces a number of strings equal to the length of the current match. In fact, included in 

the set produced by the AP heuristic are the strings produced by the FC and ID heuristics. 

Hence, it is illustrative to consider a longer example with respect to the AP heuristic. Consider 

the phrase 

” THE,CAT,AT,THE,CAR,ATE,THE,RAT” 

where the underscore character is used to denote a space. Assuming that we start with the dictionary containing only the single characters, the following table shows what strings are added to 

the dictionary as this phrase is processed: 

MATCH 

T 

H 

E 

C 

A 

T 

AT 

, 

- 

?H 

E, 

CA 

R 

AT 

E, 

R 

AT 

STRINGS ADDED 

0 

The following are two common deletion heuristics. 

FREEZE: The Jreeze heuristic: DH(D) is the empty string, that is, once the dictionary is 

full, it remains the same from that point on. 

LRU: The least recently used heuristic: DH(D) is that string in D that has been 

matched least recently. 

A third deletion heuristic that can be viewed as a variation of the LRU heuristic is the following: 

LFU: The leaat jrequatly used heuristic: DH(D) is that string in D which has been 

matched leaat frequently. In order to prevent this heuristic from degenerating 

into the FREEZE heuristic, some sort of weighting has to be performed when 
-8- 

entering a new match into the dictionary. For example, the new match can be 

assigned a frequency equal to the average frequency of the entries currently in the 

dictionary. When a match is found that is already in the dictionary, it may be 

necessary to scale down all frequency counts of dictionary entries (making fractional counts 0) if any given count reaches the maximum allowable value for an 

integer. 

In practice, the LFU deletion heuristic performs comparably to the LRU heuristic but is less convenient to implement. We shall not consider this deletion heuristic any further. 

A fourth deletion heuristic that can be viewed as as lying somewhere between the FREEZE and 

LRU deletion heuristics is the following. 

SWAP: The awap heuristic: When the primary dictionary first becomes full, an autiliary 

dictionary is started, but compression is continued based on the primary dictionary. From this point on, each time the auxiliary dictionary becomes full, the 

roles of the primary and auxiliary dictionaries are reversed, and the auxiliary dictionary is reset to be empty. Although this heuristic does not fit directly into AIgorithms 1 and 2, they can be modified to accommodate it. 

With the exception of rapidly changing data, the SWAP deletion heuristic performs comparably to 

the LRU heuristic. However, this deletion heuristic will provide a useful alternative to the LRU 

deletion heuristic for our parallel implementation on the MPP to be discussed later. 

A host of data compression methods can be derived from different combinations of the 

heuristics above. We now list four widely used combinations. Except as noted, the computational 

resources required by these four heuristics are are equivalent in the asymptotic sense, but in practical implementations can differ by significant constant factors for both time and space requirements. The trade-offs between compression performance and these constant factors will be an important concern. 

FC-FREEZE: This heuristic is the most simple to implement and, except far the start up phase 

when the dictionary is not full, runs faster because no time is spent on updating. 

FC-LRU: This heuristic requires more computational resources than FC-FREEZE, but typically yields significantly better compression. It is also more stable than FCFREEZE, in a sense to be discussed later. 

AP-LRU: As we shall see, this heuristic requires approximately the same computational 

resources as FC-LRU but typically yields better compression on text files. 

ID-LRU: This heuristic typically yields better compression than the FC-LRU heuristic and 

sometimes yields better compression than the AP-LRU heuristic. Although the 

ID-LRU heuristic may appear at first glance to be simplier or more basic than 

the AP-LRU heuristic, the ID-LRU heuristic requires significantly greater computational resources than the AP-LRU heuristic for an efficient serial implementation. However, the situation for parallel implementations is much different; we 

shall employ the ID heuristic for our MPP implementation. 
-9- 

Vector Quantization 

Vector quantization traditionally refers to any method that partitions the input into 

blocks of blockuize characters and maps each block to one of the elements in a table of tableuize 

entries, where each entry is a blockuize tuple of characters from E. Compression is achieved by 

outputting only the indices into the table. Decompression is just table lookup. A nice feature of 

this simple approach is that we know in advance that the compression ratio achieved (bits out divided by bits in) will be exactly (to simplify notation, assume that I C I and tablesize are powers 

of two): 

(log, I C I Wockuize) / log,(tableuize) 

We do not, however, have any guarantees about the quality of the “quantized” image. The 

methods used to get the best quality possible are what motivate the term “vector” quantization. 

We can view the set of all possible blocksize-tuples, blocksize21, of characters from C as 

forming a blocksize-dimensional vector space. If V is a vector of blocksize characters from E, 

then we let VI through Ifw,,, denote the components of V. A metric for the distance between 

two vectors V and W, I(V,W), can be defined. For the purposes of defining such a metric, 

depending on the particular application, we henceforth assume one (but not both) of the following: 

nn characters: To each of the characters of C is associated a unique non-negative integer in the range 0 to I C I -1. 

tc characters: To each of the characters of C is associated a unique integer in the range 

- I C I /2 to ( I C I /2)-1. That is, if I C I is a power of 2, then the set 

of integers corresponding to the characters of C is the set of integers that 

can be represented in two’s complement notation using log, I C I bits. 

In most applications, DSAD is stored in one of the above two forms. For example, with digitally 

stored black and white images or video, &bit nn characters are typically used whereas with digitally sampled speech, 12 or 16-bit tc characters are typically used. Perhaps-the three most commonly used metrics are: 

bb&izx 

L1: I(V,W) = Ivi-WiI 

b=J 

Moekdzx 

L2: I(V,W) = (Vi--Wif 

la 

w&A 

LINFINITY: I(V,W) = MAX I V,-Wi I 

isl 
- 10- 

A natural way to visualize the above three metrics is to think of them in the context of 3- 

dimensional Euclidean space (blockaize=3). The L1 metric corresponds to traveling from V to W 

by only moving along the coordinate axes. The L2 metric corresponds to traveling from V to W 

in the shortest distance possible (a straight line segment). The L-INFINITY metric simply 

measures the component on which the two vectors differ the most; it derives its name from the 

following observation. If for any integer K>O we define the Lk metric as 

d(V,W) = 

i=l 

then L1 and L2 correspond to k=l and k=2, and: 

L-ZNFINITy(V,W) = lim Lk(V,W) 

&- 

Although the name L-INFINITY arises naturally as indicated above, we shall henceforth refer to 

it simply as the MAX metric; this name is motivated more directly by the way the metric is actually computed and is also shorter to write. 

Example 2: Suppose that the input is a raster scan of a black and white image where 

each pixel is stored as a byte. A simple way to achieve 2-to-1 compression is to simply discard 

the low-order 4 bits of each pixel (Le., replace them by 0). This is an example of vector quantization where I C I =256, block~ize=l, and tableaize=l6. By performing this quantization using 

any of the metrics L1, L2, or MAX (which are equivalent when blockaize=l), we have replaced 

256 distinct intensity levels by 16 levels that are spread uniformly. This loss in precision has been 

traded for the 2-to-1 compression. 0 

Preprocemsing for the Lomalema Algorithm 

- 

As illustrated by Example 2, a special case of vector quantization is scalar quantization, 

where blocksize= 1. Scalar quantization provides a very simple method for on-line dynamic lossy 

compression: 

Quantize the incoming characters of the input atream before pausing them to an 

on-line dynamic loaaleaa compreaaion algorithm. 

This approach can be viewed as preprocessing the input for the lossless compressor to make characters that are “similar” be identical (so that the lossless compressor can more easily find patterns). This preprocessing step also has the desirable side-effect that compression ratio of the entire algorithm is the product of the ratio obtained by the scalar quantization and the ratio obtained by the lossless algorithm. In practice, this product has a “snowballing” effect; that is, the 

more compression achieved by the scalar quantization, the more that is achieved by the lossless 

compression. 

Given that we are viewing scalar quantization as a preprocessing step to lossless compression, if Q is the scalar quantization function, then from the point of view of the lossless compressor, the input alphabet is just the set of distinct values of Q(a) where a is a character of E. 

Hence, from this point on, it will be convenient to view scalar quantization as the INZT heuristic. 
- 11 - 

That is, a function that places a set of characters (INIT) in the dictionary with the understanding 

that if a character of C that is not in INIT arrives on the input stream, then it is mapped to the 

closest (in the sense of whatever metric is being used) character in INIT. Some common scalar 

quantization methods (dictionary initialization heuristics) are: 

ALL: Place all possible characters in the dictionary. No compression is achieved, no information is lost. If we are compressing data by first scalar quantizing and then 

performing lossless compression, then instructing the scalar quantizer to use ALL 

quantization forces the system to pure lossless compression. 

UNIFORM: Example 2 is an example of UNIFORM scalar quantization. In the literature, 

any technique that spreads values approximately evenly is considered to be uniform quantization. For our purposes, given an integer parameter spacing >O, for 

nn characters UNIFORM(d) places into the dictionary the values 

O,apacing,2 *spacing ,..., I C I -1 

and for tc characters the values: 

O,spacing,-spacing,2*spacing,-2*spacing, - * , I C I /%I,- I C I /2. 

LOG For a given integer parameter eztrabita, with log scalar quantization the idea is to 

save only the position of the leading non-zero bit of the character along with the next 

eztrabita bits that follow it. 

It should be noted that if the scalar quantization is sufficiently crude, dithering may be an 

effective pre and post-processing step to help smooth artificial discrete boundaries that can arise. 

Our Generdication of the Lorrlesr Algorithm - 

Scalar quantization followed by lossless compression is a simple approach that has a lossy 

component (provided by the scalar quantization) that is completely separate from a pattern 

matching component (provided by the lossless compression algorithm). We now consider a potenThe idea is to use Algorithms 1 and 2 with just two changes. 

tially more powerful approach that combines these two components. t 

The first change is that the definition of the match heuristic is generalized to: 

The match heurirtic, MH: A function that removes from the input stream a 

string t that is acceptably close (according to a specified metric) to a string in D. 

The algorithm must be supplied a vector diatance metric VM that takes a single string 8 as an argument and returns a non-negative integer equal to the “distance” between 8 and the first Is I 

incoming characters of the input stream. This function must satisfy two constraints: 

0 VM(s)=O if and only if the first 18 I incoming characters of the input stream 

-------L---------------------- 

t In practice this approach may be more powerful. In theory, a result of Ziv shows that this my not be true. 
- 12- 

are exactly the characters of a. 

0 VM(a)=oo if there are less than I a I characters left in the input stream. 

Given that such a metric is supplied to the algorithm, “acceptably close” is defined by a single integer parameter Epsilon that is also supplied to the algorithm. That is, all dictionary entries a 

such that VM(a)<Epailon are acceptably close. Because of the conditions placed on VM, the 

value Epailon=O forces pure lossless compression. 

The second change that we make to Algorithms 1 and 2 is to employ on-the-fly dictionary 

guaranteed progress. The reason for this change is that we no longer wish to force INIT to contain all of C since in many practical applications (e.g. 16-bit digitally sampled speech), I Cl is 

very large (possibly larger than I D I ). The reader should note that even if I INIT 1 < I C I , the 

on-the-fly mechanism will never be used if INIT contains enough characters so that every character of C is acceptable close to some character in INIT. 

Given the two changes discussed above, Algorithms 1 and 2 are a general purpose framework for performing on-line dynamic lossy compression, where the tradeoff between the degree of 

lossiness and the amount of compression can be adjusted via a single integer parameter Epaifon. 

Parallel Implementation on the MPP 

The basic ideas behind our translation of the techniques described above to the massively 

parallel environment of the MPP, which were developed during SBlR Phase 1, are the following: 

0 The MPP is a 128 by 128 two-dimensional array of 16,384 processors. However, we view 

it as 128 independent parallel compressors that operate in a pipeline fashion, one compressor operating on each row of the MPP. One of these compressors can be used for serial 

sources such as speech or text. The entire machine is needed for real-time compression of 

successive digital images. Each 512 by 512 digital black and white ‘mage is divided into 

128 horizontal -bands”, each 4 pixels high. Each band is fed into a row of the MPP in a 

pipelined fashion. In this situation, the i/o rate is extremely high; that is, 128 time the 

i/o rate of an individual processor. 

0 The new MPP chip designed by J. Reif at MCNC and the modified version of it that we 

propose to design contains a 8 by 16 sub-array of MPP processors. However, for the purposes of data compression, we will use it as a l by 128 array of processors that forms the 

parallel systolic pipeline that forms one of our dynamic on-line data compressors. 

0 The ID growing heuristic is used. This minimizes on-chip memory that is needed (which 

is critical with the MPP design) because dictionary entries can be represented by simple 

pointer pairs. 

0 Since our compressor will use a MPP chip to form a systolic pipelined associative 

memory, matches will be constructed in a bottom-up fashion instead of the top-down 

fashion that is used in the serial case. That is, instead of discovering a longest possible 

match all at one time (as is the case with the greedy match heuristic employed in the serial algorithm), pairs of pointers are successively combined as they flow down the pipe. 

Simulations performed during SBIR Phase I show that the bottom-up construction of 
- 13- 

matches that results from the parallel parsing does not compromise compression performance in practice, and in some cases, even improves it. Note that this is not true if a dictionary computed elsewhere is simply loaded into the processor array. It is key that the 

dictionary is dynamically learned in the array. 

0 The SWAP deletion strategy is used. Simulations show that this is equivalent in performance to the LRU strategy. However, from a hardware point of view, it is much simplier 

to implement, requiring only some simple re-routing of the i/o paths. 

0 To improve the running time, a “recycling strategy” is used where partially compressed 

data is fed through the array at a faster rate. 
- 14- 

3. Results 

For the six month duration of the SBIR Phase I funding (March 1987 

through August 1987), the work to develop our algorithm proceeded as follows: 

0 Basic research was performed on combining the techniques of vector quantization with lossless learning strategies. The result is a novel on-line 

dynamic compression algorithm where the tradeoff between the degree of 

lossiness and the amount of compression can be tuned with a single integer 

parameter. 

0 Studies were performed to show the ID learning heuristic in conjunction 

with the SWAP deletion heuristic to be most appropriate for our implementation. 

0 Studies on the effect of parallel parsing on the pure version of our algorithm were performed (see the notes preceeding the simulation code). A 

buffering / parsing strategy for an individual processor was developed. 

0 Modifications and simplifications of our algorithm were made to allow 

more direct implementation on the MPP architecture. 

0 The recycling strategy was developed to enhance through-put. 

0 Code for the VAX 11/780 was written to perform simulations to determine 

the amount of compression that could be expected with the modified version of our algorithm. 

- 

0 Code for the MPP was written and runs were made on the MPP at Goddard Space Flight center. 

RSIC, Inc. would like to take this opportunity to thank members of the 

NASA Goddard Space Flight center for their help and support during this project. 

In particular, J. Devany and D. Wildenhain for the considerable time they spent 

helping us program and use the WP, and J. Fischer, M. Halen, H. K. Ramapriyan, and J. Tilton for numerous technical consulations. 

As indicated in the project summary,. the algorithm has the following properties: 

0 It is on-line; that is only a single pass over the data is made. 

0 It is dynamic; no prior knowledge of the data is needed. A dictionary of 

“patterns” on which compression is based is dynamically constructed. 
- 15- 

0 The tradeoff between fidelity and the amount of compression achieved can 

be adjusted via a single integer parameter. As a special case, pure lossless 

compression may be specified. 

0 Because our algorithm is on-line, dynamic, and the degree of lossiness can 

be adjusted, it provides the basis for a single universal device that can be 

used for a variety of data types, including: 

0 digital images 

0 video 

0 speech 

0 text 

0 database information 

0 It can be implemented with currrent technology to operate in real-time, 

even for extremely high-bandwidth applications; e.g., 30 frames per second 

of 512 by 512 pixels per frame video. 

0 The cost of the hardware goes down as the bandwidth of the application 

goes down. 

In addition to having the desirable performance properties listed above, the 

amount of compression that is achieved for a given degree of fidelity on a given 

type of data compares favorably with existing, more specialized dgorithms. Typical amounts of compression achieved can be summarized as follows: 

text: With pure lossless compression, state-of-the-art performance 

was obtained; e.g., 3-to-1 for English text, 5-to-1 for programming language source code, and as much as 10-to-1 for very 

compressible text such as spread-sheet data. Our test data 

consisted primarily of technical papers that were stored electronically on the VAX 11/780 system we were using. 

speech: Speech sampled 8,000 times per second, 12 bits per sample 

(96 kilo-bit speech is an industry standard), could be 

compressed by more than 12-to-1 while retaining good quality, and by more than 30-to-1 and still be understandable. 

Our test data was obtained by having students read passages 

from books into a microphone connected to a digital-toanalog converter. Quality was accessed by playing back the 
- 16- 

decompressed data to independent listeners. 

video: Black and white video stored 512 by 512 pixels per frame, 8 

bits per pixel could be compressed by factors of 30-to-1 to 

50-to-1 while retaining good quality. Our test data was some 

black and white video of a person speaking against a relatively static background. 

Section 4 is the VAX simulation Pascal code. Note that Section 4 begins 

with some documation and a brief discussion of some technical details pertaining 

to the processor buffering strategy. Section 5 is the corresponding parallel Pascal 

code for the MPP. 

The result of this work is a very flexible algorithm that is well-suited for 

real-time compression for a variety of on-line data. We have applied for SBIR 

Phase II funding to build a chip set (based on the new MPP chip being developed 

at MCNC) for our algorithm. 
, 

- 17- 

4. Simulation Code 

Basic Algorithm 

rotusirn implements a data compression algorithm designed to work on a 

single row of the MPP, which can be viewed as an independent SIMD machine 

consisting of a linear arrangement of processors in which each processor can communicate to its neighbors on either side. The algorithm itself is an adaption of 

the ID strategy (discussed in the technical background section); each processor 

manages its own input buffer and its own dictionary of previously encountered token pairs. 

The main loop of the algorithm makes each processor read from its left 

neighbor enough tokens to fill its cwn input buffer. Each processor then looks up 

the contents of that buffer in its dictionary; should a match be found between the 

buffer and one of the entries in the dictionary, the output code associated with 

that entry replaces the two input tokens in the input buffer. Otherwise, the “oldest” entry in the input buffer is output to the next processor in the line, and the 

other entries in the buffer are shifted in. 

Each processor updates its local dictionary by adding to it the concatenation of the current oldest token to the last token output (the ID heuristic). Only 

in those iterations where no match was found between the processor’s input buffer 

and its dictionary does each processor add a new entry to its dictionary as 

described. We further limited the learning process so that only the leftmost processor with a non-full dictionary would learn new token pairs at agy one time. 

Implementation Details 

The preceding description, although brief, suggests at least two directions 

in which an implementation of the algorithm described could affect its performance: in our implementation we chose to examine the effects of both the size of 

the input buffer each processor uses and the method used to find what matches 
- 18- 

may exist between the buffer and entries in the dictionary. 

Buffer Size 

Since the algorithm used to add new entries to local dictionaries worked by 

concatenating the last two matches found at each processor, our initial implementation of rowsirn used a two-element input buffer at each node plus a one-token 

output buffer. The matching was done then straighforwardly between the buffer 

and each one of the entries in the dictionary; when no such match was found, a 

new entry was added to the corresponding local dictionary by concatenating the 

last token output (in the output buffer) and the “older” of the two entries in the 

input buffer. 

This first approach seemed to work as expected until we tried to compress 

a large file of blanks. We expected a very large rate of compression on this file, 

and yet we only obtained a 25 percent reduction in the size of the input file. The 

problem was due to the fact that the first processor in the array was only able to 

learn 4 different token pairs, and since its own dictionary never filled, no other 

processor could learn new token pairs to further compress the input sequence. 

This suggested we improve out implementation by increasing the size of each 

processor’s input buffer to 3, 4 or even longer buffers. This created a second 

question, namely how to search for matches between entries in the dictionary, 

each one of which 

than 2. 

Buffer Matching 

would only have two tokens, and input buffers of sizes larger 

Strategies 

The matching algorithm for the case in which the input buffer is as long as 

each entry in the dictionary is straighforward: it is enough to do a one-to-one 

matching between the input buffer and each dictionary entry. When the length 

of the input buffer is increased, however, two decisions must be made when 

designing the matching algorithm: (1) should the algorithm try to find only the 

first possible match between the input buffer and the dictionary, or would be it 

more efficient to replace each match when found and repeat the matching process 

until no more matches are found; and (2) should the algorithm test the input 

buffer against the dictionary entries starting with the most recent pair and then 

work its way towards the previous entries until a match is found, or should it 

start with the earliest pair in the buffer and work its way back. 
- 19 - 

towsim was implemented so that we could compare the results obtained 

from all combinations of both alternatives: the user may specify either left-toright (most recent to least) or right-to-left matching, and he may also specify either full matching (in which case after a match is found the two tokens are replaced by the corresponding code and the matching process is restarted on the 

new, shorter buffer) or first matching (in which case the matching process continues only until the first possible match is found and then replaces both tokens with 

the correct code). 

We discovered, when running experiments trying all possible combinations, 

that in pathological cases (such as a file consisting of lOOk blanks) the best results 

were obtained when using the full matching strategy and a buffer length of 4. On 

most files however, the performance difference among the different strategies was 

not significant enough to justify the extra effort required to implement any of 

these strategies instead of our original straight comparison between the input 

buffer of size 2 and the entries in the dictionary. 

The Simulation Code 

{ program: rowsim} 

{ RSIC, Inc.} 

{ date: July, 1987 } 

{ description:} 

{ This program provides a serial implementation of a data compression} 

{ algorithm suitable for the MPP computer. It satisfies the same per} 

{ processor constraints, in terms of processor memory, that processors} 

{ on the MF’P have to fulfill. Furthermore, the algorithms used were} 

{ chosen to make the transition to an implementation on the MPP machine) 

{ as straghtforward as possible.} 

{ usage:} 

{ 95 rowsim [-r] [-f] [-D dictionary] [-G break] [-R reserved I} 

{ 

{ where:} 

{ -ruse right-to-left buffer matching} 

{ (default: left-bright)} 

{ -fuse fast matching algorithm} 

{ 

{ 

{ 

{ 

{ 

[-S skip] [-B buffer] [-E entries]} 

(default: full buffer matching is used)} 

-D dictionaryname of dictionary file (default: ’dictionary’)} 

once the whole input file has been compressed,} 

the final dictionary is written to this file} 

-G breakcodes will be split into two groups: less than} 
- 20 - 

{ 

{ 

{ to the same group.} 

{ 

{ valid match).} 

{ 

{ 

{ 

{ 

{ 

{ 

{ 

{ (default: 32 entries/processor)} 

'break' and greater or equal. Matches will} 

only be valid between pairs of codes belonging} 

(default: only one group, any two codes are a} 

-R reservedthe first 'reserved' codes will be considered} 

to be raw input codes (default: 256)) 

-S skipignore first 'skip' characters of file - they} 

are copied without processing (default: 0)) 

-B bufferper processor input buffer will be 'buffer'} 

cells long (default: 3 cells)} 

-E entrieseach processor will hold at most 'entries'} 

{ Dictionary File: Format:} 

{ This program creates the dictionary file (default: 'dictionary') as} 

{ a series of lines, each one of the form:} 

{ <processor> <index> <code> <left> <right> <length>} 

{ where <processor> is an id from 0 to 127, <index> is an offset into} 

{ a dictionary in the range 0 to 31, <code> is the code corresponding} 

{ to this entry, <left> and <right> are the two pointers making up the} 

{ entry, and <length> is the length of the entry (in input tokens).} 

program rowsim( input, output ); 

const SmallestProcessorIndex = 0; { Processors} 

LargestProcessorIndex = 127; 

SmallestDictIndex = O;{ Dictionary } 

LargestDictIndex = 31; 

MaxNumberOfEntries = 32; 

LeftmostBufferIndex = O;{ Buffers} 

RightmostBufferIndex = 7; 

MaxBufferSize - 

SmallestPointer - O;{ Output Tokens} 

Larges tPoin ter = 4095; 

MaxStringSize = 80;{ Strings} 

8; - 

{ Default parameteer values} 

DefaultDictionary = 'Dictionary'; 

DefaultEntries = 32; 

DefaultReserved = 256; 

DefaultBufferSize = 3; 
- 21 - 

type ProcessorIndex = SmallestProcessorIndex .. LargestProcessorIndex; 

EntryIndex = SmallestDictIndex .. LargestDictIndex; 

DictSize = 0 .. MaxNumberOfEntries; 

Pointer = SmallestPointer .. LargestPointer; 

DictEntry = record 

Left, Right: Pointer 

LocalDictionary = array [ EntryIndex ] of DictEntry; 

Link 

Type: (Empty, Valid); 

Value: Pointer 

BufferIndex = LeftmostBufferIndex .. RightmostBufferIndex; 

Buffersize = 0 .. MaxBufferSize; 

Buffer = array [ BufferIndex ] of Link; 

StringIndex = 1 .. MaxStringSize; 

String 

end; 

- record 

end; 

= array [ StringIndex ] of char; 

var { Per Processor Global Data Structures} 

Dictionary: array [ ProcessorIndex ] of LocalDictionary; 

NumEntries: array [ ProcessorIndex ] of DictSize; 

InputData: array [ ProcessorIndex ] of Buffer; 

OutputData: array [ ProcessorIndex ] of Link; 

{ Global Data Structures} 

BreakSupplied: boolean; 

Reserved, Breakpoint: Pointer; 

PairsToSkip: Buffersize; 

Learn: array [ ProcessorIndex ] of boolean; 

{ Implementation Global Data Structures} 

EntriesPerProcessor: Dic tSize; 

LearningProcessor: Pointer ; 

BufSize: Buffersize; 

RightmostMatchFirst, UseFullMatchAlg: boolean; 

Dictionary Filen ame: String; 

MaxTokenValue: Pointer; 

Ignore: integer; 

{ Global variables needed by low-level 1/0 routines} 

rlosize, rleftover, wlosize, wleftover: integer; 

#include uti1ities.i” { Useful low level functions} 

#include “row.args.i” { Process command line arguments} 
- 22 - 

#include "io.i"{ Low Level 1/0 Routines} 

function Code( Processor: ProcessorIndex; Entry: EntryIndex ): Pointer; 

begin 

end; 

Code := Reserved + Processor*EntriesPerProcessor + En try 

function Iscode( Value: Pointer; var Proc: ProcessorIndex; 

var Entry: EntryIndex ): boolean; 

begin 

if (Value < Reserved) then IsCode := false 

else begin 

Proc := (Value - Reserved) div EntriesPerProcessor; 

Entry := (Value - Reserved) mod EntriesPerProcessor; 

IsCode := true 

end 

end; 

function Length( Processor: ProcessorIndex; Entry: EntryIndex ): integer; 

var 

Proc: ProcessorIndex; 

Offset: EntryIndex; 

Result: integer; 

if Iscode( Dictionary[ Processor I[ Entry ].Left, Proc, Offset ) - 

begin 

then Result := Length( Proc, Offset ) 

else Result := 1; 

then Result := Result + Length( Proc, Offset ) 

else Result := succ( Result ); 

if Iscode( Dictionary[ Processor I[ Entry ).Right, Proc, Offset ) 

Length := Result 

end; 

procedure SaveDictionary; 

var 

Processor: ProcessorIndex; 

Entry: EntryIndex; 

Dic tionaryFile: text; 

rewrite( DictionaryFile, DictionaryFilename ); 

begin 
- 23 - 

for Processor := SmallestProcessorIndex to LargestProcessorIndex do 

writeln( DictionaryFile, Processor, ' ', Entry, 

Code( Processor, Entry ), ', 

Dictionary[ Processor I[ Entry ).Left, ' ', 

Dictionary[ Processor I[ Entry ].Right, ' I, 

Length( Processor, Entry ) ) 

for Entry := 0 to pred( NumEntriesI Processor 1 ) do 11 

, 

end; 

function FindMatch( Processor: ProcessorIndex; 

var LeftPtr, RightPtr: Link; 

Size: DictSize; 

var LocalDict: LocalDictionary ): boolean; 

var 

Index: DictSize; 

En try: Dic tEn try; 

Found: boolean; 

Found := false; 

Index : = SmallestDic tIndex; 

while (Index < Size) and not Found do 

Entry := LocalDict( Index 1; 

Found := (Entry.Left = LeftPtr.Value) and 

(Entry.Right = RightPtr.Value); 

if not Found then Index := succ( Index ) 

else if RightmostMatchFirst then 

LeftPtr.Value := Code( Processor, Index ); 

RightPtr.Type := Empty 

end 

else begin 

LeftPtr.Type := Empty; 

RightPtr.Value := Code( Processor, Index ) 

begin 

begin 

begin 

end 

end; 

FindMatch := Found 

end; 

function ValidMatch( Processor: Processorhdex; 

var LocalDict: LocalDictionary; 

Current, Last: Pointer ): boolean; 
- 24 - 

var 

Repeat: boolean; 

LastIndex: EntryIndex; 

if NumEntries[ Processor 1 = 0 then Repeat := false 

else begin 

LastIndex := pred( NumEntries( Processor ] ); 

Repeat := (LocalDict[ LastIndex ].Left = Current) and 

begin 

(LocalDict( LastIndex ].Right = Last); 

end; 

if not Breaksupplied then ValidMatch := not Repeat 

else ValidMatch := (((Last <Breakpoint) and (Current <Breakpoint)) or 

((Last> =Breakpoint) and (Current> =Breakpoint))) 

and not Repeat 

end; 

procedure UpdateDictionary( Processor: ProcessorIndex; 

var LocalDic t : LocalDic tionar y ; 

Current, Last: Pointer); 

v ar 

begin 

NewEntry: EntryIndex; 

if PairsToSkip > 0 then PairsToSkip := pred( PairsToSkip ) 

else if ValidMatch( Processor, LocalDict, Current, Last ) then 

NewEntry := NumEntries[ Processor 1; 

if Code( Processor, NewEntry ) <= LargestPointer then - 

LocaDict[ NewEntry ].Left := Current; 

LocalDict[ NewEntry ].Right := Last; 

NumEntries[ Processor ] := succ( NewEntry ); 

begin 

begin 

end 

end 

end; 

function BufferIsFull( var LocalBuffer: Buffer ): boolean; 

var 

Index: Buffersize; 

Result: boolean; 

Result := true; 

Index := LeftmostBufferIndex; 

begin 
- 25 - 

while Result and (Index < BufSize) do 

Result := Result and ( LocalBuffer[ Index ].Type = Valid ); 

Index := succ( Index ) 

BufferIsFull := Result 

begin 

end; 

end; 

procedure UpdateProcessor( Processor: ProcessorIndex; 

var LocalDict: LocalDictionary; 

var Learn: boolean; 

var InData: Buffer; 

var OutData: Link ); 

var{ More per processor scratch variables ...} 

Match: boolean; 

{ Implementation variables ...} 

Localsize: DictSize; 

var 

begin 

Match := Match or 

FindMatch( Processor, InData[ Buffndex 1, 

procedure FullLeftmostMatch; 

Buff ndex: BufferIndex; 

for Buffndex := LeftmostBufferIndex to BufSize - 2 do 

InData[ succ(BufIndex) 1, 

Localsize, LocalDict ); 

end; - 

var 

begin 

Match := Match or 

FindMatch( Processor, InData[ BufIndex 1, 

procedure FullRightmostMatch; 

Buff ndex: BufferIndex; 

for BufIndex := BufSize - 2 downto LeftmostBufferIndex do 

InData[ succ( BufIndex ) 1, 

Localsize, LocalLlict ); 

end; 

var 

begin 

procedure FirstLeftmostMatch; 

Buff ndex: BufferIndex; 

Buff ndex := LeftmostBufferIndex; 

while (BufIndex < pred( BufSize )) and not Match do 
* 26 - 

begin 

Match := Match or 

FindMatch( Processor, InData[ BufIndex 1, 

InData[ succ(BufI ndex) 1, 

LocalSize, LocalDict ); 

end 

end; 

var 

begin 

BufIndex := succ( BufIndex ) 

procedure FirstRightmostMatch; 

Buff ndex: BufferIndex; 

BufIndex := pred( BufSize ); 

repeat 

Buflndex := pred( BufIndex ); 

Match := Match or FindMatch( Processor, InData[ BufIndex 1, 

InData[ succ(BufIndex) 1, 

Localsize, LocalDict ); 

until Match or (BufIndex = LeftmostBufferIndex); 

end; 

0utData.Type := Empty; 

if BufferIsFull( InData ) then 

Match := false; 

Localsize := NumEntries[ Processor 1; 

if UseFullMatchAlg then 

begin 

begin 

if RightmostMatchFirst then FullRightmostMatch - 

else FullLeftmostMatch 

else if RightmostMatchFirst then FirstRightmostMatch 

else FirstLeftmostMatch; 

if not Match then 

begin 

if Learn then 

UpdateDic tionary( Processor, LocalDic t, 

InData[ pred(BufSize) ].Value, 

0utData.Value ); 

OutData := InData[ pred( BufSize ) 1; 

end 

end; 

end; 

function CurrentDictIsFull: boolean; 
. 

begin 

CurrentDictIsFull := 

(NumEntries[ LearningProcessor ] = EntriesPerProcessor) and 

Learn[ LearningProcessor ] 

end; 

procedure Sw i t c hToNex tD ic t; 

begin 

Learn[ LearningProcessor ] := false; 

if LearningProcessor < LargestProcessorIndex then 

LearningProcessor := succ( LearningProcessor ); 

Learn[ LearningProcessor ] := true; 

{ Every new processor must skip first 'BufSize' pairs} 

PairsToSkip := BufSize 

begin 

end 

end; 

procedure ShiftBuffer( var LocalBuffer: Buffer ); 

var 

begin 

Target, Buffndex: BufferIndex; 

Target := pred( BufSize ); 

for Buffndex := BufSize - 2 downto LeftmostBufferIndex do 

if LocalBuffer[ Buffndex ].Type = Empty then Target := Buffndex; 

for Buff ndex := Target downto succ( LeftmostBufferIndex ) do 

LocalBuffer[ Buflndex ] := LocalBufferI pred( BufIndex ) 1; 

end; 

procedure ProcessToken( InputToken: Link ); 

var 

begin 

Processor: ProcessorIndex; 

InputDataI 0 I[ LeftmostBufferIndex ] := InputToken; 

{ All processors work on their buffers 

for Processor := SmallestProcessorIndex to LargestProcessorIndex do 

UpdateProcessor( Processor,Dictionary[Processor],Learn[Processor], 

InputData[Processor], OutputData[Processor] ); 

} 

{ Shift processor buffers right } 
for Processor := SmallestProcessorIndex to LargestProcessorIndex do 

ShiftBuffer( InputData[ Processor ] ); 

{ Broadcast data to the next processor in the row 

for Processor := SmallestProcessorIndex+l to LargestProcessorIndex do 

OutputDataI pred( Processor ) 1; 

} 

InputData[ Processor I[ LeftmostBufferIndex ] := 

if CurrentDictIsFull then SwitchToNextDict; 

if (OutputData[ LargestProcessorIndex ].Type = Valid) then 

WriteBits( OutputData( LargestProcessorIndex ].Value, 

LargestPoin ter ) 

end; 

procedure FlushLeftOver; 

var 

Leftover: integer; 

Index: BufferIndex; 

for Leftover := LargestProcessorIndex downto SmallestProcessorIndex do 

if InputData[ Leftover I[ Index ].Type = Valid then 

begin 

for Index := pred( BufSize ) downto LeftmostBufferIndex do 

WriteBits( InputData[ Leftover I[ Index ].Value, 

LargestPointer ); 

end; 

- 

procedure ProcessInput; 

var 

begin 

InputToken: Link; 

PassThru( Ignore ); 

while not Endomits( MaxTokenValue ) do 

1nputToken.Type := Valid; 

1nputToken.Value := ReadBits( MaxTokenValue ); 

ProcessToken( InputToken ) 

begin 

end; 

FlushLeftOver; 

FlushBits 
- 29 - 

end; 

.- 

procedure InitializeProcessors; 

var 

Processor: ProcessorIndex; 

Index: BufferIndex; 

for Processor := SmallestProcessorIndex to LargestProcessorIndex do 

Learn[ Processor ] := false; 

NumEntries[ Processor ] := 0; 

for Index := LeftmostBufferIndex to pred( BufSize ) do 

InputData[ Processor I[ Index ].Type := Empty; 

OutputDataI Processor ].Type := Empty 

end; 

LearningProcessor := SmallestProcessorIndex; 

Learn[ SmallestProcessorIndex ] := true; 

{ Initial processor must skip first pair } 

PairsToSkip := 1; 

begin 

begin 

end; 

begin 

rlosize := I;{ 1/0 initialization} 

wlosize := 1; 

UseFullMatchAlg := true; 

RightmostMatchFirst := false; 

BufSize := DefaultBufferSize; 

Breaksupplied := false; 

Breakpoint := 0; 

Ignore := 0; 

Reserved := DefaultReserved; 

EntriesPerProcessor := DefaultEntries; 

Processhguments; 

InitializeProcessors; 

ProcessInpu t; 

S av eD ic t ion ar y 
. - 30 - 

end. 

{ The functions in this file provide a means for low-level I/O.} 

{ They were originally written by James Storer.} 

function ReadByte( var SomeFile: text ): integer; 

const 

v ar 

CarriageReturn = 10; 

NextChar: char; 

Byte: integer; 

if (eof( SomeFile )) then Byte := 0 

else if (eoln( SomeFile )) then 

{read blank that PASCAL replaced for line end} 

read( SomeFile, Nextchar); 

Byte := CarriageReturn 

end 

else begin 

read( SomeFile, NextChar ); 

Byte := ord( NextChar ); 

{check for two's complement form of a non-ascii character} 

if (Byte < 0) then Byte := Byte + 256 

ReadByte := Byte - 

begin 

begin 

end; 

end; 

procedure WriteByte( var SomeFile: text; Byte: 0..255 ); 

begin 

end; 

write( SomeFile, chr( Byte )); 

{ The following functions implement a means to read/write integers using } 

{ least number of bits that can still represent integers in the relevant } 

{ range. All input/output these functions make is from 'input' and to 1 

{ 'output'. } 

function EndOfBits( MaxValue: integer ): boolean; 
begin 

if (rlosize > MaxValue) then EndOfBits := false 

else EndOfBits := eof( input ) 

end; 

{read smallest number of bits capable of holding the argument} 

function ReadBits( MaxValue: integer ): integer; 

Value, Length, MaxLength: integer; 

Value := 0; 

Length := I; 

MaxLength := 2; 

while (MaxLength <= MaxValue) do MaxLength := MaxLength * 2; 

while (Length < MaxLength) do 

if (rlosize = 1) then 

rleftover := ReadByte( input ); 

rlosize := 256; 

rlosize := rlosize div 2; 

Value := (Value * 2) + (rleftover div rlosize); 

rleftover := rleftover mod rlosize; 

Length := Length * 2 

ReadBits := Value 

var 

begin 

begin 

begin 

end; 

end; 

end; 

{write on argl arg2 using the smallest number of bits capable of holding arg3) 

procedure WriteBits( Value, MaxValue: integer); 

var 

begin 

Length, MaxLength: integer; 

MaxLength := 2; 

while (MaxLength <= MaxValue) do MaxLength := MaxLength * 2; 

Length := MaxLength; 

while (Length > I) do 

Length := Length div 2; 

wleftover := (wleftover * 2) + (Value div Length); 

begin 
- 32 - 

wlosize := wlosize * 2; 

Value := Value mod Length; 

if (wlosize = 256) then 

begin 

WriteByte( output, wleftover ); 

wlosize := 1; 

wleftover := 0 

end 

end 

end; 

{flush to output any left over fraction of a byte} 

procedure FlushBits; 

begin 

if (wlosize > 1) then 

while (wlosize < 256) do 

wleftover := wleftover * 2; 

wlosize := wlosize * 2; 

WriteByte( output, wleftover ) 

begin 

begin 

end; 

end 

end; 

{pass through a number of bytes given by argument} 

procedure PassThru(num:integer); 

var 

begin 

index: integer; 

index := 0; 

while ((index < num) and (not eof( input ))) do 

begin 

index := index + 1; 

WriteByte( output, ReadByte( input )) 

end 

end; 

{ This procedure reads in all command line parameters and modifies the} 

{ initial state of the program accordingly. Absolutely NO error } 

{ checking is done.} 
- 33 - 

procedure ProcessArguments; 

var 

index: integer; 

argument: String; 

DictionaryGiven: boolean; 

Buffer: String; 

index := 1; 

Dictionary Given := false; 

while (index <= argc -1) do 

begin 

begin 

argv( index, argument ); 

case argument[ 2 ] of 

' r '. 

'B': begin 

index := succ( index ); 

argv( index, Buffer ); 

BufSize := AtoI( Buffer ) 

RightmostMatchFirst := true; If'. . UseFullMatchAlg := false; 

end; 

'E': begin 

index := succ( index ); 

argv( index, Buffer ); 

EntriesPerProcessor := AtoI( Buffer ) 

end; 

'G': begin 

index := succ( index ); 

argv( index, Buffer ); 

Breaksupplied := true; 

Breakpoint := Ator( Buffer ) 

end; 

ID': begin 

index := succ( index ); 

DictionaryGiven := true; 

argv( index, DictionaryFilename ) 

end; 

'R': begin 

index := succ( index ); 

argv( index, Buffer ); 

Reserved := AtoI( Buffer ) 

end; 

'S': begin 

index := succ( index ); 

argv( index, Buffer ); 
8 

- 34 - 

Ignore := AtoI( Buffer ) 

end; 

index := succ( index ) 

if not DictionaryGiven then DictionaryFilename := DefaultDictionary; 

MaxTokenValue := pred( Reserved ) 

end; 

end; 

end; 

function Digit( Somechar: char ): integer; 

begin 

end; 

Digit := ord( SomeChar ) - ord( ’0’ ); 

{ The folowing AtoI function will only work if its string argument is 

a valid integer number in string representation. Absolutely NO error 

checking is done. } 

function AtoI( Somestring: String ): integer; 

var 

Result: integer; 

Minus: boolean; 

Index: StringIndex; 

Thischar: char; 

Result := 0; 

Minus := false; 

for Index := 1 to MaxStringSize do 

- begin 

begin 

ThisChar := Somestring[ Index 1; 

if (ThisChar = ’-’) and (Result = 0) then 

else if (Thischar in [ ’O’..’O’ I) then 

Minus := not Minus 

Result := Result * 10 + Digit( ThisChar ); 

end; 

if Minus then Result := - Result; 

AtoI := Result 

end; 
- 35 - 

5. MPP Code 

{ $h-,d+,m-} 

{ program: row} 

{ RSIC, Inc.} 

{ date: August, 1987) 

program row( input, output, rowjndex, col-index, DataIn, DataOut ); 

const FirstProc = 0; { Processors} 

LastProc = 127; 

FirstIndex = O;{ Dictionary Entries} 

LastIndex = 29; 

MaxEntries = 30; 

FirstPtr = O;{ Output Tokens} 

LastPtr = 4094; 

NullPtr 

MaxPtr = 4095; 

FirstImage = O;{ Images} 

LastImage = 1; 

= 4095;{ Special Null Token} 

NoShiftUp = O;{ Number of cells to shift data N/S} 

ShiftRight = -l;{ Number of cells to shift data E/W} 

ShiftLeft = 1; 

DefEhtries = 32;{ Default Values} 

Defaeserve = 256; 

ProcIndex = FirstProc .. LastProc; 

EntryIndex = FirstIndex .. LastIndex; 

DictSize = 0 .. MaxEntries; 

Pointer = FirstPtr .. MaxPtr; 

ImageIndex = FirstImage .. LastImage; 

PtrParArr = parallel array [ ProcIndex, ProcIndex ] of Pointer; 

BoolParArr = parallel array [ ProcIndex, ProcIndex ] of boolean; 

SizeParArr = parallel array [ ProcIndex, ProcIndex ] of DictSize; 

IOBuffer = stager array [ ProcIndex, ProcIndex ] of Pointer; 

StagerBuf = stager array [ ImageIndex, ProcIndex, ProcIndex ] 

of Pointer; 
- 36 - 

DictArray = array [ EntryIndex ] of PtrParArr; 

var { Parallel (Per Processor) Global Data Structures} 

OldBufPtr : PtrParArr;{ Input Buffer } 

OldBufVal : BoolParArr; 

NewBufPtr : PtrParArr; 

NewBufVal : BoolParArr; 

OutputPtr : PtrParArr;{ Output Token} 

OutputVal : BoolParArr; 

LeftDict : DictArray;{ Dictionary} 

RightDict : DictArray; 

Localsize : SizeParArr; 

Learning : BoolParArr; { Miscellaneous} 

Mask : BoolParArr; 

MustSkip : BoolParArr; 

ImageBuf : S tagerBuf; { Input/Ou tpu t} 

ImageIn : PtrParArr; 

ImageOut : PtrParArr; 

DataIn : file of IOBuffer; 

DataOut : file of IOBuffer; 

{ Scalar Global Data Structures} 

MaxOutTkn : integer;{ Max Output token} 

MaxInTkn : integer;{ Max Input token } 

InputImage : ImageIndex;{ # of current input image} 

OutImage : ImageIndex;{ # of current output image} 

InputCol : ProcIndex;{ # of current input column} 

OutputCol : ProcIndex;{ # of current output column} 

EndOfInput : boolean;{ true when last image done} 

%include 'io.i'{ Low Level 1/0 Routines} 

procedure restrc; extern; { PE initialization} 

procedure FindMatch; 

var 

Index : DictSize; 

Temp : BoolParArr; 

Searching : BoolParArr; 
- 37 - 

begin 

Searching := OldBufVal and NewBufVal; 

Temp := (LocalSize > 0); 

Searching := Searching and Temp; 

Index := FirstIndex; 

while (Index < MaxEntries) and any( Searching, 1, 2 ) do 

{ Select processors where a match could be expected} 

Mask := (LocalSize > Index) and Searching; 

{ Reduce Mask set to those where a match exists} 

Temp := (OldBufPtr = RightDict[ Index 1) and 

(NewBufPtr = LeftDict[ Index I); 

Mask := Mask and Temp; 

{ Update processors where a match was found} 

where Mask do OutputPtr := col-index * MaxEntries; 

where Mask do OutputPtr := OutputPtr + (Index + DefReserve); 

where Mask do OutputVal := true; 

where Mask do Searching := false; 

where Mask do OldBufVal := false; 

where Mask do NewBufVal := false; 

Index := Index + 1; 

begin 

I 

end; 

end; 

procedure UpdateDict; 

var 

DictIndex : DictSize; 

Offset 

Lastsize : DictSize; 

Candidates : BoolParArr; 

Temp : BoolParArr; 

Bothunder : BooParArr; 

BothOver : BoolParArr; 

ValidMatch : BoolParArr; 

Candidates := OldBufVal and NewBufVal; 

LastSize := max( Localsize, 1, 2 ); 

if LastSize > LastIndex then LastSize := LastIndex; 

for DictIndex := 0 to LastSize do 

: DictSize;{ to get around compiler bug} 

begin 

begin 

{ decide which processors should update the DictIndex’th} 

{ entry in their dictionary -> Temp} 

Offset := DictIndex; 
- 38 - 

Temp := LocalSize = Offset; 

Temp := Temp and Candidates; 

Temp := Temp and Learning; 

{ Reject those processors that do not have a valid match} 

Bothunder := (OldBufPtr < DevReserve) and 

(OutputPtr < DefReserve); 

BothOver := (OldBufPtr >= DevReserve) and 

(OutputPtr >= DefReserve); 

ValidMatch := Bothunder or Bothover; 

Temp := Temp and ValidMatch;. 

{ first pair to be learned must be skipped} 

where MustSkip do Mask := false otherwise Mask 

where Temp do MustSkip := false; 

if any( Mask, I, 2 ) then 

begin 

where Mask do LeftDict [ Offset ] := OldBufPtr; 

where Mask do RightDict[ Offset ] := OutputPtr; 

where Mask do LocalSize := LocalSize + I; 

where Mask do Candidates := false 

end 

end 

end; 

procedure UpdateAll; 

begin 

{ Clear output flag in all processors} 

OutputVal := false; 

{ Find all matches between buffers and dictionaries} 

FindMatch; 

{ Update Dictionaries, where necessary} 

Up d at eDic t ; 

{ Output older buffer entry if no match was found} 

Mask := OldBufVal and NewBufVal; 

where Mask do OutputPtr := OldBufPtr; 

where Mask do OutputVal := true; 

end; 

=T 

procedure SwitchDict; 

var 

begin 

NewMask: BoolParArr; 

{ Mask = true if local dictionary is full} 
- 39 - 

Mask := LocalSize = MaxEntries; 

Mask := Mask and Learning; 

{ NewMask = true if new dictionary is being enabled} 

NewMask := shift( Mask, NoShiftUp, ShiftRight ); 

where Mask do NewMask := false; 

{ new dictionaries must skip their first pair} 

MustSkip := MustSkip or NewMask; 

{ Update Learning mask} 

where Mask do Learning := false 

otherwise Learning := Learning or NewMask; 

end; 

procedure ProcTokens; 

begin 

{ Load input data on first column of processors} 

Next Column; 

{ Update Processor status} 

UpdateAll; 

{ Shift Buffers right, where appropriate} 

where NewBufVal do OldBufPtr := NewBufPtr; 

where NewBufVal do OldBufVal := NewBufVal; 

{ Broadcast data to next processor in row} 

NewBufPtr := shift( OutputPtr, NoShiftUp, ShiftRight ); 

NewBufVal := shift( OutputVal, NoShiftUp, ShiftRight ); - 

{ Switch to next dictionaries, if necessary} 

SwitchDict; 

{ Output, if necessary ...} 

ColumnOut; 

end; 

procedure InitProcs; 

begin 

LocalSize := 0; 

OutputVal := false; 

OldBufVal := false; 

NewBufVal := false; 

Learning := false; 
a .’ 

- 40 - 

where (col-index = FirstProc) do Learning := true; 

where (col-index = FirstProc) do MustSkip := true 

end; 

begin 

restrc;{ Initialize PECU system data structures} 

MaxOutTkn := LastPtr; 

MaxInTkn := DefReserve - 1; 

LoadImages;[ Load input images into Stager buffer} 

InitProcs;{ Initialize processor data structures} 

Initoutput;{ Initialize output routines} 

while not EndOfInput do ProcTokens; 

FlushBuffers{ Flush remaining tokens} 

end. 

procedure Loadlmages; 

var 

Index : ImageIndex; 

Offset : ImageIndex; 

Temp : PtrParArr; 

reset( DataIn ); 

for Index := FirstImage to LastImage do 

Offset := Index; 

get( DataIn ); 

transfer( DataIn, Temp ); 

waitio; 

transfer( Temp, ImageBuf[ Offset, , ] ); 

waitio; 

end; 

InputCol := 0; 

InputImage := 0; 

EndOff nput := false; 

transfer( ImageBuf[ InputImage, , 1, ImageIn ); 

begin 

begin 
- 41 - 

waitio 

end; 

procedure Nextcolumn; 

vat 

begin 

Value: integer; 

Mask := (col-index = FirstProc); 

where Mask do NewBufPtr := ImageIn; 

where Mask do NewBufVal := (NewBufPtr < > NullPtr); 

ImageIn := shift( ImageIn, NoShiftUp, ShiftLeft ); 

if (InputCol < LastProc) then lnputCo1 := InputCol + 1 

else begin 

if (InputImage = LastImage) then EndOfInput := true 

else begin 

InputImage := Inputimage + 1; 

transfer( ImageBuf[ InputImage, , 1, ImageIn ) 

InputCol := 0; 

end 

end 

end; 

procedure Initoutput; 

begin 

rewrite( DataOut ); 

ImageOut := NullPtr; 

OutputCol := 0 

end; 

procedure ColumnOut; 

begin 

Mask := (col-index = LastProc); 

where Mask do 

where OutputVal do ImageOut := OutputPtr 

otherwise ImageOut := NullPtr; 

Mask := Mask and OutputVal; 

if any( Mask, 1, 2 ) then 

begin 

begin 

if (OutputCol < LastProc) then 

OutputCol := OutputCol + 1; 
I' ' 

- 42- 

ImageOut := shift( Imageout, NoShiftUp, ShiftLeft ) 

end 

else begin 

transfer( Imageout, DataOut ); 

waitio; 

ImageOu t : = NullP tr; 

put( DataOut ) 

end 

end 

OutputCol := 0; 

end; 

procedure Flushone( var PtrArray: PtrParArr; var Bookray: BoolParArr ); 

begin 

OutputVal := Bookray; 

OutputPtr := PtrArray; 

ColumnOu t; 

Bookray := shift( Bookray, NoShiftUp, ShiftRight ); 

PtrArray := shift( PtrArray, NoShiftUp, ShiftRight ) 

end; 

procedure FlushBuffers; 

var 

Index: ProcIndex; 

Offset: ProcIndex; 

for Index := LastProc downto FirstProc do 

Flushone( OldBufPtr, OldBufVal ); 

Flushone( .NewBufPtr, NewBufVal ) 

close( DataOut ) 

begin 

begin 

end; 

end;