Tornado 0.4

[Bulat Ziganshin]

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

[Christian]

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.

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.

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.

[Christian]

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.

[donotdisturb]

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!

[Bulat Ziganshin]

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?

[Bulat Ziganshin]

donotdisturb
one of questions - are you use linear hash probing in match finder?
another one - which lzturbo version added huffman encoder?

[Christian]

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.

[donotdisturb]

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.

[donotdisturb]

Sorry look at:
http://encode.su/forums/index.php?ac...=502&page=5475

[encode]

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.

[Christian]

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.

[encode]

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!

[Shelwien]

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

[Bulat Ziganshin]

+ 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

- 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?

[Bulat Ziganshin]

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

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?

[Bulat Ziganshin]

Then, the insertion itself does some sort of self-balancing

can you describe the rebalancing algorithm?

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

[Shelwien]

@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

[Bulat Ziganshin]

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

[SvenBent]

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

[Christian]

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.

can you describe the rebalancing algorithm?

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.

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.

[Shelwien]

> 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...

[Bulat Ziganshin]

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

[Bulat Ziganshin]

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

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

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!

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

[Shelwien]

>> 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?

[Black_Fox1]

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).

[Bulat Ziganshin]

bzip was 32-bit program and it was replaced by less-efficient bzip2 due to speed/patenting issues

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

[Bulat Ziganshin]

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

[Bulat Ziganshin]

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

[encode]

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.

[Bulat Ziganshin]

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