[libav.git] / libavcodec / lzo.c

/*
 * LZO 1x decompression
 * Copyright (c) 2006 Reimar Doeffinger
 *
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * FFmpeg is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with FFmpeg; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */
#include "common.h"
//! avoid e.g. MPlayers fast_memcpy, it slows things down here
#undef memcpy
#include <string.h>
#include "lzo.h"

//! define if we may write up to 12 bytes beyond the output buffer
#define OUTBUF_PADDED 1
//! define if we may read up to 4 bytes beyond the input buffer
#define INBUF_PADDED 1
typedef struct LZOContext {
    uint8_t *in, *in_end;
    uint8_t *out_start, *out, *out_end;
    int error;
} LZOContext;

/**
 * \brief read one byte from input buffer, avoiding overrun
 * \return byte read
 */
static inline int get_byte(LZOContext *c) {
    if (c->in < c->in_end)
        return *c->in++;
    c->error |= LZO_INPUT_DEPLETED;
    return 1;
}

/**
 * \brief decode a length value in the coding used by lzo
 * \param x previous byte value
 * \param mask bits used from x
 * \return decoded length value
 */
static inline int get_len(LZOContext *c, int x, int mask) {
    int cnt = x & mask;
    if (!cnt) {
        while (!(x = get_byte(c))) cnt += 255;
        cnt += mask + x;
    }
    return cnt;
}

/**
 * \brief copy bytes from input to output buffer with checking
 * \param cnt number of bytes to copy, must be > 0
 */
static inline void copy(LZOContext *c, int cnt) {
    register uint8_t *src = c->in;
    register uint8_t *dst = c->out;
    if (src + cnt > c->in_end) {
        cnt = c->in_end - src;
        c->error |= LZO_INPUT_DEPLETED;
    }
    if (dst + cnt > c->out_end) {
        cnt = c->out_end - dst;
        c->error |= LZO_OUTPUT_FULL;
    }
#if defined(INBUF_PADDED) && defined(OUTBUF_PADDED)
    dst[0] = src[0];
    dst[1] = src[1];
    dst[2] = src[2];
    dst[3] = src[3];
    src += 4;
    dst += 4;
    cnt -= 4;
    if (cnt > 0)
#endif
        memcpy(dst, src, cnt);
    c->in = src + cnt;
    c->out = dst + cnt;
}

/**
 * \brief copy previously decoded bytes to current position
 * \param back how many bytes back we start
 * \param cnt number of bytes to copy, must be > 0
 *
 * cnt > back is valid, this will copy the bytes we just copied,
 * thus creating a repeating pattern with a period length of back.
 */
static inline void copy_backptr(LZOContext *c, int back, int cnt) {
    register uint8_t *src = &c->out[-back];
    register uint8_t *dst = c->out;
    if (src < c->out_start) {
        c->error |= LZO_INVALID_BACKPTR;
        return;
    }
    if (dst + cnt > c->out_end) {
        cnt = c->out_end - dst;
        c->error |= LZO_OUTPUT_FULL;
    }
    if (back == 1) {
        memset(dst, *src, cnt);
        dst += cnt;
    } else {
#ifdef OUTBUF_PADDED
        dst[0] = src[0];
        dst[1] = src[1];
        dst[2] = src[2];
        dst[3] = src[3];
        src += 4;
        dst += 4;
        cnt -= 4;
        if (cnt > 0) {
            dst[0] = src[0];
            dst[1] = src[1];
            dst[2] = src[2];
            dst[3] = src[3];
            dst[4] = src[4];
            dst[5] = src[5];
            dst[6] = src[6];
            dst[7] = src[7];
            src += 8;
            dst += 8;
            cnt -= 8;
        }
#endif
        if (cnt > 0) {
            int blocklen = back;
            while (cnt > blocklen) {
                memcpy(dst, src, blocklen);
                dst += blocklen;
                cnt -= blocklen;
                blocklen <<= 1;
            }
            memcpy(dst, src, cnt);
        }
        dst += cnt;
    }
    c->out = dst;
}

/**
 * \brief decode LZO 1x compressed data
 * \param out output buffer
 * \param outlen size of output buffer, number of bytes left are returned here
 * \param in input buffer
 * \param inlen size of input buffer, number of bytes left are returned here
 * \return 0 on success, otherwise error flags, see lzo.h
 *
 * make sure all buffers are appropriately padded, in must provide
 * LZO_INPUT_PADDING, out must provide LZO_OUTPUT_PADDING additional bytes
 */
int lzo1x_decode(void *out, int *outlen, void *in, int *inlen) {
    enum {COPY, BACKPTR} state = COPY;
    int x;
    LZOContext c;
    c.in = in;
    c.in_end = (uint8_t *)in + *inlen;
    c.out = c.out_start = out;
    c.out_end = (uint8_t *)out + * outlen;
    c.error = 0;
    x = get_byte(&c);
    if (x > 17) {
        copy(&c, x - 17);
        x = get_byte(&c);
        if (x < 16) c.error |= LZO_ERROR;
    }
    while (!c.error) {
        int cnt, back;
        if (x >> 4) {
            if (x >> 6) {
                cnt = (x >> 5) - 1;
                back = (get_byte(&c) << 3) + ((x >> 2) & 7) + 1;
            } else if (x >> 5) {
                cnt = get_len(&c, x, 31);
                x = get_byte(&c);
                back = (get_byte(&c) << 6) + (x >> 2) + 1;
            } else {
                cnt = get_len(&c, x, 7);
                back = (1 << 14) + ((x & 8) << 11);
                x = get_byte(&c);
                back += (get_byte(&c) << 6) + (x >> 2);
                if (back == (1 << 14)) {
                    if (cnt != 1)
                        c.error |= LZO_ERROR;
                    break;
                }
            }
        } else
        switch (state) {
            case COPY:
                cnt = get_len(&c, x, 15);
                copy(&c, cnt + 3);
                x = get_byte(&c);
                if (x >> 4)
                    continue;
                cnt = 1;
                back = (1 << 11) + (get_byte(&c) << 2) + (x >> 2) + 1;
                break;
            case BACKPTR:
                cnt = 0;
                back = (get_byte(&c) << 2) + (x >> 2) + 1;
                break;
        }
        copy_backptr(&c, back, cnt + 2);
        cnt = x & 3;
        state = cnt ? BACKPTR : COPY;
        if (cnt)
            copy(&c, cnt);
        x = get_byte(&c);
    }
    *inlen = c.in_end - c.in;
    *outlen = c.out_end - c.out;
    return c.error;
}

#ifdef TEST
#include <stdio.h>
#include <lzo/lzo1x.h>
#include "log.h"
#define MAXSZ (10*1024*1024)
int main(int argc, char *argv[]) {
    FILE *in = fopen(argv[1], "rb");
    uint8_t *orig = av_malloc(MAXSZ + 16);
    uint8_t *comp = av_malloc(2*MAXSZ + 16);
    uint8_t *decomp = av_malloc(MAXSZ + 16);
    size_t s = fread(orig, 1, MAXSZ, in);
    lzo_uint clen = 0;
    long tmp[LZO1X_MEM_COMPRESS];
    int inlen, outlen;
    int i;
    av_log_level = AV_LOG_DEBUG;
    lzo1x_999_compress(orig, s, comp, &clen, tmp);
    for (i = 0; i < 300; i++) {
START_TIMER
        inlen = clen; outlen = MAXSZ;
        if (lzo1x_decode(decomp, &outlen, comp, &inlen))
            av_log(NULL, AV_LOG_ERROR, "decompression error\n");
STOP_TIMER("lzod")
    }
    if (memcmp(orig, decomp, s))
        av_log(NULL, AV_LOG_ERROR, "decompression incorrect\n");
    else
        av_log(NULL, AV_LOG_ERROR, "decompression ok\n");
    return 0;
}
#endif
Commit	Line	Data
517840c6 RD	1	/*
	2	* LZO 1x decompression
	3	* Copyright (c) 2006 Reimar Doeffinger
	4	*
b78e7197 DB	5	* This file is part of FFmpeg.
	6	*
	7	* FFmpeg is free software; you can redistribute it and/or
517840c6 RD	8	* modify it under the terms of the GNU Lesser General Public
517840c6 RD	9	* License as published by the Free Software Foundation; either
b78e7197	10	* version 2.1 of the License, or (at your option) any later version.
517840c6	11	*
b78e7197	12	* FFmpeg is distributed in the hope that it will be useful,
517840c6 RD	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
b78e7197	18	* License along with FFmpeg; if not, write to the Free Software
5509bffa	19	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
517840c6 RD	20	*/
517840c6 RD	21	#include "common.h"
f53a2931 RD	22	//! avoid e.g. MPlayers fast_memcpy, it slows things down here
	23	#undef memcpy
	24	#include <string.h>
517840c6 RD	25	#include "lzo.h"
517840c6 RD	26
f53a2931 RD	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 4 bytes beyond the input buffer
	30	#define INBUF_PADDED 1
517840c6 RD	31	typedef struct LZOContext {
517840c6 RD	32	uint8_t in, in_end;
f53a2931	33	uint8_t out_start, out, *out_end;
517840c6 RD	34	int error;
	35	} LZOContext;
	36
	37	/**
	38	* \brief read one byte from input buffer, avoiding overrun
	39	* \return byte read
	40	*/
	41	static inline int get_byte(LZOContext *c) {
	42	if (c->in < c->in_end)
	43	return *c->in++;
	44	c->error \|= LZO_INPUT_DEPLETED;
d3c71c50	45	return 1;
517840c6 RD	46	}
	47
	48	/**
	49	* \brief decode a length value in the coding used by lzo
	50	* \param x previous byte value
	51	* \param mask bits used from x
	52	* \return decoded length value
	53	*/
	54	static inline int get_len(LZOContext *c, int x, int mask) {
	55	int cnt = x & mask;
	56	if (!cnt) {
	57	while (!(x = get_byte(c))) cnt += 255;
	58	cnt += mask + x;
	59	}
	60	return cnt;
	61	}
	62
	63	/**
	64	* \brief copy bytes from input to output buffer with checking
	65	* \param cnt number of bytes to copy, must be > 0
	66	*/
	67	static inline void copy(LZOContext *c, int cnt) {
f53a2931 RD	68	register uint8_t *src = c->in;
	69	register uint8_t *dst = c->out;
	70	if (src + cnt > c->in_end) {
	71	cnt = c->in_end - src;
517840c6 RD	72	c->error \|= LZO_INPUT_DEPLETED;
517840c6 RD	73	}
f53a2931 RD	74	if (dst + cnt > c->out_end) {
f53a2931 RD	75	cnt = c->out_end - dst;
517840c6 RD	76	c->error \|= LZO_OUTPUT_FULL;
517840c6 RD	77	}
f53a2931 RD	78	#if defined(INBUF_PADDED) && defined(OUTBUF_PADDED)
	79	dst[0] = src[0];
	80	dst[1] = src[1];
	81	dst[2] = src[2];
	82	dst[3] = src[3];
	83	src += 4;
	84	dst += 4;
	85	cnt -= 4;
	86	if (cnt > 0)
	87	#endif
	88	memcpy(dst, src, cnt);
	89	c->in = src + cnt;
	90	c->out = dst + cnt;
517840c6 RD	91	}
	92
	93	/**
	94	* \brief copy previously decoded bytes to current position
	95	* \param back how many bytes back we start
	96	* \param cnt number of bytes to copy, must be > 0
	97	*
f53a2931 RD	98	* cnt > back is valid, this will copy the bytes we just copied,
f53a2931 RD	99	* thus creating a repeating pattern with a period length of back.
517840c6 RD	100	*/
517840c6 RD	101	static inline void copy_backptr(LZOContext *c, int back, int cnt) {
f53a2931 RD	102	register uint8_t *src = &c->out[-back];
	103	register uint8_t *dst = c->out;
	104	if (src < c->out_start) {
517840c6 RD	105	c->error \|= LZO_INVALID_BACKPTR;
	106	return;
	107	}
f53a2931 RD	108	if (dst + cnt > c->out_end) {
f53a2931 RD	109	cnt = c->out_end - dst;
517840c6 RD	110	c->error \|= LZO_OUTPUT_FULL;
517840c6 RD	111	}
f53a2931 RD	112	if (back == 1) {
	113	memset(dst, *src, cnt);
	114	dst += cnt;
	115	} else {
	116	#ifdef OUTBUF_PADDED
	117	dst[0] = src[0];
	118	dst[1] = src[1];
	119	dst[2] = src[2];
	120	dst[3] = src[3];
	121	src += 4;
	122	dst += 4;
	123	cnt -= 4;
	124	if (cnt > 0) {
	125	dst[0] = src[0];
	126	dst[1] = src[1];
	127	dst[2] = src[2];
	128	dst[3] = src[3];
	129	dst[4] = src[4];
	130	dst[5] = src[5];
	131	dst[6] = src[6];
	132	dst[7] = src[7];
	133	src += 8;
	134	dst += 8;
	135	cnt -= 8;
	136	}
	137	#endif
	138	if (cnt > 0) {
	139	int blocklen = back;
	140	while (cnt > blocklen) {
	141	memcpy(dst, src, blocklen);
	142	dst += blocklen;
	143	cnt -= blocklen;
	144	blocklen <<= 1;
	145	}
	146	memcpy(dst, src, cnt);
	147	}
	148	dst += cnt;
	149	}
	150	c->out = dst;
517840c6 RD	151	}
	152
	153	/**
	154	* \brief decode LZO 1x compressed data
	155	* \param out output buffer
	156	* \param outlen size of output buffer, number of bytes left are returned here
	157	* \param in input buffer
	158	* \param inlen size of input buffer, number of bytes left are returned here
	159	* \return 0 on success, otherwise error flags, see lzo.h
f53a2931 RD	160	*
	161	* make sure all buffers are appropriately padded, in must provide
	162	* LZO_INPUT_PADDING, out must provide LZO_OUTPUT_PADDING additional bytes
517840c6 RD	163	*/
	164	int lzo1x_decode(void out, int outlen, void in, int inlen) {
	165	enum {COPY, BACKPTR} state = COPY;
	166	int x;
	167	LZOContext c;
	168	c.in = in;
214019ed	169	c.in_end = (uint8_t )in + inlen;
f53a2931	170	c.out = c.out_start = out;
214019ed	171	c.out_end = (uint8_t )out + outlen;
517840c6 RD	172	c.error = 0;
	173	x = get_byte(&c);
	174	if (x > 17) {
	175	copy(&c, x - 17);
	176	x = get_byte(&c);
	177	if (x < 16) c.error \|= LZO_ERROR;
	178	}
	179	while (!c.error) {
	180	int cnt, back;
	181	if (x >> 4) {
517840c6 RD	182	if (x >> 6) {
	183	cnt = (x >> 5) - 1;
	184	back = (get_byte(&c) << 3) + ((x >> 2) & 7) + 1;
	185	} else if (x >> 5) {
	186	cnt = get_len(&c, x, 31);
	187	x = get_byte(&c);
	188	back = (get_byte(&c) << 6) + (x >> 2) + 1;
	189	} else {
	190	cnt = get_len(&c, x, 7);
	191	back = (1 << 14) + ((x & 8) << 11);
	192	x = get_byte(&c);
	193	back += (get_byte(&c) << 6) + (x >> 2);
	194	if (back == (1 << 14)) {
	195	if (cnt != 1)
	196	c.error \|= LZO_ERROR;
	197	break;
	198	}
	199	}
	200	} else
	201	switch (state) {
	202	case COPY:
	203	cnt = get_len(&c, x, 15);
	204	copy(&c, cnt + 3);
	205	x = get_byte(&c);
	206	if (x >> 4)
	207	continue;
	208	cnt = 1;
	209	back = (1 << 11) + (get_byte(&c) << 2) + (x >> 2) + 1;
	210	break;
	211	case BACKPTR:
	212	cnt = 0;
	213	back = (get_byte(&c) << 2) + (x >> 2) + 1;
	214	break;
	215	}
	216	copy_backptr(&c, back, cnt + 2);
	217	cnt = x & 3;
d66fbc14	218	state = cnt ? BACKPTR : COPY;
517840c6 RD	219	if (cnt)
517840c6 RD	220	copy(&c, cnt);
517840c6 RD	221	x = get_byte(&c);
	222	}
	223	*inlen = c.in_end - c.in;
	224	*outlen = c.out_end - c.out;
	225	return c.error;
	226	}
266aa26c RD	227
	228	#ifdef TEST
	229	#include <stdio.h>
	230	#include <lzo/lzo1x.h>
	231	#include "log.h"
	232	#define MAXSZ (1010241024)
	233	int main(int argc, char *argv[]) {
	234	FILE *in = fopen(argv[1], "rb");
	235	uint8_t *orig = av_malloc(MAXSZ + 16);
	236	uint8_t comp = av_malloc(2MAXSZ + 16);
	237	uint8_t *decomp = av_malloc(MAXSZ + 16);
	238	size_t s = fread(orig, 1, MAXSZ, in);
	239	lzo_uint clen = 0;
	240	long tmp[LZO1X_MEM_COMPRESS];
	241	int inlen, outlen;
	242	int i;
	243	av_log_level = AV_LOG_DEBUG;
	244	lzo1x_999_compress(orig, s, comp, &clen, tmp);
	245	for (i = 0; i < 300; i++) {
	246	START_TIMER
	247	inlen = clen; outlen = MAXSZ;
	248	if (lzo1x_decode(decomp, &outlen, comp, &inlen))
	249	av_log(NULL, AV_LOG_ERROR, "decompression error\n");
	250	STOP_TIMER("lzod")
	251	}
	252	if (memcmp(orig, decomp, s))
	253	av_log(NULL, AV_LOG_ERROR, "decompression incorrect\n");
	254	else
	255	av_log(NULL, AV_LOG_ERROR, "decompression ok\n");
	256	return 0;
	257	}
	258	#endif