Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's Your Projects subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. Fate by Fire: The Sword of Neisius => Your Projects
Author Message
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 24 May 2003 07:50:29 pm    Post subject:

Well here it is my first post at UTI's new forum.

Fate by Fire: The Sword of Neisius is a rpg designed and created by Pascal Miller and myself.

It will be the biggest rpg ever on the ti83+. Plus it now has an added feature it will be in 4-level grayscale. A first ever on the ti83+. Now it's not what you're thinking. Ti83+ (crappy flickery grayscale). Wrong. This is a routine made by Diederik Kingma. It is nearly perfect. Crystal clear grayscale. The whole game will be in grayscale. So beautiful graphics are asured.

As soon as I tweak my decompression routine I'll post a screenshot. Yes it uses compression so huge maps. About 350 screens worth... :D

More to come.
Back to top
Pascal


Advanced Newbie


Joined: 24 May 2003
Posts: 76

Posted: 24 May 2003 08:51:17 pm    Post subject:

My first post too. Yea the game should be very nice when it is done. Progress is pretty quick thanks to Justin, who seems to finish some new routine every day-today it was grey scale, I won't be surprised if by next time I talk to him he will some how make the game in color.
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 24 May 2003 09:20:03 pm    Post subject:

Tomorrow's task is a working decompression routine Razz
Back to top
NETWizz
Byte by bit


Bandwidth Hog


Joined: 20 May 2003
Posts: 2369

Posted: 25 May 2003 12:38:13 pm    Post subject:

Justin, I could use a little compression routine. Please tell me a good method to compress data. If I knew how a compression routine works, I can figure out how to decompress.

Thanks.
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 25 May 2003 03:24:03 pm    Post subject:

OK I will explain RLE compression. (run-length-encoding)

Lets say that we have a data block that contains the following.

.db $20,$20,$20,$20,$20,$20,$21,$56,$35,$98,$98,$98,$98,$98,$01,$01

Now you need to check to see if there are more than 3 bytes exactly the same in succession. The reason you check to see if it's greater than 3 because a piece of compressed data is 3 bytes long.

1st byte=flag byte ;signifies that this is a run (piece of comressed data)
2nd byte=number of bytes ;number of that particular byte
3rd byte=the byte ;the byte to copy

So if your flag byte was $FF. (which is more effective for tilemaps because it is unlikely to have 255 tiles)

you could compress the above data to this.

.db $FF,$06,$20,$21,$56,$35,$FF,$05,$98,$01,$01

If it reads a byte that equals $FF it treats the next two bytes as a run.

so it would write 6 bytes to a location of your choice of $20


If there is any confusion please ask
Back to top
NETWizz
Byte by bit


Bandwidth Hog


Joined: 20 May 2003
Posts: 2369

Posted: 25 May 2003 08:14:10 pm    Post subject:

What about this?

$FF,$FF,$FF,$FF,$56,$56,$56,$56,$FF,$44,$36,$36,$36
compress

$FF,$04,$FF,$FF,$04,$56$FF,$01,$FF,$44,$FF,03,$36

As you can see, the problem comes when $FF occurs in the data less than 3 times consecutivly because we must compress it no matter what to avaoid it accidently being interpreted as a flag yeielding scarry results when uncompressed. :D

For example, if we compressed teh above as
$FF,$04,$FF,$FF,$04,$56$FF,$44,$FF,$03,$36

Then decompressed it we would have
$FF,$FF,$FF,$FF,$56,$56,$56,$56,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$36,$36,$36

Therefore, we must compress (IF you can call it that) a single $FF to $FF,$01,$FF

Now, More on your routine
The following should not be compressed
$36
$36,$36
$36,$36,$36

The wierd one is $36,$36,$36 because compressing it would yield $FF,$03,$36 which would not be smaller, but it would add time to the decompression.

Now, the last problem comes when you have more than 256 bytes. Yes, I mean 256 not 255.

Here is why. You will never see $FF,$00,$36 because it would be irrelevant to say that there are 0 $36 bytes to decompress Wink

Now, I think if we treat 0 as 1 then:

$FF,$00,$36 would mean one $36 and $FF,$FF,$36 would mean 256 $FF's


Although that is true, I propose that 256 is bad because the 00 could be an important part of the routine. So, I think we should really use 00 to $FF as 0 to 255 not 1 to 256.

For example:

$36,$36,$36,$FF,$56,$56,$56,$56,$56

$36,$36,$36,$FF,$00,$FF,$05,$56

Okay

We cannot save space compressing 3 $36's, so we do not bother.
$FF,$00 can mean that the flag is really a $FF value from the data because we would never use a flag to say that there are 0 consecutive bytes of $XX :wacko: so, $FF,$00 is better than $FF,$01,$FF

This means that if we have two or more consecutive $FF's, we would want to use

$FF,$02,$FF because our little 0 trick will not work

Now, what if we have a $00 in the data?

Data: $FF,$00

Compressed:
$FF,$00,$00

The reason of cource is that we have only one $FF and the first $00 is ignored because it just tells us that $FF is not a flag, so we must have another $00.

I doubt this will happen very often, but the flag shoud be a value that does not occur in the data much. $FF often occurs, so it should not be a variable.

Whatever you do, do not use $C9 as a flag because there are many rets that will magically take up an extra byte when compresssed if c9 is the flag. Surprised

BTW, the most interesting thing I learned today is that it is impossible to compress random noise. Rememember, random does not equal pseudo random in this case.
Back to top
NETWizz
Byte by bit


Bandwidth Hog


Joined: 20 May 2003
Posts: 2369

Posted: 25 May 2003 08:33:37 pm    Post subject:

Justin, the last flaw in our encryption/decryption routine is as follows:

If a byte is repeated more than 255 times, we cannot compress it well.

For example:

$12 259 times


$FF,$FF,$13,$FF,$04,$13

Put simply, 255 is the maximum in one run.

We would need more runs if more than 256 bytes followed.

In this situation, if we used a 16-bit (Word) to specify the number, we would have

$FF,$0103,$13

I put $0103 together because it is a 16-bit word that takes up two bytes. The $01 part represents 256 and the 03 the other three. When added, you realize that you have 259 $13's

Now, that you have upgraded to 16-bit encoding, you have new problems

1. For every run less than 256, a byte is wasted e.g. $FF,$00,$04,$13 and, we would not even bother to compress that because there is no savings.

2. We would have to specify the encoding at the beginning of the compressed data and make two passes. One to compress it at 16-bit and one to compress it with 8-bit encodign to see which yields the smaller result.

You would specify the encoding at the beginning

e.g.

$00 for 8-bit and $01 for 16-bit...

Still, you would probably never use 16-bit unless you are compressign an all black picture or something because it is rare for more than 255 bytes of consecutive code to be in a program unless it is pic data or free ram. Besides, if you have more than 255 consecutive bytes, you are going to save many bytes anyway.

259 bytes to 6 bytes is good enough if you ask me Very Happy

One last thing, who is going to mkae this super compression program? I think it would be quite difficult to make; thouth, eventually I may make an attempt.
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 26 May 2003 02:42:04 am    Post subject:

Ok well let me explain. The best method is to search your data to see if there is a byte that does not recur in your data. If there isn't you find the byte that occurs the least.

Then when you are compressing the data and you find the flagbyte value you turn it into a run.

flagbyte=$02

.db $01,$01,$01,$01,$01,$02,$03,$03,$03,$03,$03,$03

compressed

.db $02,$05,$01,$02,$01,$02,$02,$06,$03


This is the only way you could ever end up with a higher data size than the original data. Yet it is unlikely that the user will use all 256 bytes within their data block. So you just simply find a byte that is unused and set it as a flag byte.


Now for the 16bit size for large data blocks that are the same. I would simply set a flag for data less than or equal to 255, and then set a secondary flag for a 16bit size.
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 26 May 2003 02:45:25 am    Post subject:

If it is necessary I can code it rather easily. It is not that hard and I am currently working on a rle compression program for pictures. It's called Zippic and it will compress pics into an appvar. This of course will be useful to basic programmers as it will allow them to have many more pics.
Back to top
David
The XORcist!


Advanced Member


Joined: 20 May 2003
Posts: 268

Posted: 26 May 2003 08:09:03 am    Post subject:

The standard of RLE encoding is that 0 is equal to 256 repetitions. Even though it looks weird, it is best kept that way for compability.

I wrote a RLE compression routine once. I can post it to you if you want.

If you are trying to compress a tilemap, you often use a limited number of bytes.
Let's say you have 16 tiles numbered 0-15. Then you'd only need the lower 4 bits (a nibble) to represent one tile (2^4 = 16). In other words, it would be possible to compress the tilemap 50 % as one could store two tiles in one byte Rolling Eyes
Back to top
NETWizz
Byte by bit


Bandwidth Hog


Joined: 20 May 2003
Posts: 2369

Posted: 26 May 2003 08:09:34 am    Post subject:

My compression routine where you do not encode data unless you have more than 3 consecutive bytes is faster and will compress more completely.

As for RLE, you are correct, it will work.

I think it would be cool to save the uncompressed size and save a byte for flags. When In Nimbus, it could be called an RLE compressed Ion, etc

Then, when they wish to run it, the size is saved, so we inseart the correct number of bytes at usermem and uncompress it there. If writeback is neccessary, we would make the changes to the uncompressed data and recompress.

What do you think?

We could even wright a VB or C program to compress all NimbusOS programs. Very Happy
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 26 May 2003 12:12:32 pm    Post subject:

That actually sounds really cool. You wouldn't expect to get really high compression unless they have large data blocks in their code though.
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 26 May 2003 01:30:17 pm    Post subject:

Oh and here's a screen shot of the grayscale in action. It actually looks better on calculator.

Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 26 May 2003 01:33:18 pm    Post subject:

Also keep this in mind that, that screenshot is one of a ti83+ with perfect 4-level grayscale. Thanks to one of my fellow programmers at maxcoderz. Diederik Kingma.

Last edited by Guest on 26 May 2003 01:34:40 pm; edited 1 time in total
Back to top
NETWizz
Byte by bit


Bandwidth Hog


Joined: 20 May 2003
Posts: 2369

Posted: 27 May 2003 02:01:15 am    Post subject:

David, please post the RLE encoder.

Juistin, How does your greyscale engine work? I would assume it uses system interrupts.
Back to top
David
The XORcist!


Advanced Member


Joined: 20 May 2003
Posts: 268

Posted: 27 May 2003 06:58:13 am    Post subject:

Here's the code for the rle encoder:

Code:
;Run length encoding (RLE)

;Programmed by David Lindström,
;okvin@tiscali.se. Member of the
;Cirrus Programming group
;http://cirrus.tigalaxy.com
;Use in your own programs as you like,
;and give me credits if you like it!
;======
;Inputs
;======
;HL-Pointer to uncompressed data
;BC-Number of bytes to compress
;DE-Pointer to compressed data

;======
;OUTPUT
;======
;DE - Size of compressed data

#define flag 255

 push de
 push bc
new_block:
 ld b,0
scan:
 ld c,(hl)
 inc hl
 ex (sp),hl
 dec hl
 inc b
 ld a,h
 or l
 ex (sp),hl
 jr z,compare
 ld a,b   
 or a
 jr z,compare
 ld a,c
 cp (hl)
 jr z,scan

compare:
 ld a,b
 ex de,hl
 cp 3
 jr nc,storeRUN
 dec a
 jr z,store_onebyte+1
 ld (hl),c

store_onebyte:
 inc hl
 ld (hl),c
 inc hl
 ex (sp),hl
 ld a,h
 or l
 ex (sp),hl
 ex de,hl
 jr nz,new_block
 pop bc
 pop de
 ret

storeRUN:
 ld (hl),flag
 inc hl
 ld (hl),b
 jr store_onebyte

.end
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 27 May 2003 08:32:07 am    Post subject:

Jbirk wrote:
Juistin, How does your greyscale engine work?  I would assume it uses system interrupts.

It's not mine. It's developed by Diederik Kingma. It uses a IM2 interrupt that quickly changes between two bitmaps of the same picture. It is a little more complicated than that because his routine must interlace the pixels to prevent the entire screen from flashing. Bt interlacing it isolates flickering to the pixels that gives it only a slight movement effect.
Back to top
NETWizz
Byte by bit


Bandwidth Hog


Joined: 20 May 2003
Posts: 2369

Posted: 27 May 2003 01:26:48 pm    Post subject:

I thought you said it was 4 level greyscale.

I guess 2 level is black, so you must have two shades of grey.

I know that interlace means that every other line is drawn, but how is the image drawn exactly?
Back to top
NETWizz
Byte by bit


Bandwidth Hog


Joined: 20 May 2003
Posts: 2369

Posted: 27 May 2003 01:27:28 pm    Post subject:

David wrote:
Here's the code for the rle encoder:

Code:
;Run length encoding (RLE)

;Programmed by David Lindström,
;okvin@tiscali.se. Member of the
;Cirrus Programming group
;http://cirrus.tigalaxy.com
;Use in your own programs as you like,
;and give me credits if you like it!
;======
;Inputs
;======
;HL-Pointer to uncompressed data
;BC-Number of bytes to compress
;DE-Pointer to compressed data

;======
;OUTPUT
;======
;DE - Size of compressed data

#define flag 255

 push de
 push bc
new_block:
 ld b,0
scan:
 ld c,(hl)
 inc hl
 ex (sp),hl
 dec hl
 inc b
 ld a,h
 or l
 ex (sp),hl
 jr z,compare
 ld a,b   
 or a
 jr z,compare
 ld a,c
 cp (hl)
 jr z,scan

compare:
 ld a,b
 ex de,hl
 cp 3
 jr nc,storeRUN
 dec a
 jr z,store_onebyte+1
 ld (hl),c

store_onebyte:
 inc hl
 ld (hl),c
 inc hl
 ex (sp),hl
 ld a,h
 or l
 ex (sp),hl
 ex de,hl
 jr nz,new_block
 pop bc
 pop de
 ret

storeRUN:
 ld (hl),flag
 inc hl
 ld (hl),b
 jr store_onebyte

.end

David, thanks for the RLE encoder.

It looks great.
Back to top
Justin W.
Shattered Silence


Advanced Member


Joined: 24 May 2003
Posts: 429

Posted: 27 May 2003 05:24:31 pm    Post subject:

The person to ask how it works and could explain it to you the best is Diederik Kingma. [email=dedurk@hotmail.com]dedurk@hotmail.com[/email]
Back to top
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    » Goto page 1, 2, 3, 4, 5, 6, 7, 8, 9  Next
» View previous topic :: View next topic  
Page 1 of 9 » All times are GMT - 5 Hours

 

Advertisement