3

This has been an incredibly difficult question to Google. I am not looking for gzip or Zip or deflate. The algorithm I want to use is called "compress" but that does not mean I am trying to implement compression in general. I am looking for a specific algorithm.

I am looking for the adaptive Lempel-Ziv algorithm used by the compress command line tool in Unix-like systems. I am looking for the algorithm HTTP says you should use when you receive a Content-Encoding: compress header. It's the algorithm you see described when you type man compress in a POSIX shell, and in this Wikipedia article.

I understand this compression algorithm is very old and has been replaced by gzip, Zip, deflate, etc. for almost all practical purposes. But I am writing a server in C++ as a pet project and IANA specifies this Unix "compress" algorithm as one of the encodings every server should support.

The compress utility has been part of the Unix shell for a long time - since before POSIX - and I have trouble believing there's no standard C language implementation. I could use calls to system or exec to do the compression in the shell (creating another process...ugh) but that would be so much less efficient than just compiling the algorithm into my executable.

Is there a standard C implementation/library for this algorithm?

William Rosenbloom
  • 2,506
  • 1
  • 14
  • 37
  • Your question is almost certainly off-topic for SO. It is not that hard to Google, just Google [`"compress algorithm"`](https://www.google.co.uk/search?hl=en&q=cp%2Cress+algorithm&meta=&gws_rd=ssl#hl=en&q=%22compress+algorithm%22) *including* the quotes. The Wikipedia page for it for example has external links to source code implementations; [*ncompress*](http://ncompress.sourceforge.net/) for example. Not a library, but as source code you can no doubt separate the necessary routines from the UI. – Clifford Dec 19 '15 at 10:39
  • *"What is the POSIX system library for the LZW algorithm used by the `compress` utility?"* might be an on-topic way of asking this question. I retract my close vote. – Clifford Dec 19 '15 at 10:58
  • @Clifford it is done. – William Rosenbloom Dec 19 '15 at 11:00

4 Answers4

1

I think I've found some good references:

First here is the Free BSD implementation of compress based on Lempel-Ziv: https://www.freebsd.org/security/advisories/FreeBSD-SA-11:04.compress.asc

Here and here a modified version of the Lempel-Ziv algorithm (among the authors you will find Spencer W. Thomas).

Newer implementation

DOS porting

Apple version based on FREE BSD.

hint: search "compress.c" quoted.

terence hill
  • 3,354
  • 18
  • 31
  • Note that *"Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow "*, and this question looks remarkably like that - hence my posting a comment rather then an answer. The OP would do better learning effective Google technique than having us do the legwork. – Clifford Dec 19 '15 at 10:39
  • @Clifford Ok, I didn't thought about that. – terence hill Dec 19 '15 at 10:41
  • Not a problem; personally I have no problem with anyone being helpful, in any way. Others may down-vote your helpfulness - you cannot do that to a comment. The purpose of the rule is to no doubt prevent SO from being cluttered with questions better or easily answered by a Google search, or attracting answers with external links that may not age well (i.e. become broken). – Clifford Dec 19 '15 at 10:46
  • @Clifford I'd like to defend myself. I was hoping for a portable solution that would be available on all Posix systems as part of truly standard libraries. I imagine all Posix systems would be able to handle old Unix routines like `compress`. I was hoping for something based on system standards. I am not tryna find an external library if I can help it. – William Rosenbloom Dec 19 '15 at 10:47
  • @WilliamRosenbloom : Perhaps that should be clearer in your question. In that case what I did was Google `"compression library archive"`, and it seems that what you need is *libarchive* ([Linux manpage](http://linux.die.net/man/3/libarchive), [project page](http://www.libarchive.org/)). It is still a question of Google fu I think. – Clifford Dec 19 '15 at 10:54
  • These "implementations" are just adoptions of single buggy implementation from 80-x years. – puchu Mar 15 '19 at 16:56
1

Certainly in Linux the system library libarchive supports LZW as used by compress.

The library has its own project page, and in that sense therefore is portable, although it is no doubt used on other, if not all POSIX systems. Try man libarchive perhaps?

Clifford
  • 88,407
  • 13
  • 85
  • 165
  • Is this portable to OS X? I have two machines. One runs linux one runs OS X. – William Rosenbloom Dec 19 '15 at 11:09
  • I don't know; I just Googed it;-). It is listed here: http://www.apple.com/opensource/. I would start by looking on your system to see if it exists already. If not install instructions are at http://macappstore.org/libarchive/. I cannot see why it should have any OS specific dependencies, it is just processing data. There's even a [port for Windows](http://gnuwin32.sourceforge.net/packages/libarchive.htm) – Clifford Dec 19 '15 at 12:33
1

You can find an unlzw() function that I wrote here to decompress a Content-Encoding: compress transfer.

However, you do not have to support compress to be http-compliant. The compression method is a negotiation, and you can either not say that you accept compress (if you are the client) or not deliver compress when the client accepts it (if you are the server). It is not true that "every server should support" the compress encoding.

Community
  • 1
  • 1
Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • What if a user sends a POST or PUT request with a compress content encoding on its body? Don't I need to be able to decode that? Also aren't I required to send a compressed response if I receive the header `Accept-Encoding: compress, identity; q=0`? – William Rosenbloom Dec 20 '15 at 02:59
  • Good points. Yes, it is theoretically possible for a server or client to try to force your hand. So I will have to fall back to claiming that you will never see that happen in the real world with the "compress" encoding. – Mark Adler Dec 20 '15 at 16:37
0

You can use lzws library. It has no legacy code and compatible with UNIX compress. Tested on GNU/Linux, OSX, Free BSD and Windows (MinGW). Has ruby bindings.

puchu
  • 3,294
  • 6
  • 38
  • 62