Decompressing sprites

[Michal]

Hi,

i make small utility for processing GRF files. I successfully parse size, info, ....... yrel but i have problem with sprite decompressing. Maybe i wrong understand decompress procedure from http://www.ttdpatch.net/grfcodec/grf.html . For example, i extract (with HEX editor) first sprite from trg1r.grf (TTD cursor).

Code: Select all

0x0000: 14 0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 
0x0010: 20 20 20 20 20 E0 05 01 0F A0 17 01 21 A8 18 07 
0x0020: 0E 0A 0A 0A 0A 0A 0A E0 05 02 21 20 B0 18 02 0E 
0x0030: 0E A8 17 A0 18 01 0D A8 17 01 58 B0 18 01 0D C0 
0x0040: 18 02 0C 0D E8 17 98 18 B8 19 01 20 90 18 B0 19 
0x0050: A0 18 01 0C C0 17 90 19 02 0C 0C D8 73 C0 19 B0 
0x0060: 18 01 0B D8 8A E8 19 90 19 02 0B 0B D8 A1 B0 19 
0x0070: C0 18 D0 B8 E8 19 90 19 C8 CF 90 19 A0 B1 90 19 
0x0080: 90 19 90 19 90 19 90 19 90 19 02 0B 0B E8 0E 90 
0x0090: 19 C9 5B 01 88 E8 0E 90 19 E0 17 C9 5A 90 19 B0 
0x00A0: 17 90 19 B8 17 90 19 02 88 6A B8 5C 90 19 D0 17

First byte (code): value 0x14 (00010100)

MSB is not set (0), it means code + next 127 bytes are verbatim chunk if code<>0. If code=0, next 128 bytes (without code byte) are verbatim chunk.

Now, we are on address 0x0080 (code): value 0x90 (10010000)

MSB is set (1), it means bits 3..7 are negate value of the length, bits 0..2 are high bits of an offset.
Low bits are in the next byte (lofs).

0x0081 (lofs): value 0x19 (00011001)

Okay. Bits 3..7 from code: 10010, after negate: 01101 = length = 13 bytes.
Bits 0..2 from code | lofs: 000 | 00011001 = offset = 25 bytes.

Now i copy to output 13 bytes from address 0x0067 (actual 0x0080 - offset 0x0019) and return back to address 0x0082.

byte (code) 0x0082: ........ etc

--

It's right? I use this method but output is "strange". Josef's C source don't help me. C isn't my favorite language.

And sorry, my english is wrong.

Michal

[Patchman]

MSB is not set (0), it means code + next 127 bytes are verbatim chunk if code<>0. If code=0, next 128 bytes (without code byte) are verbatim chunk.

You're confusing + and &. It's not "plus", it's a bitwise "and", so what follows is 14h=20 bytes of verbatim data.

[Michal]

I see. code&7fh, IMO if MSB is not set (0) then code&7fh=code (0xxxxxxx & 01111111 = 0xxxxxxx).

Okay, i modify my program but output isn't correct. First 48 bytes of uncompressed sprite must be:

Code: Select all

0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20 20 20 20 20
0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 09 20 20 20 20 20 20 20 20 20 20

I writed this sequence from first 20 bytes and complete in agreement colors of pixels of uncompressed image.

Now compressed sprite:

Code: Select all

0x0000: 14 0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 
0x0010: 20 20 20 20 20 E0 05 01 0F A0 17 01 21 A8 18 07 
0x0020: 0E 0A 0A 0A 0A 0A 0A E0 05 02 21 20 B0 18 02 0E 
0x0030: 0E A8 17 A0 18 01 0D A8 17 01 58 B0 18 01 0D C0 
0x0040: 18 02 0C 0D E8 17 98 18 B8 19 01 20 90 18 B0 19 
0x0050: A0 18 01 0C C0 17 90 19 02 0C 0C D8 73 C0 19 B0 
0x0060: 18 01 0B D8 8A E8 19 90 19 02 0B 0B D8 A1 B0 19 
0x0070: C0 18 D0 B8 E8 19 90 19 C8 CF 90 19 A0 B1 90 19 
0x0080: 90 19 90 19 90 19 90 19 90 19 02 0B 0B E8 0E 90 
0x0090: 19 C9 5B 01 88 E8 0E 90 19 E0 17 C9 5A 90 19 B0 
0x00A0: 17 90 19 B8 17 90 19 02 88 6A B8 5C 90 19 D0 17

----

0x0000 (code) 14h 00010100, 20 decimal

MSB = 0, program send to output next 20 bytes

Code: Select all

output:
0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20

----

0x0015 (code) E0h 11100000

MSB = 1, bits 3..7 11100, negated: 00011 = length = 3 bytes

0x0016 (lofs) 05h 00000101
code bits 0..2 | lofs: 000|00000101 = offset = 5 bytes

program send to output 3 bytes from 0x0010 = 20 20 20

Code: Select all

output:
0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20 20 20 20

----

0x0017 (code) 01h 00000001, 1 decimal

MSB = 0, program send to output next 1 byte = 0F

Code: Select all

output:
0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20 20 20 20 0F

----

0x0019 (code) A0h 10100000

MSB = 1, bits 3..7 10100, negated: 01011 = length = 11 bytes

0x001A (lofs) 17h 00010111
code bits 0..2 | lofs: 000|00010111 = offset = 23 bytes

program send to output 11 bytes from 0x0002 = 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B

Code: Select all

output:
0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20 20 20 20 0F
0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B

----

0x001B (code) 1h 00000001, 1 decimal

MSB = 0, program send to output next 1 byte = 21

Code: Select all

output:
0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20 20 20 20 0F
0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 21

----

0x001D (code) A8h 10101000

MSB = 1, bits 3..7 10101, negated: 01010 = length = 10 bytes

0x001E (lofs) 18h 00011000
code bits 0..2 | lofs: 000|00011000 = offset = 24 bytes

program send to output 24 bytes from 0x0005 = 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A

Code: Select all

output:
0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20 20 20 20 0F
0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 21 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A

----

etc.

Output is unmatched and i don't know why. Algorithm is probably correct.

Michal

[Patchman]

MSB = 1, bits 3..7 11100, negated: 00011 = length = 3 bytes

Not negated, negative (sorry the page was unclear there). 11100 is (using two's complement as usual) equal to -4, so the negative would be 4, not 3.

In C you would get that from -(code >> 3) if code is a signed char, i.e. doing an arithmetic right shift instead of a logical right shift. It may simply work to take -(code / 8) in your language as long as code is declared as a signed byte variable, it won't work if it's unsigned.

[Michal]

I modify program again but output still wrong. I know, i am troublesome but helpless too.

This is log from program, detailed step by step.

Code: Select all

compressed sprite:
0x0000: 14 0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 
0x0010: 20 20 20 20 20 E0 05 01 0F A0 17 01 21 A8 18 07 
0x0020: 0E 0A 0A 0A 0A 0A 0A E0 05 02 21 20 B0 18 02 0E 
0x0030: 0E A8 17 A0 18 01 0D A8 17 01 58 B0 18 01 0D C0 
0x0040: 18 02 0C 0D E8 17 98 18 B8 19 01 20 90 18 B0 19 
0x0050: A0 18 01 0C C0 17 90 19 02 0C 0C D8 73 C0 19 B0 
0x0060: 18 01 0B D8 8A E8 19 90 19 02 0B 0B D8 A1 B0 19 
0x0070: C0 18 D0 B8 E8 19 90 19 C8 CF 90 19 A0 B1 90 19 
0x0080: 90 19 90 19 90 19 90 19 90 19 02 0B 0B E8 0E 90 
0x0090: 19 C9 5B 01 88 E8 0E 90 19 E0 17 C9 5A 90 19 B0 
0x00A0: 17 90 19 B8 17 90 19 02 88 6A B8 5C 90 19 D0 17 

Code: Select all

LOG:
file position: 0  (address: 0x0)
code: 0x14  00010100  20 -MSB = 0
read 20 bytes

0F 0F 0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 20 20 20 20 
-----------------------------------------
file position: 21  (address: 0x15)
code: 0xE0  11100000  -MSB = 1
code bits 3..7: 11100
-> length: 4
 
file position: 22  (address: 0x16)
lofs: 0x5  (00000101)
-> offset=code bits 0..2 | lofs: 000 | 00000101 =5
Jump to address 0x11 and read 4 bytes

20 20 20 20 
-----------------------------------------
file position: 23  (address: 0x17)
code: 0x1  00000001  1 -MSB = 0
read 1 bytes

0F 
-----------------------------------------
file position: 25  (address: 0x19)
code: 0xA0  10100000  -MSB = 1
code bits 3..7: 10100
-> length: 12
 
file position: 26  (address: 0x1A)
lofs: 0x17  (00010111)
-> offset=code bits 0..2 | lofs: 000 | 00010111 =23
Jump to address 0x3 and read 12 bytes

0F 0E 0E 0D 0D 0D 0D 0C 0C 0B 0B 0A 
-----------------------------------------
file position: 27  (address: 0x1B)
code: 0x1  00000001  1 -MSB = 0
read 1 bytes

21 
-----------------------------------------
file position: 29  (address: 0x1D)
code: 0xA8  10101000  -MSB = 1
code bits 3..7: 10101
-> length: 11
 
file position: 30  (address: 0x1E)
lofs: 0x18  (00011000)
-> offset=code bits 0..2 | lofs: 000 | 00011000 =24
Jump to address 0x6 and read 11 bytes

0D 0D 0D 0D 0C 0C 0B 0B 0A 20 20 
-----------------------------------------
.
.
.
etc

It is right?

Michal

[Patchman]

It seems you're using the offset as offset in the input file location, it should be an offset in the output data location instead. E.g., this:

Code: Select all

 file position: 30  (address: 0x1E) 
lofs: 0x18  (00011000) 
-> offset=code bits 0..2 | lofs: 000 | 00011000 =24 
Jump to address 0x6 and read 11 bytes

should jump to output location 38-24=14 (0Eh) and copy 11 bytes from there, instead of from position 6 in the input stream.

[Michal]

Olala, sorry, it's my mistake. I was omit - "So you subtract the offset from your position in the output stream and copy the given number of bytes."

Program is functional, i can sleep now.

One more question. GRFCodec choose pallete depending on GRF-file name?

Thanks a lot.

Michal

[chipetke]

As far as I know, it does not use the file name for this purpose.
IIRC it defaults to windows palette, and uses dos palette if you specify an option... anyways, the manual of grfcodec tells it clearly

[DaleStan]

IIRC it defaults to windows palette, and uses dos palette if you specify an option... anyways, the manual of grfcodec tells it clearly

The opposite. GRFCodec defaults to DOS palette, unless you are decoding:
TRG1R.gr, TRGCR.grf, TRGHR.grf, TRGIR.grf, TRGTR.grf, TREDIT.grf, TREND.grf, TRTITLE.grf, TRHCOM.grf, TRHCOM2.grf, or TTDPATCHW.grf.

So yes, it does check the file name, but it's not particularly intelligent.

[chipetke]

sorry...

[Michal]

Thanks

[Michal]

Oh no, I have problem again.

I tried parse and uncompressed all sprites from trg1r.grf. Problem is sprite 451 (character "!").

Code: Select all

trg1.grf

0x392E: 67 00 , (size)  - 103 decimal
0x3930: 09    , (info)  -   9 decimal
0x3931: 0E    , (ysize) -  14 decimal
0x3932: 03 00 , (xsize) -   3 decimal
0x3934: 00 00 , (xrel)  -   0 decimal
0x3936: 01 00 , (yrel)  -   1 decimal

It's agree with NFO but first speciality, size of the uncompressed image is 42 bytes (xsize*ysize) i.e. 50 bytes with info...yrel. But size = 103.

compressed sprite:

Code: Select all

0x0000: 22 1C 00 21 00 26 00 2B 00 30 00 35 00 3A 00 3F 
0x0010: 00 44 00 49 00 4E 00 53 00 55 00 5A 00 83 00 01 
0x0020: 01 01 83 E0 05 D8 0A A0 0F 90 0F 90 0F 01 80 A8 
0x0030: 39

log:

Code: Select all

input stream position: 0
code: 0x22  00100010  34 -MSB = 0
read 34 bytes

1C 00 21 00 26 00 2B 00 30 00 35 00 3A 00 3F 00 44 00 49 00 4E 00 53 00 55 00 5A 00 83 00 01 01 01 83 
-----------------------------------------
input stream position: 35
code: 0xE0  11100000  ,MSB = 1
code bits 3..7: 11100
-> length: 4
 
input stream position: 36
lofs: 0x5  (00000101)
-> offset=code bits 0..2 | lofs: 000 | 00000101 =5
 
Jump to output stream position 29 and read 4 bytes

00 01 01 01 
-----------------------------------------
input stream position: 37
code: 0xD8  11011000  ,MSB = 1
code bits 3..7: 11011
-> length: 5
 
input stream position: 38
lofs: 0xA  (00001010)
-> offset=code bits 0..2 | lofs: 000 | 00001010 =10
 
Jump to output stream position 28 and read 5 bytes

83 00 01 01 01 
-----------------------------------------
input stream position: 39
code: 0xA0  10100000  ,MSB = 1
code bits 3..7: 10100
-> length: 12
 
input stream position: 40
lofs: 0xF  (00001111)
-> offset=code bits 0..2 | lofs: 000 | 00001111 =15
 
Jump to output stream position 28 and read 12 bytes

83 00 01 01 01 83 00 01 01 01 83 00 
-----------------------------------------
input stream position: 41
code: 0x90  10010000  ,MSB = 1
code bits 3..7: 10010
-> length: 14
 
input stream position: 42
lofs: 0xF  (00001111)
-> offset=code bits 0..2 | lofs: 000 | 00001111 =15
 
Jump to output stream position 40 and read 14 bytes

01 01 01 83 00 01 01 01 83 00 01 01 01 83 
-----------------------------------------
input stream position: 43
code: 0x90  10010000  ,MSB = 1
code bits 3..7: 10010
-> length: 14
 
input stream position: 44
lofs: 0xF  (00001111)
-> offset=code bits 0..2 | lofs: 000 | 00001111 =15
 
Jump to output stream position 54 and read 14 bytes

00 01 01 01 83 00 01 01 01 83 00 01 01 01 
-----------------------------------------
input stream position: 45
code: 0x1  00000001  1 -MSB = 0
read 1 bytes
80 
-----------------------------------------
input stream position: 47
code: 0xA8  10101000  ,MSB = 1
code bits 3..7: 10101
-> length: 11
 
input stream position: 48
lofs: 0x39  (00111001)
-> offset=code bits 0..2 | lofs: 000 | 00111001 =57
 
Jump to output stream position 27 and read 11 bytes

00 83 00 01 01 01 83 00 01 01 01 
-----------------------------------------

and output:

Code: Select all

1C 00 21 00 26 00 2B 00 30 00 35 00 3A 00 3F 00
44 00 49 00 4E 00 53 00 55 00 5A 00 83 00 01 01
01 83 00 01 01 01 83 00 01 01 01 83 00 01 01 01
83 00 01 01 01 83 00 01 01 01 83 00 01 01 01 83
00 01 01 01 83 00 01 01 01 83 00 01 01 01 83 00
01 01 01 80 00 83 00 01 01 01 83 00 01 01 01

All sprites before 451 was uncompressed correctly and sprite 451 is normal sprite as all before him.

Michal

[Patchman]

See "Tile Sprites" in the GRF format specs.

[Michal]

Oops, I checked 3rd info bit, several times, but i've seen 0. I don't know why . Sorry again. I need time off.

Michal