Seeking into a deflated stream

Main Page | Report this Page

Science Forum Index » Compression Forum » Seeking into a deflated stream

Page 1 of 1

Author

Message

Thomas

Posted: Thu Feb 14, 2008 11:28 pm

Guest

Hi,

I wonder if it is possible to seek into a deflated stream without
inflating it.
I thinking about seeking into zipped textures, which contain mipmaps I
don't necessarily want to uncompress.

Has anyone an idea ?

Thanks
Tom

Thomas Pornin

Posted: Fri Feb 15, 2008 9:00 am

Guest

According to Thomas <thobuc@gmail.com>:

Quote:

I wonder if it is possible to seek 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
seeking.

--Thomas Pornin

Stefano Brocchi

Posted: Sat Feb 16, 2008 2:04 am

Guest

Hello,

Quote:

I wonder if it is possible to seek 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 seeked 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.

Quote:

I thinking about seeking 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

Mark Adler

Posted: Sat Feb 16, 2008 8:10 am

Guest

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 seek
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 seek 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.

Phil Carmody

Posted: Sat Feb 16, 2008 8:33 am

Guest

Thomas <thobuc@gmail.com> writes:

Quote:

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 seek 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

Stefano Brocchi

Posted: Sat Feb 16, 2008 10:23 am

Guest

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/software/lzgrep.ps.gz

So long,
Stefano

Thomas

Posted: Mon Feb 25, 2008 6:23 am

Guest

On 16 fév, 21:23, Stefano Brocchi
<stefano.broc...@researchandtechnology.net> wrote:

Quote:

Hi,

Thanks for all answers !
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.
I'll see if I want to keep the compatibility with the standard or not.

Sincerly,
Thomas

Thomas

Posted: Mon Feb 25, 2008 6:24 am

Guest

On 16 fév, 21:23, Stefano Brocchi
<stefano.broc...@researchandtechnology.net> wrote:

Quote:

Mark Adler

Posted: Mon Feb 25, 2008 8:50 am

Guest

On Feb 25, 8:23 am, Thomas <tho...@gmail.com> wrote:

Quote:

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 seekable 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
seekable. It will still be readable and unzippable by other zip
software.

Mark

Page 1 of 1 All times are GMT - 5 Hours The time now is Sat Sep 06, 2008 12:53 am Science Forum Index