Compression - Seeking into a deflated stream

Author

Seeking into a deflated stream

Thomas

2008-02-15, 3:56 am

Hi,

I wonder if it is possible to s

into a deflated stream without
inflating it.
I thinking about s

ing into zipped textures, which contain mipmaps I
don't necessarily want to uncompress.

Has anyone an idea ?

Thanks
Tom

Thomas Pornin

2008-02-15, 7:56 am

According to Thomas <thobuc@gmail.com>:
> I wonder if it is possible to s

into a deflated stream without
> inflating it.

Generally speaking, no. You may _recover_ from a damaged stream by
locating the headers for uncompressed blocks, but there is no generic
way for knowing from where those blocks come within the uncompressed
stream.

However, if you do control the compression process, then you can
include "full sync" points between some mipmaps, and create an index
table to unambiguously locate those sync points in the compressed
stream. A "full sync" point entails closing the current deflate block,
adding a zero-length uncompressed block, and forgetting previous data
for LZ77 processing; this ensures byte alignment and lossless data
s

ing.

--Thomas Pornin

Stefano Brocchi

2008-02-16, 7:56 am

Hello,

> I wonder if it is possible to s

into a deflated stream without
> inflating it.

I'm quite sure that in some cases it is possible to make searches in
compressed zip files without entirely decompressing the file. I'm not
sure of how this is done, but I imagine since zip files contain
pointers to already-seen strings then decompression of many of them
could be avoided gathering information on these: surely they cannot
contain the s

ed string or the search would have successfully ended,
so info could be if they start with the suffix of the searched string
or if it ends with a prefix of it. Maybe such info should be saved for
every seen character in the sliding window as two integers ? At the
end the position of the string could be found simply keeping track of
the scanned bytes and of the length of the sequences. Of course this
is very far to a definition of an algorithm, but I think something
based on this idea has been studied.

> I thinking about s

ing into zipped textures, which contain mipmaps I
> don't necessarily want to uncompress.

In your case I think the major problem is the bidimensional nature of
your data, as zip treats data sequentially as if it was 'flat'. I'm
not sure of what you are searching (I know nothing about mipmaps) but
if you are searching an image inside another image, you could search a
row of it and if you find it decompress the file only from that point
on.

So long,
Stefano

Phil Carmody

2008-02-16, 7:56 am

Thomas <thobuc@gmail.com> writes:
> Hi,
>
> I wonder if it is possible to s

into a deflated stream without
> inflating it.
> I thinking about s

ing into zipped textures, which contain mipmaps I
> don't necessarily want to uncompress.
>
> Has anyone an idea ?

Well, if order to skip a run of X bytes from the sliding window,
you don't actually care what those X bytes were, only that
there are X of them, and thus you're X bytes closer to where
you want to s

to. But you still need to procede through
the stream serially, even if you throw away half of the tokens
decoded.

Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration

Mark Adler

2008-02-16, 9:58 pm

You can't ignore the sliding dictionary while scanning a deflate
stream, since the matched string data may propagate through several
matches from the very beginning of the stream. All of the inflate
processing must be done must be done from the beginning to the s

point, e.g. decoding the codes and writing the literals and matching
strings, in order to maintain the sliding dictionary.

Thomas Pornin answered the question correctly, which is that the only
way to s

and avoid processing the deflate stream from the beginning
is if you have control over the generation of the deflate stream and
occasionally insert synchronization points that throw away the sliding
dictionary.

Stefano Brocchi

2008-02-16, 9:58 pm

I found an article about searching in files compressed with LZ-based
techniques. I haven't read it all, but probably it could be of use at
least for some ideas. The link:

http://www.dcc.uchile.cl/~gnavarro/...re/lzgrep.ps.gz

So long,
Stefano

Thomas

2008-02-25, 6:57 pm

On 16 f=E9v, 21:23, Stefano Brocchi
<stefano.broc...@researchandtechnology.net> wrote:
> I found an article about searching in files compressed with LZ-based
> techniques. I haven't read it all, but probably it could be of use at
> least for some ideas. The link:
>
> http://www.dcc.uchile.cl/~gnavarro/...re/lzgrep.ps.gz
>
> So long,
> Stefano

Hi,

Thanks for all answers !
=46rom what I've read, I cannot do what I need to without having a
custom zip format that will not be readable by other zip software.
I'll see if I want to keep the compatibility with the standard or not.

Sincerly,
Thomas

Thomas

2008-02-25, 6:57 pm

Mark Adler

2008-02-25, 6:57 pm

On Feb 25, 8:23=A0am, Thomas <tho...@gmail.com> wrote:
> From what I've read, I cannot do what I need to without having a
> custom zip format that will not be readable by other zip software.

No, that's not the case. You can create s

able data in the zip
format and remain completely compatible. The point is that you need
to create or convert the file in a special way in order to be
s

able. It will still be readable and unzippable by other zip
software.

Mark

Sponsored Links