2 Mar
2005
2 Mar
'05
4:45 p.m.
Don't suppose anyone's come across anything that'll attempt to fix a
corrupt .Z (Unix compress) file, have they?
I've got a 40MB compressed tar archive here, but uncompress barfs after
the first 23MB - it'd be nice if there was a way of skipping over the
duff bits if possible and reading *something* from the last 17MB!
cheers
Jules
2 Mar
2 Mar
4:55 p.m.
Jules wrote:
I've got a 40MB compressed tar archive here, but
uncompress barfs after
the first 23MB - it'd be nice if there was a way of skipping over the
duff bits if possible and reading *something* from the last 17MB!
I'm not sure what algorithm is used for ".Z" files. For ".gz",
the
answer would probably be no, because the dictionary is continuously
updated and a corrupt area would get completely out of sync, with no
obvious means to guess what the intervening dictionary updates should
be.
If ".Z" uses a simpler algorithm with a fixed dictionary (either
completely fixed, or fixed for the duration of one file), recovery
may well be possible.
Eric
10:55 p.m.
Don't suppose anyone's come across anything
that'll attempt to fix a
corrupt .Z (Unix compress) file, have they?
Not me, but it may be doable manually, depending. What kind of error
do you have? Wrong data, dropout, insertion, you don't know, what?
I've got a 40MB compressed tar archive here, but
uncompress barfs
after the first 23MB - it'd be nice if there was a way of skipping
over the duff bits if possible and reading *something* from the last
17MB!
In theory it may be possible. compress (.Z) uses Lempel-Ziv-Welch. An
insertion or dropout is relatively hard to fix, in large part because
it means you have trouble telling where compressed values' boundaries
are. Wrong data is comparatively easy; it will give you a corrupt
decoding table (or an outright error if the coded value is out of range
and the decoder bothers to check), but if the decompressed data is
highly redundant it's often fixable.
To fix an insertion, I'd basically have to just try deleting various
numbers of bits or bytes (depending on the medium, what the probable
unit of insertion is may vary) until you get sane decoded output.
To fix a dropout, I'd try inserting varying numbers of 0 bits (or
bytes) until I started getting garbled (instead of totally garbage)
decoded output, then treat it as corrupted data.
To fix corrupted data, I'd use a decoder that lets you look at the
decompression table. (This description assumes you know LZW. If you
don't, and you can't find a good description easily, write me off-list;
it's a relatively simple algorithm.) When you get the first garbled
output, look at what decompression table entry the bogus bits came
from. Then look back to where that entry was created and see what
you'd have to change to make it come out right. Repeat until you get a
clean decompression. (If you get a code-out-of-range error, you know
which compressed code is broken; try the different possible valid codes
until you get something that makes sense locally, and of the few that
do, look to see which produce clean data following.)
There is another possibility: ignore the garbling and keep
decompressing. If you're lucky, the encoder will emit a clear code
soon and you'll start over with a clean table, at which point you will
suddenly start getting non-garbled decompression. (If you're unlucky,
the encoder will hold off on the clear code.)
Of course, all this depends on the decompressed data being relatively
nonrandom (so you can tell when you ahve garbled data). tar headers
certainly qualify; depending on what the files contained in the archive
are, they may or may not qualify. Running text in a natural language,
and programs in most computer languages, qualify as well.
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
11:27 p.m.
On Wed, 2 Mar 2005, der Mouse wrote:
In theory it may be possible. compress (.Z) uses Lempel-Ziv-Welch. An
Described here in some detail - interesting!
http://www.dogma.net/markn/articles/lzw/lzw.htm
Cheers
Jhn
3 Mar
3 Mar
8:24 a.m.
On Wed, 2005-03-02 at 22:55 -0500, der Mouse wrote:
It was an unknown - uncompress just died with "corrupt input", which
could be any of the above.
As Al (I think it was Al) suggested, I started playing around with doing
multiple reads from the tape and after several passes I got enough to
reconstruct the archive - so the specific problem's gone.
However the question about fixing .Z files still stands - I'm suprised
that given how long the format's been around, nobody ever published a
utility to attempt to fix corrupt files.
Don't
suppose anyone's come across anything that'll attempt to fix a
corrupt .Z (Unix compress) file, have they?
Not me, but it may be doable manually, depending. What kind of error
do you have? Wrong data, dropout, insertion, you don't know, what? In theory it may be possible. compress (.Z) uses
Lempel-Ziv-Welch. An
insertion or dropout is relatively hard to fix, in large part because
it means you have trouble telling where compressed values' boundaries
are. Wrong data is comparatively easy; it will give you a corrupt
decoding table (or an outright error if the coded value is out of range
and the decoder bothers to check), but if the decompressed data is
highly redundant it's often fixable.
*likely* this was corrupt data, but I'm not certain what reading from a
tape under linux does when a bad block is found. I'd expect it to still
spit out a corrupt block but flag the error. Maybe it doesn't and just
truncates the output, which isn't too helpful at all (particularly as
there's no way in GNU tar to print out block numbers of faulty blocks,
despite what the documentation says).
There is another possibility: ignore the garbling and
keep
decompressing. If you're lucky, the encoder will emit a clear code
soon and you'll start over with a clean table, at which point you will
suddenly start getting non-garbled decompression. (If you're unlucky,
the encoder will hold off on the clear code.)
I'd assume that's what uncompress does anyway, but possibly not. It'd
seem more logical to me for it to restore as much as it could but still
flag an error, rather than just barfing at the first sign of trouble.
But if that were the case, then the file I was decompressing really was
rather broken.
Still, all sorted now in this instance. A file listing of the archive
suggests that I might have the only source code copy to bits of Acorn's
ARX and Brazil operating systems (or possibly the whole lot), which is
why I was keen to get this one particular tape read. Time to extract the
archive and see exactly what there is there...
cheers
Jules
1:50 p.m.
Jules Richardson wrote:
...
However the question about fixing .Z files still
stands - I'm suprised
that given how long the format's been around, nobody ever published a
utility to attempt to fix corrupt files.
...
There is a fundamental problem why it is not tractable in general. The
whole point of a compressor is to get rid of the redundancy as much as
possible (some of course are better than others with a given input
file). It is exactly that redundancy that makes automated recovery
possible. Disk recovery relies on the fact that everything is cross
linked with everything else so you can fix up the broken sector chains etc.
If you happen to have very specific knowledge about the failure mode and
the lost/corrupted/inserted data is just a small amount it might be
possible to have an automated aid to assist in recovering the data, but
mostly everything downstream from the failure is going to be lost.
Even though G4 compression is 2x as effective as G3 compression (on
bilevel images), fax machines still use G3 because any error propagates
to the end of the scan line whereas the same error in a G4 file can
trash the image all the way to the end of the page.
If the entire tape is compressed as a stream, then things are very bad
indeed. If the tape image compresses each file individually, then it
should be possible to skip for a while and find a good new starting point.
3 p.m.
Jim Battle wrote a good description of compression eliminating redundancy,
and mentioned:
Even though G4 compression is 2x as effective as G3
compression (on
bilevel images), fax machines still use G3 because any error propagates
to the end of the scan line whereas the same error in a G4 file can
trash the image all the way to the end of the page.
I'd point out that G4 compression was specifically designed for use over
an error-corrected ISDN link, where that would not be a problem. In
principle G4 compression would work fine on dialup if V.42 error control
were used. But as you say, all commmon fax machines stick to G3.
Eric
4:10 p.m.
Jim Battle wrote:
.Z is the output of compress, which doesn't inherently seperate data by blocks
(if it did, you could decompress until bad data was found, then skip to the
next block and start over). It does, however, support a complete flush and
rebuild of the dictionary with code 257, so if you had bad data in a .Z file,
you could attempt to skip over it by searching for the next 257 code, then
start over. The drawback to this is, what if some of the mangled data
inadvertently inserts a 257 code? :-) I don't have time to burn, so I won't
code this for you, but anyone versed in LZW/LZ78 compression schemes and C
could probably write a .Z file salvager (especially since the source code for
compress is freely available).
Any compressed format that compresses in a stream (ie where the data is not
arbitrarily blocked or otherwise seperated) is going to have this problem --
anything corrupted will boffo the rest of the file after that point.
Programs like pkzipfix, etc. simply rebuild the archive by skipping the file
with the bad data. If you want real repairs, you need an archiver that
generates parity information and tacks it onto the archive. WinRAR does this,
as does WinRK and a few others.
--
Jim Leonard (trixter at oldskool.org) http://www.oldskool.org/
Want to help an ambitious games project? http://www.mobygames.com/
Or check out some trippy MindCandy at http://www.mindcandydvd.com/
However the
question about fixing .Z files still stands - I'm suprised
that given how long the format's been around, nobody ever published a
utility to attempt to fix corrupt files.
mostly everything downstream from the failure is going to be lost.
If the entire tape is compressed as a stream, then things are very bad
indeed. If the tape image compresses each file individually, then it
should be possible to skip for a while and find a good new starting point.
5:10 p.m.
However the
question about fixing .Z files still stands - [...]
There is a fundamental problem
why it is not tractable in general.
The whole point of a compressor is to get rid of the redundancy as
much as possible [...] Yes; to the extent that recovery from
corruptedesompressededata is
possible, it means that theesompression is deficient. However, most
7c7
< compress out. Indeed, few compressors are capable of even so much as
---
compress out. Indeed, fewesompressors are capable of
even so much as
9c9
< corrupting the compressed form usually results not in valid but
---
corrupting theesompressed form usually results not in
validebut
Obviously, there was redundancy lurking in the compressed form, and
that redundancy is what my suggested recovery tactics leverage.
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
7:35 p.m.
der Mouse wrote:
And compress (.Z) compression still leaves a lot of
redundancy in the
compressed data.
Actually, it doesn't -- you can't compress a .Z very well. What I think
you're
getting at is that, since the source data has a lot of redundancy *and* is
human parsable, it can be reconstructed more easily in the case of mangled data.
>Yes; to the extent that recovery from
corruptedesompressededata is
>possible, it means that theesompression is deficient. However, most
You changed only one bit, which changed one code into another. This is a
reversable transform. I would suggest REMOVING one bit -- it is still a
single-bit error, but you will see the entire file become corrupt all the way
down the line.
--
Jim Leonard (trixter at oldskool.org) http://www.oldskool.org/
Want to help an ambitious games project? http://www.mobygames.com/
Or check out some trippy MindCandy at http://www.mindcandydvd.com/
7:55 p.m.
And compress
(.Z) compression still leaves a lot of redundancy in
the compressed data.
Actually, it doesn't -- you can't compress a .Z very
well. What I think you're getting at is that, since the
source data has a
lot of redundancy *and* is human parsable, it can be reconstructed
more easily in the case of mangled data.
Well, yeah; "is human parsable" is a form of redundancy, but one that
is almost impossible for programs to take advantage of - certainly
impossible for current programs. That's (part of) why my suggestions
for recovering from a damaged .Z file keep a human in the loop - to
leverage the human ability to detect bogus decompressions based on
redundancy programs have trouble using.
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
11:15 p.m.
der Mouse wrote:
Actually, WinRK uses a dictionary to currently achieve the very best Calgary
Corpus score, so it is most definitely exploitable.
--
Jim Leonard (trixter at oldskool.org) http://www.oldskool.org/
Want to help an ambitious games project? http://www.mobygames.com/
Or check out some trippy MindCandy at http://www.mindcandydvd.com/
As a simple example, if the high bit of a compressed
codon is 1, the
next bit is significantly more likely to be 0 than 1 - at least until
the table fills up. For a more complex example, consider the Shannon
estimate of one bit per letter for normal connected English text. At
With all due respect, we're talking about LZW, not Shannon's english language
estimate -- I don't think your comments are appropriate in the context of this
discussion. Pop on over to comp.compression and I'd be happy to discuss the
amount of entropy present in human language, but once data gets transformed by
LZW it has very little entropy left. (If it didn't, by your argument, you
could still recompress it with a bitwise encoder like PAQ -- you can't (by a
significant margin, anyway)).
What I think
you're getting at is that, since the source data has a
lot of redundancy *and* is human parsable, it can be reconstructed
more easily in the case of mangled data.
Well, yeah; "is human parsable" is a form of redundancy, but one that
is almost impossible for programs to take advantage of - certainly
11:28 p.m.
[...], but once data gets transformed by LZW it has
very little
entropy left.
I'm not sure what you mean by "entropy" here. The
information-theoretic meaning I know is diametrically opposed to the
sense in which you're using it (by it, highly compressed data has much,
not little, entropy - almost as many bits of entropy, of information
content, as it has surface bits). This is why I consistently use
"redundancy" below.
(If it didn't, by your argument, you could still
recompress it with a
bitwise encoder like PAQ -- you can't (by a significant margin,
anyway)).
That's only because the encoder isn't smart enough to take advantage of
the redundancy that's there. When I say redundancy is present, I am
speaking from an information-theoretical standpoint; the presence of
redundancy does not mean that any particular compression algorithm can
squeeze it out. Saying that no encoding software exists that can
compress some data blob, *even if true*, does not mean that there is no
redundancy in it, only that - if there is any - no extant software
knows how to find it and compress it out.
For example, I can produce effectively unlimited amounts of data that
has very little information content but which I defy any program to
compress significantly. All I need to do is pick a random key and
encrypt a stream of all-0-bits with that key using some decent
algorithm (3DES, IDEA, arcfour, whatever). Only a few bits of
information content (the size of the key, basically) but about as
uncompressible as it gets.
Well, yeah;
"is human parsable" is a form of redundancy, but one
that is almost impossible for programs to take advantage of -
Actually, WinRK uses
a dictionary to currently achieve the very best
Calgary Corpus score, so it is most definitely exploitable.
7106
days inactive
7108
days old
12 comments
6 participants
participants (6)
-
eric＠brouhaha.com -
frustum＠pacbell.net -
jpl15＠panix.com -
julesrichardsonuk＠yahoo.co.uk -
mouse＠Rodents.Montreal.QC.CA -
trixter＠oldskool.org