Crunch - very lightweight unpacker used in our Android and bada games

Previous parts

• Simple cross-platform game engine - Introduction
• Universal Box2D debug draw for OpenGL ES 1.x and OpenGL ES 2.0
• Loading images under Windows 
• Load images under Android with NDK and JNI
• Using JNI_OnLoad() in Adroid NDK development 
• Simple streaming audio mixer for Android with OpenSL ES - part 1  
• Simple streaming audio mixer for Android with OpenSL ES - part 2 

UPDATE: next day after writing this article I explored zlib compression library and found it very easy to implement. Read how to do it in "Using zlib compression library in Adroid NDK". My own unpacking utility, I spent lot of time with, described further down still works within our engine and as it is very small and fast in decompression I still may have use for it in projects without zlib. Teaching from this for me: "think twice, cut once".

 Here is next article on mobile games programming topics I came across when building our small games. This time it is about way how to minimize size of your game assets on the disk and how to quickly unpack them without need of Java code part or without need of any big library.

 Common way is to pack or compress the assets to the smallest possible size to reduce space consumed on target device. There are lossy compression formats like .jpg for pictures but what if lossless compression is needed? The possible solution in Android NDK development is to use zlib library. But it brings some overhead before you get familiar with it.

Crunch - the packer

 Fortunately I found very old program by me written in basic that compresses the data and rewritten it into Java. The program runs very slowly, but gives good results so I am using it now for assets compression. It also has only 6 bytes header, thus it is very easy to work with it. The program names Crunch and you can download it here.

 The Crunch looks like this:

 You can add multiple files and delete them from list. You can also set number of "Window bits" which says how far back in data the matches are being searched and "Match bits" which says how long can the matches be.

 The program can only compress the data. The result starts with 6 bytes header:

+0: length of packed data (4 bytes)
+4: window size bits (1 byte)
+5: match size bits (1 byte)
+6: packed data

Unpacking data

 Now  when we have our data packed, we need to decompress them in the game. To do it we first create IPacker interface that will help us to add different packing algorithms or wrap some 3rd party libraries in future.

#ifndef IPACKER_H_
#define IPACKER_H_

#include "../../System/system.h"

namespace SBC
{
namespace Engine
{

class IPacker
{
public:
 virtual ~IPacker() {};

public:
 // encodes data and returns pointer to heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* encode(u8* aUnpackedData, s32 aSize) = 0;
 virtual SBC::System::Collections::ByteBuffer* encode(
   SBC::System::Collections::ByteBuffer& aUnpackedData) = 0;
 // decodes data and returns heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* decode(u8* aPackedData, s32 aSize) = 0;
 virtual SBC::System::Collections::ByteBuffer* decode(
   SBC::System::Collections::ByteBuffer& aPackedData) = 0;
};

} /* namespace Engine */
} /* namespace SBC */
#endif /* IPACKER_H_ */

 ByteBuffer is class that I use for convenient manipulation with byte data (unsigned char / u8). It allows reading of int, short or char as well as storing it into ByteBuffer.

 Next we will implement this interface in class SBCDepacker:

#ifndef SBCDEPACKER_H_
#define SBCDEPACKER_H_

#include "IPacker.h"

namespace SBC
{
namespace Engine
{

class SBCDepacker: public IPacker
{
public:
 SBCDepacker();
 virtual ~SBCDepacker();

public:
 // IPacker implementation
 // encodes data and returns pointer to heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* encode(u8* aUnpackedData, s32 aSize);
 virtual SBC::System::Collections::ByteBuffer* encode(SBC::System::Collections::ByteBuffer& aUnpackedData);
 // decodes data and returns heap allocated ByteBuffer with it
 virtual SBC::System::Collections::ByteBuffer* decode(u8* aPackedData, s32 aSize);
 virtual SBC::System::Collections::ByteBuffer* decode(SBC::System::Collections::ByteBuffer& aPackedData);

private:
 u32 readData(s32 aNumBits, SBC::System::Collections::ByteBuffer& aPackedData);

private:
 u8 mData;
 u8 mDataBitsRest;
};

} /* namespace Engine */
} /* namespace SBC */
#endif /* SBCDEPACKER_H_ */

 It just implements methods from interface and ads private method readData() that is able to read requested number of bits from array of bytes.

 Here is implementation of decode() and readData() methods. As we can only unpack the data, the implementation for encode() just writes error message to the output. All source files is possible to download here:

//------------------------------------------------------------------------
ByteBuffer* SBCDepacker::decode(ByteBuffer& aPackedData)
{
 // clear data
 mData = 0;
 mDataBitsRest = 0;

 // read header
 s32 length = aPackedData.getInt();
 s8 winBits = aPackedData.getChar();
 s8 matchBits = aPackedData.getChar();

 // create byte array for result
 ByteBuffer* unpacked = new ByteBuffer();
 unpacked->construct(length);
 u8* dest = unpacked->getDataPtr();

 // not packed - just read
 if (!winBits && !matchBits)
 {
  memcpy(dest, aPackedData.getPositionPtr(), length);
 }
 // if packed then decode
 else
 {
  while (length)
  {
   // read 1 bit and check whether it is packed or not
   u32 result = readData(1, aPackedData);

   // packed
   if (result)
   {
    s32 zpet = readData(winBits, aPackedData);
    s32 shoda = readData(matchBits, aPackedData);

    for (s32 i = shoda; i > 0; --i)
    {
     *(dest) = *(dest - zpet);
     ++ dest;
    }

    length -= shoda;
   }
   // unpacked
   else
   {
    result = readData(8, aPackedData);

    *(dest ++) = (u8) (result & 0xFF);
    -- length;
   }
  }
 }

 // set limit to capacity
 unpacked->setLimit(unpacked->getCapacity());
 
 return unpacked;
}

//------------------------------------------------------------------------
u32 SBCDepacker::readData(s32 aNumBits, ByteBuffer& aPackedData)
{
 u32 result = 0;

 // while not requested number of bits read
 while (aNumBits > 0)
 {
  // if out of bits read next byte
  if (!mDataBitsRest)
  {
   mData = (u8) aPackedData.getChar();
   mDataBitsRest = 8;
  }

  // how many bits to read (limited with remaining bits)
  u32 num = Math::min(mDataBitsRest, aNumBits);
  // create mask for given number of bits
  u32 mask = (1 << num) - 1;

  // shift previous result and add masked values
  result = (result << num) | (mData & mask);

  // adjust variables for next read
  aNumBits -= num;
  mDataBitsRest -= num;
  mData >>= num;
 }

 return result;
}

Conclusion

 That's all. With this simple class you can unpack data previously packed with Crunch utility like this:

 // load compressed file from disk
 ByteBuffer* compressed = aLoader->loadToByteBuffer(aIdx);

 // create unpacker and unpack data
 SBCDepacker sbcDepacker;
 ByteBuffer* unpacked = sbcDepacker.decode(*compressed);

 // delete compressed data - no more needed now as all data is in unpacked
 delete compressed;

  If you do not want or need to link whole zlib library or you want something really simple that works, then you may give a try to Crunch. In our games we are currently using it for packing ETC1 textures. These are packed itself but format is targeted to reduce GPU bandwidth not minimize disk space. It can be reduced almost to half of the size with Crunch so the disk space consumption is decreased significantly.

Download Crunch 1.0

Source for unpacking