| < draft-deutsch-deflate-spec-02.txt | draft-deutsch-deflate-spec-03.txt > | |||
|---|---|---|---|---|
| INTERNET-DRAFT L. Peter Deutsch | INTERNET-DRAFT L. Peter Deutsch | |||
| DEFLATE 1.3 Aladdin Enterprises | DEFLATE 1.3 Aladdin Enterprises | |||
| Expires: 16 Sep 1996 11 Mar 1996 | Expires: 26 Sep 1996 21 Mar 1996 | |||
| DEFLATE Compressed Data Format Specification version 1.3 | DEFLATE Compressed Data Format Specification version 1.3 | |||
| File draft-deutsch-deflate-spec-02.txt | File draft-deutsch-deflate-spec-03.txt | |||
| Status of this Memo | Status of this Memo | |||
| This document is an Internet-Draft. Internet-Drafts are working | This document is an Internet-Draft. Internet-Drafts are working | |||
| documents of the Internet Engineering Task Force (IETF), its areas, | documents of the Internet Engineering Task Force (IETF), its areas, | |||
| and its working groups. Note that other groups may also distribute | and its working groups. Note that other groups may also distribute | |||
| working documents as Internet-Drafts. | working documents as Internet-Drafts. | |||
| Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||
| and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||
| skipping to change at line 30 ¶ | skipping to change at line 30 ¶ | |||
| material or to cite them other than as ``work in progress.'' | material or to cite them other than as ``work in progress.'' | |||
| To learn the current status of any Internet-Draft, please check the | To learn the current status of any Internet-Draft, please check the | |||
| ``1id-abstracts.txt'' listing contained in the Internet- Drafts | ``1id-abstracts.txt'' listing contained in the Internet- Drafts | |||
| Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), | Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), | |||
| munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or | munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or | |||
| ftp.isi.edu (US West Coast). | ftp.isi.edu (US West Coast). | |||
| Distribution of this memo is unlimited. | Distribution of this memo is unlimited. | |||
| A pointer to the latest version of this and related documentation in | ||||
| HTML format can be found at the URL | ||||
| <ftp:ftp.uu.net/pub/graphics/png/documents/zlib/zdoc-index.html>. | ||||
| Notices | Notices | |||
| Copyright (c) 1996 L. Peter Deutsch | Copyright (c) 1996 L. Peter Deutsch | |||
| Permission is granted to copy and distribute this document for any | Permission is granted to copy and distribute this document for any | |||
| purpose and without charge, including translations into other | purpose and without charge, including translations into other | |||
| languages and incorporation into compilations, provided that it is | languages and incorporation into compilations, provided that the | |||
| copied as a whole (including the copyright notice and this notice) | copyright notice and this notice are preserved, and that any | |||
| and with no changes. | substantive changes or deletions from the original are clearly | |||
| marked. | ||||
| Deutsch [Page 1] | Deutsch [Page 1] | |||
| Abstract | Abstract | |||
| This specification defines a lossless compressed data format that | This specification defines a lossless compressed data format that | |||
| compresses data using a combination of the LZ77 algorithm and Huffman | compresses data using a combination of the LZ77 algorithm and Huffman | |||
| coding, with efficiency comparable to the best currently available | coding, with efficiency comparable to the best currently available | |||
| general-purpose compression methods. The data can be produced or | general-purpose compression methods. The data can be produced or | |||
| consumed, even for an arbitrarily long sequentially presented input | consumed, even for an arbitrarily long sequentially presented input | |||
| data stream, using only an a priori bounded amount of intermediate | data stream, using only an a priori bounded amount of intermediate | |||
| skipping to change at line 361 ¶ | skipping to change at line 366 ¶ | |||
| Deutsch [Page 7] | Deutsch [Page 7] | |||
| 1) Count the number of codes for each code length. Let | 1) Count the number of codes for each code length. Let | |||
| bl_count[N] be the number of codes of length N, N >= 1. | bl_count[N] be the number of codes of length N, N >= 1. | |||
| 2) Find the numerical value of the smallest code for each code | 2) Find the numerical value of the smallest code for each code | |||
| length: | length: | |||
| code = 0; | code = 0; | |||
| bl_count[0] = 0; | bl_count[0] = 0; | |||
| for (bits = 1; bits <= MAX_BITS; bits++) { | for (bits = 1; bits <= MAX_BITS; bits++) { | |||
| next_code[bits] = code | code = (code + bl_count[bits-1]) << 1; | |||
| = (code + bl_count[bits-1]) << 1; | next_code[bits] = code; | |||
| } | } | |||
| 3) Assign numerical values to all codes, using consecutive | 3) Assign numerical values to all codes, using consecutive | |||
| values for all codes of the same length with the base values | values for all codes of the same length with the base values | |||
| determined at step 2. Codes that are never used (which have a | determined at step 2. Codes that are never used (which have a | |||
| bit length of zero) must not be assigned a value. | bit length of zero) must not be assigned a value. | |||
| for (n = 0; n <= max_code; n++) { | for (n = 0; n <= max_code; n++) { | |||
| len = tree[n].Len; | len = tree[n].Len; | |||
| if (len == 0) continue; | if (len != 0) { | |||
| tree[n].Code = next_code[len]++; | tree[n].Code = next_code[len]; | |||
| next_code[len]++; | ||||
| } | ||||
| } | } | |||
| Example: | Example: | |||
| Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3, | Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3, | |||
| 3, 2, 4, 4). After step 1, we have: | 3, 2, 4, 4). After step 1, we have: | |||
| N bl_count[N] | N bl_count[N] | |||
| - ----------- | - ----------- | |||
| 2 1 | 2 1 | |||
| End of changes. 6 change blocks. | ||||
| 9 lines changed or deleted | 16 lines changed or added | |||
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ | ||||