whats the best programm for compressing data?

By norakomi

Paragon (1137)

26-12-2005, 09:33

high again!
I've got a lot of files, and I want to compress all of them.
There is routines, data, graphix etc etc...

What is the best method of compression? (I got team bomba's bitbuster, is this very good to use?)

By BiFi

Enlighted (4348)

26-12-2005, 09:38

depends on the type of data you need to compress. I quite some cases bitbuster is good enough and freely available. In time you can always look into compression yourself and try to make an even better one.

for the infinite demo Coral 2 I made I used bitbuster and put the resulting files into a library file for faster loading...

By ro

Scribe (4920)

26-12-2005, 16:10

and when doing "realtime" decomp. use a simple RLE (Run Lenght Encoding) algo. this will sure save ya lotsa KBs, is easy and very fast.

By ARTRAG

Enlighted (6933)

29-12-2005, 19:14

@ro
I have 4bit data for the 3 PSG channels, I need to do real time RLE decompression, where real time means 8KHz playback.

How to implement RLE at nibble level, having only 313Tcycles for 3 (say 3 !!) channels?

My current solution reserve a byte for each encoded channel, the high nibble is the run counter, the low nibble is the level value.

This is fast and easy but not efficient as many times I find a long run of unique levels that are coded as
#1X,#1Y,#1Z,#1U,#1V,#1W,etc....
that is a huge waste of space as double the minimum required space.

A theorically good solution should be to use a signal that says that the following sequence is non RLE encoded, thus that you can code the "non" run segment with minimum space.

Ideally I would like the sequence of nibble:

XXXXXXXYXZYWXUVWWWWW

to be encoded like

#7X,#YX,#ZY,#WX,#UV,#5W

how to prevent the decoder to interpret #YX as an encoded run of X?

Standard theorical the strategy for creating a “signal” for the decoder is complex but effective.

First we apply coding to runs of more than one symbol and we use the run length to indicate the number of additional copies of the encoded symbol are required.

The original string
XXXXXXXYXZYWXUVWWWWW
would become:
#6X,#YX,#ZY,#WX,#UV,#4W

Second, we encode the start of an encoder run by a repeated nibble,
this means that the string would become:
#6X,#XY,#XZ,#YW,#XU,#V4,#WW

Now the decoder have to look at 3 successive nibbles in order to decide if the data are a run or unrepeated values.

The problem is: how to encode all this in asm in the time constrain I told?

PS
my current solution is at
http://www.msx.org/forumtopic5686.html
As i told you now the nibble are fixed and the waste of space in case on unrepetead samples huge...

By AuroraMSX

Paragon (1902)

30-12-2005, 10:17

@ro
I have 4bit data for the 3 PSG channels, I need to do real time RLE decompression, where real time means 8KHz playback.

How to implement RLE at nibble level, having only 313Tcycles for 3 (say 3 !!) channels?

My current solution reserve a byte for each encoded channel, the high nibble is the run counter, the low nibble is the level value.

A theorically good solution should be to use a signal that says that the following sequence is non RLE encoded, thus that you can code the "non" run segment with minimum space.

Extend the RLE to deal with repeating patterns rather than repeating single nibbles. The encoded stream would consist of tuples (records) like this: NLPPPP...P, where N is one nibble containing the number of repetitions, L the length of the pattern (in nibbles) and PPPP...P the pattern nibbles.
Eg, the pattern (all hex nibbles, spaced for easy reading):

1111 AAAAA 23232323 56789A FFFFFFFFFFFFFFFF

would be encoded to

411 51A 4223 6156789A 01F (or, in bytes 41 15 1A 42 23 61 56 78 9A 01 F0)

Some remarks:

Note the use of '0' to denote '16'. There is no need to have some special case for non-repeating patterns. A non-repeating pattern simply has a repeat-count of 1.
To simplify decoding, one could force the NL pair to be a single byte; this can be implemented by adding an extra (useless) nibble to each pattern having an odd length.
Theoretically, the encoded stream could be larger than the source file.
The encoder is somewhat tricky to implement, if you want the best compression ratio... I implemented an encoder once which searches for the longest repeating pattern, but that's not guaranteed to give the best result...
It may be better to swap the length and repeat count: LNPPPP...P. Create the decoder and see what suits you best

By ro

Scribe (4920)

30-12-2005, 11:12

use a pre-decode routine. it is on int, right? or is it PSG data streaming?
if on int: do your psg stuff, after that do de encoding of the NEXT to come string and use that in your next int.
realtime don't always mean real realtime (as in, decode, write to psg, decode more and write some more)
you might also do some "null" compression. only compress the zero values (which are very present in tracker data!)

3 channels -> 3 nibbles. 1 nibble left. use that nibble for sign and do a subversion of RLE for example.
I have to know your datastream to make good advise.

By ARTRAG

Enlighted (6933)

30-12-2005, 11:36

AuroraMSX
good ideas for a simple general compressing algorithm but ....

a) my problem are the unique values, your solution worsens their weight (at first glance)
b) I use 0 to encode 16 as well
c) my values are nibbles from a given psg channel and I need to playback them real-time (at 8KHz)
can you show me a decoder able to do that ?

If you look at the replayer (follow the link) you'll see that currently, while decoding,
I count in registers B,D & E the remaining run lenght and when one counter reachs zero
I take a new PSG value and a new run lenght.
All this fits in 447 Tcycles (that are partially used for the PSG I/O, so the net resulting time is 313 cycles)

Actually the loop, when there is no level update, just waits with dummy ex hl,(sp) in order to fit the 447 Tcycle
can you suggest a solution for using the dummy time between two level changes in order to decompress
on fly the next PSG levels ???

In theory it seems doable, but I need your illuminating view before hanging myself with my hands with
this new developement

By ARTRAG

Enlighted (6933)

30-12-2005, 11:38

@ro
no ints! real-time replayer at 8KHz!
send me an email and I'll send you a package with the data, the pcm encoder and the player

By Gilneas2

Master (235)

30-12-2005, 12:24

6156789A

Don't you mean: 1656789A?

By [WYZ]

Champion (451)

30-12-2005, 12:32

If you don't need descompression at the fly:

-Prucrunch: the best compression rate, but slower (not very noteworthy)
-bitbuster.
-bitbuster extreme: small size unpacker.

By ARTRAG

Enlighted (6933)

30-12-2005, 13:12

@wyz
I need realtime !!!
unless I/you do not rearrange the replayeer in order to use that now are "wait" in some usegull code able to
unpack next samples and make them ready for when they will be required....

But, with a time constraint of 447 Tcycle things are almost desperate....