yj1.c

//
// PAL DOS compress format (YJ_1) library
//
// Author: Lou Yihua <louyihua@21cn.com>
//
// Copyright 2006 - 2007 Lou Yihua
//
// This file is part of PAL library.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library 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
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
//

// Ported to C from C++ and modified for compatibility with Big-Endian
// by Wei Mingzhi <whistler@openoffice.org>.

// TODO: fix YJ_2 for big-endian

#include "commonx.h"

#ifndef PAL_WIN95

typedef struct _TreeNode
{
   unsigned char   value;
   unsigned char   leaf;
   unsigned short  level;
   unsigned int    weight;

   struct _TreeNode *parent;
   struct _TreeNode *left;
   struct _TreeNode *right;
} TreeNode;

typedef struct _TreeNodeList
{
   TreeNode *node;
   struct _TreeNodeList *next;
} TreeNodeList;

typedef struct _YJ_1_FILEHEADER
{
   unsigned int   Signature;          // 'YJ_1'
   unsigned int   UncompressedLength; // size before compression
   unsigned int   CompressedLength;   // size after compression
   unsigned short BlockCount;       // number of blocks
   unsigned char Unknown;
   unsigned char HuffmanTreeLength; // length of huffman tree
} YJ_1_FILEHEADER, *PYJ_1_FILEHEADER;

typedef struct _YJ_1_BLOCKHEADER
{
   unsigned short UncompressedLength; // maximum 0x4000
   unsigned short CompressedLength;   // including the header
   unsigned short LZSSRepeatTable[4];
   unsigned char LZSSOffsetCodeLengthTable[4];
   unsigned char LZSSRepeatCodeLengthTable[3];
   unsigned char CodeCountCodeLengthTable[3];
   unsigned char CodeCountTable[2];
} YJ_1_BLOCKHEADER, *PYJ_1_BLOCKHEADER;

static unsigned int
get_bits(
   const void *src,
   unsigned int *bitptr,
   unsigned int count
)
{
   unsigned char *temp = ((unsigned char *)src) + ((*bitptr >> 4) << 1);
   unsigned int bptr = *bitptr & 0xf;
   unsigned short mask;
   *bitptr += count;
   if (count > 16 - bptr)
   {
      count = count + bptr - 16;
      mask = 0xffff >> bptr;
      return (((temp[0] | (temp[1] << 8)) & mask) << count) | ((temp[2] | (temp[3] << 8)) >> (16 - count));
   }
   else
      return (((unsigned short)((temp[0] | (temp[1] << 8)) << bptr)) >> (16 - count));
}

static unsigned short
get_loop(
   const void *src,
   unsigned int *bitptr,
   PYJ_1_BLOCKHEADER header
)
{
   if (get_bits(src, bitptr, 1))
      return header->CodeCountTable[0];
   else
   {
      unsigned int temp = get_bits(src, bitptr, 2);
      if (temp)
         return get_bits(src, bitptr, header->CodeCountCodeLengthTable[temp - 1]);
      else
         return header->CodeCountTable[1];
   }
}

static unsigned short
get_count(
   const void *src,
   unsigned int *bitptr,
   PYJ_1_BLOCKHEADER header
)
{
   unsigned short temp;
   if ((temp = get_bits(src, bitptr, 2)) != 0)
   {
      if (get_bits(src, bitptr, 1))
         return get_bits(src, bitptr, header->LZSSRepeatCodeLengthTable[temp - 1]);
      else
         return SWAP16(header->LZSSRepeatTable[temp]);
   }
   else
      return SWAP16(header->LZSSRepeatTable[0]);
}

INT
Decompress(
   LPCVOID       Source,
   LPVOID        Destination,
   INT           DestSize
)
{
   PYJ_1_FILEHEADER hdr = (PYJ_1_FILEHEADER)Source;
   unsigned char *src = (unsigned char *)Source;
   unsigned char *dest;
   unsigned int i;
   TreeNode *root, *node;

   if (Source == NULL)
      return -1;
   if (SWAP32(hdr->Signature) != 0x315f4a59)
      return -1;
   if (SWAP32(hdr->UncompressedLength) > (unsigned int)DestSize)
      return -1;

   do
   {
      unsigned short tree_len = ((unsigned short)hdr->HuffmanTreeLength) * 2;
      unsigned int bitptr = 0;
      unsigned char *flag = (unsigned char *)src + 16 + tree_len;

      if ((node = root = (TreeNode *)malloc(sizeof(TreeNode) * (tree_len + 1))) == NULL)
         return -1;
      root[0].leaf = 0;
      root[0].value = 0;
      root[0].left = root + 1;
      root[0].right = root + 2;
      for (i = 1; i <= tree_len; i++)
      {
         root[i].leaf = !get_bits(flag, &bitptr, 1);
         root[i].value = src[15 + i];
         if (root[i].leaf)
            root[i].left = root[i].right = NULL;
         else
         {
            root[i].left =  root + (root[i].value << 1) + 1;
            root[i].right = root[i].left + 1;
         }
      }
      src += 16 + tree_len + (((tree_len & 0xf) ? (tree_len >> 4) + 1 : (tree_len >> 4)) << 1);
   } while (0);

   dest = (unsigned char *)Destination;

   for (i = 0; i < SWAP16(hdr->BlockCount); i++)
   {
      unsigned int bitptr;
      PYJ_1_BLOCKHEADER header;

      header = (PYJ_1_BLOCKHEADER)src;
      src += 4;
      if (!SWAP16(header->CompressedLength))
      {
         unsigned short hul = SWAP16(header->UncompressedLength);
         while (hul--)
         {
            *dest++ = *src++;
         }
         continue;
      }
      src += 20;
      bitptr = 0;
      for (;;)
      {
         unsigned short loop;
         if ((loop = get_loop(src, &bitptr, header)) == 0)
            break;

         while (loop--)
         {
            node = root;
            for(; !node->leaf;)
            {
               if (get_bits(src, &bitptr, 1))
                  node = node->right;
               else
                  node = node->left;
            }
            *dest++ = node->value;
         }

         if ((loop = get_loop(src, &bitptr, header)) == 0)
            break;

         while (loop--)
         {
            unsigned int pos, count;
            count = get_count(src, &bitptr, header);
            pos = get_bits(src, &bitptr, 2);
            pos = get_bits(src, &bitptr, header->LZSSOffsetCodeLengthTable[pos]);
            while (count--)
            {
               *dest = *(dest - pos);
               dest++;
            }
         }
      }
      src = ((unsigned char *)header) + SWAP16(header->CompressedLength);
   }
   free(root);

   return SWAP32(hdr->UncompressedLength);
}

#else

typedef struct _TreeNode
{
   unsigned short      weight;
   unsigned short      value;
   struct _TreeNode*   parent;
   struct _TreeNode*   left;
   struct _TreeNode*   right;
} TreeNode;

typedef struct _Tree
{
   TreeNode*   node;
   TreeNode**   list;
} Tree;

static unsigned char data1[0x100] =
{
0x3f,0x0b,0x17,0x03,0x2f,0x0a,0x16,0x00,0x2e,0x09,0x15,0x02,0x2d,0x01,0x08,0x00,
0x3e,0x07,0x14,0x03,0x2c,0x06,0x13,0x00,0x2b,0x05,0x12,0x02,0x2a,0x01,0x04,0x00,
0x3d,0x0b,0x11,0x03,0x29,0x0a,0x10,0x00,0x28,0x09,0x0f,0x02,0x27,0x01,0x08,0x00,
0x3c,0x07,0x0e,0x03,0x26,0x06,0x0d,0x00,0x25,0x05,0x0c,0x02,0x24,0x01,0x04,0x00,
0x3b,0x0b,0x17,0x03,0x23,0x0a,0x16,0x00,0x22,0x09,0x15,0x02,0x21,0x01,0x08,0x00,
0x3a,0x07,0x14,0x03,0x20,0x06,0x13,0x00,0x1f,0x05,0x12,0x02,0x1e,0x01,0x04,0x00,
0x39,0x0b,0x11,0x03,0x1d,0x0a,0x10,0x00,0x1c,0x09,0x0f,0x02,0x1b,0x01,0x08,0x00,
0x38,0x07,0x0e,0x03,0x1a,0x06,0x0d,0x00,0x19,0x05,0x0c,0x02,0x18,0x01,0x04,0x00,
0x37,0x0b,0x17,0x03,0x2f,0x0a,0x16,0x00,0x2e,0x09,0x15,0x02,0x2d,0x01,0x08,0x00,
0x36,0x07,0x14,0x03,0x2c,0x06,0x13,0x00,0x2b,0x05,0x12,0x02,0x2a,0x01,0x04,0x00,
0x35,0x0b,0x11,0x03,0x29,0x0a,0x10,0x00,0x28,0x09,0x0f,0x02,0x27,0x01,0x08,0x00,
0x34,0x07,0x0e,0x03,0x26,0x06,0x0d,0x00,0x25,0x05,0x0c,0x02,0x24,0x01,0x04,0x00,
0x33,0x0b,0x17,0x03,0x23,0x0a,0x16,0x00,0x22,0x09,0x15,0x02,0x21,0x01,0x08,0x00,
0x32,0x07,0x14,0x03,0x20,0x06,0x13,0x00,0x1f,0x05,0x12,0x02,0x1e,0x01,0x04,0x00,
0x31,0x0b,0x11,0x03,0x1d,0x0a,0x10,0x00,0x1c,0x09,0x0f,0x02,0x1b,0x01,0x08,0x00,
0x30,0x07,0x0e,0x03,0x1a,0x06,0x0d,0x00,0x19,0x05,0x0c,0x02,0x18,0x01,0x04,0x00
};
static unsigned char data2[0x10] =
{
0x08,0x05,0x06,0x04,0x07,0x05,0x06,0x03,0x07,0x05,0x06,0x04,0x07,0x04,0x05,0x03
};

static void adjust_tree(Tree tree, unsigned short value)
{
   TreeNode* node = tree.list[value];
   TreeNode tmp;
   TreeNode* tmp1;
   TreeNode* temp;
   while(node->value != 0x280)
   {
      temp = node + 1;
      while(node->weight == temp->weight)
         temp++;
      temp--;
      if (temp != node)
      {
         tmp1 = node->parent;
         node->parent = temp->parent;
         temp->parent = tmp1;
         if (node->value > 0x140)
         {
            node->left->parent = temp;
            node->right->parent = temp;
         }
         else
            tree.list[node->value] = temp;
         if (temp->value > 0x140)
         {
            temp->left->parent = node;
            temp->right->parent = node;
         }
         else
            tree.list[temp->value] = node;
         tmp = *node; *node = *temp; *temp = tmp;
         node = temp;
      }
      node->weight++;
      node = node->parent;
   }
   node->weight++;
}

static int build_tree(Tree *tree)
{
   int i, ptr;
   TreeNode** list;
   TreeNode* node;
   if ((tree->list = list = (TreeNode **)malloc(sizeof(TreeNode*) * 321)) == NULL)
      return 0;
   if ((tree->node = node = (TreeNode *)malloc(sizeof(TreeNode) * 641)) == NULL)
   {
      free(list);
      return 0;
   }
   memset(list, 0, 321 * sizeof(TreeNode*));
   memset(node, 0, 641 * sizeof(TreeNode));
   for(i = 0; i <= 0x140; i++)
      list[i] = node + i;
   for(i = 0; i <= 0x280; i++)
   {
      node[i].value = i;
      node[i].weight = 1;
   }
   tree->node[0x280].parent = tree->node + 0x280;
   for(i = 0, ptr = 0x141; ptr <= 0x280; i += 2, ptr++)
   {
      node[ptr].left = node + i;
      node[ptr].right = node + i + 1;
      node[i].parent = node[i + 1].parent = node + ptr;
      node[ptr].weight = node[i].weight + node[i + 1].weight;
   }
   return 1;
}

#pragma pack(1)
typedef struct _BitField
{
   unsigned char   b0:   1;
   unsigned char   b1:   1;
   unsigned char   b2:   1;
   unsigned char   b3:   1;
   unsigned char   b4:   1;
   unsigned char   b5:   1;
   unsigned char   b6:   1;
   unsigned char   b7:   1;
} BitField;
#pragma pack()

static int bt(const void* data, unsigned int pos)
{
   BitField* bit = (BitField*)((unsigned char*)data + (pos >> 3));
   switch(pos & 0x7)
   {
   case 0:   return bit->b0;
   case 1:   return bit->b1;
   case 2:   return bit->b2;
   case 3:   return bit->b3;
   case 4:   return bit->b4;
   case 5:   return bit->b5;
   case 6:   return bit->b6;
   case 7:   return bit->b7;
   }
   return 0;
}

static void bit(void* data, unsigned int pos, int set)
{
   BitField* bit = (BitField*)((unsigned char*)data + (pos >> 3));
   switch(pos & 0x7)
   {
   case 0:
      bit->b0 = set;
      break;
   case 1:
      bit->b1 = set;
      break;
   case 2:
      bit->b2 = set;
      break;
   case 3:
      bit->b3 = set;
      break;
   case 4:
      bit->b4 = set;
      break;
   case 5:
      bit->b5 = set;
      break;
   case 6:
      bit->b6 = set;
      break;
   case 7:
      bit->b7 = set;
      break;
   }
}

INT
Decompress(
   LPCVOID       Source,
   LPVOID        Destination,
   INT           DestSize
)
{
   unsigned int len = 0, ptr = 0, Length = 0;
   unsigned char* src = (unsigned char*)Source + 4;
   unsigned char* dest;
   Tree tree;
   TreeNode* node;

   if (Source == NULL)
      return -1;

   if (!build_tree(&tree))
      return -1;

   Length = SWAP32(*((unsigned int*)Source));
   if (Length > DestSize)
      return -1;
   dest = (unsigned char*)Destination;

   while (1)
   {
      unsigned short val;
      node = tree.node + 0x280;
      while(node->value > 0x140)
      {
         if (bt(src, ptr))
            node = node->right;
         else
            node = node->left;
         ptr++;
      }
      val = node->value;
      if (tree.node[0x280].weight == 0x8000)
      {
         int i;
         for(i = 0; i < 0x141; i++)
            if (tree.list[i]->weight & 0x1)
               adjust_tree(tree, i);
         for(i = 0; i <= 0x280; i++)
            tree.node[i].weight >>= 1;
      }
      adjust_tree(tree, val);
      if (val > 0xff)
      {
         int i;
         unsigned int temp, tmp, pos;
         unsigned char* pre;
         for(i = 0, temp = 0; i < 8; i++, ptr++)
            temp |= (unsigned int)bt(src, ptr) << i;
         tmp = temp & 0xff;
         for(; i < data2[tmp & 0xf] + 6; i++, ptr++)
            temp |= (unsigned int)bt(src, ptr) << i;
         temp >>= data2[tmp & 0xf];
         pos = (temp & 0x3f) | ((unsigned int)data1[tmp] << 6);
         if (pos == 0xfff)
            break;
         pre = dest - pos - 1;
         for(i = 0; i < val - 0xfd; i++)
            *dest++ = *pre++;
         len += val - 0xfd;
      }
      else
      {
         *dest++ = (unsigned char)val;
         len++;
      }
   }

   free(tree.list);
   free(tree.node);
   return Length;
}

#endif