LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 5IO.&4 r\o. &l3-fc'7 Cop ^ Digitized by the Internet Archive in 2013 http://archive.org/details/firmwaredatacomp617taow W£6AS uiUCDCS-R-7^-6l7 yyi aJLM A FIRMWARE DATA COMPRESSION UNIT January 197^- by William Yan-Yuen Tao DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS THE LIBRARY OF THE FC3 15 1974 ' Y OF ILLINOIS UIUCDCS-R-7 i +-6l7 A FIRMWARE DATA COMPRESSION UNIT by William Yan-Yuen Tao January 197^ Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois This work was supported in part by the National Science Foundation under Grant No. US NSF GJ-36265 and was submitted in partial fulfillment for the Master of Science degree in Computer Science, 197^. Ill TABLE OF CONTENTS Page I. INTRODUCTION 1 II. GENERAL REVIEW OF DATA COMPEESSION 3 III. DESIGN CONSIDERATIONS 7 IV. IMPLEMENTATION 12 A. Huffman Codes Construction 12 B. Encoding 1^ 1. Data Structure of the Code Table for Encoding Ik 2 . The Encoding Algorithm 17 3 . Performance 19 C . Decoding 20 1. Decoding Algorithm 2k 2 . Decoding Performance 2k V. SIMULATION RUN 26 LIST OF REFERENCES 31 APPENDIX A. Listings of the Simulation Run 32 B. Firmware Listings for Encoding and Decoding Routines 38 IV LIST OF FIGURES Figure Page 1. Bit Mapping lj. 2 . Run Length Coding , i|. 3« Data Compression Block Diagram 7 k. Example of Huffman Code .. 13 5. Binary Tree Representation of Huffman Code 1^ 6. Schematic Representation of the Code Table 18 7. Schematic Representation of d. Table, c + #(C „ ) - 1 Table J s . d . and s . - c Table 22 8. Schematic Representation of Pattern Table 23 9. Detail Block Diagram of Data Compression-Decompression Unit 29 I. INTRODUCTION In present days, most data processing and large information retrieval systems are faced with the serious problem of ever increasing size of their data bases. An obvious solution to this problem is to install more storage devices at a further increase in cost. In many instances where the data base is extremely large, the increase in storage volume can be achieved only by using larger and more expensive on-line storing devices. For example, a file may be too large to reside in a 231^ Disc and hence the larger and more expensive 3330 has to be used. This problem of data explosion can be solved partially by representing the stored information by more efficient codes. In most of the current information systems, individual characters are encoded separately (ASCII code, EBCDIC code). The probabilities of occurrence of the characters are not taken into consideration. A frequently occurring character is encoded into as many bits as a seldom occurred character. Also, no attempt is made to encode strings of characters that occur frequently. As a result of this method of encoding, information is encoded using more bits than necessary. This is where data compression comes into the picture. Besides • reducing the amount of storage required, data compression may reduce program execution time even after making allowance for the decompression overhead, because there would be a lot fewer blocks of data to access. In data communication, sending compressed data over communication lines effectively means an increase in the line capacity. Although the present trend on the price of mass storage devices is a downward one with the new development of bubble memory, etc., the use of compression in data communication is likely to increase in importance with the increase application in communication networks. In this report, a data compression-decompression algorithm has been developed. The compression technique employed is the Huffman coding method which minimizes the average length of the codewords for encoding. This algorithm is table driven. It is developed in firmware on the Lockheed SUE microprogrammable minicomputer as a stand alone unit. Due to the removal of the data compression-decompression function from the main CPU and the high speed of execution of microprogram, overhead in performing the data compression-decompression algorithm is minimized tremendously. The result of this is a net gain in precious on-line storage area and I/O time with no loss in main CPU overhead. In the following sections, a general discussion of compression techniques will be presented, followed by a discussion on the design considerations of a data compression-decompression unit. A detail presentation of the implementation will then follow with discussions of the compression and decompression algorithms and data structures. In order to illustrate the effectiveness of the implementation, a simulation test was run and the results are also presented. II. GENERAL REVIEW OF DATA COMPRESSION Although there are a variety of compression techniques around, they all have one common goal among them — that is, to reduce redundancy in the original file. How they go about doing it and their effectiveness vary. They can generally be broken down into the following several groups. 1. Data dependent techniques. This type of techniques is frequently employed in files with well-defined fields in each record. It takes advantage of the logical relationships between values of successive fields to reduce redundancy [k] . Differencing is an example of this type of techniques. It is not uncommon to find sequenced numeric fields in a business record. Instead of storing the full representation of each field, only the difference between the present field and the previous one is stored. An even greater compression ratio can be achieved if this difference is stored in binary instead of the coded characters. 2. Null suppression. This technique takes advantage of the large amount of blanks and zeros that occur in a business record and suppress them to a shorter representation. It is probably the most widely used data compression technique for business data files since it is easy to implement, inexpensive to run and achieve reasonable degree of compression. Two popular techniques are bit mapping and run length coding [k-]. Figure 1 is a simple example that illustrates the use of bit mapping in blank suppression. Each bit in the bit map corresponds to a fixed storage size, usually one computer word or CUSTOMER NAME : DOE ,_, ^ U i_l u u , JOHN u u u i_i Original Data D E J H N Compressed Data 110001100 D 9 E J $ H N bit map Figure 1. Bit Mapping byte. A one in the bit map indicates that data is present in that relative position of the record while a zero indicates blanks. In run length coding, a special character is used to indicate the start of a string of blanks or zeros. This character is then followed by a count character which indicates the number of blanks or zeros in the original string, minus two; the two coming from the mark character and count character. Figure 2 is an example of run length coding. part number description quantity 00000021a B0LTS u u u u u u U 0000015 original data: 0000002^1 B0LTS u u u u u u u 0000015 compressed data: #J-2^1B0LTS*5#315 i — i i_j i i # indicates string of 0, * indicates string of blanks Figure 2. Run Length Coding It is more convenient to choose some seldom occurred characters to use as a mark character. In case such character occurs in the data, the ambiguity can be resolved by storing two such characters in a row. Where the character set includes unused characters such as in EBCDIC code, the obvious choices for mark characters are of course the unused characters. 3. Pattern substitution. The basic philosophy of this technique is first to compile a list of distinct patterns that makes up the whole file. Each pattern in this list is then assigned a unique codeword, the simplest being the number of that pattern in the list. Compression is then accomplished by replacing each occurrence of a pattern in the file by its corresponding codeword. The SOLID system developed at Penn State University is a famous example using this technique [3]. The codewords used in the SOLID system are all 8 bits long (256 different codewords). The list of distinct patterns is compiled by a recursive bit-pattern recognition technique. h. Statistic encoding. This technique takes advantage of the statistical probabilities of occurrence of message units (single character, patterns) so that short code words are used for frequently occurring message units and longer code words are used for message units that occur infrequently. This technique in effect amounts to minimizing of the average code word length. Among the codes designed to njninizc the average codeword length, Huffman code is optimum in the sense that it has the shortest average codeword length [1]. In addition to being the most efficient code, Huffman code is also an instantaneous code. That is, in Huffman code every codeword corresponds to a distinct message unit (uniqely decipherable), no codeword is a prefix of some other longer codewords. This allows decoding to be done efficiently as each time a message unit is identified from a codeword, it is -unique and no ambiguity has to be resolved. An example of Huffman code is given in Figure k. III. DESIGN CONSIDERATIONS In this report, a data compression-decompression algorithm has been developed in firmware on a mi c reprogrammable minicomputer. The compression technique employed is Huffman coding with the character set extended to include patterns of multiple characters. The principle design objective of this project was to design a transportable compression-decompression "node" (or black box) that resides in the I/O path of a computer system and perform data compression and decompression according to the control signal received. (See Figure J. ) fast memory- control signals original data \ data compression- decompression unit compressed data original data compressed data K K on-line secondary storage Figure 3« Data Compression Block Diagram This design objective implies that the compression technique used in the unit should be data independent in order that the compression algorithm can be applied to different files without any changes to the algorithm itself. This objective can be fulfilled if the characteristics of the file that are used by the algorithm to perform compression (decompression) can be 8 systematically parametrised and entered into a table. To compress (decompress) different files, only the corresponding set of parameters for that file has to he loaded and the compression (decompression) is done by a fixed algorithm that accesses these parameters in the table. Of the four groups of compression techniques discussed in Section II, both group 3 and group k- make use of code tables to do compression, hence they lend themselves more readily to be implemented in a table driven manner. Although techniques in group 1 can be implemented to operate in a table look up manner, the algorithms to look up the tables, besides the contents of the tables, have to be tailored to suit the special properties of each different file. As for null suppression, the degree of compression achieved is inadequate if it is used alone. However, the same effect of null suppression on long repetitive patterns is desirable in a compression algorithm. It is also noticed that pattern substitution is actually the same as recoding the original information with some other codes. Compression is achieved by recoding longer message units than those in the original data. In this case, , characters of patterns are encoded instead of just single characters as in the original data. The codes, however, are not weighted according to the proba- bilities of occurrence of the patterns. The SOLID system, for example, uses a set of 256 code words all of which are 8 bits long. Hence compression ratio can be further increased if statistical codes are used to do the encoding. Since Huffman code is optimum [1], the Huffman encoding method is chosen. The set of message units to be recoded includes the basic character set and patterns of varying length. The basic set of characters are included to Insure that during encoding, if no longer patterns can be detected, the process would proceed by encoding at least one character. Once the statistics of a particular type of file are collected and the Huffman codewords constructed, encoding and decoding will he driven hy 2 groups of tables (for detail see section on Implementation). This implies the compression and decompression algorithms are data independent, fulfilling the design objective. Traditionally, data compression algorithms have been implemented in software, and hence have to reside in the file access software of the operating system. This results in a significant amount of CPU overhead. Although there is usually a net gain in program execution time after making allowance for CPU overhead, data compression would have to be ruled out in the case of a compute-bound system. Also, software implementation would require changes to operating system in order to make the compression-decompression operation transparent to the users. With these undesirable effects of software implementation in mind, other forms of implementations were explored. It is well known that nowadays minicomputers are getting less expensive. They are also fast and have elegant, up-to-date architectures. Of particular interest is the class of microprogrammable minicomputers. Microprogramming offers high speed of operation and flexibility to tailor the processor to the specific task it has to perform. This results in high efficiency of operation. If the compression-decompression function is removed from the main CPU, and implemented in a microprogrammable minicomputer the main CPU is relieved to do more important tasks, tasks it is designed to handle efficiently. In fact, in the present trend of computer system design, it is common to have one or more data communication processors or 10 "front ends" to reduce overhead in the main CPU. There is no reason why we cannot have a dedicated miniprocessor to perform data compression- decompression. Or in fact, with the earlier mention of expected rising importance of data compression in communications, the data compression- decompression algorithm can he incorporated in one of the data communication "front ends" or remote data concentrator running in background mode. Hence it has been decided to explore the feasibility of implementing a data compression-decompression unit in firmware. The algorithms are designed and written and test run on the simulator for a microprogrammable minicomputer and their performances evaluated. The target machine for this implementation is the Lockheed SUE processor. It is microprogrammable. It is felt that this machine is a good representation of the wide range of choices of microprogrammable minicomputers available on the today. Some of its favorable characteristics are as follows [9]: 1. l6-bit data word. 2. 36-bit microcode word. 3. l6-bit parallel ALU that logically processes 2 registers in 130ns, or arithmetically within l60ns. k. Priority interrupts with k levels. 5. Multiprocessor configuration capability. 6. Concurrent processing with direct memory transfer. Some of the characteristics of Infibus, the data bus to which the SUE processor is connected, are as follows: 1. Full l6-bit data word transfer. 2. Communication is fully asynchronous - the bus select and bus service cycles are overlapped. 11 3. Overlapped cycles with a minimum of 200ns service cycle provides a combined transfer rate of 5 Megahertzs. The superior performance of this minicomputer is evident from the features cited above. And yet the cost of a processor is $995* and the Inflbus and Inflbus controller is $530. 12 IV. IMPLEMENTATION A. Huffman Codes Construction To compress a file, we first examine its content to choose a set of distinct message units {m. } which makes up the whole file. Again, the message units are either basic characters or strings of characters with the characters encoded in ASCII code. Each of these message units is to be assigned a codeword in Huffman code. The probability of occurrence for each of the message units in the original file Is estimated. Let p. denote the probability of occurrence of the message unit m. . The Huffman codeword length £., of the message unit m. , is then given by £. = L-log p. J [1] where |_a] is the closest integer greater than or equal to a. If the message units in the set (m. } are arranged according to the ascending order of 1 (i.e., descending order of p.), then the corresponding set of codewords {c.} can be constructed with the following algorithm: [7] Algorithm C (Huffman Codes Construction) This algorithm constructs a set of Huffman codewords {c.} for a corresponding set of message units {nu}. The only information needed is the set of codeword lengths { £ } which is arranged in ascending order: CI (Initialize) CI is a string of £. zeros, set i <- 2. C2 (same code length) If £. = i.,, then c = c^ + 1, go to Ck. C3 (longer code length) If £. > £. __, then c ± = c.^ + 1 followed by £ = l zeros. i i-l 13 Ck (do next) If the set {i.} is exhausted, then done, otherwise i *- i + 1, go to C2. After the set of Huffman codes {c.} has been constructed, this set {c.} and the set of message units {m. } are organized, together with some additional information to be described later, into 2 groups of tables to drive the encoding (compression) and decoding (decompression) algorithms. (Figure k is an example of Huffman code and Algorithm C. Original String - "AB . , ABCDAXABCD , , A" Compressed String - "110 1 10 1 00 1 01 1 111 I 00 1 10 1 01" Probability of Message Unit ' Occurr m . % ABCD i/k A i/k i— i i/k AB 1/8 X 1/8 Codeword Length Codeword t. 1 c i 2 00 2 01 2 10 3 110 3 111 Figure k. Example of Huffman Code The set of codewords (c.) may also be represented by an ordered binary tree [71 • The number of terminal nodes in the binary tree is equal to the number of codewords. The codewords are ordered from left to right in the tree with exactly I. branches from the top of the tree to the i-th terminal node. A "0" is associated with each left branch and a "l" is associated with each right branch. See Figure 5 for an example of the set of codewords. Ill- Figure 5. Binary Tree Representation of Huffman Code B. Encoding A very general algorithm for encoding a string of data in Huffman code can be given as follow 1. Choose the longest pattern that is included in the set {m. } at the beginning of the original string of data. 2. Encode this pattern by replacing it with the code word corresponding to it. 3. Remove the pattern just encoded from the beginning of the original string. If there is no more data left, then encoding is done. Otherwise go to step 1. This process is simple if the set of message units consists of all equal length patterns and this length is known ahead of time. However, the situation is considerably complicated with the presence of varying length patterns, especially when one pattern could be the prefix of some other patterns. 1. Data Structure of the Code Table for Encoding There are two characteristics of the set of message units {m. } that make step 1 of the general encoding algorithm prohibitively slow if conventional table structures are used to organize the code table. First, 15 as mentioned before, is the presence of varying length message units in the set {nu}. Second is that there is no break characters to identify out each message unit. The original data is made up of one continuous string of message units, and at each point during encoding, the longest possible message unit has to be recognized in order to achieve maximum compression. In order to do this with reasonable efficiency, a multilevel linked structure is used to represent the code table. The total number of levels in the structure is equal to the length of the longest pattern in the set {m. }. The first level corresponds to the first character of a pattern, the second level corresponds to the second character, if there is any, and so on. The first level is a directly indexed table that includes all the single characters in the ASCII code set and organized in order of the ASCII code of the characters. Each node of the table has the form: bit 15 f CLEN 15 LINK i i i i I C0DE 1 I t CLEN is a ij— bit field that contains the length of the codeword for the character corresponding to that node. The codeword is stored in CODE. The longest codeword allowed is obviously l6. We compute code length from: 1. = [-log (probability of occurrence, P.) J /# of occurrence of m. in original data -log, ' 3 2\Total # of message units in original datay = Ll°So (Total # of message units in original data) - logo ($ of occurrence of m. in original data) J In the worst case, say a certain message unit itl occurs only once in the given data, and the set {m. } contains only single characters (8-bit bytes). Let's calculate a lower bound on the size of data that can be handled by a longest Huffman code length of l6. 16 1 i = 16 = [log 2 (Total # of message units in data) - log (# of occurrence of m, in data)] = [logg (size of data in bytes) - logp(l)] .". size of data = 2 bytes = 65K bytes In practical situation, there are seldom any message units that occur only once in the whole set of data, and the set of message units usually contains patterns in addition to all the single characters. Hence, the size of the data that can be compressed, is usually greater than 65K. LINK is a pointer pointing to the base address of a small table of hash buckets. However, LINK is null if that particular character occurs only as a single character in the set {m.} and does not start any pattern. Each node in the table of hash buckets has the following form: 7 T HASH I HASH is a pointer pointing to a table that contains the nodes of all the second character patterns that start with that first character. For example, if 'A', 'AB' and 'AC! are all in the set of message units, then the first level entry of 'A' would consist of a link pointer to a hash table that contains a pointer to entries 'B' and 'C. The second level is linked to the third level in similar manner, and so on. Hashing with chaining is used to recognize characters from second level on in order to minimize search time. The hash function is a simple one. The least significant 5 bits of the character are used as an index into the hash bucket table, which contains a pointer to the entry of that • IT character if that character is indeed in the table. The nodes in the table for characters in second level and higher levels have the following form: 15 15 CHAR i 15 CLEN LINK _l L 15 CODE ,!, „ J i — > CHAIN FLAG CLEN, LINK and CODE are the same as before. CHAR has the ASCII code of the character corresponds to the node. CHAIN is a link to other nodes that hash to the same address. It is null if there is no collision. FLAG is a 1-bit field that indicates whether there is a code word associated with the pattern indent if ied so far or not. For example, if both 'AB' and 'ABCDE' are patterns, then the entry 'B' in the second level and 'E' in the fifth level would have codewords, while ' C in level three and 'D' in level four would not. At this point, a pictorial representation of the data structure of the code table can be given. (See Figure 6.) 2. The Encoding Algorithm The complete algorithm for encoding is hence as follows: Algor i thm E (Huffman Encoding)' This algorithm inputs a string of text characters, recognizes at any point the longest possible pattern m, € {m. } , the set of unique patterns that makes up the whole text, and outputs the corresponding Huffman codeword of that pattern. El [Initialize] The cursor of the text string P, is initialized to 1. E2 [Next pattern] If input has been exhausted, then done. Otherwise I, J «- 1, read next character (i), and TEMPI, TEMP2 <- C(l), the character. E3 [Identity pattern] If LINK[TEMP2] is null, then output Cj#DE[TEMP2] , set P «- P + J and go to E2. Otherwise I «- I + 1, and read next character C(l). 18 128 entries \ V. ^H » i \^^\ 'B ! i„.l \ -^— — *- j • 1 i m \ 'C 1 1 . — - i 1 — — — • 1 • Figure 6. Schematic Representation of the Code Table 19 Elf [Hash] If HASH[C(l)] is null then output C0DE[ TEMPI], set P - P + J and go to E2. Otherwise TEMP2 <- HASH[C(l)]. E5 [Match character] If C(l) = CHAR[TEMP2], then go to E7. E6 [Chain down] If CHAIN[TEMP2] is null, then output C0DE[ TEMPI], set P <- P + J and go to E2. Otherwise set TEMP2 *- CHAIN[IEMP2] and go to E5. E7 [Update TEMPI] If FIAG[TEMP2] = 1 then go to EJ. Otherwise TEMPI <- 1EMP2, J <- J + 1 and go to E3. 3. Performance For the purpose of timing, the process of encoding can be divided into 2 parts. One is the identification of the longest pattern that is in the set {m. } from the original data. The other is the outputting of the codeword into the compressed data stream after the pattern is identified. The exact amount of time required to encode a file using Algorithm E is evidently dependent upon the hardware characteristics of the computer the encoding is done on. Another factor affecting this is the relationship among the patterns included in the set (m. } ; for example, how many patterns are prefixes of other patterns. However, some processor independent aspects of the algorithm can be given here in the form of number of standard operations and memory accesses required to encode each pattern. The majority of the memory-accesses occur during the identification of a pattern. This job can be considered as being made up of the following tasks, assuming the pattern is of length n: m = ■# of lookahead characters k = § of collisions 1. Read n+m characters from the original data. 2. Read n+m links. 3. Read n+m-1 hash buckets. k. Read n+m-2 characters in table. 20 5. Read k chains. 6. Read k+1 characters for comparison to resolve collision. 7« Read the codeword for the identified pattern. Hence the total number of memoryreads required to identify a pattern of length nis(^m+ ^n + 2k - 2). For example, 'ABCD' and 'ABCDEF' are both in the set {m. }, and the data we are looking at is ABCDEXY The pattern identified is 'ABCD', but the algorithm would read to X to decide this. .". n = k, m = 2, assume there is no collision, k = .*. # of memory read =6+6 + 5+^ + 1 = 22 To output a codeword, assuming a computer word size of l6 bits, the maximum number of shifts that has to be performed is 8. And in case of a codeword filling up one word or crossing word boundary, there would be one memory write. The rest of the operations are for overhead and initialization and are a function of the processor hardware. C. Decoding Let F be a set of data to be compressed and (m. } 1 < i < n is the set of n distinct message units that makes up the whole set F. Let p be the probability of occurrence of m. in set F. [m. } is arranged in descending order of p., i.e., p. > p. for i < j. Let 1. be the Huffman code length of m . .'. fm. } is in descending order of p., if {1.} is arranged 11 11 correspondingly, i.e., it is in ascending order, 1 ± < 1 , i < j. The algorithm for constructing the set of Huffman codes for the set {nu} has been given in section IV. Let {d.} be the set of distinct code lengths J in the set fl.}. fc. ) is divided into subsets of codes of equal code 1 1 length, i.e., C, = {c. 11. = d } 21 If #({ } ) is used to denote number of elements in a set A, then k Z #(C ) = n, where #({d )) = k 3=1 3 d Let s be the smallest index of the c.'s in a C, . c would also have the i l d. s . J a 3 smallest binary value of all the code words in C . By virtue of C2 and C3 3 of Algorithm C, the binary values of the codes in C are all less than 3 c + #(C ). In other words, all binary numbers of length d. and between 3 3 c and c + #(C n ) are code words in C , . s . s . " d . d . 3 3 3 3 During decoding, if we started out examining the smallest code length d_ and work our way up, we only have to compare the next d. bits of the compressed data stream with c + #(C ) in order to determine whether it S 3 3 is a codeword in C. or not. Once this is determined, we can calculate d. 3 the index of this codeword and retrieve the corresponding pattern in the set {m. } and output it. The index in {m. } is calculated as q = s . + c - c where c is the codeword identified 3 q s q = c + (s - c ) by satisfying c < c < c + #(C ) H J 3 3 3 3 Hence in order to perform decoding, we need k- tables - the m. table, the d table, the c + #(C, ) - 1 table and the s. - c table. The data structures for the latter 3 tables are simple sequential tables. (See Figure 7.) Since the patterns in the set {m. } are all of varying length, the index of a pattern in the set {m. ) calculated after identifying out a codeword is used to index into a pointer table which points to a table that contains all the patterns. (see Figure 8.) 22 (D H ■§ -P ■ • • • EH P-H O H ■s EH -rJ o + 03 O CD H ■s +3 ■■d o + ., o CO • • • • o i 0) H ■s Eh t3 o O •H -P * CD CD ?H ft CD o •H -P O H ■§ Eh CD H ■§ +3 d • • • • ~ 1 7 H 0) •H !h -P CD CD o ttO •H F-h d c<3 23 pointer table PLEN PTR .«£- PATTERN m. table 1 A single char 1 PATTERN Figure 8. Schematic Representation of Pattern Table 2k Each node in the pointer table has the following form: 1 PLEN T PTR PLEN contains the length of the pattern in the pattern table. However, if the message unit identified is a single character, its entry in the pointer table would have the following form: ^■'-'^""" 1 1 PATTERN (single char) - i This enables the original chracter to be read immediately instead of one more level of addressing. 1. Decoding Algorithm The decoding algorithm can now be given as follows: Algorithm D (Huffman Decoding) This algorithm. inputs a string of compressed data F', identifies each Huffman codeword and outputs the corresponding pattern for each codeword. The identification of codewords is driven by the d. table and the c + #(C ) - 1 table while retrieving the correct d 3 3 pattern is driven by the s . - c table and pointer table. 3 s. Dl (initialize) J *- 1 D2 (Identify codeword) The first CLEN(j) bits of F' is put into TEMPI, If TEMPI > UBOUND(j) then J *- J + 1 and repeats D2. R5 (Retrieve pattern) Set INDEX *- TEMPI + OFFSET(j) Output PATTERN (PTR( INDEX)) Dj+ (Continue) Remove CLEN(j) bits from F', if there is no more data left, then done. Otherwise go to Dl. 2 . Decoding Performance The average number of comparison required to decode one pattern using Algorithm D is 25 T = Z 3 P(C d ) where P(C ) = sum of probabilities of occurrence of all 2 the patterns that have code words in C , . d. 3 Since #((d.}) Z P(C ) = z P. = i j=l j i=l hence the average number of comparison T is always less than #({d.}), the number of different codeword lengths. For example, in order to decode a pattern of length n, assuming m number of comparisons, the number of memory access required to perform this can be divided into the following group: 1. Read m entries in d. table. 2. Read m entries in c + |(C, ) - 1 table. s . " d . 3. Read 1 entry in s . - c table. 3 S 3 km Read 1 entry in pointer table. 5. Read n entries in pattern table. 6. Write n entries into the output buffer. .*. Total $ of memory access required = 2m + 2n + 2. The number of shift operation required is obvious d.. And if the codeword crosses word boundary, then an extra memory read is required to fetch the next compressed word. 26 V. SIMULATION RIM Both the encoding and decoding algorithms have been written in SUE microcode and debugged using a SUE simulator program running under DOS on a PDP-ll/20. In order to do a study on the compression ratio and rate of compression and decompression, a large scale simulation run "was planned. The sample text used is a copy of a PAL-11 assembler language program source file. This file is selected because of its similarity to commercial files. Each source statement is analogous to a business record with well defined fields. The following is a description of a typical source statement : label operator operand comment e.g., START: MOV WORD, Rl ;INIT COUNTER In order to compile the set of patterns to be encoded by Huffman codes, a PL/l program has been written which does pattern recognition to come up with a set of patterns {m. }, its corresponding set of probabilities of occurrence {p.} and calculates the set of codeword lengths [Si.}. Another program was written in MACRO-11 assembler language on the PDP-11 to construct the set of codewords {c.}, build the encoding table and construct the sets {d. }, {c + #(C ) - 1}, {s. - c } and build the decoding tables. 1 ' s . d . j s . The original data is as shown in Figure A.l, Appendix A. The set of message units {m. } and the corresponding set of Huffman codewords (c.} is as shown in Figure A. 2, Appendix A. 27 Instead of compressing the whole file, the first IK bytes are compressed and the compressed data is as shown in Figure A. 3, Appendix 1. The compressed data was only ^00 bytes long, i.e., hoio of the original size. This compressed data was then inputted to the decoding routine and the decompressed (original) data is as shown in Figure A.k, Appendix A. The average time required to encode one character has been calculated to be 6.3/Lts, while decoding has been timed at a rate of 8.3ius per character. The basic requirement before compressing or decompressing a file is the presence of the necessary tables. In most large data processing and information retrieval systems (e.g., Airline Reservation, MEDLARS, etc.), the content is fairly stable over a period of time and any changes to it are all of the same nature as the existing content. Hence the construction of the tables for data compression and decompression, albeit a time consuming one, would just be an initial investment. The tables would remain effective for a large number of updatings of the data base over a long period of time before any updating of the tables is necessary to maintain efficiency. Obviously, the data compression-decompression unit can handle files with different contents if the tables for the different contents are known to the unit. The tables for the different types of files can be stored in an on-line secondary storage device. There will be an initial setup cost of swapping in the appropriate tables into the fast memory of the data compression-decompression unit before compressing or decompressing a file. However, if the data compression-decompression unit is dedicated to one type of file only, there is no reason why the tables cannot be resident 28 in the fast memory of the unit. A more detailed block diagram for such a data compression-decompression unit is given in Figure 9. From the statistics of the rate of encoding and decoding of the file used in the simulation run, and the statistics of some of the algorithm implemented in software in some of the reference articles ([2], [k], [7], [8]), it can be seen the speed of operation this firmware compression unit is comparable to using a fast big computer to do the same thing in software. However, much of this timing is dependent on the hardware— namely, the architecture of the processor, the speed of execution of the microcodes, the speed of the data bus and the speed of the memory used for tables and buffer area. It should be noted that although SUE has some attractive features, it is not exactly a general-purpose microprogrammable processor. Rather, its architecture is primarily oriented towards the implementation of its macro language. An important point demonstrated by this report is that the superior performance and yet inexpensive cost of minicomputers have made this project feasible and practical. This further manifests the possibility of isolating out other organizationally independent entities, each performing different functions, of the modern computer system— like data communication, I/O processing, compiling, etc., and implement them in minicomputers. This decentralization of computer power to decrease cost and increase system throughput is of course nothing new. In 1970, there was the Logicon 2+2 timesharing system in the market which is composed of four functionally specialized minicomputers and support up to 128 terminals. Such performance is comparable to the conventional timeshare computer system using one big fast central computer. Also, communication "front end" processors for large 29 /N K 3 •H ! o M M \< -p co co s a; 0) (i) H H in •H ,Q ci; Hh cri > 1 o •rj g ra -p w cri Ph >> fH cri T) Pi O CD o bO cd cri ra U o a) -p £ ra •H H Pi O •H co co CD f o CD R I +3 Pi -H ° fi •H D co 03 CD |H I o cri -P cri R -P •H cri £ -P 13 cri R Pi o <+H •H o w w £3 CD cri ^H *H & bO s cri o •H O R d) R ^ I O a O o H •H pq CO co H CD •H u cri & -p a CD o R O CD bO •H CD o o -P CD CO S 30 computers already exist in the market today. Indeed, instead of one big fast general-purpose computer, the nucleus of a computer system may in the future consist of a network of minicomputers, each doing its own dedicated task and cooperatively tied together. 31 LIST OF REFERENCES [1] Ash, R., Information Theory, John Wiley & Sons, New York (1965). [2] Snyderman, M. and B. Hunt, "The Myriad Virtues of Text Compaction," DATAMATION, Vol. l6, No. l6 (1970 ), pp. 36-^0. [3] deMaine, P. A. D. and B. A. Marron, "Automatic Data Compression," Comm. of ACM, Vol. 10, No. 11 (1967), pp. 711-715- [k] Ruth, S. S. and P. J. Kreutzer, "Data Compression for Large Business Files," DATAMATION, September (1972), pp. 62-66. [5] Mulford, J. E. and R. K. Ridall, "Data Compression Techniques for Economic Processing of Large Commercial Files," Proceedings of the Symposium on Information Storage and Retrieval (1971), pp. 207-215. [6] Knuth, D. E., The Art of Computer Programming, Vol. 1, Add! son-Wesley (1968). [7] Cullum, R. D., A Method for the Removal of Redundancy in Printed Text, CSL Report R-586, University of Illinois (1972). [8] Houston, G. B., "Application of Data Compaction to Computer Network," ICC '73 Conference Record, Vol. II (1973), pp. kl-2k to iH-30. [9] SUE Computer Handbook, Lockheed Electronics (1973)- 32 APPENDIX A Listings of the Simulation Run MOV #1,R0 ; p CUNj INCB PKNj > ; MOVB CLEN(R0),WORD ; ,BIN2D #ADR1,W0RD f I JSR R&rWRITF | .WORD PHN1 ; ; CMPB *17,PRN1 ; BGT PlLEN ; MOV #-4,R0 ;INIT PTR To PRINT STATS MOV TOTAL, WORD ; BR CONV l } ^TABL: MOVB TABL(R0)rPRN jSLT UP PRN BUFFER MOV TAB|_*2(R0),WOR4 ; } CONVt ,BIN2D #ADR,W0RD ;BIN TO ASCII DEC } JSR RSfWRITF. I .WORD PRN ; I CMP #P,R0 ;D0Nfc? BLE HCODE |YES ADD #4,R0 ;ADV PTR BR PTABL } PRNli .ASCII '01 ' ; ADRl: .BLKB 5 f .BYTE CR,LF » CLEN| ,BLKB 16, |CODE LENGTH TABLF I OUTPUT BUFFER TO PRINT TABL PRN« .ASCII i » f *DRt ,BLKB 5 ;5 DECIMAL DIGITS .BYTE CR,LF | TABU ,BLKW 256, |TABl HAS 128 ENTRIES }2 FIELDS PER LNTRY I ASR R4 ASR R4 ; MOV R0,R4 l ASL Rl flNDEX INTO TABL BEQ ,*10 ,YtS CONV| .BIN2D ADR, TOTAL |8IN TO ASCII DEC CLR R0 UNIT PTR TO PRINT STATS ASL (R0) |SHIFT A ADD (R1),R4 |ADD THE NUMBER IN ADD #4,R3 |ADV PTR TO DO NEXT BEQ ECCODE |YES, DONE TST TABL*6(R3) ;NEXT ENTRY IN TABL ? INCB CIEN(R4) |INCR ENTRY IN CODE LENGTH TABLE NCLENi MOV TABL*2(R3) f Rl ;GET ^OCCURENCE CLR R3 ;INIT PTR TO TABL SUB #4,R2 »P«P-1 MOV R4,TABL(R0) I MOV R4,TABL(R2) | A3R R4 /ASCII CODE ASR R4 IASCII CODE OF M P MOV R3,TABL*2CR0) I MOV TABL*2(R0),TABL*2(R2) JSWAP In FREQ OF OCCURENCE MOV TABL*2(R2),R3 ;T(P) TO TEMP STORAGE ADD M,R1 ;ADV J MOV #4,Rl |R1 PTS TO 2ND ENTRY (J) P ■ 508, ;TABL SIZE IN BYTE INC TABL+2CRI) |INCR CHAR CNT ACUMf aSL Rl »RJ MULT BY 4 TO ; Figure A.l 33 pattern c0 de i 000 'Rl 0010 1 I f i i >#» 00110 ?T» 001 1 1 'N' 01000 .'E' 01001 'I' 01010 !*' 01011 )C 011000 :»• 011001 'D' 011010 ;o» 0110U ;B» 0iii00 l; 011101 ?P' 011110 S' 011111 '»' 100000 100001 100010 • M 1000110 !■' 1000111 ;?' 1001000 ?•' 1001001 '<' 1001010 1' 1001011 ;4' 1001100 'TABL' 1001101 1001110 Ji' 100H11 F' 1010000 JU' 1010001 w ' 1010010 *' 1010011 MOV • 1010100 'Ml 10101010 ! vi 10101011 [♦' 10101100 :* ■ 10101101 j i ' 10101110 ; 5 ' 1010HU 'HI 10110000 J3' 10110001 ;G' 10110010 "t 1 101100110 ;r • 10H001U J) I 101101000 If J 101101001 'CODE' 101101010 1 1 ! 101101011 ' 10110U00 ;j 101101101 [*' 10110H10 x l 101101111 .6' 101110000 ! Q ' 10H10001 :-' 1011100100 .'"' 1011100101 ;•' 10H100U0 *' 1011100111 ;*' 10111010000 10111010001 '*' 10111010010 Figure A. 2 ^ ***** sug m a crqprogrAm 900: 0000/ 02A0/ 9D2E/ &28E/ 0467/ 9875/ 28B5/ C4A4/ « 10 1 3169/ 33C4/ 8960/ 0659/ 02A9/ BABB/ 4998/ 7528/ ¥20! 9451/ F7C1/ 49B2/ 6A30/ 125C/ 5224/ 3514/ F5B5/ 930: 6682/ 9364/ O0At/ 640B/ 6BF6/ ?88A/ BE0A/ 44A3/ 940: A406/ 4093/ 49B2/ 6A17/ 8912/ C00C/ B203/ 154F/ »50t 5A4D/ 3A5D/ D181/ E244/ B019/ 01CB/ 2383/ 3CC3/ «60: A940/ 1180/ A827/ 5C93/ 2028/ F057/ ?90A/ 399E/ 970: 3918/ ED99/ E252/ 0E67/ CEB3/ BE05/ 4076/ CEB7/ 9fl0: 60A4/ 0934/ 2B80/ 72CF/ 0B0D/ A2AC/ 00CB/ 2F4D/ 990: B5C5/ 54DD/ 50A4/ D365/ 1479/ F03C/ 480C/ BE93/ 9A0: 9A8B/ C678/ 9067/ 28D0/ A09B/ 3835/ 4136/ B244/ 9B0: A28F/ 3E0A/ 4094/ C332/ CB&D/ A2AE/ B64B/ 8A44/ 9C0: A6A2/ 9CB6/ 8A0A/ 4D93/ 4233/ 8A41/ 8ED9/ 96FB/ 900: PA51/ 9A4B/ 0C81/ 6D7E/ CFU/ 57C1/ 4894/ 7480/ 9E0! C612/ 6936/ 4D42/ F120/ 0066/ 5901/ 8AA7/ 8lA7/ 9F0! 3D01/ 4702/ 3340/ A137/ 380E/ 3A90/ 6B0B/ 5011/ A00: A9A5/ F-016/ D340/ 03A6/ 4051/ C08C/ B6AA/ CCFl/ A10! ECE0/ CE59/ F17A/ 6811/ 9F24/ 4BAD/ 92B7/ 0852/ A20: A2B6/ 47B5/ f;56C/ 02B9/ 6D59/ AB64/ B8F0/ BAD3/ A30: 5E.00/ 8C04/ 9729/ 9030/ B050/ 3B40/ 08CC/ 3A94/ A40: 56C9/ 71DB/ 75A6/ 5DC2/ 4800/ CCDA/ 8CEA/ 5164/ A50: 7B«3/ 4D4B/ 3137/ 44EF/ 5139/ 9CA3/ 4282/ 48C7/ A60: 6CCF/ 1290/ 7340/ 7891/ 5A69/ 2B7D/ 852A/ 2B64/ A70: 36C0/ 232D/ A2AD/ 3497/ 1DB7/ 5A6B/ C01 1/ ABCC/ A80! 0258/ 5552/ 0033/ 4AB2/ 51DF/ 024B/ 94CE/ 9858/ A90: 2810/ 0000/ 0000/ 0000/ 0000/ 0000/ 0000/ 0000/ / , (50J/ /i 30 Y ):jl (/ / Q AI2 OR$5 5/ / P, > DM/ /$ • 12 #2 0/ /ZMjlQ D0 K* • N7/ / $Y4 + ", K/M/ /5ETH *S / / F J (P 85A620/ /" > M C2K ",6K 0/ /"6 M B3 A Y / /OK WAH / /H 6MB Y ' •/ /« G 3MJ78 M P / /)X S#S&#Q# 6*L / / NY SK-. 7XR/ /"6G5E 9 Y* 8 :S/ /a ) 00PM L: / /Vl [ &1BH LZ Q / / MK17D 09 MB HG/ / I M Z ♦ *♦ / /6#*-«U4 7Z # +1/ /RXURJ3J2QO K N X/ /( / Figure A. 3 35 ***** SUE macroproGram 900: 2020/ 2020/ 2020/ 2020/ 4p4F/ 5620/ 2020/ 2020/ / MOV / 910: 2331/ 2C52/ 3020/ 2020/ 2020/ 2020/ 2020/ 2020/ /#1,R0 / 920: 3B50/ 434C/ 454E/ 3A20/ 2049/ 4t43/ 4220/ 2020/ /jPCLEN: INCB / 930: 2050/ 524E/ 3120/ 2020/ 2020/ 2020/ 2020/ 2020/ / PRN1 / ¥401 203B/ 3B20/ 2020/ 2020/ 2020/ 204|)/ 4F56/ 4220/ / ft MOVB / «50: 2020/ 2043/ 4C45/ 4E28/ 5230/ 292C/ 574F/ 5244/ / CLEN (R0) , WORD/ 960: 2020/ 203B/ 2020/ 2020/ 2020/ 2020/ 2fc42/ 494t/ / I ,BIN/ *70: 3244/ 2020/ 2341/ 4452/ 312C/ 574F/ 5244/ 2020/ /2D *ADRl,WORD / 980: 2020/ 2020/ 3B3B/ 2020/ 2020/ 2020/ 2020/ 4A53/ / ft JS/ 990t 5220/ 2020/ 2020/ 5235/ 2C57/ 5249/ 5445/ 2020/ /R R5,WRlTE / 9A0: 2020/ 2020/ 2020/ 3B20/ 2020/ 2020/ 2020/ 202E/ / J ./ *B0: 574E/ 5244/ 2020/ 2050/ 524L/ 3120/ 2020/ 2020/ /WORD PRN1 / 9C0: 2020/ 2020/ 2020/ 203B/ 3B20/ 2020/ 20?0/ 2020/ / }', / «D0: 2043/ 4D50/ 4220/ 2020/ 2023/ 3137/ 2C50/ 524E/ / CMPB *17»PRN/ 9E0: 3120/ 2020/ 2020/ 2020/ 203B/ 2020/ 7029/ 2020/ /l I / 9F0: 2020/ 4247/ 5420/ 2020/ 2020/ 5043/ 4C45/ 4E20/ / BGT PclEN / A00: 2020/ 2020/ 2020/ 2020/ 2020/ 3B20/ 2020/ 2020/ / / / A10: 2020/ 204D/ 4F56/ 2020/ 2020/ 2023/ 2D34/ 2C52/ / MOV #-4,R/ A20: 3020/ 2020/ 2020/ 2020/ 2020/ 203B/ 494E/ 4954/ /0 |INIT/ A30I 2050/ 5452/ 2054/ 4F20/ 5052/ 494F/ 5420/ 5354/ / PTR TO PRINT ST/ A40I 4154/ 5320/ 2020/ 2020/ 2020/ 204D/ 4F56/ 2020/ /ATS MOV / *50l 2020/ 2054/ 4F54/ 414C/ 2C57/ 4F52/ 4420/ 2020/ / TOTAL, WORD / A60: 2020/ 203B/ 2020/ 2020/ 2020/ 2020/ 4252/ 2020/ / I BR / A70I 2020/ 2020/ 434F/ 4E56/ 2020/ 2020/ 2222/ 2020/ / CONV / A80: 2020/ 2020/ 3B3B/ 5054/ 4142/ 4C3A/ 2020/ 4D4F/ / ;iPTABLt MO/ A90I 5642/ 2020/ 2020/ 5441/ 424C/ 2852/ 3029/ 2C50/ /VB TABl(R0),P/ Figure A.k (Continued on next page) 36 AA0| 524E.V 2020/ 2020/ 3B53/ 4554/ 2055/ 5020/ 5052/ *B0; 4120/ 4255/ 4646/ 4552/ 2020/ 2020/ 2020/ 2020/ AC0I 4D4F/ 5620/ 2020/ 2020/ 5441/ 424C/ 2B32/ 2852/ AD0I 3029/ 2C57/ 4F52/ 3420/ 3B3B/ 434F/ 4E56/ 3A20/ AE0t 2020/ 2L42/ 494E/ 3244/ 2020/ 2341/ 4452/ 2C57/ AF0I 4F52/ 4420/ 2020/ 2020/ 2020/ 3B42/ 494E/ 2054/ B00: 4F20/ 4153/ 4349/ 4920/ 4445/ 433B/ 2020/ 2020/ »10I 2020/ 2020/ 4A53/ 5220/ 2020/ 2020/ 5235/ 2C57/ B20J 5249/ 5445/ 2020/ 2020/ 2020/ 2020/ 3B20/ 2020/ »30» 2020/ 2020/ 202t/ 574F/ 5244/ 2020/ 2050/ 524E/ B40I 2020/ 2020/ 2020/ 2020/ 2020/ 2020/ 203B/ 3B20/ »50» 2020/ 2020/ 2020/ 2043/ 4D50/ 2020/ 2020/ 2023/ B60I 502C/ 5230/ 2020/ 2020/ 2020/ 2020/ 2020/ 203B/ H70I 444FV 4E45/ 3F20/ 2020/ 2020/ 2020/ 2042/ 4C4b/ BB0J 2020/ 2020/ 2048/ 434F/ 4445/ 2020/ 2020/ 2020/ B90I 2020/ 2020/ 203B/ 5945/ 5320/ 2020/ 2020/ 2020/ BA0I 2041/ 4444/ 2020/ 2020/ 2023/ 342C/ 5230/ 2020/ »B0l 2020/ 2020/ 2020/ 2020/ 203B/ 4144/ 5620/ 5054/ »C0l 5220/ 2020/ 2020/ 2020/ 2042/ 5220/ 2020/ 2020/ BD0I 2050/ 5441/ 424C/ 2020/ 2020/ 2020/ 2020/ 2020/ BE0I 203B/ 5052/ 4E31/ 3A20/ 2020/ 2E4J/ 5343/ 4949/ BF0I 2020/ 2730/ 3A20/ 2027/ 2020/ 2020/ 2020/ 2020/ C00I 2020/ 3B41/ 4452/ 313A/ 2020/ 202E/ 424C/ 4B42/ CJ0I 2020/ 2035/ 2020/ 2020/ 2020/ 2020/ 2020/ 2020/ C20I 2020/ 203B/ 2020/ 2020/ 2020/ 2020/ 2E42/ 5954/ C30I 4520/ 2020/ 4352/ 2C4C/ 4620/ 2020/ 2020/ 2020/ C40| 2020/ 2020/ 3B43/ 4C45/ 4E3A/ 2020/ 202E/ 424C/ C50I 4B42/ 2020/ 2031/ 362E/ 2020/ 2020/ 2020/ 2020/ C60I 2020/ 2020/ 203B/ 434F/ 4445/ 204C/ 454E/ 4754/ /RN |3ET UP PR/ /N BUFFER / /MOV TABL*2(R/ /0),WOR4 HCONVi / / .BIN2D i *adr,w/ /ORD JBIN T/ /O ASCII Drc> / / J8R R5 f W/ /RITF ; / / .WORD PRN/ / n / / CMP */ /P,R0 i/ /DONE? BLE/ / HCODF / / IYES / / ADD #4 # R0 / / |ADV PT/ /R BR / / PTABL / / IPRNli , ,ascii/ / «0| • / / MDRii .BLKB/ / 5 / / 1 ,BYT/ /E CR,LF / / ;cieni ,BL/ /KB 16, / / ICODE LEN6T/ Figure A.k (Continued on next page) 37 C70I 4820/ 5441/ 424C/ 453B/ 2020/ 4F55/ 5450/ 5554/ /H TABLE) OUTPUT/ C80! 2042/ 5546/ 4645/ 5220/ 544F/ 2050/ 5249/ 4E54/ / BUFFER TO PRINT/ t90i 2054/ 4142/ 4C50/ 524E/ 3A20/ 2020/ 202E/ 4153/ / TABLPRNj ,AS/ CA0| 434g/ 4920/ 2027/ 2020/ 2027/ 2020/ 2020/ 2020/ /CII ' • / CB0| 2020/ 2020/ 203B/ 4144/ 523A/ 2020/ 2020/ 2F42/ / |AOR» .8/ CC0I 4C4B/ 4220/ 2020/ 3520/ 2020/ 2020/ 2020/ 2020/ /LKB 5 / CD0I 2020/ 2020/ 2020/ 3B35/ 2044/ 4543/ 4940/ 414C/ / ;5 DECIMAL/ CE0I 2044/ 4947/ 4954/ 5320/ 2020/ 2020/ 2020/ 202E/ / DIGITS ,/ CF0I 4259/ 5445/ 2020/ 2043/ 522C/ 4C46/ 2020/ 2020/ /BYTE CR,LF / 0001 0000/ 0000/ 0000/ 0000/ 0000/ 0000/ 0000/ 0000/ / / Figure A.k- (Cont. ) APPENDIX B Firmware Listings for Encoding and Decoding Routines 38 ENCODF MACRO V004A PAGE 1 1 2 000000 3 4 5 6 7 8 9 10 ii 12 13 14 15 16 17 18 19 20 00000 21 00000 22 23 00001 24 00001 25 26 00002 27 28 00003 29 00003 30 *1 00004 32 ?3 00005 34 35 00006 36 00006 37 38 00007 ?• 00007 40 41 00010 .MCALL HELLO HELLO ENCODE ROUTIN REGI I I ; ; ; ; i i ; i i NtXTl HAITI I NtXTLl fe TO STER R0 ■ Rl ■ R2 ■ R3 ■ R4 ■ R5 ■ R6 « R7 ■ R8 ■ R9 ■ RA » RB ■ 00 HUFFMAN ENCODING FROM A GIVEN CODE TABLE SETUP • TNPUT BUFFER PTR - 1 OUTPUT BUFFER PTR - 1 1 WORD OF ENCODED TEXT BASE REG FOR 2ND OR HIGHER LEVEL ENTRIES CURRENT CHAR LOOKAHEAD CHAR BASE REG FOR 1ST LEVEL ENTRIES LAST WORK WORK ADDR NEXT LINK STORAGE STORAGE OF LAST ENTRY AVAILABLE BIT POSITION IN ENCODED WORD 3PC READB,ARITH,ADD,C,X0 LIT 0001,XWRITE,YWRITE A#$ ; LOC STAIDXFYM21ZW0 f 000 119000P3ED1050 BAN ABRT,TRAN,Y,X5 YA,XNRITEfS I LOC STACDXFYM21ZW0 | 001 30A00501F50040 SEQ Y.BAR,X4,YR,XWRlTE#S > LOC STACDXFYM21ZW0 | 002 00500400FFF040 JCT ONES, DONE, X.BAR X4,XWRITErYWRITE T,$ I LOC STACDXFYM21ZW0 } 003 50000403450060 SPC SLAO,S I LOC STACDXFYM21ZW0 I 004 10F00F0387F000 SPC SLAO,S I LOC STACDXFYM21ZW0 I 005 10F00F0387F000 SPC READ, ARITH, ADD. C X6,YT,YWRITE A,$ | LOC STACDXFYM21ZW0 } 006 11900602F9F010 SEQ TRAN,Y,X9 LIT 0FFF,XWRITE,S ; LOC STACDXFYM21ZW0 | 007 00A009038FF040 jREAD NEXT CHAR |$A,R0»R0+1 |SR*CURRENT CHAR |R5»$A |0NES,R4b/SR ;ST,R4«/R4 I BAW ABRT,S |ST»4*»T »READ LINK |SA«ST*R6 |R9"0FFF I ;SR«LINK 39 tNCODF MACRO V004A PAGL 1* 4? 44 00011 00011 45 46 47 00012 00012 48 49 b0 00013 00013 52 t>3 00014 00014 54 55 *6 00015 00015 57 58 00016 59 «0 ?1 00017 00017 62 ?3 00020 64 65 66 00021 00021 67 6fl 00022 69 70 00023 00023 72 73 74 00024 00024 ; ; J LOC STACDXFYM21ZW0 ; 008 30F0OF03r50000 SCO NAND,X9 ; »9, $T =/ ( SR.rq) YR,XWPITLf YWRITE T,$ > ; LOC STACDXFYM21ZWU ; 009 O0400gpifc)pFF0fi0 JBF Tl 1, NOtDD,SKPjMP ; T 1 1 S : NO CODF. NEXT TRAN,Y f YT,$ J0N£S=ST ; LOC STACnxFYM2lZW0 ; 0OA 60A02F O2R0F0O0 SFQ T«AN,Y,XA,YA,XWRlTE >RA,$A»$A YWRITf A,S • J LOC STACDXFYM2UW0 ; 00B O0A00AO1FFF050 StQ TRAN,Y,X7,YR,XWRlTE ;R7,$A««R YWRITt A,S ; ; LOC STACDXFYM21ZW0 ; 00C 30A0PI700FFF050 JCT ONtS,FNC0O ;LINK NULL: EMCOD NEXT TRAN f X, X5,YWRITF A,S ;$A»H5 ; LOC STACDXFYM21ZWU ; 000 50F00503429010 SEQ TRAN,Y,X0,YA,XWRlTL,S ;R0«$A ; LOC STACDXFYM2lZwO I 0OE O0A0O001FFF040 ; NOCODl SPC REAOB,ARITH,AOO.C »RtAD NFXT CHAR X5,LIT 0001, XWRITE, YWRITE A,$ /*A,R5»R5M I LOC STACDXFYM21ZW0 I 00F U900503ED1050 SEQ 0R,X9,LIT 0800, XWRITE, $ ;R9«R9*0800 ; LOC STAC0XFYM21ZWCJ ; 010 00E009O3RF8040 BAN ABRT, X.BAR, X9 ; IR-LOOKAHE AD CHAR XWRITE,* ;R9«/R9 ; LOC STACOXFYM21ZW0 I 011 30000903F50040 3EQ Y.BAK,X8,YR,XWRtTE,S / ONf-.S, R8-/SR I LOC STACDXFYM21ZW0 I 012 005008O0FFF040 JCT ONES, ENCOD, X.BAR |RB»/R8 X8,XWRITF,$ | > LOC STACPXFYM21ZW0 ; 013 50000803429040 SEQ ARITH,SUB,C,X8 ;RB-R8-XI20» LIT 0020,XWRITfc,S , tNCODE MACRO V&04A PAfiL 1* ho 75 h 00025 00025 7fl 79 80 30026 0002fi «1 82 83 00027 00027 84 85 66 00030 00030 87 Bfl 00031 B9 90 00032 »1 00032 92 93 00033 94 95 00034 96 97 00035 98 99 00036 102 101 10; 1 0037 ! 0037 10^ 104 \ 0040 ; S2I SEQ YWRITE A SPC YR,XWRIT SEQ YA,XWRIT SEQ YWRITE I. BAW SEQ YWRITE T BRN SEQ JCF SPC SPC X3,YT,YW 105 \ NtXTCl BAW I LOC STACPXF YM2lZwO 014 01600803D2F040 *JD,X8,LIT 001F % LOC STACDXFYM2UWU 01b 00B00803C1F010 READB,TRAN,Y,X4 LOC STACDXFYM21ZW0 016 10A00400FDF040 RITH,ADD,C,X9 ,YWRITF A,$ LOC STACUXFYM21ZW0 017 01900901FFF050 RAN, Y, LIT 00PID OP,$ LOC STACDXFYM21ZW0 018 00A00F03FFn030 BRT,S LOC STACDXFYM21ZW0 019 30F00F03F50000 ,BAR,ALUBAR,YR S LOC STAC0XFYM21ZW0 01A 00501F00FFF020 NCOD,SKIP,$ LOC STACDXFYM21ZW0 01B 20F03F03C29000 ,BAR,YT,YWRITC T,S LOC STACDXFYM21ZW0 01C 00500F02FFF020 00PF,S2,$ LOC STACDXFYM21ZW0 01D 40F00F0381D000 SLAO f $ LOC STACDXFYM21ZW0 01E 10F00F0387F000 EAD,ARITH,ADD,C ITE A,$ LOC STACDXFYM21ZW0 01F 11900302F9F010 BRTf $ LOC STACDXFYM21ZW0 020 30F00F03F50000 ;SA»R8,001F ;R4»$R(L0f)KAHEAn CHAR) I ;$A,R9»$A*R9 |E0-3«000D ;$R«HASH BUCKET ;$T»/$R |SKIP NEXT IF NOT ALL I'S )HASH BUCKET NULL, FNCOD N EXT ;$T*/$T |ST»8*$T »READ CLENICHAR |SA«R3*$T ;SR«CLtNJCHAR Ill ENCODE M*C«0 V004A PAGE 1+ 106 004] 107 i08 0042 109 0042 ; U0 111 0043 112 0043 ; 113 114 0044 115 0044 ; 116 117 004b US 0045 CHAIN! 119 120 0046 1 121 122 0047 123 0047 I 124 125 0050 I 126 0050 127 l2B 0051 129 0051 1 ENCODl 130 131 0052 f 32 0052 1 133 (34 0053 135 0053 1 W 0054 1 136 0054 SEQ EQUIV,ALUSKP,X4,YR, S ; ALU1«/ (R4. XOR. $R) ; LOC STACDXFYM21ZWU I 021 PI0902400FFF000 B*N CHAIN, SKIP,TRAN.Y,X8 jDIFFERS; CHAIN DOWN LIT 000fi,XI*RITt,S JR8-0006 t LOC STACDXFYM21ZW0 ; 022 20A03803E26040 BRN NFXTL,TRAN,Y |R8«$A X8,YA,XWRITF_,S ; I LOC STACDXFYM21ZW0 I 023 ?0A00801C07040 SPC READ, ARITH, ADD. C /$A«R8*2 X8,LIT 0002, YWRITE A,s /READ NEXT LtVtL PTR } LOC STACDXFYM2UW0 I 024 11900803F92010 SPC READ, ARITH,ADD,C I SA»$A*R8 (000fi) X8,YA, YWRITE A,$ >READ CHAIN I LOC STACDXFYM21ZWO t 025 HQ006P1F9F010 BAN ARRT,* ;SR«CHAIN J LOC STACDXFYM21ZW0 ; 026 30F00F03F50000 SPC read, y, bar, aiuskp »sa»$r YR,YWRITE A,S ; ; LOC STACDXFYM21ZW0 I 027 10502F00F9F010 BRN NEXTC»SKIP jSAa/SA Y,BAR,YA, YWRITE A,S > I LOC STACDXFYM21ZW0 | 028 20503F01C20010 SPC READ, ARITH, ADD, C |*A,RA»RA*2 XA,LIT 0002, XWRITE, YWRITE A,$ |READ CODE I LOC STACDXFYM21ZW0 I 029 11900A03E92050 SEQ AND, X7, LIT F000 |»T"R7,F000 YWRITE T,$ > t LOC STACDXFYM21ZN0 f 02A 00B007037FF020 SEQ TRAN,Y,LIT 000C |E0-3«000C YWRITE LOOP,! , I LOC STACDXFYM21ZW0 ) 02B 00A00F03EFC030 SEQ TRAN,Y,X9 |R9«000F LIT 000F,XWRITE",S ; I LOC STACDXFYM21ZW0 ; 02C 00A00903EFF040 k2 fcNCODF MACHO V304A PAGF X* 139 140 0055 141 142 *)056 143 144 00t>7 14t) 146 147 148 149 150 151 152 153 154 155 156 157 0060 156 006PI 159 160 0061 161 0061 162 163 0062 164 0062 165 166 0063 167 0063 168 169 0064 170 0064 171 172 0065 173 0065 174 175 i 3066 176 1 3066 S4: JCF L00PF,S4,$ | ; LOC STACDXFYM21ZWQ I 020 40F0PIFPi3fl2D000 ; SPC SLLC f S , ; LOC STACDXFYM21ZW0 ; 02E 10F00FP3R7F000 i BAW ARKT,$ ;$R=CODL ; LOC STACDXFYM21ZW0 ; k)2F 30F0f(H^3rbP000 i ) ) ROUTINt TO ENTER A COPE WORD INTO THE L^CODFD TFXT STREAM I RFGISTFR SLTUP - ; $R ■ HUFFMAN CODE (RIGHT JUSTIFIED) i $T ■ CODP UFNGTH - 1 ' «l "OUTPUT BUFFER CURSOR (FOR ENCODED TEXT) I R2 ■ CURRENT ENCODED TEXT WORD ; R9 » X • PI0PIF • > RB ■ CURRFNT AVAILABLE HIT POSITION IN R2 ; ; Sf-Q • ARITH,SUR,t,XP ;RD,$T»Rb-$T YT, XWRITErYWRIIF T,$ ; J LOC STACDXFYH21ZWU ; 030 01600B02FFF060 ; SEQ ARITH,DEC,C ;RB«RR-1 XB,XWRITE,S , ( LOC STACDXFYM21ZW0 I 031 0JF00B03FFF040 JBT T15,XWDB,SKPJMP ;E0-3=ST, T15«1|S«XWDB NEX T TRAN t Y,YT,YWRITE LOOP.S , ; LOC STACDXFYM21ZW0 t 032 70A02F02F40030 ; JCF 0NES,SHW,SKPJMP ;$T»SR, RB«-ljS.RITE TRAN f Y,YR,YWRITE T,$ ; f LOC STACDXFYM21ZW0 ; 033 40A02F00436020 B«N RITF |S.RITE CLEAR, YWRITE A,S ;$A«0 » LOC STACDXFYM21ZW0 J 034 20300F03C4B010 SF.Q TRAN,Y,XB,LIT 000F |RB«000F XWRITE,$ J f LOC STACDXFYM21ZW0 I 035 00A00B03EFF040 I SHW « J CF E03S,SHFL,SKPJMP jSA-RB, E03»0!S.SHFL NEXT TRAN t X,XB»YWRITE A,S , I LOC STACDXFYM21ZW0 ENCODE MACRO V004A PAGE !♦ ^3 177 178 179 0067 0067 1S0 181 0070 182 183 0071 184 185 [86 0072 0072 187 188 189 0073 0073 190 191 192 0074 0074 193 [94 0075 195 [96 0076 197 196 [99 9977 9977 200 201 0100 202 203 0101 204 205 0102 206 207 208 0103 0103 I SHFRl I ; i SHFLl Sit XWDBt ; i 331 / 036 40F02B0393B010 SPC RfrADB,ARlTH,ADD.C,X0 LIT 0001,XWRITE,YWRITF A,S LOC STACDXFYM212WO 037 1190000JED1050 JCF SPC BRN YT,XWRIT LOOPF»SHFRr$ tOC STACDXFYM21ZW0 038 40F00F03838000 SRLCf J UOC STACDXFYM21ZW0 039 10F00FB3F7F000 AIT1,SKIP,EX0R,X2 LOC STACDXFYM212W0 03A 20603202C01040 SEQ YA,YWRI SPC LIT 0001 JCF SPC BRN W YT,XWRITE SEQ SEQ JCF ARITH,SUB,C,X9 TE LOOP,* LOC STACDXFYM21ZW0 03B 01600901FFF030 EADB,ARITH,ADD.C,X0 XWRITErYWRlTE A,S LOC STACDXFYM21ZW0 03C 11900003ED1050 LOOPF,SL,S LOC STACDXFYM21ZW0 03D 40F00F03«3D000 3LL0,S LOC STACDXFYM21ZW0 03E 10F00F03A7F000 AITlrSKIP,EX0R,X2 9% LOC STAC0XFYM21ZW0 03F 20603202C01040 RAN,X,X9,YWRITE A,l LOC STACDXFYM21ZW0 040 00F00903FFF010 RAN,Y,YR,YWRITE T#I LOC STAC0XFYM21ZW0 041 00A00F00FFF020 L00PF»S3, I LOC STACDXFYM21ZW0 042 40F00F03842000 fREAD NCXT CHAR /$A,R0«Rtf+i ;R2»R2,X0R.ST ;E0«3«R9-$A I /READ NEXT CHAR |SA,R0«R0*1 |R2bR2,X0R.IT |SA»R9 ;»T«SR (CODE) SPC SRIC,AND,XB YA,XWRITEr$ ;SRLC# RB«RB,$A I tNCODF MACRO VC04A PAGE 1* kk 209 210 0104 211 212 213 0105 0105 214 2lb 216 0106 0106 217 218 0107 219 220 0110 221 222 0111 223 224 225 0112 0112 226 227 0113 228 229 230 0114 0114 231 232 233 0115 0115 234 235 0116 236 237 0117 238 239 0120 ; Sb: SFQ SEQ LIT 8000 SEQ YWRITE JCF SPC SEQ SEQ YWRITE ; RITE! SEQ SPC IOC STACDXFYM21ZW0 043 10B00B01F7F040 RAN t Y,X9,YT,XWRlTE,S IOC STACDXFYM21ZW0 044 00A00902FFF040 TRAN»Y,SETC , YinRITF T,S LOC STACDXFYM21ZW0 045 00A1HF0378F0P0 ARITH,X,C,XR 00P,$ LOC STACDXFYM21ZW0 046 01PI00BPI3FFF030 00PF,S5,$ LOC STACDXFYM21ZW0 047 40F00F0J847000 RAO f $ LOC STACDXFYH21ZW0 048 10F00F03C7F000 ND,X9,YT, YWRITF A,$ LOC STACDXFYM21ZW0 049 00B009PI2FFF010 ASK,X,X9,YT S LOC STACDXFYM21ZW0 04A 00700902FFF020 X0R,X2,YT f YWRlTE T,S LOC STACDXFYM21ZW0 04B 00600202FFF020 RITE, IRAN, Y,X2 YA,XwRITEr$ LOC 04C SEQ LIT 0002 BRN BAH I DONEJABRTI STACDXFYM21ZW0 10A00201FAF040 RITH,ADD.C,X1 XWRITE, YWRITE A,$ LOC STACDXFYM21ZW0 04D 01900103EF2050 FXT,$ LOC 04E 'III* 04F STACDXFYM21ZW0 20F00F03C00000 STACDXFYM21ZW0 30F00F03F50000 )R9»$T * ST-8000, CRYS'l ;F.0-3»RR*i ;$A«R9,ST ;$T»R9,/$T i »$T«R2,X0R.$T /WRITE ENCODED WORD |R2'SA ;SA,R1«R1*2 SFQ jNO-OP FOR DUMMY LABELS tNCOOE MACRO V004A PARE !♦ 240 241 0121 .ENDPM ; IOC STACDXFYM21ZW0 ; 050 00F00Ffl3FFF000 k6 ENCODE MACRO V004A PARE 1* SYMBOL TABLE A i 000001 ABORT i i 000007 ABRT chain 000045 CLABFF" • 000010 CLRLINF« Cset « 000005 CVTOL1' > 000004 DONE encod 000051 L0.3 i ■ 000000 E03S ■ t07S • 000012 L07S2 i ■ 000016 EllS « t-12,151 000003 E14S . i 000014 ElbS ■ U,7 ■ 000001 £-8,11 ' i 000002 HLTFf « INTPERi 000003 INTPNDi ' 000001 LOOP « LOOPF ■ 000010 LPKEY i > 000002 NFXT NEXTC 000040 NEXTL 000007 NE13.1- NOCOD 000017 NZTOLi' > 000005 ONES ■ READ « 00001 1 NEADB < i 000015 RITE «00S « 000002 SEHFF ' • 000006 SHfL SHFR 000070 SHW 000066 SL SLAO ■ 100007 SLLC i » 100067 SLLL • SLLO ■ 100047 SWAO i ■ 100107 SRLC • SRLL ■ 100127 SRLO i i 100147 S2 S3 000102 S4 000055 S5 T ■ 000002 TA C > 000012 TB « TC " 000014 TD t 000015 TF TF 000017 T0 s > 000000 Tl ■ T10 ■ 000012 Til i 000013 Tl2 » T13 " 000015 T14 > 000016 T15 * T2 ■ 000002 T3 i > 000003 T4 ■ T5 ■ 000005 T6 ■ 000006 T7 T8 « 000010 T9 i 000011 VSET ■ *AIT1 000001 WRITE i i 000012 WRITES* XWDB 000100 YONES • i 000000 SAF « *CF ■ 000000 $CH i • 000002 SCODL *C0 ■ 000002 SCI SDF « i 000000 SC2 ■ »C3 000000 i 000000 SFF •high ■ 000746RG 002 SLCC • > 000120 SLOCUS* *L1F ■ 000017 SL2F i > 000017 SMF ■ JMSTOR" 000402 $NTRD « i 000001 SOPTS ■ •PASS2" 000000 $PTR • > 000122 SSF » *SH ■ 100007 STABLE 000000RG 003 STAF * STBSIZ" 000377 $TF i 000000 SWF ■ *XF ■ 000017 SYF « ■ 000003 $ZF » *.» - 000000 S,2 « > 000005 $.i « . ABS, 000121 000 000000 001 SCODEX 003014 002 •TABLX 000400 003 000120 000001 000120 000011 000(7113 000017 000000 000003 000000 000003 000004 000113 000073 000075 100027 100167 000035 000107 000013 000016 000001 000014 000017 000004 000007 000006 000016 000017 000000RG 000000 000000 000001 000017 000000 000000 000017 000000 000000 000000 90? ERRORS DETECTEDI FREE COREI 9156, WORDS rSYKENCODE DECODE MACRO V004A PACE 1 J +7 2 3 4 i> b 7 B 9 10 11 12 13 14 15 16 17 18 00000 19 20 0000[» 21 00000 22 23 00001 24 00001 2b 26 00002 27 0000? 2B 29 00003 JH Jl 00004 32 00004 33 34 00005 35 00005 36 i7 00006 38 00006 39 «0 00007 41 00007 ROUTINE TO DO HUFFMAN DECODING RFGISTER SET UP - R0 ■ PTR TO ENCODED TFXT DUFFER (CAN'T DE 0) Rl ■ PTR TO DFCODED (ORIGINAL) TE*T BUFFER R2 » * OF BITS REMAIN IN CURRENT tNCODtn WORD R3 ■ X'000F' W4 ■ CODE LENGTH H5 ■ CODE R6 ■ BASE PTR TO 4 LISTS FOR DECODING R7 • BASF PTR TO PATTFRN TABLE (DICTIONARY) KB ■ WORK RFGISTER R9 ■ WORK RFGISTER RA ■ LISTS' INDEX I WB ■ CUWRFNT WOUD OF FNCODEO TLXT NbYTtl .MCALL HELLO HFLLO DCCODF SPC READ TRAN,X,X0,YWRI!P a,S / LOC STACDXFYM2lZwO ; 000 10FU0003F9F010 SEO T W AN.V,LIT 0010 XWRTTE,X2,S ; LOC STA10XFYM21ZWU ; 001 C10A00203D1F040 SCQ TRAN,Y,LIT 000F XWRITE»X3»S J LOC STACDXF YM21ZW0 ; 002 00A00J03E* H040 BAK SPC AHRT,$ J LOC STACnxrYH2lZw0 ; 003 30F00F03Ft)0000 RL'ADB, T"AN,Y,YR XWRITE,XB,S ; LOC STACDXFYM21ZW0 ; 004 10A00B00FDF040 SEQ TRAN,X,X6 YWRITF A,S ; LOC STACDXFYM21ZW0 I 005 00F00603F* F010 BAW ABRTfCLFAR XWRITE,X5,S ; LOC STACDXFYM21ZW0 ; 006 30300S03Fb0040 SEQ TRAN,Y,YH XWRITEr X4,YWKITE A,S ; LOC STACDXFYM21ZW0 > 007 00A00400FFF050 ; jDECODL |COMPRfSSC D Ti XT ) INI T READ J *A«R0 >f?2«00in > ;R3»000F >$R»1ST COMPRf Sstn xoi'D ;RB»JR |SA»R6 ; ;SR»CODE LENGTH ;R5»0 >R4,$A«$R(cnDE LENGTH) ; kQ DECOOF MACHO V004A PAGE I* 4 2 43 44 000 1 Pi 0001? 45 46 00011 47 48 49 00012 00012 60 52 00013 00013 53 S4 55 00014 00014 56 57 58 00015 00015 59 60 ?1 00016 00016 62 63 *< 00017 00017 65 66 00020 67 6S 59 00021 00021 7 00022 72 73 00023 00023 74 CHECK! SEQ ARITH,SUB,C f$T«R2-$A X2,YA,YWRITF T,S ; ; LOC STACDXFYM21ZWU f 008 01600201FFF020 > JBT Tlb,XWpB,SKPjMP,S } T 15» 1 : S«XwDB NEXT ; LOC STACDXFYM2UWU ; 009 70F02F03F14000 ; SEQ TRAN,Y,YT >R2*$T XWRITt,X2»S ; ; LOC STACDXFYM212W0 } 00A 00A00202FFF040 I SEU ARITH,SUB,C |E0-3«R3-$A X3,YA,YWRITF LOOP,S ; } LOC STACDXFYM21ZW0 ,* 00B 01600301FFF030 I SCO ARITH,ADD,C ;$A«R6*16 X6,LIT 0010,YWRITE A,$ I I LOC STACDXFYM21ZW0 ; 00C 01900603D1F010 ; SPC READ#ARITH,ADD,C | INIT Rfc'AO XA,YA,YWRITE A,$ ;Sa*$A*Ra ; LOC STACDXFYM21ZW0 I 00D 11900A01F9F010 ; 3EQ AR1TH,ADD,C j$a«$A*Ra XA,YA,YWRITF A,$ ; ; LOC STACDXFYM21ZW0 t 00E PI1900A01FFF010 ; SEQ TRAN,X,CLCV |ST«RB XB,YWRITE T,* ; ; LOC STACDXFYM21ZW0 I 00F 00F20B03FFF020 I Si: SPC SLAO,S ;$T»2*$T ; LOC STACDXFYM21ZW0 J 010 10F00F0387F000 I JCF L00PF,S1, ARITH,SKPJMP | R5*2*R5*C YIN SHLX t CfENCIN,Xb f XWRITE#$ i I LOC STACDXFYM21ZW0 I 011 41C12503810040 BRN NEXTL/S IS«NEXTL NfcXT } LOC STACDXFYM21ZW0 t 012 20F00F03C28000 BAN ARRT^TRAN.Y > YT,XWRITEfXB,$ ;RB«$T f LOC STACDXFYM21ZW0 ; 013 30A00B02F50040 49 DECODE MACRO V004A PAGE 1+ 75 00024 76 00024 XwDl 77 78 00025 ; 70 80 00026 Bl 00026 i 82 «3 m*Z7 B4 00027 i 85 B6 00030 87 000JP» I BR »9 PI0031 90 00031 J 91 W? 00032 93 00032 ; 94 95 00033 ; 321 96 97 00034 98 00034 ; 99 100 0035 RCTi 101 102 0036 ; 103 104 0037 i 105 0037 106 107 0040 i SPC READ, ARITH, ADD, C jlNIT READ(NLXT C TEXT) LIT 0002,X0,XWKITE,YWRITE A,S ;$A,RCl«R0*2 I LOC STACDXFYM21ZW0 ; 014 11900003E92050 3EQ X,BAR,X2 r S /0NES-/R2 I LOC STACDXFYM21ZW0 } 015 00000203EFF000 SEQ EX0R,X2,YT ; R2»R2,X0R, ST LWRITF,$ ; ; LOC STACDXFYM21ZW0 ; 016 006002PI2KFF070 JCT ONES f RCT ; ONF S" 1 l S-RCT tX0R,X2,YT,YWRITE T,S ; S I .R2, XOR, $T I LOC STACDXFYM21ZW0 I 017 506002P241D020 SEQ LX0R,X2,YT ; R2aR2, XOR. ST PWHITE f S , ; LOC STACDXFYM21ZW0 ; 018 00600202FFF070 SEO ARITH,SUB.C /C0-J*R1-*T X3,YT,YWRTTC L00P r $ ; ; LOl STACDXFYM2UW0 ; 019 01600302FFF0J0 SEU TRAN,X,CLCV |1T«RB XR,Y W RITF T,S ;CRYS«i? I LOC STACDXFYM21ZW0 I 01A ?I0F20BC13FFF020 SPC SLAO,S ;Sja2*ST I LOC STACDXFYM2lZ*0 ; 010 10F00F03R7F000 JCF L00PF,S2,ARITH,SKPJMP ; SHLX t C,FNCIN,X5,XWRlTE»S ; I LOC STACDXFYM21ZW0 I 01C 41C12503R1H040 BAH ABRT,S ;SH.C TEXT J LOC STACDXFYM21ZW0 ) 01D 30F00F03F50000 SEQ Y,BAR,XB f YR,XWRllE»$ /ONES,RB«/$R I LOC STACDXFYM21ZW0 ; 01E 00500B00FFF040 JCT ONES, DONfc,SKPJMP »ST,RB»/RB X,BAR,XB,XWRITL#YWRITE T,S ; / LOC STACDXFYM21ZW0 ; 01F 50002B03450060 SEQ ARITH,ADD f C,X6 >SA»R6M6 DECODE MACRO V004A PAGE !♦ 50 108 0CI4P 109 110 0341 111 0041 ; 112 113 0042 114 0042 ; 115 1 16 0043 1 1 7 0043 i lie 1 19 0044 120 0044 t 121 122 0045 t Si: 123 i24 0046 (25 0046 1 126 (27 0047 126 0047 ; 129 130 0050 131 0050 i NEX 132 (33 0051 (34 0051 1 135 (36 0052 (37 0052 ; 138 139 0053 140 0053 ; LIT 0010,YWRITt A,S ; LOC STACDXFYM212W0 ) 020 0190060JP1P010 SPC READ, ARITH, ADD. C XA,YA,YWRnF A,$ ; LOC STACDXFYM21ZW0 ) 021 11900A01T9F010 SFQ ARITH,ADD,C XA,YA,YWRITE A,S ) LOC STACDXFYM21ZW0 ; 022 01900A01FFF010 SFQ ARITH,ADD,C,X2 LIT 00!0,XWRITE#$ I LOC STACDXFYM21ZW0 ; 023 01900203DIF040 SEQ AR1TH,DFC.C,X2 YWRITE LOOP f $ I LOC STACDXFYM21ZW0 J 024 01F00203FFF030 SPC SLAO,S ; LOC STACDXFYM21ZW0 ; 025 10F00F0387F000 JCF L00PF,S3 r ARnH,SKPjMP SHLX f C,ENCIN r Xb,XWRlTE,$ ; LOC STACDXFYM21ZW0 ; 026 41C1250J825040 BAW ABRTrTRAN.Y YT,XB,XWRlTEr« | LOC STACDXFYM21ZW0 I 027 30A00B02F50040 TLJ SEQ ARITH,SUB,C X5,YR, YWRITE T,S ; LOC STACDXFYM21ZW0 I 028 01600500FFF020 JBT T15,FND, Y.BAR YT f SKPJMp,$ ; LOC STACDXFYM21ZW0 t 029 70502F02F31000 JCT ONES,FND SFTC,SKPJMP,$ ; LOC STACDXFYM21ZW0 | 02A 50F12F03431000 SPC READB,ARITH,X.C ENCIN,XA,XWRITE#YWRITE A,S | LOC STACDXFYM21ZW0 I 02B 11010A03FDF050 ;$A»$A*RA ; ?$Aa$A+RA J ;R2«R2*0010 ; ;F0-3«R2-1 |$R»C(MJ)+#C(J)-1 ; ;$T«R5-$R I |T15"1 |3»FN0 NEXT |ONES»/ST J$T«0JS«rND NFXJ |CRYS»1 IINIT READB |SA p RA«RA*1 51 DECODE MACRO V004A PAGE 1* 141 142 0054 143 0054 I 144 145 0055 146 0055 ) 147 148 0056 I 149 150 0057 151 0057 ; 152 153 006fl 154 006P ; 155 156 0061 157 0061 ; FNDt 156 159 0062 160 0062 ; 161 162 0063 163 0063 } 164 165 0064 ) 166 167 0065 166 0065 i 169 170 0066 171 0066 ) 172 173 0067 t74 0067 ; SF.Q ARITH,ADD,C,X6 |SA»$A*R6 YA, YWRITE A,S I i LOC STACDXFYM21ZW0 ; 02C 01 LOC STACDXFYM2UW0 ; 02E 30F00F03F50000 BRN CHECK, IRAN, Y iS-CHFC* YR,X4,XWRITF,S |R4«$R I LOC STACDXFYM212W0 ; 02F 20A0P400C&R040 SEQ AR1TH,SUB,C,X4 >$A»R4-$T YT,YwRITE A,S I J LOC STACDXFYM21ZWO J 03U PI1600402FFF010 SEQ ARITH, ADD.C,X6 ;$A»R6*48 LIT 0030, YWRITE A,S I f LOC STACDXFYM21ZW0 ; 031 Pl$A«SA*RA YA, YWRITE A,S » } LOC STACDXFYM21ZW0 I 033 01900A01FFF010 B*H AHRTfS )SR«MJ-C(HJ) i LOC STACDXFYM21ZW0 I 034 30F00F03F5PI000 SEQ ARITH, ADD, C,X5 |$A,R5«R5+$R YR,XWRITErYWRITE A,S I | LOC STACDXFYM21ZW0 | 035 <"1900500FFF050 SEQ ARITH, ADD.C,X6 >$A«R6*fl0 LIT 0050, YWRITE A,S » I LOC STACDXFYM21ZW0 | 036 01900603D5F010 SPC RFAD, ARITH, ADD. C I I NI T READ(PTR) X5,YA, YWRITE A,$ |$A«SA*RA | LOC STACDXFYM21ZW0 DECODF MACHO V004A PAGE 1* 52 175 176 177 0070 007P! 176 179 180 0071 0071 181 182 183 0072 0072 184 185 0073 186 187 188 0074 0074 189 190 191 0075 0075 192 193 0076 194 195 ZZ77 196 197 198 0100 0100 199 200 20J 0101 0101 202 203 0102 204 205 0103 ; S4: ; AlilNl } 037 11900501F9F010 SEQ ARITH,ADD,C X5,YA, YWRITE A,S IOC STACDXFYM2lZwO 038 01900501FFF010 SEQ YWRITF L TRAN.Y,LIT 000C oop,$ SEQ X5,XWRITE,$ LOC 03A BAN ABKT,$ LOC STACDXFYM21ZW0 03B 30F00F03F50000 SEQ TRAN,Y,YR YWRITE T,S LOC STACDXFYH21ZW0 03C 00A00Fpi0rFF020 JBF T15,LEN1#SKPJMP AND, X5,YR,XWRITE, YWRITE A,S LOC STACDXFYM2UW0 03D 60802500F4R050 JCF SPC SEQ YWRITE LOOP,S LOC 040 SPC ADD,C#X7 SPC BAh 206 LOC 039 STAC0XFYM21ZW0 00A00F03EFC030 RAN. Y, LIT PiFFT STACDXFYM21ZW0 CI0A005038FF040 nOPF,S4,« LOC STACDXFYM21ZW0 03E 40F00Fdi83E000 SLLC* LOC STACDXFYM21ZW0 03F 10F00F0JB7F000 RAN,Y,YT STACDXFYM21ZW0 00A00FK2FFF030 RFADB,A«ITH ,YA, YWRITE A,$ LOC 3TACDXFYM21ZW0 041 11900701FDF010 SLAO,S LOC STACDXFYM21ZW0 042 10F00FC5387F000 BRT,S LOC STACDXFYM21ZW0 043 30F00K03F50000 ;SAa$A«Rb ; ; ta-j« l tat? > |Rba0FFF J jSRaPTK >$T»$R ; |Tl5»0:S«LtMl NfXT >R5,$A«SR,Rft(2irFM |F 0-3-ST I |IIMIT RFAOB(ORIG CHAR) >$A«$A*R7 JE0-3«E0-J*1 >$R»i BYTE OF ORlG CHAR DECODE MACRO V004A PAGE !♦ 53 207 014)4 SPC WRJTEB,TRAN # Y | INIT WRITfcB 208 0104 YR,YWRITE T,8 ;$T«$R I LOC STACDXFYM21ZWO ) 044 10A00F00FEF020 209 ; 210 0105 SEQ ARITH,ADD,C,X1 ; 211 0105 LIT 000 l f . -■'n-'i f$A,Rl»Ri*l t LOC STAC0XFYM21ZW0 t 045 01900103FH050 212 ; 213 0106 BAM ABRTrS f LOC STACDXFYM21ZWU ; 046 30F00F03F50000 1 214 t 215 0107 JCF LOOPFrAGIN,$ 1 LOC STAC0XFYM21ZW0 1 047 40F00F03841000 ; 216 \ 217 0110 SEQ ARITH,ADD,C r X5 ; 218 0110 LIT 0001 r jSA, R5«R5*1 ) LOC STACDXFYM21ZW0 | 048 01900503EF10S0 219 ) 220 0111 BRN NBYTE, CLEAR, XA ;S«NBYTE 221 0111 XWRITEf $ |RA«0 I LOC STACDXFYM21ZW0 I 049 20300A03C05040 222 i 223 0112 SPC READB,S | LOC STACDXFYM21ZW0 1 04A 10F00F03FDF000 1 224 \ 225 0113 UNU SPC WRITEB,TRAN.X I INIT WRITES 226 0113 X5 r YWRITE T,S |$T«R5 I LOC STACDXFYM21ZW0 t 04B 10F00503FEF020 227 1 228 0114 SEQ ARITH, ADD,C,X1 1 229 0114 LIT 0001, |SA,R1«R1M | LOC STACDXFYM21ZW0 1 04C 01900103EF1050 230 t 231 0115 BAN ABRT,I | LOC STACDXFYM21ZW0 ) 04D 30F00F03F50000 1 232 1 233 0116 BRN NBYTE, CLEAR, XA )S«NBYTE 234 0H6 XWRITEr S |RA«0 t LOC STACDXFYM21ZW0 | 04E 20300A03C05040 235 1 236 0117 SPC READB,S 1 LOC STACDXFYM21ZW0 1 04F 10F00F03FOF000 1 237 1 236 0120 ABRTlDONEt SEQ,S 1 » LOC STACDXFYM21ZW0 DECODE MACRO V004A PAGE !♦ 239 012J fENDPM ' 050 0"0HWFF000 5k y> • 0ECODJ V004A Of M OL TA PAGE !♦ 3YMB A AGIN CLRUNF OONF E07S E4.7 HLTFF Ceni IPKEY ME13.1 RCT K00S SLLC 3RA0 Srlo S3 TA TO t0 Til U4 T3 T6 T9 KRITEB *AF *CODE *C2 *FT >LOCLS IMF • OPTS »SF ITAF SWF >ZF *.3 . ABS, KODEX ITABLX BLE 000001 000101 000001 000120 000012 000003 000001 000000 000113 000002 000003 000035 000002 100067 100107 100147 000045 000012 000015 000000 000013 000016 000003 000006 000011 000016 000017 000000RG 000000 000000 000001 000017 000000 000000 000017 000000 000000 000000 000121 000000 003014 000400 ABORT ■ CHECK CSET ■ E0.3 ■ E07S2 ■ E143 ■ E8,H ■ INTPER* LOOP ■ NBYTE NZTOLl« READ « SEHFF ■ SL.LL ■ SRLC • 31 S4 TB TE Tt T12 T15 T4 T7 VSET XWDB $CF 002 sr.0 SC3 JHIGH SLIF IMSTOR SPASS2 SSH STBSI7 $XF S.l 000 001 002 003 000007 000010 000005 000000 000016 000014 000002 000003 000003 000005 000005 000011 000006 100027 100167 000020 000076 000013 000016 000001 000014 000017 000004 000007 000006 000024 000000 000001 000000 000746RT, 000017 000402 000000 100007 000377 000017 000000 ABRT clabff CVTOL1 E03S EltS E153 FfJD 1NTPNO LOOPF NFXTL ONES READB 3LA0 SLLO SRLL S? T TC TF Tl0 T13 T? TS T8 WRITE yones $CH SCI snr 002 st.cc $L2F SNTRD $PTR STABLE $TF SYF S.2 000120 000010 000004 000011 000013 000017 000061 000001 000010 000050 000004 000015 100007 10004/ 10012/ 000033 000002 000014 000017 000012 000015 000002 000005 000010 000012 000000 000001 000000 000000 000120 000^1/ 000001 000122 000000RG 000000 000003 000005 0.? ERRORS DETECTFDI FREE COREI 9176, WORDS rSYKDECODE 1& %*> \^ v «*** «ft UNIVERSITY OF ILLINOIS-URBAN A 510,84 IL6R no. C002 no. 613-617(1973 Internal report / 3 0112 088401036 HHI W^i H