lzo.c 8.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287
  1. /*
  2. * LZO 1x decompression
  3. * Copyright (c) 2006 Reimar Doeffinger
  4. *
  5. * This file is part of FFmpeg.
  6. *
  7. * FFmpeg is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU Lesser General Public
  9. * License as published by the Free Software Foundation; either
  10. * version 2.1 of the License, or (at your option) any later version.
  11. *
  12. * FFmpeg is distributed in the hope that it will be useful,
  13. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15. * Lesser General Public License for more details.
  16. *
  17. * You should have received a copy of the GNU Lesser General Public
  18. * License along with FFmpeg; if not, write to the Free Software
  19. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20. */
  21. #include "avutil.h"
  22. #include "common.h"
  23. /// Avoid e.g. MPlayers fast_memcpy, it slows things down here.
  24. #undef memcpy
  25. #include <string.h>
  26. #include "lzo.h"
  27. /// Define if we may write up to 12 bytes beyond the output buffer.
  28. #define OUTBUF_PADDED 1
  29. /// Define if we may read up to 8 bytes beyond the input buffer.
  30. #define INBUF_PADDED 1
  31. typedef struct LZOContext {
  32. const uint8_t *in, *in_end;
  33. uint8_t *out_start, *out, *out_end;
  34. int error;
  35. } LZOContext;
  36. /**
  37. * @brief Reads one byte from the input buffer, avoiding an overrun.
  38. * @return byte read
  39. */
  40. static inline int get_byte(LZOContext *c) {
  41. if (c->in < c->in_end)
  42. return *c->in++;
  43. c->error |= AV_LZO_INPUT_DEPLETED;
  44. return 1;
  45. }
  46. #ifdef INBUF_PADDED
  47. #define GETB(c) (*(c).in++)
  48. #else
  49. #define GETB(c) get_byte(&(c))
  50. #endif
  51. /**
  52. * @brief Decodes a length value in the coding used by lzo.
  53. * @param x previous byte value
  54. * @param mask bits used from x
  55. * @return decoded length value
  56. */
  57. static inline int get_len(LZOContext *c, int x, int mask) {
  58. int cnt = x & mask;
  59. if (!cnt) {
  60. while (!(x = get_byte(c))) cnt += 255;
  61. cnt += mask + x;
  62. }
  63. return cnt;
  64. }
  65. //#define UNALIGNED_LOADSTORE
  66. #define BUILTIN_MEMCPY
  67. #ifdef UNALIGNED_LOADSTORE
  68. #define COPY2(d, s) *(uint16_t *)(d) = *(uint16_t *)(s);
  69. #define COPY4(d, s) *(uint32_t *)(d) = *(uint32_t *)(s);
  70. #elif defined(BUILTIN_MEMCPY)
  71. #define COPY2(d, s) memcpy(d, s, 2);
  72. #define COPY4(d, s) memcpy(d, s, 4);
  73. #else
  74. #define COPY2(d, s) (d)[0] = (s)[0]; (d)[1] = (s)[1];
  75. #define COPY4(d, s) (d)[0] = (s)[0]; (d)[1] = (s)[1]; (d)[2] = (s)[2]; (d)[3] = (s)[3];
  76. #endif
  77. /**
  78. * @brief Copies bytes from input to output buffer with checking.
  79. * @param cnt number of bytes to copy, must be >= 0
  80. */
  81. static inline void copy(LZOContext *c, int cnt) {
  82. register const uint8_t *src = c->in;
  83. register uint8_t *dst = c->out;
  84. if (cnt > c->in_end - src) {
  85. cnt = FFMAX(c->in_end - src, 0);
  86. c->error |= AV_LZO_INPUT_DEPLETED;
  87. }
  88. if (cnt > c->out_end - dst) {
  89. cnt = FFMAX(c->out_end - dst, 0);
  90. c->error |= AV_LZO_OUTPUT_FULL;
  91. }
  92. #if defined(INBUF_PADDED) && defined(OUTBUF_PADDED)
  93. COPY4(dst, src);
  94. src += 4;
  95. dst += 4;
  96. cnt -= 4;
  97. if (cnt > 0)
  98. #endif
  99. memcpy(dst, src, cnt);
  100. c->in = src + cnt;
  101. c->out = dst + cnt;
  102. }
  103. static inline void memcpy_backptr(uint8_t *dst, int back, int cnt);
  104. /**
  105. * @brief Copies previously decoded bytes to current position.
  106. * @param back how many bytes back we start, must be > 0
  107. * @param cnt number of bytes to copy, must be >= 0
  108. *
  109. * cnt > back is valid, this will copy the bytes we just copied,
  110. * thus creating a repeating pattern with a period length of back.
  111. */
  112. static inline void copy_backptr(LZOContext *c, int back, int cnt) {
  113. register const uint8_t *src = &c->out[-back];
  114. register uint8_t *dst = c->out;
  115. if (src < c->out_start || src > dst) {
  116. c->error |= AV_LZO_INVALID_BACKPTR;
  117. return;
  118. }
  119. if (cnt > c->out_end - dst) {
  120. cnt = FFMAX(c->out_end - dst, 0);
  121. c->error |= AV_LZO_OUTPUT_FULL;
  122. }
  123. memcpy_backptr(dst, back, cnt);
  124. c->out = dst + cnt;
  125. }
  126. static inline void memcpy_backptr(uint8_t *dst, int back, int cnt) {
  127. const uint8_t *src = &dst[-back];
  128. if (back <= 1) {
  129. memset(dst, *src, cnt);
  130. } else {
  131. #ifdef OUTBUF_PADDED
  132. COPY2(dst, src);
  133. COPY2(dst + 2, src + 2);
  134. src += 4;
  135. dst += 4;
  136. cnt -= 4;
  137. if (cnt > 0) {
  138. COPY2(dst, src);
  139. COPY2(dst + 2, src + 2);
  140. COPY2(dst + 4, src + 4);
  141. COPY2(dst + 6, src + 6);
  142. src += 8;
  143. dst += 8;
  144. cnt -= 8;
  145. }
  146. #endif
  147. if (cnt > 0) {
  148. int blocklen = back;
  149. while (cnt > blocklen) {
  150. memcpy(dst, src, blocklen);
  151. dst += blocklen;
  152. cnt -= blocklen;
  153. blocklen <<= 1;
  154. }
  155. memcpy(dst, src, cnt);
  156. }
  157. }
  158. }
  159. void av_memcpy_backptr(uint8_t *dst, int back, int cnt) {
  160. memcpy_backptr(dst, back, cnt);
  161. }
  162. int av_lzo1x_decode(void *out, int *outlen, const void *in, int *inlen) {
  163. int state= 0;
  164. int x;
  165. LZOContext c;
  166. if (*outlen <= 0 || *inlen <= 0) {
  167. int res = 0;
  168. if (*outlen <= 0)
  169. res |= AV_LZO_OUTPUT_FULL;
  170. if (*inlen <= 0)
  171. res |= AV_LZO_INPUT_DEPLETED;
  172. return res;
  173. }
  174. c.in = in;
  175. c.in_end = (const uint8_t *)in + *inlen;
  176. c.out = c.out_start = out;
  177. c.out_end = (uint8_t *)out + * outlen;
  178. c.error = 0;
  179. x = GETB(c);
  180. if (x > 17) {
  181. copy(&c, x - 17);
  182. x = GETB(c);
  183. if (x < 16) c.error |= AV_LZO_ERROR;
  184. }
  185. if (c.in > c.in_end)
  186. c.error |= AV_LZO_INPUT_DEPLETED;
  187. while (!c.error) {
  188. int cnt, back;
  189. if (x > 15) {
  190. if (x > 63) {
  191. cnt = (x >> 5) - 1;
  192. back = (GETB(c) << 3) + ((x >> 2) & 7) + 1;
  193. } else if (x > 31) {
  194. cnt = get_len(&c, x, 31);
  195. x = GETB(c);
  196. back = (GETB(c) << 6) + (x >> 2) + 1;
  197. } else {
  198. cnt = get_len(&c, x, 7);
  199. back = (1 << 14) + ((x & 8) << 11);
  200. x = GETB(c);
  201. back += (GETB(c) << 6) + (x >> 2);
  202. if (back == (1 << 14)) {
  203. if (cnt != 1)
  204. c.error |= AV_LZO_ERROR;
  205. break;
  206. }
  207. }
  208. } else if(!state){
  209. cnt = get_len(&c, x, 15);
  210. copy(&c, cnt + 3);
  211. x = GETB(c);
  212. if (x > 15)
  213. continue;
  214. cnt = 1;
  215. back = (1 << 11) + (GETB(c) << 2) + (x >> 2) + 1;
  216. } else {
  217. cnt = 0;
  218. back = (GETB(c) << 2) + (x >> 2) + 1;
  219. }
  220. copy_backptr(&c, back, cnt + 2);
  221. state=
  222. cnt = x & 3;
  223. copy(&c, cnt);
  224. x = GETB(c);
  225. }
  226. *inlen = c.in_end - c.in;
  227. if (c.in > c.in_end)
  228. *inlen = 0;
  229. *outlen = c.out_end - c.out;
  230. return c.error;
  231. }
  232. #ifdef TEST
  233. #include <stdio.h>
  234. #include <lzo/lzo1x.h>
  235. #include "log.h"
  236. #define MAXSZ (10*1024*1024)
  237. /* Define one of these to 1 if you wish to benchmark liblzo
  238. * instead of our native implementation. */
  239. #define BENCHMARK_LIBLZO_SAFE 0
  240. #define BENCHMARK_LIBLZO_UNSAFE 0
  241. int main(int argc, char *argv[]) {
  242. FILE *in = fopen(argv[1], "rb");
  243. uint8_t *orig = av_malloc(MAXSZ + 16);
  244. uint8_t *comp = av_malloc(2*MAXSZ + 16);
  245. uint8_t *decomp = av_malloc(MAXSZ + 16);
  246. size_t s = fread(orig, 1, MAXSZ, in);
  247. lzo_uint clen = 0;
  248. long tmp[LZO1X_MEM_COMPRESS];
  249. int inlen, outlen;
  250. int i;
  251. av_log_set_level(AV_LOG_DEBUG);
  252. lzo1x_999_compress(orig, s, comp, &clen, tmp);
  253. for (i = 0; i < 300; i++) {
  254. START_TIMER
  255. inlen = clen; outlen = MAXSZ;
  256. #if BENCHMARK_LIBLZO_SAFE
  257. if (lzo1x_decompress_safe(comp, inlen, decomp, &outlen, NULL))
  258. #elif BENCHMARK_LIBLZO_UNSAFE
  259. if (lzo1x_decompress(comp, inlen, decomp, &outlen, NULL))
  260. #else
  261. if (av_lzo1x_decode(decomp, &outlen, comp, &inlen))
  262. #endif
  263. av_log(NULL, AV_LOG_ERROR, "decompression error\n");
  264. STOP_TIMER("lzod")
  265. }
  266. if (memcmp(orig, decomp, s))
  267. av_log(NULL, AV_LOG_ERROR, "decompression incorrect\n");
  268. else
  269. av_log(NULL, AV_LOG_ERROR, "decompression OK\n");
  270. return 0;
  271. }
  272. #endif