Commissioned by Gosteleradio

Hello and prosperity to you, All! After a long sleep I will finally deliver what I promised xx-twenty years ago ;) If anyone has already forgotten, then this “that” is nothing more than lzw algorithm in docs and examples. I won’t throw out any s-s-sorts (there’s a lot of text, but there’s little sense), I'll throw in a couple of och. simple examples on ASMA. The dockets go immediately after this letter. Here are only brief algorithms and my art. Written for demonstration purposes only, therefore completely devoid of real application. Notes on the examples: 1-data size #00-#0F 2-dictionary size 256 sequences (8 bits) 3-data length <256 bytes No 4-packing is performed on the bitstream. Brief algorithms: =========8<==Cut=Here==8<============= LZW Compression/Decompression ROUTINE LZW_COMPRESS STRING=get input character WHILE there are still input characters DO CHARACTER=get input character IF STRING+CHARACTER is in the string table THEN STRING=STRING+CHARACTER ELSE output the code for STRING add STRING+CHARACTER to the string table STRING=CHARACTER END of IF END of WHILE output the code for STRING ROUTINE LZW_DECOMPRESS read OLD_CODE output OLD_CODE WHILE there are still input characters DO read NEW_CODE IF NEW_CODE is not in the translation table THEN STRING=get translation of OLD_CODE STRING=STRING+CHARACTER ELSESTRING=get translation of NEW_CODE END of IF output STRING CHARACTER=first character in STRING add OLD_CODE+CHARACTER to the translation table OLD_CODE=NEW_CODE END of WHILE =========8<==Cut=Here==8<============= Actually the programs. Written in Storm Was not written for the purpose of demonstrating elegant code, so sorry for the crookedness ;) =========8<==Cut=Here==8<============= ;LZW algos test Dark/X-Trade'98 ;Click the sequence of unpacked ;tetrads into 8-bit codes (fixed size ;van). Very slowly... ;- COMPRESSOR ------------- CHRTB EQU #7000;Packaging Dictionary PFXTB EQU CHRTB+256;Prefixes ;- EXPANDER --------------- TRNTB EQU #9000;Dictionary for unpacking ;;PFXTB EQU TRNTB+256;... TRASHBF EQU #9200;Buffer for string ;--------------------------------------- ; All ^^^ buffers are 256 bytes ;Dictionaries have the same format, therefore ;spaced for clarity only. ORG #6000 LD HL,TEXT; from where we click LD DE,#8000;where we put it LD B,TEXTSZ CALL LZW8CM EXX LD HL,-#8000 ADD HL,DE; HL=shrink length LD B,L LD HL,#8000;from where click LD DE,#A000;where we put it CALL LZW8EX RET DW 0 ;COMPRESSOR. HL=FROM; DE=TO; B=LEN ;--------------------------------------- LZW8CM INC B EXX ;Initializing the dictionary.LD A,17:LD (LASTIDX),A DEC A ;16-используется как пустой префикс. LD HL,CHRTB CALL SETDICT CALL GETC:LD D,A; GET STRING CM2 CALL GETC:LD E,A; GET CHAR JR C,CMEOF CALL FINDSTR:JR C,CM3 LD D,L:JR CM2; FND:PFX=STR+CHAR CM3 CALL PUTCD; NOTFND:OUTCODE 4 STR LD HL,LASTIDX; STR+CHR->DICT LD A,(HL) INC (HL) LD L,A LD H,CHRTB[ LD (HL),E:INC H; CHAR LD (HL),D; PREFIX LD D,E JR CM2 CMEOF CALL PUTCD RET ;EXPANDER. HL=FROM; DE=TO; B=LEN ;--------------------------------------- LZW8EX INC B EXX LD A,17:LD (NXTCODE),A LD HL,TRNTB XOR A; PREFIX CALL SETDICT CALL GETC:LD D,A; OLDCODE CALL PUTC EX1 CALL GETC:LD E,A; NEWCODE JR C,EXEOF NXTCODE EQU $+1 CP 0 JR C,EX4; STRING IN DICT EX3 LD A,C LD BC,TRASHBF+255 LD (BC),A LD L,D; STRING=OLDCODE+CHAR JR EX5 EX4 LD BC,TRASHBF+256 LD L,E; STRING=NEWCODE EX5 LD H,TRNTB[ CALL EXPSTR LD HL,TRASHBF+256:OR A:SBC HL,BC LD A,(BC):EXA CALL COPYSTR; OUTPUT STRING EXA ; OLDCODE+CHAR->DICT LD HL,(NXTCODE):LD H,TRNTB[ LD (HL),A:INC H LD (HL),D LD C,A; C=CHARLD A,L:INC A:LD (NXTCODE),A LD D,E JR EX1 EXEOF RET ;--------------------------------------- ;HL=DICT; BC=BUFF EXPSTR LD A,(HL):INC H;стринг->буффер LD L,(HL):DEC H DEC BC:LD (BC),A INC L:DEC L:JR NZ,EXPSTR RET ;BC=SRC; DE'=DST; HL=LEN COPYSTR LD A,(BC):INC BC;буфер->out CALL PUTC DEC HL LD A,H:OR L:JR NZ,COPYSTR RET ;E=CHAR; D=PREFIX => NC-> L=NEWPREFIX FINDSTR LD HL,CHRTB!#FF LASTIDX EQU $+1 LD BC,0 INC BC FNDS INC L LD A,E CPIR:SCF:RET PO INC H:DEC L LD A,(HL) DEC H CP D JR NZ,FNDS RET ;- SHARED ROUTINES --------------------- GETC EXX OR A LD A,(HL):INC HL DJNZ GETC1 SCF GETC1 EXX RET PUTCD LD A,D; PREFIX PUTC EXX LD (DE),A:INC DE EXX RET ;HL=DICT; A=PREFIX SETDICT ;;LD HL,CHRTB LD B,16 SDCT0 LD (HL),L:INC H LD (HL),A:DEC H INC L DJNZ SDCT0 XOR A SDCT1 LD (HL),A:INC H LD (HL),A:DEC H INC L:JR NZ,SDCT1 RET ;- DATA -------------------------------- TEXT DB #0A,#0B,#0C,#0A,#0B,#0C DB #0A,#0B,#0C,#0A,#0B,#0C DB #0A,#0B,#0C,#0A,#0B TEXTSZ EQU 17 =========8<==ОтРеЗаТь=ЗДеСь==8<============= to be continued...evil Vitalik AKA Dark / X-Trade

Hello and prosperity to you, All! =========8<==Cut=Here==8<============= - 1 - Steve Blackstock EXPLANATION OF LZW AND GIF I hope this little document helps enlighten those who want to know a little more about the Lempel-Ziv compression algorithm Welch and, specifically, about its implementation for the GIF format. Before we begin, a little about terminology in the world of this document: "Symbol": fundamental data element. In regular text in files this is a separate byte. In raster images, you are interested in, this is the index that indicates the color of a given pixel. I will refer to arbitrary character like "K". "Character stream": A character stream such as a data file. "Chain": several consecutive characters. Chain length can vary from 1 to a very large number of characters. I I can specify an arbitrary chain as "[...]K". "Prefix": almost the same as a chain, but it is implied that the prefix immediately precedes the character, and the prefix can have zero length. I will refer to an arbitrary prefix, as in "[...]". "Root": a single-character string. For most purposes this is simplesymbol, but sometimes it can be different. This is [...]K, where [...] empty. "Code": a number defined by a known number of bits that encodes the chain. "Code Stream": Output stream of codes such as "raster data". "Element": code and its chain. "Chain table": a list of elements usually, but not necessarily, unique. This should be enough to understand the document. LZW is a data compression method that extracts benefits for repetitive data chains. Since raster data usually contains quite a lot of such repetitions, LZW is a good method for compressing and expanding them. For now, let's look at regular coding and decoding using the LZW algorithm. GIF uses variation this algorithm. When shrinking and expanding, LZW manipulates three objects: a stream of symbols, a stream of codes and a table of strings. When compressed the stream of symbols is the input and the stream of codes is the output. When expansion, the input is a stream of codes, and the stream of symbols is on days off. The string table is generated by both compression and opening, but it is never transferred from compression to opening and vice versa. . - 2 - The first thing we do with LZW compression isinitializing our character string. To do this, we you need to select a size code (number of bits) and know how many possible meanings our symbols can take. Let's put code size equal to 12 bits, which means it can be memorized 0FFF, or 4096, elements in our string table. Let's also Let's say we have 32 possible different symbols. (This corresponds, for example, to a picture with 32 possible colors for each pixel.) To initialize the table, we will set matching code #0 to character #0, code #1 to character #1, etc., until code #31 and symbol #31. In fact, we indicated that each code 0 to 31 is the root. There will be no others in the table codes that have this property. Now we will start data compression. Let's first define something called the "current prefix". This prefix we will constantly remember and compare with him here and in further. I will refer to it as "[.c.]". Initially current the prefix contains nothing. Let's also define "current chain" which is formed by the current prefix and the next character in a stream of characters. I will denote the current chain as "[.c.]K", where K is some character. Now look at the first character in the character stream. Let's callits P. Let's make [.c.]P the current chain. (At this point it is of course, the root is P.) Now let's search the string table to determine whether [.c.]P is included in it. Of course now it is will happen because our table was initialized all roots are placed. In this case we do nothing. Now make the current prefix [.c.]P. We take the next symbol from the stream by symbol. Let's call him Q. Let's add the current prefix to form [.c.]Q, i.e. current chain. We search the chain table to determine does it include [.c.]Q. In this case, this, of course, will not happen. Yeah! Now we need to do something. Let's add [.c.]Q (which in this case is PQ) to the chain table under code #32, and output the code for [.c.] to the code stream. Now let's start again with current prefix corresponding to the root P. Continue adding characters to [.c.] to form [.c.]K, until until we can find [.c.]K in the string table. Then print the code for [.c.] and add [.c.]K to the string table. On In pseudo code, the algorithm will be described approximately like this: [1] Initialize the string table; [2] [.c.] <- empty; [3] K <- next character in the character stream; [4] Is [.c.]K included in the string table? (yes: [.c.] <- [.c.]K; go to [3]; )(none: add [.c.]K to the string table; output code for [.c.] to code stream; [.c.] <- K; go to [3]; ) . - 3 - How simple it is! Of course, when we do step [3] and there are no more characters left in the input stream, you output the code for [.c.] and leave the table. Everything is done. Want an example? Let's assume that we have 4-character alphabet: A,B,C,D. The character stream looks like ABACABA. Let's squeeze it. First we initialize our chain table: #0=A, #1=B, #2=C, #3=D. The first character is A, which is included in the string table, therefore [.c.] becomes equal to A. Next we take AB, which is not included in the table, hence we output code #0 (for [.c.]), and add AB to table of chains with code #4. [.c.] becomes equal to B. Next we take [.c.]A = BA, which is not included in the string table, therefore we output code #1, and add BA to the table of chains with code #5. [.c.] becomes equal to A. Next we take AC, which is not included in the chain table. We output code #0 and add AC to the table chains with code #6. Now [.c.] is equal to C. Next we take [.c.]A = CA that is not included in the table. Print #2 for C, and add CA to the table under code #7. Now [.c.]=A. Next we take AB, whichIS INCLUDED in the string table, therefore [.c.] becomes equal AB, and we are looking for ABA, which is not in the string table, so we print the code for AB, which is #4, and add ABA to the table chains under code #8. [.c.] is equal to A. We can no longer take characters, so we print code #0 for A and call it a day. Therefore, the code stream is #0#1#0#2#4#0. A few words (three) should be said about efficiency: use a hashing strategy. Searching the string table can be associated with significant computation and hashing significantly reduces these costs. Please note that "direct LZW" compression works with the risk of string table overflow - the result is a code that cannot be represented by the number of bits, previously set for codes. There are several ways to to deal with this problem and GIF implements the most the simplest one. We will do the same. An important point to note is is that at any point during compression is performed condition: if [...]K is included in the table of strings, then [...] also enters it. This circumstance leads to an effective method memorizing chains in a table. Instead of memorizing table the entire chain, use the fact that any chain canbe represented as a prefix plus the symbol: [...]K. If you deposit [...]K into the table, you know what [...] is already in it, and so you can remember the code for [...] plus the trailing character K. That's all you need to worry about when compressing. Disclosure, perhaps more complex conceptually, but software implementation its simpler. . =========8<==Cut=Here==8<============= evil Vitalik AKA Dark / X-Trade

Hello and prosperity to you, All! =========8<==Cut=Here==8<============= - 4 - Let's describe how this is done. We start again with initialization chain tables. This table is formed based on the knowledge which we have about the flow that is ultimately generated symbols, for example, about the possible meanings of symbols. In GIF files this information is in the header, as the number of possible values pixels However, the beauty of LZW is that that's all we need necessary. The compression was done in such a way that we never we will encounter code in the code stream that we could not convert in a chain. We need to define something called "current code" which we will refer to as "", and "old code", to which we will refer to as "". To start unpacking Let's take the first code. It now becomes . This code will be initialize the chain table as root. We output root to character stream. Let's make this code the old code . (*) Now take the following code and assign it to . It's possible that this code isn't part of the chaining table, but let's For now let's assume that it is there. We output the chain, the corresponding into the character stream. Now let's find the first onecharacter in the chain you just received. Let's call him K. Let's add it to the prefix [...] generated by , to get a new chain [...]K. Let's add this chain to the table chains and set the old code equal to the current code . Repeat from the place that I marked with an asterisk and you all you will do it. Read this paragraph again if you only "we ran" through it!!! Now let's consider the possibility that is not included in the chain table. Let's go back to compression and try understand what happens if a chain appears in the input stream type P[...]P[...]PQ. Let us assume that P[...] is already in table, but P[...]P - no. The encoder will perform grammar parses P[...], and finds that P[...]P is not in the table. This will output the code for P[...] and add P[...]P to the table chains. Then it will take P[...]P for the next chain and will determine that P[...]P is in the table and produce an output code for P[...]P, if it turns out that P[...]PQ is missing from the table. The decoder is always "one step behind" encoder. When the decoder sees the code for P[...]P, it doesn't will add this code to his table right away because he needs initial character P[...]P to be added to the chain for the lastcode P[...] to generate the code for P[...]P. However, when the decoder will find a code that is not yet known to him, he will always will be 1 more than the last one added to the table. Therefore, he can guess that the chain for this code is must be and, in fact, always will be correct. If I'm a decoder, and I saw code #124, and my table chains contains the last code only with #123, I can assume that the code with #124 should be there, add it to my string table and output the chain itself. If code #123 generates a chain that I will refer here as a prefix [...], then code #124 in this special case there will be [...] plus the first character [...]. So I have to add the first character [...] to itself. Not so bad. . - 5 - As an example (quite common), let's Let's assume that we have a raster image in which the first three pixels have the same color. Those. my character stream looks like: QQQ.... To be specific, let's say that we we have 32 colors and Q corresponds to color #12. The encoder will generate code sequence 12,32,.... (if you don’t understand why, take a minute to understand.) Recall that code #32 is not included in initial table, which contains codes #0 to #31.The decoder will see code #12 and translate it as color Q. It will then will see code #32, the meaning of which he does not yet know. But if he thinks about it long enough, he will be able to understand that QQ should be element #32 in the table and QQ must be the next chain output. Thus, the pseudo decoding code can be represented as follows: [1] Initialize string string; [2] take the first code: ; [3] output the string for to a character stream; [4] = ; [5] <- next code in the code stream; [6] does exist in the string table? (yes: output the string for to a character stream; [...] <- broadcast for ; K <- first translation character for ; add [...]K to the string table; <- ; ) (no: [...] <- broadcast for ; K <- first character [...]; output [...]K to a character stream and append it to it to the table of chains; <- ) [7] go to [5]; Again, if you find in step [5] that there is no more characters, you must complete. Deriving chains and finding the initial characters in them pose problems in themselves effectiveness, but I'm not going to suggest ways tosolutions. Half the fun of programming is allowing such things! . - 6 - --- And now GIF variations on this theme. In the header part In a GIF file, there is a field called in the raster data stream "size code". This is a very confusing name for this field, but we must come to terms with it. In fact, this is the "root size". Actual size (in bits) of compression codes in reality changes during the shrink/expand process and I'll refer to it here as in "compression size". The initial table, as usual, contains codes for all roots, but two special codes are added to the top of it. Let's say we have a "code size" which is usually a number bits per pixel. Let's denote it N. If the number of bits per pixel is 1, N must equal 2: the roots occupy cells #0 and #1 in the initial table and two special codes will occupy cells #4 #5. B in any other case N is equal to the number of bits per pixel, the roots occupy cells #0 to #(2**N-1), and special codes are (2**N) and (2**N + 1). The initial compression size will be N+1 bits per code. If you when encoding, you first output codes of length (N+1) bits and, if you are decoding, you first select (N+1) bits from code stream. The special codes used are: orclear code equal to (2**N) and or end of information equal to (2**N + 1). tells the encoder what to do again initialize the chain table and reset the compression size equal to (N+1). means there are no more codes. If you encoding or decoding, you must start adding elements into the chain table with + 2. If you enter encoding, you should output as the very first code, and then again every time you reach the code #4095 (hex FFF) because GIF does not allow size compression greater than 12 bits. If you are conducting a disclosure, you should reinitialize your chain table as soon as you find . Variable compression size doesn't really add much value hassle. If you are encoding you start with a compression size of (N+1) bits, and once you output the code (2**(compression size)-1), you increase the compression size by one bit. Therefore, the next code in your output will be one bit longer. Remember that the largest compression size is 12 bits, which corresponds to code 4095. If you reach this limit, you should output as the following code and start over. If you are driving decoding, you should increase your compression size AS SOON AS YOUwrite element #(2**(compression size) - 1) to the string table. The next code you READ will be one bit longer. Not make mistakes by waiting until you need to add to the table code (2**compression size). You already missed a bit from the last code. Packing codes into a bitstream of raster data is also is a potential stumbling block for newbies encoding and decoding. The least significant bit of the code must match The least significant available bit of the first available byte in the code stream. For example, if you started with a 5-bit compression code, and your three the first codes, say, , , , where e, j, and o bits #0, your code stream will start like: . - 7 - byte#0: hijabcde byte#1: .klmnofg So the difference between regular LZW and LZW for GIF consist in the presence of two additional special codes and variable compression size. If you understood LZW and you understood these differences, you understand everything! As a P.S. You may have noticed that the encoder has little bit flexibility during compression. I described "greedy" a method that selects so many characters before printing the code, as far as possible. In fact, this method is standard for LZW and results in the best compression ratio.However, there is no rule that prohibits you stop and print the code for the current prefix, regardless on whether it is already in the table or not, and add this chain plus the next character to the string table. There are various reasons to want to do this, especially if the chain is too long and causes hashing difficulties. If this is for you need, do it. I hope this helps you. Steve Blackstock Steve Blackstock was helped to speak Russian by an employee Institute of Applied Mathematics AH CCCP A. Samotokhin =========8<==Cut=Here==8<============= employee of the Institute of Applied Mathematics AH CCCP A. Samotokhin helped will appear in the echo sleepy-evil Vitalik AKA Dark / X-Trade