3
0

lzo1x_c.c 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  1. /* implementation of the LZO1[XY]-1 compression algorithm
  2. This file is part of the LZO real-time data compression library.
  3. Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
  4. All Rights Reserved.
  5. Markus F.X.J. Oberhumer <markus@oberhumer.com>
  6. http://www.oberhumer.com/opensource/lzo/
  7. The LZO library is free software; you can redistribute it and/or
  8. modify it under the terms of the GNU General Public License as
  9. published by the Free Software Foundation; either version 2 of
  10. the License, or (at your option) any later version.
  11. The LZO library is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. GNU General Public License for more details.
  15. You should have received a copy of the GNU General Public License
  16. along with the LZO library; see the file COPYING.
  17. If not, write to the Free Software Foundation, Inc.,
  18. 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19. */
  20. /***********************************************************************
  21. // compress a block of data.
  22. ************************************************************************/
  23. static NOINLINE unsigned
  24. do_compress(const uint8_t* in, unsigned in_len,
  25. uint8_t* out, unsigned* out_len,
  26. void* wrkmem)
  27. {
  28. register const uint8_t* ip;
  29. uint8_t* op;
  30. const uint8_t* const in_end = in + in_len;
  31. const uint8_t* const ip_end = in + in_len - M2_MAX_LEN - 5;
  32. const uint8_t* ii;
  33. const void* *const dict = (const void**) wrkmem;
  34. op = out;
  35. ip = in;
  36. ii = ip;
  37. ip += 4;
  38. for (;;) {
  39. register const uint8_t* m_pos;
  40. unsigned m_off;
  41. unsigned m_len;
  42. unsigned dindex;
  43. D_INDEX1(dindex,ip);
  44. GINDEX(m_pos,m_off,dict,dindex,in);
  45. if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
  46. goto literal;
  47. #if 1
  48. if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  49. goto try_match;
  50. D_INDEX2(dindex,ip);
  51. #endif
  52. GINDEX(m_pos,m_off,dict,dindex,in);
  53. if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
  54. goto literal;
  55. if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  56. goto try_match;
  57. goto literal;
  58. try_match:
  59. #if 1 && defined(LZO_UNALIGNED_OK_2)
  60. if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
  61. #else
  62. if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
  63. #endif
  64. {
  65. } else {
  66. if (m_pos[2] == ip[2]) {
  67. #if 0
  68. if (m_off <= M2_MAX_OFFSET)
  69. goto match;
  70. if (lit <= 3)
  71. goto match;
  72. if (lit == 3) { /* better compression, but slower */
  73. assert(op - 2 > out); op[-2] |= (uint8_t)(3);
  74. *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
  75. goto code_match;
  76. }
  77. if (m_pos[3] == ip[3])
  78. #endif
  79. goto match;
  80. }
  81. else {
  82. /* still need a better way for finding M1 matches */
  83. #if 0
  84. /* a M1 match */
  85. #if 0
  86. if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
  87. #else
  88. if (m_off <= M1_MAX_OFFSET && lit == 3)
  89. #endif
  90. {
  91. register unsigned t;
  92. t = lit;
  93. assert(op - 2 > out); op[-2] |= (uint8_t)(t);
  94. do *op++ = *ii++; while (--t > 0);
  95. assert(ii == ip);
  96. m_off -= 1;
  97. *op++ = (uint8_t)(M1_MARKER | ((m_off & 3) << 2));
  98. *op++ = (uint8_t)(m_off >> 2);
  99. ip += 2;
  100. goto match_done;
  101. }
  102. #endif
  103. }
  104. }
  105. /* a literal */
  106. literal:
  107. UPDATE_I(dict, 0, dindex, ip, in);
  108. ++ip;
  109. if (ip >= ip_end)
  110. break;
  111. continue;
  112. /* a match */
  113. match:
  114. UPDATE_I(dict, 0, dindex, ip, in);
  115. /* store current literal run */
  116. if (pd(ip, ii) > 0) {
  117. register unsigned t = pd(ip, ii);
  118. if (t <= 3) {
  119. assert(op - 2 > out);
  120. op[-2] |= (uint8_t)(t);
  121. }
  122. else if (t <= 18)
  123. *op++ = (uint8_t)(t - 3);
  124. else {
  125. register unsigned tt = t - 18;
  126. *op++ = 0;
  127. while (tt > 255) {
  128. tt -= 255;
  129. *op++ = 0;
  130. }
  131. assert(tt > 0);
  132. *op++ = (uint8_t)(tt);
  133. }
  134. do *op++ = *ii++; while (--t > 0);
  135. }
  136. /* code the match */
  137. assert(ii == ip);
  138. ip += 3;
  139. if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++
  140. || m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++
  141. #ifdef LZO1Y
  142. || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++
  143. || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++
  144. #endif
  145. ) {
  146. --ip;
  147. m_len = pd(ip, ii);
  148. assert(m_len >= 3);
  149. assert(m_len <= M2_MAX_LEN);
  150. if (m_off <= M2_MAX_OFFSET) {
  151. m_off -= 1;
  152. #if defined(LZO1X)
  153. *op++ = (uint8_t)(((m_len - 1) << 5) | ((m_off & 7) << 2));
  154. *op++ = (uint8_t)(m_off >> 3);
  155. #elif defined(LZO1Y)
  156. *op++ = (uint8_t)(((m_len + 1) << 4) | ((m_off & 3) << 2));
  157. *op++ = (uint8_t)(m_off >> 2);
  158. #endif
  159. }
  160. else if (m_off <= M3_MAX_OFFSET) {
  161. m_off -= 1;
  162. *op++ = (uint8_t)(M3_MARKER | (m_len - 2));
  163. goto m3_m4_offset;
  164. } else {
  165. #if defined(LZO1X)
  166. m_off -= 0x4000;
  167. assert(m_off > 0);
  168. assert(m_off <= 0x7fff);
  169. *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
  170. goto m3_m4_offset;
  171. #elif defined(LZO1Y)
  172. goto m4_match;
  173. #endif
  174. }
  175. }
  176. else {
  177. {
  178. const uint8_t* end = in_end;
  179. const uint8_t* m = m_pos + M2_MAX_LEN + 1;
  180. while (ip < end && *m == *ip)
  181. m++, ip++;
  182. m_len = pd(ip, ii);
  183. }
  184. assert(m_len > M2_MAX_LEN);
  185. if (m_off <= M3_MAX_OFFSET) {
  186. m_off -= 1;
  187. if (m_len <= 33)
  188. *op++ = (uint8_t)(M3_MARKER | (m_len - 2));
  189. else {
  190. m_len -= 33;
  191. *op++ = M3_MARKER | 0;
  192. goto m3_m4_len;
  193. }
  194. } else {
  195. #if defined(LZO1Y)
  196. m4_match:
  197. #endif
  198. m_off -= 0x4000;
  199. assert(m_off > 0);
  200. assert(m_off <= 0x7fff);
  201. if (m_len <= M4_MAX_LEN)
  202. *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
  203. else {
  204. m_len -= M4_MAX_LEN;
  205. *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11));
  206. m3_m4_len:
  207. while (m_len > 255) {
  208. m_len -= 255;
  209. *op++ = 0;
  210. }
  211. assert(m_len > 0);
  212. *op++ = (uint8_t)(m_len);
  213. }
  214. }
  215. m3_m4_offset:
  216. *op++ = (uint8_t)((m_off & 63) << 2);
  217. *op++ = (uint8_t)(m_off >> 6);
  218. }
  219. #if 0
  220. match_done:
  221. #endif
  222. ii = ip;
  223. if (ip >= ip_end)
  224. break;
  225. }
  226. *out_len = pd(op, out);
  227. return pd(in_end, ii);
  228. }
  229. /***********************************************************************
  230. // public entry point
  231. ************************************************************************/
  232. int DO_COMPRESS(const uint8_t* in, unsigned in_len,
  233. uint8_t* out, unsigned* out_len,
  234. void* wrkmem)
  235. {
  236. uint8_t* op = out;
  237. unsigned t;
  238. if (in_len <= M2_MAX_LEN + 5)
  239. t = in_len;
  240. else {
  241. t = do_compress(in,in_len,op,out_len,wrkmem);
  242. op += *out_len;
  243. }
  244. if (t > 0) {
  245. const uint8_t* ii = in + in_len - t;
  246. if (op == out && t <= 238)
  247. *op++ = (uint8_t)(17 + t);
  248. else if (t <= 3)
  249. op[-2] |= (uint8_t)(t);
  250. else if (t <= 18)
  251. *op++ = (uint8_t)(t - 3);
  252. else {
  253. unsigned tt = t - 18;
  254. *op++ = 0;
  255. while (tt > 255) {
  256. tt -= 255;
  257. *op++ = 0;
  258. }
  259. assert(tt > 0);
  260. *op++ = (uint8_t)(tt);
  261. }
  262. do *op++ = *ii++; while (--t > 0);
  263. }
  264. *op++ = M4_MARKER | 1;
  265. *op++ = 0;
  266. *op++ = 0;
  267. *out_len = pd(op, out);
  268. return 0; /*LZO_E_OK*/
  269. }