Page 3 of 3 FirstFirst 123
Results 61 to 84 of 84

Thread: Tornado 0.4

  1. #61
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by Shelwien
    Id say that most of "others work" value is motivational. As its generally easier to write something from scratch than decrypting the "others work".
    I completly agree.

    Imo, all these recriminations are hard to bear. Bulat, if you are sure, then please gather some bullet proof information and present it to the community - maybe as a single document or a web page. If there is hard evidence and not only indications everyone will believe you. On the other hand, maybe dnd can provide some code snippets or whatever to fortify his position. There must be a way to clear all these things up.

  2. #62
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Quote Originally Posted by Christian
    its generally easier to write something from scratch
    when youve studied a lot of others ideas, you can believe that you write something from scratch because you combine too much sources. but its not the same as lack of knowledge when someone says that he wrote even arithmetic coder himself. btw, are you wrote ari yourself?

    Quote Originally Posted by Christian
    please gather some bullet proof information
    its here - common match finder and set of coders

  3. #63
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    http://shelwien.googlepages.com/tor03lzt92.htm
    Switched to tor03 and added -s- and -s- -h64m variants.
    Still doesn't look similar, even not considering that lzturbo is
    twice slower at similar compression levels.

  4. #64
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by Bulat Ziganshin
    but its not the same as lack of knowledge when someone says that he wrote even arithmetic coder himself. btw, are you wrote ari yourself?
    Of course I did. And of course I did not reinvent arithmetic coding - I read several papers to get the idea and then implemented it myself.
    Stupid me, my first approach was even the classical one - with E1/E2 and E3 rescaling. I just dont understand why you think that writing huffman or arithmetic coders is so difficult.

    Quote Originally Posted by Bulat Ziganshin
    its here - common match finder and set of coders
    Imo, this is not proof, but indication.

  5. #65
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    > when you've studied a lot of others ideas, you can believe
    > that you write something from scratch because you combine
    > too much sources.

    "Sources" are only representations of some structures and ideas
    (I won't even say "algorithms" because a common-sense definition
    of algorithm supposes that there could be several different
    algorithms with the same output).
    And algorithms are normally written not by copy-pasting some
    existing sources, but by translating these ideas into a given
    language. So there is "writing from scratch" - actually its
    even possible to make an automated translator that would do that,
    knowing only the language syntax and not using any alternative
    implementation experience.
    But then, "ideas" are not absolute either - they're only
    derivatives of the problem we're solving. So, having an
    experience (=collection of ideas) might allow to find a
    solution more effectively (though such a solution generally
    wouldn't be optimal).
    Well, what I'm trying to say is that with such simple and
    strictly defined problems like source coding (=mapping of
    set of strings into a set of numbers) one doesn't really
    need any experience to find a solution, similar to already
    developed by someone. Instead, its commonly required to
    find your own solution for the problem to understand
    someone's implementation. And such an understanding is
    commonly needed almost for any code management, be it
    porting, speed/size optimizations, custom implementations
    or anything else.

    > but it's not the same as lack of knowledge
    > when someone says that he wrote even arithmetic coder
    > himself. btw, are you wrote ari yourself?

    I did. Because I didn't believe that available implementations
    weren't redundant, and the only reliable way to measure
    the supposed redundancy would be to find a really precise
    solution and compare.

    Btw, before that the same thing happened with huffman codes,
    where significantly better solution did exist... the nonprefix codes,
    although maybe impractical, do provide a better compression.

  6. #66
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Quote Originally Posted by Shelwien
    Well, what Im trying to say is that with such simple and
    strictly defined problems like source coding (=mapping of
    set of strings into a set of numbers) one doesnt really
    need any experience to find a solution, similar to already
    developed by someone.
    well, so why you dont wrote ppmonstr analog yourself?

  7. #67
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    If you didn't notice, I decompiled ppmonstr, so its not a problem to do
    the same thing as dnd, if only I wanted.
    Actually, I added missing orders there and replaced the rangecoder
    with less redundant, so in a way I already have my own "ppmonstr analog".
    And I know how to improve its compression too.
    But anyway its a lot of work, and not very creative at that, so boring.

    Also I don't have any use for universal compressors anymore.
    So what I mostly do is designing the custom models for specific data types.
    And there's a lot of work on improvement of model blocks like counters,
    mixers,mappings etc. Also I'm developing some model definition language.
    Such models have applications ranging from OCR to stock market trading.
    But it seems that nobody wants to discuss all that here.

    And as to applying my experience to universal compression... well, guess
    I'll do it eventually, if this forum would continue to exist long enough.
    I mean, I only work on it when I want to show something to people who
    talk to me, and that's rare.

    Edit: Here's what I was talking about:
    http://shelwien.googlepages.com/deppm.exe
    Hope Shkarin won't mind if its not sources.

  8. #68
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Quote Originally Posted by Shelwien
    Switched to tor03 and added -s- and -s- -h64m variants.
    first, i wonder how you tested - precompiled tor 0.3 binary doesnt support -s- option, are you compiled it yourself? second, for me its hard to understand your tables. ive experimented too - -58 mode looks close to "tor -9 -x- -s- -h64m -u1" with input data split into 16mb blocks, but still a bit worse - even with all tornado "optimizers" disabled

  9. #69
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    It did accept -s- with modes -1 to -4... guess it didn't work anyway...

  10. #70
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Quote Originally Posted by Shelwien
    It did accept -s- with modes -1 to -4... guess it didnt work anyway...
    -s- is default in these modes. so use big tor 0.4 executable which supports all the 120 algorithm variations anyway, it looks like only basic tornado MF is used in lzt, so only the coders question remains

  11. #71
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    Well, here's some lzturbo pseudocode:
    http://shelwien.googlepages.com/lzturbo.rar
    Execution starts from the start() function.

    Guess you'd be able to find some clues there,
    like hash functions and their constants etc.

    Also it should be possible to generate some examples
    exploiting the match finder specifics.

  12. #72
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    325
    Thanks
    18
    Thanked 6 Times in 5 Posts
    Bulat: "yes, but he tries to convince us that he was developed everything from scratch"

    I think that this is a case of two people who don't speak English natively mis-understanding each others butchered English sentances. I doubt he means he did everything "from scratch".

    As to whether lzturbo contains code from tornado, i don't know, we'd really need to see the source. A disassembly won't show too much due to different compilers/switches producing different code.

  13. #73
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Quote Originally Posted by Intrinsic
    A disassembly wont show too much due to different compilers/switches producing different code.
    disassembly will show enough if you know assembler once ive recreated rar2 algorithm just by looking at its decompression loop

  14. #74
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    what I posted is not disassembly, if nobody looked at it yet.

    And there eg. we have this:
    Code:
    tornado: 
    struct BaseMatchFinder 
    [...] 
        uint hash (uint x)    {return ((x*123456791) >> HashShift) & HashMask;} 
     
    lzturbo: 
    v65 = 123456791 * *(_DWORD *)v6; 
    v79 = *(_DWORD *)v6; 
    v80 = v65 >> v75;
    But I don't see anything similar to the rangecoder used in tornado,
    only things like:
    Code:
    if ( (unsigned int)(v282 - 10) > 0xFF ) 
    { 
      __asm { bsr     edx, esi } 
      if ( _ZF ) 
        _EDX = -1; 
      v298 = _EDX + 1; 
      while ( v24 < _EDX ) 
      { 
        v24 += 8; 
        *(_BYTE *)v7 = (unsigned int)v26 >> 24; 
        v26 <<= 8; 
        ++v7; 
      } 
      v67 = v24 - _EDX; 
      while ( v67 < v298 ) 
      { 
        v67 += 8; 
        *(_BYTE *)v7 = (unsigned int)v26 >> 24; 
        v26 <<= 8; 
        ++v7; 
      } 
      v65 = v67 - v298; 
      goto LABEL_227; 
    }

  15. #75
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Just as a note: You'll find this exact 123456791 constant in PAQ's source, too.

  16. #76
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    yes, but paq hash is
    Code:
      cx=cx*987654323+i;  // permute (don't hash) cx to spread the dist 
    ribution 
      cx=cx<<16|cx>>16; 
      cxt[i]=cx*123456791+i;
    and is different from what we can see in lzturbo... and tornado,
    the constant just allows to easily find it.

    Anyway, I'm just trying to help Bulat in finding some evidence.

  17. #77
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,023
    Thanks
    415
    Thanked 416 Times in 158 Posts
    Quote Originally Posted by Christian
    Just as a note: Youll find this exact 123456791 constant in PAQs source, too.
    And in LZPM as well. Such hashing also was in detail described at this forum, given this prime number. According to my tests, this number is a very good prime number for hashing - if we hash 32-bit integers. So, maybe dnd just reading this forum for a long time.

  18. #78
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Quote Originally Posted by encode
    So, maybe dnd just reading this forum for a long time
    or tornado sources for a short one actually, ive used your value and someone may find it starting form obvious 123456789 value. but the combination of hash formula, constant used and MF anatomy is rather specific

    Quote Originally Posted by Shelwien
    what I posted is not disassembly, if nobody looked at it yet.
    hm, its C-fied disassembly it was easy to find case 1..case 5 code which runs (de)compressors but decompressors bodies are still too cryptic for me

    Quote Originally Posted by Shelwien
    But I dont see anything similar to the rangecoder used in tornado,
    anyway its not mine and can be replaced by other rcs. what im interested to see is similarities/differences between ari/huf coders. unfortunately its still hard to dig

  19. #79
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    Anyway, does anyone blame Shelwien for taking SSE out of PPMonstr or AR for modifying PAQ to win the Hutter prize?

  20. #80
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    ... or entire tornado algorithm to be sold as "lzturbo library"?

  21. #81
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    Well, the matter here is supposed GPL violation.
    Or, more like, dnd claiming that he written all the code himself,
    as I don't think it'd became a problem if he'd been just quietly
    working on it, even without opening the sources.

    And, btw, it is similar to what AR does (he didn't start with hutter contest).
    That is, using somebody's work to advertise yourself.

  22. #82
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    Bulat: We don't know that (yet).

    Shelwien: It would help a lot for dnd to release sources, let there be Bulat's work or not. At least AR's work shows visible improvement in advertised parts and not "remix" like dnd's does.

  23. #83
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    Quote Originally Posted by Shelwien
    And, btw, it is similar to what AR does (he didnt start with hutter contest).
    That is, using somebodys work to advertise yourself.
    but ar tells that hes using others work. also he opens the source after some time.

    if dnd make at least decompressor open source then bulat can determine if dnd copied his work.

  24. #84
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    Quote Originally Posted by Black_Fox
    It would help a lot for dnd to release sources
    i dont expect this taking into account that he not even want to say about general algorithm ideas

    what im pretty sure for now is that he is using my match finder as is - i.e. with its algorithm, hash function and even multiplication constant. developed from scratch, of course

Page 3 of 3 FirstFirst 123

Similar Threads

  1. FreeArc compression suite (4x4, Tornado, REP, Delta, Dict...)
    By Bulat Ziganshin in forum Data Compression
    Replies: 554
    Last Post: 26th September 2018, 03:41
  2. Some comments on Tornado
    By m^2 in forum Data Compression
    Replies: 14
    Last Post: 24th November 2008, 02:25
  3. Tornado 0.3
    By Bulat Ziganshin in forum Forum Archive
    Replies: 12
    Last Post: 10th March 2008, 07:16
  4. Tornado - fast lzari compressor
    By Bulat Ziganshin in forum Forum Archive
    Replies: 23
    Last Post: 27th July 2007, 14:26
  5. tornado 0.2 is not yet finished...
    By Bulat Ziganshin in forum Forum Archive
    Replies: 15
    Last Post: 12th July 2007, 00:06

Posting Permissions

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