Data compression (in Ada)

Data compression (in Ada)

[Mike Roske]

I am looking for an Ada 83 implementation of a file
compression/decompression algorithm (a la Zip).  It doesn't have to be
compatible with Zip.

I have a need to take a file, compress it, and store it on an embedded
file system (part of the load process).  At run-time I will be
uncompressing the file into RAM in order to access the data.  There 
isn't enough EEPROM to store the uncompressed file, but I have enough
RAM once I get started.

My software MUST be written in Ada83 (contract requirement).

Any help would be greatly appreciated!

Thanks in advance,

--> Mike

-- 
*-------------------------------------------------------*
* Michael Roske
* Sanders, A Lockheed Martin Company
* mroske@mailgw.sanders.lockheed.com
* (603) 885-9240
*-------------------------------------------------------*
* "I'd rather be flying RC..."                     
*-------------------------------------------------------*

Re: Data compression (in Ada)

[Tore Joergensen]

Mike Roske (mroske@mailgw.sanders.lockheed.com) wrote:
: I am looking for an Ada 83 implementation of a file
: compression/decompression algorithm (a la Zip).  It doesn't have to be
: compatible with Zip.

: I have a need to take a file, compress it, and store it on an embedded
: file system (part of the load process).  At run-time I will be
: uncompressing the file into RAM in order to access the data.  There 
: isn't enough EEPROM to store the uncompressed file, but I have enough
: RAM once I get started.

Try to find some information on LZW compression. This is the compression
algorithm Zip is based on, and it's fairly easy to implement. I'd 
recommend to use a table index-size of two bytes and a data-size of
one byte (then you will avoid having to shift the bits), unless this
doesn't make sense for your program. I made a LZW compression program
in Ada as an assignment in a course, but I don't have the code anymore.
It is really easy to implement, and the nice thing about it is that
it builds the compression-table while you write and read the file, so
you don't have to store the table with the file.
-- 
+-------------------------+-------------------------------------------+
| Tore B. Joergensen      | e-mail : tore@lis.pitt.edu                |
| Centre Court Villa      | web    : http://www.pitt.edu/~tojst1      |
| 5535 Centre Avenue # 6  |                                           |
| Pgh, PA 15232, USA      | Norwegian MSIS-student at Univ. of Pgh.   |
+-------------------------+-------------------------------------------+

Re: Data compression (in Ada)

[John Howard]

On 29 Jun 1996, Tore Joergensen wrote:

> Mike Roske (mroske@mailgw.sanders.lockheed.com) wrote:
> : I am looking for an Ada 83 implementation of a file
> : compression/decompression algorithm (a la Zip).  It doesn't have to be
> : compatible with Zip.
>
> : I have a need to take a file, compress it, and store it on an embedded
> : file system (part of the load process).  At run-time I will be
> : uncompressing the file into RAM in order to access the data.  There 
> : isn't enough EEPROM to store the uncompressed file, but I have enough
> : RAM once I get started.

> Try to find some information on LZW compression. This is the compression
[snip]

LZW is a good general-purpose compression method though there are times 
when LZW compression actually expands the size instead of reducing it.
More serious is the fact that the Lempel-Ziv Welch (LZW) algorithm is
patented.  Don't use it unless you are willing to pay royalties.  UniSys
(or whatever they changed the name to) acquired the LZW patent.  The LZW 
patent has only recently been enforced with lawsuits.  Terry Welch is the 
culprit who published the algorithm for all the world to appreciate.  The
trouble is the owner did not enforce licensing until several years after 
LZW was made popular via the efforts of CompuServe.

That stealthy move has caused alot of problems already.  GIF is based on 
LZW and GIF is becoming popular due to Web browsers.  TIFF v5 and v6
defines LZW as part of their standard compression algorithms.  TIFF v6
recognizes LZW as patented and recommends its use be dropped.  The LZW 
stealth move is the main reason TIFF v6.0 was largely abandoned (JPEG as 
hastily defined to replace LZW for v6.0 was defective which basically left 
only RLE as a viable option supported by TIFF).  The new Adobe Public 
Document Format (PDF) also defines LZW as part of its standard.  The 
problem is that Adobe has licensed the use of LZW with its owner.  So even 
though PDF is a standard released to the public it can't be duplicated by 
software developers who don't license LZW with its owner.  PDF is 
copyrighted by Adobe but Adobe is not obligated to make PDF open.  That 
allows possible future stealth moves by Adobe or a successor (as happened 
from UniSys by acquiring the LZW patent).  PDF is a good strategic move 
for Adobe but PDF should be replaced with something truly open.  Certainly 
no public standard called "open" should rely upon patented algorithms 
requiring royalties.  [In May, I became interested in implementing Adobe 
PDF in Ada but I found LZW unavoidably defined by the standard.  Fool us 
once -- shame on you.  Fool us twice -- shame on us.  I have decided to
wait for a new TIFF standard and see what develops with alternative public
document formats that are truly open.]

The viable solution is to abandon LZW and instead use Lempel-Ziv Huffman
(LZH) or Run-Length Encoding (RLE) or Apple's PackBits for either 
compressing text files or black/white images.  PCX and fax formats are 
variations of RLE.  Go to www.adobe.com for information on RLE and 
PackBits.  LZH is found as Pascal source code on a Simtel mirror or in the 
SourceWare Archive Group (SWAG) sources.  There are variations of public
and royalty-free JPEG algorithms which are designed for compressing color
images.  Arithmetic compression is another neat algorithm which would 
often be desirable to use but cannot become popular to implement until its 
patent expires.

-- John Howard <jhoward@sky.net>

Re: Data compression (in Ada)

[Fergus Henderson]

Sorry, this article has nothing do with Ada.

John Howard <jhoward@sky.net> writes:

>LZW is a good general-purpose compression method though there are times 
>when LZW compression actually expands the size instead of reducing it.

This is true of *any* non-lossy compression method.

(Proof left as an exercise for the reader, but as a hint: think what
would happen if you had a compression method that always reduced the
size, and you then applied it repetitively...)

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Data compression (in Ada)

[Robert Dewar]

Fergus said

">LZW is a good general-purpose compression method though there are times
>when LZW compression actually expands the size instead of reducing it.

This is true of *any* non-lossy compression method."

Well yes, but this is an uninteresting observation, since it is trivial
to limit this increase in size to a single bit (simple proof, use the first
bit in the file to indicate whether or not the remaining bits have been
compressed at all!)

Re: Data compression (in Ada)

[Robert Dewar]

iMike says, looking for compression software

"My software MUST be written in Ada83 (contract requirement)."

To me this is the sort of thing that gives the Ada policy a bad name. What
on earth is the point of this. It seems obvious that it would be better to
invoke an existing reliable COTS product for this purpose (there are
several good proprietary and free software solutions).

Re: Data compression (in Ada)

[Gary Howell]

In article <31D41C54.794BDF32@mailgw.sanders.lockheed.com>,
	Mike Roske <mroske@mailgw.sanders.lockheed.com> writes:
>I am looking for an Ada 83 implementation of a file
>compression/decompression algorithm (a la Zip).  It doesn't have to be
>compatible with Zip.
>
>I have a need to take a file, compress it, and store it on an embedded
>file system (part of the load process).  At run-time I will be
>uncompressing the file into RAM in order to access the data.  There 
>isn't enough EEPROM to store the uncompressed file, but I have enough
>RAM once I get started.
>
>My software MUST be written in Ada83 (contract requirement).
>

The following description from the PAL is exactly what you're looking for:

------------- Ada Software Repository Prologue ----------------
--                                                            -
-- Unit name    : Object Code Compression
--              : (1) compression_encode
--              : (2) compression_decode
--              : (3) compression_verify
--              : (4) set_parameter_file
-- Version      : 1.1
-- Author       : Bruce Petrick
--              : The Aerospace Corporation
--              : 2350 East El Segundo Boulevard
--              : El Segundo, CA 90245-4691

--snip

	It is well designed, well coded, and easy to tailor.

-- 
--|-----------------------------------------------------------------------
--|Gary L. Howell                      | EMAIL  G.Howell@cerc.wes.army.mil
--|Coastal Engineering Research Center | Voice  601-634-2006
--|USAE Waterways Experiment Station   | FAX    601-634-3151
--|-----------------------------------------------------------------------

Re: Data compression (in Ada)

[Paul Whittington]

AdaSAGE has a package called COMPRESS that does this.  

You'll need to get the GNAT/Linux/AdaSAGE source code from

  ftp://ftp.cdrom.com/pub/ada/sage/cdrom002/source/gnat/linux/adasage.tgz

Having un-ZIPed and un-TARed adasage.tgz you'll want to look at

  AdaSAGE/source/compress.ad*

Hope this helps! TTFN Paul.  

Mike Roske wrote:
> ... an Ada 83 implementation of a file compression/decompression
> algorithm ...

Re: Data compression (in Ada)

[Hannes Haug]

>>>>> "Mike" == Mike Roske <mroske@mailgw.sanders.lockheed.com> writes:

    Mike> I am looking for an Ada 83 implementation of a file
    Mike> compression/decompression algorithm (a la Zip).
    Mike> It doesn't have to be compatible with Zip.

Perhaps you should have a look at "The Data Compression Book" by
Nelson & Gailly. It comes with a floppy with the C source code.

 -hannes

Re: Data compression (in Ada)

[Mike Roske]

Hannes Haug wrote:
> 
> >>>>> "Mike" == Mike Roske <mroske@mailgw.sanders.lockheed.com> writes:
> 
>     Mike> I am looking for an Ada 83 implementation of a file
>     Mike> compression/decompression algorithm (a la Zip).
>     Mike> It doesn't have to be compatible with Zip.
> 
> Perhaps you should have a look at "The Data Compression Book" by
> Nelson & Gailly. It comes with a floppy with the C source code.
> 
>  -hannes

Thanks for the input.  I do have source for Info-ZIP (written in C).
What I'm trying to avoid is the (difficult?) task of converting it to
Ada83.  Has anyone already done this?

--> Mike

-- 
*-------------------------------------------------------*
* Michael Roske
* Sanders, A Lockheed Martin Company
* mroske@mailgw.sanders.lockheed.com
* (603) 885-9240
*-------------------------------------------------------*
* "I'd rather be flying RC..."                     
*-------------------------------------------------------*

Re: Data compression (in Ada)

[Michael Feldman]

In article <31D41C54.794BDF32@mailgw.sanders.lockheed.com>,
Mike Roske  <mroske@mailgw.sanders.lockheed.com> wrote:
>I am looking for an Ada 83 implementation of a file
>compression/decompression algorithm (a la Zip).  It doesn't have to be
>compatible with Zip.

But it might as well be compatible with zip. Why not grab the C sources
for info-zip and translate it to Ada (since your contract requires Ada).
The info-zip sources are freely distributed, not under GPL but under
comparable rules. If you don;t mind distributing your sources, you
might try a translation.

Mike Feldman

Re: Data compression (in Ada)

[Theodore E. Dennison]

Mike Roske wrote:
> 
> I am looking for an Ada 83 implementation of a file
> compression/decompression algorithm (a la Zip).  It doesn't have to be
> compatible with Zip.
> 
...
> My software MUST be written in Ada83 (contract requirement).
> 

Surely a COTS compression utility/library (which you could interface to from
Ada) would not violate your contract requirements.

-- 
T.E.D.          
                |  Work - mailto:dennison@escmail.orl.mmc.com  |
                |  Home - mailto:dennison@iag.net              |
                |  URL  - http://www.iag.net/~dennison         |