compression with 9 bits don't work

it simply doesn't work (no 8-codes block flush after the clear code?):
$ compress -cb9 /usr/bin/compress >/tmp/test.Z
$ compress -dc /tmp/test.Z
insize:7901 posbits:0 inbuf:00 0A F7 23 CC (0)
uncompress: corrupt input
$ gzip -tv /tmp/test.Z
gzip: /tmp/correct.Z: corrupt input.

and it is not working for a long time (at least 12 years):
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=220820

the debian proposed patch (using at least 10 bits) would break the Single UNIX Specification, Version 4 (IEEE Std 1003.1) as 9 <= bits <= 14:
http://pubs.opengroup.org/onlinepubs/9699919799/utilities/compress.html

if the bug cannot be resolved, a note should be added, like the one present in the debian package readme:
"If you create files using -b9 (maxbits of 9), your file is probably corrupted, and you will only be able to recover parts of it."

ciao!

my previous sentence was incorrect: the debian proposed patch would NOT break the SUSv4 as "the format of compressed files is unspecified", so if the -b9 option is accepted (even if ignored) the conformance is not affected

gzip unlzw is just a bit modified decompressor from ncompress.

The main problem is cipher in compress:

boff = outbits = (outbits-1)+((n_bits<<3)-((outbits-boff-1+(n_bits<<3))%(n_bits<<3)));

And it's variant in decompress:

posbits = ((posbits-1) + ((n_bits<<3) - (posbits-1+(n_bits<<3))%(n_bits<<3)));

There is no comments, no git history available. It is a fast, simple LZW file compressor =)

I can't decode this "code" bomb. It looks like some alien tried to write remainder, but failed. I am writing it in the following way. But my compressor is not ready yet. I have to be compatible with ncompress, so this bomd should be demined.

See #17

Patch provided by debian maintainer is just a strange dance around code bits. Code bits has nothing to do with this issue. The problem is write manipulations with posbits:

posbits = 3<<3;
posbits = 0;
posbits = ((posbits-1) + ((n_bits<<3) - (posbits-1+(n_bits<<3))%(n_bits<<3))); // worst nightmare ever
input(inbuf,posbits,code,n_bits,bitmask);
posbits -= n_bits;

Here we can see "some optimizations".

compress version 4.2.1 improvements
  o Completly rewrite of the compress and decompress functions.
      compress speedup 25-50% (user cpu time).
      decompress speedup 20-30% (user cpu time).

I can predict that this formula appears here, because version 4.0 has no any %(n_bits<<3). I will try to dive into 4.0 to answer how to remove it from current version.

Finally I've restored the reason why our grandfathers were using n_bits << 3 in 1985.

if (offset == (n_bits << 3)) {
  bp = buf;
  bits = n_bits;
  bytes_out += bits;
  do
    putchar(*bp++);
  while (--bits);
  offset = 0;
}

offset == (n_bits << 3) means destination remainder is 100% empty.

Example: we are writing 9 bit codes, destination remainder will be empty when 9 * x % 8 = 0 => x = 8, 16, ..., but for 14 bit codes it is not so accurate: 14 * x % 8 = 0 => x = 4, 8, .... This method is dummy, but reliable.

It means that we have some kind of n_bits * 8 virtual destination pre-buffer and we are flushing it into main buffer only in special cases.

More obvious way is to write bytes that has already been completed. For example libtiff.

/*
* Flush buffer if code doesn't fit.
*/
if (r_off + bits > sp->lzw_bitsize) {
  /*
  * Calculate the number of full bytes that can be
  * written and save anything else for the next write.
  */

This solution is completely different from virtual destination pre-buffer and obvious, moreover it is well documented. Nobody will suffer on reverse engineering it in libtiff.

Does boff mean buffer offset? It does not, it is just completely wrong abbreviation, which produces pain for all who tries to read it. It can be named as virtual destination pre-buffer bit offset.

We can see the following formula:

boff = -(((OBUFSIZ<<3)-boff)%(n_bits<<3));

This formula is a key to understand how boff is working.

Let's take n_bits = 9, n_bits * 8 = 72, outbits = 200.

          +------+ +------+ +------+   +---------------------+
outbits = |  72  | |  72  | |  56  | + |  16 zeroes (-boff)  |
          +------+ +------+ +------+   +---------------------+

          +----200-filled-bits-----+

We want to flush this structure into output buffer. Let's obufsiz = 8, obufsiz * 8 = 64.

          +----------+       +-----+ +------+ +------+   +---------------------+
outbits = |    64    | <---+ |  8  | |  72  | |  56  | + |  16 zeroes (-boff)  |
          +----------+       +-----+ +------+ +------+   +---------------------+

          +--outbuf--+       +--136-remaining-bits---+

Now we need to realign remaining bits by 72 and change boff.

          +--------+ +--------+   +--------------------+
outbits = |   72   | |   64   | + |  8 zeroes (-boff)  |
          +--------+ +--------+   +--------------------+

          +--136-filled-bits--+

Let's try to check previous formula: boff = - ((64 - (- 16)) % 72) = - 8. It works fine.

We can see that our output is aligned with n_bits * 8 and boff equals to amount of empty bits of aligned data with minus sign.

Now let's return back to compress-4.0.

if (free_ent > maxcode || (clear_flg > 0)) {
  /*
   * Write the whole buffer, because the input side won't
   * discover the size increase until after it has read it.
   */
  if (offset > 0) {
    if (fwrite(buf, 1, n_bits, stdout) != n_bits)
      writeerr();
    bytes_out += n_bits;
  }
  offset = 0;
}

That's it, now we can see the main underwater rock of this implementation. offset > 0 but offset != n_bits * 8, but we are writing whole aligned buffer with zeroes!

So we don't need to decode this magic formula boff = outbits = (outbits-1)+((n_bits<<3)-((outbits-boff-1+(n_bits<<3))%(n_bits<<3)));. We know that it just moves outbits forward. This formula makes us to output magic zeroes in future.

Maybe this formula wrong, I don't know. But now we knows the reason why it exists and can fix it.

We should document that any content with mime application/x-compress consist of groups aligned by n_bits * 8 and right padded with zeroes.
Than we can try to fix this issue.

PS It is a surprise for me. I was writing destination remainder in single byte right padded with zeroes. Alignment is not actually required. But if we want to be compatible with ncompress we have to allow this alignment.

I've added a paragraph into wikipedia. English is not my native laguage, maybe I made some mistakes, please fix it.

I've found the reason of this issue.

ncompress 4.2:

boff = outbits = (3<<3);
bytes_out = 0;

ncompress 4.0:

offset = 0;
bytes_out = 3; /* includes 3-byte header mojo */

3 header bytes provides 24 bit offset. It breaks alignment logic with 9 bits. There should not be any offset for alignment calculation.

wow, you have done a wonderful analysis, congratulations! I should try to fix my compress shell script with your findings!

I've just finished implementing alignment in lzws. I can confirm that it works perfect. I've compressed linux-4.20.3.tar into linux-4.20.3.tar.Z and ncompress decompressed it into the same archive.

Now I can explain what this magic formula is about.

unaligned_destination_byte_length = (unaligned_destination_byte_length + destination_byte_length) % unaligned_by_code_bit_length

You can see how actually simple it is. BTW I don't need to explain anything here =)

How to obtain the original monster? There are some bad advices:

Do not store unaligned_by_code_bit_length, count it on the fly.
Do not store unaligned_destination_byte_length, use unaligned_by_code_bit_length - unaligned_destination_byte_offset instead.
Store unaligned_destination_byte_offset.
Work in bits instead of bytes.

Than I am going to finish decompressor in lzws. Than I will try to fix ncompress and backport it into gzip if it will be required.

I've downloaded a bunch of tar.Z files from internet. I have to say that alignment bits won't guaranteed to be zero. There was an implementation of lzw that writes alignment bytes from buffer without initializing them. You can reproduce it with httpd-2.1.3-beta.tar.Z. It has non zero alignment bits. So we have just to ignore alignment bits during reading.

PS same thing for remainder. Both alignment and remainder bits won't guaranteed to be zero. Ncompress itself writes zeroes as a remainder, but there can be other implementations that writes uninitialized bytes as a remainder.

fixed nine bits processing, updated reset code behaviour

@andrew-aladev

I've added a paragraph into wikipedia.

@andrew-aladev I was writing a lzw decompressor (for education mostly) and wanted to handle reset codes but run into the alignment issue. I'm not entirely clear on how it works, can you answer some of my questions?

Each group (except last) should be aligned by amount of bits multiplied by 8 and right padded with zeroes.

This padding only applies after emitting a reset code, right? Because currently my decoder increases the number of bits when dictionary size increases without doing any alignment. And it seems to be working fine.

	if (cursym == (1 << bits) && bits < maxbits) {
		++bits;
	}

For reset code, I track the number of bits that have been read. And after encountering a reset code, I keep reading (i.e ignoring) bits until the number of bits read is divisible by bits * 8:

	int code = bitread(bi, bits);
	bitsread += bits;
	if (code == 256 && blockmode) {
		while (bitsread % (8 * bits) != 0) {
			bitread(bi, 1);
			bitsread += 1;
		}
		// reset state...
	}

Unfortunately this doesn't seem to work reliably. Did I misunderstand how the alignment is supposed to work?

@N-R-K

Hello @N-R-K, I can explain a bit about how it works. Output group means several values of the same bit length. For example, you want to output 10 values with 9-bit length, than 20 values with 10-bit length, 30 values with 11-bit length, etc.

A clear (reset) code means you want to reset the internal compressor/decompressor state. It means you want to reset the dictionary and current bit length. It happens when dictionary is full or the compression ratio becomes too bad. There is a static gap for ratio calculation: compress will read at least 10000 before checking the ratio value.

This padding only applies after emitting a reset code

You can actually not apply any padding; it is required only for compatibility with the tar.Z historical format. lzws has a special mode --unaligned-bit-groups that allows to drop this compatibility.

If you want to be compatible with the tar.Z historical format, you need to align any output group, which means you need to apply right padding at the end of each group except the last one. Last group means the last group before the reset code or at EOF.

Values alignment is not the only one problem for tar.Z format, please read more about LSB and MSB here output_compatibility.txt.

I poked at this a little. In standard "block mode", the code size expansions happen to land on 8-code boundaries every time, so you can generally read the compressed data as a continuous stream of codes without regard to alignment considerations. This works until you hit a CLEAR code, which changes the code width without regard to file position.

This is why the compress implementation in unar is able to use a generic LZW implementation, right up to the point where a table clear happens.

If you generate a compressed file with block mode disabled, by passing the -C flag to compress v4.0, the CLEAR code is not reserved. The code table therefore has one additional value available. This throws everything off by one, and the 8-code block alignment becomes significant at the first code size change. I confirmed that unar fails to handle such files:

% unar test.Z
test.Z: Compress
  test... Failed! (Error on decrunching)
Extraction to current directory failed! (1 file failed.)

Other utilities on my Linux system, such as (N)compress 4.2.4.6 and gzip v1.10, handled the same file just fine.

Interesting stuff. If it weren't for the notes in the wikipedia page, I probably wouldn't have been aware of it.

Navigation Menu

Repository navigation

compression with 9 bits don't work #5

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

compression with 9 bits don't work #5

Description

Activity

trek00 commented on Nov 27, 2015

andrew-aladev commented on Nov 29, 2018

andrew-aladev commented on Nov 30, 2018

andrew-aladev commented on Jan 18, 2019

andrew-aladev commented on Jan 20, 2019

andrew-aladev commented on Jan 20, 2019

trek00 commented on Jan 20, 2019

andrew-aladev commented on Jan 24, 2019

andrew-aladev commented on Feb 22, 2019

andrew-aladev commented on Mar 13, 2019

N-R-K commented on Apr 11, 2024

andrew-aladjev commented on Apr 11, 2024

fadden commented on Aug 30, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions