yj1.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437
  1. //
  2. // PAL DOS compress format (YJ_1) library
  3. //
  4. // Author: Lou Yihua <louyihua@21cn.com>
  5. //
  6. // Copyright 2006 - 2007 Lou Yihua
  7. //
  8. // This file is part of PAL library.
  9. //
  10. // This library is free software; you can redistribute it and/or
  11. // modify it under the terms of the GNU Lesser General Public
  12. // License as published by the Free Software Foundation; either
  13. // version 2.1 of the License, or (at your option) any later version.
  14. //
  15. // This library is distributed in the hope that it will be useful,
  16. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  17. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18. // Lesser General Public License for more details.
  19. //
  20. // You should have received a copy of the GNU Lesser General Public
  21. // License along with this library; if not, write to the Free Software
  22. // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  23. //
  24. // Ported to C from C++ and modified for compatibility with Big-Endian
  25. // by Wei Mingzhi <whistler@openoffice.org>.
  26. // TODO: fix YJ_2 for big-endian
  27. #include "common.h"
  28. typedef struct _YJ1_TreeNode
  29. {
  30. unsigned char value;
  31. unsigned char leaf;
  32. unsigned short level;
  33. unsigned int weight;
  34. struct _YJ1_TreeNode *parent;
  35. struct _YJ1_TreeNode *left;
  36. struct _YJ1_TreeNode *right;
  37. } YJ1_TreeNode;
  38. typedef struct _YJ1_TreeNodeList
  39. {
  40. YJ1_TreeNode *node;
  41. struct _YJ1_TreeNodeList *next;
  42. } YJ1_TreeNodeList;
  43. typedef struct _YJ_1_FILEHEADER
  44. {
  45. unsigned int Signature; // 'YJ_1'
  46. unsigned int UncompressedLength; // size before compression
  47. unsigned int CompressedLength; // size after compression
  48. unsigned short BlockCount; // number of blocks
  49. unsigned char Unknown;
  50. unsigned char HuffmanTreeLength; // length of huffman tree
  51. } YJ_1_FILEHEADER, *PYJ_1_FILEHEADER;
  52. typedef struct _YJ_1_BLOCKHEADER
  53. {
  54. unsigned short UncompressedLength; // maximum 0x4000
  55. unsigned short CompressedLength; // including the header
  56. unsigned short LZSSRepeatTable[4];
  57. unsigned char LZSSOffsetCodeLengthTable[4];
  58. unsigned char LZSSRepeatCodeLengthTable[3];
  59. unsigned char CodeCountCodeLengthTable[3];
  60. unsigned char CodeCountTable[2];
  61. } YJ_1_BLOCKHEADER, *PYJ_1_BLOCKHEADER;
  62. static unsigned int
  63. yj1_get_bits(
  64. const void *src,
  65. unsigned int *bitptr,
  66. unsigned int count
  67. )
  68. {
  69. unsigned char *temp = ((unsigned char *)src) + ((*bitptr >> 4) << 1);
  70. unsigned int bptr = *bitptr & 0xf;
  71. unsigned short mask;
  72. *bitptr += count;
  73. if (count > 16 - bptr)
  74. {
  75. count = count + bptr - 16;
  76. mask = 0xffff >> bptr;
  77. return (((temp[0] | (temp[1] << 8)) & mask) << count) | ((temp[2] | (temp[3] << 8)) >> (16 - count));
  78. }
  79. else
  80. return (((unsigned short)((temp[0] | (temp[1] << 8)) << bptr)) >> (16 - count));
  81. }
  82. static unsigned short
  83. yj1_get_loop(
  84. const void *src,
  85. unsigned int *bitptr,
  86. PYJ_1_BLOCKHEADER header
  87. )
  88. {
  89. if (yj1_get_bits(src, bitptr, 1))
  90. return header->CodeCountTable[0];
  91. else
  92. {
  93. unsigned int temp = yj1_get_bits(src, bitptr, 2);
  94. if (temp)
  95. return yj1_get_bits(src, bitptr, header->CodeCountCodeLengthTable[temp - 1]);
  96. else
  97. return header->CodeCountTable[1];
  98. }
  99. }
  100. static unsigned short
  101. yj1_get_count(
  102. const void *src,
  103. unsigned int *bitptr,
  104. PYJ_1_BLOCKHEADER header
  105. )
  106. {
  107. unsigned short temp;
  108. if ((temp = yj1_get_bits(src, bitptr, 2)) != 0)
  109. {
  110. if (yj1_get_bits(src, bitptr, 1))
  111. return yj1_get_bits(src, bitptr, header->LZSSRepeatCodeLengthTable[temp - 1]);
  112. else
  113. return SDL_SwapLE16(header->LZSSRepeatTable[temp]);
  114. }
  115. else
  116. return SDL_SwapLE16(header->LZSSRepeatTable[0]);
  117. }
  118. INT
  119. YJ1_Decompress(
  120. LPCVOID Source,
  121. LPVOID Destination,
  122. INT DestSize
  123. )
  124. {
  125. PYJ_1_FILEHEADER hdr = (PYJ_1_FILEHEADER)Source;
  126. unsigned char *src = (unsigned char *)Source;
  127. unsigned char *dest;
  128. unsigned int i;
  129. YJ1_TreeNode *root, *node;
  130. if (Source == NULL)
  131. return -1;
  132. if (SDL_SwapLE32(hdr->Signature) != 0x315f4a59)
  133. return -1;
  134. if (SDL_SwapLE32(hdr->UncompressedLength) > (unsigned int)DestSize)
  135. return -1;
  136. do
  137. {
  138. unsigned short tree_len = ((unsigned short)hdr->HuffmanTreeLength) * 2;
  139. unsigned int bitptr = 0;
  140. unsigned char *flag = (unsigned char *)src + 16 + tree_len;
  141. if ((node = root = (YJ1_TreeNode *)malloc(sizeof(YJ1_TreeNode) * (tree_len + 1))) == NULL)
  142. return -1;
  143. root[0].leaf = 0;
  144. root[0].value = 0;
  145. root[0].left = root + 1;
  146. root[0].right = root + 2;
  147. for (i = 1; i <= tree_len; i++)
  148. {
  149. root[i].leaf = !yj1_get_bits(flag, &bitptr, 1);
  150. root[i].value = src[15 + i];
  151. if (root[i].leaf)
  152. root[i].left = root[i].right = NULL;
  153. else
  154. {
  155. root[i].left = root + (root[i].value << 1) + 1;
  156. root[i].right = root[i].left + 1;
  157. }
  158. }
  159. src += 16 + tree_len + (((tree_len & 0xf) ? (tree_len >> 4) + 1 : (tree_len >> 4)) << 1);
  160. } while (0);
  161. dest = (unsigned char *)Destination;
  162. for (i = 0; i < SDL_SwapLE16(hdr->BlockCount); i++)
  163. {
  164. unsigned int bitptr;
  165. PYJ_1_BLOCKHEADER header;
  166. header = (PYJ_1_BLOCKHEADER)src;
  167. src += 4;
  168. if (!SDL_SwapLE16(header->CompressedLength))
  169. {
  170. unsigned short hul = SDL_SwapLE16(header->UncompressedLength);
  171. while (hul--)
  172. {
  173. *dest++ = *src++;
  174. }
  175. continue;
  176. }
  177. src += 20;
  178. bitptr = 0;
  179. for (;;)
  180. {
  181. unsigned short loop;
  182. if ((loop = yj1_get_loop(src, &bitptr, header)) == 0)
  183. break;
  184. while (loop--)
  185. {
  186. node = root;
  187. for (; !node->leaf;)
  188. {
  189. if (yj1_get_bits(src, &bitptr, 1))
  190. node = node->right;
  191. else
  192. node = node->left;
  193. }
  194. *dest++ = node->value;
  195. }
  196. if ((loop = yj1_get_loop(src, &bitptr, header)) == 0)
  197. break;
  198. while (loop--)
  199. {
  200. unsigned int pos, count;
  201. count = yj1_get_count(src, &bitptr, header);
  202. pos = yj1_get_bits(src, &bitptr, 2);
  203. pos = yj1_get_bits(src, &bitptr, header->LZSSOffsetCodeLengthTable[pos]);
  204. while (count--)
  205. {
  206. *dest = *(dest - pos);
  207. dest++;
  208. }
  209. }
  210. }
  211. src = ((unsigned char *)header) + SDL_SwapLE16(header->CompressedLength);
  212. }
  213. free(root);
  214. return SDL_SwapLE32(hdr->UncompressedLength);
  215. }
  216. /* ============================================================================================================================================= */
  217. typedef struct _YJ2_TreeNode
  218. {
  219. unsigned short weight;
  220. unsigned short value;
  221. struct _YJ2_TreeNode *parent;
  222. struct _YJ2_TreeNode *left;
  223. struct _YJ2_TreeNode *right;
  224. } YJ2_TreeNode;
  225. typedef struct _YJ2_Tree
  226. {
  227. YJ2_TreeNode *node;
  228. YJ2_TreeNode **list;
  229. } YJ2_Tree;
  230. static unsigned char yj2_data1[0x100] =
  231. {
  232. 0x3f, 0x0b, 0x17, 0x03, 0x2f, 0x0a, 0x16, 0x00, 0x2e, 0x09, 0x15, 0x02, 0x2d, 0x01, 0x08, 0x00,
  233. 0x3e, 0x07, 0x14, 0x03, 0x2c, 0x06, 0x13, 0x00, 0x2b, 0x05, 0x12, 0x02, 0x2a, 0x01, 0x04, 0x00,
  234. 0x3d, 0x0b, 0x11, 0x03, 0x29, 0x0a, 0x10, 0x00, 0x28, 0x09, 0x0f, 0x02, 0x27, 0x01, 0x08, 0x00,
  235. 0x3c, 0x07, 0x0e, 0x03, 0x26, 0x06, 0x0d, 0x00, 0x25, 0x05, 0x0c, 0x02, 0x24, 0x01, 0x04, 0x00,
  236. 0x3b, 0x0b, 0x17, 0x03, 0x23, 0x0a, 0x16, 0x00, 0x22, 0x09, 0x15, 0x02, 0x21, 0x01, 0x08, 0x00,
  237. 0x3a, 0x07, 0x14, 0x03, 0x20, 0x06, 0x13, 0x00, 0x1f, 0x05, 0x12, 0x02, 0x1e, 0x01, 0x04, 0x00,
  238. 0x39, 0x0b, 0x11, 0x03, 0x1d, 0x0a, 0x10, 0x00, 0x1c, 0x09, 0x0f, 0x02, 0x1b, 0x01, 0x08, 0x00,
  239. 0x38, 0x07, 0x0e, 0x03, 0x1a, 0x06, 0x0d, 0x00, 0x19, 0x05, 0x0c, 0x02, 0x18, 0x01, 0x04, 0x00,
  240. 0x37, 0x0b, 0x17, 0x03, 0x2f, 0x0a, 0x16, 0x00, 0x2e, 0x09, 0x15, 0x02, 0x2d, 0x01, 0x08, 0x00,
  241. 0x36, 0x07, 0x14, 0x03, 0x2c, 0x06, 0x13, 0x00, 0x2b, 0x05, 0x12, 0x02, 0x2a, 0x01, 0x04, 0x00,
  242. 0x35, 0x0b, 0x11, 0x03, 0x29, 0x0a, 0x10, 0x00, 0x28, 0x09, 0x0f, 0x02, 0x27, 0x01, 0x08, 0x00,
  243. 0x34, 0x07, 0x0e, 0x03, 0x26, 0x06, 0x0d, 0x00, 0x25, 0x05, 0x0c, 0x02, 0x24, 0x01, 0x04, 0x00,
  244. 0x33, 0x0b, 0x17, 0x03, 0x23, 0x0a, 0x16, 0x00, 0x22, 0x09, 0x15, 0x02, 0x21, 0x01, 0x08, 0x00,
  245. 0x32, 0x07, 0x14, 0x03, 0x20, 0x06, 0x13, 0x00, 0x1f, 0x05, 0x12, 0x02, 0x1e, 0x01, 0x04, 0x00,
  246. 0x31, 0x0b, 0x11, 0x03, 0x1d, 0x0a, 0x10, 0x00, 0x1c, 0x09, 0x0f, 0x02, 0x1b, 0x01, 0x08, 0x00,
  247. 0x30, 0x07, 0x0e, 0x03, 0x1a, 0x06, 0x0d, 0x00, 0x19, 0x05, 0x0c, 0x02, 0x18, 0x01, 0x04, 0x00
  248. };
  249. static unsigned char yj2_data2[0x10] =
  250. {
  251. 0x08, 0x05, 0x06, 0x04, 0x07, 0x05, 0x06, 0x03, 0x07, 0x05, 0x06, 0x04, 0x07, 0x04, 0x05, 0x03
  252. };
  253. static void yj2_adjust_tree(YJ2_Tree tree, unsigned short value)
  254. {
  255. YJ2_TreeNode* node = tree.list[value];
  256. YJ2_TreeNode tmp;
  257. YJ2_TreeNode* tmp1;
  258. YJ2_TreeNode* temp;
  259. while (node->value != 0x280)
  260. {
  261. temp = node + 1;
  262. while (node->weight == temp->weight)
  263. temp++;
  264. temp--;
  265. if (temp != node)
  266. {
  267. tmp1 = node->parent;
  268. node->parent = temp->parent;
  269. temp->parent = tmp1;
  270. if (node->value > 0x140)
  271. {
  272. node->left->parent = temp;
  273. node->right->parent = temp;
  274. }
  275. else
  276. tree.list[node->value] = temp;
  277. if (temp->value > 0x140)
  278. {
  279. temp->left->parent = node;
  280. temp->right->parent = node;
  281. }
  282. else
  283. tree.list[temp->value] = node;
  284. tmp = *node; *node = *temp; *temp = tmp;
  285. node = temp;
  286. }
  287. node->weight++;
  288. node = node->parent;
  289. }
  290. node->weight++;
  291. }
  292. static int yj2_build_tree(YJ2_Tree *tree)
  293. {
  294. int i, ptr;
  295. YJ2_TreeNode** list;
  296. YJ2_TreeNode* node;
  297. if ((tree->list = list = (YJ2_TreeNode **)malloc(sizeof(YJ2_TreeNode*) * 321)) == NULL)
  298. return 0;
  299. if ((tree->node = node = (YJ2_TreeNode *)malloc(sizeof(YJ2_TreeNode) * 641)) == NULL)
  300. {
  301. free(list);
  302. return 0;
  303. }
  304. memset(list, 0, 321 * sizeof(YJ2_TreeNode*));
  305. memset(node, 0, 641 * sizeof(YJ2_TreeNode));
  306. for (i = 0; i <= 0x140; i++)
  307. list[i] = node + i;
  308. for (i = 0; i <= 0x280; i++)
  309. {
  310. node[i].value = i;
  311. node[i].weight = 1;
  312. }
  313. tree->node[0x280].parent = tree->node + 0x280;
  314. for (i = 0, ptr = 0x141; ptr <= 0x280; i += 2, ptr++)
  315. {
  316. node[ptr].left = node + i;
  317. node[ptr].right = node + i + 1;
  318. node[i].parent = node[i + 1].parent = node + ptr;
  319. node[ptr].weight = node[i].weight + node[i + 1].weight;
  320. }
  321. return 1;
  322. }
  323. static int yj2_bt(const unsigned char* data, unsigned int pos)
  324. {
  325. return (data[pos >> 3] & (unsigned char)(1 << (pos & 0x7))) >> (pos & 0x7);
  326. }
  327. INT
  328. YJ2_Decompress(
  329. LPCVOID Source,
  330. LPVOID Destination,
  331. INT DestSize
  332. )
  333. {
  334. int Length;
  335. unsigned int len = 0, ptr = 0;
  336. unsigned char* src = (unsigned char*)Source + 4;
  337. unsigned char* dest;
  338. YJ2_Tree tree;
  339. YJ2_TreeNode* node;
  340. if (Source == NULL)
  341. return -1;
  342. if (!yj2_build_tree(&tree))
  343. return -1;
  344. Length = SDL_SwapLE32(*((unsigned int*)Source));
  345. if (Length > DestSize)
  346. return -1;
  347. dest = (unsigned char*)Destination;
  348. while (1)
  349. {
  350. unsigned short val;
  351. node = tree.node + 0x280;
  352. while (node->value > 0x140)
  353. {
  354. if (yj2_bt(src, ptr))
  355. node = node->right;
  356. else
  357. node = node->left;
  358. ptr++;
  359. }
  360. val = node->value;
  361. if (tree.node[0x280].weight == 0x8000)
  362. {
  363. int i;
  364. for (i = 0; i < 0x141; i++)
  365. if (tree.list[i]->weight & 0x1)
  366. yj2_adjust_tree(tree, i);
  367. for (i = 0; i <= 0x280; i++)
  368. tree.node[i].weight >>= 1;
  369. }
  370. yj2_adjust_tree(tree, val);
  371. if (val > 0xff)
  372. {
  373. int i;
  374. unsigned int temp, tmp, pos;
  375. unsigned char* pre;
  376. for (i = 0, temp = 0; i < 8; i++, ptr++)
  377. temp |= (unsigned int)yj2_bt(src, ptr) << i;
  378. tmp = temp & 0xff;
  379. for (; i < yj2_data2[tmp & 0xf] + 6; i++, ptr++)
  380. temp |= (unsigned int)yj2_bt(src, ptr) << i;
  381. temp >>= yj2_data2[tmp & 0xf];
  382. pos = (temp & 0x3f) | ((unsigned int)yj2_data1[tmp] << 6);
  383. if (pos == 0xfff)
  384. break;
  385. pre = dest - pos - 1;
  386. for (i = 0; i < val - 0xfd; i++)
  387. *dest++ = *pre++;
  388. len += val - 0xfd;
  389. }
  390. else
  391. {
  392. *dest++ = (unsigned char)val;
  393. len++;
  394. }
  395. }
  396. free(tree.list);
  397. free(tree.node);
  398. return Length;
  399. }
  400. INT (*Decompress)(LPCVOID, LPVOID, INT);