[hackers] [flate] todo update || nsz

changeset: 98:25d9b5e796f6
user: nsz <nszabolcs_AT_gmail.com>
date: Tue Aug 11 14:46:50 2009 +0200
files: README TODO deflate.c flate.h inflate.c
description:
todo update

diff -r fd3836ea7105 -r 25d9b5e796f6 README
--- a/README Tue Aug 11 14:19:18 2009 +0200
+++ b/README Tue Aug 11 14:46:50 2009 +0200
@@ -14,6 +14,6 @@
         make
 
 features:
+ deflate: raw deflate compression
         inflate: decode raw deflate compressed data
- inflate_simple: minimal implementation
- deflate: raw deflate compression
+ inflate_simple: minimal inflate
diff -r fd3836ea7105 -r 25d9b5e796f6 TODO
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/TODO Tue Aug 11 14:46:50 2009 +0200
@@ -0,0 +1,44 @@
+flate
+-----
+man
+error message ?
+inflate assumes Flate* < 0
+_reset _free
+_zlib _gzip _zip
+deflate, inflate exmplae -> flate_example
+test, benchmark:
+ empty block
+ all zero (rle)
+ uncompressed block
+ test with small nin/nout (1,2..9 bytes)
+
+
+inflate
+-------
+error message
+init globals
+(rev lookup vs revinc)
+(test/optimize uncompressed block)
+read less than 7 bits in clen decode
+bound checks in clen decode
+
+
+deflate
+-------
+space opt:
+ overlap rbuf/dstwin
+ hufflen: overlap arrays (parent+heap only)
+time opt:
+ match loop unroll
+ less branching in deflate_state (check avail > MinMatch once)
+ bisect len/distbase -> lookup table
+ rolling hash
+better compression:
+ block split heuristics with lfreq, dfreq
+ (zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree)
+code cleanups:
+ bounds on the compressend size
+ verify dstsize
+ input from in+nin instead of src+srcend
+ setting s->state..
+ ushort vs int
diff -r fd3836ea7105 -r 25d9b5e796f6 deflate.c
--- a/deflate.c Tue Aug 11 14:19:18 2009 +0200
+++ b/deflate.c Tue Aug 11 14:46:50 2009 +0200
@@ -1,54 +1,27 @@
 #include <stdlib.h>
 #include <string.h>
-#include <stdio.h>
 #include "flate.h"
 
-/*
-TODO:
- space opt:
- overlap rbuf/dstwin
- hufflen: overlap arrays (parent+heap only)
- time opt:
- match loop unroll
- less branching in deflate_state (check avail > MinMatch once)
- bisect len/distbase -> lookup table
- rolling hash
- better compression:
- block split heuristics with lfreq, dfreq
- (zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree)
- code cleanups:
- bounds on the compressend size
- verify dstsize
- input from in+nin instead of src+srcend
- setting s->state..
- ushort vs int
- tests:
- empty block
- all zero (rle)
- uncompressed block
- test with small nin/nout (1,2..9 bytes)
-*/
+enum {
+ CodeBits = 16, /* max number of bits in a code + 1 */
+ EOB = 256, /* end of block symbol */
+ Nlit = 256, /* number of lit codes */
+ Nlen = 29, /* number of len codes */
+ Nlitlen = Nlit + Nlen + 3, /* litlen codes + block end + 2 unused */
+ Ndist = 30, /* number of distance codes */
+ Nclen = 19 /* number of code length codes */
+ MinMatch = 3, /* min match length */
+ MaxMatch = 258, /* max match length */
+ MaxDist = 1 << 15, /* max match distance */
 
-enum {
- MinMatch = 3, /* min match length */
- MaxMatch = 258, /* max match length */
- MaxChainLen = 256, /* max length of hash chain */
+ MaxChainLen = 256, /* max length of hash chain */
         HashBits = 13,
         HashSize = 1 << HashBits, /* hash table size */
         BigDist = 1 << 12, /* max match distance for short match length */
- MaxDist = 1 << 15, /* max match distance */
         WinSize = 2*MaxDist + MaxMatch, /* input window size */
         DstSize = MaxDist + 2*MaxMatch + 6, /* output window size (worst case compressed block size) */
         LzSize = 1 << 13, /* lz buffer size */
         LzLitFlag = 1 << 15, /* marks literal run length in lz buffer */
-
- CodeBits = 16, /* max number of bits in a code + 1 */
- EOB = 256, /* end of block symbol */
- Nlit = 256, /* number of lit codes */
- Nlen = 29, /* number of len codes */
- Nlitlen = Nlit + Nlen + 3, /* litlen codes + block end + 2 unused */
- Ndist = 30, /* number of distance codes */
- Nclen = 19 /* number of code length codes */
 };
 
 typedef struct {
@@ -62,32 +35,32 @@
 } LzCode;
 
 typedef struct {
- int state; /* prev return value */
- int eof; /* end of input */
- int pos; /* position in input win */
- int startpos; /* block start pos in input win */
- int avail; /* available in input win */
- Match prevm; /* previous (deferred) match */
- uchar *src; /* input data (not yet in win) */
+ int state; /* prev return value */
+ int eof; /* end of input */
+ int pos; /* position in input win */
+ int startpos; /* block start pos in input win */
+ int avail; /* available in input win */
+ Match prevm; /* previous (deferred) match */
+ uchar *src; /* input data (not yet in win) */
         uchar *srcend;
- uchar *dst; /* compressed output (position in dstbuf) */
- uchar *dstbegin; /* start position of unflushed data in dstbuf */
+ uchar *dst; /* compressed output (position in dstbuf) */
+ uchar *dstbegin; /* start position of unflushed data in dstbuf */
         uint bits;
         int nbits;
- uchar win[WinSize]; /* input window */
- ushort head[HashSize]; /* position of hash chain heads */
- ushort chain[MaxDist]; /* hash chain */
- LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */
- LzCode *lz; /* current pos in lzbuf */
- int nlit; /* literal run length */
+ uchar win[WinSize]; /* input window */
+ ushort head[HashSize]; /* position of hash chain heads */
+ ushort chain[MaxDist]; /* hash chain */
+ LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */
+ LzCode *lz; /* current pos in lzbuf */
+ int nlit; /* literal run length */
         ushort lfreq[Nlitlen];
         ushort dfreq[Ndist];
         uchar dstbuf[DstSize];
 } State;
 
-static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */
+static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */
 static ushort fixlcode[Nlitlen];
-static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */
+static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */
 static ushort fixdcode[Ndist];
 
 /* base offset and extra bits tables */
diff -r fd3836ea7105 -r 25d9b5e796f6 flate.h
--- a/flate.h Tue Aug 11 14:19:18 2009 +0200
+++ b/flate.h Tue Aug 11 14:46:50 2009 +0200
@@ -9,7 +9,6 @@
         FlateIn = -2,
         FlateOut = -3
 };
-/* TODO inflate assumes Flate* < 0 */
 
 typedef struct {
         int nin;
@@ -20,7 +19,6 @@
         void *state;
 } FlateStream;
 
-/* TODO: _reset _free */
 int deflate(FlateStream *s);
 int deflate_callback(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, void *), void *wdata);
 int inflate(FlateStream *s);
diff -r fd3836ea7105 -r 25d9b5e796f6 inflate.c
--- a/inflate.c Tue Aug 11 14:19:18 2009 +0200
+++ b/inflate.c Tue Aug 11 14:46:50 2009 +0200
@@ -2,16 +2,6 @@
 #include <string.h>
 #include "flate.h"
 
-/*
-TODO:
- error message
- init globals
- (rev lookup vs revinc)
- (test/optimize uncompressed block)
- read less than 7 bits in clen decode
- bound checks in clen decode
-*/
-
 enum {
         CodeBits = 16, /* max number of bits in a code + 1 */
         LitlenTableBits = 9, /* litlen code bits used in lookup table */
Received on Tue Aug 11 2009 - 13:07:17 UTC