//
// 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