EarlyMorning - Progress & Discussion

One suite to code them all. An complete IDE and assembler for all your z80 projects!

Moderators: benryves, kv83

Post Reply
User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4135
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

I suggest making it variable. It kind of depends on the data as to what the run-indicator should be but yes, from what ive seen its usually 255.
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

or is this the more common way of doing this?

(short: in the encoded data it repeats a the value to indicate that there are at least 2 the same values in a row

so "3,3,3,3,4,4,5" would be "3,3,4, 4,4,2, 5"

this way, you wouldn't lose that one bit)
Image
User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4135
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

The only thing is, a run is typically only encoded if it has a length of more than 3, because there is no size payoff otherwise.
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

Even worse, there would be an increase. (going from 2 bytes (X,X) to 3 bytes (X, X-indicator, amount))

hmmm... I still don't like the variable idea though :x
Image
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

I have used both, When you need the full range(0-255) 2 bytes recurring is good since it would only make it larger in runs of 2. There's also the benefit of not defining any escape key so no extra info is needed. This would be really practical.

Then again you could scan for the least often used byte in the data and provide that at the beginning of the compressed data. Which could work well.

In terms of coding ease recurring bytes would be easiest for everyone. Since its just a tiny routine on our end and you don't have do extra fancy stuff on your end

You are going to consider more elaborate compression themes later right? Since rle is only know for its small decomp code and its speed.


Request:

Can I drag and drop tiles and maps into a different order? Selecting move up takes a while.
Image
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

Then again you could scan for the least often used byte in the data and provide that at the beginning of the compressed data. Which could work well.
Hmmmm... so it would be something like that (same data: "3,3,3,3,4,4,5" )?

Code: Select all

 .db 6; control character 
 .db 3,6,4, 4,6,2, 5
What happens if all 256 characters are used? :?
You are going to consider more elaborate compression themes later right? Since rle is only know for its small decomp code and its speed.
Yes, but i'm a noob on compression. If you want any, give me a link to a tutorial and/or a format you would expect, and I'll make it :)
Can I drag and drop tiles and maps into a different order? Selecting move up takes a while.
If you mean with "takes a while" that you have too click a lot of times, that can be fixed. If you mean "it takes a while to move a sprite in terms of EM loading", it will be the same :) (The load increases with more maps. Imagine 50 maps with a size of 50x50 and a spritesheet of 50 sprites in which #50 is moved to #0 ... all maps have to be adjusted) I'll look into it though, so that it will be included in the next release. It won't be drag and drop though, more like "give new id for resource" and he will move it to that place and move all other resources with id higher or the same one down in the list.
Image
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

kv83 wrote:What happens if all 256 characters are used? :?
That's why you choose the least often used, it would be the most compressed using an escape key. The worst case scenario would make the compressed data (1+size/256) larger than the original, where as the worst case in recuring bytes is (size/2) larger . So you see the least often used escape key would have a better worst case.
Yes, but i'm a noob on compression. If you want any, give me a link to a tutorial and/or a format you would expect, and I'll make it Smile
Im not much of a compression guy either, I really only know LZW, though I hear PuCrunch does wonders and doesn't require extra ram other than the space for the deompressed data.
I'll look into it though, so that it will be included in the next release. It won't be drag and drop though, more like "give new id for resource" and he will move it to that place and move all other resources with id higher or the same one down in the list.
Yeah that's still better than clicking 20 times.(not to mention the pop up that always ask).
Image
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

<kv83> Jim... you there?

<Jim_e_> Im here now

<kv83> k.

<kv83> about the RLE compression

<kv83> I don't get it.

<kv83> say your escape-char is 6

<Jim_e_> yeah

<kv83> how does the decoder know when it's a escape-char, and when it's not

<kv83> say we have 3,3,3,4,4,5,5,5,5,5,6 as data and 6 is also the escape-char

<Jim_e_> it should be provided at the begining of the compress data

<kv83> even then, when the data above is compressed, it looks like this:

<Jim_e_> so the first byte always indicates what the escape char is

<Jim_e_> sure it always increases the size by 1

<kv83> 3,6,1,4,4,5,6,5,6 ... you see what I mean?

<kv83> how can the decoder know that the last 6 is NOT an escape-char

<kv83> (sorry for beeing dumb :P)

<Jim_e_> 3,6,2,4,4,5,6,6,6,6,1

<Jim_e_> the run length should say how many times the last byte was duplicated

<Jim_e_> oh wait that example I just did is wrong

<Jim_e_> :P

<kv83> :P

<Jim_e_> put the escape first

<kv83> ah... so a "6" is in the encoded data a "6,6,1"

<Jim_e_> 6,3,3,4,4,6,5,5,6,6,`

<Jim_e_> ` = 1 (typo)

<kv83> right?

<Jim_e_> 6,3,3,4,4,6,5,5,6,6,1

<Jim_e_> yeah 6,6,1

<kv83> i see ... hehe... clever

<kv83> k, well than that's obvious the best solution to use :) thanks!

<Jim_e_> no problem

<kv83> any objections if I post this in the topic? =P

<Jim_e_> nope
and so it's done :P that's the format I'll use for RLE thanks to Jim E and tr1p :)
Image
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Post by King Harold »

ok that's cool but the stuff on this page might be helpfull for funny lossless compression. Probebly not all that usefull, but maybe a bit... Im sure i didn't invent anything new and i didnt explain it well either but it may still be nice. (but do know that i thought of them myself without any help when i was still programming in TI basic)
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

sorry, but it ain't... it's a "simplistic" version of RLE afais. Thanks anyway.

(Btw, there are some huge errors on that page :P)
Image
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

Actually now that I think of it theres one more thing I would do. I would have the runlength come before the actually byte that is to repeated. For example

1,2,2,3,3,3,3,3,4,5,5,5,5,1

Would compress to

1,2,2,6,5,3,4,6,4,5,1

Its purely because it would be faster to deompress.

;hl compressed
;de destination

Code: Select all

decomprle:
	ld c,(hl)		;get decompressed size
	inc hl
	ld b,(hl)
	inc hl
	ld a,(hl)		;get escape
	inc hl
decloop:
	cp (hl)
	jr z,escchar
	ldi
	jp pe,decloop
	ret
escchar:
	inc hl
	push af
	ld a,(hl)		;run length
	inc hl
escloop:
	ldi
	jp po,donerle
	dec hl			;stay on byte to be copied
	dec a
	jr nz,escloop
	pop af
	inc hl
	jr decloop
donerle:
	pop af
	ret
Image
User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4135
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

I see what you mean with the escape char being first, thats a pretty decent solution i think. I say you go with that and allow the run indicator/escape char to be defined somewhere in the settings.
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Post by Timendus »

Edit: Sorry, I was looking on the wrong page :P

Depends who you ask :)

Personally, I use yet another version:

aaaaabcc > a5bcc

I use the most common byte as the control character to save a byte. In full screen image data (which is what I usually have to compress) it's usually $00 or $FF and there's nothing or almost nothing to win in the other bytes.

The second article you mention is a good, more general, way to do it I think.
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

I say you go with that and allow the run indicator/escape char to be defined somewhere in the settings.
The plan is, to make the escape char the char which is least often used. So every map can have in "theory" a different RLE-char :)
Image
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

Timendus wrote:I use the most common byte as the control character to save a byte. In full screen image data (which is what I usually have to compress) it's usually $00 or $FF and there's nothing or almost nothing to win in the other bytes.
If you use the most common bytes as the control character then you would dramatically increase the size if there aren't many runs.
Image
Post Reply