gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Huffman Decoder in VBA

#23001 - f(DarkAngel) - Fri Jul 02, 2004 3:46 pm

Has anyone got huffman encoding work in VBA (1.7.2)? I've been implementing a huffman encoder and it never works correctly on VBA, i can't be sure since i don't have equipment to test it on real hardware either.
Both Cowbite and GBATek says the 5th byte is treeSize/2-1 but VBA bios.cpp tries to get the original value by (treeSize<<1)+1 instead of (treeSize+1)<<1.

Here's the original code from VBA 1.7.2
Code:

// VisualBoyAdvance - Nintendo Gameboy/GameboyAdvance (TM) emulator.
// Copyright (C) 1999-2003 Forgotten
// Copyright (C) 2004 Forgotten and the VBA development team

// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2, or(at your option)
// any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

void BIOS_HuffUnComp()
{
#ifdef DEV_VERSION
  if(systemVerbose & VERBOSE_SWI) {
    log("HuffUnComp: 0x%08x,0x%08x (VCOUNT=%d)\n",
        reg[0].I,
        reg[1].I,
        VCOUNT);
  }
#endif
 
  u32 source = reg[0].I;
  u32 dest = reg[1].I;

  u32 header = CPUReadMemory(source);
  source += 4;

  if(((source & 0xe000000) == 0) ||
     ((source + ((header >> 8) & 0x1fffff)) & 0xe000000) == 0)
    return; 
 
  u8 treeSize = CPUReadByte(source++);

  u32 treeStart = source;

  source += (treeSize<<1) + 1;
 
  int len = header >> 8;

  u32 mask = 0x80000000;
  u32 data = CPUReadMemory(source);
  source += 4;

  int pos = 0;
  u8 rootNode = CPUReadByte(treeStart);
  u8 currentNode = rootNode;
  bool writeData = false;
  int byteShift = 0;
  int byteCount = 0;
  u32 writeValue = 0;

  if((header & 0x0F) == 8) {
    while(len > 0) {
      // take left
      if(pos == 0)
        pos++;
      else
        pos += (((currentNode & 0x3F)+1)<<1);
     
      if(data & mask) {
        // right
        if(currentNode & 0x40)
          writeData = true;
        currentNode = CPUReadByte(treeStart+pos+1);
      } else {
        // left
        if(currentNode & 0x80)
          writeData = true;
        currentNode = CPUReadByte(treeStart+pos);
      }
     
      if(writeData) {
        writeValue |= (currentNode << byteShift);
        byteCount++;
        byteShift += 8;

        pos = 0;
        currentNode = rootNode;
        writeData = false;

        if(byteCount == 4) {
          byteCount = 0;
          byteShift = 0;
          CPUWriteMemory(dest, writeValue);
          writeValue = 0;
          dest += 4;
          len -= 4;
        }
      }
      mask >>= 1;
      if(mask == 0) {
        mask = 0x80000000;
        data = CPUReadMemory(source);
        source += 4;
      }
    }
  } else {
    int halfLen = 0;
    int value = 0;
    while(len > 0) {
      // take left
      if(pos == 0)
        pos++;
      else
        pos += (((currentNode & 0x3F)+1)<<1);

      if((data & mask)) {
        // right
        if(currentNode & 0x40)
          writeData = true;
        currentNode = CPUReadByte(treeStart+pos+1);
      } else {
        // left
        if(currentNode & 0x80)
          writeData = true;
        currentNode = CPUReadByte(treeStart+pos);
      }
     
      if(writeData) {
        if(halfLen == 0)
          value |= currentNode;
        else
          value |= (currentNode<<4);

        halfLen += 4;
        if(halfLen == 8) {
          writeValue |= (value << byteShift);
          byteCount++;
          byteShift += 8;
         
          halfLen = 0;
          value = 0;

          if(byteCount == 4) {
            byteCount = 0;
            byteShift = 0;
            CPUWriteMemory(dest, writeValue);
            dest += 4;
            writeValue = 0;
            len -= 4;
          }
        }
        pos = 0;
        currentNode = rootNode;
        writeData = false;
      }
      mask >>= 1;
      if(mask == 0) {
        mask = 0x80000000;
        data = CPUReadMemory(source);
        source += 4;
      }
    }   
  }
}


If GBATek and Cowbite are correct, this seems to be a bug and i'm going to post a bug-report to sf tracker.
_________________
death scream...

#23002 - Lord Graga - Fri Jul 02, 2004 4:02 pm

It's not the BIOS huffuncomp routine unless you actually call that routine via ASM... :P

HUFF uncomp is done like this:

Code:
//---------------------------------------------------------------------------------
void HuffUnComp(void *source, void *dest)
//---------------------------------------------------------------------------------
{
   SystemCall(19);
}


This is the definition of SystemCall():
Code:
#if   defined   ( __thumb__ )
#define   SystemCall(Number)    asm ("SWI     "#Number"\n" :::  "r0", "r1", "r2", "r3")
#else
#define   SystemCall(Number)    asm ("SWI     "#Number"   << 16\n" :::"r0", "r1", "r2", "r3")
#endif

#23010 - Miked0801 - Fri Jul 02, 2004 6:14 pm

Bah, right your own decompressor - it'll go faster :)

#23062 - Lupin - Sat Jul 03, 2004 8:13 am

i think he was just posting the uncompress function of VBA, not his own uncompress function.

There was a sample on gbadev some time ago showing huffman uncomp - it worked on VBA
_________________
Team Pokeme
My blog and PM ASM tutorials

#23077 - f(DarkAngel) - Sat Jul 03, 2004 2:38 pm

It think my post was truly clear. I was waiting for at least 1 reply that is an answer related to my question (thanks Lupin).
Graga, i know how to execute a swi. Save such posts to "beginners" section. And i said, that didn't work on VBA. This is why i checked out the VBA source code.
BTW, I don't know how this "own uncompressor" thing got invented.

Lupin, do you still have the source?
_________________
death scream...

#23138 - FluBBa - Mon Jul 05, 2004 1:21 pm

If you own a GBA (which I hope you do) just download a BIOS from the net somehwere, then you can easily see if it's VBA's implementation that doesn't work or if it's on your side.
_________________
I probably suck, my not is a programmer.

#23161 - caitsith2 - Tue Jul 06, 2004 4:26 am

FluBBa wrote:
If you own a GBA (which I hope you do) just download a BIOS from the net somehwere, then you can easily see if it's VBA's implementation that doesn't work or if it's on your side.


Or even better, write your own bios dumping routine, and dump it yourself. It goes something like this. The bios call for MidiKey2Freq is SWI 0x1F, and should be defined as u32 MidiKey2Freq(u32 wavedata, u8 cMK, u8 cFP);.

Code:


    int i, j;

    for (i=0;i<0x4000;i++)
    {
        j = MidiKey2Freq(i-(((i & 3)+1)| 3), 168, 0);
        j = j * 2;
        j = j >> 24;

        //Code here to somehow transfer j over to your PC.  How you do
        // that transfer, depends on what kind of real hardware/pc
        // development setup you have.  One possibility, if you use just a
        // flashcart, is to write j over into the sram, then dump that sram
        // later.
    }

#23163 - DiscoStew - Tue Jul 06, 2004 4:57 am

Are you sure it was a good idea to post that?
_________________
DS - It's all about DiscoStew

#23164 - tepples - Tue Jul 06, 2004 5:01 am

Martin Korth already posted code equivalent to caitsith2's.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#23165 - caitsith2 - Tue Jul 06, 2004 5:59 am

That, and there is an advantage to dumping the bios yourself. The main advantage, is that it is the only legal way to obtain the bios.

#23169 - DiscoStew - Tue Jul 06, 2004 8:57 am

Didn't know, but now I do. It is just one of those things where your not quite sure if it is ok.
_________________
DS - It's all about DiscoStew

#23319 - Lupin - Fri Jul 09, 2004 8:50 pm

Hm, i was wrong - the demo was just about LZSS compression not huffman, anyways here is the demo posted some time ago:

http://www.gbadev.org/download.php?section=misc&filename=lzssdemo.zip
_________________
Team Pokeme
My blog and PM ASM tutorials