yj1.c 11 KB

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