Java port of TarsaLZP

[Piotr Tarsa]

Hi!

Just for your information: I have started porting TarsaLZP into Java. Java code is much more readable than assembly code so it will be easier for you to figure out what is going on in my algorithm. As for now it's not working. There are only some common (for decoder and encoder) fuctions related to modelling and simple GUI.

Archive with NetBeans project of TarsaLZP is here: http://www.ii.uj.edu.pl/~tarsa/jTarsaLZP.7z .

Currently I have exams so I can't work on the code but I will be free at the beginning of next month.

If you know some good (fast and efficient) arithmetic coder written in Java, please let me know.

I will experiment with Java version of TarsaLZP and when big achievments are done I will port them to assembly.

On my ToDo list are:
- order-12 LZP (or another order higher than ,
- skipping read from higher order models if symbol is not seen in lower order models (just write because reading in that case is unnecessary) - I don't know if it will speed things up as AFAIK memory controller writes and reads entire cache lines (maybe I'm wrong here and it can update only a few bytes),

Cherrs,
Piotr.


EDIT:
jTarsaLZP is working now. Read the rest of topic to know how it works and how it progressed.

[Nania Francesco]

Thanks for porting! C++ version is possible ?

[Nania Francesco]

void encodeFlag(int probability, boolean match)
{
if (match) {
rcRange = rcRange * probability / 65536;
} else {
rcBuffer += rcRange * probability / 65536;
rcRange -= rcRange * probability / 65536;
}
while (rcRange < 0x01000000) {
//outputByte(rcBuffer >> 24);
rcBuffer <<=8;
rcRange <<=8;
}
}

Int decodeFlag(int probability)
{

...............????

return match;
}

[Piotr Tarsa]

It should look like that:

boolean decodeFlag(int probability)
{
  int rcHelper = rcRange * probability / 65536;
  if (rcHelper > rcBuffer) {
    rcRange = rcHelper;
    return true;
  } else {
    rcRange -= rcHelper;
    rcBuffer -= rcHelper;
    return false;
  }
  // normalization is missing here
}

But I don't have time to check.

[encode]

It should look like that:

boolean decodeFlag(int probability)
{
  int rcHelper = rcRange * probability / 65536; // overflow!
  if (rcHelper > rcBuffer) {
    rcRange = rcHelper;
    return true;
  } else {
    rcRange -= rcHelper;
    rcBuffer -= rcHelper;
    return false;
  }
  // normalization is missing here
}

But I don't have time to check.

[Piotr Tarsa]

Thanks for pointing it out. There should be 'long', not 'int'.

[encode]

Thanks for pointing it out. There should be 'long', not 'int'.

Not even long. Int64 or something - 64-bit integer. Because rcRange must be 32-bit integer. And instead of a division, better use right shift:

  UInt32 rcHelper = ((UInt64(rcRange) * probability) >> 16;

[Piotr Tarsa]

Java uses 64 bit longs. Every integral value is signed.

BTW: Because of heavy use of longs 64 bit Java Virtual Machine is recommended.

[Nania Francesco]

normalization ????

rcRange<<=8;
rcBuffer=(rcBuffer<<+getbyte(infile);

[Piotr Tarsa]

Yes. Something like that. Before returns:

while (rcRange < 0x01000000) {
  rcBuffer = (rcBuffer << 8) + inputByte();
  rcRange <<= 8;
}

[Piotr Tarsa]

Slightly updated the code.

PS:
I've read Agner Fog's tutorials and there is a evidence that writing to uncached memory causes fetching entire memory line to cache and then writing it back. But there are instructions like MOVNTxxx available in some SSE versions which causes writing to memory avoiding cache. So I'll probably use it in assembly version as I'm planning to rewrite that version to 64 bit.

Some serious work should be done at beginning of July.

[Piotr Tarsa]

Encoding is almost working now. I have a small problem with infinite loop. I need to read more about Java I/O architecture. Maybe someone other is familiar with Java...

[Piotr Tarsa]

Encoding now makes reasonable results. I had a lot of problems with types casting (something not present when programming in assembly ).

Edit:
Sorry for posting many posts in a row .

[Fu Siyuan]

I'm expecting of your program. So excuse me, will your open source then?

[Piotr Tarsa]

I provided full source code in the archive. See first post. I'm constantly updating it, but the link stays the same. You need to download NetBeans IDE from netbeans.org, unpack the archive and open it in NetBeans IDE.

[Piotr Tarsa]

Encoder now works properly and is bit-for-bit compatible with http://asembler.republika.pl/bin/TarsaLZP.zip .

Francesco should be happy

[Nania Francesco]

Yes Piotr , Nice job !

[Piotr Tarsa]

Decoding runs fine now.

I've changed modelling a bit - I've changes updateSEEx to updateSEEHistoryx when LZP with order x isn't chosen at the moment. I feel that I'm doing many things in wrong way, especially the SEE.

I think that I should not update LZP order 4 model when using LZP order 8 model, but when I skip it (ie. when LZP order 8 is chosen then don't update LZP order 4) compression becomes worse - compressed enwik8 becomes about 500,000 bytes larger, enwik9 becomes about 3,900,000 bytes larger. What do you think?

[Piotr Tarsa]

I've tried adding order-12 LZP model, but nothing good happened. On enwik8 it made the result better by only 10,000,000 byte and it doubled the time. The gains are not worth the speed hit. I will continue by improving current order 4 and order 8 tandem.

[Rugxulo]

I always liked the fact that TarsaLZP was so small and written in FASM. But being Windows only as well as ever-increasing amounts of RAM limited its appeal a bit to me (no offense). Nevertheless, good job!