//
// 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 "_common.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
