Page 2 of 3 FirstFirst 123 LastLast
Results 31 to 60 of 84

Thread: Tornado 0.4

  1. #31
    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 Simon Berger
    Aren?t it ever the same with the things Bulat writes? I was writing a message like this many times and then canceled it because I thought is it my problem...?
    I have really much respect about the inventions you did with freearc and I am happy about every new release. But I see you think too good about what you do and didn?t get to manage to hide it for others. It can be seen in almost every of your posts. Often there is a deprecative touch.
    I hope you can handle this sort of criticism and don?t react with despite.
    my english is a bit limited so ive reread this many times before i prcisely understood that you wrote. so

    1) seems that you read only part of my messages. look at freearc thread - there we have discussed that im mainly good "compression manager" and main part of freearc is lzma, ppmd, grzip, tta algorithms. im sure that im not the best developer in the area of compression algorithms

    2) OTOH we are looking from different points of view. for you, its natural to undervalue others work, for me its natural to overvalue my own work. for example, all lzhuf/lzari compressors developed in last 15 years, used either hash chians invented by Robert Jung (1990), or binary trees proposed in LZX (~1997). hash tables is the first new datastructure proposed for this task in last 10 years

    3) saying about tornado, i doesnt claim that its the best. it is slower than slug in fast modes, it compress worse than lzma in highest modes. but its unique as any other complex compression algorithm. it has unique combination of match finders, coders that gives it some "smell" - combination of speed/compression characteristics. what i say here is that lzturbo has *exactly* the same combination of characteristics and that his author demonstrates toital lack of knowledge of compression algorithms combined with aggressive justifications.

    first, he tries to prove that lzturbo doesnt use my matchfinder or encoders, when he failed - he starts saying that they are so obvious that anyone can invent them. at the same time he tries to hide similarities (bytecoder/bitcoder names, replaced -3* encoder in 0.92). i insist that there are too many similarities and they are very far from trivial, they are unique to tornado (unique doesnt mean best, its just different). noone developing his program independently will make exactly the same set of inventions

  2. #32
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Although I have a personal opinion on this topic, I do not want to take anyones side. But I think this whole discussion is too biased and there is too little hard evidence. Sadly, I can not contribute any facts - just some thougts.

    Quote Originally Posted by Bulat Ziganshin
    ps: btw, the most irritating dns phrase was about easiness of developing fast huffman encoder.
    I strongly believe, that a couple of people I know in person are easily capable of designing fast huffman coders. Additionally, Huffman is really a classic in computer science.

    Quote Originally Posted by Bulat Ziganshin
    i suspect that he just combined parallel bzip2 for multithreading/background i/o, tornado for match finder and coders and lzma for lazy/optimal parsing in his program
    Shouldnt this accusation be easy to prove by comparing fragments of compiled code etc.? I dont know how the others feel about this fight, but maybe someone with good disassembling knowledge can finally provide a proof or an acquittal.

    Nonetheless, the set of properties Tornado and LZTurbo share is exceptionally big.

  3. #33
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by toffer
    If i remember correctly, some strings containing a file extension list from freearc could be found inside the lzturbo executables.
    I forgot about this one - but I dont think that this is a coincidence. I wonder why dnd has not yet commented on this.

  4. #34
    Member
    Join Date
    Aug 2007
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi Bulat,
    i haven't time to look at your posts. I have some questions befor responding,
    - I don't understand what is your problems with lzturbo. Sometime you say it is using your code another times you say it uses similiar things.
    - Is your understanding from gpl, only because you are using byte-coding, or huffman-coding nobody else can use that in another compressor?
    - Please be more specific in your writing. What do you think lzturbo is using
    from your tornado code, contained only in your code, not common knownledge and not described elsewhere? i don't accept responses such huffman-coder or my match-finder.
    - What do you think lzturbo is not allowed to do?
    - What solutions do you propose to terminate this discussion?
    Thanks!

  5. #35
    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
    I strongly believe, that a couple of people I know in person are easily capable of designing fast huffman coders. Additionally, Huffman is really a classic in computer science.
    i dont consider zips coder which uses heap sorting as fast how many people you know developed faster way to do it?

  6. #36
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    donotdisturb
    one of questions - are you use linear hash probing in match finder?
    another one - which lzturbo version added huffman encoder?

  7. #37
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by Bulat Ziganshin
    i dont consider zips coder which uses heap sorting as fast how many people you know developed faster way to do it?
    Iirc, Radix sort is teached in first semester lectures. I dont know about any implementation in detail - but huffman is used in so many fields, Im quite sure, that there are bullet fast implementations. I just said, that I know many people easily *capable* of writing a fast coder - because I think it IS easy.
    Besides, imo tree generation in ZIP isnt optimized too much because:
    1) It is not a hot spot at all.
    2) 2 pass radix sort isnt any faster than heap sort for small alphabets.
    3) 1 pass radix sort uses either big tables or srews with symbol counts.
    4) For decompression ZIP does not sort at all - it stores the trees in a compact way. At least this is what somebody told me.

  8. #38
    Member
    Join Date
    Aug 2007
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi Christian,
    I think this thing is dead. Look at:
    http://encode.su/forums/index.php?ac...page=1#msg5479

    Actually the list is removed.

    To bulat,
    - The problem is not what are lzturbo internals. I think it is legitim, if
    in don't want to speek about lzturbo internals.
    The whole problem hier IS LZTURBO using your code YES or NO.
    - It's not because, you use some common algorithm, that someone is not allowed to use this algorithm with different implementation in his next versions.
    Please answer now to my questions. I don't have and want to spend a lot of time repeating the same things. Please do not
    use street language.

  9. #39
    Member
    Join Date
    Aug 2007
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts

  10. #40
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,023
    Thanks
    415
    Thanked 416 Times in 158 Posts
    donotdisturb
    Note that this forum is mostly about what's inside a program. The readers is more interested not in new experimental product, say compressor X, but how this new compressor works. Like you see, the most of authors on this forum, including me, each time describe what's inside and what's changed. Yes, sometimes authors like Christian hiding info, but even he answers the questions, which are straight asked by the community. It's because each new compression technique is subject to discussion. As far as I understand, your answer is NO - you never use Bulat's source. OK, at the same time you never go into details like:
    + Match Finder, which is very specific. Like Bulat said, the memory usage is very uncommon, TORNADO is the only program with such memory requirements.
    + Why do you use four modes like in TORNADO? In fact, there is only one other program with such options - TORNADO!
    + Why the TORNADO extension list was found in first releases of LZTURBO? Don't say about any libraries, this list of extensions is a unique one, even I and some users from this forum added a few rare extensions on it. [!] So, when I found *MY* extensions in *YOUR* executable it was the answer.

  11. #41
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by encode
    Yes, sometimes authors like Christian hiding info, but even he answers the questions, which are straight asked by the community.
    Only a short OT comment. I think many authors of closed source programs try to hide some of their secret ingredients. Look at Uharc, WinRK, PPMonstr, Rings or your LZPM.

  12. #42
    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
    LZPM
    Yes, but at the same time, you can find a part of the LZPMs decoder source at this forum. In addition, some of the details are very deeply described at this forum - ranging from arithmetic encoder model to parsing strategies. Like I said, LZPM is just an improved QUAD, and QUAD is open source!

  13. #43
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    It seems really off-topic, but I did some tests.
    http://shelwien.googlepages.com/tor04.htm
    http://shelwien.googlepages.com/lzpm015.htm <-- some other compressors for comparison
    http://shelwien.googlepages.com/tor04_A1_Ox_ipo.exe <-- IntelC build

  14. #44
    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
    + Why the TORNADO extension list was found in first releases of LZTURBO? Dont say about any libraries, this list of extensions is a unique one, even I and some users from this forum added a few rare extensions on it. [!] So, when I found *MY* extensions in *YOUR* executable it was the answer.
    its a list from freearc

    Quote Originally Posted by donotdisturb
    - Its not because, you use some common algorithm,
    can you describe common algorithms i use and point to their authors? how about lzturbo - does it use "common algorithms" too and therefore doesnt contain your intellectual property?

  15. #45
    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
    I think many authors of closed source programs try to hide some of their secret ingredients.
    even use of huffman coder? i dont asked dns to reveal secret details, i just asked about two concrete ideas - are he use these or not

    Quote Originally Posted by Christian
    Iirc, Radix sort is teached in first semester lectures.
    the zips problem is that list of freqs isnt sorted before building huffman tree, instead all freqs are sorted dynamically using heap tree. slowness of this procedure was the reason to use simpler encoding in -es (fastest) compression mode of pkzip 2

    so, how many people you are know found the ways to deal with all the problems himself?

    the same is true for arithmetic coder - how many people you are know developed efficient arithmetic encoder from a scratch, without knowing about Shindler work?

    how many people you are know invented new data structure for finding matches or contexts and how many of them was done this 1) a few months after this idea was published in other program, 2) without any prior experience in the area?

  16. #46
    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
    Then, the insertion itself does some sort of self-balancing
    can you describe the rebalancing algorithm?

    Quote Originally Posted by Christian
    we need to find only 7+ matches at large distances that may be implemented with indexing by 4 bytes on EVERY 4th POSITION
    Actually, you can do this. But if I understand you correct, you buy the lower memory footprint by increasing the time needed for a search.
    the situation is even worse - BTs cant be used to search "adjacent" matches exactly because its sorted. say, after weve seen 0+5 match we will never see 3+4 match, although its better for our position. thank you for help, it saves me a lot of time!

    so, only HC/HT may be used for such match finder. it may insert matches found in 4 lists simultaneously or even separate passes may be used - time is spent mainly on cache misses. the one more problem for optimal parsing is that matches appear in each list not in order of increased lengths

    or, HT for 7+-long matches may be used but this way we need to use 4x-8x memory for exhaustive string searching

  17. #47
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    @Bulat:
    1. Schindler is written like that, while "shindler" was used due
    to 8:3 naming restrictions.
    2. Original rangecoder is http://www.compressconsult.com/rangecoder/rngcod13.zip
    and that's not what you're using

  18. #48
    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
    Original rangecoder
    i mean that he invented idea of saving bytes instead of bits. i dont think that anyone has reinvented it independently so claims that lzturbo was developed from scratch make me laugh loudly. he just doesnt understand how compression algorithms are developed

  19. #49
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    926
    Thanks
    58
    Thanked 116 Times in 93 Posts
    So wats new in the tabloids

    are LZturbo using Tornado Source or not ?

    I have my ides. but that probably because i dont know the technical stuff. and can only comprehended the simple stuff like
    "4 encoding modes both having the. 3 disabled."


    how about making tornado closed source for a moment and see if LZturbo improvenst stalls

  20. #50
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by Bulat Ziganshin
    so, how many people you are know found the ways to deal with all the problems himself?
    I wrote capable of. And you can tell me whatever you want - writing a fast huffman coder is a piece of cake.

    Quote Originally Posted by Bulat Ziganshin
    can you describe the rebalancing algorithm?
    Quote Originally Posted by Christian
    Using this idea, youll come to the conclusion, that you want to insert EACH new node as the ROOT. Then, the insertion itself does some sort of self-balancing because it has to RECONSTRUCT the tree. Still, the tree CAN DEGENERATE.
    Just reread carefully. Still, youll have to grab a piece of paper and a pencil yourself.


    Quote Originally Posted by Bulat Ziganshin
    i mean that he invented idea of saving bytes instead of bits. i dont think that anyone has reinvented it independently so claims that lzturbo was developed from scratch make me laugh loudly.
    I really dont want to protect dnd. But you have to be objective. To invent, design, develop and implement are quite different things.

  21. #51
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    > i mean that he invented idea of saving bytes instead of bits.
    > i don't think that anyone has reinvented it independently

    I doubt about that as its trivial.
    Its much more rare to see eg. a coder with half-bit renormalization.
    Also I tend to call any arithmetic coders rangecoders as its a
    more convenient term.

    In that sense, btw, Matt's rc is much more interesting -
    its technically a carryless rangecoder, but overflows are avoided
    using rounding specifics, without any explicit code, so its a simplest rc ever.
    Though I'm not sure that its really fastest - there're some drawbacks.

    Btw, wonder if you checked various media codecs for huffman implementations.
    I think there're much more open source huffman coders in that area.
    Alhough, well, it might be not easy to find eg. the function used for
    mp3 huffman trees construction...

  22. #52
    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 SvenBent
    how about making tornado closed source for a moment and see if LZturbo improvenst stalls
    1. this experiment was already made by accident. lzturbo was going to the stable 1.0 version, with only two versions issued due 6 months. then, tornado 0.3 was published and next week he issued 2 new program versions
    2. i dont think that this is so important that i need to change plans of my programs. its enough that ive issued 4x4 to show how eaily multithreading may be added to any compresor

  23. #53
    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
    I doubt about that as its trivial.
    dont undervalue others work. the fact is that various arithmetic coders was in wide use about 10 years before rc and compressors sufficiently suffice from lack of fast patent-free coder (recall f.e. bzip vs bzip2 history). there was a lot of work in this area before rc finally arrived

    Quote Originally Posted by Shelwien
    I think therere much more open source huffman coders in that area.
    yes, but he tries to convince us that he was developed everything from scratch he doesnt even understand that "his" program cant use arithmetic coder because its patented

    Quote Originally Posted by Christian
    And you can tell me whatever you want - writing a fast huffman coder is a piece of cake.
    Christian, writing anything easy - as far as you know how to do it right. the whole problem is invention of these right ways. unforunately, dns doesnt demonstrate even a bit of knowledge - all he is able to say is that huffman encoding or hashing are well-known things!

    Quote Originally Posted by Christian
    To invent, design, develop and implement are quite different things.
    yes, and its why anyone telling that he was developed everything from scratch while not knowing elementary things (such as why closed hashing cant be used in match finder) looks like a liar

  24. #54
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,136
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    >> I doubt about that as its trivial.
    >
    > don't undervalue other's work.

    I'd say that most of "other's work" value is motivational.
    As its generally easier to write something from scratch than
    decrypting the "other's work".

    > the fact is that various arithmetic coders was in wide use about 10 years before rc

    Do you remember that 16bit architectures were common at that time?
    Of course a bytewise coder wouldn't have any use with 16bit registers.

    > and compressors sufficiently suffice from lack of

    %)

    > fast patent-free coder (recall f.e. bzip vs bzip2 history)

    I don't think that arithmetic coding was ever patented in whole.
    Its kinda the same as patenting object enumeration.
    So its more a problem of some people having too high goals.
    I mean, designing algorithms to be industry standards =
    making lots of money = hardware implementations =
    multiplication-free coders = patented.

    > yes, but he tries to convince us that he was developed
    > everything from scratch he doesn't even understand that
    > "his" program can't use arithmetic coder because it's patented

    Actually, I do believe that he used your sources, but when I thought
    that compression stats similarity would be the best proof, well...
    http://shelwien.googlepages.com/lzt092.htm
    I think that doesn't really look the same. Can tornado's advanced
    parameters be tuned to act like that?

  25. #55
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    I think that Hamid was inspired by multiple sources, gaining completely different results than Tornado on my testset - results of Tornado and of LZTurbo. Notice very similar totals, but completely different handling of (in)compressible data. Many questions would be answered, if LZTurbo was GPL'd (it's nevertheless compulsory, if any GPL code was used).

  26. #56
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    bzip was 32-bit program and it was replaced by less-efficient bzip2 due to speed/patenting issues


    Quote Originally Posted by Shelwien
    I think that doesnt really look the same.
    1) tornado doesnt have optimal parsing so dont test lzturbo -*9 modes
    2) -1* => -c1, -2* => -c2, -3* => -c3, -5* => -c4
    3) it seems that he doesnt use my 2/3-byte matchfinders (because they make program a bit slower and useless on enwik9 ) so use -s- for tornado. also use tor 0.3 for tests because 0.4 was arrived after lzturbo 0.92 (im sure its mirrored in 0.93)
    4) -31 => -2 -l2, -58 => -12 -s- -b128m -h64m. dont forget to split file into small parts (128mb for -58 equivalent) because lzturbo doesnt use sliding window

  27. #57
    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
    Notice very similar totals, but completely different handling of (in)compressible data.
    the reason is that i use streaming compression while lzturbo compress data in independent blocks. in his implementation its very easy to avoid results that are larger than input data. btw, i can do the same in 4x4 for lzma and tornado - it doesnt need any changes in compression libraries

    similar totals are cincedence - lzturbo lacks sliding window, 2/3-byte matches, but have optimal parsing instead. look instead at memory reqs and timings for similar modes and compare lzt 0.92 with tor 0.3

  28. #58
    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
    I think that Hamid was inspired by multiple sources,
    as i said in the last post at first page, i think that he was bundled together parallel bzip2, tornado and lzma code and the main problem he had to solve is seamless integration of OP from lzma with my code

  29. #59
    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 Bulat Ziganshin
    the main problem he had to solve is seamless integration of OP from lzma with my code
    Not necessarily he did that, LZTURBO may use both of them.

  30. #60
    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
    Not necessarily he did that, LZTURBO may use both of them.
    in this case it will work perfect from the first version while actually he is still debugging OP machinery. moreover, memreqs and compression results of lzt definitely shows that it doesnt use neither lzma coder nor its match finders

Page 2 of 3 FirstFirst 123 LastLast

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
  •