< 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/