fastlz.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556
  1. /*
  2. FastLZ - lightning-fast lossless compression library
  3. Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
  4. Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
  5. Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
  6. Permission is hereby granted, free of charge, to any person obtaining a copy
  7. of this software and associated documentation files (the "Software"), to deal
  8. in the Software without restriction, including without limitation the rights
  9. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10. copies of the Software, and to permit persons to whom the Software is
  11. furnished to do so, subject to the following conditions:
  12. The above copyright notice and this permission notice shall be included in
  13. all copies or substantial portions of the Software.
  14. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15. IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16. FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17. AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18. LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19. OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20. THE SOFTWARE.
  21. */
  22. #if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
  23. /*
  24. * Always check for bound when decompressing.
  25. * Generally it is best to leave it defined.
  26. */
  27. #define FASTLZ_SAFE
  28. /*
  29. * Give hints to the compiler for branch prediction optimization.
  30. */
  31. #if defined(__GNUC__) && (__GNUC__ > 2)
  32. #define FASTLZ_EXPECT_CONDITIONAL(c) (__builtin_expect((c), 1))
  33. #define FASTLZ_UNEXPECT_CONDITIONAL(c) (__builtin_expect((c), 0))
  34. #else
  35. #define FASTLZ_EXPECT_CONDITIONAL(c) (c)
  36. #define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
  37. #endif
  38. /*
  39. * Use inlined functions for supported systems.
  40. */
  41. #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
  42. #define FASTLZ_INLINE inline
  43. #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
  44. #define FASTLZ_INLINE __inline
  45. #else
  46. #define FASTLZ_INLINE
  47. #endif
  48. /*
  49. * Prevent accessing more than 8-bit at once, except on x86 architectures.
  50. */
  51. #if !defined(FASTLZ_STRICT_ALIGN)
  52. #define FASTLZ_STRICT_ALIGN
  53. #if defined(__i386__) || defined(__386) /* GNU C, Sun Studio */
  54. #undef FASTLZ_STRICT_ALIGN
  55. #elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
  56. #undef FASTLZ_STRICT_ALIGN
  57. #elif defined(_M_IX86) /* Intel, MSVC */
  58. #undef FASTLZ_STRICT_ALIGN
  59. #elif defined(__386)
  60. #undef FASTLZ_STRICT_ALIGN
  61. #elif defined(_X86_) /* MinGW */
  62. #undef FASTLZ_STRICT_ALIGN
  63. #elif defined(__I86__) /* Digital Mars */
  64. #undef FASTLZ_STRICT_ALIGN
  65. #endif
  66. #endif
  67. /*
  68. * FIXME: use preprocessor magic to set this on different platforms!
  69. */
  70. typedef unsigned char flzuint8;
  71. typedef unsigned short flzuint16;
  72. typedef unsigned int flzuint32;
  73. /* Disable "conversion from A to B, possible loss of data" warning when using MSVC */
  74. #if defined(_MSC_VER)
  75. #pragma warning(disable: 4244)
  76. #endif
  77. /* prototypes */
  78. int fastlz_compress(const void* input, int length, void* output);
  79. int fastlz_compress_level(int level, const void* input, int length, void* output);
  80. int fastlz_decompress(const void* input, int length, void* output, int maxout);
  81. #define MAX_COPY 32
  82. #define MAX_LEN 264 /* 256 + 8 */
  83. #define MAX_DISTANCE 8192
  84. #if !defined(FASTLZ_STRICT_ALIGN)
  85. #define FASTLZ_READU16(p) *((const flzuint16*)(p))
  86. #else
  87. #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
  88. #endif
  89. #define HASH_LOG 13
  90. #define HASH_SIZE (1<< HASH_LOG)
  91. #define HASH_MASK (HASH_SIZE-1)
  92. #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
  93. #undef FASTLZ_LEVEL
  94. #define FASTLZ_LEVEL 1
  95. #undef FASTLZ_COMPRESSOR
  96. #undef FASTLZ_DECOMPRESSOR
  97. #define FASTLZ_COMPRESSOR fastlz1_compress
  98. #define FASTLZ_DECOMPRESSOR fastlz1_decompress
  99. static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
  100. static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
  101. #include "fastlz.c"
  102. #undef FASTLZ_LEVEL
  103. #define FASTLZ_LEVEL 2
  104. #undef MAX_DISTANCE
  105. #define MAX_DISTANCE 8191
  106. #define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
  107. #undef FASTLZ_COMPRESSOR
  108. #undef FASTLZ_DECOMPRESSOR
  109. #define FASTLZ_COMPRESSOR fastlz2_compress
  110. #define FASTLZ_DECOMPRESSOR fastlz2_decompress
  111. static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
  112. static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
  113. #include "fastlz.c"
  114. int fastlz_compress(const void* input, int length, void* output)
  115. {
  116. /* for short block, choose fastlz1 */
  117. if(length < 65536)
  118. return fastlz1_compress(input, length, output);
  119. /* else... */
  120. return fastlz2_compress(input, length, output);
  121. }
  122. int fastlz_decompress(const void* input, int length, void* output, int maxout)
  123. {
  124. /* magic identifier for compression level */
  125. int level = ((*(const flzuint8*)input) >> 5) + 1;
  126. if(level == 1)
  127. return fastlz1_decompress(input, length, output, maxout);
  128. if(level == 2)
  129. return fastlz2_decompress(input, length, output, maxout);
  130. /* unknown level, trigger error */
  131. return 0;
  132. }
  133. int fastlz_compress_level(int level, const void* input, int length, void* output)
  134. {
  135. if(level == 1)
  136. return fastlz1_compress(input, length, output);
  137. if(level == 2)
  138. return fastlz2_compress(input, length, output);
  139. return 0;
  140. }
  141. #else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
  142. static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
  143. {
  144. const flzuint8* ip = (const flzuint8*) input;
  145. const flzuint8* ip_bound = ip + length - 2;
  146. const flzuint8* ip_limit = ip + length - 12;
  147. flzuint8* op = (flzuint8*) output;
  148. const flzuint8* htab[HASH_SIZE];
  149. const flzuint8** hslot;
  150. flzuint32 hval;
  151. flzuint32 copy;
  152. /* sanity check */
  153. if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
  154. {
  155. if(length)
  156. {
  157. /* create literal copy only */
  158. *op++ = length-1;
  159. ip_bound++;
  160. while(ip <= ip_bound)
  161. *op++ = *ip++;
  162. return length+1;
  163. }
  164. else
  165. return 0;
  166. }
  167. /* initializes hash table */
  168. for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
  169. *hslot = ip;
  170. /* we start with literal copy */
  171. copy = 2;
  172. *op++ = MAX_COPY-1;
  173. *op++ = *ip++;
  174. *op++ = *ip++;
  175. /* main loop */
  176. while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
  177. {
  178. const flzuint8* ref;
  179. flzuint32 distance;
  180. /* minimum match length */
  181. flzuint32 len = 3;
  182. /* comparison starting-point */
  183. const flzuint8* anchor = ip;
  184. /* check for a run */
  185. #if FASTLZ_LEVEL==2
  186. if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
  187. {
  188. distance = 1;
  189. ip += 3;
  190. ref = anchor - 1 + 3;
  191. goto match;
  192. }
  193. #endif
  194. /* find potential match */
  195. HASH_FUNCTION(hval,ip);
  196. hslot = htab + hval;
  197. ref = htab[hval];
  198. /* calculate distance to the match */
  199. distance = anchor - ref;
  200. /* update hash table */
  201. *hslot = anchor;
  202. /* is this a match? check the first 3 bytes */
  203. if(distance==0 ||
  204. #if FASTLZ_LEVEL==1
  205. (distance >= MAX_DISTANCE) ||
  206. #else
  207. (distance >= MAX_FARDISTANCE) ||
  208. #endif
  209. *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
  210. goto literal;
  211. #if FASTLZ_LEVEL==2
  212. /* far, needs at least 5-byte match */
  213. if(distance >= MAX_DISTANCE)
  214. {
  215. if(*ip++ != *ref++ || *ip++!= *ref++)
  216. goto literal;
  217. len += 2;
  218. }
  219. match:
  220. #endif
  221. /* last matched byte */
  222. ip = anchor + len;
  223. /* distance is biased */
  224. distance--;
  225. if(!distance)
  226. {
  227. /* zero distance means a run */
  228. flzuint8 x = ip[-1];
  229. while(ip < ip_bound)
  230. if(*ref++ != x) break; else ip++;
  231. }
  232. else
  233. for(;;)
  234. {
  235. /* safe because the outer check against ip limit */
  236. if(*ref++ != *ip++) break;
  237. if(*ref++ != *ip++) break;
  238. if(*ref++ != *ip++) break;
  239. if(*ref++ != *ip++) break;
  240. if(*ref++ != *ip++) break;
  241. if(*ref++ != *ip++) break;
  242. if(*ref++ != *ip++) break;
  243. if(*ref++ != *ip++) break;
  244. while(ip < ip_bound)
  245. if(*ref++ != *ip++) break;
  246. break;
  247. }
  248. /* if we have copied something, adjust the copy count */
  249. if(copy)
  250. /* copy is biased, '0' means 1 byte copy */
  251. *(op-copy-1) = copy-1;
  252. else
  253. /* back, to overwrite the copy count */
  254. op--;
  255. /* reset literal counter */
  256. copy = 0;
  257. /* length is biased, '1' means a match of 3 bytes */
  258. ip -= 3;
  259. len = ip - anchor;
  260. /* encode the match */
  261. #if FASTLZ_LEVEL==2
  262. if(distance < MAX_DISTANCE)
  263. {
  264. if(len < 7)
  265. {
  266. *op++ = (len << 5) + (distance >> 8);
  267. *op++ = (distance & 255);
  268. }
  269. else
  270. {
  271. *op++ = (7 << 5) + (distance >> 8);
  272. for(len-=7; len >= 255; len-= 255)
  273. *op++ = 255;
  274. *op++ = len;
  275. *op++ = (distance & 255);
  276. }
  277. }
  278. else
  279. {
  280. /* far away, but not yet in the another galaxy... */
  281. if(len < 7)
  282. {
  283. distance -= MAX_DISTANCE;
  284. *op++ = (len << 5) + 31;
  285. *op++ = 255;
  286. *op++ = distance >> 8;
  287. *op++ = distance & 255;
  288. }
  289. else
  290. {
  291. distance -= MAX_DISTANCE;
  292. *op++ = (7 << 5) + 31;
  293. for(len-=7; len >= 255; len-= 255)
  294. *op++ = 255;
  295. *op++ = len;
  296. *op++ = 255;
  297. *op++ = distance >> 8;
  298. *op++ = distance & 255;
  299. }
  300. }
  301. #else
  302. if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
  303. while(len > MAX_LEN-2)
  304. {
  305. *op++ = (7 << 5) + (distance >> 8);
  306. *op++ = MAX_LEN - 2 - 7 -2;
  307. *op++ = (distance & 255);
  308. len -= MAX_LEN-2;
  309. }
  310. if(len < 7)
  311. {
  312. *op++ = (len << 5) + (distance >> 8);
  313. *op++ = (distance & 255);
  314. }
  315. else
  316. {
  317. *op++ = (7 << 5) + (distance >> 8);
  318. *op++ = len - 7;
  319. *op++ = (distance & 255);
  320. }
  321. #endif
  322. /* update the hash at match boundary */
  323. HASH_FUNCTION(hval,ip);
  324. htab[hval] = ip++;
  325. HASH_FUNCTION(hval,ip);
  326. htab[hval] = ip++;
  327. /* assuming literal copy */
  328. *op++ = MAX_COPY-1;
  329. continue;
  330. literal:
  331. *op++ = *anchor++;
  332. ip = anchor;
  333. copy++;
  334. if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
  335. {
  336. copy = 0;
  337. *op++ = MAX_COPY-1;
  338. }
  339. }
  340. /* left-over as literal copy */
  341. ip_bound++;
  342. while(ip <= ip_bound)
  343. {
  344. *op++ = *ip++;
  345. copy++;
  346. if(copy == MAX_COPY)
  347. {
  348. copy = 0;
  349. *op++ = MAX_COPY-1;
  350. }
  351. }
  352. /* if we have copied something, adjust the copy length */
  353. if(copy)
  354. *(op-copy-1) = copy-1;
  355. else
  356. op--;
  357. #if FASTLZ_LEVEL==2
  358. /* marker for fastlz2 */
  359. *(flzuint8*)output |= (1 << 5);
  360. #endif
  361. return op - (flzuint8*)output;
  362. }
  363. static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
  364. {
  365. const flzuint8* ip = (const flzuint8*) input;
  366. const flzuint8* ip_limit = ip + length;
  367. flzuint8* op = (flzuint8*) output;
  368. flzuint8* op_limit = op + maxout;
  369. flzuint32 ctrl = (*ip++) & 31;
  370. int loop = 1;
  371. do
  372. {
  373. const flzuint8* ref = op;
  374. flzuint32 len = ctrl >> 5;
  375. flzuint32 ofs = (ctrl & 31) << 8;
  376. if(ctrl >= 32)
  377. {
  378. #if FASTLZ_LEVEL==2
  379. flzuint8 code;
  380. #endif
  381. len--;
  382. ref -= ofs;
  383. if (len == 7-1)
  384. #if FASTLZ_LEVEL==1
  385. len += *ip++;
  386. ref -= *ip++;
  387. #else
  388. do
  389. {
  390. code = *ip++;
  391. len += code;
  392. } while (code==255);
  393. code = *ip++;
  394. ref -= code;
  395. /* match from 16-bit distance */
  396. if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
  397. if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
  398. {
  399. ofs = (*ip++) << 8;
  400. ofs += *ip++;
  401. ref = op - ofs - MAX_DISTANCE;
  402. }
  403. #endif
  404. #ifdef FASTLZ_SAFE
  405. if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
  406. return 0;
  407. if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
  408. return 0;
  409. #endif
  410. if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
  411. ctrl = *ip++;
  412. else
  413. loop = 0;
  414. if(ref == op)
  415. {
  416. /* optimize copy for a run */
  417. flzuint8 b = ref[-1];
  418. *op++ = b;
  419. *op++ = b;
  420. *op++ = b;
  421. for(; len; --len)
  422. *op++ = b;
  423. }
  424. else
  425. {
  426. #if !defined(FASTLZ_STRICT_ALIGN)
  427. const flzuint16* p;
  428. flzuint16* q;
  429. #endif
  430. /* copy from reference */
  431. ref--;
  432. *op++ = *ref++;
  433. *op++ = *ref++;
  434. *op++ = *ref++;
  435. #if !defined(FASTLZ_STRICT_ALIGN)
  436. /* copy a byte, so that now it's word aligned */
  437. if(len & 1)
  438. {
  439. *op++ = *ref++;
  440. len--;
  441. }
  442. /* copy 16-bit at once */
  443. q = (flzuint16*) op;
  444. op += len;
  445. p = (const flzuint16*) ref;
  446. for(len>>=1; len > 4; len-=4)
  447. {
  448. *q++ = *p++;
  449. *q++ = *p++;
  450. *q++ = *p++;
  451. *q++ = *p++;
  452. }
  453. for(; len; --len)
  454. *q++ = *p++;
  455. #else
  456. for(; len; --len)
  457. *op++ = *ref++;
  458. #endif
  459. }
  460. }
  461. else
  462. {
  463. ctrl++;
  464. #ifdef FASTLZ_SAFE
  465. if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
  466. return 0;
  467. if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
  468. return 0;
  469. #endif
  470. *op++ = *ip++;
  471. for(--ctrl; ctrl; ctrl--)
  472. *op++ = *ip++;
  473. loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
  474. if(loop)
  475. ctrl = *ip++;
  476. }
  477. }
  478. while(FASTLZ_EXPECT_CONDITIONAL(loop));
  479. return op - (flzuint8*)output;
  480. }
  481. #endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */