fastlz.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479
  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. /*
  23. * Give hints to the compiler for branch prediction optimization.
  24. */
  25. #if defined(__GNUC__) && (__GNUC__ > 2)
  26. #define FASTLZ_EXPECT_CONDITIONAL(c) (__builtin_expect((c), 1))
  27. #define FASTLZ_UNEXPECT_CONDITIONAL(c) (__builtin_expect((c), 0))
  28. #else
  29. #define FASTLZ_EXPECT_CONDITIONAL(c) (c)
  30. #define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
  31. #endif
  32. /*
  33. * Use inlined functions for supported systems.
  34. */
  35. #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
  36. #define FASTLZ_INLINE inline
  37. #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
  38. #define FASTLZ_INLINE __inline
  39. #else
  40. #define FASTLZ_INLINE
  41. #endif
  42. typedef unsigned char flzuint8;
  43. typedef unsigned short flzuint16;
  44. typedef unsigned int flzuint32;
  45. /* prototypes */
  46. int fastlz_compress(const void* input, int length, void* output);
  47. int fastlz_decompress(const void* input, int length, void* output);
  48. #define MAX_COPY 32
  49. #define MAX_LEN 264 /* 256 + 8 */
  50. #define MAX_DISTANCE 256
  51. #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
  52. #define HASH_LOG 13
  53. #define HASH_SIZE (1<< HASH_LOG)
  54. #define HASH_MASK (HASH_SIZE-1)
  55. #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
  56. FASTLZ_INLINE int fastlz_compress(const void* input, int length, void* output)
  57. {
  58. const flzuint8* ip = (const flzuint8*) input;
  59. const flzuint8* ip_bound = ip + length - 2;
  60. const flzuint8* ip_limit = ip + length - 12;
  61. flzuint8* op = (flzuint8*) output;
  62. const flzuint8* htab[HASH_SIZE];
  63. const flzuint8** hslot;
  64. flzuint32 hval;
  65. flzuint32 copy;
  66. /* sanity check */
  67. if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
  68. {
  69. if(length)
  70. {
  71. /* create literal copy only */
  72. *op++ = length-1;
  73. ip_bound++;
  74. while(ip <= ip_bound)
  75. *op++ = *ip++;
  76. return length+1;
  77. }
  78. else
  79. return 0;
  80. }
  81. /* initializes hash table */
  82. for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
  83. *hslot = ip;
  84. /* we start with literal copy */
  85. copy = 2;
  86. *op++ = MAX_COPY-1;
  87. *op++ = *ip++;
  88. *op++ = *ip++;
  89. /* main loop */
  90. while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
  91. {
  92. const flzuint8* ref;
  93. flzuint32 distance;
  94. /* minimum match length */
  95. flzuint32 len = 3;
  96. /* comparison starting-point */
  97. const flzuint8* anchor = ip;
  98. /* check for a run */
  99. /* find potential match */
  100. HASH_FUNCTION(hval,ip);
  101. hslot = htab + hval;
  102. ref = htab[hval];
  103. /* calculate distance to the match */
  104. distance = anchor - ref;
  105. /* update hash table */
  106. *hslot = anchor;
  107. /* is this a match? check the first 3 bytes */
  108. if(distance==0 ||
  109. (distance >= MAX_DISTANCE) ||
  110. *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
  111. goto literal;
  112. /* last matched byte */
  113. ip = anchor + len;
  114. /* distance is biased */
  115. distance--;
  116. if(!distance)
  117. {
  118. /* zero distance means a run */
  119. flzuint8 x = ip[-1];
  120. while(ip < ip_bound)
  121. if(*ref++ != x) break; else ip++;
  122. }
  123. else
  124. for(;;)
  125. {
  126. /* safe because the outer check against ip limit */
  127. if(*ref++ != *ip++) break;
  128. if(*ref++ != *ip++) break;
  129. if(*ref++ != *ip++) break;
  130. if(*ref++ != *ip++) break;
  131. if(*ref++ != *ip++) break;
  132. if(*ref++ != *ip++) break;
  133. if(*ref++ != *ip++) break;
  134. if(*ref++ != *ip++) break;
  135. while(ip < ip_bound)
  136. if(*ref++ != *ip++) break;
  137. break;
  138. }
  139. /* if we have copied something, adjust the copy count */
  140. if(copy)
  141. /* copy is biased, '0' means 1 byte copy */
  142. *(op-copy-1) = copy-1;
  143. else
  144. /* back, to overwrite the copy count */
  145. op--;
  146. /* reset literal counter */
  147. copy = 0;
  148. /* length is biased, '1' means a match of 3 bytes */
  149. ip -= 3;
  150. len = ip - anchor;
  151. /* encode the match */
  152. if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
  153. while(len > MAX_LEN-2)
  154. {
  155. *op++ = (7 << 5) + (distance >> 8);
  156. *op++ = MAX_LEN - 2 - 7 -2;
  157. *op++ = (distance & 255);
  158. len -= MAX_LEN-2;
  159. }
  160. if(len < 7)
  161. {
  162. *op++ = (len << 5) + (distance >> 8);
  163. *op++ = (distance & 255);
  164. }
  165. else
  166. {
  167. *op++ = (7 << 5) + (distance >> 8);
  168. *op++ = len - 7;
  169. *op++ = (distance & 255);
  170. }
  171. /* update the hash at match boundary */
  172. HASH_FUNCTION(hval,ip);
  173. htab[hval] = ip++;
  174. HASH_FUNCTION(hval,ip);
  175. htab[hval] = ip++;
  176. /* assuming literal copy */
  177. *op++ = MAX_COPY-1;
  178. continue;
  179. literal:
  180. *op++ = *anchor++;
  181. ip = anchor;
  182. copy++;
  183. if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
  184. {
  185. copy = 0;
  186. *op++ = MAX_COPY-1;
  187. }
  188. }
  189. /* left-over as literal copy */
  190. ip_bound++;
  191. while(ip <= ip_bound)
  192. {
  193. *op++ = *ip++;
  194. copy++;
  195. if(copy == MAX_COPY)
  196. {
  197. copy = 0;
  198. *op++ = MAX_COPY-1;
  199. }
  200. }
  201. /* if we have copied something, adjust the copy length */
  202. if(copy)
  203. *(op-copy-1) = copy-1;
  204. else
  205. op--;
  206. return op - (flzuint8*)output;
  207. }
  208. #include <stdio.h>
  209. #define log1(NUM) printf("%i op=%i(%x) ip=%i(%x) len=%i ctrl=%i ofs=%i(%i) limit=%i\n",NUM, (((int)op - (int)output)), *op, (((int)ip - (int)input)),*ip, len, ctrl, ofs, (ofs >> 8),ip < ip_limit);
  210. int fastlz_decompress(const void* input, int length, void* output)
  211. {
  212. const flzuint8* ip = (const flzuint8*) input;
  213. const flzuint8* ip_limit = ip + length;
  214. flzuint8* op = (flzuint8*) output;
  215. flzuint32 ctrl = (*ip++) & 31;
  216. int loop = 1;
  217. do
  218. {
  219. const flzuint8* ref = op;
  220. flzuint32 len = ctrl >> 5;
  221. flzuint32 ofs = (ctrl & 31) << 8;
  222. printf("-------------------\n");
  223. log1(1)
  224. if(ctrl >= 32)
  225. {
  226. len--;
  227. ref -= ofs;
  228. if (len == 7-1)
  229. len += *ip++;
  230. ref -= *ip++;
  231. log1(1)
  232. if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
  233. ctrl = *ip++;
  234. else
  235. loop = 0;
  236. log1(1)
  237. if(ref == op)
  238. {
  239. log1(2)
  240. /* optimize copy for a run */
  241. flzuint8 b = ref[-1];
  242. *op++ = b;
  243. *op++ = b;
  244. *op++ = b;
  245. for(; len; --len)
  246. *op++ = b;
  247. }
  248. else
  249. {
  250. log1(3)
  251. /* copy from reference */
  252. ref--;
  253. *op++ = *ref++;
  254. *op++ = *ref++;
  255. *op++ = *ref++;
  256. for(; len; --len)
  257. *op++ = *ref++;
  258. }
  259. }
  260. else
  261. {
  262. ctrl++;
  263. log1(4)
  264. *op++ = *ip++;
  265. for(--ctrl; ctrl; ctrl--){
  266. log1(5)
  267. *op++ = *ip++;
  268. }
  269. loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
  270. if(loop){
  271. ctrl = *ip++;
  272. }
  273. log1(6)
  274. }
  275. }
  276. while(FASTLZ_EXPECT_CONDITIONAL(loop));
  277. return op - (flzuint8*)output;
  278. }
  279. #include <stdlib.h>
  280. #include <assert.h>
  281. #include "ringbuffer.h"
  282. //#define log2(NUM) printf("%i op=%i(%x) ip=%i(%x) ref=%i(%x) dist=%i buf->end=%i len=%i ctrl=%i ofs=%i(%i) limit=%i\n",NUM, output_index,output[output_index], input_index,input[input_index],ref_index,input[ref_index],output_index - ref_index,ref_buffer_ptr->end, len, ctrl, ofs, ofs>>6,input_index < ip_limit);
  283. #define log2(NUM) printf("%i op=%i(%x) ip=%i ref=%i dist=%i buf->end=%i len=%i ctrl=%i ofs=%i(%i) limit=%i\n",NUM, output_index,output[output_index], input_index,ref_index,output_index - ref_index,ref_buffer_ptr->end, len, ctrl, ofs, ofs>>6,input_index < ip_limit);
  284. #define OUTPUT_INC(B) do { \
  285. __b = B;\
  286. output[output_index] = __b;\
  287. bufferWrite(ref_buffer_ptr, __b);\
  288. output_index++;\
  289. } while (0)
  290. #define OUTPUT_INC_FROM_REFINC() do { \
  291. __dist = (output_index-ref_index); \
  292. __c = buffer_get(ref_buffer_ptr, __dist); \
  293. printf("output_index=%i ref_index=%i(%x) dist=%i(%x) buf->end=%i buf->size=%i position=%i\n", output_index, ref_index, __c, __dist, __c, ref_buffer_ptr->end, ref_buffer_ptr->size, __mod(ref_buffer_ptr->end - __dist, ref_buffer_ptr->size)); \
  294. output[output_index] = __c;\
  295. bufferWrite(ref_buffer_ptr, __c);\
  296. output_index++;\
  297. ref_index++;\
  298. } while (0)
  299. #define FROM_REF(OUT) do { \
  300. flzuint16 __dist = (output_index-ref_index+1); \
  301. OUT = buffer_get(ref_buffer_ptr, __dist); \
  302. } while (0)
  303. #define INPUT_INC(OUT) do { \
  304. if (input_index<32768) { \
  305. OUT = input1[input_index++]; \
  306. } else { \
  307. OUT = input2[input_index-32768]; \
  308. input_index++; \
  309. }\
  310. } while (0)
  311. ring_buffer_typedef(unsigned char, byte_buffer);
  312. int fastlz_decompress2(unsigned char* input1, unsigned char* input2, int length, unsigned char* output)
  313. {
  314. flzuint32 input_index = 0;
  315. flzuint32 ip_limit = length;
  316. flzuint32 output_index = 0;
  317. flzuint32 ref_index = 0;
  318. //flzuint32 ctrl = (input[input_index++]) & 31;
  319. flzuint32 ctrl;
  320. INPUT_INC(ctrl);
  321. ctrl = ctrl & 31;
  322. int loop = 1;
  323. byte_buffer ref_buffer;
  324. buffer_init(ref_buffer, MAX_DISTANCE, unsigned char);
  325. byte_buffer* ref_buffer_ptr;
  326. ref_buffer_ptr = &ref_buffer;
  327. do
  328. {
  329. flzuint8 __b;
  330. flzuint16 __dist;
  331. flzuint8 __c;
  332. flzuint8 tmp;
  333. ref_index = output_index;
  334. flzuint32 len = ctrl >> 5;
  335. flzuint32 ofs = (ctrl & 31) << 6;
  336. printf("-------------------\n");
  337. log2(1)
  338. if(ctrl >= 32)
  339. {
  340. len--;
  341. ref_index -= ofs;
  342. if (len == 7-1){
  343. INPUT_INC(tmp);
  344. len += tmp;
  345. //len += input[input_index++];
  346. }
  347. INPUT_INC(tmp);
  348. ref_index -= tmp;
  349. //ref_index -= input[input_index++];
  350. log2(1)
  351. if(FASTLZ_EXPECT_CONDITIONAL( input_index < ip_limit))
  352. INPUT_INC(ctrl);
  353. //ctrl = input[input_index++];
  354. else
  355. loop = 0;
  356. log2(1)
  357. if(ref_index == output_index)
  358. {
  359. log2(2)
  360. //flzuint8 b = output[ref_index-1];
  361. flzuint8 b;
  362. FROM_REF(b);
  363. OUTPUT_INC(b);
  364. OUTPUT_INC(b);
  365. OUTPUT_INC(b);
  366. for(; len; --len)
  367. OUTPUT_INC(b);
  368. }
  369. else
  370. {
  371. log2(3)
  372. ref_index--;
  373. OUTPUT_INC_FROM_REFINC();
  374. OUTPUT_INC_FROM_REFINC();
  375. OUTPUT_INC_FROM_REFINC();
  376. for(; len; --len)
  377. OUTPUT_INC_FROM_REFINC();
  378. }
  379. }
  380. else
  381. {
  382. ctrl++;
  383. log2(4)
  384. INPUT_INC(tmp);
  385. OUTPUT_INC(tmp);
  386. //OUTPUT_INC(input[input_index++]);
  387. for(--ctrl; ctrl; ctrl--){
  388. log2(5)
  389. INPUT_INC(tmp);
  390. OUTPUT_INC(tmp);
  391. //OUTPUT_INC(input[input_index++]);
  392. }
  393. loop = FASTLZ_EXPECT_CONDITIONAL(input_index < ip_limit);
  394. if (loop){
  395. INPUT_INC(ctrl);
  396. //ctrl = input[input_index++];
  397. }
  398. log2(6)
  399. }
  400. }
  401. while(FASTLZ_EXPECT_CONDITIONAL(loop));
  402. buffer_destroy(ref_buffer_ptr);
  403. return 0;
  404. }