Results 1 to 14 of 14

Thread: New challenge for encode.ru! Help on an unknown compression format

  1. #1
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts

    New challenge for encode.ru! Help on an unknown compression format

    Hi pals, I have another question for you. From oldgamesitalia.net, a community that translate games and create tools to help other people translate oldgames into their language easily. For free.
    We're struggling to find out how to decode a raster image. We tried RLE and some LZW dialect but nothing worked.
    It is a compression used by Dynamix for her old dos games, in particular case "Rise of the Dragon" (an old adventure game) but all the DGDS engine uses this format, so hundreds of games.

    The format is VQT (can be spotted as a tag inside *.bmp images that aren't plain bmp at all). "VQ" might stand for "vector quantisation". a technique also used in the Westwood video format. Though I'm not sure, since I think it works on differences between frames, and VQT is also used for still SCR images.
    The image I brought to your attention is a single frame with transparent background of the main character falling, so the same image shifted on screen from top to bottom.
    Anyway, the image I need to decode is a 24 pixel wide and 14 height, 8bpp without palette.
    here is the RAW:
    Code:
    ......9^.r..6Ç. ....... ù.O..h¢...à........9Ñ...Ç...£....&.$..okkO.`.prr..á...Pá•6..8<SBª...µ...joù....R`.qBi.áN.@Y{.~b;{|B;O;.A;</.m*k.kg.......8.hô.D¢7O;..É...AêÉv÷K6gy^.v......v..8ù...÷`.6.Ç.ö....%ÅO{..]¢.22â....Ç
    I attached the file I took the raw from (bfall.bmp). The tags in the file header have information about the dimension of the frame and the file length but nothing more. I think the raw data is the image I need to decode, exactly 216 bytes (0xD8, the size after "VQT:" tag in bfall.bmp)
    Attached you will also find 4 png that show the frame. It is the figure falling with different hacked backgrounds captured in-game.

    Hope you could help us, we're kind of stuck.
    Cheers!
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	dragon_015.png 
Views:	124 
Size:	17.3 KB 
ID:	5333   Click image for larger version. 

Name:	dragon_016.png 
Views:	113 
Size:	14.7 KB 
ID:	5334   Click image for larger version. 

Name:	dragon_017.png 
Views:	72 
Size:	2.1 KB 
ID:	5335   Click image for larger version. 

Name:	dragon_018.png 
Views:	68 
Size:	2.9 KB 
ID:	5336  
    Attached Files Attached Files
    Last edited by theruler; 24th September 2017 at 15:01.

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Well, entropy analysis (via cdm) says bit order is 0 to 7.
    Optimal parsing output on bit stream is in attached files (0s.txt is simply sorted).
    Sample:
    Code:
    "000000000000000100"
    "000000000001011111"
    "000000000010"      
    "000000000010000000"
    "00000000001011011" 
    "0000000000101111"  
    "000000000100"      
    "00000000010100"    
    "00000000010110110" 
    "000000001101101"   
    "000000001101101111"
    I suppose it could be unary coding of log(runlen) + run len.
    Attached Files Attached Files

  3. #3
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Unfortunately I don't know what that means, sorry. Could you please be "less" specific?

    A friend rebuilt the image from a screenshot into another image format used by the game that he has previously successfully decoded.
    Attached are raw data, probably the result of the compressed raw data I previously posted. The problem is to find the algorithm that can go from A to B.


    Code:
    0000000000000000000000000000FA000000000000000000 ..............ú.........
    00000000000000000000000000FA9C000000000000000000 .............úœ.........
    00000000000000000000000000E3D2000000000000000000 .............ãÒ.........
    00000000000000000000000000D2E3000000000000000000 .............Òã.........
    00DA00000000000000000000009CDA00E4DA0000FA870000 .Ú...........œÚ.äÚ..ú‡..
    00DAE50000000000796D790000DBDA008793E600E329D300 .Úå.....ymy..ÛÚ.‡“æ.ã)Ó.
    00DAE5BC72727272F0797379F0DA13DB93D3DB00F021E500 .Úå¼rrrrðysyðÚ_Û“ÓÛ.ð!å.
    00DAE5DADBDBDBDADA13E379DAD979E5DADA73996EDBDB00 .ÚåÚÛÛÛÚÚ_ãyÚÙyåÚÚs™nÛÛ.
    0000000000000000DBDB13DAD99CE5DAE279E3DBDBE50000 ........ÛÛ_ÚÙœåÚâyãÛÛå..
    F0050000F8BC75CAF0D9DAD92FE5DAE2D6F0000000000000 ð_..ø¼uÊðÙÚÙ/åÚâÖð......
    DAF0BCCAF4D9DA089CF4DA79E5DADA207CDB000000000000 Úð¼ÊôÙÚ_œôÚyåÚÚ_|Û......
    00DADADADA0000DADA20BCDADA202F79DB00000000000000 .ÚÚÚÚ..ÚÚ ¼ÚÚ_/yÛ.......
    0000000000000000DADAE5DA7979DBDB0000000000000000 ........ÚÚåÚyyÛÛ........
    000000000000000000DADADBDADB00000000000000000000 .........ÚÚÛÚÛ..........
    Attached Images Attached Images  
    Attached Files Attached Files

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    What I mean is,

    1) the "raw" file looks like bitcode, visually. But I doubt that its huffman.

    2) from repeated patterns in "raw" (which I listed in txt files) we can try finding clues about coding method.
    For example, I see lots of "000...01" patterns in there, which could mean unary coding.
    https://en.wikipedia.org/wiki/Unary_coding
    Like, it could be RLE with unary coding of length - might make sense with small sprites like that.

    If that unpacked picture is precise, we can also try finding numbers from it (like "FA") in the "raw".
    At least ones that would be encoded by literals with LZ should be there.

    3) From the "VQT" name, it could be also some vector quantization
    https://en.wikipedia.org/wiki/Vector...ta_compression
    But in that case we'd not be able to decode it without actual algorithm.

  5. The Following User Says Thank You to Shelwien For This Useful Post:

    theruler (25th September 2017)

  6. #5
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Thanks a lot for the explanation Shelwien.
    There's no FA in original VQT, but I've found something that is definitely in that raw data we've reconstructed.
    this chunk of four bytes from bfall.bmp:
    D29CE3DA

    Could it be of any help?
    Last edited by theruler; 24th September 2017 at 20:59.

  7. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    That's certainly interesting. Doesn't it mean that picture has to be rotated though?
    Also, I guess it means that bitcode is 7-0, not 0-7.

    Still, you can look for FA as "11111010" in binary code, because compression methods
    frequently use codes with variable number of bits.
    Its possible that your D2 block just got accidentally aligned.
    Attached Files Attached Files

  8. The Following User Says Thank You to Shelwien For This Useful Post:

    theruler (25th September 2017)

  9. #7
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Shelwien View Post
    Doesn't it mean that picture has to be rotated though?
    That's exactly what we've discovered, too.

    So you suggest to put all in binary and than back? Which kind of decompression?
    We don't actually need to re-compress the image, we have to decode it to put in a viewable form, edit and insert back in the container in a format we've already found working (VGA/BIN Dynamix engine DGDS).

  10. #8
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > So you suggest to put all in binary and than back? Which kind of decompression?

    I still don't know that obviously.
    But if we can find patterns, like what is decoded to what, it can help with reverse-engineering.

    > We don't actually need to re-compress the image, we have to decode it to put in a viewable form

    That gives me another idea actually - you can try editing the compressed image (like flipping bits in it) and see what happens to unpacked version.

    Well, the best way is probably to find the program that decodes it - in this case it should be easy enough too, because of the named tags.
    Do you have unencrypted executables for the game?

  11. The Following User Says Thank You to Shelwien For This Useful Post:

    theruler (25th September 2017)

  12. #9
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Nice idea. Trying right now.

    Here is the exe.
    Attached Files Attached Files

  13. #10
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Flipping 9CE3DA02 to E39C02DA turned that pixel green. (019)

    Flipping 395EED72 to 5E3972ED "apparently" did nothing. (020)

    Flipping F06A6F97 to 6AF0976F "apparently" did nothing. (021)
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	dragon_016.png 
Views:	55 
Size:	14.7 KB 
ID:	5348   Click image for larger version. 

Name:	dragon_019.png 
Views:	50 
Size:	14.6 KB 
ID:	5349   Click image for larger version. 

Name:	dragon_021.png 
Views:	45 
Size:	14.6 KB 
ID:	5350  

  14. #11
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Well, the only time "VQT" is mentioned is this:

    seg007:0E3F 33 C0 xor ax, ax
    seg007:0E41 50 push ax
    seg007:0E42 B8 8C 15 mov ax, offset aBmpVqt ; "BMP:VQT:"
    seg007:0E45 50 push ax
    seg007:0E46 FF 76 06 push [bp+arg_0]
    seg007:0E49 9A 52 23 23 2E call FindTag?
    seg007:0E4E 83 C4 06 add sp, 6
    seg007:0E51 83 FA FF cmp dx, -1
    seg007:0E54 75 08 jnz short loc_354BE
    seg007:0E56 3D FF FF cmp ax, -1
    seg007:0E59 75 03 jnz short loc_354BE

    Also, it seems that actual processing is done by some overlay, so none of interesting code is here.

  15. #12
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    The reply from the friend of mine working into the project:

    Yes, I did look into the exe too. The "BMP:VQT:" string (at dseg:158C) is indeed the lookup of the VQT chunk inside the BMP chunk; they treat it like directories and subdirectories. A bit after that in the code it also looks up "BMP:OFF:", so after that it should add the offset to the VQT chunk data pointer and get the actual data to decompress in there. So somewhere after it should be the function to actually decompress it.
    There's another one. "SCR:VQT:", a bit above the "BMP:VQT:" string, at dseg:1570. It's referenced at seg007:005D. Since SCR format only contains one image there's no offsets for this one, so it should go to the decompression code right away. But I really suck at reading logic from 16-bit ASM; IDA doesn't even manage to link these references to the data segment, so I suspect I'm missing a lot more information than that.
    I'm not sure what "actual processing is done by some overlay" means, though.
    Do you mean an overlay file outside the exe?
    Have to check.

  16. #13
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Found a file inside volume.001 that might be the overlay you spoke of.
    It has OVL and VGA tag.
    Attached Files Attached Files

  17. #14
    Member
    Join Date
    Aug 2015
    Location
    Italy
    Posts
    17
    Thanks
    4
    Thanked 0 Times in 0 Posts
    Any news?

Similar Threads

  1. Files hosted on Encode.ru and geocites.com are lost!
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 4
    Last Post: 30th April 2011, 15:51
  2. Replies: 6
    Last Post: 5th April 2011, 18:04
  3. Spam on Encode.ru ?
    By Fairy in forum The Off-Topic Lounge
    Replies: 5
    Last Post: 19th November 2008, 22:58
  4. Long live ENCODE.RU!
    By encode in forum Forum Archive
    Replies: 8
    Last Post: 15th April 2008, 20:53
  5. ENCODE.RU will survive!
    By encode in forum Forum Archive
    Replies: 8
    Last Post: 10th April 2007, 04:37

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •