gtpack.c 71 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259
  1. /******************************************************************************
  2. *
  3. * A variant of ttpack designed to output XPak compressed data.
  4. *
  5. * -----------------------------------------------------------------------------
  6. *
  7. * original project name: TIGCC Tools Suite
  8. * file name: ttpack.c
  9. * initial date: 14/08/2000
  10. * authors: albert@cs.tut.fi
  11. * thomas.nussbaumer@gmx.net
  12. * Paul Froissart
  13. * description: packing program
  14. *
  15. * -----------------------------------------------------------------------------
  16. *
  17. * based on code from Pasi 'Albert' Ojala, albert@cs.tut.fi
  18. *
  19. * heavily reduced to fit to the needs by thomas.nussbaumer@gmx.net
  20. *
  21. * modified to fit XPak's compression format
  22. *
  23. ******************************************************************************/
  24. #include <stdio.h>
  25. #include <stdlib.h>
  26. #include <string.h>
  27. #include <math.h>
  28. #include <ctype.h>
  29. #include <time.h>
  30. //#define ONCALC_PACKER_EMU
  31. //#define EVEN_LZ // allow only LZ sequences with the same parity
  32. //#define NEW_RANGE // LZhuf-like range coding
  33. //#define X_STATS
  34. #define NO_XVERBOSE
  35. //#define ZRANGE
  36. //#define ZRANGE_FAST
  37. #include "tt.h" // generic defines
  38. #include "ttversion.h" // tigcc tools suite version info
  39. #include "revtools.h" // used for id displaying
  40. #include "ttunpack.h" // errorcodes definition
  41. #include "packhead.h" // compressed header definition
  42. #define CVS_FILE_REVISION "$Revision: 1.4 $"
  43. #define FIXF_MACHMASK 0xff
  44. #define FIXF_WRAP 256
  45. #define FIXF_DLZ 512
  46. #define F_VERBOSE (1<<0)
  47. #define F_STATS (1<<1)
  48. #define F_AUTO (1<<2)
  49. #define F_NOOPT (1<<3)
  50. #define F_AUTOEX (1<<4)
  51. #define F_TEXTINPUT (1<<5)
  52. #define F_TEXTOUTPUT (1<<6)
  53. #define F_NORLE (1<<9)
  54. #define F_ERROR (1<<15)
  55. #ifndef min
  56. #define min(a,b) ((a<b)?(a):(b))
  57. #endif
  58. #ifndef ONCALC_PACKER_EMU
  59. #define LRANGE (((2<<maxGamma)-3)*256) /* 0..125, 126 -> 1..127 */
  60. #else
  61. #define LRANGE 6144 /* packer() emulation */
  62. #endif
  63. #ifdef NEW_RANGE
  64. #undef LRANGE
  65. #define LRANGE 4096
  66. #endif
  67. #ifdef ZRANGE
  68. #undef LRANGE
  69. #define LRANGE 6144
  70. #endif
  71. #define MAXLZLEN (2<<maxGamma)
  72. #define MAXRLELEN (((2<<maxGamma)-2)*256) /* 0..126 -> 1..127 */
  73. #define DEFAULT_LZLEN LRANGE
  74. unsigned short *rle, *elr, *lzlen, *lzpos;
  75. unsigned short *lzlen2, *lzpos2;
  76. int *length, inlen;
  77. unsigned char *indata, *mode, *newesc;
  78. unsigned short *backSkip;
  79. enum MODE {
  80. LITERAL = 0,
  81. LZ77 = 1,
  82. RLE = 2,
  83. DLZ = 3,
  84. MMARK = 4
  85. };
  86. int lzopt = 0;
  87. int maxGamma = 7;
  88. int reservedBytes = 2;
  89. int escBits = 2;
  90. int escMask = 0xc0;
  91. int extraLZPosBits = 0;
  92. int rleUsed = 31;
  93. /*
  94. //=============================================================================
  95. // outputs usage information of this tool
  96. //=============================================================================
  97. void PrintUsage() {
  98. fprintf(stderr, "Usage: ttpack [-<flags>] <infile> <outfile>\n" \
  99. " -hti treat input as hex textinput\n" \
  100. " -hto generate hex textoutput\n" \
  101. " -fdelta use delta-lz77 -- shortens some files\n" \
  102. " e<val> force escape bits\n" \
  103. " r<val> restrict lz search range\n" \
  104. " n no RLE/LZ length optimization\n" \
  105. " s full statistics\n" \
  106. " v verbose\n" \
  107. " p<val> force extralzposbits\n" \
  108. " m<val> max len 5..7 (2*2^5..2*2^7)\n");
  109. }
  110. */
  111. /*
  112. //=============================================================================
  113. // the packing code
  114. //=============================================================================
  115. int SavePack(int flags,int type, unsigned char *data, int size, char *target,
  116. int start, int escape, unsigned char *rleValues,
  117. int endAddr, int extraLZPosBits,int memStart, int memEnd)
  118. {
  119. FILE *fp = NULL;
  120. int i;
  121. if (!data) return 10;
  122. if (!target) fp = stdout;
  123. if ((type & FIXF_MACHMASK) == 0) {
  124. // Save without decompressor
  125. if (fp || (fp = fopen(target, "wb"))) {
  126. PackedHeader cth;
  127. RLEEntries re;
  128. cth.origsize_lo = inlen & 0xff;
  129. cth.origsize_hi = (inlen >> 8);
  130. #ifndef COMPACT
  131. cth.magic1 = MAGIC_CHAR1;
  132. cth.magic2 = MAGIC_CHAR2;
  133. cth.compsize_lo = (size + rleUsed + sizeof(PackedHeader)) & 0xff;
  134. cth.compsize_hi = (size + rleUsed + sizeof(PackedHeader)) >> 8;
  135. #else
  136. #ifndef OLD_HDR
  137. memcpy(cth.magic,"GTPk",4);
  138. cth.compsize_lo = (size + rleUsed + sizeof(PackedHeader)) & 0xff;
  139. cth.compsize_hi = (size + rleUsed + sizeof(PackedHeader)) >> 8;
  140. #endif
  141. #endif
  142. cth.esc1 = (escape >> (8-escBits));
  143. //cth.notused3
  144. //cth.notused4
  145. cth.esc2 = escBits;
  146. #if !defined(COMPACT) || defined(OLD_HDR)
  147. cth.gamma1 = maxGamma + 1;
  148. cth.gamma2 = (1 << maxGamma);
  149. #endif
  150. cth.extralz = extraLZPosBits;
  151. //cth.notused1 = 0xff;
  152. //cth.notused2 = 0xff;
  153. cth.rleentries = rleUsed;
  154. for(i=0; i<rleUsed; i++) re.value[i] = rleValues[i+1];
  155. if (flags & F_TEXTOUTPUT) {
  156. unsigned int loop;
  157. unsigned int written=0;
  158. for (i=0;i<sizeof(PackedHeader);i++,written++) {
  159. fprintf(fp,"0x%02x,",*(((unsigned char*)&cth)+i));
  160. if ((!(written % DEFAULT_ITEMS_PER_LINE)) && written) fputc('\n',fp);
  161. }
  162. for (i=0;i<cth.rleentries;i++,written++) {
  163. fprintf(fp,"0x%02x,",re.value[i]);
  164. if (!(written % DEFAULT_ITEMS_PER_LINE)) fputc('\n',fp);
  165. }
  166. for (loop=0;loop < size;loop++,written++) {
  167. if (loop < size - 1) fprintf(fp,"0x%02x,",data[loop]);
  168. else fprintf(fp,"0x%02x",data[loop]);
  169. if (!(written % DEFAULT_ITEMS_PER_LINE)) fputc('\n',fp);
  170. }
  171. }
  172. else {
  173. fwrite(&cth, 1, sizeof(PackedHeader), fp); // write header
  174. fwrite(&re, 1, cth.rleentries, fp); // write rle values
  175. fwrite(data, size, 1, fp); // write compressed data
  176. if(fp != stdout) fclose(fp);
  177. }
  178. return 0;
  179. }
  180. fprintf(stderr, "Could not open %s for writing\n", target);
  181. return 10;
  182. }
  183. fprintf(stderr, "FATAL: invalid type!!\n");
  184. return 10;
  185. } */
  186. int lrange, maxlzlen, maxrlelen;
  187. #ifdef X_STATS
  188. #define OUT_SIZE (65536*10)
  189. #else
  190. #define OUT_SIZE 65536
  191. #endif
  192. unsigned char outBuffer[OUT_SIZE];
  193. int outPointer = 0;
  194. int bitMask = 0x80;
  195. //=============================================================================
  196. //
  197. //=============================================================================
  198. void FlushBits(void) {
  199. if (bitMask != 0x80) outPointer++;
  200. }
  201. //=============================================================================
  202. //
  203. //=============================================================================
  204. void PutBit(int bit) {
  205. if (bit && outPointer < OUT_SIZE) outBuffer[outPointer] |= bitMask;
  206. bitMask >>= 1;
  207. if (!bitMask) {
  208. #ifndef NO_XVERBOSE
  209. printf("[%02x]\n",(int)(unsigned char)outBuffer[outPointer]);
  210. #endif
  211. bitMask = 0x80;
  212. outPointer++;
  213. }
  214. }
  215. int lenValue[256];
  216. //--------------------------------------------
  217. // why not initializing value lenValue[0] ????
  218. //--------------------------------------------
  219. //=============================================================================
  220. //
  221. //=============================================================================
  222. #if K_GAMMA-1
  223. void InitValueLen() {
  224. int i,h;
  225. for (i=1; i<256; i++) {
  226. int count = 0;
  227. if (i<2) count = 0; /* 1 */
  228. else if (i<4) count = 1; /* 2-3 */
  229. else if (i<8) count = 2; /* 4-7 */
  230. else if (i<16) count = 3; /* 8-15 */
  231. else if (i<32) count = 4; /* 16-31 */
  232. else if (i<64) count = 5; /* 32-63 */
  233. else if (i<128) count = 6; /* 64-127 */
  234. else if (i<256) count = 7; /* 128-255 */
  235. // lenValue[i] = (count>>1)+count+2;
  236. switch (count) {
  237. case 0: h=1; break;
  238. case 1: if (i==2) h=1; else h=2; break;
  239. case 2: h=4; break;
  240. case 3: h=5; break;
  241. case 4: h=6; break;
  242. case 5: h=7; break;
  243. case 6: h=8; break;
  244. case 7: h=9; break;
  245. }
  246. lenValue[i]=h+count;
  247. }
  248. }
  249. #else
  250. void InitValueLen() {
  251. int i;
  252. // could be heavily optimized, but isn't necessary
  253. for (i=1; i<256; i++) {
  254. int count = 0;
  255. if (i<2) count = 0; /* 1 */
  256. else if (i<4) count = 1; /* 2-3 */
  257. else if (i<8) count = 2; /* 4-7 */
  258. else if (i<16) count = 3; /* 8-15 */
  259. else if (i<32) count = 4; /* 16-31 */
  260. else if (i<64) count = 5; /* 32-63 */
  261. else if (i<128) count = 6; /* 64-127 */
  262. else if (i<256) count = 7; /* 128-255 */
  263. lenValue[i] = 2*count;
  264. /*if (count<maxGamma)*/ lenValue[i]++;
  265. }
  266. }
  267. #endif
  268. #define LenValue(a) (lenValue[a])
  269. //=============================================================================
  270. //
  271. //=============================================================================
  272. void PutNBits(int byte, int bits) {
  273. while (bits--)
  274. PutBit((byte & (1<<bits)));
  275. }
  276. #if K_GAMMA-1
  277. static int stats[256];
  278. #endif
  279. //=============================================================================
  280. //
  281. //=============================================================================
  282. void PutValue(int value) {
  283. int bits = 0, count = 0;
  284. #if K_GAMMA-1
  285. stats[value]++;
  286. for (count=0;count<LenValue(value);count++) PutBit(0);
  287. #else
  288. while (value>1) {
  289. bits = (bits<<1) | (value & 1); /* is reversed compared to value */
  290. value >>= 1;
  291. count++;
  292. PutBit(1);
  293. }
  294. /*if (count<maxGamma)*/ PutBit(0);
  295. while (count--) {
  296. PutBit((bits & 1)); /* output is reversed again -> same as value */
  297. bits >>= 1;
  298. }
  299. #endif
  300. }
  301. #ifdef NEW_RANGE
  302. unsigned char p_len[64] = {
  303. 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  304. 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  305. 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  306. 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  307. 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  308. 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  309. 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  310. 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  311. };
  312. unsigned char p_code[64] = {
  313. 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  314. 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  315. 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  316. 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  317. 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  318. 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  319. 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  320. 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  321. };
  322. //=============================================================================
  323. //
  324. //=============================================================================
  325. void PutRange(int c) {
  326. int i;
  327. /* output upper 6 bits with encoding */
  328. i = c >> 6;
  329. PutNBits((unsigned)p_code[i] >> (8-p_len[i]), p_len[i]);
  330. /* output lower 6 bits directly */
  331. PutNBits((c & 0x3f), 6);
  332. }
  333. #endif
  334. int gainedEscaped = 0;
  335. int gainedRle = 0, gainedSRle = 0, gainedLRle = 0;
  336. int gainedLz = 0, gainedRlecode = 0;
  337. int gainedDLz = 0, timesDLz = 0;
  338. int timesEscaped = 0, timesNormal = 0;
  339. int timesRle = 0, timesSRle = 0, timesLRle = 0;
  340. int timesLz = 0;
  341. int lenStat[8][4];
  342. //0:
  343. //1:
  344. //2: SRLE
  345. //3: RLE byte
  346. //4:
  347. //=============================================================================
  348. //
  349. //=============================================================================
  350. int OutputNormal(int *esc, unsigned char *data, int newesc) {
  351. timesNormal++;
  352. if ((data[0] & escMask) == *esc) {
  353. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  354. PutBit(0);
  355. PutBit(1);
  356. PutBit(0);
  357. *esc = newesc;
  358. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  359. PutNBits(data[0], 8-escBits);
  360. gainedEscaped += escBits + 3;
  361. timesEscaped++;
  362. return 1;
  363. }
  364. PutNBits(data[0], 8);
  365. return 0;
  366. }
  367. //=============================================================================
  368. //
  369. //=============================================================================
  370. void OutputEof(int *esc) {
  371. /* EOF marker */
  372. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  373. PutValue(3); /* >2 */
  374. PutValue((2<<maxGamma)-1); /* Maximum value */
  375. FlushBits();
  376. }
  377. unsigned char rleValues[32] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  378. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  379. int rleHist[256];
  380. //=============================================================================
  381. //
  382. //=============================================================================
  383. int IsShortRleByte(int data) {
  384. int index;
  385. for (index = 1; index <= rleUsed; index++)
  386. if (data == rleValues[index])
  387. return 1;
  388. return 0;
  389. }
  390. void PutRleByte(int data) {
  391. int index;
  392. for (index = 1; index <= rleUsed; index++) {
  393. if (data == rleValues[index]) {
  394. if (index==1) lenStat[0][3]++;
  395. else if (index<=3) lenStat[1][3]++;
  396. else if (index<=7) lenStat[2][3]++;
  397. else if (index<=15) lenStat[3][3]++;
  398. else if (index<=31) lenStat[4][3]++;
  399. gainedRlecode += 8 - LenValue(index);
  400. PutValue(index);
  401. return;
  402. }
  403. }
  404. PutValue(32 + (data>>3));
  405. gainedRlecode -= LenValue(32+(data>>3)) + 3;
  406. PutNBits(data, 3);
  407. lenStat[5][3]++;
  408. }
  409. unsigned char rleLen[256];
  410. //=============================================================================
  411. //
  412. //=============================================================================
  413. void InitRleLen() {
  414. int i;
  415. for (i=0; i<256; i++) rleLen[i] = LenValue(32 + 0) + 3;
  416. for (i=1; i<32; i++) rleLen[rleValues[i]] = LenValue(i);
  417. }
  418. #define LenRleByte(d) (rleLen[d])
  419. //=============================================================================
  420. //
  421. //=============================================================================
  422. int LenRle(int len, int data) {
  423. int out = 0;
  424. do {
  425. if (len == 1) {
  426. out += escBits + 3 + 8;
  427. len = 0;
  428. }
  429. else if (len <= (1<<maxGamma)) {
  430. out += escBits + 3 + LenValue(len-1) + LenRleByte(data);
  431. len = 0;
  432. }
  433. else {
  434. int tmp = min(len, maxrlelen);
  435. out += escBits + 3 + maxGamma + 8 +
  436. LenValue(((tmp-1)>>8)+1) + LenRleByte(data);
  437. len -= tmp;
  438. }
  439. } while (len);
  440. return out;
  441. }
  442. //=============================================================================
  443. //
  444. //=============================================================================
  445. int OutputRle(int *esc, unsigned char *data, int rlelen) {
  446. int len = rlelen, tmp;
  447. while (len) {
  448. if (len >= 2 && len <= (1<<maxGamma) && (len >= 3 || IsShortRleByte(*data))) {
  449. /* Short RLE */
  450. if (len==2) lenStat[0][2]++;
  451. else if (len<=4) lenStat[1][2]++;
  452. else if (len<=8) lenStat[2][2]++;
  453. else if (len<=16) lenStat[3][2]++;
  454. else if (len<=32) lenStat[4][2]++;
  455. else if (len<=64) lenStat[5][2]++;
  456. else if (len<=128) lenStat[6][2]++;
  457. else if (len<=256) lenStat[6][2]++;
  458. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  459. PutBit(0);
  460. PutBit(1);
  461. PutBit(1);
  462. PutValue(len-1);
  463. PutRleByte(*data);
  464. tmp = 8*len -escBits -3 -LenValue(len-1) -LenRleByte(*data);
  465. gainedRle += tmp;
  466. gainedSRle += tmp;
  467. timesRle++;
  468. timesSRle++;
  469. return 0;
  470. }
  471. if (len<3) {
  472. while (len--)
  473. OutputNormal(esc, data, *esc);
  474. return 0;
  475. }
  476. if (len <= maxrlelen) {
  477. /* Run-length encoding */
  478. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  479. PutBit(0);
  480. PutBit(1);
  481. PutBit(1);
  482. PutValue((1<<maxGamma) + (((len-1)&0xff)>>(8-maxGamma)));
  483. PutNBits((len-1), 8-maxGamma);
  484. PutValue(((len-1)>>8) + 1);
  485. PutRleByte(*data);
  486. tmp = 8*len -escBits -3 -maxGamma -8 -LenValue(((len-1)>>8)+1)
  487. -LenRleByte(*data);
  488. gainedRle += tmp;
  489. gainedLRle += tmp;
  490. timesRle++;
  491. timesLRle++;
  492. return 0;
  493. }
  494. /* Run-length encoding */
  495. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  496. PutBit(0);
  497. PutBit(1);
  498. PutBit(1);
  499. PutValue((1<<maxGamma) + (((maxrlelen-1)&0xff)>>(8-maxGamma)));
  500. PutNBits((maxrlelen-1) & 0xff, 8-maxGamma);
  501. PutValue(((maxrlelen-1)>>8)+1);
  502. PutRleByte(*data);
  503. tmp = 8*maxrlelen -escBits -3 -maxGamma -8
  504. -LenValue(((maxrlelen-1)>>8)+1) -LenRleByte(*data);
  505. gainedRle += tmp;
  506. gainedLRle += tmp;
  507. timesRle++;
  508. timesLRle++;
  509. len -= maxrlelen;
  510. data += maxrlelen;
  511. }
  512. return 0;
  513. }
  514. #ifdef ZRANGE
  515. char zrlen[96]={
  516. 0,
  517. 2,2,2,2,
  518. 3,3,3,3,
  519. 4,4,4,4,4,4,4,4,
  520. 5,5,5,5,5,5,5,5,
  521. 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  522. 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  523. 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
  524. };
  525. #define ZrLen(p) (zrlen[((p)-1)>>6])
  526. #endif
  527. //=============================================================================
  528. //
  529. //=============================================================================
  530. int LenLz(int lzlen, int lzpos) {
  531. #ifdef EVEN_LZ
  532. if (lzpos&1) return 100000;
  533. #endif
  534. if (lzlen==2) {
  535. #if !defined(ZRANGE) || defined(ZRANGE_FAST)
  536. #ifdef EVEN_LZ
  537. if (lzpos <= 256) return escBits + 2 + 7;
  538. #else
  539. if (lzpos <= 256) return escBits + 2 + 8;
  540. #endif
  541. else return 100000;
  542. #else
  543. if (lzpos <= 64) return escBits + 2 + 7;
  544. else if (lzpos <= 128) return escBits + 2 + 8;
  545. else if (lzpos <= 256) return escBits + 2 + 9;
  546. else return 100000;
  547. #endif
  548. }
  549. #ifdef ZRANGE
  550. return escBits + 8 + ZrLen(lzpos) + LenValue(lzlen-1);
  551. #else
  552. #ifdef EVEN_LZ
  553. return escBits + 7 + extraLZPosBits +
  554. #else
  555. return escBits + 8 + extraLZPosBits +
  556. #endif
  557. LenValue(((lzpos-1)>>(8+extraLZPosBits))+1) +
  558. LenValue(lzlen-1);
  559. #endif
  560. }
  561. #ifdef X_STATS
  562. #define XS_NUM (LRANGE/64+1)
  563. int lzstats[16][XS_NUM];
  564. int lzstatlong[XS_NUM];
  565. #endif
  566. //=============================================================================
  567. //
  568. //=============================================================================
  569. int OutputLz(int *esc, int lzlen, int lzpos, char *data, int curpos) {
  570. #ifdef X_STATS
  571. if (lzlen<=16)
  572. lzstats[lzlen-1][(lzpos-1)>>6]++;
  573. else
  574. lzstatlong[(lzpos-1)>>6]++;
  575. #endif
  576. if (lzlen==2) lenStat[0][1]++;
  577. else if (lzlen<=4) lenStat[1][1]++;
  578. else if (lzlen<=8) lenStat[2][1]++;
  579. else if (lzlen<=16) lenStat[3][1]++;
  580. else if (lzlen<=32) lenStat[4][1]++;
  581. else if (lzlen<=64) lenStat[5][1]++;
  582. else if (lzlen<=128) lenStat[6][1]++;
  583. else if (lzlen<=256) lenStat[7][1]++;
  584. if (lzlen >= 2 && lzlen <= maxlzlen) {
  585. int tmp;
  586. PutNBits((*esc>>(8-escBits)), escBits); /* escBits>=0 */
  587. tmp = ((lzpos-1)>>(8+extraLZPosBits))+2;
  588. if (tmp==2) lenStat[0][0]++;
  589. else if (tmp<=4) lenStat[1][0]++;
  590. else if (tmp<=8) lenStat[2][0]++;
  591. else if (tmp<=16) lenStat[3][0]++;
  592. else if (tmp<=32) lenStat[4][0]++;
  593. else if (tmp<=64) lenStat[5][0]++;
  594. else if (tmp<=128) lenStat[6][0]++;
  595. else if (tmp<=256) lenStat[6][0]++;
  596. if (lzlen==2) {
  597. PutValue(lzlen-1);
  598. PutBit(0);
  599. if (lzpos > 256) fprintf(stderr,"Error at %d: lzpos too long (%d) for lzlen==2\n",curpos, lzpos);
  600. #ifdef ZRANGE
  601. #ifdef ZRANGE_FAST
  602. PutNBits(((lzpos-1) & 0xff) ^ 0xff, 8);
  603. #else
  604. {
  605. int x=lzpos-1;
  606. switch (x>>6) {
  607. case 0: PutNBits(x,7); break; // x=0b00****** => 0******
  608. case 1: PutNBits(x+64,8); break; // x=0b01****** => 10******
  609. case 2: PutNBits(x+256,9); break; // x=0b10****** => 110******
  610. case 3: PutNBits(x+256,9); break; // x=0b11****** => 111******
  611. }
  612. }
  613. #endif
  614. #endif
  615. }
  616. else {
  617. #ifdef ZRANGE
  618. PutValue(lzlen-1);
  619. /* PutNBits(0,ZrLen(lzpos));
  620. PutNBits(0,8);*/
  621. {
  622. int x=~(lzpos-1),u=(x+64)>>8;
  623. switch (ZrLen(lzpos)) {
  624. /*u=0*/ case 0: PutNBits(x,8); break;
  625. /*u=-1*/ case 2: PutNBits(0x1,2); PutNBits(x,8); break;
  626. /*u=-2*/ case 3: PutNBits(0x0,2); PutNBits(x,8); PutNBits(0x0,1); break;
  627. /*u=-4..-3*/ case 4: PutNBits(0x0,2); PutNBits(x,8); PutNBits(0x2+(u&1),2); break;
  628. /*u=-6..-5*/ case 5: PutNBits(0x2,2); PutNBits(x,8); PutNBits(0x0+(u&1),3); break;
  629. /*u=-12..-7*/ case 6: PutNBits(0x2,2); PutNBits(x,8); PutNBits(0x4+((u+(12&7))&7),4); break;
  630. /*u=-24..-13*/ case 7: PutNBits(0x2,2); PutNBits(x,8); PutNBits(0x14+((u+(24&15))&15),5); break;
  631. }
  632. }
  633. #else
  634. #ifdef X_STATS
  635. PutValue(lzlen-1);
  636. // PutNBits(0,1+3);
  637. PutNBits(0,3);
  638. #else
  639. PutValue(lzlen-1);
  640. #ifndef NEW_RANGE
  641. PutValue( ((lzpos-1) >> (8+extraLZPosBits)) +1);
  642. PutNBits( ((lzpos-1) >> 8), extraLZPosBits);
  643. #endif
  644. #endif
  645. #endif
  646. }
  647. // PutNBits(0xFF, 8);
  648. #ifndef ZRANGE
  649. #ifndef NEW_RANGE
  650. #ifdef EVEN_LZ
  651. PutNBits((((lzpos-1) & 0xff) ^ 0xff) >> 1, 7);
  652. if (lzpos&1) fprintf(stderr, "Error: odd lzpos\n");
  653. #else
  654. PutNBits(((lzpos-1) & 0xff) ^ 0xff, 8);
  655. #endif
  656. #else
  657. PutRange(lzpos-1);
  658. #endif
  659. #endif
  660. gainedLz += 8*lzlen -LenLz(lzlen, lzpos);
  661. timesLz++;
  662. return 3;
  663. }
  664. fprintf(stderr, "Error: lzlen too short/long (%d)\n", lzlen);
  665. return lzlen;
  666. }
  667. /* Non-recursive version */
  668. /* NOTE! IMPORTANT! the "length" array length must be inlen+1 */
  669. //=============================================================================
  670. //
  671. //=============================================================================
  672. int OptimizeLength(int optimize) {
  673. int i;
  674. length[inlen] = 0; /* one off the end, our 'target' */
  675. for (i=inlen-1; i>=0; i--) {
  676. int r1 = 8 + length[i+1], r2, r3;
  677. /* if (i<=0x40b1 && !(i&((1<<0)-1)))
  678. printf("");*/
  679. if (!lzlen[i] && !rle[i] && (!lzlen2 || !lzlen2[i])) {
  680. length[i] = r1;
  681. mode[i] = LITERAL;
  682. continue;
  683. }
  684. /* If rle>maxlzlen, skip to the start of the rle-maxlzlen.. */
  685. if (rle[i] > maxlzlen && elr[i] > 1) {
  686. int z = elr[i];
  687. i -= elr[i];
  688. r2 = LenRle(rle[i], indata[i]) + length[i+ rle[i]];
  689. if (optimize) {
  690. int ii, mini = rle[i], minv = r2;
  691. int bot = rle[i] - (1<<maxGamma);
  692. if (bot < 2)
  693. bot = 2;
  694. for (ii=mini-1; ii>=bot; ii--) {
  695. int v = LenRle(ii, indata[i]) + length[i + ii];
  696. if (v < minv) {
  697. minv = v;
  698. mini = ii;
  699. }
  700. }
  701. if (minv != r2) {
  702. lzopt += r2 - minv;
  703. rle[i] = mini;
  704. r2 = minv;
  705. }
  706. }
  707. length[i] = r2;
  708. mode[i] = RLE;
  709. for (; z>=0; z--) {
  710. length[i+z] = r2;
  711. mode[i+z] = RLE;
  712. }
  713. continue;
  714. }
  715. r3 = r2 = r1 + 1000; /* r3 >= r2 > r1 */
  716. if (rle[i]) {
  717. r2 = LenRle(rle[i], indata[i]) + length[i+ rle[i]];
  718. if (optimize) {
  719. int ii, mini = rle[i], minv = r2;
  720. /* Check only the original length and all shorter
  721. lengths that are power of two.
  722. Does not really miss many 'minimums' this way,
  723. at least not globally..
  724. Makes the assumption that the Elias Gamma Code is
  725. used, i.e. values of the form 2^n are 'optimal' */
  726. ii = 2;
  727. while (rle[i] > ii) {
  728. int v = LenRle(ii, indata[i]) + length[i + ii];
  729. if (v < minv) {
  730. minv = v;
  731. mini = ii;
  732. }
  733. ii <<= 1;
  734. }
  735. if (minv != r2) {
  736. lzopt += r2 - minv;
  737. rle[i] = mini;
  738. r2 = minv;
  739. }
  740. }
  741. }
  742. if (lzlen[i]) {
  743. r3 = LenLz(lzlen[i], lzpos[i]) + length[i + lzlen[i]];
  744. if (optimize && lzlen[i]>2) {
  745. int ii, mini = lzlen[i], minv = r3;
  746. int topLen = LenLz(lzlen[i], lzpos[i])
  747. - LenValue(lzlen[i]-1);
  748. /* Check only the original length and all shorter
  749. lengths that are power of two.
  750. Does not really miss many 'minimums' this way,
  751. at least not globally..
  752. Makes the assumption that the Elias Gamma Code is
  753. used, i.e. values of the form 2^n are 'optimal' */
  754. ii = 4;
  755. while (lzlen[i] > ii) {
  756. int v = topLen + LenValue(ii-1) + length[i + ii];
  757. if (v < minv) {
  758. minv = v;
  759. mini = ii;
  760. }
  761. ii <<= 1;
  762. }
  763. /*
  764. Note:
  765. 2-byte optimization checks are no longer done
  766. with the rest, because the equation gives too long
  767. code lengths for 2-byte matches if extraLzPosBits>0.
  768. */
  769. /* Two-byte rescan/check */
  770. if (backSkip[i] && backSkip[i] <= 256) {
  771. #ifdef EVEN_LZ
  772. if (backSkip[i]&1) {
  773. int j=backSkip[i];
  774. while (j && (j&1))
  775. j=backSkip[j];
  776. if (j && j<=256) {
  777. int v = LenLz(2, j) + length[i + 2];
  778. if (v < minv) {
  779. minv = v;
  780. mini = 2;
  781. lzlen[i] = mini;
  782. r3 = minv;
  783. lzpos[i] = j;
  784. }
  785. }
  786. } else {
  787. #endif
  788. /* There are previous occurrances (near enough) */
  789. int v = LenLz(2, (int)backSkip[i]) + length[i + 2];
  790. if (v < minv) {
  791. minv = v;
  792. mini = 2;
  793. lzlen[i] = mini;
  794. r3 = minv;
  795. lzpos[i] = (int)backSkip[i];
  796. }
  797. #ifdef EVEN_LZ
  798. }
  799. #endif
  800. }
  801. if (minv != r3 && minv < r2) {
  802. lzopt += r3 - minv;
  803. lzlen[i] = mini;
  804. r3 = minv;
  805. }
  806. }
  807. }
  808. if (r2 <= r1) {
  809. if (r2 <= r3) {
  810. length[i] = r2;
  811. mode[i] = RLE;
  812. }
  813. else {
  814. length[i] = r3;
  815. mode[i] = LZ77;
  816. }
  817. }
  818. else {
  819. if (r3 <= r1) {
  820. length[i] = r3;
  821. mode[i] = LZ77;
  822. }
  823. else {
  824. length[i] = r1;
  825. mode[i] = LITERAL;
  826. }
  827. }
  828. if (lzlen2 && lzlen2[i] > 3) {
  829. r3 = escBits + 2*maxGamma + 16 + LenValue(lzlen2[i]-1) + length[i + lzlen2[i]];
  830. //r3 = LenDLz(lzlen2[i], lzpos2[i]) + length[i + lzlen2[i]];
  831. if (r3 < length[i]) {
  832. length[i] = r3;
  833. mode[i] = DLZ;
  834. }
  835. }
  836. }
  837. return length[0];
  838. }
  839. /*
  840. The algorithm in the OptimizeEscape() works as follows:
  841. 1) Only unpacked bytes are processed, they are marked
  842. with MMARK. We proceed from the end to the beginning.
  843. Variable A (old/new length) is updated.
  844. 2) At each unpacked byte, one and only one possible
  845. escape matches. A new escape code must be selected
  846. for this case. The optimal selection is the one which
  847. provides the shortest number of escapes to the end
  848. of the file,
  849. i.e. A[esc] = 1+min(A[0], A[1], .. A[states-1]).
  850. For other states A[esc] = A[esc];
  851. If we change escape in this byte, the new escape is
  852. the one with the smallest value in A.
  853. 3) The starting escape is selected from the possibilities
  854. and mode 0 is restored to all mode 3 locations.
  855. */
  856. //=============================================================================
  857. //
  858. //=============================================================================
  859. int OptimizeEscape(int *startEscape, int *nonNormal) {
  860. int i, /*j,*/ states = (1<<escBits);
  861. long other = 0;
  862. long a[256]; /* needs int/long */
  863. long b[256]; /* Remembers the # of escaped for each */
  864. int esc8 = 8-escBits;
  865. for (i=0; i<256; i++) b[i] = a[i] = -1;
  866. if (states>256) {
  867. fprintf(stderr, "Escape optimize: only 256 states (%d)!\n",states);
  868. return 0;
  869. }
  870. /* Mark those bytes that are actually outputted */
  871. for (i=0; i<inlen; ) {
  872. switch (mode[i]) {
  873. case DLZ:
  874. other++;
  875. i += lzlen2[i];
  876. break;
  877. case LZ77:
  878. other++;
  879. i += lzlen[i];
  880. break;
  881. case RLE:
  882. other++;
  883. i += rle[i];
  884. break;
  885. /*case LITERAL:*/
  886. default:
  887. mode[i++] = MMARK; /* mark it used so we can identify it */
  888. break;
  889. }
  890. }
  891. #ifdef WEIRD_ORIGINAL_ESC
  892. /* note : this ESC control is OK, but doesn't comply with on-calc GTPk */
  893. for (i=inlen-1; i>=0; i--) {
  894. /* Using a table to skip non-normal bytes does not help.. */
  895. if (mode[i] == MMARK) {
  896. int k = (indata[i] >> esc8);
  897. /* Change the tag values back to normal */
  898. mode[i] = LITERAL;
  899. /*
  900. k are the matching bytes,
  901. minv is the minimum value,
  902. minp is the minimum index
  903. */
  904. newesc[i] = (minp << esc8);
  905. a[k] = minv + 1;
  906. b[k] = b[minp] + 1;
  907. if (k==minp) {
  908. /* Minimum changed -> need to find a new minimum */
  909. /* a[k] may still be the minimum */
  910. minv++;
  911. for (k=states-1; k>=0; k--) {
  912. if (a[k] < minv) {
  913. minv = a[k];
  914. minp = k;
  915. /*
  916. There may be others, but the first one that
  917. is smaller than the old minimum is equal to
  918. any other new minimum.
  919. */
  920. break;
  921. }
  922. }
  923. }
  924. }
  925. }
  926. /* Select the best value for the initial escape */
  927. if (startEscape) {
  928. i = inlen; /* make it big enough */
  929. for (j=states-1; j>=0; j--) {
  930. if (a[j] <= i) {
  931. *startEscape = (j << esc8);
  932. i = a[j];
  933. }
  934. }
  935. }
  936. if (nonNormal)
  937. *nonNormal = other;
  938. return b[startEscape ? (*startEscape>>esc8) : 0];
  939. #else
  940. {
  941. /* this fairly simple (but efficient) algo comes from GTPk */
  942. char esc_used[256];
  943. int esc_rem=states-1;
  944. int lastesc=-1,escaped=0;
  945. int k;
  946. memset(esc_used,0,256);
  947. for (i=0; i<inlen; i++) {
  948. if (mode[i] == MMARK) {
  949. k = (indata[i] >> esc8);
  950. mode[i] = LITERAL;
  951. if (!esc_used[k] && !esc_rem--) {
  952. memset(esc_used,0,256);
  953. esc_rem=states-1;
  954. escaped++;
  955. if (lastesc>=0) newesc[lastesc] = (k << esc8);
  956. else if (startEscape) *startEscape = (k << esc8);
  957. lastesc=i;
  958. } else {
  959. esc_used[k]=1;
  960. }
  961. }
  962. }
  963. for (k=0;;k++) {
  964. if (!esc_used[k]) {
  965. if (lastesc>=0) newesc[lastesc] = (k << esc8);
  966. else if (startEscape) *startEscape = (k << esc8);
  967. break;
  968. }
  969. }
  970. newesc[0] = *startEscape;
  971. if (nonNormal)
  972. *nonNormal = other;
  973. return escaped;
  974. }
  975. #endif
  976. }
  977. //=============================================================================
  978. // Initialize the RLE byte code table according to all RLE's found so far O(n)
  979. //=============================================================================
  980. void InitRle(int flags) {
  981. int p, mr, mv, i;
  982. for (i=1; i<32; i++) {
  983. mr = -1;
  984. mv = 0;
  985. for (p=0; p<256; p++) {
  986. if (rleHist[p] > mv) {
  987. mv = rleHist[p];
  988. mr = p;
  989. }
  990. }
  991. if (mr>=0) {
  992. rleValues[i] = mr;
  993. rleHist[mr] = -1;
  994. } else
  995. break;
  996. }
  997. InitRleLen();
  998. }
  999. //=============================================================================
  1000. // Initialize the RLE byte code table according to RLE's actually used O(n)
  1001. //=============================================================================
  1002. void OptimizeRle(int flags) {
  1003. int p, mr, mv, i;
  1004. if ((flags & F_NORLE)) {
  1005. rleUsed = 0;
  1006. return;
  1007. }
  1008. if (flags & F_STATS) fprintf(stderr, "RLE Byte Code Re-Tune, RLE Ranks:\n");
  1009. for (p=0; p<256; p++) rleHist[p] = 0;
  1010. for (p=0; p<inlen; ) {
  1011. switch (mode[p]) {
  1012. case DLZ:
  1013. p += lzlen2[p];
  1014. break;
  1015. case LZ77:
  1016. p += lzlen[p];
  1017. break;
  1018. case RLE:
  1019. rleHist[indata[p]]++;
  1020. p += rle[p];
  1021. break;
  1022. default:
  1023. p++;
  1024. break;
  1025. }
  1026. }
  1027. for (i=1; i<32; i++) {
  1028. mr = -1;
  1029. // mv = 0;
  1030. // mv = (LenValue(i)+8 <= 14)?0:1;
  1031. mv = 1;
  1032. for (p=0; p<256; p++) {
  1033. if (rleHist[p] > mv) {
  1034. mv = rleHist[p];
  1035. mr = p;
  1036. }
  1037. }
  1038. if (mr>=0) {
  1039. rleValues[i] = mr;
  1040. if (flags & F_STATS) {
  1041. fprintf(stderr, " %2d.0x%02x %-3d ", i, mr, mv);
  1042. if (!((i - 1) % 6)) fprintf(stderr, "\n");
  1043. }
  1044. rleHist[mr] = -1;
  1045. }
  1046. else {
  1047. break;
  1048. }
  1049. }
  1050. rleUsed = i-1;
  1051. if (rleUsed)
  1052. for (;i<32;i++)
  1053. rleValues[i]=rleValues[i-1];
  1054. if (flags & F_STATS)
  1055. if (((i - 1) % 6)!=1) fprintf(stderr, "\n");
  1056. InitRleLen();
  1057. }
  1058. int outlen;
  1059. //=============================================================================
  1060. //
  1061. //=============================================================================
  1062. int PackLz77(int lzsz, int flags, int *startEscape,int endAddr, int memEnd, int type)
  1063. {
  1064. int i, j, p, headerSize;
  1065. int escape;
  1066. unsigned char *hashValue;
  1067. unsigned char *a;
  1068. int k;
  1069. unsigned short *lastPair;
  1070. int rescan = 0;
  1071. #ifndef NO_XVERBOSE
  1072. int vescape;
  1073. #endif
  1074. if (lzsz < 0 || lzsz > lrange) {
  1075. fprintf(stderr, "LZ range must be from 0 to %d (was %d). Set to %d.\n",
  1076. lrange, lzsz, lrange);
  1077. lzsz = lrange;
  1078. }
  1079. if (lzsz > 65535) {
  1080. fprintf(stderr,
  1081. "LZ range must be from 0 to 65535 (was %d). Set to 65535.\n",
  1082. lzsz);
  1083. lzsz = 65535;
  1084. }
  1085. if (!lzsz) fprintf(stderr, "Warning: zero LZ range. Only RLE packing used.\n");
  1086. InitRleLen();
  1087. length = (int *)calloc(sizeof(int), inlen + 1);
  1088. mode = (unsigned char *)calloc(sizeof(unsigned char), inlen);
  1089. rle = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  1090. elr = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  1091. lzlen = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  1092. lzpos = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  1093. if ((type & FIXF_DLZ)) {
  1094. lzlen2 = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  1095. lzpos2 = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  1096. }
  1097. else {
  1098. lzlen2 = lzpos2 = NULL;
  1099. }
  1100. newesc = (unsigned char *)calloc(sizeof(unsigned char), inlen);
  1101. backSkip = (unsigned short *)calloc(sizeof(unsigned short), inlen);
  1102. hashValue = (unsigned char *)malloc(inlen);
  1103. lastPair = (unsigned short *)calloc(sizeof(unsigned short), 256*256);
  1104. /* error checking */
  1105. if (!length || !mode || !rle || !elr || !lzlen || !lzpos || !newesc ||
  1106. !lastPair || !backSkip
  1107. || ((type & FIXF_DLZ) && (!lzlen2 || !lzpos2))
  1108. || !hashValue)
  1109. {
  1110. fprintf(stderr, "Memory allocation failed!\n");
  1111. goto errorexit;
  1112. }
  1113. i = 0;
  1114. j = 0;
  1115. a = indata + inlen;
  1116. for (p=inlen-1; p>=0; p--) {
  1117. k = j;
  1118. j = i;
  1119. i = *--a; /* Only one read per position */
  1120. hashValue[p] = i*3 + j*5 + k*7; /* 7.95 % */
  1121. }
  1122. /* Detect all RLE and LZ77 jump possibilities */
  1123. for (p=0; p<inlen; p++) {
  1124. if (!(p & 2047)) {
  1125. fprintf(stderr, "\r%d ", p);
  1126. fflush(stderr); /* for SAS/C */
  1127. }
  1128. /* check run-length code - must be done, LZ77 search needs it! */
  1129. if (rle[p] <= 0) {
  1130. unsigned char *a = indata + p;
  1131. int val = *a++; /* if this were uchar, it would go to stack..*/
  1132. int top = inlen - p;
  1133. int rlelen = 1;
  1134. /* Loop for the whole RLE */
  1135. while (rlelen<top && *a++ == (unsigned char)val) rlelen++;
  1136. if (rlelen>=2) {
  1137. rleHist[indata[p]]++;
  1138. for (i=rlelen-1; i>=0; i--) {
  1139. rle[p+i] = rlelen-i;
  1140. elr[p+i] = i; /* For RLE backward skipping */
  1141. }
  1142. }
  1143. }
  1144. /* check LZ77 code */
  1145. if (p+rle[p]+1<inlen) {
  1146. int bot = p - lzsz, maxval, maxpos, rlep = rle[p];
  1147. unsigned char hashCompare = hashValue[p];
  1148. /*
  1149. There's always 1 equal byte, although it may
  1150. not be marked as RLE.
  1151. */
  1152. if (rlep <= 0)
  1153. rlep = 1;
  1154. if (bot < 0)
  1155. bot = 0;
  1156. bot += (rlep-1);
  1157. /*
  1158. First get the shortest possible match (if any).
  1159. If there is no 2-byte match, don't look further,
  1160. because there can't be a longer match.
  1161. */
  1162. i = (int)lastPair[ (indata[p]<<8) | indata[p+1] ] -1;
  1163. if (i>=0 && i>=bot) {
  1164. /* Got a 2-byte match at least */
  1165. maxval = 2;
  1166. maxpos = p-i;
  1167. /*
  1168. A..AB rlep # of A's, B is something else..
  1169. Search for bytes that are in p + (rlep-1), i.e.
  1170. the last rle byte ('A') and the non-matching one
  1171. ('B'). When found, check if the rle in the compare
  1172. position (i) is long enough (i.e. the same number
  1173. of A's at p and i-rlep+1).
  1174. There are dramatically less matches for AB than for
  1175. AA, so we get a huge speedup with this approach.
  1176. We are still guaranteed to find the most recent
  1177. longest match there is.
  1178. */
  1179. i = (int)lastPair[(indata[p+(rlep-1)]<<8) | indata[p+rlep]] -1;
  1180. while (i>=bot /* && i>=rlep-1 */) { /* bot>=rlep-1, i>=bot ==> i>=rlep-1 */
  1181. /* Equal number of A's ? */
  1182. if (!(rlep-1) || rle[i-(rlep-1)]==rlep) { /* 'head' matches */
  1183. /* rlep==1 ==> (rlep-1)==0 */
  1184. /* ivanova.run: 443517 rlep==1,
  1185. 709846 rle[i+1-rlep]==rlep */
  1186. /*
  1187. Check the hash values corresponding to the last
  1188. two bytes of the currently longest match and
  1189. the first new matching(?) byte. If the hash
  1190. values don't match, don't bother to check the
  1191. data itself.
  1192. */
  1193. if (
  1194. hashValue[i+maxval-rlep-1] == hashCompare
  1195. ) {
  1196. unsigned char *a = indata + i+2; /* match */
  1197. unsigned char *b = indata + p+rlep-1+2;/* curpos */
  1198. int topindex = inlen-(p+rlep-1);
  1199. /* the 2 first bytes ARE the same.. */
  1200. j = 2;
  1201. while (j < topindex && *a++==*b++)
  1202. j++;
  1203. if (j + rlep-1 > maxval) {
  1204. int tmplen = j+rlep-1, tmppos = p-i+rlep-1;
  1205. if (tmplen > maxlzlen)
  1206. tmplen = maxlzlen;
  1207. /* Accept only versions that really are shorter */
  1208. if (tmplen*8 - LenLz(tmplen, tmppos) >
  1209. maxval*8 - LenLz(maxval, maxpos)) {
  1210. maxval = tmplen;
  1211. maxpos = tmppos;
  1212. hashCompare = hashValue[p+maxval-2];
  1213. }
  1214. if (maxval == maxlzlen)
  1215. break;
  1216. }
  1217. }
  1218. }
  1219. if (!backSkip[i])
  1220. break; /* No previous occurrances (near enough) */
  1221. i -= (int)backSkip[i];
  1222. }
  1223. /*
  1224. If there is 'A' in the previous position also,
  1225. RLE-like LZ77 is possible, although rarely
  1226. shorter than real RLE.
  1227. */
  1228. if (p && rle[p-1] > maxval) {
  1229. maxval = rle[p-1] - 1;
  1230. maxpos = 1;
  1231. }
  1232. /*
  1233. Last, try to find as long as possible match
  1234. for the RLE part only.
  1235. */
  1236. if (maxval < maxlzlen && rlep > maxval) {
  1237. bot = p - lzsz;
  1238. if (bot < 0)
  1239. bot = 0;
  1240. /* Note: indata[p] == indata[p+1] */
  1241. i = (int)lastPair[indata[p]*257] -1;
  1242. while (/* i>= rlep-2 &&*/ i>=bot) {
  1243. if (elr[i] + 2 > maxval) {
  1244. maxval = min(elr[i] + 2, rlep);
  1245. maxpos = p - i + (maxval-2);
  1246. if(maxval == rlep)
  1247. break; /* Got enough */
  1248. }
  1249. i -= elr[i];
  1250. if (!backSkip[i])
  1251. break; /* No previous occurrances (near enough) */
  1252. i -= (int)backSkip[i];
  1253. }
  1254. }
  1255. if (p+maxval > inlen) {
  1256. fprintf(stderr,"Error @ %d, lzlen %d, pos %d - exceeds inlen\n",p, maxval, maxpos);
  1257. maxval = inlen - p;
  1258. }
  1259. if (maxpos<=256 || maxval > 2) {
  1260. if (maxpos < 0) fprintf(stderr, "Error @ %d, lzlen %d, pos %d\n",p, maxval, maxpos);
  1261. lzlen[p] = (maxval<maxlzlen)?maxval:maxlzlen;
  1262. /*#ifdef EVEN_LZ
  1263. if (maxpos&1)
  1264. fprintf(stderr,"Error: misalign in maxpos\n");
  1265. #endif*/
  1266. lzpos[p] = maxpos;
  1267. }
  1268. }
  1269. }
  1270. /* check LZ77 code again, ROT1..255 */
  1271. if ((type & FIXF_DLZ) && p+rle[p]+1<inlen) {
  1272. int rot;
  1273. for (rot = 1; rot < 255; rot++) {
  1274. int bot = p - /*lzsz*/256, maxval, maxpos, rlep = rle[p];
  1275. unsigned char valueCompare = (indata[p+2] + rot) & 0xff;
  1276. if (rlep <= 0) rlep = 1;
  1277. if (bot < 0) bot = 0;
  1278. bot += (rlep-1);
  1279. i = (int)lastPair[ (((indata[p] + rot) & 0xff)<<8) |
  1280. ((indata[p+1] + rot) & 0xff) ] -1;
  1281. if (i>=0 && i>=bot) {
  1282. maxval = 2;
  1283. maxpos = p-i;
  1284. /*
  1285. A..AB rlep # of A's, B is something else..
  1286. Search for bytes that are in p + (rlep-1), i.e.
  1287. the last rle byte ('A') and the non-matching one
  1288. ('B'). When found, check if the rle in the compare
  1289. position (i) is long enough (i.e. the same number
  1290. of A's at p and i-rlep+1).
  1291. There are dramatically less matches for AB than for
  1292. AA, so we get a huge speedup with this approach.
  1293. We are still guaranteed to find the most recent
  1294. longest match there is.
  1295. */
  1296. i = (int)lastPair[(((indata[p+(rlep-1)] + rot) & 0xff)<<8) |
  1297. ((indata[p+rlep] + rot) & 0xff)] -1;
  1298. while (i>=bot /* && i>=rlep-1 */) { /* bot>=rlep-1, i>=bot ==> i>=rlep-1 */
  1299. /* Equal number of A's ? */
  1300. if (!(rlep-1) || rle[i-(rlep-1)]==rlep) { /* 'head' matches */
  1301. /* rlep==1 ==> (rlep-1)==0 */
  1302. /* ivanova.run: 443517 rlep==1,
  1303. 709846 rle[i+1-rlep]==rlep */
  1304. /*
  1305. Check the hash values corresponding to the last
  1306. two bytes of the currently longest match and
  1307. the first new matching(?) byte. If the hash
  1308. values don't match, don't bother to check the
  1309. data itself.
  1310. */
  1311. if (indata[i+maxval-rlep+1] == valueCompare) {
  1312. unsigned char *a = indata + i+2; /* match */
  1313. unsigned char *b = indata + p+rlep-1+2;/* curpos */
  1314. int topindex = inlen-(p+rlep-1);
  1315. /* the 2 first bytes ARE the same.. */
  1316. j = 2;
  1317. while (j < topindex && *a++==((*b++ + rot) & 0xff))
  1318. j++;
  1319. if (j + rlep-1 > maxval) {
  1320. int tmplen = j+rlep-1, tmppos = p-i+rlep-1;
  1321. if (tmplen > maxlzlen)
  1322. tmplen = maxlzlen;
  1323. /* Accept only versions that really are shorter */
  1324. if (tmplen*8 - LenLz(tmplen, tmppos) >
  1325. maxval*8 - LenLz(maxval, maxpos)) {
  1326. maxval = tmplen;
  1327. maxpos = tmppos;
  1328. valueCompare = (indata[p+maxval] + rot) & 0xff;
  1329. }
  1330. if (maxval == maxlzlen)
  1331. break;
  1332. }
  1333. }
  1334. }
  1335. if (!backSkip[i])
  1336. break; /* No previous occurrances (near enough) */
  1337. i -= (int)backSkip[i];
  1338. }
  1339. if (p+maxval > inlen) {
  1340. fprintf(stderr,"Error @ %d, lzlen %d, pos %d - exceeds inlen\n",p, maxval, maxpos);
  1341. maxval = inlen - p;
  1342. }
  1343. if (maxval > 3 && maxpos <= 256 &&
  1344. (maxval > lzlen2[p] ||
  1345. (maxval == lzlen2[p] && maxpos < lzpos2[p]))) {
  1346. if (maxpos < 0)
  1347. fprintf(stderr, "Error @ %d, lzlen %d, pos %d\n",p, maxval, maxpos);
  1348. lzlen2[p] = (maxval<maxlzlen)?maxval:maxlzlen;
  1349. lzpos2[p] = maxpos;
  1350. }
  1351. }
  1352. }
  1353. if (lzlen2[p] <= lzlen[p] || lzlen2[p] <= rle[p]) {
  1354. lzlen2[p] = lzpos2[p] = 0;
  1355. }
  1356. }
  1357. /* Update the two-byte history ('hash table') &
  1358. backSkip ('linked list') */
  1359. if (p+1<inlen) {
  1360. int index = (indata[p]<<8) | indata[p+1];
  1361. int ptr = p - (lastPair[index]-1);
  1362. if (ptr > p || ptr > 0xffff)
  1363. ptr = 0;
  1364. backSkip[p] = ptr;
  1365. lastPair[index] = p+1;
  1366. }
  1367. }
  1368. if ((flags & F_NORLE)) {
  1369. for (p=1; p<inlen; p++) {
  1370. if (rle[p-1]-1 > lzlen[p]) {
  1371. lzlen[p] = (rle[p]<maxlzlen)?rle[p]:maxlzlen;
  1372. lzpos[p] = 1;
  1373. }
  1374. }
  1375. for (p=0; p<inlen; p++) {
  1376. rle[p] = 0;
  1377. }
  1378. }
  1379. fprintf(stderr, "\r \r"); /* clean up the display */
  1380. fflush(stderr);
  1381. /* fprintf(stderr, "\rChecked: %d \n", p);
  1382. fflush(stderr); */
  1383. /* Initialize the RLE selections */
  1384. InitRle(flags);
  1385. /* Check the normal bytes / all ratio */
  1386. if ((flags & F_AUTO)) {
  1387. int mb, mv;
  1388. if (flags & F_VERBOSE) {
  1389. fprintf(stderr, "Selecting the number of escape bits.. ");
  1390. fflush(stderr);
  1391. }
  1392. /*
  1393. Absolute maximum number of escaped bytes with
  1394. the escape optimize is 2^-n, where n is the
  1395. number of escape bits used.
  1396. This worst case happens only on equal-
  1397. distributed normal bytes (01230123..).
  1398. This is why the typical values are so much smaller.
  1399. */
  1400. mb = 0;
  1401. mv = 8*OUT_SIZE;
  1402. for (escBits=1; escBits<9; escBits++) {
  1403. int escaped, other = 0, c;
  1404. escMask = (0xff00>>escBits) & 0xff;
  1405. /* Find the optimum path for selected escape bits (no optimize) */
  1406. OptimizeLength(0);
  1407. /* Optimize the escape selections for this path & escBits */
  1408. escaped = OptimizeEscape(&escape, &other);
  1409. /* Compare value: bits lost for escaping -- bits lost for prefix */
  1410. c = (escBits+3)*escaped + other*escBits;
  1411. if (flags & F_STATS) {
  1412. fprintf(stderr, " %d:%d", escBits, c);
  1413. fflush(stderr); /* for SAS/C */
  1414. }
  1415. if (c < mv) {
  1416. mb = escBits;
  1417. mv = c;
  1418. } else {
  1419. /* minimum found */
  1420. break;
  1421. }
  1422. if (escBits==4 && (flags & F_STATS)) fprintf(stderr, "\n");
  1423. }
  1424. if (mb==1) { /* Minimum was 1, check 0 */
  1425. int escaped;
  1426. escBits = 0;
  1427. escMask = 0;
  1428. /* Find the optimum path for selected escape bits (no optimize) */
  1429. OptimizeLength(0);
  1430. /* Optimize the escape selections for this path & escBits */
  1431. escaped = OptimizeEscape(&escape, NULL);
  1432. if ((flags & F_STATS)) {
  1433. fprintf(stderr, " %d:%d", escBits, 3*escaped);
  1434. fflush(stderr); /* for SAS/C */
  1435. }
  1436. if (3*escaped < mv) {
  1437. mb = 0;
  1438. /* mv = 3*escaped; */
  1439. }
  1440. }
  1441. if ((flags & F_STATS)) fprintf(stderr, "\n");
  1442. if (flags & F_VERBOSE) fprintf(stderr, "Selected %d-bit escapes\n", mb);
  1443. escBits = mb;
  1444. escMask = (0xff00>>escBits) & 0xff;
  1445. }
  1446. if (!(flags & F_NOOPT)) {
  1447. if (flags & F_VERBOSE) {
  1448. fprintf(stderr, "Optimizing LZ77 and RLE lengths...");
  1449. fflush(stderr);
  1450. }
  1451. }
  1452. /* Find the optimum path (optimize) */
  1453. OptimizeLength((flags & F_NOOPT)?0:1);
  1454. if (flags & F_STATS) {
  1455. if (!(flags & F_NOOPT)) fprintf(stderr, " gained %d units.\n", lzopt/8);
  1456. }
  1457. else {
  1458. //fprintf(stderr, "\n");
  1459. }
  1460. if (1 || (flags & F_AUTOEX)) {
  1461. long lzstat[5] = {0,0,0,0,0}, i, cur = 0, old = extraLZPosBits;
  1462. if (flags & F_VERBOSE) {
  1463. fprintf(stderr, "Selecting LZPOS LO length.. ");
  1464. fflush(stderr);
  1465. }
  1466. for (p=0; p<inlen; ) {
  1467. switch (mode[p]) {
  1468. case LZ77:
  1469. extraLZPosBits = 0;
  1470. lzstat[0] += LenLz(lzlen[p], lzpos[p]);
  1471. extraLZPosBits = 1;
  1472. lzstat[1] += LenLz(lzlen[p], lzpos[p]);
  1473. extraLZPosBits = 2;
  1474. lzstat[2] += LenLz(lzlen[p], lzpos[p]);
  1475. extraLZPosBits = 3;
  1476. lzstat[3] += LenLz(lzlen[p], lzpos[p]);
  1477. extraLZPosBits = 4;
  1478. lzstat[4] += LenLz(lzlen[p], lzpos[p]);
  1479. p += lzlen[p];
  1480. break;
  1481. case DLZ:
  1482. p += lzlen2[p];
  1483. break;
  1484. case RLE:
  1485. p += rle[p];
  1486. break;
  1487. default:
  1488. p++;
  1489. break;
  1490. }
  1491. }
  1492. for (i=0; i<5; i++) {
  1493. if (flags & F_STATS) fprintf(stderr, " %ld:%ld", i + 8, lzstat[i]);
  1494. if (lzstat[i] < lzstat[cur]) cur = i;
  1495. }
  1496. extraLZPosBits = (flags & F_AUTOEX)?cur:old;
  1497. if (flags & F_STATS) fprintf(stderr, "\n");
  1498. if (flags & F_VERBOSE) {
  1499. fprintf(stderr, "Selected %d-bit LZPOS LO part\n",extraLZPosBits + 8);
  1500. if (cur != old) fprintf(stderr,"Note: Using option -p%ld you may get better results.\n",cur);
  1501. }
  1502. /* Find the optimum path (optimize) */
  1503. if (extraLZPosBits != old) OptimizeLength((flags & F_NOOPT)?0:1);
  1504. }
  1505. if (1) {
  1506. long stat[4] = {0,0,0,0};
  1507. for (p=0; p<inlen; ) {
  1508. switch (mode[p]) {
  1509. case LZ77:
  1510. if ((lzpos[p] >> 8)+1 > (1<<maxGamma))
  1511. stat[3]++;
  1512. if (lzlen[p] > (1<<maxGamma))
  1513. stat[0]++;
  1514. p += lzlen[p];
  1515. break;
  1516. case RLE:
  1517. if (rle[p] > (1<<(maxGamma-1))) {
  1518. if (rle[p] <= (1<<maxGamma))
  1519. stat[1]++;
  1520. }
  1521. p += rle[p];
  1522. break;
  1523. case DLZ:
  1524. p += lzlen2[p];
  1525. break;
  1526. default:
  1527. p++;
  1528. break;
  1529. }
  1530. }
  1531. /* TODO: better formula.. */
  1532. if (maxGamma < 7 && stat[0] + stat[1] + stat[3] > 10) {
  1533. if (flags & F_VERBOSE) fprintf(stderr,"Note: Using option -m%d you may get better results.\n",maxGamma+1);
  1534. }
  1535. if (maxGamma > 5 && stat[0] + stat[1] + stat[3] < 4) {
  1536. if (flags & F_VERBOSE) fprintf(stderr,"Note: Using option -m%d you may get better results.\n",maxGamma-1);
  1537. }
  1538. }
  1539. /* Optimize the escape selections */
  1540. OptimizeEscape(&escape, NULL);
  1541. if (startEscape) *startEscape = escape;
  1542. OptimizeRle(flags); /* Retune the RLE selections */
  1543. #ifdef NO_XVERBOSE
  1544. if (flags & F_VERBOSE) {
  1545. int oldEscape = escape;
  1546. if (flags & F_VERBOSE) printf("normal RLE LZLEN LZPOS(absolute)\n\n");
  1547. for (p=0; p<inlen; ) {
  1548. switch (mode[p]) {
  1549. case LZ77:
  1550. mode[p - lzpos[p]] |= MMARK; /* Was referred to by lz77 */
  1551. p += lzlen[p];
  1552. break;
  1553. case RLE:
  1554. p += rle[p];
  1555. break;
  1556. case DLZ:
  1557. mode[p - lzpos2[p]] |= MMARK; /* Was referred to by lz77 */
  1558. p += lzlen2[p];
  1559. break;
  1560. /* case LITERAL:
  1561. case MMARK:*/
  1562. default:
  1563. p++;
  1564. break;
  1565. }
  1566. }
  1567. j = 0;
  1568. for (p=0; p<inlen; p++) {
  1569. switch (mode[p]) {
  1570. case MMARK | DLZ:
  1571. case DLZ:
  1572. if (j==p) {
  1573. if (flags & F_VERBOSE) printf(">");
  1574. j += lzlen2[p];
  1575. } else
  1576. printf(" ");
  1577. if (lzpos2) {
  1578. if (flags & F_VERBOSE) printf(" %04x*%03d*+%02x", lzpos2[p], lzlen2[p],(indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1579. }
  1580. if (flags & F_VERBOSE) printf(" 001 %03d %03d %04x(%04x) %02x %s\n",
  1581. rle[p],lzlen[p],lzpos[p],p-lzpos[p],indata[p],
  1582. (mode[p] & MMARK)?"#":" ");
  1583. break;
  1584. case MMARK | LITERAL:
  1585. case LITERAL:
  1586. if (flags & F_VERBOSE) {
  1587. if (j==p) printf(">");
  1588. else printf(" ");
  1589. if (lzpos2) {
  1590. printf(" %04x %03d +%02x", lzpos2[p], lzlen2[p],
  1591. (indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1592. }
  1593. }
  1594. if (j==p) {
  1595. if (flags & F_VERBOSE) {
  1596. printf("*001* %03d %03d %04x(%04x) %02x %s %02x",
  1597. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1598. (mode[p] & MMARK)?"#":" ", newesc[p]);
  1599. }
  1600. if ((indata[p] & escMask) == escape) {
  1601. escape = newesc[p];
  1602. if (flags & F_VERBOSE) printf("«");
  1603. }
  1604. if (flags & F_VERBOSE) printf("\n");
  1605. j += 1;
  1606. } else {
  1607. if (flags & F_VERBOSE) printf("*001* %03d %03d %04x(%04x) %02x %s %02x\n",
  1608. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1609. (mode[p] & MMARK)?"#":" ", newesc[p]);
  1610. }
  1611. break;
  1612. case MMARK | LZ77:
  1613. case LZ77:
  1614. if (j==p) {
  1615. if (flags & F_VERBOSE) printf(">");
  1616. j += lzlen[p];
  1617. } else
  1618. if (flags & F_VERBOSE) printf(" ");
  1619. if (lzpos2) {
  1620. if (flags & F_VERBOSE) printf(" %04x %03d +%02x", lzpos2[p], lzlen2[p],
  1621. (indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1622. }
  1623. if (flags & F_VERBOSE) printf(" 001 %03d *%03d* %04x(%04x) %02x %s\n",
  1624. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1625. (mode[p] & MMARK)?"#":" ");
  1626. break;
  1627. case MMARK | RLE:
  1628. case RLE:
  1629. if (j==p) {
  1630. if (flags & F_VERBOSE) printf(">");
  1631. j += rle[p];
  1632. } else
  1633. if (flags & F_VERBOSE) printf(" ");
  1634. if (lzpos2) {
  1635. if (flags & F_VERBOSE) printf(" %04x %03d +%02x", lzpos2[p], lzlen2[p],
  1636. (indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1637. }
  1638. if (flags & F_VERBOSE) printf(" 001 *%03d* %03d %04x(%04x) %02x %s\n",
  1639. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1640. (mode[p] & MMARK)?"#":" ");
  1641. break;
  1642. default:
  1643. j++;
  1644. break;
  1645. }
  1646. mode[p] &= ~MMARK;
  1647. }
  1648. escape = oldEscape;
  1649. }
  1650. #endif
  1651. #ifndef NO_XVERBOSE
  1652. if (flags & F_VERBOSE) {
  1653. for (p=0; p<inlen; ) {
  1654. switch (mode[p]) {
  1655. case LZ77:
  1656. mode[p - lzpos[p]] |= MMARK; /* Was referred to by lz77 */
  1657. p += lzlen[p];
  1658. break;
  1659. case RLE:
  1660. p += rle[p];
  1661. break;
  1662. case DLZ:
  1663. mode[p - lzpos2[p]] |= MMARK; /* Was referred to by lz77 */
  1664. p += lzlen2[p];
  1665. break;
  1666. /* case LITERAL:
  1667. case MMARK:*/
  1668. default:
  1669. p++;
  1670. break;
  1671. }
  1672. }
  1673. j = 0;
  1674. vescape=escape;
  1675. }
  1676. #endif
  1677. for (p=0; p<inlen; ) {
  1678. #ifndef NO_XVERBOSE
  1679. if (flags & F_VERBOSE) {
  1680. switch (mode[p]) {
  1681. case MMARK | DLZ:
  1682. case DLZ:
  1683. if (j==p) {
  1684. if (flags & F_VERBOSE) printf(">");
  1685. j += lzlen2[p];
  1686. } else
  1687. printf(" ");
  1688. if (lzpos2) {
  1689. if (flags & F_VERBOSE) printf(" %04x*%03d*+%02x", lzpos2[p], lzlen2[p],(indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1690. }
  1691. if (flags & F_VERBOSE) printf(" 001 %03d %03d %04x(%04x) %02x %s\n",
  1692. rle[p],lzlen[p],lzpos[p],p-lzpos[p],indata[p],
  1693. (mode[p] & MMARK)?"#":" ");
  1694. break;
  1695. case MMARK | LITERAL:
  1696. case LITERAL:
  1697. if (flags & F_VERBOSE) {
  1698. if (j==p) printf(">");
  1699. else printf(" ");
  1700. if (lzpos2) {
  1701. printf(" %04x %03d +%02x", lzpos2[p], lzlen2[p],
  1702. (indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1703. }
  1704. }
  1705. if (j==p) {
  1706. if (flags & F_VERBOSE) {
  1707. printf("*001* %03d %03d %04x(%04x) %02x %s %02x",
  1708. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1709. (mode[p] & MMARK)?"#":" ", newesc[p]);
  1710. }
  1711. if ((indata[p] & escMask) == vescape) {
  1712. vescape = newesc[p];
  1713. if (flags & F_VERBOSE) printf("«");
  1714. }
  1715. if (flags & F_VERBOSE) printf("\n");
  1716. j += 1;
  1717. } else {
  1718. if (flags & F_VERBOSE) printf("*001* %03d %03d %04x(%04x) %02x %s %02x\n",
  1719. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1720. (mode[p] & MMARK)?"#":" ", newesc[p]);
  1721. }
  1722. break;
  1723. case MMARK | LZ77:
  1724. case LZ77:
  1725. if (j==p) {
  1726. if (flags & F_VERBOSE) printf(">");
  1727. j += lzlen[p];
  1728. } else
  1729. if (flags & F_VERBOSE) printf(" ");
  1730. if (lzpos2) {
  1731. if (flags & F_VERBOSE) printf(" %04x %03d +%02x", lzpos2[p], lzlen2[p],
  1732. (indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1733. }
  1734. if (flags & F_VERBOSE) printf(" 001 %03d *%03d* %04x(%04x) %02x %s\n",
  1735. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1736. (mode[p] & MMARK)?"#":" ");
  1737. break;
  1738. case MMARK | RLE:
  1739. case RLE:
  1740. if (j==p) {
  1741. if (flags & F_VERBOSE) printf(">");
  1742. j += rle[p];
  1743. } else
  1744. if (flags & F_VERBOSE) printf(" ");
  1745. if (lzpos2) {
  1746. if (flags & F_VERBOSE) printf(" %04x %03d +%02x", lzpos2[p], lzlen2[p],
  1747. (indata[p] - indata[p-lzpos2[p]]) & 0xff);
  1748. }
  1749. if (flags & F_VERBOSE) printf(" 001 *%03d* %03d %04x(%04x) %02x %s\n",
  1750. rle[p], lzlen[p], lzpos[p], p-lzpos[p], indata[p],
  1751. (mode[p] & MMARK)?"#":" ");
  1752. break;
  1753. default:
  1754. j++;
  1755. break;
  1756. }
  1757. mode[p] &= ~MMARK;
  1758. }
  1759. #endif
  1760. switch (mode[p]) {
  1761. case LITERAL: /* normal */
  1762. length[p] = outPointer;
  1763. OutputNormal(&escape, indata+p, newesc[p]);
  1764. p++;
  1765. break;
  1766. case DLZ:
  1767. for (i=0; i<lzlen2[p]; i++) length[p+i] = outPointer;
  1768. PutNBits((escape>>(8-escBits)), escBits);
  1769. PutValue(lzlen2[p]-1);
  1770. PutValue((2<<maxGamma)-1);
  1771. PutNBits((indata[p] - indata[p-lzpos2[p]]) & 0xff, 8);
  1772. PutNBits(((lzpos2[p]-1) & 0xff) ^ 0xff, 8);
  1773. gainedDLz += 8*lzlen2[p] -(escBits + LenValue(lzlen2[p]-1) + 2*maxGamma + 16);
  1774. timesDLz++;
  1775. p += lzlen2[p];
  1776. break;
  1777. case LZ77: /* lz77 */
  1778. /* Not possible for smaller backSkip table
  1779. (the table is overwritten during previous use) */
  1780. /* Re-search matches to get the closest one */
  1781. if (lzopt && lzlen[p] > 2 && lzlen[p] > rle[p]) {
  1782. int bot = p - lzpos[p] + 1, i;
  1783. unsigned short rlep = rle[p];
  1784. if (!rlep)
  1785. rlep = 1;
  1786. if (bot < 0)
  1787. bot = 0;
  1788. bot += (rlep-1);
  1789. i = p - (int)backSkip[p];
  1790. while (i>=bot /* && i>=rlep-1 */) {
  1791. /* Equal number of A's ? */
  1792. if (rlep==1 || rle[i-rlep+1]==rlep) { /* 'head' matches */
  1793. unsigned char *a = indata + i+1; /* match */
  1794. unsigned char *b = indata + p+rlep-1+1; /* curpos */
  1795. int topindex = inlen-(p+rlep-1);
  1796. j = 1;
  1797. while (j < topindex && *a++==*b++)
  1798. j++;
  1799. if (j + rlep-1 >= lzlen[p]) {
  1800. int tmppos = p-i+rlep-1;
  1801. #ifdef EVEN_LZ
  1802. if (!(tmppos&1)) {
  1803. #endif
  1804. rescan +=
  1805. LenLz(lzlen[p], lzpos[p]) -
  1806. LenLz(lzlen[p], tmppos);
  1807. #ifdef EVEN_LZ
  1808. if (tmppos&1)
  1809. fprintf(stderr,"Error: misalign in tmppos\n");
  1810. #endif
  1811. lzpos[p] = tmppos;
  1812. break;
  1813. #ifdef EVEN_LZ
  1814. }
  1815. #endif
  1816. }
  1817. }
  1818. if (!backSkip[i])
  1819. break; /* No previous occurrances (near enough) */
  1820. i -= (int)backSkip[i];
  1821. }
  1822. }
  1823. for (i=0; i<lzlen[p]; i++)
  1824. length[p+i] = outPointer;
  1825. OutputLz(&escape, lzlen[p], lzpos[p], indata+p-lzpos[p], p);
  1826. p += lzlen[p];
  1827. break;
  1828. case RLE: /* rle */
  1829. for (i=0; i<rle[p]; i++)
  1830. length[p+i] = outPointer;
  1831. OutputRle(&escape, indata+p, rle[p]);
  1832. p += rle[p];
  1833. break;
  1834. default: /* Error Flynn :-) */
  1835. p++;
  1836. fprintf(stderr, "Internal error: mode %d\n", mode[p]);
  1837. break;
  1838. }
  1839. }
  1840. OutputEof(&escape);
  1841. i = inlen;
  1842. for (p=0; p<inlen; p++) {
  1843. int pos = (inlen - outPointer) + (int)length[p] - p;
  1844. i = min(i, pos);
  1845. }
  1846. if (i<0)
  1847. reservedBytes = -i + 2;
  1848. else
  1849. reservedBytes = 0;
  1850. headerSize = sizeof(PackedHeader) + rleUsed;
  1851. outlen = outPointer; /* we don't count the header... */
  1852. errorexit:
  1853. if (rle) free(rle);
  1854. if (elr) free(elr);
  1855. if (lzlen) free(lzlen);
  1856. if (lzpos) free(lzpos);
  1857. if (length) free(length);
  1858. if (mode) free(mode);
  1859. if (newesc) free(newesc);
  1860. if (lastPair) free(lastPair);
  1861. if (backSkip) free(backSkip);
  1862. if (hashValue) free(hashValue);
  1863. return 0;
  1864. }
  1865. #define NO_HEX_CHARACTER 255
  1866. //=============================================================================
  1867. // converts hexdigit to number
  1868. //=============================================================================
  1869. unsigned char hex2int(unsigned char c) {
  1870. c = tolower(c);
  1871. if (c >= 'a' && c <= 'f') return c - 'a' + 10;
  1872. if (c >= '0' && c <= '9') return c - '0';
  1873. return NO_HEX_CHARACTER;
  1874. }
  1875. //=============================================================================
  1876. // converts hex text into binary
  1877. //=============================================================================
  1878. int ConvertText2Bin(unsigned char* ib,int origlen) {
  1879. int pos;
  1880. int cnt = 0;
  1881. int searchforendofline = 0;
  1882. int len_after_convert = 0;
  1883. unsigned char val = 0;
  1884. unsigned char actual;
  1885. len_after_convert = 0;
  1886. for (pos = 0; pos < origlen;pos++) {
  1887. if (searchforendofline) {
  1888. if (ib[pos] == '\n') searchforendofline = 0;
  1889. continue;
  1890. }
  1891. if (ib[pos] == '/') {
  1892. cnt = 0;
  1893. if (pos < origlen-1 && ib[pos+1] == '/') searchforendofline = 1;
  1894. continue;
  1895. }
  1896. actual = hex2int(ib[pos]);
  1897. if (actual == NO_HEX_CHARACTER) {
  1898. cnt = 0;
  1899. continue;
  1900. }
  1901. if (cnt == 0) {
  1902. val = actual*16;
  1903. cnt++;
  1904. }
  1905. else {
  1906. val += actual;
  1907. cnt=0;
  1908. ib[len_after_convert++] = val;
  1909. }
  1910. }
  1911. return(len_after_convert);
  1912. }
  1913. void *GTPackDo(void *buf,unsigned short *buflen) {
  1914. int startEscape;
  1915. char *ptr;
  1916. // unsigned long timeused = clock();
  1917. lrange = LRANGE;
  1918. maxlzlen = MAXLZLEN;
  1919. maxrlelen = MAXRLELEN;
  1920. InitValueLen();
  1921. indata = buf;
  1922. inlen = *buflen;
  1923. PackLz77(lrange, F_AUTO|F_AUTOEX, &startEscape, 1234, 12345, 0);
  1924. free(indata);
  1925. {
  1926. int i;
  1927. PackedHeader cth;
  1928. RLEEntries re;
  1929. cth.origsize_lo = inlen & 0xff;
  1930. cth.origsize_hi = (inlen >> 8);
  1931. memcpy(cth.magic,"GTPk",4);
  1932. cth.compsize_lo = (outlen + rleUsed + sizeof(PackedHeader)) & 0xff;
  1933. cth.compsize_hi = (outlen + rleUsed + sizeof(PackedHeader)) >> 8;
  1934. cth.esc1 = (startEscape >> (8-escBits));
  1935. cth.esc2 = escBits;
  1936. cth.extralz = extraLZPosBits;
  1937. cth.rleentries = rleUsed;
  1938. for(i=0; i<rleUsed; i++) re.value[i] = rleValues[i+1];
  1939. indata = malloc((*buflen=sizeof(PackedHeader)+cth.rleentries+outlen));
  1940. ptr = indata;
  1941. memcpy(ptr, &cth, sizeof(PackedHeader)), ptr+=sizeof(PackedHeader);
  1942. memcpy(ptr, &re, cth.rleentries), ptr+=cth.rleentries;
  1943. memcpy(ptr, outBuffer, outlen), ptr+=outlen;
  1944. }
  1945. return indata;
  1946. }
  1947. //#############################################################################
  1948. //###################### NO MORE FAKES BEYOND THIS LINE #######################
  1949. //#############################################################################
  1950. //
  1951. //=============================================================================
  1952. // Revision History
  1953. //=============================================================================
  1954. //
  1955. // $Log: ttpack.c,v $
  1956. // Revision 1.5 2005/08/04 21:27:43 Paul Froissart
  1957. // adapted for XPak
  1958. //
  1959. // Revision 1.4 2000/08/23 20:10:56 Thomas Nussbaumer
  1960. // header corrected
  1961. //
  1962. // Revision 1.3 2000/08/23 20:10:17 Thomas Nussbaumer
  1963. // adapted to automatic version display (revtools.h)
  1964. //
  1965. // Revision 1.2 2000/08/20 15:30:11 Thomas Nussbaumer
  1966. // minor correction of header
  1967. //
  1968. // Revision 1.1 2000/08/16 23:05:59 Thomas Nussbaumer
  1969. // initial version
  1970. //
  1971. //