Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2164 > unrolled thread

Harry Potter: my progress with compression

Back to article view | Back to comp.compression

Contents

  Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2013-12-17 11:19 -0800
    Re: Harry Potter: my progress with compression earl_colby_pottinger@yahoo.com - 2013-12-17 14:21 -0800
      Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2013-12-18 06:20 -0800
        Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-01-21 08:18 -0800
          Re: Harry Potter: my progress with compression BGB <cr88192@hotmail.com> - 2014-01-21 13:54 -0600
            Re: Harry Potter: my progress with compression glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-01-21 22:37 +0000
              Re: Harry Potter: my progress with compression BGB <cr88192@hotmail.com> - 2014-01-21 20:27 -0600
                Re: Harry Potter: my progress with compression glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-01-22 03:55 +0000
                  Re: Harry Potter: my progress with compression Robert Wessel <robertwessel2@yahoo.com> - 2014-01-21 23:59 -0600
                  Re: Harry Potter: my progress with compression BGB <cr88192@hotmail.com> - 2014-01-22 02:35 -0600
    Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-01-28 10:38 -0800
      Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-02-10 07:20 -0800
        Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-02-24 09:13 -0800

#2164 — Harry Potter: my progress with compression

Okay.  The last time I had access to my compression software--last Thanksgiving weekend--I improved the software a lot and transferred some code snippets to a flash drive for printing at the library--my only computer with access to a printer broke :'(.  So far, so good--now my technique shows better numbers than Deflate on most files.  After the printing--last Thursday--I perused the paperwork and found a lot of logic errors along with some performance tweaks and optimizations.  I don't yet know how or if it works, and I won't know until I return to my mother's house--my only programming computer is there and I don't always have the option to go there.  Anyway, I am still working hard on it.

BTW, what audience do I have for file compression?  I lost my two main reasons for it myself, but it would be useful to put more stuff on removable media--especially a floppy disk--or a server.  It could also improve the data transfer rate of dial-up internet access.  If you have a lot of large computer games, it also might help.

[toc] | [next] | [standalone]

#2165

Why don't you have your own machine?  The Aspire One I am using right now costed me $219.00 new, you can get some used laptops for about $100 (two generations old) or a used desktop for $50.00


In-fact one of my desktops cost me nothing as I recovered for the local dump for some parts and it turned out to have nothing wrong with it but the Windows installed on it. Look around, there are some cheap machines out there.

[toc] | [prev] | [next] | [standalone]

#2167

On Tuesday, December 17, 2013 5:21:06 PM UTC-5, earl_colby...@yahoo.com wrote:
> Why don't you have your own machine?  The Aspire One I am using right now costed me $219.00 new, you can get some used laptops for about $100 (two generations old) or a used desktop for $50.00
> 
I do.  Unfortunately, I'm not allowed to use my computer at home; I lost some computer privileges at my day program, and my mother's WinVista computer's totally broken.  So, I am forced to use my mother's Win98 computer.  It can still do the job, but I can only go to her house once every few weekends.

> In-fact one of my desktops cost me nothing as I recovered for the local dump for some parts and it turned out to have nothing wrong with it but the Windows installed on it. Look around, there are some cheap machines out there.

I may be getting a used laptop soon.  :)

[toc] | [prev] | [next] | [standalone]

#2198

Update: I am debugging now, but the numbers so far are only marginally better than Deflate.  :(

[toc] | [prev] | [next] | [standalone]

#2199

On 1/21/2014 10:18 AM, Harry Potter wrote:
> Update: I am debugging now, but the numbers so far are only marginally better than Deflate.  :(
>

Deflate is kind of hard to really beat out significantly short of huge 
dictionaries and matches (and a data-set prone to said matches), and or 
throwing an expensive entropy-coding scheme at it (such as arithmetic 
coding).


for example, I got some (modest) compression gains recently with a 
recent format, I suspect mostly due to the larger dictionary, and 
possibly specifics of the format being compressed (video frames).

it also gains some (slightly) via use of an arithmetic coder, but this 
does not come free:
in the profiler, around 45% of the running time is spent in the 
arithmetic decoder: ~35% in the function that reads a bit and updates 
the probability, and ~10% in the function to re-normalize.

it is, I suspect, mostly due to branch mis-predictions in this case 
(there is an "if()" branch to update a few variables and the model 
depending on the input bit).


so, for performance-sensitive cases, probably back to Huffman.
well, and/or use a codec design sufficiently expensive to decode that it 
mostly hides the cost of the AC (and if it gets extra bad, they resort 
to a multithreaded decoder or similar...).

still have it decoding now at 210 Mpix/sec for a single-threaded decoder 
with AC enabled (and 730 Mpix/sec for multithreaded), so probably not 
too horrible.

[toc] | [prev] | [next] | [standalone]

#2200

BGB <cr88192@hotmail.com> wrote:

(snip)

> Deflate is kind of hard to really beat out significantly short of huge 
> dictionaries and matches (and a data-set prone to said matches), and or 
> throwing an expensive entropy-coding scheme at it (such as arithmetic 
> coding).
 
> for example, I got some (modest) compression gains recently with a 
> recent format, I suspect mostly due to the larger dictionary, and 
> possibly specifics of the format being compressed (video frames).
 
> it also gains some (slightly) via use of an arithmetic coder, 
> but this does not come free:

Some time ago, I was comparing JBIG2 to LZW for bit image
compression for PDFs. JBIG2 compresses better, but is noticeably
slower to decompress. (To compress, too, but one assumes it will
be decompressed more times.) 

When viewed with Adobe Reader, the LZW images update about as
fast as you can watch them, but for JBIG2, you can see the delay.

The arithmetic coder words on one bit at a time, where LZW 
processes the input one byte at a time. 

> in the profiler, around 45% of the running time is spent in the 
> arithmetic decoder: ~35% in the function that reads a bit and updates 
> the probability, and ~10% in the function to re-normalize.

I din't profile it, but that sounds about like I might expect.
 
> it is, I suspect, mostly due to branch mis-predictions in this case 
> (there is an "if()" branch to update a few variables and the model 
> depending on the input bit).
 
> so, for performance-sensitive cases, probably back to Huffman.
> well, and/or use a codec design sufficiently expensive to decode that it 
> mostly hides the cost of the AC (and if it gets extra bad, they resort 
> to a multithreaded decoder or similar...).

I still like LZW, but it depends a lot on the actual data.
 
> still have it decoding now at 210 Mpix/sec for a single-threaded decoder 
> with AC enabled (and 730 Mpix/sec for multithreaded), so probably not 
> too horrible.

Sounds about right. 15Mpix for an 8.5x11 page at 400dpi. My computer
might be slower, too.

-- glen

[toc] | [prev] | [next] | [standalone]

#2201

On 1/21/2014 4:37 PM, glen herrmannsfeldt wrote:
> BGB <cr88192@hotmail.com> wrote:
>
> (snip)
>
>> Deflate is kind of hard to really beat out significantly short of huge
>> dictionaries and matches (and a data-set prone to said matches), and or
>> throwing an expensive entropy-coding scheme at it (such as arithmetic
>> coding).
>
>> for example, I got some (modest) compression gains recently with a
>> recent format, I suspect mostly due to the larger dictionary, and
>> possibly specifics of the format being compressed (video frames).
>
>> it also gains some (slightly) via use of an arithmetic coder,
>> but this does not come free:
>
> Some time ago, I was comparing JBIG2 to LZW for bit image
> compression for PDFs. JBIG2 compresses better, but is noticeably
> slower to decompress. (To compress, too, but one assumes it will
> be decompressed more times.)
>
> When viewed with Adobe Reader, the LZW images update about as
> fast as you can watch them, but for JBIG2, you can see the delay.
>
> The arithmetic coder words on one bit at a time, where LZW
> processes the input one byte at a time.
>

yeah.


with both Deflate and BTLZA in Huffman-only mode, it basically encodes 
each literal symbol at once, using a Huffman code. so, it is basically a 
few shifts and bit-operations.

this basically consists of writing a sequence of bits all at once.

for decoding, it will "peek" 8 bits, fetch a symbol from a table and see 
if it is a match, and otherwise peek 16 bits, and check the symbols with 
the given 8-bit prefix. after finding the correct symbol, it will 
advance forward N bits (and as-needed, the "bit window" will be shifted 
over, and encoded bytes will be pulled in).

most of the time, the symbol will match exactly (also, making this table 
any larger tends to make the decoder slower, apparently due to an 
increase in cache-misses...).


Arithmetic Mode A is basically similar, just rather than bytes going 
to/from the output buffer, then are fed-into / pulled from the 
arithmetic coder.


Arithmetic Mode B differs slightly in that it does not use the "bit 
window" (does bit-by-bit I/O directly), and uses multiple context models.

however, as-is, there is the issue as to how to best match the encoded 
Huffman symbols, where one doesn't know the number of bits in advance, 
and where you can't simply decode extra bits and be like "oh, 
never-mind" in this mode. currently this involves kind of a dead-slow 
"snapshot" mechanism, but is likely to be replaced by decoding symbols 1 
bit at a time in this mode (should be faster in this case).


>> in the profiler, around 45% of the running time is spent in the
>> arithmetic decoder: ~35% in the function that reads a bit and updates
>> the probability, and ~10% in the function to re-normalize.
>
> I din't profile it, but that sounds about like I might expect.
>

yeah...

it is sad when the AC related functions basically use more CPU time than 
*pretty much everything else* in a video codec...

granted, the rest of the codec is designed mostly to be performance 
centric (I guess it is VQ based, but it is hard to classify exactly).


>> it is, I suspect, mostly due to branch mis-predictions in this case
>> (there is an "if()" branch to update a few variables and the model
>> depending on the input bit).
>
>> so, for performance-sensitive cases, probably back to Huffman.
>> well, and/or use a codec design sufficiently expensive to decode that it
>> mostly hides the cost of the AC (and if it gets extra bad, they resort
>> to a multithreaded decoder or similar...).
>
> I still like LZW, but it depends a lot on the actual data.
>

could be.

I haven't really evaluated LZW all that well.

in some tests I had done once before (years ago) LZ77 variants came out 
on top in terms of decode speeds, with LZP variants coming up a little 
behind (a little slower on the decode end than LZ77, but generally 
pretty fast WRT encoding).

in my tests with LZW in the past, I was unable to really get either 
particularly good speed or compression out of it (vs a more Deflate-like 
encoder).


generally, the cost from Huffman coding has been small enough to be 
passable (with a more notable reduction in terms of file-sizes), whereas 
AC has tended to be sufficiently slow to be difficult to justify vs the 
fairly small increase in compression over Huffman (like, 85kB vs 100kB, 
but taking several times longer to decode).


I suspect the AC may help though in terms that there is likely a lot of 
redundancy between adjacent symbols which Huffman can't really help with.

I had considered the possibility of using a PPM like strategy, but 
figured this would likely be fairly expensive (even vs an arithmetic 
coder), so opted with an AC-based stratrgy and trying to predict the 
following bits based on preceding bits.


>> still have it decoding now at 210 Mpix/sec for a single-threaded decoder
>> with AC enabled (and 730 Mpix/sec for multithreaded), so probably not
>> too horrible.
>
> Sounds about right. 15Mpix for an 8.5x11 page at 400dpi. My computer
> might be slower, too.
>

possible, but by the time it reaches the arithmetic coder, it is already 
a fraction of a bit-per-pixel on average...


so, as-is, it gets it from around 0.30 to 0.40 bpp (for a Deflate-based 
back-end), to around 0.15-0.25 bpp (for the LZ+AC based back-end).

as-is, it is around 1.0-2.0 bpp if no Deflate is used (for the data 
coming out of the codec front-end), and 8 (or 16) bpp for the 
intermediate "pixel blocks".

typically, the raw video frames though are around 2Mpix each (ex: 
1920x1080), so 210 Mpix/sec is roughly 105 frames/second at 1080p, or 
365 frames/second for decoding spread over 4 threads.

this being on a 3.4 GHz AMD Phenom II (with 16GB DDR3).


so, the front-end encoder looks something like:
1, transform pixel data into fixed-size pixel blocks (4x4 pixels in 128 
or 256 bits), which basically contain a pair of colors and bits used to 
interpolate between them (with the colors chosen based mostly on 
brightness);
2, quantize the pixel blocks, by finding cheaper ways to approximately 
represent these pixels (blocks from the prior frame, flat colors, 1bpp 
pixels, subsampled 2x2 pixel blocks, colors indexed into a 256-color 
palette, colors predicted from adjacent blocks, ...);
3, serialize the blocks into a sequence of commands representing this 
pattern of blocks;
4, pass off to backend.

back-end then works like:
1, do LZ77 stuff, finding and replacing repeating strings with 
dictionary references, ...
2, count up statistics for whatever symbols are present;
3, build Huffman tables, and encode these into the output;
4, encode LZ-compressed data into the Huffman coded output;
5, if AC is used, AC encode the output bits.


decoding then basically reverses the process, first decoding the 
command-sequence, then basically "unpacking" the commands into a 
sequence of blocks (in one of several block formats).

most of this unpacking basically consists of lots of memory-copying and 
table-driven operations (feeding bytes through tables to indices into 
other tables, ...). some of the tables are static and prebuilt, others 
are transmitted in-stream (such as any color-palettes used), and others 
are built as the frame is decoded (such as "mode transition tables", ... 
where basically the coded image represents a finite-state-machine, with 
the modes indicating at which point which pixel-block formats and 
color-formats and similar will be used for various commands, ...).


these blocks may then be converted back into RGBA, which basically 
consists of:
if flat colored block:
     unpack color into RGBA;
     fill output block with this color.
convert ColorA and ColorB back their RGBA values;
calculate intermediate colors (into a table);
use pixel-bits for each pixel to pick the color from the table, which is 
then copied to the output pixel.


generally, my main decoder loops target output block-formats though 
which can be used more directly by the GPU, as going all the way to RGBA 
is generally less efficient than going to a compressed-texture format 
used by the graphics hardware (though, not all hardware supports the 
same output formats, ...).

[toc] | [prev] | [next] | [standalone]

#2202

BGB <cr88192@hotmail.com> wrote:

(snip)
> however, as-is, there is the issue as to how to best match the encoded 
> Huffman symbols, where one doesn't know the number of bits in advance, 
> and where you can't simply decode extra bits and be like "oh, 
> never-mind" in this mode. currently this involves kind of a dead-slow 
> "snapshot" mechanism, but is likely to be replaced by decoding symbols 1 
> bit at a time in this mode (should be faster in this case).

Never having actually written one, I always figured you would use
a lookup table with input width the size of the longest symbol,
though that makes a large table. That assumes speed is more
important than memory use.
 
> it is sad when the AC related functions basically use more CPU 
> time than *pretty much everything else* in a video codec...
 
> granted, the rest of the codec is designed mostly to be performance 
> centric (I guess it is VQ based, but it is hard to classify exactly).

I was thinking once about the two main uses of compression, 
distribution of software packages and backups.

For distribution, you compress once and uncompress many times.
For backups you compress once and rarely uncompress.

Some algorithms might compress faster than they decompress,
or vice versa, and so be better for one case than the other.

-- glen

[toc] | [prev] | [next] | [standalone]

#2203

On Wed, 22 Jan 2014 03:55:53 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:


>I was thinking once about the two main uses of compression, 
>distribution of software packages and backups.
>
>For distribution, you compress once and uncompress many times.
>For backups you compress once and rarely uncompress.
>
>Some algorithms might compress faster than they decompress,
>or vice versa, and so be better for one case than the other.


I'm not so sure about the backups.  Usually you have a reasonable time
for performing the backups, and a certain amount of flexibility
(assuming a decent backup system that isn't forcing your system to be
unavailable during the backup).  But when you need to do a big restore
is when performance is really critical (since you've probably got
something down for the duration).

Still there are certainly backup systems that have made the tradeoff
to improve backup performance while worsening restores.  Image backups
as a whole, for example (at least when you're not doing an image
restore).

[toc] | [prev] | [next] | [standalone]

#2204

On 1/21/2014 9:55 PM, glen herrmannsfeldt wrote:
> BGB <cr88192@hotmail.com> wrote:
>
> (snip)
>> however, as-is, there is the issue as to how to best match the encoded
>> Huffman symbols, where one doesn't know the number of bits in advance,
>> and where you can't simply decode extra bits and be like "oh,
>> never-mind" in this mode. currently this involves kind of a dead-slow
>> "snapshot" mechanism, but is likely to be replaced by decoding symbols 1
>> bit at a time in this mode (should be faster in this case).
>
> Never having actually written one, I always figured you would use
> a lookup table with input width the size of the longest symbol,
> though that makes a large table. That assumes speed is more
> important than memory use.
>

when working with raw bits, that is a viable strategy...

I generally only use a partial table (8-bit lookup), mostly as in my 
experience, the cost in terms of L1 and L2 misses from a 12-bit or 
16-bit lookup table outweighs any gains from the larger table, and 
typically in the fallback case, you are looking at a fairly small number 
of symbols anyways...


the problem though is when the Huffman coder is running on top of a 
bitwise arithmetic coder which uses multiple contexts:
you can't safely over-read because then the bits past the end will have 
been read with the wrong context, and the AC's context weights will now 
have been messed up, ...

basically, this means one of:
some mechanism to rewind the operation (expensive);
compensating for any over-read on the encoder end (ugly);
having the decoder always read the exact number of bits.

so, the advantage of decoding the symbol a bit at a time on top of the 
AC is mostly that it avoids over-reading (and thus the need for any sort 
of rewind mechanism or similar).

another possible option would be always reading a fixed number of bits, 
and thus relying solely on the arithmetic coder for entropy coding.


this issue is N/A for "Arithmetic Mode A", which only uses a single 
context model, thus rendering the over-read issue N/A.


some of this basically works by swapping out the vtables used for a lot 
of the bitstream operations (depending on stream mode).

so, changing the stream mode doesn't just involve a little hackery to 
basically reinitialize the bitstream and similar, but also swaps out a 
lot of the functions and similar.

nevermind if "Mode B" actually swaps out a pretty large part of the 
logic to try to make this stuff work.



>> it is sad when the AC related functions basically use more CPU
>> time than *pretty much everything else* in a video codec...
>
>> granted, the rest of the codec is designed mostly to be performance
>> centric (I guess it is VQ based, but it is hard to classify exactly).
>
> I was thinking once about the two main uses of compression,
> distribution of software packages and backups.
>
> For distribution, you compress once and uncompress many times.
> For backups you compress once and rarely uncompress.
>
> Some algorithms might compress faster than they decompress,
> or vice versa, and so be better for one case than the other.
>

I am mostly using my compressors mostly for asset data and video and 
similar.

also some other things (such as terrain voxel data) are compressed, but 
the encoding/decoding is speed sensitive, mostly as it is essentially a 
form of RAM compression (mostly due to working with data bigger than a 
32-bit address space within the confines of said 32-bit address space).


typically for file distribution, speed is less important, since it is 
more or less decompressing at the speed of user patience and/or HDD I/O 
speeds...

like, it doesn't matter as much, if the HDD goes at 100MB/s, then one 
can't really make it any faster. well, that is if you are lucky, if 
writing lots of small files, the actual I/O speed the OS can give is 
generally *much* slower. (well, unless one has RAID or SSDs or 
something...).


in contrast, some of what is being dealt with in video stuff (at higher 
resolutions) is generally somewhat in excess of HDD I/O speeds, so it is 
basically data at levels where it couldn't really be read-from or 
written to the HDD in real-time if one were working with uncompressed video.

and, generally for things like real-time screen capture and similar, it 
is necessary to compress the video before writing it to the HDD.


like, consider one is doing screen capture at 1680x1050 at 30fps:

raw video: 212MB/sec (wont go onto HDD, would be 12.7GB per minute).
if it can be dropped down to 6 bpp: 40MB/sec (steep, but the HDD can do 
it, roughly works out to 2.4GB per minute);
if down to 2 bpp: 14MB/sec (a lot better, a person might almost not 
notice that 900MB per minute of video);
what about 0.5 bpp? then it is 210MB per minute;
and 0.25? 105MB per minute.
and 0.06? 26MB per minute (basically, this is what a lot of the YouTube 
videos seem to be).


although, luckily, at the AC stage, the data is already compressed down 
pretty far.

well, and it is already squeezed down pretty far by the time it hits the 
LZ compressor and similar as well.


or such...

[toc] | [prev] | [next] | [standalone]

#2205

I have another idea which might help, but it's classified.  For now I just want to get it to work and then make it more efficient.

[toc] | [prev] | [next] | [standalone]

#2219

So, I tried a new concept in compression, and it seems to work.  As of now, the ratio jumped by more than 2%.  However, the compression ratio for archive files is unrealistically good.  I think I have an idea what the bug is but not where.

[toc] | [prev] | [next] | [standalone]

#2235

On Monday, February 10, 2014 10:20:59 AM UTC-5, Harry Potter wrote:
> So, I tried a new concept in compression, and it seems to work.  As of now, the ratio jumped by more than 2%.  However, the compression ratio for archive files is unrealistically good.  I think I have an idea what the bug is but not where.

I have yet to debug the software, as I didn't yet get a chance to.  :(  However, I have a few new ideas to improve the codec and want to try them out.  BTW, IIRC, the ratio on the test file actually jumped a little over 3.5%  :)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web