yj1.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496
  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. #ifndef PAL_WIN95
  29. typedef struct _TreeNode
  30. {
  31. unsigned char value;
  32. unsigned char leaf;
  33. unsigned short level;
  34. unsigned int weight;
  35. struct _TreeNode *parent;
  36. struct _TreeNode *left;
  37. struct _TreeNode *right;
  38. } TreeNode;
  39. typedef struct _TreeNodeList
  40. {
  41. TreeNode *node;
  42. struct _TreeNodeList *next;
  43. } 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. 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. get_loop(
  85. const void *src,
  86. unsigned int *bitptr,
  87. PYJ_1_BLOCKHEADER header
  88. )
  89. {
  90. if (get_bits(src, bitptr, 1))
  91. return header->CodeCountTable[0];
  92. else
  93. {
  94. unsigned int temp = get_bits(src, bitptr, 2);
  95. if (temp)
  96. return get_bits(src, bitptr, header->CodeCountCodeLengthTable[temp - 1]);
  97. else
  98. return header->CodeCountTable[1];
  99. }
  100. }
  101. static unsigned short
  102. get_count(
  103. const void *src,
  104. unsigned int *bitptr,
  105. PYJ_1_BLOCKHEADER header
  106. )
  107. {
  108. unsigned short temp;
  109. if ((temp = get_bits(src, bitptr, 2)) != 0)
  110. {
  111. if (get_bits(src, bitptr, 1))
  112. return get_bits(src, bitptr, header->LZSSRepeatCodeLengthTable[temp - 1]);
  113. else
  114. return SWAP16(header->LZSSRepeatTable[temp]);
  115. }
  116. else
  117. return SWAP16(header->LZSSRepeatTable[0]);
  118. }
  119. INT
  120. 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. TreeNode *root, *node;
  131. if (Source == NULL)
  132. return -1;
  133. if (SWAP32(hdr->Signature) != 0x315f4a59)
  134. return -1;
  135. if (SWAP32(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 = (TreeNode *)malloc(sizeof(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 = !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 < SWAP16(hdr->BlockCount); i++)
  164. {
  165. unsigned int bitptr;
  166. PYJ_1_BLOCKHEADER header;
  167. header = (PYJ_1_BLOCKHEADER)src;
  168. src += 4;
  169. if (!SWAP16(header->CompressedLength))
  170. {
  171. unsigned short hul = SWAP16(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 = get_loop(src, &bitptr, header)) == 0)
  184. break;
  185. while (loop--)
  186. {
  187. node = root;
  188. for(; !node->leaf;)
  189. {
  190. if (get_bits(src, &bitptr, 1))
  191. node = node->right;
  192. else
  193. node = node->left;
  194. }
  195. *dest++ = node->value;
  196. }
  197. if ((loop = get_loop(src, &bitptr, header)) == 0)
  198. break;
  199. while (loop--)
  200. {
  201. unsigned int pos, count;
  202. count = get_count(src, &bitptr, header);
  203. pos = get_bits(src, &bitptr, 2);
  204. pos = 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) + SWAP16(header->CompressedLength);
  213. }
  214. free(root);
  215. return SWAP32(hdr->UncompressedLength);
  216. }
  217. #else
  218. typedef struct _TreeNode
  219. {
  220. unsigned short weight;
  221. unsigned short value;
  222. struct _TreeNode* parent;
  223. struct _TreeNode* left;
  224. struct _TreeNode* right;
  225. } TreeNode;
  226. typedef struct _Tree
  227. {
  228. TreeNode* node;
  229. TreeNode** list;
  230. } Tree;
  231. static unsigned char 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 data2[0x10] =
  251. {
  252. 0x08,0x05,0x06,0x04,0x07,0x05,0x06,0x03,0x07,0x05,0x06,0x04,0x07,0x04,0x05,0x03
  253. };
  254. static void adjust_tree(Tree tree, unsigned short value)
  255. {
  256. TreeNode* node = tree.list[value];
  257. TreeNode tmp;
  258. TreeNode* tmp1;
  259. 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 build_tree(Tree *tree)
  294. {
  295. int i, ptr;
  296. TreeNode** list;
  297. TreeNode* node;
  298. if ((tree->list = list = (TreeNode **)malloc(sizeof(TreeNode*) * 321)) == NULL)
  299. return 0;
  300. if ((tree->node = node = (TreeNode *)malloc(sizeof(TreeNode) * 641)) == NULL)
  301. {
  302. free(list);
  303. return 0;
  304. }
  305. memset(list, 0, 321 * sizeof(TreeNode*));
  306. memset(node, 0, 641 * sizeof(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. #pragma pack(1)
  325. typedef struct _BitField
  326. {
  327. unsigned char b0: 1;
  328. unsigned char b1: 1;
  329. unsigned char b2: 1;
  330. unsigned char b3: 1;
  331. unsigned char b4: 1;
  332. unsigned char b5: 1;
  333. unsigned char b6: 1;
  334. unsigned char b7: 1;
  335. } BitField;
  336. #pragma pack()
  337. static int bt(const void* data, unsigned int pos)
  338. {
  339. BitField* bit = (BitField*)((unsigned char*)data + (pos >> 3));
  340. switch(pos & 0x7)
  341. {
  342. case 0: return bit->b0;
  343. case 1: return bit->b1;
  344. case 2: return bit->b2;
  345. case 3: return bit->b3;
  346. case 4: return bit->b4;
  347. case 5: return bit->b5;
  348. case 6: return bit->b6;
  349. case 7: return bit->b7;
  350. }
  351. return 0;
  352. }
  353. static void bit(void* data, unsigned int pos, int set)
  354. {
  355. BitField* bit = (BitField*)((unsigned char*)data + (pos >> 3));
  356. switch(pos & 0x7)
  357. {
  358. case 0:
  359. bit->b0 = set;
  360. break;
  361. case 1:
  362. bit->b1 = set;
  363. break;
  364. case 2:
  365. bit->b2 = set;
  366. break;
  367. case 3:
  368. bit->b3 = set;
  369. break;
  370. case 4:
  371. bit->b4 = set;
  372. break;
  373. case 5:
  374. bit->b5 = set;
  375. break;
  376. case 6:
  377. bit->b6 = set;
  378. break;
  379. case 7:
  380. bit->b7 = set;
  381. break;
  382. }
  383. }
  384. INT
  385. Decompress(
  386. LPCVOID Source,
  387. LPVOID Destination,
  388. INT DestSize
  389. )
  390. {
  391. int Length;
  392. unsigned int len = 0, ptr = 0;
  393. unsigned char* src = (unsigned char*)Source + 4;
  394. unsigned char* dest;
  395. Tree tree;
  396. TreeNode* node;
  397. if (Source == NULL)
  398. return -1;
  399. if (!build_tree(&tree))
  400. return -1;
  401. Length = SWAP32(*((unsigned int*)Source));
  402. if (Length > DestSize)
  403. return -1;
  404. dest = (unsigned char*)Destination;
  405. while (1)
  406. {
  407. unsigned short val;
  408. node = tree.node + 0x280;
  409. while(node->value > 0x140)
  410. {
  411. if (bt(src, ptr))
  412. node = node->right;
  413. else
  414. node = node->left;
  415. ptr++;
  416. }
  417. val = node->value;
  418. if (tree.node[0x280].weight == 0x8000)
  419. {
  420. int i;
  421. for(i = 0; i < 0x141; i++)
  422. if (tree.list[i]->weight & 0x1)
  423. adjust_tree(tree, i);
  424. for(i = 0; i <= 0x280; i++)
  425. tree.node[i].weight >>= 1;
  426. }
  427. adjust_tree(tree, val);
  428. if (val > 0xff)
  429. {
  430. int i;
  431. unsigned int temp, tmp, pos;
  432. unsigned char* pre;
  433. for(i = 0, temp = 0; i < 8; i++, ptr++)
  434. temp |= (unsigned int)bt(src, ptr) << i;
  435. tmp = temp & 0xff;
  436. for(; i < data2[tmp & 0xf] + 6; i++, ptr++)
  437. temp |= (unsigned int)bt(src, ptr) << i;
  438. temp >>= data2[tmp & 0xf];
  439. pos = (temp & 0x3f) | ((unsigned int)data1[tmp] << 6);
  440. if (pos == 0xfff)
  441. break;
  442. pre = dest - pos - 1;
  443. for(i = 0; i < val - 0xfd; i++)
  444. *dest++ = *pre++;
  445. len += val - 0xfd;
  446. }
  447. else
  448. {
  449. *dest++ = (unsigned char)val;
  450. len++;
  451. }
  452. }
  453. free(tree.list);
  454. free(tree.node);
  455. return Length;
  456. }
  457. #endif