CODER.H This is the header file needed to use CODER.C.

CODER.C This file contains the routines needed to implement
an arithemtic coder.

BITIO.H This is the header file needed to use BITIO.C.

BITIO.C This is the module used to do bit-oriented I/O.

COMP-1.C This is the main module for a fixed-context
compression program. It is used to drive MODEL-1
and MODEL-1A. It doesn't know about escape codes.

EXPAND-1.C This is the main module for a fixed-context
decompression program. It is used with MODEL-1
and MODEL-1A. Doesn't know about escape codes,
order (-1) models, or any of that stuff.

MODEL.H This is the header file that is used when working
with any of the modeling modules.

MODEL-1.C This is the modeling model for a very siple order-0
fixed context model. To be used with COMP-1 or
EXPAND-1.

COMP-2.C This is the main module for a highest-context
compression program. It handles escape codes, and
does compression ratio checking as well. It is
used with MODEL-2 and MODEL-2A.

EXPAND-2.C This is the main module for a highest-context
decompression program. It understands all of the
fancy stuff used in MODEL-2 and MODEL-2A.

MODEL-2.C This is the highly optimized source for a
variable order compression program. It is
used with COMP-2 or EXPAND-2.

MODEL-1A.C This is an order-1 fixed context modeling unit, that
can be combined with COMP-1 and EXPAND-1. Used
to test compression for higher order models that
don't use escape codes.

MODEL-2A.C This is the source for an order-1 highest-order
modeling program. It understands escape codes,
but has a simple data structure that takes up a
lot of room. So it is fast, but takes up lots
of RAM. Can't be expanded beyond order-1 in a

PC due to memory limitations.

CODER.H This is the header file needed to use CODER.C.

CODER.C This file contains the routines needed to implement
an arithemtic coder.

BITIO.H This is the header file needed to use BITIO.C.

BITIO.C This is the module used to do bit-oriented I/O.

COMP-1.C This is the main module for a fixed-context
compression program. It is used to drive MODEL-1
and MODEL-1A. It doesn't know about escape codes.

EXPAND-1.C This is the main module for a fixed-context
decompression program. It is used with MODEL-1
and MODEL-1A. Doesn't know about escape codes,
order (-1) models, or any of that stuff.

MODEL.H This is the header file that is used when working
with any of the modeling modules.

MODEL-1.C This is the modeling model for a very siple order-0
fixed context model. To be used with COMP-1 or
EXPAND-1.

COMP-2.C This is the main module for a highest-context
compression program. It handles escape codes, and
does compression ratio checking as well. It is
used with MODEL-2 and MODEL-2A.

EXPAND-2.C This is the main module for a highest-context
decompression program. It understands all of the
fancy stuff used in MODEL-2 and MODEL-2A.

MODEL-2.C This is the highly optimized source for a
variable order compression program. It is
used with COMP-2 or EXPAND-2.

MODEL-1A.C This is an order-1 fixed context modeling unit, that
can be combined with COMP-1 and EXPAND-1. Used
to test compression for higher order models that
don't use escape codes.

MODEL-2A.C This is the source for an order-1 highest-order
modeling program. It understands escape codes,
but has a simple data structure that takes up a
lot of room. So it is fast, but takes up lots
of RAM. Can't be expanded beyond order-1 in a

PC due to memory limitations.


1. The problem was caused by an overflow in the arithmetic coder
due to long strings of repeated characters. This has been
fixed.

2. The program now tests for repeated strings and bypasses the
scan procedure. This has improved the performance significantly
for the slowest files.

3. I have included all the source files and executables. Most of
the changes are in MODEL.C. I have made some minor changes to
some of the other routines, such as correcting spelling mistakes.

4. I have checked the underflow situation at end of file, and I am
still convinced that my method works. The version of the
arithetic coding algorithm published in the CACM presents random
bits to the decoder at end of file, so that the final value output
by the coder must include enough bits to allow the final symbol
to be resolved no matter what follows. This means outputting the
underflow bits plus two more to ensure the input value is bracketed
by the high and low limits.

I get around this problem by returning zeroes after the decoder
detects end of file.

Thank you for the chance to fix the problems.

Charles.

CODER.H This is the header file needed to use CODER.C.

CODER.C This file contains the routines needed to implement
an arithemtic coder.

BITIO.H This is the header file needed to use BITIO.C.

BITIO.C This is the module used to do bit-oriented I/O.

COMP-1.C This is the main module for a fixed-context
compression program. It is used to drive MODEL-1
and MODEL-1A. It doesn't know about escape codes.

EXPAND-1.C This is the main module for a fixed-context
decompression program. It is used with MODEL-1
and MODEL-1A. Doesn't know about escape codes,
order (-1) models, or any of that stuff.

MODEL.H This is the header file that is used when working
with any of the modeling modules.

MODEL-1.C This is the modeling model for a very siple order-0
fixed context model. To be used with COMP-1 or
EXPAND-1.

COMP-2.C This is the main module for a highest-context
compression program. It handles escape codes, and
does compression ratio checking as well. It is
used with MODEL-2 and MODEL-2A.

EXPAND-2.C This is the main module for a highest-context
decompression program. It understands all of the
fancy stuff used in MODEL-2 and MODEL-2A.

MODEL-2.C This is the highly optimized source for a
variable order compression program. It is
used with COMP-2 or EXPAND-2.

MODEL-1A.C This is an order-1 fixed context modeling unit, that
can be combined with COMP-1 and EXPAND-1. Used
to test compression for higher order models that
don't use escape codes.

MODEL-2A.C This is the source for an order-1 highest-order
modeling program. It understands escape codes,
but has a simple data structure that takes up a
lot of room. So it is fast, but takes up lots
of RAM. Can't be expanded beyond order-1 in a

PC due to memory limitations.


1. The problem was caused by an overflow in the arithmetic coder
due to long strings of repeated characters. This has been
fixed.

2. The program now tests for repeated strings and bypasses the
scan procedure. This has improved the performance significantly
for the slowest files.

3. I have included all the source files and executables. Most of
the changes are in MODEL.C. I have made some minor changes to
some of the other routines, such as correcting spelling mistakes.

4. I have checked the underflow situation at end of file, and I am
still convinced that my method works. The version of the
arithetic coding algorithm published in the CACM presents random
bits to the decoder at end of file, so that the final value output
by the coder must include enough bits to allow the final symbol
to be resolved no matter what follows. This means outputting the
underflow bits plus two more to ensure the input value is bracketed
by the high and low limits.

I get around this problem by returning zeroes after the decoder
detects end of file.

Thank you for the chance to fix the problems.

Charles.
HUFFSTUFF.ZIP: 15-Aug-90
-----------------------------

The following files are included:


HUFF1.C C source code for Huffman Code compression program.

HUFF1.EXE Executable Huffman Code compression program compiled
under Lattice C V6.0.

DHUFF.C C Source code for Huffman Code decompression program.

DHUFF.EXE Executable Huffman Code decompression program compiled
under Lattice C V6.0.

README.DOC This file.


** These programs were compiled using the command:
lc -O -L -aw -ciust -d0 -n -ml


I believe that these programs are "portable" enough to be recompiled using
another C compiler without too much trouble.

Please feel free to modify, improve, etc. these programs as you see fit.
They are hereby placed in the public domain. Being interested in
compression techniques, I would like to see any modifications, improvements,
etc. (Variable code sizes, etc.)


William Demas
72677, 3146
The program SPLAY is a pascal to C translation of a program that
Kim Kokkonen wrote in Turbo Pascal to implement Splay Trees.

This program compresses and decompresses files, and does a pretty good
job of it.

Contents:

SPLAY.PAS Original TP source code
SPLAY.C Translation of code to C
SPLAY.EXE Compiled version of SPLAY.C (small model)
README.DOC You are looking at it

Read the comments at the beginning of SPLAY.C for more info.