Page 2 of 2 FirstFirst 12
Results 31 to 41 of 41

Thread: Spec for portable PAQ

  1. #31
    Member
    Join Date
    May 2008
    Location
    brazil
    Posts
    163
    Thanks
    0
    Thanked 3 Times in 3 Posts

    contact sflc

    Quote Originally Posted by Matt Mahoney View Post
    If I knew how. I suppose I could write a letter to USPTO but I can't find any information on the procedure. If the examiners are doing their job they should reject it. But it is easier for them to grant a patent than do research and fight with the applicant. That's why we have idiotic patents like the combover.
    http://www.google.com/patents?vid=USPAT4022227
    Contact Software Freedom law center for more help:
    http://www.softwarefreedom.org/about/contact/

  2. #32
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    OK, I figured it out. I just needed the address to write to.
    http://www.uspto.gov/web/offices/pac...tm#sect1901.03

    Thanks for all the help.

  3. #33
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,943
    Thanks
    293
    Thanked 1,286 Times in 728 Posts
    Meanwhile, the spec reached v14... and lost some useful explanations on the way,
    while getting more scary pseudocode.
    Is it related to this patenting discussion, i wonder?
    Well, I have all the versions anyway...

  4. #34
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    Well, now up to version 17, probably with more to come. I decided to put the compressor documentation in a different file that I will release along with the compressor when it is done. I want to make sure that it is possible to implement the standard from the spec alone.

    One major change is I took out the complicated context hashing functions and replaced it with a general purpose programming language (pseudo-assembler for speed) which will be much more flexible. It looks like I can write all the contexts I had before in this language with just a few instructions. I figure the interpreter will run about 1/4 to 1/2 the speed of compiled code. That's not a big problem because the hashing is only done once per byte. In my tests with the old hash functions, the time was insignificant. After I play with it awhile I might add a few more instructions to speed up common operations like I did with the HASH and HASHB instructions.

    I also added an ISSE component (like paq9a) and a BWT transform. The ISSE is a cascading indirect context model (with bit histories) that mixes the output of the previous stage. In my experiments it is getting very good compression, so much that you can't improve on it much with SSE (which I might ultimately take out if that is the case).

    There was a major architectural change where the components communicate stretched probabilities. It is faster this way (the mixer just does linear averaging) and gets better compression because the predictions aren't clamped. In my tests, the Calgary corpus takes about 2 seconds per component with assertion checking on.

    The architecture seems ideal for a polymorphic array of components with virtual predict() and update() functions. But for speed, that's not how I did it. A component is monolithic. It has enough state to do everything. The predict() and update() functions use a switch inside of a loop that switches on the type and does all the code inline. The code for each component is fairly short, like in the spec.

  5. #35
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,012
    Thanks
    399
    Thanked 398 Times in 152 Posts
    Why do such customizable hashing? Maybe easier and better to use a few or just one predefined hash functions with some parameters - i.e. how many bytes to hash?..

  6. #36
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    You can write contexts for very specific file types, like high order bits of differences of nearby pixels in uncompressed video depending on stuff in the header, etc. You could (in theory) write a context function that decodes JPEG huffman coding so your context includes where you are in the DCT zigzag coefficient sequence. It is like embedding the decompression algorithm in the archive. The decompressor you have today (or next month...) would be able to read compressed files that use algorithms developed years in the future.

    I will probably make one more change where the context array H[0...255] is general purpose memory and the components each select which element they use as context. I will need to run performance tests first. It will probably add a few nanoseconds per byte per component, not a big increase, but allow easier program development.

  7. #37
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    Adding component pointers to H didn't hurt speed any, so I added it. Also, I took out the ad-hoc transforms like E8E9 and CAP and generalized it with a transform consisting of a ZPAQL program header (that's what I call the pseudo-assembler) followed by the transformed data. The transform consists of running the program on each input byte of data and adding an OUT instruction. The registers point to a working buffer of bytes instead of a hash array, but it is basically the same instruction set. Transforms like E8E9 and CAP are short programs instead.

    http://cs.fit.edu/~mmahoney/compression/zpaq1.pdf

  8. #38
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    Update: I have implemented the ZPAQL virtual machine and it appears to be 7-8 times slower than optimized C++. As a test, I implemented a ZPAQL program to convert text to upper case. It is called once per input byte with the input in the A register. It converts enwik8 to upper case in 8 seconds. An equivalent C++ program took 1 second.
    Code:
        a<97  (input byte is in A)
        jt 6
        a>122
        jt 2
        a&~32
        out  (jump here is a<97 or a>122 and output A)
        halt
    Next I wrote a CAP transform. In ZPAQ, the compressor would replace uppercase letters with an escape character followed by the lowercase letter, then append a header to the output with a program to reverse the transform. I used 33 ("!") as the escape byte. The reverse transform looks like this:

    Code:
        jf 5  (flag F is true if last byte was an escape)
        a^=32
        out
        a<a (set flag to false for next time)
        halt
        a==33  (jump here for normal case)
        jt 1  (skip output if A is an escape)
        out
        halt
    The transform in C++ takes 1 second on enwik8 and expands the output about 3%. The inverse transform takes 7 seconds to restore the original file. The header adds 13 bytes for the program, 2 bytes for the program size and 1 byte to indicate that a program is present. Instructions with numbers in them are 2 bytes, and the others are 1 byte.

    This is how the program is written. It treats parenthesis as comments. I am including 2 development tools as ZPAQ options. One compiles the program and steps through each instruction showing the register contents and a memory dump after each input byte (given as arguments) is processed. The second tool, which I used here, runs a program at full speed with an input and output file (or stdin/stdout). It calls the program once for each input byte.

    I still need to integrate this with the model which currently uses an older version of the context hash function. The new version uses two identical virtual machines, one to compute the context hashes and the second as a postprocessor. The machine is implemented as a giant switch statement taking the opcode as input. I wrote a Perl script to generate the C++ interpreter code from table 1 of the ZPAQ spec. Likewise I wrote another script to generate the symbol table for the compiler. I wrote most of it in half a day yesterday, and spent today mostly testing and making minor improvements (like adding a condition flag F to the machine state). The toughest part was designing the instruction set.

    I have figured out how to write more complex transforms in ZPAQL like E8E9, dictionary, and LZP, but haven't written them yet. The first version of ZPAQ will probably not include these transforms, but I can always add them later without breaking compatibility.

    If you are worried about speed, note that you can always optimize the decompressor by looking for specific programs in the headers. Or another way might be for the decompressor to read the header, convert it to C (fairly straightforward), compile it with an external compiler to a DLL, load it, and run it. No, I am not working on that approach.

  9. #39
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Your VM code can be translated to assembler almost instruction by instruction. Why not generate simple x86 code from it *in place* and call it? It'll make things several times faster. I dunnot know if there is a portable way to make a memory chunk executable, though.

  10. #40
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    Portability is one problem. I want the format to be machine independent. Another is security. If you could embed x86 code to be executed there is no way to know if it has a trojan or virus. With a VM in a sandbox the code must be safe. Also, the VM code can be compiled with a JIT compiler by the decompressor like with Java bytecode. The x8 slowdown is for purely interpreted code, similar to the slowdown for early Java interpreters. It is still fast compared to CM modeling.

  11. #41
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I meant the (de)compressor generates the ASM code from your VM code, which is stored in the archive. Not to store ASM code within the archive.

    This way you can make it safe, but that'd require to write a simple assembler.

Page 2 of 2 FirstFirst 12

Similar Threads

  1. PAQ turns up in the most unlikely places
    By willvarfar in forum Data Compression
    Replies: 0
    Last Post: 27th May 2010, 10:19
  2. Paq mixer theory
    By Shelwien in forum Data Compression
    Replies: 0
    Last Post: 22nd November 2009, 01:32
  3. can someone help me compiling paq by myself?
    By noshutdown in forum Forum Archive
    Replies: 4
    Last Post: 4th December 2007, 09:49
  4. New fast open-source paq-based jpeg compressor
    By Bulat Ziganshin in forum Forum Archive
    Replies: 14
    Last Post: 13th September 2007, 13:57

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •