How difficult is it to build a shrinking/deflating routine?

[MichaelW]

For that 1202 byte data block Winzip can compress it to 523 bytes (in a 641-byte archive), and RtlCompressBuffer can compress it to 666 bytes at standard compression and 659 bytes at maximum compression. I think run-length encoding will not compress it enough to be worth the effort.

In the Data Compression Handbook, Second Edition, Mark Nelson and Jean-Loup Gailly, 1996, M&T books, ISBN 1-55851-434-1, order 3 arithmetic coding produced the highest compression ratio for text files, as well as the highest overall ratio across text, graphics, and executable files, tested against Huffman, Adaptive Huffman, and several variants each of LZSS and LZW.

[Magnum]

I have some code that has the ability to zip/unzip directly in memory without any intermediate files.

Is that something that would be of help to you ?

Andy

[jj2007]

For that 1202 byte data block Winzip can compress it to 523 bytes (in a 641-byte archive), and RtlCompressBuffer can compress it to 666 bytes

Probably the best alternative to reinventing the wheel.

RtlCompressBuffer: Microsoft started to document it, as well as many other API, with the new SDK for Seven.

There is much better compression available, like FreeArc used in MasmBasic's ZipFiles, but the authors rarely offer (de)compression of a buffer.

[frktons]

I have some code that has the ability to zip/unzip directly in memory without any intermediate files.

Is that something that would be of help to you ?

Andy

Yes Andy, it is this kind of routine that I need to implement.
Thanks

[frktons]

RtlCompressBuffer
Probably the best alternative to reinventing the wheel.

There is much better compression available, like FreeArc used in MasmBasic's ZipFiles, but the authors rarely offer (de)compression of a buffer.

If I don't reinvent the wheel it is hard for me to learn some Assembly. :lol:
Good sort/zip/unzip algos are quite difficult to write, and a good dose of math
is usually necessary. Unfortunately I missed my dose.  ::)

I know, however, that you implemented a good one in MasmBasic.
It would be nice to see it in action with the string in the pgm that
I posted in this 3D.    :t

[FORTRANS]

Hi,

   Some data compression ratio data for text from "The
Data Compression Book", Mark Nelson, 1991, shows
Huffman about 40, Arithmetic about 40 to 70, LZSS about
55 to 60, and LZW about 50 to 60.  Higher numbers are
better ratios.  I did LZW for a GIF creation program and
part of a Huffman compressor to check the logic.  A
quick glance at my code shows the LZW at maybe three
times the size of the Huffman.  Hey guys, how would you
relate complexity to code size?

   MichaelW, my edition has 527 pages and 12 chapters, and
two appendices.  How does that compare to your copy?  He
did not have a chapter on Run Length Encoding.

   Dave, LZW for GIF files allow for 4,096 tokens, give or
take, some are predefined.  Which is 12 bits maximum.
The book above did up to 15 bit LZW.

   Frank, your text is short enough that straight LZW is
probably a poor match.  The more the token table is full
the better it compresses.  If have a lot of short pieces of
text, there are some "tricks" you can try to improve things.
Huffman is somewhat less size dependent for performance
(bigger is still better), but requires the decode table in the
compressed data hurting smaller files.

Regards,

Steve N.

[frktons]

   Frank, your text is short enough that straight LZW is
probably a poor match. 

Steve N.

I suppose you are right, Steve  :t

I think I'll use RtlCompressBuffer just to have some
algo to confront with, and afterwhile I'm going to try some
homemade code.

The task in itself is almost impossible to achieve with this
kind of text, but I'll give it a shot nevertheless. 

[Magnum]

Too big to post code, so there is an attachment.

It's in C++ but should be easy to convert.

Andy

[FORTRANS]

Hi,

   The tricks I mentioned involve compressing all ~30 pieces
of text as one piece to get enough data to compress well.
Then use some method to break out one of the 30 when
decompressing.  A couple of methods come to mind.
Neither seems easy right now.  And of course add code,
making it larger.

Regards,

Steve

[jj2007]

I know, however, that you implemented a good one in MasmBasic.
It would be nice to see it in action with the string in the pgm that
I posted in this 3D.    :t

That's feasible but doesn't make sense with such short strings. Here is a real example:

include \masm32\MasmBasic\MasmBasic.inc        ; download
        Init
        Let esi=FileRead$("\Masm32\include\Windows.inc")        ; get a string - could be from .data, too
        FileWrite "ZipTest.tmp", esi        ; write it to a file
        GetFiles "ZipTest.tmp"        ; load the Files$() array
        ZipFiles "ZipTest"        ; zip all files (it's exactly one, of course)
        Inkey "Check 'ZipTest.arc'"
        Exit
end start

Output:
FreeArc 0.666 creating archive: ZipTest.arc
Compressed 1 file, 977,412 => 145,460 bytes. Ratio 14.8%
Compression time: cpu 1.23 secs, real 1.33 secs. Speed 736 kB/s
All OK
Check 'ZipTest.arc'

For comparison: WinZip compresses to over 180k; however, the real surprise comes when you compress, say, all 1,000 assembler sources in Masm32 with FreeArc. See here for more info - attention, "Programs ... must finish the compression stage within 12h" is not a joke.

[dedndave]

i compressed it to 87% of the original size without writing any code   :lol:

original

MOVHLPS— Move Packed Single-Precision Floating-Point Values High to Low

MOVHLPS xmm1, xmm2

SSE

Description
-----------

This instruction cannot be used for memory to register moves.

128-bit two-argument form:
Moves two packed single-precision floating-point values from the high quadword of the second XMM argument
(second operand) to the low quadword of the first XMM register (first argument). The high quadword of the destination
operand is left unchanged. Bits (VLMAX-1:64) of the corresponding YMM destination register are unmodified.

128-bit three-argument form
Moves two packed single-precision floating-point values from the high quadword of the third XMM argument (third
operand) to the low quadword of the destination (first operand). Copies the high quadword from the second XMM
argument (second operand) to the high quadword of the destination (first operand). Bits (VLMAX-1:128) of the
destination YMM register are zeroed.

In 64-bit mode, use of the REX.R prefix permits this instruction to access additional registers (XMM8-XMM15).
If VMOVHLPS is encoded with VEX.L= 1, an attempt to execute the instruction encoded with VEX.L= 1 will cause
an #UD exception.

compressed

MOVHLPS— Move Packed Single-Precision Floating-Point Values High to Low

MOVHLPS xmm1,xmm2

SSE

Description:

cannot be used for memory to register moves

128-bit two-arguments:
Move two packed single-precision floating-point values from the high qword of the second XMM
reg operand to the low qword of the first XMM reg operand. The high qword of the destination
operand and Bits (VLMAX-1:64) of the corresponding YMM destination register are left unchanged.

128-bit three-arguments:
Move two packed single-precision floating-point values from the high qword of the third XMM reg operand
to the low qword of the first operand. Copies the high qword from the second XMM reg operand to
the high qword of the first operand. Bits (VLMAX-1:128) of the destination YMM register are zeroed.

In 64-bit mode, use of the REX.R prefix permits this instruction to access additional registers (XMM8-XMM15).
If VMOVHLPS is encoded with VEX.L= 1, an attempt to execute the instruction encoded with VEX.L= 1 will cause
an #UD exception.

[frktons]

It's in C++ but should be easy to convert.

Andy

Thanks Andy. I don't speak C++ but I'll check it anyway.

i compressed it to 87% of the original size without writing any code   :lol:

Compliments Dave, you got the real thing

That's feasible but doesn't make sense with such short strings. Here is a real example:

include \masm32\MasmBasic\MasmBasic.inc        ; download
        Init
        Let esi=FileRead$("\Masm32\include\Windows.inc")        ; get a string - could be from .data, too
        FileWrite "ZipTest.tmp", esi        ; write it to a file
        GetFiles "ZipTest.tmp"        ; load the Files$() array
        ZipFiles "ZipTest"        ; zip all files (it's exactly one, of course)
        Inkey "Check 'ZipTest.arc'"
        Exit
end start

Output:
FreeArc 0.666 creating archive: ZipTest.arc
Compressed 1 file, 977,412 => 145,460 bytes. Ratio 14.8%
Compression time: cpu 1.23 secs, real 1.33 secs. Speed 736 kB/s
All OK
Check 'ZipTest.arc'

For comparison: WinZip compresses to over 180k; however, the real surprise comes when you compress, say, all 1,000 assembler sources in Masm32 with FreeArc. See here for more info - attention, "Programs ... must finish the compression stage within 12h" is not a joke.

Thanks Jochen. Your implementation only write and read from files?
Usually all the algos use a temporary buffer. Isn't it available to your code?

[frktons]

Hi,

   The tricks I mentioned involve compressing all ~30 pieces
of text as one piece to get enough data to compress well.
Then use some method to break out one of the 30 when
decompressing.  A couple of methods come to mind.
Neither seems easy right now.  And of course add code,
making it larger.

Regards,

Steve

Thanks Steve. Probably it is out of my league to do something like that
in Assembly. By the way, considering the program could have dozens of
strings, it'd be useful to see how to put together the strings and to divide
them after the compression. ::)

[FORTRANS]

By the way, considering the program could have dozens of
strings, it'd be useful to see how to put together the strings and to divide
them after the compression. ::)

Hi,

  One way to do it with plain text is to use control codes
to separate the strings.  Use a zero to make it easy to
print, for instance.  Then make a routine to decode the
strings, count them, and print a specific string.

HTH,

Steve N.

[jj2007]

Thanks Jochen. Your implementation only write and read from files?
Usually all the algos use a temporary buffer. Isn't it available to your code?

There is much better compression available, like FreeArc used in MasmBasic's ZipFiles, but the authors rarely offer (de)compression of a buffer.