pucrunch.c 51 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627
  1. /* pucrunch.c: Pucrunch compression code
  2. Pucrunch 1997-2005 by Pasi 'Albert' Ojala, a1bert@iki.fi
  3. Copyright (C) 2000 Thomas Nussbaumer
  4. Copyright (C) 2007 Kevin Kofler
  5. This program is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2, or (at your option)
  8. any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software Foundation,
  15. Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  16. #include <stdio.h>
  17. #include <stdlib.h>
  18. #include <string.h>
  19. #include <math.h>
  20. #include <ctype.h>
  21. #include <time.h>
  22. #include "../generic.h"
  23. #include "../formats/packhead.h" // compressed header definition
  24. #include "../formats/tios.h"
  25. #include "export.h"
  26. #include "pucrunch.h"
  27. #define VERBOSE_OUT stdout
  28. #ifndef min
  29. #define min(a,b) ((a<b)?(a):(b))
  30. #endif
  31. #if defined(__GNUC__) && __GNUC__ >= 4
  32. #define OFFSETOF __builtin_offsetof
  33. #else
  34. #define OFFSETOF(type,member) ((size_t) &(((type*)0)->member))
  35. #endif
  36. #define LRANGE (((2<<maxGamma)-3)*256) /* 0..125, 126 -> 1..127 */
  37. #define MAXLZLEN (2<<maxGamma)
  38. #define MAXRLELEN (((2<<maxGamma)-2)*256) /* 0..126 -> 1..127 */
  39. #define DEFAULT_LZLEN LRANGE
  40. static unsigned short *rle, *elr, *lzlen, *lzpos;
  41. static int *length, inlen;
  42. static unsigned char *indata, *mode, *newesc;
  43. static unsigned short *backSkip;
  44. enum MODE {
  45. LITERAL = 0,
  46. LZ77 = 1,
  47. RLE = 2,
  48. MMARK = 4
  49. };
  50. static int lzopt = 0;
  51. static int maxGamma = 7;
  52. static int reservedBytes = 2;
  53. static int escBits = 2;
  54. static int escMask = 0xc0;
  55. static int extraLZPosBits = 0;
  56. static int rleUsed = 31;
  57. static unsigned char rleLen[256];
  58. static int lenValue[256];
  59. static int lrange, maxlzlen, maxrlelen;
  60. static int gainedEscaped = 0;
  61. static int gainedRle = 0, gainedSRle = 0, gainedLRle = 0;
  62. static int gainedLz = 0, gainedRlecode = 0;
  63. static int timesEscaped = 0, timesNormal = 0;
  64. static int timesRle = 0, timesSRle = 0, timesLRle = 0;
  65. static int timesLz = 0;
  66. static int lenStat[8][4];
  67. static unsigned char rleValues[32] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  68. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  69. static int rleHist[256];
  70. #define OUT_SIZE 65536
  71. static unsigned char outBuffer[OUT_SIZE];
  72. static int outPointer = 0;
  73. static int bitMask = 0x80;
  74. static void TTPackInit(void) {
  75. int i;
  76. rleValues[0] = 1;
  77. for (i=1;i<32;i++) rleValues[i] = 0;
  78. for (i=0;i<256;i++) {
  79. rleLen[i] = 0;
  80. lenValue[i] = 0;
  81. rleHist[i] = 0;
  82. }
  83. for (i=0;i<OUT_SIZE;i++) outBuffer[i] = 0;
  84. lrange = 0, maxlzlen = 0, maxrlelen = 0;
  85. gainedEscaped = 0;
  86. gainedRle = 0, gainedSRle = 0, gainedLRle = 0;
  87. gainedLz = 0, gainedRlecode = 0;
  88. timesEscaped = 0, timesNormal = 0;
  89. timesRle = 0, timesSRle = 0, timesLRle = 0;
  90. timesLz = 0;
  91. lrange = 0;
  92. maxlzlen = 0;
  93. maxrlelen = 0;
  94. outPointer = 0;
  95. bitMask = 0x80;
  96. lzopt = 0;
  97. maxGamma = 7;
  98. reservedBytes = 2;
  99. escBits = 2;
  100. escMask = 0xc0;
  101. extraLZPosBits = 0;
  102. rleUsed = 31;
  103. rle = NULL;
  104. elr = NULL;
  105. lzlen = NULL;
  106. lzpos = NULL;
  107. length = NULL;
  108. inlen = 0;
  109. indata = NULL;
  110. mode = NULL;
  111. newesc = NULL;
  112. backSkip = NULL;
  113. }
  114. //=============================================================================
  115. // the packing code
  116. //=============================================================================
  117. static int SavePack(unsigned char *data, int size, EXP_FILE *fp, int escape,
  118. unsigned char *rleValues, int extraLZPosBits)
  119. {
  120. int i;
  121. if (!data) return 10;
  122. /* Save without decompressor */
  123. PackedHeader cth;
  124. RLEEntries re;
  125. cth.origsize_lo = inlen & 0xff;
  126. cth.origsize_hi = (inlen >> 8);
  127. cth.magic1 = MAGIC_CHAR1;
  128. cth.magic2 = MAGIC_CHAR2;
  129. cth.compsize_lo = (size + rleUsed + sizeof(PackedHeader)) & 0xff;
  130. cth.compsize_hi = (size + rleUsed + sizeof(PackedHeader)) >> 8;
  131. cth.esc1 = (escape >> (8-escBits));
  132. cth.notused3 = 0; // just to make sure it has a defined value
  133. cth.notused4 = 0; // just to make sure it has a defined value
  134. cth.esc2 = escBits;
  135. cth.gamma1 = maxGamma + 1;
  136. cth.gamma2 = (1 << maxGamma);
  137. cth.extralz = extraLZPosBits;
  138. cth.notused1 = 0; // just to make sure it has a defined value
  139. cth.notused2 = 0; // just to make sure it has a defined value
  140. cth.rleentries = rleUsed;
  141. for(i=0; i<rleUsed; i++) re.value[i] = rleValues[i+1];
  142. {
  143. int packedSize = sizeof(PackedHeader) + cth.rleentries + size + 6;
  144. ExportWriteTI2(fp, packedSize); // write size bytes
  145. ExportWrite(fp, &cth, 1, sizeof(PackedHeader)); // write header
  146. ExportWrite(fp, &re, 1, cth.rleentries); // write rle values
  147. ExportWrite(fp, data, size, 1); // write compressed data
  148. /* Now fix the on-computer size */
  149. if (!OutputBin && !OutputBinMainOnly) {
  150. long position = ExportTell(fp);
  151. HI4 packedSizeEnc;
  152. packedSize += 2 + sizeof (TIOS_HOST_FILE_HEADER) + sizeof (TIOS_HOST_FILE_FOOTER);
  153. WriteHI4(packedSizeEnc, packedSize);
  154. ExportSeek(fp, OFFSETOF(TIOS_HOST_FILE_HEADER, FileSize));
  155. fwrite(&packedSizeEnc, 4, 1, fp->File.File);
  156. ExportSeek(fp, position);
  157. }
  158. }
  159. return 0;
  160. }
  161. //=============================================================================
  162. //
  163. //=============================================================================
  164. static void FlushBits(void) {
  165. if (bitMask != 0x80) outPointer++;
  166. }
  167. //=============================================================================
  168. //
  169. //=============================================================================
  170. static void PutBit(int bit) {
  171. if (bit && outPointer < OUT_SIZE) outBuffer[outPointer] |= bitMask;
  172. bitMask >>= 1;
  173. if (!bitMask) {
  174. bitMask = 0x80;
  175. outPointer++;
  176. }
  177. }
  178. //=============================================================================
  179. //
  180. //=============================================================================
  181. static void PutValue(int value) {
  182. int bits = 0, count = 0;
  183. while (value>1) {
  184. bits = (bits<<1) | (value & 1); /* is reversed compared to value */
  185. value >>= 1;
  186. count++;
  187. PutBit(1);
  188. }
  189. if (count<maxGamma) PutBit(0);
  190. while (count--) {
  191. PutBit((bits & 1)); /* output is reversed again -> same as value */
  192. bits >>= 1;
  193. }
  194. }
  195. //--------------------------------------------
  196. // why not initializing value lenValue[0] ????
  197. //--------------------------------------------
  198. //=============================================================================
  199. //
  200. //=============================================================================
  201. static void InitValueLen(void) {
  202. int i;
  203. // could be heavily optimized, but isn't necessary
  204. for (i=1; i<256; i++) {
  205. int count = 0;
  206. if (i<2) count = 0; /* 1 */
  207. else if (i<4) count = 1; /* 2-3 */
  208. else if (i<8) count = 2; /* 4-7 */
  209. else if (i<16) count = 3; /* 8-15 */
  210. else if (i<32) count = 4; /* 16-31 */
  211. else if (i<64) count = 5; /* 32-63 */
  212. else if (i<128) count = 6; /* 64-127 */
  213. else if (i<256) count = 7; /* 128-255 */
  214. lenValue[i] = 2*count;
  215. if (count<maxGamma) lenValue[i]++;
  216. }
  217. }
  218. #define LenValue(a) (lenValue[a])
  219. //=============================================================================
  220. //
  221. //=============================================================================
  222. static void PutNBits(int byte, int bits) {
  223. while (bits--)
  224. PutBit((byte & (1<<bits)));
  225. }
  226. //=============================================================================
  227. //
  228. //=============================================================================
  229. static int OutputNormal(int *esc, unsigned char *data, int newesc) {
  230. timesNormal++;
  231. if ((data[0] & escMask) == *esc) {
  232. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  233. PutBit(0);
  234. PutBit(1);
  235. PutBit(0);
  236. *esc = newesc;
  237. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  238. PutNBits(data[0], 8-escBits);
  239. gainedEscaped += escBits + 3;
  240. timesEscaped++;
  241. return 1;
  242. }
  243. PutNBits(data[0], 8);
  244. return 0;
  245. }
  246. //=============================================================================
  247. //
  248. //=============================================================================
  249. static void OutputEof(int *esc) {
  250. /* EOF marker */
  251. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  252. PutValue(3); /* >2 */
  253. PutValue((2<<maxGamma)-1); /* Maximum value */
  254. FlushBits();
  255. }
  256. //=============================================================================
  257. //
  258. //=============================================================================
  259. static void PutRleByte(int data) {
  260. int index;
  261. for (index = 1; index < 32; index++) {
  262. if (data == rleValues[index]) {
  263. if (index==1) lenStat[0][3]++;
  264. else if (index<=3) lenStat[1][3]++;
  265. else if (index<=7) lenStat[2][3]++;
  266. else if (index<=15) lenStat[3][3]++;
  267. else if (index<=31) lenStat[4][3]++;
  268. gainedRlecode += 8 - LenValue(index);
  269. PutValue(index);
  270. return;
  271. }
  272. }
  273. PutValue(32 + (data>>3));
  274. gainedRlecode -= LenValue(32+(data>>3)) + 3;
  275. PutNBits(data, 3);
  276. lenStat[5][3]++;
  277. }
  278. //=============================================================================
  279. //
  280. //=============================================================================
  281. static void InitRleLen(void) {
  282. int i;
  283. for (i=0; i<256; i++) rleLen[i] = LenValue(32 + 0) + 3;
  284. for (i=1; i<32; i++) rleLen[rleValues[i]] = LenValue(i);
  285. }
  286. #define LenRleByte(d) (rleLen[d])
  287. //=============================================================================
  288. //
  289. //=============================================================================
  290. static int LenRle(int len, int data) {
  291. int out = 0;
  292. do {
  293. if (len == 1) {
  294. out += escBits + 3 + 8;
  295. len = 0;
  296. }
  297. else if (len <= (1<<maxGamma)) {
  298. out += escBits + 3 + LenValue(len-1) + LenRleByte(data);
  299. len = 0;
  300. }
  301. else {
  302. int tmp = min(len, maxrlelen);
  303. out += escBits + 3 + maxGamma + 8 +
  304. LenValue(((tmp-1)>>8)+1) + LenRleByte(data);
  305. len -= tmp;
  306. }
  307. } while (len);
  308. return out;
  309. }
  310. //=============================================================================
  311. //
  312. //=============================================================================
  313. static int OutputRle(int *esc, unsigned char *data, int rlelen) {
  314. int len = rlelen, tmp;
  315. while (len) {
  316. if (len >= 2 && len <= (1<<maxGamma)) {
  317. /* Short RLE */
  318. if (len==2) lenStat[0][2]++;
  319. else if (len<=4) lenStat[1][2]++;
  320. else if (len<=8) lenStat[2][2]++;
  321. else if (len<=16) lenStat[3][2]++;
  322. else if (len<=32) lenStat[4][2]++;
  323. else if (len<=64) lenStat[5][2]++;
  324. else if (len<=128) lenStat[6][2]++;
  325. else if (len<=256) lenStat[6][2]++;
  326. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  327. PutBit(0);
  328. PutBit(1);
  329. PutBit(1);
  330. PutValue(len-1);
  331. PutRleByte(*data);
  332. tmp = 8*len -escBits -3 -LenValue(len-1) -LenRleByte(*data);
  333. gainedRle += tmp;
  334. gainedSRle += tmp;
  335. timesRle++;
  336. timesSRle++;
  337. return 0;
  338. }
  339. if (len<3) {
  340. while (len--)
  341. OutputNormal(esc, data, *esc);
  342. return 0;
  343. }
  344. if (len <= maxrlelen) {
  345. /* Run-length encoding */
  346. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  347. PutBit(0);
  348. PutBit(1);
  349. PutBit(1);
  350. PutValue((1<<maxGamma) + (((len-1)&0xff)>>(8-maxGamma)));
  351. PutNBits((len-1), 8-maxGamma);
  352. PutValue(((len-1)>>8) + 1);
  353. PutRleByte(*data);
  354. tmp = 8*len -escBits -3 -maxGamma -8 -LenValue(((len-1)>>8)+1)
  355. -LenRleByte(*data);
  356. gainedRle += tmp;
  357. gainedLRle += tmp;
  358. timesRle++;
  359. timesLRle++;
  360. return 0;
  361. }
  362. /* Run-length encoding */
  363. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  364. PutBit(0);
  365. PutBit(1);
  366. PutBit(1);
  367. PutValue((1<<maxGamma) + (((maxrlelen-1)&0xff)>>(8-maxGamma)));
  368. PutNBits((maxrlelen-1) & 0xff, 8-maxGamma);
  369. PutValue(((maxrlelen-1)>>8)+1);
  370. PutRleByte(*data);
  371. tmp = 8*maxrlelen -escBits -3 -maxGamma -8
  372. -LenValue(((maxrlelen-1)>>8)+1) -LenRleByte(*data);
  373. gainedRle += tmp;
  374. gainedLRle += tmp;
  375. timesRle++;
  376. timesLRle++;
  377. len -= maxrlelen;
  378. data += maxrlelen;
  379. }
  380. return 0;
  381. }
  382. //=============================================================================
  383. //
  384. //=============================================================================
  385. static int LenLz(int lzlen, int lzpos) {
  386. if (lzlen==2) {
  387. if (lzpos <= 256) return escBits + 2 + 8;
  388. else return 100000;
  389. }
  390. return escBits + 8 + extraLZPosBits +
  391. LenValue(((lzpos-1)>>(8+extraLZPosBits))+1) +
  392. LenValue(lzlen-1);
  393. }
  394. //=============================================================================
  395. //
  396. //=============================================================================
  397. static int OutputLz(int *esc, int lzlen, int lzpos, int curpos) {
  398. if (lzlen==2) lenStat[0][1]++;
  399. else if (lzlen<=4) lenStat[1][1]++;
  400. else if (lzlen<=8) lenStat[2][1]++;
  401. else if (lzlen<=16) lenStat[3][1]++;
  402. else if (lzlen<=32) lenStat[4][1]++;
  403. else if (lzlen<=64) lenStat[5][1]++;
  404. else if (lzlen<=128) lenStat[6][1]++;
  405. else if (lzlen<=256) lenStat[7][1]++;
  406. if (lzlen >= 2 && lzlen <= maxlzlen) {
  407. int tmp;
  408. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  409. tmp = ((lzpos-1)>>(8+extraLZPosBits))+2;
  410. if (tmp==2) lenStat[0][0]++;
  411. else if (tmp<=4) lenStat[1][0]++;
  412. else if (tmp<=8) lenStat[2][0]++;
  413. else if (tmp<=16) lenStat[3][0]++;
  414. else if (tmp<=32) lenStat[4][0]++;
  415. else if (tmp<=64) lenStat[5][0]++;
  416. else if (tmp<=128) lenStat[6][0]++;
  417. else if (tmp<=256) lenStat[6][0]++;
  418. if (lzlen==2) {
  419. PutValue(lzlen-1);
  420. PutBit(0);
  421. if (lzpos > 256) Warning(NULL, "lzpos at %d too long (%d) for lzlen==2\n", curpos, lzpos);
  422. }
  423. else {
  424. PutValue(lzlen-1);
  425. PutValue( ((lzpos-1) >> (8+extraLZPosBits)) +1);
  426. PutNBits( ((lzpos-1) >> 8), extraLZPosBits);
  427. }
  428. PutNBits(((lzpos-1) & 0xff) ^ 0xff, 8);
  429. gainedLz += 8*lzlen -LenLz(lzlen, lzpos);
  430. timesLz++;
  431. return 3;
  432. }
  433. Warning(NULL, "lzlen too short/long (%d)\n", lzlen);
  434. return lzlen;
  435. }
  436. /* Non-recursive version */
  437. /* NOTE! IMPORTANT! the "length" array length must be inlen+1 */
  438. //=============================================================================
  439. //
  440. //=============================================================================
  441. static int OptimizeLength(int optimize) {
  442. int i;
  443. length[inlen] = 0; /* one off the end, our 'target' */
  444. for (i=inlen-1; i>=0; i--) {
  445. int r1 = 8 + length[i+1], r2, r3;
  446. if (!lzlen[i] && !rle[i]) {
  447. length[i] = r1;
  448. mode[i] = LITERAL;
  449. continue;
  450. }
  451. /* If rle>maxlzlen, skip to the start of the rle-maxlzlen.. */
  452. if (rle[i] > maxlzlen && elr[i] > 1) {
  453. int z = elr[i];
  454. i -= elr[i];
  455. r2 = LenRle(rle[i], indata[i]) + length[i+ rle[i]];
  456. if (optimize) {
  457. int ii, mini = rle[i], minv = r2;
  458. int bot = rle[i] - (1<<maxGamma);
  459. if (bot < 2)
  460. bot = 2;
  461. for (ii=mini-1; ii>=bot; ii--) {
  462. int v = LenRle(ii, indata[i]) + length[i + ii];
  463. if (v < minv) {
  464. minv = v;
  465. mini = ii;
  466. }
  467. }
  468. if (minv != r2) {
  469. lzopt += r2 - minv;
  470. rle[i] = mini;
  471. r2 = minv;
  472. }
  473. }
  474. length[i] = r2;
  475. mode[i] = RLE;
  476. for (; z>=0; z--) {
  477. length[i+z] = r2;
  478. mode[i+z] = RLE;
  479. }
  480. continue;
  481. }
  482. r3 = r2 = r1 + 1000; /* r3 >= r2 > r1 */
  483. if (rle[i]) {
  484. r2 = LenRle(rle[i], indata[i]) + length[i+ rle[i]];
  485. if (optimize) {
  486. int ii, mini = rle[i], minv = r2;
  487. /* Check only the original length and all shorter
  488. lengths that are power of two.
  489. Does not really miss many 'minimums' this way,
  490. at least not globally..
  491. Makes the assumption that the Elias Gamma Code is
  492. used, i.e. values of the form 2^n are 'optimal' */
  493. ii = 2;
  494. while (rle[i] > ii) {
  495. int v = LenRle(ii, indata[i]) + length[i + ii];
  496. if (v < minv) {
  497. minv = v;
  498. mini = ii;
  499. }
  500. ii <<= 1;
  501. }
  502. if (minv != r2) {
  503. lzopt += r2 - minv;
  504. rle[i] = mini;
  505. r2 = minv;
  506. }
  507. }
  508. }
  509. if (lzlen[i]) {
  510. r3 = LenLz(lzlen[i], lzpos[i]) + length[i + lzlen[i]];
  511. if (optimize && lzlen[i]>2) {
  512. int ii, mini = lzlen[i], minv = r3;
  513. int topLen = LenLz(lzlen[i], lzpos[i])
  514. - LenValue(lzlen[i]-1);
  515. /* Check only the original length and all shorter
  516. lengths that are power of two.
  517. Does not really miss many 'minimums' this way,
  518. at least not globally..
  519. Makes the assumption that the Elias Gamma Code is
  520. used, i.e. values of the form 2^n are 'optimal' */
  521. ii = 4;
  522. while (lzlen[i] > ii) {
  523. int v = topLen + LenValue(ii-1) + length[i + ii];
  524. if (v < minv) {
  525. minv = v;
  526. mini = ii;
  527. }
  528. ii <<= 1;
  529. }
  530. /*
  531. Note:
  532. 2-byte optimization checks are no longer done
  533. with the rest, because the equation gives too long
  534. code lengths for 2-byte matches if extraLzPosBits>0.
  535. */
  536. /* Two-byte rescan/check */
  537. if (backSkip[i] && backSkip[i] <= 256) {
  538. /* There are previous occurrances (near enough) */
  539. int v = LenLz(2, (int)backSkip[i]) + length[i + 2];
  540. if (v < minv) {
  541. minv = v;
  542. mini = 2;
  543. lzlen[i] = mini;
  544. r3 = minv;
  545. lzpos[i] = (int)backSkip[i];
  546. }
  547. }
  548. if (minv != r3 && minv < r2) {
  549. lzopt += r3 - minv;
  550. lzlen[i] = mini;
  551. r3 = minv;
  552. }
  553. }
  554. }
  555. if (r2 <= r1) {
  556. if (r2 <= r3) {
  557. length[i] = r2;
  558. mode[i] = RLE;
  559. }
  560. else {
  561. length[i] = r3;
  562. mode[i] = LZ77;
  563. }
  564. }
  565. else {
  566. if (r3 <= r1) {
  567. length[i] = r3;
  568. mode[i] = LZ77;
  569. }
  570. else {
  571. length[i] = r1;
  572. mode[i] = LITERAL;
  573. }
  574. }
  575. }
  576. return length[0];
  577. }
  578. /*
  579. The algorithm in the OptimizeEscape() works as follows:
  580. 1) Only unpacked bytes are processed, they are marked
  581. with MMARK. We proceed from the end to the beginning.
  582. Variable A (old/new length) is updated.
  583. 2) At each unpacked byte, one and only one possible
  584. escape matches. A new escape code must be selected
  585. for this case. The optimal selection is the one which
  586. provides the shortest number of escapes to the end
  587. of the file,
  588. i.e. A[esc] = 1+min(A[0], A[1], .. A[states-1]).
  589. For other states A[esc] = A[esc];
  590. If we change escape in this byte, the new escape is
  591. the one with the smallest value in A.
  592. 3) The starting escape is selected from the possibilities
  593. and mode 0 is restored to all mode 3 locations.
  594. */
  595. //=============================================================================
  596. //
  597. //=============================================================================
  598. static int OptimizeEscape(int *startEscape, int *nonNormal) {
  599. int i, j, states = (1<<escBits);
  600. long minp = 0, minv = 0, other = 0;
  601. long a[256]; /* needs int/long */
  602. long b[256]; /* Remembers the # of escaped for each */
  603. int esc8 = 8-escBits;
  604. for (i=0; i<256; i++) b[i] = a[i] = -1;
  605. if (states>256) {
  606. Warning(NULL, "Escape optimize: only 256 states (%d)!\n",states);
  607. return 0;
  608. }
  609. /* Mark those bytes that are actually outputted */
  610. for (i=0; i<inlen; ) {
  611. switch (mode[i]) {
  612. case LZ77:
  613. other++;
  614. i += lzlen[i];
  615. break;
  616. case RLE:
  617. other++;
  618. i += rle[i];
  619. break;
  620. /*case LITERAL:*/
  621. default:
  622. mode[i++] = MMARK; /* mark it used so we can identify it */
  623. break;
  624. }
  625. }
  626. for (i=inlen-1; i>=0; i--) {
  627. /* Using a table to skip non-normal bytes does not help.. */
  628. if (mode[i] == MMARK) {
  629. int k = (indata[i] >> esc8);
  630. /* Change the tag values back to normal */
  631. mode[i] = LITERAL;
  632. /*
  633. k are the matching bytes,
  634. minv is the minimum value,
  635. minp is the minimum index
  636. */
  637. newesc[i] = (minp << esc8);
  638. a[k] = minv + 1;
  639. b[k] = b[minp] + 1;
  640. if (k==minp) {
  641. /* Minimum changed -> need to find a new minimum */
  642. /* a[k] may still be the minimum */
  643. minv++;
  644. for (k=states-1; k>=0; k--) {
  645. if (a[k] < minv) {
  646. minv = a[k];
  647. minp = k;
  648. /*
  649. There may be others, but the first one that
  650. is smaller than the old minimum is equal to
  651. any other new minimum.
  652. */
  653. break;
  654. }
  655. }
  656. }
  657. }
  658. }
  659. /* Select the best value for the initial escape */
  660. if (startEscape) {
  661. i = inlen; /* make it big enough */
  662. for (j=states-1; j>=0; j--) {
  663. if (a[j] <= i) {
  664. *startEscape = (j << esc8);
  665. i = a[j];
  666. }
  667. }
  668. }
  669. if (nonNormal)
  670. *nonNormal = other;
  671. return b[startEscape ? (*startEscape>>esc8) : 0];
  672. }
  673. //=============================================================================
  674. // Initialize the RLE byte code table according to all RLE's found so far O(n)
  675. //=============================================================================
  676. static void InitRle(void) {
  677. int p, mr, mv, i;
  678. for (i=1; i<32; i++) {
  679. mr = -1;
  680. mv = 0;
  681. for (p=0; p<256; p++) {
  682. if (rleHist[p] > mv) {
  683. mv = rleHist[p];
  684. mr = p;
  685. }
  686. }
  687. if (mv>0) {
  688. rleValues[i] = mr;
  689. rleHist[mr] = -1;
  690. } else
  691. break;
  692. }
  693. InitRleLen();
  694. }
  695. //=============================================================================
  696. // Initialize the RLE byte code table according to RLE's actually used O(n)
  697. //=============================================================================
  698. static void OptimizeRle(int flags) {
  699. int p, mr, mv, i;
  700. if (flags & F_STATS) fprintf(VERBOSE_OUT, "RLE Byte Code Re-Tune, RLE Ranks:\n");
  701. for (p=0; p<256; p++) rleHist[p] = 0;
  702. for (p=0; p<inlen; ) {
  703. switch (mode[p]) {
  704. case LZ77:
  705. p += lzlen[p];
  706. break;
  707. case RLE:
  708. rleHist[indata[p]]++;
  709. p += rle[p];
  710. break;
  711. default:
  712. p++;
  713. break;
  714. }
  715. }
  716. for (i=1; i<32; i++) {
  717. mr = -1;
  718. mv = 0;
  719. for (p=0; p<256; p++) {
  720. if (rleHist[p] > mv) {
  721. mv = rleHist[p];
  722. mr = p;
  723. }
  724. }
  725. if (mv>0) {
  726. rleValues[i] = mr;
  727. if (flags & F_STATS) {
  728. fprintf(VERBOSE_OUT, " %2d.0x%02x %-3d ", i, mr, mv);
  729. if (!((i - 1) % 6)) fprintf(VERBOSE_OUT, "\n");
  730. }
  731. rleHist[mr] = -1;
  732. }
  733. else {
  734. break;
  735. }
  736. }
  737. rleUsed = i-1;
  738. if (flags & F_STATS)
  739. if (((i - 1) % 6)!=1) fprintf(VERBOSE_OUT, "\n");
  740. InitRleLen();
  741. }
  742. //=============================================================================
  743. //
  744. //=============================================================================
  745. static int PackLz77(int lzsz, int flags, int *startEscape)
  746. {
  747. int i, j, outlen, p, headerSize;
  748. int escape;
  749. unsigned char *hashValue;
  750. unsigned char *a;
  751. int k;
  752. unsigned short *lastPair;
  753. unsigned short err_occured = 0;
  754. int rescan = 0;
  755. if (lzsz < 0 || lzsz > lrange) {
  756. Warning(NULL, "LZ range must be from 0 to %d (was %d). Set to %d.\n",
  757. lrange, lzsz, lrange);
  758. lzsz = lrange;
  759. }
  760. if (lzsz > 65535) {
  761. Warning(NULL,
  762. "LZ range must be from 0 to 65535 (was %d). Set to 65535.\n",
  763. lzsz);
  764. lzsz = 65535;
  765. }
  766. if (!lzsz) Warning(NULL, "Zero LZ range. Only RLE packing used.\n");
  767. InitRleLen();
  768. length = (int *)calloc(sizeof(int), inlen + 1);
  769. mode = (unsigned char *)calloc(sizeof(unsigned char), inlen);
  770. rle = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  771. elr = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  772. lzlen = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  773. lzpos = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  774. newesc = (unsigned char *)calloc(sizeof(unsigned char), inlen);
  775. backSkip = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  776. hashValue = (unsigned char *)malloc(inlen);
  777. lastPair = (unsigned short *)calloc(sizeof(unsigned short), 256*256);
  778. /* error checking */
  779. if (!length || !mode || !rle || !elr || !lzlen || !lzpos || !newesc ||
  780. !lastPair || !backSkip
  781. || !hashValue)
  782. {
  783. Error(NULL, "Memory allocation failed!\n");
  784. err_occured = 1;
  785. goto errorexit;
  786. }
  787. i = 0;
  788. j = 0;
  789. a = indata + inlen;
  790. for (p=inlen-1; p>=0; p--) {
  791. k = j;
  792. j = i;
  793. i = *--a; /* Only one read per position */
  794. hashValue[p] = i*3 + j*5 + k*7; /* 7.95 % */
  795. }
  796. /* Detect all RLE and LZ77 jump possibilities */
  797. for (p=0; p<inlen; p++) {
  798. if (flags & F_VERBOSE) {
  799. if (!(p & 2047)) {
  800. fprintf(VERBOSE_OUT, "\r%d ", p);
  801. fflush(VERBOSE_OUT); /* for SAS/C */
  802. }
  803. }
  804. /* check run-length code - must be done, LZ77 search needs it! */
  805. if (rle[p] <= 0) {
  806. unsigned char *a = indata + p;
  807. int val = *a++; /* if this were uchar, it would go to stack..*/
  808. int top = inlen - p;
  809. int rlelen = 1;
  810. /* Loop for the whole RLE */
  811. while (rlelen<top && *a++ == (unsigned char)val) rlelen++;
  812. if (rlelen>=2) {
  813. rleHist[indata[p]]++;
  814. for (i=rlelen-1; i>=0; i--) {
  815. rle[p+i] = rlelen-i;
  816. elr[p+i] = i; /* For RLE backward skipping */
  817. }
  818. }
  819. }
  820. /* check LZ77 code */
  821. if (p+rle[p]+1<inlen) {
  822. int bot = p - lzsz, maxval, maxpos, rlep = rle[p];
  823. unsigned char hashCompare = hashValue[p];
  824. /*
  825. There's always 1 equal byte, although it may
  826. not be marked as RLE.
  827. */
  828. if (rlep <= 0)
  829. rlep = 1;
  830. if (bot < 0)
  831. bot = 0;
  832. bot += (rlep-1);
  833. /*
  834. First get the shortest possible match (if any).
  835. If there is no 2-byte match, don't look further,
  836. because there can't be a longer match.
  837. */
  838. i = (int)lastPair[ (indata[p]<<8) | indata[p+1] ] -1;
  839. if (i>=0 && i>=bot) {
  840. /* Got a 2-byte match at least */
  841. maxval = 2;
  842. maxpos = p-i;
  843. /*
  844. A..AB rlep # of A's, B is something else..
  845. Search for bytes that are in p + (rlep-1), i.e.
  846. the last rle byte ('A') and the non-matching one
  847. ('B'). When found, check if the rle in the compare
  848. position (i) is long enough (i.e. the same number
  849. of A's at p and i-rlep+1).
  850. There are dramatically less matches for AB than for
  851. AA, so we get a huge speedup with this approach.
  852. We are still guaranteed to find the most recent
  853. longest match there is.
  854. */
  855. i = (int)lastPair[(indata[p+(rlep-1)]<<8) | indata[p+rlep]] -1;
  856. while (i>=bot /* && i>=rlep-1 */) { /* bot>=rlep-1, i>=bot ==> i>=rlep-1 */
  857. /* Equal number of A's ? */
  858. if (!(rlep-1) || rle[i-(rlep-1)]==rlep) { /* 'head' matches */
  859. /* rlep==1 ==> (rlep-1)==0 */
  860. /* ivanova.run: 443517 rlep==1,
  861. 709846 rle[i+1-rlep]==rlep */
  862. /*
  863. Check the hash values corresponding to the last
  864. two bytes of the currently longest match and
  865. the first new matching(?) byte. If the hash
  866. values don't match, don't bother to check the
  867. data itself.
  868. */
  869. if (
  870. hashValue[i+maxval-rlep-1] == hashCompare
  871. ) {
  872. unsigned char *a = indata + i+2; /* match */
  873. unsigned char *b = indata + p+rlep-1+2;/* curpos */
  874. int topindex = inlen-(p+rlep-1);
  875. /* the 2 first bytes ARE the same.. */
  876. j = 2;
  877. while (j < topindex && *a++==*b++)
  878. j++;
  879. if (j + rlep-1 > maxval) {
  880. int tmplen = j+rlep-1, tmppos = p-i+rlep-1;
  881. if (tmplen > maxlzlen)
  882. tmplen = maxlzlen;
  883. /* Accept only versions that really are shorter */
  884. if (tmplen*8 - LenLz(tmplen, tmppos) >
  885. maxval*8 - LenLz(maxval, maxpos)) {
  886. maxval = tmplen;
  887. maxpos = tmppos;
  888. hashCompare = hashValue[p+maxval-2];
  889. }
  890. if (maxval == maxlzlen)
  891. break;
  892. }
  893. }
  894. }
  895. if (!backSkip[i])
  896. break; /* No previous occurrances (near enough) */
  897. i -= (int)backSkip[i];
  898. }
  899. /*
  900. If there is 'A' in the previous position also,
  901. RLE-like LZ77 is possible, although rarely
  902. shorter than real RLE.
  903. */
  904. if (p && rle[p-1] > maxval) {
  905. maxval = rle[p-1] - 1;
  906. maxpos = 1;
  907. }
  908. /*
  909. Last, try to find as long as possible match
  910. for the RLE part only.
  911. */
  912. if (maxval < maxlzlen && rlep > maxval) {
  913. bot = p - lzsz;
  914. if (bot < 0)
  915. bot = 0;
  916. /* Note: indata[p] == indata[p+1] */
  917. i = (int)lastPair[indata[p]*257] -1;
  918. while (/* i>= rlep-2 &&*/ i>=bot) {
  919. if (elr[i] + 2 > maxval) {
  920. maxval = min(elr[i] + 2, rlep);
  921. maxpos = p - i + (maxval-2);
  922. if(maxval == rlep)
  923. break; /* Got enough */
  924. }
  925. i -= elr[i];
  926. if (!backSkip[i])
  927. break; /* No previous occurrances (near enough) */
  928. i -= (int)backSkip[i];
  929. }
  930. }
  931. if (p+maxval > inlen) {
  932. Warning(NULL, "Error @ %d, lzlen %d, pos %d - exceeds inlen\n",p, maxval, maxpos);
  933. maxval = inlen - p;
  934. }
  935. if (maxpos<=256 || maxval > 2) {
  936. if (maxpos < 0) Warning(NULL, "Error @ %d, lzlen %d, pos %d\n",p, maxval, maxpos);
  937. lzlen[p] = (maxval<maxlzlen)?maxval:maxlzlen;
  938. lzpos[p] = maxpos;
  939. }
  940. }
  941. }
  942. /* Update the two-byte history ('hash table') &
  943. backSkip ('linked list') */
  944. if (p+1<inlen) {
  945. int index = (indata[p]<<8) | indata[p+1];
  946. int ptr = p - (lastPair[index]-1);
  947. if (ptr > p || ptr > 0xffff)
  948. ptr = 0;
  949. backSkip[p] = ptr;
  950. lastPair[index] = p+1;
  951. }
  952. }
  953. if (flags & F_VERBOSE) {
  954. fprintf(VERBOSE_OUT, "\rChecked: %d \n", p);
  955. fflush(VERBOSE_OUT);
  956. }
  957. /* Initialize the RLE selections */
  958. InitRle();
  959. /* Check the normal bytes / all ratio */
  960. {
  961. int mb, mv;
  962. if (flags & F_VERBOSE) {
  963. fprintf(VERBOSE_OUT, "Selecting the number of escape bits.. ");
  964. fflush(VERBOSE_OUT);
  965. }
  966. /*
  967. Absolute maximum number of escaped bytes with
  968. the escape optimize is 2^-n, where n is the
  969. number of escape bits used.
  970. This worst case happens only on equal-
  971. distributed normal bytes (01230123..).
  972. This is why the typical values are so much smaller.
  973. */
  974. mb = 0;
  975. mv = 8*OUT_SIZE;
  976. for (escBits=1; escBits<9; escBits++) {
  977. int escaped, other = 0, c;
  978. escMask = (0xff00>>escBits) & 0xff;
  979. /* Find the optimum path for selected escape bits (no optimize) */
  980. OptimizeLength(0);
  981. /* Optimize the escape selections for this path & escBits */
  982. escaped = OptimizeEscape(&escape, &other);
  983. /* Compare value: bits lost for escaping -- bits lost for prefix */
  984. c = (escBits+3)*escaped + other*escBits;
  985. if (flags & F_STATS) {
  986. fprintf(VERBOSE_OUT, " %d:%d", escBits, c);
  987. fflush(VERBOSE_OUT); /* for SAS/C */
  988. }
  989. if (c < mv) {
  990. mb = escBits;
  991. mv = c;
  992. } else {
  993. /* minimum found */
  994. break;
  995. }
  996. if (escBits==4 && (flags & F_STATS)) fprintf(VERBOSE_OUT, "\n");
  997. }
  998. if (mb==1) { /* Minimum was 1, check 0 */
  999. int escaped;
  1000. escBits = 0;
  1001. escMask = 0;
  1002. /* Find the optimum path for selected escape bits (no optimize) */
  1003. OptimizeLength(0);
  1004. /* Optimize the escape selections for this path & escBits */
  1005. escaped = OptimizeEscape(&escape, NULL);
  1006. if ((flags & F_STATS)) {
  1007. fprintf(VERBOSE_OUT, " %d:%d", escBits, 3*escaped);
  1008. fflush(VERBOSE_OUT); /* for SAS/C */
  1009. }
  1010. if (3*escaped < mv) {
  1011. mb = 0;
  1012. /* mv = 3*escaped; */
  1013. }
  1014. }
  1015. if ((flags & F_STATS)) fprintf(VERBOSE_OUT, "\n");
  1016. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT, "Selected %d-bit escapes\n", mb);
  1017. escBits = mb;
  1018. escMask = (0xff00>>escBits) & 0xff;
  1019. }
  1020. if (flags & F_VERBOSE) {
  1021. fprintf(VERBOSE_OUT, "Optimizing LZ77 and RLE lengths...");
  1022. fflush(VERBOSE_OUT);
  1023. }
  1024. /* Find the optimum path (optimize) */
  1025. OptimizeLength(1);
  1026. if (flags & F_STATS) {
  1027. fprintf(VERBOSE_OUT, " gained %d units.\n", lzopt/8);
  1028. }
  1029. else {
  1030. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT, "\n");
  1031. }
  1032. {
  1033. long lzstat[5] = {0,0,0,0,0}, i, cur = 0, old = extraLZPosBits;
  1034. if (flags & F_VERBOSE) {
  1035. fprintf(VERBOSE_OUT, "Selecting LZPOS LO length.. ");
  1036. fflush(VERBOSE_OUT);
  1037. }
  1038. for (p=0; p<inlen; ) {
  1039. switch (mode[p]) {
  1040. case LZ77:
  1041. extraLZPosBits = 0;
  1042. lzstat[0] += LenLz(lzlen[p], lzpos[p]);
  1043. extraLZPosBits = 1;
  1044. lzstat[1] += LenLz(lzlen[p], lzpos[p]);
  1045. extraLZPosBits = 2;
  1046. lzstat[2] += LenLz(lzlen[p], lzpos[p]);
  1047. extraLZPosBits = 3;
  1048. lzstat[3] += LenLz(lzlen[p], lzpos[p]);
  1049. extraLZPosBits = 4;
  1050. lzstat[4] += LenLz(lzlen[p], lzpos[p]);
  1051. p += lzlen[p];
  1052. break;
  1053. case RLE:
  1054. p += rle[p];
  1055. break;
  1056. default:
  1057. p++;
  1058. break;
  1059. }
  1060. }
  1061. for (i=0; i<5; i++) {
  1062. if (flags & F_STATS) fprintf(VERBOSE_OUT, " %ld:%ld", i + 8, lzstat[i]);
  1063. if (lzstat[i] < lzstat[cur]) cur = i;
  1064. }
  1065. extraLZPosBits = cur;
  1066. if (flags & F_STATS) fprintf(VERBOSE_OUT, "\n");
  1067. if (flags & F_VERBOSE) {
  1068. fprintf(VERBOSE_OUT, "Selected %d-bit LZPOS LO part\n",extraLZPosBits + 8);
  1069. if (cur != old) fprintf(VERBOSE_OUT,"Note: Using option -p%ld you may get better results.\n",cur);
  1070. }
  1071. /* Find the optimum path (optimize) */
  1072. if (extraLZPosBits != old) OptimizeLength(1);
  1073. }
  1074. {
  1075. long stat[4] = {0,0,0,0};
  1076. for (p=0; p<inlen; ) {
  1077. switch (mode[p]) {
  1078. case LZ77:
  1079. if ((lzpos[p] >> 8)+1 > (1<<maxGamma))
  1080. stat[3]++;
  1081. if (lzlen[p] > (1<<maxGamma))
  1082. stat[0]++;
  1083. p += lzlen[p];
  1084. break;
  1085. case RLE:
  1086. if (rle[p] > (1<<(maxGamma-1))) {
  1087. if (rle[p] <= (1<<maxGamma))
  1088. stat[1]++;
  1089. }
  1090. p += rle[p];
  1091. break;
  1092. default:
  1093. p++;
  1094. break;
  1095. }
  1096. }
  1097. /* TODO: better formula.. */
  1098. if (maxGamma < 7 && stat[0] + stat[1] + stat[3] > 10) {
  1099. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,"Note: Using option -m%d you may get better results.\n",maxGamma+1);
  1100. }
  1101. if (maxGamma > 5 && stat[0] + stat[1] + stat[3] < 4) {
  1102. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,"Note: Using option -m%d you may get better results.\n",maxGamma-1);
  1103. }
  1104. }
  1105. /* Optimize the escape selections */
  1106. OptimizeEscape(&escape, NULL);
  1107. if (startEscape) *startEscape = escape;
  1108. OptimizeRle(flags); /* Retune the RLE selections */
  1109. if (flags & F_VERBOSE) {
  1110. int oldEscape = escape;
  1111. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,"normal RLE LZLEN LZPOS(absolute)\n\n");
  1112. for (p=0; p<inlen; ) {
  1113. switch (mode[p]) {
  1114. case LZ77:
  1115. mode[p - lzpos[p]] |= MMARK; /* Was referred to by lz77 */
  1116. p += lzlen[p];
  1117. break;
  1118. case RLE:
  1119. p += rle[p];
  1120. break;
  1121. /* case LITERAL:
  1122. case MMARK:*/
  1123. default:
  1124. p++;
  1125. break;
  1126. }
  1127. }
  1128. j = 0;
  1129. for (p=0; p<inlen; p++) {
  1130. switch (mode[p]) {
  1131. case MMARK | LITERAL:
  1132. case LITERAL:
  1133. if (flags & F_VERBOSE) {
  1134. if (j==p) fprintf(VERBOSE_OUT,">");
  1135. else fprintf(VERBOSE_OUT," ");
  1136. }
  1137. if (j==p) {
  1138. if (flags & F_VERBOSE) {
  1139. fprintf(VERBOSE_OUT,"*001* %03d %03d %04x(%04x) %02x %s %02x",
  1140. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1141. (mode[p] & MMARK)?"#":" ", newesc[p]);
  1142. }
  1143. if ((indata[p] & escMask) == escape) {
  1144. escape = newesc[p];
  1145. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,"<<");
  1146. }
  1147. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,"\n");
  1148. j += 1;
  1149. } else {
  1150. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,"*001* %03d %03d %04x(%04x) %02x %s %02x\n",
  1151. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1152. (mode[p] & MMARK)?"#":" ", newesc[p]);
  1153. }
  1154. break;
  1155. case MMARK | LZ77:
  1156. case LZ77:
  1157. if (j==p) {
  1158. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,">");
  1159. j += lzlen[p];
  1160. } else
  1161. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT," ");
  1162. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT," 001 %03d *%03d* %04x(%04x) %02x %s\n",
  1163. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1164. (mode[p] & MMARK)?"#":" ");
  1165. break;
  1166. case MMARK | RLE:
  1167. case RLE:
  1168. if (j==p) {
  1169. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,">");
  1170. j += rle[p];
  1171. } else
  1172. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT," ");
  1173. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT," 001 *%03d* %03d %04x(%04x) %02x %s\n",
  1174. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1175. (mode[p] & MMARK)?"#":" ");
  1176. break;
  1177. default:
  1178. j++;
  1179. break;
  1180. }
  1181. mode[p] &= ~MMARK;
  1182. }
  1183. escape = oldEscape;
  1184. }
  1185. for (p=0; p<inlen; ) {
  1186. switch (mode[p]) {
  1187. case LITERAL: /* normal */
  1188. length[p] = outPointer;
  1189. OutputNormal(&escape, indata+p, newesc[p]);
  1190. p++;
  1191. break;
  1192. case LZ77: /* lz77 */
  1193. /* Not possible for smaller backSkip table
  1194. (the table is overwritten during previous use) */
  1195. /* Re-search matches to get the closest one */
  1196. if (lzopt && lzlen[p] > 2 && lzlen[p] > rle[p]) {
  1197. int bot = p - lzpos[p] + 1, i;
  1198. unsigned short rlep = rle[p];
  1199. if (!rlep)
  1200. rlep = 1;
  1201. if (bot < 0)
  1202. bot = 0;
  1203. bot += (rlep-1);
  1204. i = p - (int)backSkip[p];
  1205. while (i>=bot /* && i>=rlep-1 */) {
  1206. /* Equal number of A's ? */
  1207. if (rlep==1 || rle[i-rlep+1]==rlep) { /* 'head' matches */
  1208. unsigned char *a = indata + i+1; /* match */
  1209. unsigned char *b = indata + p+rlep-1+1; /* curpos */
  1210. int topindex = inlen-(p+rlep-1);
  1211. j = 1;
  1212. while (j < topindex && *a++==*b++)
  1213. j++;
  1214. if (j + rlep-1 >= lzlen[p]) {
  1215. int tmppos = p-i+rlep-1;
  1216. rescan +=
  1217. LenLz(lzlen[p], lzpos[p]) -
  1218. LenLz(lzlen[p], tmppos);
  1219. lzpos[p] = tmppos;
  1220. break;
  1221. }
  1222. }
  1223. if (!backSkip[i])
  1224. break; /* No previous occurrances (near enough) */
  1225. i -= (int)backSkip[i];
  1226. }
  1227. }
  1228. for (i=0; i<lzlen[p]; i++)
  1229. length[p+i] = outPointer;
  1230. OutputLz(&escape, lzlen[p], lzpos[p], p);
  1231. p += lzlen[p];
  1232. break;
  1233. case RLE: /* rle */
  1234. for (i=0; i<rle[p]; i++)
  1235. length[p+i] = outPointer;
  1236. OutputRle(&escape, indata+p, rle[p]);
  1237. p += rle[p];
  1238. break;
  1239. default: /* Error Flynn :-) */
  1240. p++;
  1241. Warning(NULL, "Internal error: mode %d\n", mode[p]);
  1242. break;
  1243. }
  1244. }
  1245. OutputEof(&escape);
  1246. i = inlen;
  1247. for (p=0; p<inlen; p++) {
  1248. int pos = (inlen - outPointer) + (int)length[p] - p;
  1249. i = min(i, pos);
  1250. }
  1251. if (i<0)
  1252. reservedBytes = -i + 2;
  1253. else
  1254. reservedBytes = 0;
  1255. headerSize = 16 + rleUsed;
  1256. outlen = outPointer + headerSize; /* unpack code */
  1257. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT, "In: %d, out: %d, ratio: %5.2f%% (%4.2f[%4.2f] b/B)"
  1258. ", gained: %5.2f%%\n",
  1259. inlen, outlen, (double)outlen*100.0/(double)inlen + 0.005,
  1260. 8.0*(double)outlen/(double)inlen + 0.005,
  1261. 8.0*(double)(outlen-headerSize+rleUsed+4)/(double)inlen + 0.005,
  1262. 100.0 - (double)outlen*100.0/(double)inlen + 0.005);
  1263. if (flags & F_VERBOSE) {
  1264. fprintf(VERBOSE_OUT, "Gained RLE: %d (S+L:%d+%d), LZ: %d, Esc: %d"
  1265. ", Decompressor: %d\n",
  1266. gainedRle/8, gainedSRle/8, gainedLRle/8,
  1267. gainedLz/8, -gainedEscaped/8, -headerSize);
  1268. fprintf(VERBOSE_OUT, "Times RLE: %d (%d+%d), LZ: %d, Esc: %d (normal: %d)"
  1269. ", %d escape bit%s\n",
  1270. timesRle, timesSRle, timesLRle,
  1271. timesLz, timesEscaped, timesNormal,
  1272. escBits, (escBits==1)?"":"s" );
  1273. }
  1274. if ((flags & F_STATS)) {
  1275. const char *ll[] = {"2", "3-4", "5-8", "9-16", "17-32", "33-64",
  1276. "65-128", "129-256"};
  1277. fprintf(VERBOSE_OUT, "(Gained by RLE Code: %d, LZPOS LO Bits %d"
  1278. ", maxLen: %d, tag bit/prim. %4.2f)\n",
  1279. gainedRlecode/8 - rleUsed,
  1280. extraLZPosBits + 8,
  1281. (2<<maxGamma),
  1282. (double)((timesRle+timesLz)*escBits +
  1283. timesEscaped*(escBits + 3))/
  1284. (double)(timesRle+timesLz+timesNormal) + 0.0049);
  1285. fprintf(VERBOSE_OUT, " LZPOS HI+2 LZLEN S-RLE RLEcode\n");
  1286. fprintf(VERBOSE_OUT, " ------------------------------\n");
  1287. for (i=0; i<=maxGamma; i++) {
  1288. fprintf(VERBOSE_OUT, "%-7s %5d %5d", ll[i],
  1289. lenStat[i][0], lenStat[i][1]);
  1290. if (i<maxGamma)
  1291. fprintf(VERBOSE_OUT, " %5d", lenStat[i][2]);
  1292. else
  1293. fprintf(VERBOSE_OUT, " -");
  1294. if (i<6)
  1295. fprintf(VERBOSE_OUT, " %5d%s\n", lenStat[i][3], (i==5)?"*":"");
  1296. else
  1297. fprintf(VERBOSE_OUT, " -\n");
  1298. }
  1299. fprintf(VERBOSE_OUT, "LZ77 rescan gained %d bytes\n", rescan/8);
  1300. }
  1301. errorexit:
  1302. if (rle) free(rle);
  1303. if (elr) free(elr);
  1304. if (lzlen) free(lzlen);
  1305. if (lzpos) free(lzpos);
  1306. if (length) free(length);
  1307. if (mode) free(mode);
  1308. if (newesc) free(newesc);
  1309. if (lastPair) free(lastPair);
  1310. if (backSkip) free(backSkip);
  1311. if (hashValue) free(hashValue);
  1312. return err_occured;
  1313. }
  1314. //=============================================================================
  1315. // as usual: the main, but a long one ...
  1316. //=============================================================================
  1317. int TTPack(int flags, int in_len, unsigned char *in_data, EXP_FILE *out_file) {
  1318. int startAddr = 0x258;
  1319. int lzlen = -1;
  1320. int startEscape = 0;
  1321. int n;
  1322. unsigned long timeused = clock();
  1323. TTPackInit();
  1324. lrange = LRANGE;
  1325. maxlzlen = MAXLZLEN;
  1326. maxrlelen = MAXRLELEN;
  1327. InitValueLen();
  1328. if (lzlen == -1) lzlen = DEFAULT_LZLEN;
  1329. inlen = in_len;
  1330. indata = in_data;
  1331. if (startAddr + inlen -1 > 0xffff) {
  1332. Error(NULL, "File is too large to handle (>64936 Bytes)");
  1333. if (indata) free(indata);
  1334. return 1;
  1335. }
  1336. n = PackLz77(lzlen, flags, &startEscape);
  1337. if (!n) {
  1338. // outBuffer ... static global array (65536 Bytes)
  1339. SavePack(outBuffer, outPointer, out_file, startEscape, rleValues, extraLZPosBits);
  1340. timeused = clock()-timeused;
  1341. if (!timeused) timeused++;
  1342. if (flags & F_VERBOSE) fprintf(VERBOSE_OUT,
  1343. "Compressed %d bytes in %4.2f seconds (%4.2f kB/sec)\n",
  1344. inlen,
  1345. (double)timeused/CLOCKS_PER_SEC,
  1346. (double)CLOCKS_PER_SEC*inlen/timeused/1024.0);
  1347. return 0;
  1348. }
  1349. if (indata) free(indata);
  1350. return n;
  1351. }