Thread: Tornado 0.4

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.

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?

Originally Posted by Christian

please gather some bullet proof information

its here - common match finder and set of coders

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.

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.

Originally Posted by Bulat Ziganshin

its here - common match finder and set of coders

Imo, this is not proof, but indication.

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

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?

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.

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

It did accept -s- with modes -1 to -4... guess it didn't work anyway...

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

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.

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.

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

what I posted is not disassembly, if nobody looked at it yet.

And there eg. we have this:
<div class="jscript"><pre>tornado:
struct BaseMatchFinder
[...]
uint hash (uint x) {return ((x*123456791) >> HashShift) & HashMask;}

lzturbo:
v65 = 123456791 * *(_DWORD *)v6;
v79 = *(_DWORD *)v6;
v80 = v65 >> v75;</pre></div>

But I don&#039;t see anything similar to the rangecoder used in tornado,
only things like:
<div class="jscript"><pre>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;
}</pre></div>

Just as a note: You&#039;ll find this exact 123456791 constant in PAQ&#039;s source, too.

yes, but paq hash is
<div class="jscript"><pre> cx=cx*987654323+i; // permute (don&#039;t hash) cx to spread the dist
ribution
cx=cx<<16|cx>>16;
cxt[i]=cx*123456791+i;</pre></div>

and is different from what we can see in lzturbo... and tornado,
the constant just allows to easily find it.

Anyway, I&#039;m just trying to help Bulat in finding some evidence.

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.

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

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

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

Anyway, does anyone blame Shelwien for taking SSE out of PPMonstr or AR for modifying PAQ to win the Hutter prize?

... or entire tornado algorithm to be sold as "lzturbo library"?

Well, the matter here is supposed GPL violation.
Or, more like, dnd claiming that he written all the code himself,
as I don&#039;t think it&#039;d became a problem if he&#039;d been just quietly
working on it, even without opening the sources.

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

Bulat: We don&#039;t know that (yet).

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

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.

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