News: 11 March 2016 - Forum Rules
Current Moderators - DarkSol, KingMike, MathOnNapkins, Azkadellia, Danke

Author Topic: Necromancer text compression scheme  (Read 2303 times)

tomaitheous

  • Hero Member
  • *****
  • Posts: 543
    • View Profile
    • PC Engine Dev
Necromancer text compression scheme
« on: September 05, 2013, 09:59:00 pm »
I've done quite a bit of work with compression schemes in the past, but this one is pretty unfamiliar to me. It appears to be some sort of binary tree compression scheme.

 There's two varaibles; a down counter (always re/load with a value of $07, check looks for $ff value) and an byte bit mask.

 There's also a table/block. Each entry is either 2 or 3 bytes long (though there might be an entry that is 4 bytes long, IIRC). The ending byte is always $FF. So something like $97,$ff,$07,$ff,$85,$ff. #$ff is the terminator of each entry (which means skip to the next). The mask corresponding bit determines whether to skip 1 byte or two bytes. If two bytes, then the value from the 'block' or tree is added to the tree/block pointer, helping incrementing it. When a non termination value is read, it's passed to the string build routine, and then the tree pointer is reset back to the beginning of the block.

 There's also another block and pointer. When the down counter expires, this pointer is incremented and the mask is reloaded. Neither the base nor the index of the tree access system is reset at this point.

 There's another layer of mechanism in place as well. At the very start of the call, there's a variable that stops the string routine from accumulating. When this variable expires (decremented; 00 = expired), then it will copy valid string data to the string build routine. Else, it just accumulates the second pointer position.

 Soo... does this description sound familiar? Sound like a binary tree compression scheme? I'm on the verge of figuring it out; just need to trace back to the top layer function calls and hopefully begin test (and text) extract trials. Any advice or comments?

-Tom

Malias

  • Sr. Member
  • ****
  • Posts: 294
    • View Profile
Re: Necromancer text compression scheme
« Reply #1 on: September 06, 2013, 01:17:32 am »
If I understand it correctly, it sounds like a table-based Huffman tree.  The ones I've seen before were hard coded, so it's hard to tell.  :-\
The great achievement is to lose one's reason for no reason, and to let my lady know that if I can do this without cause, what should I do if there were cause?
     ~Don Quixote~

tomaitheous

  • Hero Member
  • *****
  • Posts: 543
    • View Profile
    • PC Engine Dev
Re: Necromancer text compression scheme
« Reply #2 on: September 06, 2013, 08:47:50 pm »
If I understand it correctly, it sounds like a table-based Huffman tree.  The ones I've seen before were hard coded, so it's hard to tell.  :-\

 There appears to be a 4 byte header that sets all of this up, but the intro to the game puts hard/immediate values into place of reading from a header table. But in game, appears to be all called from a header table. Hopefully not too many areas/events are hardcoded.


 Edit: Ok, what was throwing me for a loop, was the offsets inside the huffman tree. I figured only variable/values would be there. But that's not the case. Weird. Guess I've never seen it implemented like this (or rather, I never wrote a huffman tree like this). If bit is 1, add the value from the tree to the pointer. If clear, skip two bytes in the table. Actual 'character' is encoded in 3 bytes in the table (pointer accumulators are 2 bytes) and this 'character' also preceded by #$01 - so that the pointer is incremented to align with the char (and not a terminator value of #$ff).

 They kind of missed an optimization. They could have added 'words' to the table entries as well, but appears only single characters are in the entry (once a valid character is read, the position into the tree is reset). Maybe 2 and 3 char groups don't lend well to Japanese/hiragana?
« Last Edit: September 06, 2013, 09:22:10 pm by tomaitheous »

Pikachumanson

  • Hero Member
  • *****
  • Posts: 607
    • View Profile
Re: Necromancer text compression scheme
« Reply #3 on: September 21, 2013, 10:25:02 pm »
When i talked to someone who attempted to hack this game before, kingofcrusher95 i think, he mention something about having to rewrite/write four or five text routines. I'm glad you are trying to figure out what makes this game tick!