diff options
Diffstat (limited to 'contrib/ffmpeg/libavutil')
43 files changed, 4837 insertions, 0 deletions
diff --git a/contrib/ffmpeg/libavutil/Makefile b/contrib/ffmpeg/libavutil/Makefile new file mode 100644 index 000000000..a760401ab --- /dev/null +++ b/contrib/ffmpeg/libavutil/Makefile @@ -0,0 +1,27 @@ +include ../config.mak + +OBJS= mathematics.o \ + rational.o \ + intfloat_readwrite.o \ + crc.o \ + md5.o \ + lls.o \ + adler32.o \ + log.o \ + mem.o \ + fifo.o \ + tree.o \ + lzo.o \ + random.o \ + aes.o \ + base64.o \ + +HEADERS = avutil.h common.h mathematics.h integer.h rational.h \ + intfloat_readwrite.h md5.h adler32.h log.h fifo.h lzo.h \ + random.h mem.h base64.h + +NAME=avutil +LIBVERSION=$(LAVUVERSION) +LIBMAJOR=$(LAVUMAJOR) + +include ../common.mak diff --git a/contrib/ffmpeg/libavutil/adler32.c b/contrib/ffmpeg/libavutil/adler32.c new file mode 100644 index 000000000..50d57470b --- /dev/null +++ b/contrib/ffmpeg/libavutil/adler32.c @@ -0,0 +1,71 @@ +/* adler32.c -- compute the Adler-32 checksum of a data stream + * This is a modified version based on adler32.c from the zlib library. + * + * Copyright (C) 1995 Mark Adler + * + * This software is provided 'as-is', without any express or implied + * warranty. In no event will the authors be held liable for any damages + * arising from the use of this software. + * + * Permission is granted to anyone to use this software for any purpose, + * including commercial applications, and to alter it and redistribute it + * freely, subject to the following restrictions: + * + * 1. The origin of this software must not be misrepresented; you must not + * claim that you wrote the original software. If you use this software + * in a product, an acknowledgment in the product documentation would be + * appreciated but is not required. + * 2. Altered source versions must be plainly marked as such, and must not be + * misrepresented as being the original software. + * 3. This notice may not be removed or altered from any source distribution. + * + */ + +#include "common.h" +#include "adler32.h" + +#define BASE 65521L /* largest prime smaller than 65536 */ + +#define DO1(buf) {s1 += *buf++; s2 += s1;} +#define DO4(buf) DO1(buf); DO1(buf); DO1(buf); DO1(buf); +#define DO16(buf) DO4(buf); DO4(buf); DO4(buf); DO4(buf); + +unsigned long av_adler32_update(unsigned long adler, const uint8_t *buf, unsigned int len) +{ + unsigned long s1 = adler & 0xffff; + unsigned long s2 = adler >> 16; + + while (len>0) { +#ifdef CONFIG_SMALL + while(len>4 && s2 < (1U<<31)){ + DO4(buf); len-=4; +#else + while(len>16 && s2 < (1U<<31)){ + DO16(buf); len-=16; +#endif + } + DO1(buf); len--; + s1 %= BASE; + s2 %= BASE; + } + return (s2 << 16) | s1; +} + +#ifdef TEST +#include "log.h" +#define LEN 7001 +volatile int checksum; +int main(){ + int i; + char data[LEN]; + av_log_level = AV_LOG_DEBUG; + for(i=0; i<LEN; i++) + data[i]= ((i*i)>>3) + 123*i; + for(i=0; i<1000; i++){ + START_TIMER + checksum= av_adler32_update(1, data, LEN); + STOP_TIMER("adler") + } + av_log(NULL, AV_LOG_DEBUG, "%X == 50E6E508\n", checksum); +} +#endif diff --git a/contrib/ffmpeg/libavutil/adler32.h b/contrib/ffmpeg/libavutil/adler32.h new file mode 100644 index 000000000..f56d416fb --- /dev/null +++ b/contrib/ffmpeg/libavutil/adler32.h @@ -0,0 +1,27 @@ +/* + * copyright (c) 2006 Mans Rullgard + * + * 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 + */ + +#ifndef ADLER32_H +#define ADLER32_H + +unsigned long av_adler32_update(unsigned long adler, const uint8_t *buf, + unsigned int len); + +#endif diff --git a/contrib/ffmpeg/libavutil/aes.c b/contrib/ffmpeg/libavutil/aes.c new file mode 100644 index 000000000..55ae0d4f3 --- /dev/null +++ b/contrib/ffmpeg/libavutil/aes.c @@ -0,0 +1,239 @@ +/* + * copyright (c) 2007 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + * + * some optimization ideas from aes128.c by Reimar Doeffinger + */ + +#include "common.h" +#include "aes.h" + +typedef struct AVAES{ + uint8_t round_key[15][4][4]; + uint8_t state[2][4][4]; + int rounds; +}AVAES; + +const int av_aes_size= sizeof(AVAES); + +static const uint8_t rcon[10] = { + 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36 +}; + +static uint8_t sbox[256]; +static uint8_t inv_sbox[256]; +#ifdef CONFIG_SMALL +static uint32_t enc_multbl[1][256]; +static uint32_t dec_multbl[1][256]; +#else +static uint32_t enc_multbl[4][256]; +static uint32_t dec_multbl[4][256]; +#endif + +static inline void addkey(uint64_t dst[2], uint64_t src[2], uint64_t round_key[2]){ + dst[0] = src[0] ^ round_key[0]; + dst[1] = src[1] ^ round_key[1]; +} + +static void subshift(uint8_t s0[2][16], int s, uint8_t *box){ + uint8_t (*s1)[16]= s0[0] - s; + uint8_t (*s3)[16]= s0[0] + s; + s0[0][0]=box[s0[1][ 0]]; s0[0][ 4]=box[s0[1][ 4]]; s0[0][ 8]=box[s0[1][ 8]]; s0[0][12]=box[s0[1][12]]; + s1[0][3]=box[s1[1][ 7]]; s1[0][ 7]=box[s1[1][11]]; s1[0][11]=box[s1[1][15]]; s1[0][15]=box[s1[1][ 3]]; + s0[0][2]=box[s0[1][10]]; s0[0][10]=box[s0[1][ 2]]; s0[0][ 6]=box[s0[1][14]]; s0[0][14]=box[s0[1][ 6]]; + s3[0][1]=box[s3[1][13]]; s3[0][13]=box[s3[1][ 9]]; s3[0][ 9]=box[s3[1][ 5]]; s3[0][ 5]=box[s3[1][ 1]]; +} + +static inline int mix_core(uint32_t multbl[4][256], int a, int b, int c, int d){ +#ifdef CONFIG_SMALL +#define ROT(x,s) ((x<<s)|(x>>(32-s))) + return multbl[0][a] ^ ROT(multbl[0][b], 8) ^ ROT(multbl[0][c], 16) ^ ROT(multbl[0][d], 24); +#else + return multbl[0][a] ^ multbl[1][b] ^ multbl[2][c] ^ multbl[3][d]; +#endif +} + +static inline void mix(uint8_t state[2][4][4], uint32_t multbl[4][256], int s1, int s3){ + ((uint32_t *)(state))[0] = mix_core(multbl, state[1][0][0], state[1][s1 ][1], state[1][2][2], state[1][s3 ][3]); + ((uint32_t *)(state))[1] = mix_core(multbl, state[1][1][0], state[1][s3-1][1], state[1][3][2], state[1][s1-1][3]); + ((uint32_t *)(state))[2] = mix_core(multbl, state[1][2][0], state[1][s3 ][1], state[1][0][2], state[1][s1 ][3]); + ((uint32_t *)(state))[3] = mix_core(multbl, state[1][3][0], state[1][s1-1][1], state[1][1][2], state[1][s3-1][3]); +} + +static inline void crypt(AVAES *a, int s, uint8_t *sbox, uint32_t *multbl){ + int r; + + for(r=a->rounds-1; r>0; r--){ + mix(a->state, multbl, 3-s, 1+s); + addkey(a->state[1], a->state[0], a->round_key[r]); + } + subshift(a->state[0][0], s, sbox); +} + +void av_aes_crypt(AVAES *a, uint8_t *dst, uint8_t *src, int count, uint8_t *iv, int decrypt){ + while(count--){ + addkey(a->state[1], src, a->round_key[a->rounds]); + if(decrypt) { + crypt(a, 0, inv_sbox, dec_multbl); + if(iv){ + addkey(a->state[0], a->state[0], iv); + memcpy(iv, src, 16); + } + addkey(dst, a->state[0], a->round_key[0]); + }else{ + if(iv) addkey(a->state[1], a->state[1], iv); + crypt(a, 2, sbox, enc_multbl); + addkey(dst, a->state[0], a->round_key[0]); + if(iv) memcpy(iv, dst, 16); + } + src+=16; + dst+=16; + } +} + +static void init_multbl2(uint8_t tbl[1024], int c[4], uint8_t *log8, uint8_t *alog8, uint8_t *sbox){ + int i, j; + for(i=0; i<1024; i++){ + int x= sbox[i>>2]; + if(x) tbl[i]= alog8[ log8[x] + log8[c[i&3]] ]; + } +#ifndef CONFIG_SMALL + for(j=256; j<1024; j++) + for(i=0; i<4; i++) + tbl[4*j+i]= tbl[4*j + ((i-1)&3) - 1024]; +#endif +} + +// this is based on the reference AES code by Paulo Barreto and Vincent Rijmen +int av_aes_init(AVAES *a, const uint8_t *key, int key_bits, int decrypt) { + int i, j, t, rconpointer = 0; + uint8_t tk[8][4]; + int KC= key_bits>>5; + int rounds= KC + 6; + uint8_t log8[256]; + uint8_t alog8[512]; + + if(!enc_multbl[4][1023]){ + j=1; + for(i=0; i<255; i++){ + alog8[i]= + alog8[i+255]= j; + log8[j]= i; + j^= j+j; + if(j>255) j^= 0x11B; + } + for(i=0; i<256; i++){ + j= i ? alog8[255-log8[i]] : 0; + j ^= (j<<1) ^ (j<<2) ^ (j<<3) ^ (j<<4); + j = (j ^ (j>>8) ^ 99) & 255; + inv_sbox[j]= i; + sbox [i]= j; + } + init_multbl2(dec_multbl[0], (int[4]){0xe, 0x9, 0xd, 0xb}, log8, alog8, inv_sbox); + init_multbl2(enc_multbl[0], (int[4]){0x2, 0x1, 0x1, 0x3}, log8, alog8, sbox); + } + + if(key_bits!=128 && key_bits!=192 && key_bits!=256) + return -1; + + a->rounds= rounds; + + memcpy(tk, key, KC*4); + + for(t= 0; t < (rounds+1)*16;) { + memcpy(a->round_key[0][0]+t, tk, KC*4); + t+= KC*4; + + for(i = 0; i < 4; i++) + tk[0][i] ^= sbox[tk[KC-1][(i+1)&3]]; + tk[0][0] ^= rcon[rconpointer++]; + + for(j = 1; j < KC; j++){ + if(KC != 8 || j != KC>>1) + for(i = 0; i < 4; i++) tk[j][i] ^= tk[j-1][i]; + else + for(i = 0; i < 4; i++) tk[j][i] ^= sbox[tk[j-1][i]]; + } + } + + if(decrypt){ + for(i=1; i<rounds; i++){ + uint8_t tmp[3][16]; + memcpy(tmp[2], a->round_key[i][0], 16); + subshift(tmp[1], 0, sbox); + mix(tmp, dec_multbl, 1, 3); + memcpy(a->round_key[i][0], tmp[0], 16); + } + }else{ + for(i=0; i<(rounds+1)>>1; i++){ + for(j=0; j<16; j++) + FFSWAP(int, a->round_key[i][0][j], a->round_key[rounds-i][0][j]); + } + } + + return 0; +} + +#ifdef TEST +#include "log.h" + +int main(){ + int i,j; + AVAES ae, ad, b; + uint8_t rkey[2][16]= { + {0}, + {0x10, 0xa5, 0x88, 0x69, 0xd7, 0x4b, 0xe5, 0xa3, 0x74, 0xcf, 0x86, 0x7c, 0xfb, 0x47, 0x38, 0x59}}; + uint8_t pt[16], rpt[2][16]= { + {0x6a, 0x84, 0x86, 0x7c, 0xd7, 0x7e, 0x12, 0xad, 0x07, 0xea, 0x1b, 0xe8, 0x95, 0xc5, 0x3f, 0xa3}, + {0}}; + uint8_t rct[2][16]= { + {0x73, 0x22, 0x81, 0xc0, 0xa0, 0xaa, 0xb8, 0xf7, 0xa5, 0x4a, 0x0c, 0x67, 0xa0, 0xc4, 0x5e, 0xcf}, + {0x6d, 0x25, 0x1e, 0x69, 0x44, 0xb0, 0x51, 0xe0, 0x4e, 0xaa, 0x6f, 0xb4, 0xdb, 0xf7, 0x84, 0x65}}; + uint8_t temp[16]; + + av_aes_init(&ae, "PI=3.141592654..", 128, 0); + av_aes_init(&ad, "PI=3.141592654..", 128, 1); + av_log_level= AV_LOG_DEBUG; + + for(i=0; i<2; i++){ + av_aes_init(&b, rkey[i], 128, 1); + av_aes_crypt(&b, temp, rct[i], 1, NULL, 1); + for(j=0; j<16; j++) + if(rpt[i][j] != temp[j]) + av_log(NULL, AV_LOG_ERROR, "%d %02X %02X\n", j, rpt[i][j], temp[j]); + } + + for(i=0; i<10000; i++){ + for(j=0; j<16; j++){ + pt[j]= random(); + } +{START_TIMER + av_aes_crypt(&ae, temp, pt, 1, NULL, 0); + if(!(i&(i-1))) + av_log(NULL, AV_LOG_ERROR, "%02X %02X %02X %02X\n", temp[0], temp[5], temp[10], temp[15]); + av_aes_crypt(&ad, temp, temp, 1, NULL, 1); +STOP_TIMER("aes")} + for(j=0; j<16; j++){ + if(pt[j] != temp[j]){ + av_log(NULL, AV_LOG_ERROR, "%d %d %02X %02X\n", i,j, pt[j], temp[j]); + } + } + } + return 0; +} +#endif diff --git a/contrib/ffmpeg/libavutil/aes.h b/contrib/ffmpeg/libavutil/aes.h new file mode 100644 index 000000000..34ba0a2fa --- /dev/null +++ b/contrib/ffmpeg/libavutil/aes.h @@ -0,0 +1,45 @@ +/* + * copyright (c) 2007 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef AES_H +#define AES_H + +extern const int av_aes_size; + +struct AVAES; + +/** + * initalizes a AVAES context + * @param key_bits 128, 192 or 256 + * @param decrypt 0 for encryption, 1 for decryption + */ +int av_aes_init(struct AVAES *a, const uint8_t *key, int key_bits, int decrypt); + +/** + * encrypts / decrypts. + * @param count number of 16 byte blocks + * @param dst destination array, can be equal to src + * @param src source array, can be equal to dst + * @param iv initalization vector for CBC mode, if NULL then ECB will be used + * @param decrypt 0 for encryption, 1 for decryption + */ +void av_aes_crypt(struct AVAES *a, uint8_t *dst, uint8_t *src, int count, uint8_t *iv, int decrypt); + +#endif /* AES_H */ diff --git a/contrib/ffmpeg/libavutil/avutil.h b/contrib/ffmpeg/libavutil/avutil.h new file mode 100644 index 000000000..32bc40bfb --- /dev/null +++ b/contrib/ffmpeg/libavutil/avutil.h @@ -0,0 +1,137 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef AVUTIL_H +#define AVUTIL_H + +/** + * @file avutil.h + * external api header. + */ + + +#ifdef __cplusplus +extern "C" { +#endif + +#define AV_STRINGIFY(s) AV_TOSTRING(s) +#define AV_TOSTRING(s) #s + +#define LIBAVUTIL_VERSION_INT ((49<<16)+(4<<8)+0) +#define LIBAVUTIL_VERSION 49.4.0 +#define LIBAVUTIL_BUILD LIBAVUTIL_VERSION_INT + +#define LIBAVUTIL_IDENT "Lavu" AV_STRINGIFY(LIBAVUTIL_VERSION) + + +#include "common.h" +#include "mathematics.h" +#include "rational.h" +#include "integer.h" +#include "intfloat_readwrite.h" +#include "log.h" + +/** + * Pixel format. Notes: + * + * PIX_FMT_RGB32 is handled in an endian-specific manner. A RGBA + * color is put together as: + * (A << 24) | (R << 16) | (G << 8) | B + * This is stored as BGRA on little endian CPU architectures and ARGB on + * big endian CPUs. + * + * When the pixel format is palettized RGB (PIX_FMT_PAL8), the palettized + * image data is stored in AVFrame.data[0]. The palette is transported in + * AVFrame.data[1] and, is 1024 bytes long (256 4-byte entries) and is + * formatted the same as in PIX_FMT_RGB32 described above (i.e., it is + * also endian-specific). Note also that the individual RGB palette + * components stored in AVFrame.data[1] should be in the range 0..255. + * This is important as many custom PAL8 video codecs that were designed + * to run on the IBM VGA graphics adapter use 6-bit palette components. + */ +enum PixelFormat { + PIX_FMT_NONE= -1, + PIX_FMT_YUV420P, ///< Planar YUV 4:2:0, 12bpp, (1 Cr & Cb sample per 2x2 Y samples) + PIX_FMT_YUYV422, ///< Packed YUV 4:2:2, 16bpp, Y0 Cb Y1 Cr + PIX_FMT_RGB24, ///< Packed RGB 8:8:8, 24bpp, RGBRGB... + PIX_FMT_BGR24, ///< Packed RGB 8:8:8, 24bpp, BGRBGR... + PIX_FMT_YUV422P, ///< Planar YUV 4:2:2, 16bpp, (1 Cr & Cb sample per 2x1 Y samples) + PIX_FMT_YUV444P, ///< Planar YUV 4:4:4, 24bpp, (1 Cr & Cb sample per 1x1 Y samples) + PIX_FMT_RGB32, ///< Packed RGB 8:8:8, 32bpp, (msb)8A 8R 8G 8B(lsb), in cpu endianness + PIX_FMT_YUV410P, ///< Planar YUV 4:1:0, 9bpp, (1 Cr & Cb sample per 4x4 Y samples) + PIX_FMT_YUV411P, ///< Planar YUV 4:1:1, 12bpp, (1 Cr & Cb sample per 4x1 Y samples) + PIX_FMT_RGB565, ///< Packed RGB 5:6:5, 16bpp, (msb) 5R 6G 5B(lsb), in cpu endianness + PIX_FMT_RGB555, ///< Packed RGB 5:5:5, 16bpp, (msb)1A 5R 5G 5B(lsb), in cpu endianness most significant bit to 0 + PIX_FMT_GRAY8, ///< Y , 8bpp + PIX_FMT_MONOWHITE, ///< Y , 1bpp, 1 is white + PIX_FMT_MONOBLACK, ///< Y , 1bpp, 0 is black + PIX_FMT_PAL8, ///< 8 bit with PIX_FMT_RGB32 palette + PIX_FMT_YUVJ420P, ///< Planar YUV 4:2:0, 12bpp, full scale (jpeg) + PIX_FMT_YUVJ422P, ///< Planar YUV 4:2:2, 16bpp, full scale (jpeg) + PIX_FMT_YUVJ444P, ///< Planar YUV 4:4:4, 24bpp, full scale (jpeg) + PIX_FMT_XVMC_MPEG2_MC,///< XVideo Motion Acceleration via common packet passing(xvmc_render.h) + PIX_FMT_XVMC_MPEG2_IDCT, + PIX_FMT_UYVY422, ///< Packed YUV 4:2:2, 16bpp, Cb Y0 Cr Y1 + PIX_FMT_UYYVYY411, ///< Packed YUV 4:1:1, 12bpp, Cb Y0 Y1 Cr Y2 Y3 + PIX_FMT_BGR32, ///< Packed RGB 8:8:8, 32bpp, (msb)8A 8B 8G 8R(lsb), in cpu endianness + PIX_FMT_BGR565, ///< Packed RGB 5:6:5, 16bpp, (msb) 5B 6G 5R(lsb), in cpu endianness + PIX_FMT_BGR555, ///< Packed RGB 5:5:5, 16bpp, (msb)1A 5B 5G 5R(lsb), in cpu endianness most significant bit to 1 + PIX_FMT_BGR8, ///< Packed RGB 3:3:2, 8bpp, (msb)2B 3G 3R(lsb) + PIX_FMT_BGR4, ///< Packed RGB 1:2:1, 4bpp, (msb)1B 2G 1R(lsb) + PIX_FMT_BGR4_BYTE, ///< Packed RGB 1:2:1, 8bpp, (msb)1B 2G 1R(lsb) + PIX_FMT_RGB8, ///< Packed RGB 3:3:2, 8bpp, (msb)2R 3G 3B(lsb) + PIX_FMT_RGB4, ///< Packed RGB 1:2:1, 4bpp, (msb)2R 3G 3B(lsb) + PIX_FMT_RGB4_BYTE, ///< Packed RGB 1:2:1, 8bpp, (msb)2R 3G 3B(lsb) + PIX_FMT_NV12, ///< Planar YUV 4:2:0, 12bpp, 1 plane for Y and 1 for UV + PIX_FMT_NV21, ///< as above, but U and V bytes are swapped + + PIX_FMT_RGB32_1, ///< Packed RGB 8:8:8, 32bpp, (msb)8R 8G 8B 8A(lsb), in cpu endianness + PIX_FMT_BGR32_1, ///< Packed RGB 8:8:8, 32bpp, (msb)8B 8G 8R 8A(lsb), in cpu endianness + + PIX_FMT_GRAY16BE, ///< Y , 16bpp, big-endian + PIX_FMT_GRAY16LE, ///< Y , 16bpp, little-endian + PIX_FMT_NB, ///< number of pixel formats, DO NOT USE THIS if you want to link with shared libav* because the number of formats might differ between versions +}; + +#ifdef WORDS_BIGENDIAN +#define PIX_FMT_RGBA PIX_FMT_RGB32_1 +#define PIX_FMT_BGRA PIX_FMT_BGR32_1 +#define PIX_FMT_ARGB PIX_FMT_RGB32 +#define PIX_FMT_ABGR PIX_FMT_BGR32 +#define PIX_FMT_GRAY16 PIX_FMT_GRAY16BE +#else +#define PIX_FMT_RGBA PIX_FMT_BGR32 +#define PIX_FMT_BGRA PIX_FMT_RGB32 +#define PIX_FMT_ARGB PIX_FMT_BGR32_1 +#define PIX_FMT_ABGR PIX_FMT_RGB32_1 +#define PIX_FMT_GRAY16 PIX_FMT_GRAY16LE +#endif + +#if LIBAVUTIL_VERSION_INT < (50<<16) +#define PIX_FMT_UYVY411 PIX_FMT_UYYVYY411 +#define PIX_FMT_RGBA32 PIX_FMT_RGB32 +#define PIX_FMT_YUV422 PIX_FMT_YUYV422 +#endif + +#ifdef __cplusplus +} +#endif + +#endif /* AVUTIL_H */ diff --git a/contrib/ffmpeg/libavutil/base64.c b/contrib/ffmpeg/libavutil/base64.c new file mode 100644 index 000000000..bee800c82 --- /dev/null +++ b/contrib/ffmpeg/libavutil/base64.c @@ -0,0 +1,230 @@ +/* + * Base64.c + * Copyright (c) 2006 Ryan Martell. (rdm4@martellventures.com) + * + * 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 + */ + +/** +* @file base64.c + * @brief Base64 Encode/Decode + * @author Ryan Martell <rdm4@martellventures.com> (with lots of Michael) + */ + +#include "common.h" +#include "base64.h" + +/* ---------------- private code */ +static uint8_t map2[] = +{ + 0x3e, 0xff, 0xff, 0xff, 0x3f, 0x34, 0x35, 0x36, + 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x01, + 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, + 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, + 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x1a, 0x1b, + 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x23, + 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, + 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33 +}; + +int av_base64_decode(uint8_t * out, const char *in, int out_length) +{ + int i, v; + uint8_t *dst = out; + + v = 0; + for (i = 0; in[i] && in[i] != '='; i++) { + unsigned int index= in[i]-43; + if (index>=(sizeof(map2)/sizeof(map2[0])) || map2[index] == 0xff) + return -1; + v = (v << 6) + map2[index]; + if (i & 3) { + if (dst - out < out_length) { + *dst++ = v >> (6 - 2 * (i & 3)); + } + } + } + + return (dst - out); +} + +/***************************************************************************** +* b64_encode: stolen from VLC's http.c +* simplified by michael +* fixed edge cases and made it work from data (vs. strings) by ryan. +*****************************************************************************/ + +char *av_base64_encode(char * buf, int buf_len, uint8_t * src, int len) +{ + static const char b64[] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; + char *ret, *dst; + unsigned i_bits = 0; + int i_shift = 0; + int bytes_remaining = len; + + if (len >= UINT_MAX / 4 || + buf_len < len * 4 / 3 + 12) + return NULL; + ret = dst = buf; + if (len) { // special edge case, what should we really do here? + while (bytes_remaining) { + i_bits = (i_bits << 8) + *src++; + bytes_remaining--; + i_shift += 8; + + do { + *dst++ = b64[(i_bits << 6 >> i_shift) & 0x3f]; + i_shift -= 6; + } while (i_shift > 6 || (bytes_remaining == 0 && i_shift > 0)); + } + while ((dst - ret) & 3) + *dst++ = '='; + } + *dst = '\0'; + + return ret; +} + +// #define TEST_BASE64 + +#ifdef TEST_BASE64 +#include "avutil.h" + +int b64test() +{ + int numerr = 0; + int len; + int numtest = 1; + uint8_t decode[1000]; + struct test { + void *data; + int len; + const char *result; + } *t, tests[] = { + { + "", 0, ""}, { + "1", 1, "MQ=="}, { + "22", 2, "MjI="}, { + "333", 3, "MzMz"}, { + "4444", 4, "NDQ0NA=="}, { + "55555", 5, "NTU1NTU="}, { + "abc:def", 7, "YWJjOmRlZg=="}, { + NULL} + }; + for (t = tests; t->data; t++) { + char *str; + + av_log(NULL, AV_LOG_ERROR, "Encoding %s...\n", (char *) t->data); + str = av_base64_encode(t->data, t->len); + if (str) { + av_log(NULL, AV_LOG_ERROR, "Encoded to %s...\n", str); + if (strcmp(str, t->result) != 0) { + av_log(NULL, AV_LOG_ERROR, "failed test %d: %s != %s\n", + numtest, str, t->result); + numerr++; + } + av_free(str); + } + + av_log(NULL, AV_LOG_ERROR, "Done encoding, about to decode...\n"); + len = av_base64_decode(decode, t->result, sizeof(decode)); + if (len != t->len) { + av_log(NULL, AV_LOG_ERROR, "failed test %d: len %d != %d\n", + numtest, len, t->len); + numerr++; + } else if (memcmp(decode, t->data, t->len) != 0) { + av_log(NULL, AV_LOG_ERROR, "failed test %d: data\n", numtest); + numerr++; + } else { + av_log(NULL, AV_LOG_ERROR, "Decoded to %s\n", + (char *) t->data); + } + numtest++; + } + +#undef srand +#undef rand + + { + int test_count; + srand(123141); // time(NULL)); + for (test_count = 0; test_count < 100; test_count++) { + int size = rand() % 1024; + int ii; + uint8_t *data; + char *encoded_result; + + av_log(NULL, AV_LOG_ERROR, "Test %d: Size %d bytes...", + test_count, size); + data = (uint8_t *) av_malloc(size); + for (ii = 0; ii < size; ii++) { + data[ii] = rand() % 255; + } + + encoded_result = av_base64_encode(data, size); + if (encoded_result) { + int decode_buffer_size = size + 10; // try without 10 as well + uint8_t *decode_buffer = av_malloc(decode_buffer_size); + if (decode_buffer) { + int decoded_size = + av_base64_decode(decode_buffer, encoded_result, + decode_buffer_size); + + if (decoded_size != size) { + av_log(NULL, AV_LOG_ERROR, + "Decoded/Encoded size mismatch (%d != %d)\n", + decoded_size, size); + } else { + if (memcmp(decode_buffer, data, decoded_size) == 0) { + av_log(NULL, AV_LOG_ERROR, "Passed!\n"); + } else { + av_log(NULL, AV_LOG_ERROR, + "Failed (Data differs)!\n"); + } + } + av_free(decode_buffer); + } + + av_free(encoded_result); + } + } + } + + // these are invalid strings, that it currently decodes (which it probably shouldn't?) + { + uint8_t str[32]; + if (av_base64_decode(str, "M=M=", sizeof(str)) != -1) { + av_log(NULL, AV_LOG_ERROR, + "failed test %d: successful decode of `M=M='\n", + numtest++); + numerr++; + } + if (av_base64_decode(str, "MQ===", sizeof(str)) != -1) { + av_log(NULL, AV_LOG_ERROR, + "failed test %d: successful decode of `MQ==='\n", + numtest++); + numerr++; + } + } + + return numerr; +} +#endif + diff --git a/contrib/ffmpeg/libavutil/base64.h b/contrib/ffmpeg/libavutil/base64.h new file mode 100644 index 000000000..3d905313c --- /dev/null +++ b/contrib/ffmpeg/libavutil/base64.h @@ -0,0 +1,34 @@ +/* + * Base64.c + * Copyright (c) 2006 Ryan Martell. (rdm4@martellventures.com) + * + * 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 + */ + +/** + * decodes base64 + * param order as strncpy() + */ +int av_base64_decode(uint8_t * out, const char *in, int out_length); + +/** + * encodes base64 + * @param src data, not a string + * @param buf output string + */ +char *av_base64_encode(char * buf, int buf_len, uint8_t * src, int len); + diff --git a/contrib/ffmpeg/libavutil/bswap.h b/contrib/ffmpeg/libavutil/bswap.h new file mode 100644 index 000000000..03d613db2 --- /dev/null +++ b/contrib/ffmpeg/libavutil/bswap.h @@ -0,0 +1,175 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +/** + * @file bswap.h + * byte swap. + */ + +#ifndef __BSWAP_H__ +#define __BSWAP_H__ + +#ifdef HAVE_BYTESWAP_H +#include <byteswap.h> +#else + +#ifdef ARCH_X86_64 +# define LEGACY_REGS "=Q" +#else +# define LEGACY_REGS "=q" +#endif + +#if defined(ARCH_X86) +static av_always_inline uint16_t bswap_16(uint16_t x) +{ + __asm("rorw $8, %0" : + LEGACY_REGS (x) : + "0" (x)); + return x; +} + +static av_always_inline uint32_t bswap_32(uint32_t x) +{ +#if __CPU__ != 386 + __asm("bswap %0": + "=r" (x) : +#else + __asm("xchgb %b0,%h0\n" + " rorl $16,%0\n" + " xchgb %b0,%h0": + LEGACY_REGS (x) : +#endif + "0" (x)); + return x; +} + +static inline uint64_t bswap_64(uint64_t x) +{ +#ifdef ARCH_X86_64 + __asm("bswap %0": + "=r" (x) : + "0" (x)); + return x; +#else + union { + uint64_t ll; + struct { + uint32_t l,h; + } l; + } r; + r.l.l = bswap_32 (x); + r.l.h = bswap_32 (x>>32); + return r.ll; +#endif +} + +#elif defined(ARCH_SH4) + +static av_always_inline uint16_t bswap_16(uint16_t x) { + __asm__("swap.b %0,%0":"=r"(x):"0"(x)); + return x; +} + +static av_always_inline uint32_t bswap_32(uint32_t x) { + __asm__( + "swap.b %0,%0\n" + "swap.w %0,%0\n" + "swap.b %0,%0\n" + :"=r"(x):"0"(x)); + return x; +} + +static inline uint64_t bswap_64(uint64_t x) +{ + union { + uint64_t ll; + struct { + uint32_t l,h; + } l; + } r; + r.l.l = bswap_32 (x); + r.l.h = bswap_32 (x>>32); + return r.ll; +} +#else + +static av_always_inline uint16_t bswap_16(uint16_t x){ + return (x>>8) | (x<<8); +} + +#ifdef ARCH_ARM +static av_always_inline uint32_t bswap_32(uint32_t x){ + uint32_t t; + __asm__ ( + "eor %1, %0, %0, ror #16 \n\t" + "bic %1, %1, #0xFF0000 \n\t" + "mov %0, %0, ror #8 \n\t" + "eor %0, %0, %1, lsr #8 \n\t" + : "+r"(x), "+r"(t)); + return x; +} +#else +static av_always_inline uint32_t bswap_32(uint32_t x){ + x= ((x<<8)&0xFF00FF00) | ((x>>8)&0x00FF00FF); + return (x>>16) | (x<<16); +} +#endif + +static inline uint64_t bswap_64(uint64_t x) +{ +#if 0 + x= ((x<< 8)&0xFF00FF00FF00FF00ULL) | ((x>> 8)&0x00FF00FF00FF00FFULL); + x= ((x<<16)&0xFFFF0000FFFF0000ULL) | ((x>>16)&0x0000FFFF0000FFFFULL); + return (x>>32) | (x<<32); +#else + union { + uint64_t ll; + uint32_t l[2]; + } w, r; + w.ll = x; + r.l[0] = bswap_32 (w.l[1]); + r.l[1] = bswap_32 (w.l[0]); + return r.ll; +#endif +} +#endif /* defined(ARCH_X86) */ + +#endif /* !HAVE_BYTESWAP_H */ + +// be2me ... BigEndian to MachineEndian +// le2me ... LittleEndian to MachineEndian + +#ifdef WORDS_BIGENDIAN +#define be2me_16(x) (x) +#define be2me_32(x) (x) +#define be2me_64(x) (x) +#define le2me_16(x) bswap_16(x) +#define le2me_32(x) bswap_32(x) +#define le2me_64(x) bswap_64(x) +#else +#define be2me_16(x) bswap_16(x) +#define be2me_32(x) bswap_32(x) +#define be2me_64(x) bswap_64(x) +#define le2me_16(x) (x) +#define le2me_32(x) (x) +#define le2me_64(x) (x) +#endif + +#endif /* __BSWAP_H__ */ diff --git a/contrib/ffmpeg/libavutil/common.h b/contrib/ffmpeg/libavutil/common.h new file mode 100644 index 000000000..9ec5c7c78 --- /dev/null +++ b/contrib/ffmpeg/libavutil/common.h @@ -0,0 +1,326 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +/** + * @file common.h + * common internal and external api header. + */ + +#ifndef COMMON_H +#define COMMON_H + +#include <inttypes.h> + +#ifdef HAVE_AV_CONFIG_H +/* only include the following when compiling package */ +# include "config.h" + +# include <stdlib.h> +# include <stdio.h> +# include <string.h> +# include <ctype.h> +# include <limits.h> +# include <errno.h> +# include <math.h> +#endif /* HAVE_AV_CONFIG_H */ + +#ifndef av_always_inline +#if defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ > 0) +# define av_always_inline __attribute__((always_inline)) inline +# define av_noinline __attribute__((noinline)) +#else +# define av_always_inline inline +# define av_noinline +#endif +#endif + +#ifdef HAVE_AV_CONFIG_H +# include "internal.h" +#endif /* HAVE_AV_CONFIG_H */ + +#ifndef attribute_deprecated +#if defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ > 0) +# define attribute_deprecated __attribute__((deprecated)) +#else +# define attribute_deprecated +#endif +#endif + +#include "mem.h" + +//rounded divison & shift +#define RSHIFT(a,b) ((a) > 0 ? ((a) + ((1<<(b))>>1))>>(b) : ((a) + ((1<<(b))>>1)-1)>>(b)) +/* assume b>0 */ +#define ROUNDED_DIV(a,b) (((a)>0 ? (a) + ((b)>>1) : (a) - ((b)>>1))/(b)) +#define FFABS(a) ((a) >= 0 ? (a) : (-(a))) +#define FFSIGN(a) ((a) > 0 ? 1 : -1) + +#define FFMAX(a,b) ((a) > (b) ? (a) : (b)) +#define FFMIN(a,b) ((a) > (b) ? (b) : (a)) + +#define FFSWAP(type,a,b) do{type SWAP_tmp= b; b= a; a= SWAP_tmp;}while(0) + +/* misc math functions */ +extern const uint8_t ff_log2_tab[256]; + +static inline int av_log2(unsigned int v) +{ + int n; + + n = 0; + if (v & 0xffff0000) { + v >>= 16; + n += 16; + } + if (v & 0xff00) { + v >>= 8; + n += 8; + } + n += ff_log2_tab[v]; + + return n; +} + +static inline int av_log2_16bit(unsigned int v) +{ + int n; + + n = 0; + if (v & 0xff00) { + v >>= 8; + n += 8; + } + n += ff_log2_tab[v]; + + return n; +} + +/* median of 3 */ +static inline int mid_pred(int a, int b, int c) +{ +#ifdef HAVE_CMOV + int i=b; + asm volatile( + "cmp %2, %1 \n\t" + "cmovg %1, %0 \n\t" + "cmovg %2, %1 \n\t" + "cmp %3, %1 \n\t" + "cmovl %3, %1 \n\t" + "cmp %1, %0 \n\t" + "cmovg %1, %0 \n\t" + :"+&r"(i), "+&r"(a) + :"r"(b), "r"(c) + ); + return i; +#elif 0 + int t= (a-b)&((a-b)>>31); + a-=t; + b+=t; + b-= (b-c)&((b-c)>>31); + b+= (a-b)&((a-b)>>31); + + return b; +#else + if(a>b){ + if(c>b){ + if(c>a) b=a; + else b=c; + } + }else{ + if(b>c){ + if(c>a) b=c; + else b=a; + } + } + return b; +#endif +} + +/** + * clip a signed integer value into the amin-amax range + * @param a value to clip + * @param amin minimum value of the clip range + * @param amax maximum value of the clip range + * @return clipped value + */ +static inline int av_clip(int a, int amin, int amax) +{ + if (a < amin) return amin; + else if (a > amax) return amax; + else return a; +} + +/** + * clip a signed integer value into the 0-255 range + * @param a value to clip + * @return clipped value + */ +static inline uint8_t av_clip_uint8(int a) +{ + if (a&(~255)) return (-a)>>31; + else return a; +} + +/* math */ +int64_t ff_gcd(int64_t a, int64_t b); + +/** + * converts fourcc string to int + */ +static inline int ff_get_fourcc(const char *s){ +#ifdef HAVE_AV_CONFIG_H + assert( strlen(s)==4 ); +#endif + + return (s[0]) + (s[1]<<8) + (s[2]<<16) + (s[3]<<24); +} + +#define MKTAG(a,b,c,d) (a | (b << 8) | (c << 16) | (d << 24)) +#define MKBETAG(a,b,c,d) (d | (c << 8) | (b << 16) | (a << 24)) + +/*! + * \def GET_UTF8(val, GET_BYTE, ERROR) + * converts a utf-8 character (up to 4 bytes long) to its 32-bit ucs-4 encoded form + * \param val is the output and should be of type uint32_t. It holds the converted + * ucs-4 character and should be a left value. + * \param GET_BYTE gets utf-8 encoded bytes from any proper source. It can be + * a function or a statement whose return value or evaluated value is of type + * uint8_t. It will be executed up to 4 times for values in the valid utf-8 range, + * and up to 7 times in the general case. + * \param ERROR action that should be taken when an invalid utf-8 byte is returned + * from GET_BYTE. It should be a statement that jumps out of the macro, + * like exit(), goto, return, break, or continue. + */ +#define GET_UTF8(val, GET_BYTE, ERROR)\ + val= GET_BYTE;\ + {\ + int ones= 7 - av_log2(val ^ 255);\ + if(ones==1)\ + ERROR\ + val&= 127>>ones;\ + while(--ones > 0){\ + int tmp= GET_BYTE - 128;\ + if(tmp>>6)\ + ERROR\ + val= (val<<6) + tmp;\ + }\ + } + +/*! + * \def PUT_UTF8(val, tmp, PUT_BYTE) + * converts a 32-bit unicode character to its utf-8 encoded form (up to 4 bytes long). + * \param val is an input only argument and should be of type uint32_t. It holds + * a ucs4 encoded unicode character that is to be converted to utf-8. If + * val is given as a function it's executed only once. + * \param tmp is a temporary variable and should be of type uint8_t. It + * represents an intermediate value during conversion that is to be + * outputted by PUT_BYTE. + * \param PUT_BYTE writes the converted utf-8 bytes to any proper destination. + * It could be a function or a statement, and uses tmp as the input byte. + * For example, PUT_BYTE could be "*output++ = tmp;" PUT_BYTE will be + * executed up to 4 times for values in the valid utf-8 range and up to + * 7 times in the general case, depending on the length of the converted + * unicode character. + */ +#define PUT_UTF8(val, tmp, PUT_BYTE)\ + {\ + int bytes, shift;\ + uint32_t in = val;\ + if (in < 0x80) {\ + tmp = in;\ + PUT_BYTE\ + } else {\ + bytes = (av_log2(in) + 4) / 5;\ + shift = (bytes - 1) * 6;\ + tmp = (256 - (256 >> bytes)) | (in >> shift);\ + PUT_BYTE\ + while (shift >= 6) {\ + shift -= 6;\ + tmp = 0x80 | ((in >> shift) & 0x3f);\ + PUT_BYTE\ + }\ + }\ + } + +#if defined(ARCH_X86) || defined(ARCH_POWERPC) +#if defined(ARCH_X86_64) +static inline uint64_t read_time(void) +{ + uint64_t a, d; + asm volatile( "rdtsc\n\t" + : "=a" (a), "=d" (d) + ); + return (d << 32) | (a & 0xffffffff); +} +#elif defined(ARCH_X86_32) +static inline long long read_time(void) +{ + long long l; + asm volatile( "rdtsc\n\t" + : "=A" (l) + ); + return l; +} +#else //FIXME check ppc64 +static inline uint64_t read_time(void) +{ + uint32_t tbu, tbl, temp; + + /* from section 2.2.1 of the 32-bit PowerPC PEM */ + __asm__ __volatile__( + "1:\n" + "mftbu %2\n" + "mftb %0\n" + "mftbu %1\n" + "cmpw %2,%1\n" + "bne 1b\n" + : "=r"(tbl), "=r"(tbu), "=r"(temp) + : + : "cc"); + + return (((uint64_t)tbu)<<32) | (uint64_t)tbl; +} +#endif + +#define START_TIMER \ +uint64_t tend;\ +uint64_t tstart= read_time();\ + +#define STOP_TIMER(id) \ +tend= read_time();\ +{\ + static uint64_t tsum=0;\ + static int tcount=0;\ + static int tskip_count=0;\ + if(tcount<2 || tend - tstart < FFMAX(8*tsum/tcount, 2000)){\ + tsum+= tend - tstart;\ + tcount++;\ + }else\ + tskip_count++;\ + if(((tcount+tskip_count)&(tcount+tskip_count-1))==0){\ + av_log(NULL, AV_LOG_DEBUG, "%"PRIu64" dezicycles in %s, %d runs, %d skips\n", tsum*10/tcount, id, tcount, tskip_count);\ + }\ +} +#else +#define START_TIMER +#define STOP_TIMER(id) {} +#endif + +#endif /* COMMON_H */ diff --git a/contrib/ffmpeg/libavutil/crc.c b/contrib/ffmpeg/libavutil/crc.c new file mode 100644 index 000000000..02fb860b8 --- /dev/null +++ b/contrib/ffmpeg/libavutil/crc.c @@ -0,0 +1,111 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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" +#include "crc.h" + +#if LIBAVUTIL_VERSION_INT < (50<<16) +AVCRC *av_crcEDB88320; +AVCRC *av_crc04C11DB7; +AVCRC *av_crc8005 ; +AVCRC *av_crc07 ; +#else +AVCRC av_crcEDB88320[257]; +AVCRC av_crc04C11DB7[257]; +AVCRC av_crc8005 [257]; +AVCRC av_crc07 [257]; +#endif + +/** + * Inits a crc table. + * @param ctx must be an array of sizeof(AVCRC)*257 or sizeof(AVCRC)*1024 + * @param cts_size size of ctx in bytes + * @return <0 on failure + */ +int av_crc_init(AVCRC *ctx, int le, int bits, uint32_t poly, int ctx_size){ + int i, j; + uint32_t c; + + if (bits < 8 || bits > 32 || poly >= (1LL<<bits)) + return -1; + if (ctx_size != sizeof(AVCRC)*257 && ctx_size != sizeof(AVCRC)*1024) + return -1; + + for (i = 0; i < 256; i++) { + if (le) { + for (c = i, j = 0; j < 8; j++) + c = (c>>1)^(poly & (-(c&1))); + ctx[i] = c; + } else { + for (c = i << 24, j = 0; j < 8; j++) + c = (c<<1) ^ ((poly<<(32-bits)) & (((int32_t)c)>>31) ); + ctx[i] = bswap_32(c); + } + } + ctx[256]=1; +#ifndef CONFIG_SMALL + if(ctx_size >= sizeof(AVCRC)*1024) + for (i = 0; i < 256; i++) + for(j=0; j<3; j++) + ctx[256*(j+1) + i]= (ctx[256*j + i]>>8) ^ ctx[ ctx[256*j + i]&0xFF ]; +#endif + + return 0; +} + +uint32_t av_crc(const AVCRC *ctx, uint32_t crc, const uint8_t *buffer, size_t length){ + const uint8_t *end= buffer+length; + +#ifndef CONFIG_SMALL + if(!ctx[256]) + while(buffer<end-3){ + crc ^= le2me_32(*(uint32_t*)buffer); buffer+=4; + crc = ctx[3*256 + ( crc &0xFF)] + ^ctx[2*256 + ((crc>>8 )&0xFF)] + ^ctx[1*256 + ((crc>>16)&0xFF)] + ^ctx[0*256 + ((crc>>24) )]; + } +#endif + while(buffer<end) + crc = ctx[((uint8_t)crc) ^ *buffer++] ^ (crc >> 8); + + return crc; +} + +#ifdef TEST +#undef printf +main(){ + uint8_t buf[1999]; + int i; + int p[4][4]={{1, 32, 0xedb88320L, 0x3D5CDD04}, + {0, 32, 0x04c11db7L, 0xC0F5BAE0}, + {0, 16, 0x8005 , 0x1FBB }, + {0, 8, 0x07 , 0xE3 },}; + AVCRC ctx[1 ? 1024:257]; + + for(i=0; i<sizeof(buf); i++) + buf[i]= i+i*i; + + for(i=0; i<4; i++){ + av_crc_init(ctx, p[i][0], p[i][1], p[i][2], sizeof(ctx)); + printf("crc %08X =%X\n", p[i][2], av_crc(ctx, 0, buf, sizeof(buf))); + } +} +#endif diff --git a/contrib/ffmpeg/libavutil/crc.h b/contrib/ffmpeg/libavutil/crc.h new file mode 100644 index 000000000..1f6431992 --- /dev/null +++ b/contrib/ffmpeg/libavutil/crc.h @@ -0,0 +1,42 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef CRC_H +#define CRC_H + +typedef uint32_t AVCRC; + +#if LIBAVUTIL_VERSION_INT < (50<<16) +extern AVCRC *av_crcEDB88320; +extern AVCRC *av_crc04C11DB7; +extern AVCRC *av_crc8005 ; +extern AVCRC *av_crc07 ; +#else +extern AVCRC av_crcEDB88320[]; +extern AVCRC av_crc04C11DB7[]; +extern AVCRC av_crc8005 []; +extern AVCRC av_crc07 []; +#endif + +int av_crc_init(AVCRC *ctx, int le, int bits, uint32_t poly, int ctx_size); +uint32_t av_crc(const AVCRC *ctx, uint32_t start_crc, const uint8_t *buffer, size_t length); + +#endif /* CRC_H */ + diff --git a/contrib/ffmpeg/libavutil/fifo.c b/contrib/ffmpeg/libavutil/fifo.c new file mode 100644 index 000000000..8ac3a0cb5 --- /dev/null +++ b/contrib/ffmpeg/libavutil/fifo.c @@ -0,0 +1,114 @@ +/* + * A very simple circular buffer FIFO implementation + * Copyright (c) 2000, 2001, 2002 Fabrice Bellard + * Copyright (c) 2006 Roman Shaposhnik + * + * 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" +#include "fifo.h" + +int av_fifo_init(AVFifoBuffer *f, int size) +{ + f->wptr = f->rptr = + f->buffer = av_malloc(size); + f->end = f->buffer + size; + if (!f->buffer) + return -1; + return 0; +} + +void av_fifo_free(AVFifoBuffer *f) +{ + av_free(f->buffer); +} + +int av_fifo_size(AVFifoBuffer *f) +{ + int size = f->wptr - f->rptr; + if (size < 0) + size += f->end - f->buffer; + return size; +} + +/** + * Get data from the fifo (returns -1 if not enough data). + */ +int av_fifo_read(AVFifoBuffer *f, uint8_t *buf, int buf_size) +{ + return av_fifo_generic_read(f, buf_size, NULL, buf); +} + +/** + * Resizes a FIFO. + */ +void av_fifo_realloc(AVFifoBuffer *f, unsigned int new_size) { + unsigned int old_size= f->end - f->buffer; + + if(old_size < new_size){ + int len= av_fifo_size(f); + AVFifoBuffer f2; + + av_fifo_init(&f2, new_size); + av_fifo_read(f, f2.buffer, len); + f2.wptr += len; + av_free(f->buffer); + *f= f2; + } +} + +void av_fifo_write(AVFifoBuffer *f, const uint8_t *buf, int size) +{ + do { + int len = FFMIN(f->end - f->wptr, size); + memcpy(f->wptr, buf, len); + f->wptr += len; + if (f->wptr >= f->end) + f->wptr = f->buffer; + buf += len; + size -= len; + } while (size > 0); +} + + +/** get data from the fifo (return -1 if not enough data) */ +int av_fifo_generic_read(AVFifoBuffer *f, int buf_size, void (*func)(void*, void*, int), void* dest) +{ + int size = av_fifo_size(f); + + if (size < buf_size) + return -1; + do { + int len = FFMIN(f->end - f->rptr, buf_size); + if(func) func(dest, f->rptr, len); + else{ + memcpy(dest, f->rptr, len); + dest = (uint8_t*)dest + len; + } + av_fifo_drain(f, len); + buf_size -= len; + } while (buf_size > 0); + return 0; +} + +/** discard data from the fifo */ +void av_fifo_drain(AVFifoBuffer *f, int size) +{ + f->rptr += size; + if (f->rptr >= f->end) + f->rptr -= f->end - f->buffer; +} diff --git a/contrib/ffmpeg/libavutil/fifo.h b/contrib/ffmpeg/libavutil/fifo.h new file mode 100644 index 000000000..e1e85293d --- /dev/null +++ b/contrib/ffmpeg/libavutil/fifo.h @@ -0,0 +1,100 @@ +/* + * 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 + */ + +/** + * @file fifo.h + * A very simple circular buffer FIFO implementation. + */ + +#ifndef FIFO_H +#define FIFO_H + +typedef struct AVFifoBuffer { + uint8_t *buffer; + uint8_t *rptr, *wptr, *end; +} AVFifoBuffer; + +/** + * Initializes an AVFifoBuffer. + * @param *f AVFifoBuffer to initialize + * @param size of FIFO + * @return <0 for failure >=0 otherwise + */ +int av_fifo_init(AVFifoBuffer *f, int size); + +/** + * Frees an AVFifoBuffer. + * @param *f AVFifoBuffer to free + */ +void av_fifo_free(AVFifoBuffer *f); + +/** + * Returns the amount of data in bytes in the AVFifoBuffer, that is the + * amount of data you can read from it. + * @param *f AVFifoBuffer to read from + * @return size + */ +int av_fifo_size(AVFifoBuffer *f); + +/** + * Reads data from an AVFifoBuffer. + * @param *f AVFifoBuffer to read from + * @param *buf data destination + * @param buf_size number of bytes to read + */ +int av_fifo_read(AVFifoBuffer *f, uint8_t *buf, int buf_size); + +/** + * Feeds data from an AVFifoBuffer to a user supplied callback. + * @param *f AVFifoBuffer to read from + * @param buf_size number of bytes to read + * @param *func generic read function + * @param *dest data destination + */ +int av_fifo_generic_read(AVFifoBuffer *f, int buf_size, void (*func)(void*, void*, int), void* dest); + +/** + * Writes data into an AVFifoBuffer. + * @param *f AVFifoBuffer to write to + * @param *buf data source + * @param size data size + */ +void av_fifo_write(AVFifoBuffer *f, const uint8_t *buf, int size); + +/** + * Resizes an AVFifoBuffer. + * @param *f AVFifoBuffer to resize + * @param size new AVFifoBuffer size in bytes + */ +void av_fifo_realloc(AVFifoBuffer *f, unsigned int size); + +/** + * Reads and discards the specified amount of data from an AVFifoBuffer. + * @param *f AVFifoBuffer to read from + * @param size amount of data to read in bytes + */ +void av_fifo_drain(AVFifoBuffer *f, int size); + +static inline uint8_t av_fifo_peek(AVFifoBuffer *f, int offs) +{ + uint8_t *ptr = f->rptr + offs; + if (ptr >= f->end) + ptr -= f->end - f->buffer; + return *ptr; +} +#endif /* FIFO_H */ diff --git a/contrib/ffmpeg/libavutil/integer.c b/contrib/ffmpeg/libavutil/integer.c new file mode 100644 index 000000000..3269a366a --- /dev/null +++ b/contrib/ffmpeg/libavutil/integer.c @@ -0,0 +1,197 @@ +/* + * arbitrary precision integers + * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + * + */ + +/** + * @file integer.c + * arbitrary precision integers. + * @author Michael Niedermayer <michaelni@gmx.at> + */ + +#include "common.h" +#include "integer.h" + +AVInteger av_add_i(AVInteger a, AVInteger b){ + int i, carry=0; + + for(i=0; i<AV_INTEGER_SIZE; i++){ + carry= (carry>>16) + a.v[i] + b.v[i]; + a.v[i]= carry; + } + return a; +} + +AVInteger av_sub_i(AVInteger a, AVInteger b){ + int i, carry=0; + + for(i=0; i<AV_INTEGER_SIZE; i++){ + carry= (carry>>16) + a.v[i] - b.v[i]; + a.v[i]= carry; + } + return a; +} + +int av_log2_i(AVInteger a){ + int i; + + for(i=AV_INTEGER_SIZE-1; i>=0; i--){ + if(a.v[i]) + return av_log2_16bit(a.v[i]) + 16*i; + } + return -1; +} + +AVInteger av_mul_i(AVInteger a, AVInteger b){ + AVInteger out; + int i, j; + int na= (av_log2_i(a)+16) >> 4; + int nb= (av_log2_i(b)+16) >> 4; + + memset(&out, 0, sizeof(out)); + + for(i=0; i<na; i++){ + unsigned int carry=0; + + if(a.v[i]) + for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){ + carry= (carry>>16) + out.v[j] + a.v[i]*b.v[j-i]; + out.v[j]= carry; + } + } + + return out; +} + +int av_cmp_i(AVInteger a, AVInteger b){ + int i; + int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1]; + if(v) return (v>>16)|1; + + for(i=AV_INTEGER_SIZE-2; i>=0; i--){ + int v= a.v[i] - b.v[i]; + if(v) return (v>>16)|1; + } + return 0; +} + +AVInteger av_shr_i(AVInteger a, int s){ + AVInteger out; + int i; + + for(i=0; i<AV_INTEGER_SIZE; i++){ + int index= i + (s>>4); + unsigned int v=0; + if(index+1<AV_INTEGER_SIZE && index+1>=0) v = a.v[index+1]<<16; + if(index <AV_INTEGER_SIZE && index >=0) v+= a.v[index ]; + out.v[i]= v >> (s&15); + } + return out; +} + +AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){ + int i= av_log2_i(a) - av_log2_i(b); + AVInteger quot_temp; + if(!quot) quot = "_temp; + + assert((int16_t)a[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b[AV_INTEGER_SIZE-1] >= 0); + assert(av_log2(b)>=0); + + if(i > 0) + b= av_shr_i(b, -i); + + memset(quot, 0, sizeof(AVInteger)); + + while(i-- >= 0){ + *quot= av_shr_i(*quot, -1); + if(av_cmp_i(a, b) >= 0){ + a= av_sub_i(a, b); + quot->v[0] += 1; + } + b= av_shr_i(b, 1); + } + return a; +} + +AVInteger av_div_i(AVInteger a, AVInteger b){ + AVInteger quot; + av_mod_i(", a, b); + return quot; +} + +AVInteger av_int2i(int64_t a){ + AVInteger out; + int i; + + for(i=0; i<AV_INTEGER_SIZE; i++){ + out.v[i]= a; + a>>=16; + } + return out; +} + +int64_t av_i2int(AVInteger a){ + int i; + int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1]; + + for(i= AV_INTEGER_SIZE-2; i>=0; i--){ + out = (out<<16) + a.v[i]; + } + return out; +} + +#if 0 +#undef NDEBUG +#include <assert.h> + +const uint8_t ff_log2_tab[256]={ + 0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, + 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 +}; + +main(){ + int64_t a,b; + + for(a=7; a<256*256*256; a+=13215){ + for(b=3; b<256*256*256; b+=27118){ + AVInteger ai= av_int2i(a); + AVInteger bi= av_int2i(b); + + assert(av_i2int(ai) == a); + assert(av_i2int(bi) == b); + assert(av_i2int(av_add_i(ai,bi)) == a+b); + assert(av_i2int(av_sub_i(ai,bi)) == a-b); + assert(av_i2int(av_mul_i(ai,bi)) == a*b); + assert(av_i2int(av_shr_i(ai, 9)) == a>>9); + assert(av_i2int(av_shr_i(ai,-9)) == a<<9); + assert(av_i2int(av_shr_i(ai, 17)) == a>>17); + assert(av_i2int(av_shr_i(ai,-17)) == a<<17); + assert(av_log2_i(ai) == av_log2(a)); + assert(av_i2int(av_div_i(ai,bi)) == a/b); + } + } +} +#endif diff --git a/contrib/ffmpeg/libavutil/integer.h b/contrib/ffmpeg/libavutil/integer.h new file mode 100644 index 000000000..2a4d70316 --- /dev/null +++ b/contrib/ffmpeg/libavutil/integer.h @@ -0,0 +1,82 @@ +/* + * arbitrary precision integers + * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + * + */ + +/** + * @file integer.h + * arbitrary precision integers + * @author Michael Niedermayer <michaelni@gmx.at> + */ + +#ifndef INTEGER_H +#define INTEGER_H + +#define AV_INTEGER_SIZE 8 + +typedef struct AVInteger{ + uint16_t v[AV_INTEGER_SIZE]; +} AVInteger; + +AVInteger av_add_i(AVInteger a, AVInteger b); +AVInteger av_sub_i(AVInteger a, AVInteger b); + +/** + * returns the rounded down value of the logarithm of base 2 of the given AVInteger. + * this is simply the index of the most significant bit which is 1. Or 0 of all bits are 0 + */ +int av_log2_i(AVInteger a); +AVInteger av_mul_i(AVInteger a, AVInteger b); + +/** + * returns 0 if a==b, 1 if a>b and -1 if a<b. + */ +int av_cmp_i(AVInteger a, AVInteger b); + +/** + * bitwise shift. + * @param s the number of bits by which the value should be shifted right, may be negative for shifting left + */ +AVInteger av_shr_i(AVInteger a, int s); + +/** + * returns a % b. + * @param quot a/b will be stored here + */ +AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b); + +/** + * returns a/b. + */ +AVInteger av_div_i(AVInteger a, AVInteger b); + +/** + * converts the given int64_t to an AVInteger. + */ +AVInteger av_int2i(int64_t a); + +/** + * converts the given AVInteger to an int64_t. + * if the AVInteger is too large to fit into an int64_t, + * then only the least significant 64bit will be used + */ +int64_t av_i2int(AVInteger a); + +#endif // INTEGER_H diff --git a/contrib/ffmpeg/libavutil/internal.h b/contrib/ffmpeg/libavutil/internal.h new file mode 100644 index 000000000..eefbfa1e4 --- /dev/null +++ b/contrib/ffmpeg/libavutil/internal.h @@ -0,0 +1,293 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +/** + * @file internal.h + * common internal api header. + */ + +#ifndef INTERNAL_H +#define INTERNAL_H + +#ifndef attribute_used +#if defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ > 0) +# define attribute_used __attribute__((used)) +#else +# define attribute_used +#endif +#endif + +#ifndef attribute_unused +#if defined(__GNUC__) +# define attribute_unused __attribute__((unused)) +#else +# define attribute_unused +#endif +#endif + +#ifndef M_PI +#define M_PI 3.14159265358979323846 +#endif + +#ifndef INT16_MIN +#define INT16_MIN (-0x7fff-1) +#endif + +#ifndef INT16_MAX +#define INT16_MAX 0x7fff +#endif + +#ifndef INT32_MIN +#define INT32_MIN (-0x7fffffff-1) +#endif + +#ifndef INT32_MAX +#define INT32_MAX 0x7fffffff +#endif + +#ifndef UINT32_MAX +#define UINT32_MAX 0xffffffff +#endif + +#ifndef INT64_MIN +#define INT64_MIN (-0x7fffffffffffffffLL-1) +#endif + +#ifndef INT64_MAX +#define INT64_MAX INT64_C(9223372036854775807) +#endif + +#ifndef UINT64_MAX +#define UINT64_MAX UINT64_C(0xFFFFFFFFFFFFFFFF) +#endif + +#ifndef INT_BIT +# if INT_MAX != 2147483647 +# define INT_BIT 64 +# else +# define INT_BIT 32 +# endif +#endif + +#if ( defined(__PIC__) || defined(__pic__) ) && ! defined(PIC) +# define PIC +#endif + +#include "intreadwrite.h" +#include "bswap.h" + +#include <stddef.h> +#ifndef offsetof +# define offsetof(T,F) ((unsigned int)((char *)&((T *)0)->F)) +#endif + +#ifdef __MINGW32__ +# ifdef _DEBUG +# define DEBUG +# endif + +# define snprintf _snprintf +# define vsnprintf _vsnprintf + +# ifdef CONFIG_WINCE +# define perror(a) +# define abort() +# endif + +/* __MINGW32__ end */ +#elif defined (CONFIG_OS2) +/* OS/2 EMX */ + +# include <float.h> + +#endif /* !__MINGW32__ && CONFIG_OS2 */ + +#ifdef USE_FASTMEMCPY +# include "libvo/fastmemcpy.h" +#endif + +// Use rip-relative addressing if compiling PIC code on x86-64. +#if defined(__MINGW32__) || defined(__CYGWIN__) || \ + defined(__OS2__) || (defined (__OpenBSD__) && !defined(__ELF__)) +# if defined(ARCH_X86_64) && defined(PIC) +# define MANGLE(a) "_" #a"(%%rip)" +# else +# define MANGLE(a) "_" #a +# endif +#else +# if defined(ARCH_X86_64) && defined(PIC) +# define MANGLE(a) #a"(%%rip)" +# elif defined(CONFIG_DARWIN) +# define MANGLE(a) "_" #a +# else +# define MANGLE(a) #a +# endif +#endif + +/* debug stuff */ + +#if !defined(DEBUG) && !defined(NDEBUG) +# define NDEBUG +#endif +#include <assert.h> + +/* dprintf macros */ +#ifdef DEBUG +# define dprintf(pctx, ...) av_log(pctx, AV_LOG_DEBUG, __VA_ARGS__) +#else +# define dprintf(pctx, ...) +#endif + +#define av_abort() do { av_log(NULL, AV_LOG_ERROR, "Abort at %s:%d\n", __FILE__, __LINE__); abort(); } while (0) + +/* math */ + +extern const uint32_t ff_inverse[256]; + +#if defined(ARCH_X86) +# define FASTDIV(a,b) \ + ({\ + int ret,dmy;\ + asm volatile(\ + "mull %3"\ + :"=d"(ret),"=a"(dmy)\ + :"1"(a),"g"(ff_inverse[b])\ + );\ + ret;\ + }) +#elif defined(ARCH_ARMV4L) +# define FASTDIV(a,b) \ + ({\ + int ret,dmy;\ + asm volatile(\ + "umull %1, %0, %2, %3"\ + :"=&r"(ret),"=&r"(dmy)\ + :"r"(a),"r"(ff_inverse[b])\ + );\ + ret;\ + }) +#elif defined(CONFIG_FASTDIV) +# define FASTDIV(a,b) ((uint32_t)((((uint64_t)a)*ff_inverse[b])>>32)) +#else +# define FASTDIV(a,b) ((a)/(b)) +#endif + +extern const uint8_t ff_sqrt_tab[128]; + +static inline int ff_sqrt(int a) +{ + int ret=0; + int s; + int ret_sq=0; + + if(a<128) return ff_sqrt_tab[a]; + + for(s=15; s>=0; s--){ + int b= ret_sq + (1<<(s*2)) + (ret<<s)*2; + if(b<=a){ + ret_sq=b; + ret+= 1<<s; + } + } + return ret; +} + +#if defined(ARCH_X86) +#define MASK_ABS(mask, level)\ + asm volatile(\ + "cdq \n\t"\ + "xorl %1, %0 \n\t"\ + "subl %1, %0 \n\t"\ + : "+a" (level), "=&d" (mask)\ + ); +#else +#define MASK_ABS(mask, level)\ + mask= level>>31;\ + level= (level^mask)-mask; +#endif + +#ifdef HAVE_CMOV +#define COPY3_IF_LT(x,y,a,b,c,d)\ +asm volatile (\ + "cmpl %0, %3 \n\t"\ + "cmovl %3, %0 \n\t"\ + "cmovl %4, %1 \n\t"\ + "cmovl %5, %2 \n\t"\ + : "+r" (x), "+r" (a), "+r" (c)\ + : "r" (y), "r" (b), "r" (d)\ +); +#else +#define COPY3_IF_LT(x,y,a,b,c,d)\ +if((y)<(x)){\ + (x)=(y);\ + (a)=(b);\ + (c)=(d);\ +} +#endif + +/* avoid usage of various functions */ +#define malloc please_use_av_malloc +#define free please_use_av_free +#define realloc please_use_av_realloc +#define time time_is_forbidden_due_to_security_issues +#define rand rand_is_forbidden_due_to_state_trashing +#define srand srand_is_forbidden_due_to_state_trashing +#define sprintf sprintf_is_forbidden_due_to_security_issues_use_snprintf +#define strcat strcat_is_forbidden_due_to_security_issues_use_pstrcat +#define exit exit_is_forbidden +#if !(defined(LIBAVFORMAT_BUILD) || defined(_FRAMEHOOK_H)) +#define printf please_use_av_log +#define fprintf please_use_av_log +#endif + +#define CHECKED_ALLOCZ(p, size)\ +{\ + p= av_mallocz(size);\ + if(p==NULL && (size)!=0){\ + perror("malloc");\ + goto fail;\ + }\ +} + +#ifndef HAVE_LRINTF +/* XXX: add ISOC specific test to avoid specific BSD testing. */ +/* better than nothing implementation. */ +/* btw, rintf() is existing on fbsd too -- alex */ +static av_always_inline long int lrintf(float x) +{ +#ifdef __MINGW32__ +# ifdef ARCH_X86_32 + int32_t i; + asm volatile( + "fistpl %0\n\t" + : "=m" (i) : "t" (x) : "st" + ); + return i; +# else + /* XXX: incorrect, but make it compile */ + return (int)(x + (x < 0 ? -0.5 : 0.5)); +# endif /* ARCH_X86_32 */ +#else + return (int)(rint(x)); +#endif /* __MINGW32__ */ +} +#endif /* HAVE_LRINTF */ + +#endif /* INTERNAL_H */ diff --git a/contrib/ffmpeg/libavutil/intfloat_readwrite.c b/contrib/ffmpeg/libavutil/intfloat_readwrite.c new file mode 100644 index 000000000..261cf76c3 --- /dev/null +++ b/contrib/ffmpeg/libavutil/intfloat_readwrite.c @@ -0,0 +1,97 @@ +/* + * portable IEEE float/double read/write functions + * + * Copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +/** + * @file intfloat_readwrite.c + * Portable IEEE float/double read/write functions. + */ + +#include "common.h" +#include "intfloat_readwrite.h" + +double av_int2dbl(int64_t v){ + if(v+v > 0xFFEULL<<52) + return 0.0/0.0; + return ldexp(((v&((1LL<<52)-1)) + (1LL<<52)) * (v>>63|1), (v>>52&0x7FF)-1075); +} + +float av_int2flt(int32_t v){ + if(v+v > 0xFF000000U) + return 0.0/0.0; + return ldexp(((v&0x7FFFFF) + (1<<23)) * (v>>31|1), (v>>23&0xFF)-150); +} + +double av_ext2dbl(const AVExtFloat ext){ + uint64_t m = 0; + int e, i; + + for (i = 0; i < 8; i++) + m = (m<<8) + ext.mantissa[i]; + e = (((int)ext.exponent[0]&0x7f)<<8) | ext.exponent[1]; + if (e == 0x7fff && m) + return 0.0/0.0; + e -= 16383 + 63; /* In IEEE 80 bits, the whole (i.e. 1.xxxx) + * mantissa bit is written as opposed to the + * single and double precision formats */ + if (ext.exponent[0]&0x80) + m= -m; + return ldexp(m, e); +} + +int64_t av_dbl2int(double d){ + int e; + if ( !d) return 0; + else if(d-d) return 0x7FF0000000000000LL + ((int64_t)(d<0)<<63) + (d!=d); + d= frexp(d, &e); + return (int64_t)(d<0)<<63 | (e+1022LL)<<52 | (int64_t)((fabs(d)-0.5)*(1LL<<53)); +} + +int32_t av_flt2int(float d){ + int e; + if ( !d) return 0; + else if(d-d) return 0x7F800000 + ((d<0)<<31) + (d!=d); + d= frexp(d, &e); + return (d<0)<<31 | (e+126)<<23 | (int64_t)((fabs(d)-0.5)*(1<<24)); +} + +AVExtFloat av_dbl2ext(double d){ + struct AVExtFloat ext= {{0}}; + int e, i; double f; uint64_t m; + + f = fabs(frexp(d, &e)); + if (f >= 0.5 && f < 1) { + e += 16382; + ext.exponent[0] = e>>8; + ext.exponent[1] = e; + m = (uint64_t)ldexp(f, 64); + for (i=0; i < 8; i++) + ext.mantissa[i] = m>>(56-(i<<3)); + } else if (f != 0.0) { + ext.exponent[0] = 0x7f; ext.exponent[1] = 0xff; + if (f != 1/0.0) + ext.mantissa[0] = ~0; + } + if (d < 0) + ext.exponent[0] |= 0x80; + return ext; +} + diff --git a/contrib/ffmpeg/libavutil/intfloat_readwrite.h b/contrib/ffmpeg/libavutil/intfloat_readwrite.h new file mode 100644 index 000000000..c535b64c8 --- /dev/null +++ b/contrib/ffmpeg/libavutil/intfloat_readwrite.h @@ -0,0 +1,39 @@ +/* + * copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef INTFLOAT_READWRITE_H +#define INTFLOAT_READWRITE_H + +#include "common.h" + +/* IEEE 80 bits extended float */ +typedef struct AVExtFloat { + uint8_t exponent[2]; + uint8_t mantissa[8]; +} AVExtFloat; + +double av_int2dbl(int64_t v); +float av_int2flt(int32_t v); +double av_ext2dbl(const AVExtFloat ext); +int64_t av_dbl2int(double d); +int32_t av_flt2int(float d); +AVExtFloat av_dbl2ext(double d); + +#endif /* INTFLOAT_READWRITE_H */ diff --git a/contrib/ffmpeg/libavutil/intreadwrite.h b/contrib/ffmpeg/libavutil/intreadwrite.h new file mode 100644 index 000000000..7225f0b67 --- /dev/null +++ b/contrib/ffmpeg/libavutil/intreadwrite.h @@ -0,0 +1,99 @@ +/* + * 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 + */ + +#ifndef INTREADWRITE_H +#define INTREADWRITE_H + +#ifdef __GNUC__ + +struct unaligned_64 { uint64_t l; } __attribute__((packed)); +struct unaligned_32 { uint32_t l; } __attribute__((packed)); +struct unaligned_16 { uint16_t l; } __attribute__((packed)); + +#define LD16(a) (((const struct unaligned_16 *) (a))->l) +#define LD32(a) (((const struct unaligned_32 *) (a))->l) +#define LD64(a) (((const struct unaligned_64 *) (a))->l) + +#define ST16(a, b) (((struct unaligned_16 *) (a))->l) = (b) +#define ST32(a, b) (((struct unaligned_32 *) (a))->l) = (b) + +#else /* __GNUC__ */ + +#define LD16(a) (*((uint16_t*)(a))) +#define LD32(a) (*((uint32_t*)(a))) +#define LD64(a) (*((uint64_t*)(a))) + +#define ST16(a, b) *((uint16_t*)(a)) = (b) +#define ST32(a, b) *((uint32_t*)(a)) = (b) + +#endif /* !__GNUC__ */ + +/* endian macros */ +#define AV_RB8(x) (((uint8_t*)(x))[0]) +#define AV_WB8(p, d) { ((uint8_t*)(p))[0] = (d); } + +#define AV_RB16(x) ((((uint8_t*)(x))[0] << 8) | ((uint8_t*)(x))[1]) +#define AV_WB16(p, d) { \ + ((uint8_t*)(p))[1] = (d); \ + ((uint8_t*)(p))[0] = (d)>>8; } + +#define AV_RB24(x) ((((uint8_t*)(x))[0] << 16) | \ + (((uint8_t*)(x))[1] << 8) | \ + ((uint8_t*)(x))[2]) +#define AV_WB24(p, d) { \ + ((uint8_t*)(p))[2] = (d); \ + ((uint8_t*)(p))[1] = (d)>>8; \ + ((uint8_t*)(p))[0] = (d)>>16; } + +#define AV_RB32(x) ((((uint8_t*)(x))[0] << 24) | \ + (((uint8_t*)(x))[1] << 16) | \ + (((uint8_t*)(x))[2] << 8) | \ + ((uint8_t*)(x))[3]) +#define AV_WB32(p, d) { \ + ((uint8_t*)(p))[3] = (d); \ + ((uint8_t*)(p))[2] = (d)>>8; \ + ((uint8_t*)(p))[1] = (d)>>16; \ + ((uint8_t*)(p))[0] = (d)>>24; } + +#define AV_RL8(x) AV_RB8(x) +#define AV_WL8(p, d) AV_WB8(p, d) + +#define AV_RL16(x) ((((uint8_t*)(x))[1] << 8) | ((uint8_t*)(x))[0]) +#define AV_WL16(p, d) { \ + ((uint8_t*)(p))[0] = (d); \ + ((uint8_t*)(p))[1] = (d)>>8; } + +#define AV_RL24(x) ((((uint8_t*)(x))[2] << 16) | \ + (((uint8_t*)(x))[1] << 8) | \ + ((uint8_t*)(x))[0]) +#define AV_WL24(p, d) { \ + ((uint8_t*)(p))[0] = (d); \ + ((uint8_t*)(p))[1] = (d)>>8; \ + ((uint8_t*)(p))[2] = (d)>>16; } + +#define AV_RL32(x) ((((uint8_t*)(x))[3] << 24) | \ + (((uint8_t*)(x))[2] << 16) | \ + (((uint8_t*)(x))[1] << 8) | \ + ((uint8_t*)(x))[0]) +#define AV_WL32(p, d) { \ + ((uint8_t*)(p))[0] = (d); \ + ((uint8_t*)(p))[1] = (d)>>8; \ + ((uint8_t*)(p))[2] = (d)>>16; \ + ((uint8_t*)(p))[3] = (d)>>24; } + +#endif /* INTREADWRITE_H */ diff --git a/contrib/ffmpeg/libavutil/lls.c b/contrib/ffmpeg/libavutil/lls.c new file mode 100644 index 000000000..aa9467dce --- /dev/null +++ b/contrib/ffmpeg/libavutil/lls.c @@ -0,0 +1,151 @@ +/* + * linear least squares model + * + * Copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +/** + * @file lls.c + * linear least squares model + */ + +#include <math.h> +#include <string.h> + +#include "lls.h" + +#ifdef TEST +#define av_log(a,b,...) printf(__VA_ARGS__) +#endif + +void av_init_lls(LLSModel *m, int indep_count){ + memset(m, 0, sizeof(LLSModel)); + + m->indep_count= indep_count; +} + +void av_update_lls(LLSModel *m, double *var, double decay){ + int i,j; + + for(i=0; i<=m->indep_count; i++){ + for(j=i; j<=m->indep_count; j++){ + m->covariance[i][j] *= decay; + m->covariance[i][j] += var[i]*var[j]; + } + } +} + +void av_solve_lls(LLSModel *m, double threshold, int min_order){ + int i,j,k; + double (*factor)[MAX_VARS+1]= &m->covariance[1][0]; + double (*covar )[MAX_VARS+1]= &m->covariance[1][1]; + double *covar_y = m->covariance[0]; + int count= m->indep_count; + + for(i=0; i<count; i++){ + for(j=i; j<count; j++){ + double sum= covar[i][j]; + + for(k=i-1; k>=0; k--) + sum -= factor[i][k]*factor[j][k]; + + if(i==j){ + if(sum < threshold) + sum= 1.0; + factor[i][i]= sqrt(sum); + }else + factor[j][i]= sum / factor[i][i]; + } + } + for(i=0; i<count; i++){ + double sum= covar_y[i+1]; + for(k=i-1; k>=0; k--) + sum -= factor[i][k]*m->coeff[0][k]; + m->coeff[0][i]= sum / factor[i][i]; + } + + for(j=count-1; j>=min_order; j--){ + for(i=j; i>=0; i--){ + double sum= m->coeff[0][i]; + for(k=i+1; k<=j; k++) + sum -= factor[k][i]*m->coeff[j][k]; + m->coeff[j][i]= sum / factor[i][i]; + } + + m->variance[j]= covar_y[0]; + for(i=0; i<=j; i++){ + double sum= m->coeff[j][i]*covar[i][i] - 2*covar_y[i+1]; + for(k=0; k<i; k++) + sum += 2*m->coeff[j][k]*covar[k][i]; + m->variance[j] += m->coeff[j][i]*sum; + } + } +} + +double av_evaluate_lls(LLSModel *m, double *param, int order){ + int i; + double out= 0; + + for(i=0; i<=order; i++) + out+= param[i]*m->coeff[order][i]; + + return out; +} + +#ifdef TEST + +#include <stdlib.h> +#include <stdio.h> + +int main(){ + LLSModel m; + int i, order; + + av_init_lls(&m, 3); + + for(i=0; i<100; i++){ + double var[4]; + double eval, variance; +#if 0 + var[1] = rand() / (double)RAND_MAX; + var[2] = rand() / (double)RAND_MAX; + var[3] = rand() / (double)RAND_MAX; + + var[2]= var[1] + var[3]/2; + + var[0] = var[1] + var[2] + var[3] + var[1]*var[2]/100; +#else + var[0] = (rand() / (double)RAND_MAX - 0.5)*2; + var[1] = var[0] + rand() / (double)RAND_MAX - 0.5; + var[2] = var[1] + rand() / (double)RAND_MAX - 0.5; + var[3] = var[2] + rand() / (double)RAND_MAX - 0.5; +#endif + av_update_lls(&m, var, 0.99); + av_solve_lls(&m, 0.001, 0); + for(order=0; order<3; order++){ + eval= av_evaluate_lls(&m, var+1, order); + av_log(NULL, AV_LOG_DEBUG, "real:%f order:%d pred:%f var:%f coeffs:%f %f %f\n", + var[0], order, eval, sqrt(m.variance[order] / (i+1)), + m.coeff[order][0], m.coeff[order][1], m.coeff[order][2]); + } + } + return 0; +} + +#endif diff --git a/contrib/ffmpeg/libavutil/lls.h b/contrib/ffmpeg/libavutil/lls.h new file mode 100644 index 000000000..59ad2e958 --- /dev/null +++ b/contrib/ffmpeg/libavutil/lls.h @@ -0,0 +1,45 @@ +/* + * linear least squares model + * + * Copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef LLS_H +#define LLS_H + +#define MAX_VARS 32 + +//FIXME avoid direct access to LLSModel from outside + +/** + * Linear least squares model. + */ +typedef struct LLSModel{ + double covariance[MAX_VARS+1][MAX_VARS+1]; + double coeff[MAX_VARS][MAX_VARS]; + double variance[MAX_VARS]; + int indep_count; +}LLSModel; + +void av_init_lls(LLSModel *m, int indep_count); +void av_update_lls(LLSModel *m, double *param, double decay); +void av_solve_lls(LLSModel *m, double threshold, int min_order); +double av_evaluate_lls(LLSModel *m, double *param, int order); + +#endif diff --git a/contrib/ffmpeg/libavutil/log.c b/contrib/ffmpeg/libavutil/log.c new file mode 100644 index 000000000..4fd503d0d --- /dev/null +++ b/contrib/ffmpeg/libavutil/log.c @@ -0,0 +1,82 @@ +/* + * log functions + * Copyright (c) 2003 Michel Bardiaux + * + * 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 + */ + +/** + * @file log.c + * log. + */ + +#include "avutil.h" + +int av_log_level = AV_LOG_INFO; + +void av_log_default_callback(void* ptr, int level, const char* fmt, va_list vl) +{ + static int print_prefix=1; + AVClass* avc= ptr ? *(AVClass**)ptr : NULL; + if(level>av_log_level) + return; +#undef fprintf + if(print_prefix && avc) { + fprintf(stderr, "[%s @ %p]", avc->item_name(ptr), avc); + } +#define fprintf please_use_av_log + + print_prefix= strstr(fmt, "\n") != NULL; + + vfprintf(stderr, fmt, vl); +} + +#if LIBAVUTIL_VERSION_INT < (50<<16) +static void (*av_log_callback)(void*, int, const char*, va_list) = av_log_default_callback; +#else +void (*av_vlog)(void*, int, const char*, va_list) = av_log_default_callback; +#endif + +void av_log(void* avcl, int level, const char *fmt, ...) +{ + va_list vl; + va_start(vl, fmt); + av_vlog(avcl, level, fmt, vl); + va_end(vl); +} + +#if LIBAVUTIL_VERSION_INT < (50<<16) +void av_vlog(void* avcl, int level, const char *fmt, va_list vl) +{ + av_log_callback(avcl, level, fmt, vl); +} + +int av_log_get_level(void) +{ + return av_log_level; +} + +void av_log_set_level(int level) +{ + av_log_level = level; +} + +void av_log_set_callback(void (*callback)(void*, int, const char*, va_list)) +{ + av_log_callback = callback; +} +#endif diff --git a/contrib/ffmpeg/libavutil/log.h b/contrib/ffmpeg/libavutil/log.h new file mode 100644 index 000000000..fa88f5fb2 --- /dev/null +++ b/contrib/ffmpeg/libavutil/log.h @@ -0,0 +1,116 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef LOG_H +#define LOG_H + +#include <stdarg.h> + +/** + * Used by av_log + */ +typedef struct AVCLASS AVClass; +struct AVCLASS { + const char* class_name; + const char* (*item_name)(void*); /* actually passing a pointer to an AVCodecContext + or AVFormatContext, which begin with an AVClass. + Needed because av_log is in libavcodec and has no visibility + of AVIn/OutputFormat */ + const struct AVOption *option; +}; + +/* av_log API */ + +#if LIBAVUTIL_VERSION_INT < (50<<16) +#define AV_LOG_QUIET -1 +#define AV_LOG_FATAL 0 +#define AV_LOG_ERROR 0 +#define AV_LOG_WARNING 1 +#define AV_LOG_INFO 1 +#define AV_LOG_VERBOSE 1 +#define AV_LOG_DEBUG 2 +#else +#define AV_LOG_QUIET -8 + +/** + * something went really wrong and we will crash now + */ +#define AV_LOG_PANIC 0 + +/** + * something went wrong and recovery is not possible + * like no header in a format which depends on it or a combination + * of parameters which are not allowed + */ +#define AV_LOG_FATAL 8 + +/** + * something went wrong and cannot losslessly be recovered + * but not all future data is affected + */ +#define AV_LOG_ERROR 16 + +/** + * something somehow does not look correct / something which may or may not + * lead to some problems like use of -vstrict -2 + */ +#define AV_LOG_WARNING 24 + +#define AV_LOG_INFO 32 +#define AV_LOG_VERBOSE 40 + +/** + * stuff which is only useful for libav* developers + */ +#define AV_LOG_DEBUG 48 +#endif +extern int av_log_level; + +/** + * Send the specified message to the log if the level is less than or equal to + * the current av_log_level. By default, all logging messages are sent to + * stderr. This behavior can be altered by setting a different av_vlog callback + * function. + * + * @param avcl A pointer to an arbitrary struct of which the first field is a + * pointer to an AVClass struct. + * @param level The importance level of the message, lower values signifying + * higher importance. + * @param fmt The format string (printf-compatible) that specifies how + * subsequent arguments are converted to output. + * @see av_vlog + */ +#ifdef __GNUC__ +extern void av_log(void*, int level, const char *fmt, ...) __attribute__ ((__format__ (__printf__, 3, 4))); +#else +extern void av_log(void*, int level, const char *fmt, ...); +#endif + +#if LIBAVUTIL_VERSION_INT < (50<<16) +extern void av_vlog(void*, int level, const char *fmt, va_list); +extern int av_log_get_level(void); +extern void av_log_set_level(int); +extern void av_log_set_callback(void (*)(void*, int, const char*, va_list)); +extern void av_log_default_callback(void* ptr, int level, const char* fmt, va_list vl); +#else +extern void (*av_vlog)(void*, int, const char*, va_list); +#endif + +#endif /* LOG_H */ diff --git a/contrib/ffmpeg/libavutil/lzo.c b/contrib/ffmpeg/libavutil/lzo.c new file mode 100644 index 000000000..d3849a743 --- /dev/null +++ b/contrib/ffmpeg/libavutil/lzo.c @@ -0,0 +1,273 @@ +/* + * 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 8 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; +} + +#ifdef INBUF_PADDED +#define GETB(c) (*(c).in++) +#else +#define GETB(c) get_byte(&(c)) +#endif + +/** + * \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; +} + +//#define UNALIGNED_LOADSTORE +#define BUILTIN_MEMCPY +#ifdef UNALIGNED_LOADSTORE +#define COPY2(d, s) *(uint16_t *)(d) = *(uint16_t *)(s); +#define COPY4(d, s) *(uint32_t *)(d) = *(uint32_t *)(s); +#elif defined(BUILTIN_MEMCPY) +#define COPY2(d, s) memcpy(d, s, 2); +#define COPY4(d, s) memcpy(d, s, 4); +#else +#define COPY2(d, s) (d)[0] = (s)[0]; (d)[1] = (s)[1]; +#define COPY4(d, s) (d)[0] = (s)[0]; (d)[1] = (s)[1]; (d)[2] = (s)[2]; (d)[3] = (s)[3]; +#endif + +/** + * \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 (cnt > c->in_end - src) { + cnt = FFMAX(c->in_end - src, 0); + c->error |= LZO_INPUT_DEPLETED; + } + if (cnt > c->out_end - dst) { + cnt = FFMAX(c->out_end - dst, 0); + c->error |= LZO_OUTPUT_FULL; + } +#if defined(INBUF_PADDED) && defined(OUTBUF_PADDED) + COPY4(dst, src); + 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 || src > dst) { + c->error |= LZO_INVALID_BACKPTR; + return; + } + if (cnt > c->out_end - dst) { + cnt = FFMAX(c->out_end - dst, 0); + c->error |= LZO_OUTPUT_FULL; + } + if (back == 1) { + memset(dst, *src, cnt); + dst += cnt; + } else { +#ifdef OUTBUF_PADDED + COPY2(dst, src); + COPY2(dst + 2, src + 2); + src += 4; + dst += 4; + cnt -= 4; + if (cnt > 0) { + COPY2(dst, src); + COPY2(dst + 2, src + 2); + COPY2(dst + 4, src + 4); + COPY2(dst + 6, src + 6); + 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) { + int state= 0; + 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 = GETB(c); + if (x > 17) { + copy(&c, x - 17); + x = GETB(c); + if (x < 16) c.error |= LZO_ERROR; + } + if (c.in > c.in_end) + c.error |= LZO_INPUT_DEPLETED; + while (!c.error) { + int cnt, back; + if (x > 15) { + if (x > 63) { + cnt = (x >> 5) - 1; + back = (GETB(c) << 3) + ((x >> 2) & 7) + 1; + } else if (x > 31) { + cnt = get_len(&c, x, 31); + x = GETB(c); + back = (GETB(c) << 6) + (x >> 2) + 1; + } else { + cnt = get_len(&c, x, 7); + back = (1 << 14) + ((x & 8) << 11); + x = GETB(c); + back += (GETB(c) << 6) + (x >> 2); + if (back == (1 << 14)) { + if (cnt != 1) + c.error |= LZO_ERROR; + break; + } + } + } else if(!state){ + cnt = get_len(&c, x, 15); + copy(&c, cnt + 3); + x = GETB(c); + if (x > 15) + continue; + cnt = 1; + back = (1 << 11) + (GETB(c) << 2) + (x >> 2) + 1; + } else { + cnt = 0; + back = (GETB(c) << 2) + (x >> 2) + 1; + } + copy_backptr(&c, back, cnt + 2); + state= + cnt = x & 3; + copy(&c, cnt); + x = GETB(c); + } + *inlen = c.in_end - c.in; + if (c.in > c.in_end) + *inlen = 0; + *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; +#ifdef LIBLZO + if (lzo1x_decompress_safe(comp, inlen, decomp, &outlen, NULL)) +#elif defined(LIBLZO_UNSAFE) + if (lzo1x_decompress(comp, inlen, decomp, &outlen, NULL)) +#else + if (lzo1x_decode(decomp, &outlen, comp, &inlen)) +#endif + 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 diff --git a/contrib/ffmpeg/libavutil/lzo.h b/contrib/ffmpeg/libavutil/lzo.h new file mode 100644 index 000000000..5b3d98f40 --- /dev/null +++ b/contrib/ffmpeg/libavutil/lzo.h @@ -0,0 +1,35 @@ +/* + * 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 + */ + +#ifndef LZO_H +#define LZO_H + +#define LZO_INPUT_DEPLETED 1 +#define LZO_OUTPUT_FULL 2 +#define LZO_INVALID_BACKPTR 4 +#define LZO_ERROR 8 + +#define LZO_INPUT_PADDING 8 +#define LZO_OUTPUT_PADDING 12 + +int lzo1x_decode(void *out, int *outlen, void *in, int *inlen); + +#endif diff --git a/contrib/ffmpeg/libavutil/mathematics.c b/contrib/ffmpeg/libavutil/mathematics.c new file mode 100644 index 000000000..4be027d9d --- /dev/null +++ b/contrib/ffmpeg/libavutil/mathematics.c @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +/** + * @file mathematics.c + * Miscellaneous math routines and tables. + */ + +#include "common.h" +#include "mathematics.h" + +const uint8_t ff_sqrt_tab[128]={ + 0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, + 9, 9, 9, 9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11 +}; + +const uint8_t ff_log2_tab[256]={ + 0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, + 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 +}; + +int64_t ff_gcd(int64_t a, int64_t b){ + if(b) return ff_gcd(b, a%b); + else return a; +} + +int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd){ + int64_t r=0; + assert(c > 0); + assert(b >=0); + assert(rnd >=0 && rnd<=5 && rnd!=4); + + if(a<0 && a != INT64_MIN) return -av_rescale_rnd(-a, b, c, rnd ^ ((rnd>>1)&1)); + + if(rnd==AV_ROUND_NEAR_INF) r= c/2; + else if(rnd&1) r= c-1; + + if(b<=INT_MAX && c<=INT_MAX){ + if(a<=INT_MAX) + return (a * b + r)/c; + else + return a/c*b + (a%c*b + r)/c; + }else{ +#if 1 + uint64_t a0= a&0xFFFFFFFF; + uint64_t a1= a>>32; + uint64_t b0= b&0xFFFFFFFF; + uint64_t b1= b>>32; + uint64_t t1= a0*b1 + a1*b0; + uint64_t t1a= t1<<32; + int i; + + a0 = a0*b0 + t1a; + a1 = a1*b1 + (t1>>32) + (a0<t1a); + a0 += r; + a1 += a0<r; + + for(i=63; i>=0; i--){ +// int o= a1 & 0x8000000000000000ULL; + a1+= a1 + ((a0>>i)&1); + t1+=t1; + if(/*o || */c <= a1){ + a1 -= c; + t1++; + } + } + return t1; + } +#else + AVInteger ai; + ai= av_mul_i(av_int2i(a), av_int2i(b)); + ai= av_add_i(ai, av_int2i(r)); + + return av_i2int(av_div_i(ai, av_int2i(c))); + } +#endif +} + +int64_t av_rescale(int64_t a, int64_t b, int64_t c){ + return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF); +} + +int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq){ + int64_t b= bq.num * (int64_t)cq.den; + int64_t c= cq.num * (int64_t)bq.den; + return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF); +} +#if 0 +#include "integer.h" +#undef printf +main(){ + int64_t a,b,c,d,e; + + for(a=7; a<(1LL<<62); a+=a/3+1){ + for(b=3; b<(1LL<<62); b+=b/4+1){ + for(c=9; c<(1LL<<62); c+=(c*2)/5+3){ + int64_t r= c/2; + AVInteger ai; + ai= av_mul_i(av_int2i(a), av_int2i(b)); + ai= av_add_i(ai, av_int2i(r)); + + d= av_i2int(av_div_i(ai, av_int2i(c))); + + e= av_rescale(a,b,c); + + if((double)a * (double)b / (double)c > (1LL<<63)) + continue; + + if(d!=e) printf("%"PRId64"*%"PRId64"/%"PRId64"= %"PRId64"=%"PRId64"\n", a, b, c, d, e); + } + } + } +} +#endif diff --git a/contrib/ffmpeg/libavutil/mathematics.h b/contrib/ffmpeg/libavutil/mathematics.h new file mode 100644 index 000000000..0b74b254b --- /dev/null +++ b/contrib/ffmpeg/libavutil/mathematics.h @@ -0,0 +1,51 @@ +/* + * copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef MATHEMATICS_H +#define MATHEMATICS_H + +#include "rational.h" + +enum AVRounding { + AV_ROUND_ZERO = 0, ///< round toward zero + AV_ROUND_INF = 1, ///< round away from zero + AV_ROUND_DOWN = 2, ///< round toward -infinity + AV_ROUND_UP = 3, ///< round toward +infinity + AV_ROUND_NEAR_INF = 5, ///< round to nearest and halfway cases away from zero +}; + +/** + * rescale a 64bit integer with rounding to nearest. + * a simple a*b/c isn't possible as it can overflow + */ +int64_t av_rescale(int64_t a, int64_t b, int64_t c); + +/** + * rescale a 64bit integer with specified rounding. + * a simple a*b/c isn't possible as it can overflow + */ +int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding); + +/** + * rescale a 64bit integer by 2 rational numbers. + */ +int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq); + +#endif /* MATHEMATICS_H */ diff --git a/contrib/ffmpeg/libavutil/md5.c b/contrib/ffmpeg/libavutil/md5.c new file mode 100644 index 000000000..f71703124 --- /dev/null +++ b/contrib/ffmpeg/libavutil/md5.c @@ -0,0 +1,180 @@ +/* + * Copyright (C) 2006 Michael Niedermayer (michaelni@gmx.at) + * Copyright (C) 2003-2005 by Christopher R. Hertel (crh@ubiqx.mn.org) + * + * 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 + * + * References: + * IETF RFC 1321: The MD5 Message-Digest Algorithm + * Ron Rivest. IETF, April, 1992 + * + * based on http://ubiqx.org/libcifs/source/Auth/MD5.c + * from Christopher R. Hertel (crh@ubiqx.mn.org) + * simplified, cleaned and IMO redundant comments removed by michael + * + * if you use gcc, then version 4.1 or later and -fomit-frame-pointer is + * strongly recommended + */ + +#include "common.h" +#include <string.h> +#include "md5.h" + +typedef struct AVMD5{ + uint64_t len; + uint8_t block[64]; + uint32_t ABCD[4]; +} AVMD5; + +const int av_md5_size= sizeof(AVMD5); + +static const uint8_t S[4][4] = { + { 7, 12, 17, 22 }, /* Round 1 */ + { 5, 9, 14, 20 }, /* Round 2 */ + { 4, 11, 16, 23 }, /* Round 3 */ + { 6, 10, 15, 21 } /* Round 4 */ +}; + +static const uint32_t T[64] = { // T[i]= fabs(sin(i+1)<<32) + 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, /* Round 1 */ + 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, + 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, + 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, + + 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, /* Round 2 */ + 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8, + 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, + 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, + + 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, /* Round 3 */ + 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, + 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, + 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, + + 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, /* Round 4 */ + 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1, + 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, + 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391, +}; + +#define CORE(i, a, b, c, d) \ + t = S[i>>4][i&3];\ + a += T[i];\ +\ + if(i<32){\ + if(i<16) a += (d ^ (b&(c^d))) + X[ i &15 ];\ + else a += (c ^ (d&(c^b))) + X[ (1+5*i)&15 ];\ + }else{\ + if(i<48) a += (b^c^d) + X[ (5+3*i)&15 ];\ + else a += (c^(b|~d)) + X[ ( 7*i)&15 ];\ + }\ + a = b + (( a << t ) | ( a >> (32 - t) )); + +static void body(uint32_t ABCD[4], uint32_t X[16]){ + + int t; + int i attribute_unused; + unsigned int a= ABCD[3]; + unsigned int b= ABCD[2]; + unsigned int c= ABCD[1]; + unsigned int d= ABCD[0]; + +#ifdef WORDS_BIGENDIAN + for(i=0; i<16; i++) + X[i]= bswap_32(X[i]); +#endif + +#ifdef CONFIG_SMALL + for( i = 0; i < 64; i++ ){ + CORE(i,a,b,c,d) + t=d; d=c; c=b; b=a; a=t; + } +#else +#define CORE2(i) CORE(i,a,b,c,d) CORE((i+1),d,a,b,c) CORE((i+2),c,d,a,b) CORE((i+3),b,c,d,a) +#define CORE4(i) CORE2(i) CORE2((i+4)) CORE2((i+8)) CORE2((i+12)) +CORE4(0) CORE4(16) CORE4(32) CORE4(48) +#endif + + ABCD[0] += d; + ABCD[1] += c; + ABCD[2] += b; + ABCD[3] += a; +} + +void av_md5_init(AVMD5 *ctx){ + ctx->len = 0; + + ctx->ABCD[0] = 0x10325476; + ctx->ABCD[1] = 0x98badcfe; + ctx->ABCD[2] = 0xefcdab89; + ctx->ABCD[3] = 0x67452301; +} + +void av_md5_update(AVMD5 *ctx, const uint8_t *src, const int len){ + int i, j; + + j= ctx->len & 63; + ctx->len += len; + + for( i = 0; i < len; i++ ){ + ctx->block[j++] = src[i]; + if( 64 == j ){ + body(ctx->ABCD, (uint32_t*) ctx->block); + j = 0; + } + } +} + +void av_md5_final(AVMD5 *ctx, uint8_t *dst){ + int i; + uint64_t finalcount= le2me_64(ctx->len<<3); + + av_md5_update(ctx, "\200", 1); + while((ctx->len & 63)<56) + av_md5_update(ctx, "", 1); + + av_md5_update(ctx, &finalcount, 8); + + for(i=0; i<4; i++) + ((uint32_t*)dst)[i]= le2me_32(ctx->ABCD[3-i]); +} + +void av_md5_sum(uint8_t *dst, const uint8_t *src, const int len){ + AVMD5 ctx[1]; + + av_md5_init(ctx); + av_md5_update(ctx, src, len); + av_md5_final(ctx, dst); +} + +#ifdef TEST +#include <stdio.h> +#undef printf +main(){ + uint64_t md5val; + int i; + uint8_t in[1000]; + + for(i=0; i<1000; i++) in[i]= i*i; + av_md5_sum( (uint8_t*)&md5val, in, 1000); printf("%"PRId64"\n", md5val); + av_md5_sum( (uint8_t*)&md5val, in, 63); printf("%"PRId64"\n", md5val); + av_md5_sum( (uint8_t*)&md5val, in, 64); printf("%"PRId64"\n", md5val); + av_md5_sum( (uint8_t*)&md5val, in, 65); printf("%"PRId64"\n", md5val); + for(i=0; i<1000; i++) in[i]= i % 127; + av_md5_sum( (uint8_t*)&md5val, in, 999); printf("%"PRId64"\n", md5val); +} +#endif diff --git a/contrib/ffmpeg/libavutil/md5.h b/contrib/ffmpeg/libavutil/md5.h new file mode 100644 index 000000000..8d1b4b5fe --- /dev/null +++ b/contrib/ffmpeg/libavutil/md5.h @@ -0,0 +1,34 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef MD5_H +#define MD5_H + +extern const int av_md5_size; + +struct AVMD5; + +void av_md5_init(struct AVMD5 *ctx); +void av_md5_update(struct AVMD5 *ctx, const uint8_t *src, const int len); +void av_md5_final(struct AVMD5 *ctx, uint8_t *dst); +void av_md5_sum(uint8_t *dst, const uint8_t *src, const int len); + +#endif /* MD5_H */ + diff --git a/contrib/ffmpeg/libavutil/mem.c b/contrib/ffmpeg/libavutil/mem.c new file mode 100644 index 000000000..a91ac4a07 --- /dev/null +++ b/contrib/ffmpeg/libavutil/mem.c @@ -0,0 +1,152 @@ +/* + * default memory allocator for libavutil + * Copyright (c) 2002 Fabrice Bellard. + * + * 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 + */ + +/** + * @file mem.c + * default memory allocator for libavutil. + */ + +#include "common.h" + +/* here we can use OS dependent allocation functions */ +#undef malloc +#undef free +#undef realloc + +#ifdef HAVE_MALLOC_H +#include <malloc.h> +#endif + +/* you can redefine av_malloc and av_free in your project to use your + memory allocator. You do not need to suppress this file because the + linker will do it automatically */ + +void *av_malloc(unsigned int size) +{ + void *ptr; +#ifdef CONFIG_MEMALIGN_HACK + long diff; +#endif + + /* let's disallow possible ambiguous cases */ + if(size > (INT_MAX-16) ) + return NULL; + +#ifdef CONFIG_MEMALIGN_HACK + ptr = malloc(size+16); + if(!ptr) + return ptr; + diff= ((-(long)ptr - 1)&15) + 1; + ptr += diff; + ((char*)ptr)[-1]= diff; +#elif defined (HAVE_MEMALIGN) + ptr = memalign(16,size); + /* Why 64? + Indeed, we should align it: + on 4 for 386 + on 16 for 486 + on 32 for 586, PPro - k6-III + on 64 for K7 (maybe for P3 too). + Because L1 and L2 caches are aligned on those values. + But I don't want to code such logic here! + */ + /* Why 16? + because some cpus need alignment, for example SSE2 on P4, & most RISC cpus + it will just trigger an exception and the unaligned load will be done in the + exception handler or it will just segfault (SSE2 on P4) + Why not larger? because i didnt see a difference in benchmarks ... + */ + /* benchmarks with p3 + memalign(64)+1 3071,3051,3032 + memalign(64)+2 3051,3032,3041 + memalign(64)+4 2911,2896,2915 + memalign(64)+8 2545,2554,2550 + memalign(64)+16 2543,2572,2563 + memalign(64)+32 2546,2545,2571 + memalign(64)+64 2570,2533,2558 + + btw, malloc seems to do 8 byte alignment by default here + */ +#else + ptr = malloc(size); +#endif + return ptr; +} + +void *av_realloc(void *ptr, unsigned int size) +{ +#ifdef CONFIG_MEMALIGN_HACK + int diff; +#endif + + /* let's disallow possible ambiguous cases */ + if(size > (INT_MAX-16) ) + return NULL; + +#ifdef CONFIG_MEMALIGN_HACK + //FIXME this isn't aligned correctly, though it probably isn't needed + if(!ptr) return av_malloc(size); + diff= ((char*)ptr)[-1]; + return realloc(ptr - diff, size + diff) + diff; +#else + return realloc(ptr, size); +#endif +} + +void av_free(void *ptr) +{ + /* XXX: this test should not be needed on most libcs */ + if (ptr) +#ifdef CONFIG_MEMALIGN_HACK + free(ptr - ((char*)ptr)[-1]); +#else + free(ptr); +#endif +} + +void av_freep(void *arg) +{ + void **ptr= (void**)arg; + av_free(*ptr); + *ptr = NULL; +} + +void *av_mallocz(unsigned int size) +{ + void *ptr; + + ptr = av_malloc(size); + if (ptr) + memset(ptr, 0, size); + return ptr; +} + +char *av_strdup(const char *s) +{ + char *ptr; + int len; + len = strlen(s) + 1; + ptr = av_malloc(len); + if (ptr) + memcpy(ptr, s, len); + return ptr; +} + diff --git a/contrib/ffmpeg/libavutil/mem.h b/contrib/ffmpeg/libavutil/mem.h new file mode 100644 index 000000000..4ebdad8f5 --- /dev/null +++ b/contrib/ffmpeg/libavutil/mem.h @@ -0,0 +1,65 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +/** + * @file mem.h + * Memory handling functions. + */ + +#ifndef AV_MEM_H +#define AV_MEM_H + +#ifdef __GNUC__ + #define DECLARE_ALIGNED(n,t,v) t v __attribute__ ((aligned (n))) +#else + #define DECLARE_ALIGNED(n,t,v) __declspec(align(n)) t v +#endif + +/** + * Memory allocation of size byte with alignment suitable for all + * memory accesses (including vectors if available on the + * CPU). av_malloc(0) must return a non NULL pointer. + */ +void *av_malloc(unsigned int size); + +/** + * av_realloc semantics (same as glibc): if ptr is NULL and size > 0, + * identical to malloc(size). If size is zero, it is identical to + * free(ptr) and NULL is returned. + */ +void *av_realloc(void *ptr, unsigned int size); + +/** + * Free memory which has been allocated with av_malloc(z)() or av_realloc(). + * NOTE: ptr = NULL is explicetly allowed + * Note2: it is recommended that you use av_freep() instead + */ +void av_free(void *ptr); + +void *av_mallocz(unsigned int size); +char *av_strdup(const char *s); + +/** + * Frees memory and sets the pointer to NULL. + * @param ptr pointer to the pointer which should be freed + */ +void av_freep(void *ptr); + +#endif /* AV_MEM_H */ diff --git a/contrib/ffmpeg/libavutil/random.c b/contrib/ffmpeg/libavutil/random.c new file mode 100644 index 000000000..c3e71e699 --- /dev/null +++ b/contrib/ffmpeg/libavutil/random.c @@ -0,0 +1,104 @@ +/* + * Mersenne Twister Random Algorithm + * Copyright (c) 2006 Ryan Martell. + * Based on A C-program for MT19937, with initialization improved 2002/1/26. Coded by + * Takuji Nishimura and Makoto Matsumoto. + * + * 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 + */ + + +/** +see http://en.wikipedia.org/wiki/Mersenne_twister for an explanation of this algorithm. +*/ +#include <stdio.h> +#include "random.h" + +//#define DEBUG + +#ifdef DEBUG +#include "common.h" +#include "log.h" +#endif + + +/* Period parameters */ +#define M 397 +#define A 0x9908b0df /* constant vector a */ +#define UPPER_MASK 0x80000000 /* most significant w-r bits */ +#define LOWER_MASK 0x7fffffff /* least significant r bits */ + +/** initializes mt[AV_RANDOM_N] with a seed */ +void av_init_random(unsigned int seed, AVRandomState *state) +{ + int index; + + /* + This differs from the wikipedia article. Source is from the Makoto + Makoto Matsumoto and Takuji Nishimura code, with the following comment: + */ + /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ + /* In the previous versions, MSBs of the seed affect */ + /* only MSBs of the array mt[]. */ + state->mt[0] = seed & 0xffffffff; + for (index = 1; index < AV_RANDOM_N; index++) { + unsigned int prev= state->mt[index - 1]; + state->mt[index] = (1812433253UL * (prev ^ (prev>>30)) + index) & 0xffffffff; + } + state->index= index; // will cause it to generate untempered numbers the first iteration +} + +/** generate AV_RANDOM_N words at one time (which will then be tempered later) (av_random calls this; you shouldn't) */ +void av_random_generate_untempered_numbers(AVRandomState *state) +{ + int kk; + unsigned int y; + + for (kk = 0; kk < AV_RANDOM_N - M; kk++) { + y = (state->mt[kk] & UPPER_MASK) | (state->mt[kk + 1] & LOWER_MASK); + state->mt[kk] = state->mt[kk + M] ^ (y >> 1) ^ ((y&1)*A); + } + for (; kk < AV_RANDOM_N - 1; kk++) { + y = (state->mt[kk] & UPPER_MASK) | (state->mt[kk + 1] & LOWER_MASK); + state->mt[kk] = state->mt[kk + (M - AV_RANDOM_N)] ^ (y >> 1) ^ ((y&1)*A); + } + y = (state->mt[AV_RANDOM_N - 1] & UPPER_MASK) | (state->mt[0] & LOWER_MASK); + state->mt[AV_RANDOM_N - 1] = state->mt[M - 1] ^ (y >> 1) ^ ((y&1)*A); + state->index = 0; +} + +#ifdef DEBUG +void av_benchmark_random(void) +{ + int x=0; + int i, j; + AVRandomState state; + + av_init_random(0xdeadbeef, &state); + for (j = 0; j < 100; j++) { + START_TIMER; + x+= av_random(&state); + STOP_TIMER("first call to av_random"); + for (i = 1; i < AV_RANDOM_N; i++) { + START_TIMER; + x+= av_random(&state); + STOP_TIMER("AV_RANDOM_N calls of av_random"); + } + } + av_log(NULL, AV_LOG_ERROR, "final value:%X\n", x); +} +#endif diff --git a/contrib/ffmpeg/libavutil/random.h b/contrib/ffmpeg/libavutil/random.h new file mode 100644 index 000000000..d9d08a5de --- /dev/null +++ b/contrib/ffmpeg/libavutil/random.h @@ -0,0 +1,69 @@ +/* + * Mersenne Twister Random Algorithm + * Copyright (c) 2006 Ryan Martell. + * Based on A C-program for MT19937, with initialization improved 2002/1/26. Coded by + * Takuji Nishimura and Makoto Matsumoto. + * + * 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 + */ + +#ifndef AV_RANDOM_H +#define AV_RANDOM_H + +#define AV_RANDOM_N 624 + +typedef struct { + unsigned int mt[AV_RANDOM_N]; ///< the array for the state vector + int index; ///< current untempered value we use as the base. +} AVRandomState; + + +void av_init_random(unsigned int seed, AVRandomState *state); ///< to be inlined, the struct must be visible, so it doesn't make sense to try and keep it opaque with malloc/free like calls +void av_random_generate_untempered_numbers(AVRandomState *state); ///< Regenerate the untempered numbers (must be done every 624 iterations, or it will loop) + +/** generates a random number on [0,0xffffffff]-interval */ +static inline unsigned int av_random(AVRandomState *state) +{ + unsigned int y; + + // regenerate the untempered numbers if we should... + if (state->index >= AV_RANDOM_N) + av_random_generate_untempered_numbers(state); + + // grab one... + y = state->mt[state->index++]; + + /* Now temper (Mersenne Twister coefficients) The coefficients for MT19937 are.. */ + y ^= (y >> 11); + y ^= (y << 7) & 0x9d2c5680; + y ^= (y << 15) & 0xefc60000; + y ^= (y >> 18); + + return y; +} + +/** return random in range [0-1] as double */ +static inline double av_random_real1(AVRandomState *state) +{ + /* divided by 2^32-1 */ + return av_random(state) * (1.0 / 4294967296.0); +} + +// only available if DEBUG is defined in the .c file +void av_benchmark_random(void); +#endif // AV_RANDOM_H + diff --git a/contrib/ffmpeg/libavutil/rational.c b/contrib/ffmpeg/libavutil/rational.c new file mode 100644 index 000000000..ac0c9d371 --- /dev/null +++ b/contrib/ffmpeg/libavutil/rational.c @@ -0,0 +1,104 @@ +/* + * Rational numbers + * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + * + */ + +/** + * @file rational.c + * Rational numbers + * @author Michael Niedermayer <michaelni@gmx.at> + */ + +//#include <math.h> +#include <limits.h> + +#include "common.h" +#include "mathematics.h" +#include "rational.h" + +int av_reduce(int *dst_nom, int *dst_den, int64_t nom, int64_t den, int64_t max){ + AVRational a0={0,1}, a1={1,0}; + int sign= (nom<0) ^ (den<0); + int64_t gcd= ff_gcd(FFABS(nom), FFABS(den)); + + if(gcd){ + nom = FFABS(nom)/gcd; + den = FFABS(den)/gcd; + } + if(nom<=max && den<=max){ + a1= (AVRational){nom, den}; + den=0; + } + + while(den){ + uint64_t x = nom / den; + int64_t next_den= nom - den*x; + int64_t a2n= x*a1.num + a0.num; + int64_t a2d= x*a1.den + a0.den; + + if(a2n > max || a2d > max){ + if(a1.num) x= (max - a0.num) / a1.num; + if(a1.den) x= FFMIN(x, (max - a0.den) / a1.den); + + if (den*(2*x*a1.den + a0.den) > nom*a1.den) + a1 = (AVRational){x*a1.num + a0.num, x*a1.den + a0.den}; + break; + } + + a0= a1; + a1= (AVRational){a2n, a2d}; + nom= den; + den= next_den; + } + assert(ff_gcd(a1.num, a1.den) <= 1U); + + *dst_nom = sign ? -a1.num : a1.num; + *dst_den = a1.den; + + return den==0; +} + +AVRational av_mul_q(AVRational b, AVRational c){ + av_reduce(&b.num, &b.den, b.num * (int64_t)c.num, b.den * (int64_t)c.den, INT_MAX); + return b; +} + +AVRational av_div_q(AVRational b, AVRational c){ + return av_mul_q(b, (AVRational){c.den, c.num}); +} + +AVRational av_add_q(AVRational b, AVRational c){ + av_reduce(&b.num, &b.den, b.num * (int64_t)c.den + c.num * (int64_t)b.den, b.den * (int64_t)c.den, INT_MAX); + return b; +} + +AVRational av_sub_q(AVRational b, AVRational c){ + return av_add_q(b, (AVRational){-c.num, c.den}); +} + +AVRational av_d2q(double d, int max){ + AVRational a; +#define LOG2 0.69314718055994530941723212145817656807550013436025 + int exponent= FFMAX( (int)(log(fabs(d) + 1e-20)/LOG2), 0); + int64_t den= 1LL << (61 - exponent); + av_reduce(&a.num, &a.den, (int64_t)(d * den + 0.5), den, max); + + return a; +} diff --git a/contrib/ffmpeg/libavutil/rational.h b/contrib/ffmpeg/libavutil/rational.h new file mode 100644 index 000000000..63c0b150f --- /dev/null +++ b/contrib/ffmpeg/libavutil/rational.h @@ -0,0 +1,114 @@ +/* + * Rational numbers + * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + * + */ + +/** + * @file rational.h + * Rational numbers. + * @author Michael Niedermayer <michaelni@gmx.at> + */ + +#ifndef RATIONAL_H +#define RATIONAL_H + +/** + * Rational number num/den. + */ +typedef struct AVRational{ + int num; ///< numerator + int den; ///< denominator +} AVRational; + +/** + * Compare two rationals. + * @param a first rational + * @param b second rational + * @return 0 if a==b, 1 if a>b and -1 if a<b. + */ +static inline int av_cmp_q(AVRational a, AVRational b){ + const int64_t tmp= a.num * (int64_t)b.den - b.num * (int64_t)a.den; + + if(tmp) return (tmp>>63)|1; + else return 0; +} + +/** + * Rational to double conversion. + * @param a rational to convert + * @return (double) a + */ +static inline double av_q2d(AVRational a){ + return a.num / (double) a.den; +} + +/** + * Reduce a fraction. + * This is useful for framerate calculations. + * @param dst_nom destination numerator + * @param dst_den destination denominator + * @param nom source numerator + * @param den source denominator + * @param max the maximum allowed for dst_nom & dst_den + * @return 1 if exact, 0 otherwise + */ +int av_reduce(int *dst_nom, int *dst_den, int64_t nom, int64_t den, int64_t max); + +/** + * Multiplies two rationals. + * @param b first rational. + * @param c second rational. + * @return b*c. + */ +AVRational av_mul_q(AVRational b, AVRational c); + +/** + * Divides one rational by another. + * @param b first rational. + * @param c second rational. + * @return b/c. + */ +AVRational av_div_q(AVRational b, AVRational c); + +/** + * Adds two rationals. + * @param b first rational. + * @param c second rational. + * @return b+c. + */ +AVRational av_add_q(AVRational b, AVRational c); + +/** + * Subtracts one rational from another. + * @param b first rational. + * @param c second rational. + * returns b-c. + */ +AVRational av_sub_q(AVRational b, AVRational c); + +/** + * Converts a double precision floating point number to a rational. + * @param d double to convert + * @param max the maximum allowed numerator and denominator + * @return (AVRational) d. + */ +AVRational av_d2q(double d, int max); + +#endif // RATIONAL_H diff --git a/contrib/ffmpeg/libavutil/sha1.c b/contrib/ffmpeg/libavutil/sha1.c new file mode 100644 index 000000000..6c10791f4 --- /dev/null +++ b/contrib/ffmpeg/libavutil/sha1.c @@ -0,0 +1,160 @@ +// SHA-1 code Copyright 2007 Michael Nidermayer <michaelni@gmx.at> +// license LGPL +// based on public domain SHA-1 code by Steve Reid <steve@edmweb.com> + +#include "common.h" +#include "sha1.h" + +typedef struct AVSHA1 { + uint64_t count; + uint8_t buffer[64]; + uint32_t state[5]; +} AVSHA1; + +#define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits)))) + +/* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */ +#define blk0(i) (block[i] = be2me_32(((uint32_t*)buffer)[i])) +#define blk(i) (block[i] = rol(block[i-3]^block[i-8]^block[i-14]^block[i-16],1)) + +#define R0(v,w,x,y,z,i) z+=((w&(x^y))^y) +blk0(i)+0x5A827999+rol(v,5);w=rol(w,30); +#define R1(v,w,x,y,z,i) z+=((w&(x^y))^y) +blk (i)+0x5A827999+rol(v,5);w=rol(w,30); +#define R2(v,w,x,y,z,i) z+=( w^x ^y) +blk (i)+0x6ED9EBA1+rol(v,5);w=rol(w,30); +#define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk (i)+0x8F1BBCDC+rol(v,5);w=rol(w,30); +#define R4(v,w,x,y,z,i) z+=( w^x ^y) +blk (i)+0xCA62C1D6+rol(v,5);w=rol(w,30); + +/* Hash a single 512-bit block. This is the core of the algorithm. */ + +static void transform(uint32_t state[5], uint8_t buffer[64]){ + uint32_t block[80]; + unsigned int i, a, b, c, d, e; + + a = state[0]; + b = state[1]; + c = state[2]; + d = state[3]; + e = state[4]; +#ifdef CONFIG_SMALL + for(i=0; i<80; i++){ + int t; + if(i<16) t= be2me_32(((uint32_t*)buffer)[i]); + else t= rol(block[i-3]^block[i-8]^block[i-14]^block[i-16],1); + block[i]= t; + t+= e+rol(a,5); + if(i<40){ + if(i<20) t+= ((b&(c^d))^d) +0x5A827999; + else t+= ( b^c ^d) +0x6ED9EBA1; + }else{ + if(i<60) t+= (((b|c)&d)|(b&c))+0x8F1BBCDC; + else t+= ( b^c ^d) +0xCA62C1D6; + } + e= d; + d= c; + c= rol(b,30); + b= a; + a= t; + } +#else + for(i=0; i<15; i+=5){ + R0(a,b,c,d,e,0+i); R0(e,a,b,c,d,1+i); R0(d,e,a,b,c,2+i); R0(c,d,e,a,b,3+i); R0(b,c,d,e,a,4+i); + } + R0(a,b,c,d,e,15); R1(e,a,b,c,d,16); R1(d,e,a,b,c,17); R1(c,d,e,a,b,18); R1(b,c,d,e,a,19); + for(i=20; i<40; i+=5){ + R2(a,b,c,d,e,0+i); R2(e,a,b,c,d,1+i); R2(d,e,a,b,c,2+i); R2(c,d,e,a,b,3+i); R2(b,c,d,e,a,4+i); + } + for(; i<60; i+=5){ + R3(a,b,c,d,e,0+i); R3(e,a,b,c,d,1+i); R3(d,e,a,b,c,2+i); R3(c,d,e,a,b,3+i); R3(b,c,d,e,a,4+i); + } + for(; i<80; i+=5){ + R4(a,b,c,d,e,0+i); R4(e,a,b,c,d,1+i); R4(d,e,a,b,c,2+i); R4(c,d,e,a,b,3+i); R4(b,c,d,e,a,4+i); + } +#endif + state[0] += a; + state[1] += b; + state[2] += c; + state[3] += d; + state[4] += e; +} + +void av_sha1_init(AVSHA1* ctx){ + ctx->state[0] = 0x67452301; + ctx->state[1] = 0xEFCDAB89; + ctx->state[2] = 0x98BADCFE; + ctx->state[3] = 0x10325476; + ctx->state[4] = 0xC3D2E1F0; + ctx->count = 0; +} + +void av_sha1_update(AVSHA1* ctx, uint8_t* data, unsigned int len){ + unsigned int i, j; + + j = ctx->count & 63; + ctx->count += len; +#ifdef CONFIG_SMALL + for( i = 0; i < len; i++ ){ + ctx->buffer[ j++ ] = data[i]; + if( 64 == j ){ + transform(ctx->state, ctx->buffer); + j = 0; + } + } +#else + if ((j + len) > 63) { + memcpy(&ctx->buffer[j], data, (i = 64-j)); + transform(ctx->state, ctx->buffer); + for ( ; i + 63 < len; i += 64) { + transform(ctx->state, &data[i]); + } + j=0; + } + else i = 0; + memcpy(&ctx->buffer[j], &data[i], len - i); +#endif +} + +void av_sha1_final(AVSHA1* ctx, uint8_t digest[20]){ + int i; + uint64_t finalcount= be2me_64(ctx->count<<3); + + av_sha1_update(ctx, "\200", 1); + while ((ctx->count & 63) != 56) { + av_sha1_update(ctx, "", 1); + } + av_sha1_update(ctx, &finalcount, 8); /* Should cause a transform() */ + for(i=0; i<5; i++) + ((uint32_t*)digest)[i]= be2me_32(ctx->state[i]); +} + +// use the following to test +// gcc -DTEST -DHAVE_AV_CONFIG_H -I.. sha1.c -O2 -W -Wall -o sha1 && time ./sha1 +#ifdef TEST +#include <stdio.h> +#undef printf + +int main(){ + int i, k; + AVSHA1 ctx; + unsigned char digest[20]; + + for(k=0; k<3; k++){ + av_sha1_init(&ctx); + if(k==0) + av_sha1_update(&ctx, "abc", 3); + else if(k==1) + av_sha1_update(&ctx, "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 56); + else + for(i=0; i<1000*1000; i++) + av_sha1_update(&ctx, "a", 1); + av_sha1_final(&ctx, digest); + for (i = 0; i < 20; i++) + printf("%02X", digest[i]); + putchar('\n'); + } + //Test Vectors (from FIPS PUB 180-1) + printf("A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D\n" + "84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1\n" + "34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F\n"); + + return 0; +} +#endif diff --git a/contrib/ffmpeg/libavutil/sha1.h b/contrib/ffmpeg/libavutil/sha1.h new file mode 100644 index 000000000..8739cbde9 --- /dev/null +++ b/contrib/ffmpeg/libavutil/sha1.h @@ -0,0 +1,11 @@ +#ifndef AV_SHA1_H +#define AV_SHA1_H + +extern const int av_sha1_size; + +struct AVSHA1; + +void av_sha1_init(struct AVSHA1* context); +void av_sha1_update(struct AVSHA1* context, uint8_t* data, unsigned int len); +void av_sha1_final(struct AVSHA1* context, uint8_t digest[20]); +#endif diff --git a/contrib/ffmpeg/libavutil/softfloat.c b/contrib/ffmpeg/libavutil/softfloat.c new file mode 100644 index 000000000..f12fd17a0 --- /dev/null +++ b/contrib/ffmpeg/libavutil/softfloat.c @@ -0,0 +1,72 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 <inttypes.h> +#include <stdio.h> +#include <assert.h> +#include "softfloat.h" +#include "common.h" +#include "log.h" + +#undef printf + +int main(){ + SoftFloat one= av_int2sf(1, 0); + SoftFloat sf1, sf2; + double d1, d2; + int i, j; +av_log_level = AV_LOG_DEBUG; + + d1= 1; + for(i= 0; i<10; i++){ + d1= 1/(d1+1); + } + printf("test1 double=%d\n", (int)(d1 * (1<<24))); + + sf1= one; + for(i= 0; i<10; i++){ + sf1= av_div_sf(one, av_normalize_sf(av_add_sf(one, sf1))); + } + printf("test1 sf =%d\n", av_sf2int(sf1, 24)); + + + for(i= 0; i<100; i++){ + START_TIMER + d1= i; + d2= i/100.0; + for(j= 0; j<1000; j++){ + d1= (d1+1)*d2; + } + STOP_TIMER("float add mul") + } + printf("test2 double=%d\n", (int)(d1 * (1<<24))); + + for(i= 0; i<100; i++){ + START_TIMER + sf1= av_int2sf(i, 0); + sf2= av_div_sf(av_int2sf(i, 2), av_int2sf(200, 3)); + for(j= 0; j<1000; j++){ + sf1= av_mul_sf(av_add_sf(sf1, one),sf2); + } + STOP_TIMER("softfloat add mul") + } + printf("test2 sf =%d (%d %d)\n", av_sf2int(sf1, 24), sf1.exp, sf1.mant); + return 0; +} diff --git a/contrib/ffmpeg/libavutil/softfloat.h b/contrib/ffmpeg/libavutil/softfloat.h new file mode 100644 index 000000000..5bb2c1cbc --- /dev/null +++ b/contrib/ffmpeg/libavutil/softfloat.h @@ -0,0 +1,122 @@ +/* + * Copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + * + */ + +#define MIN_EXP -126 +#define MAX_EXP 126 +#define ONE_BITS 29 + +typedef struct SoftFloat{ + int32_t exp; + int32_t mant; +}SoftFloat; + +static SoftFloat av_normalize_sf(SoftFloat a){ + if(a.mant){ +#if 1 + while((a.mant + 0x20000000U)<0x40000000U){ + a.mant += a.mant; + a.exp -= 1; + } +#else + int s=ONE_BITS + 1 - av_log2(a.mant ^ (a.mant<<1)); + a.exp -= s; + a.mant <<= s; +#endif + if(a.exp < MIN_EXP){ + a.exp = MIN_EXP; + a.mant= 0; + } + }else{ + a.exp= MIN_EXP; + } + return a; +} + +static inline SoftFloat av_normalize1_sf(SoftFloat a){ +#if 1 + if(a.mant + 0x40000000 < 0){ + a.exp++; + a.mant>>=1; + } + return a; +#elif 1 + int t= a.mant + 0x40000000 < 0; + return (SoftFloat){a.exp+t, a.mant>>t}; +#else + int t= (a.mant + 0x40000000U)>>31; + return (SoftFloat){a.exp+t, a.mant>>t}; +#endif +} + +/** + * + * @return will not be more denormalized then a+b, so if either input is + * normalized then the output wont be worse then the other input + * if both are normalized then the output will be normalized + */ +static inline SoftFloat av_mul_sf(SoftFloat a, SoftFloat b){ + a.exp += b.exp; + a.mant = (a.mant * (int64_t)b.mant) >> ONE_BITS; + return av_normalize1_sf(a); +} + +/** + * + * b has to be normalized and not zero + * @return will not be more denormalized then a + */ +static SoftFloat av_div_sf(SoftFloat a, SoftFloat b){ + a.exp -= b.exp+1; + a.mant = ((int64_t)a.mant<<(ONE_BITS+1)) / b.mant; + return av_normalize1_sf(a); +} + +static inline int av_cmp_sf(SoftFloat a, SoftFloat b){ + int t= a.exp - b.exp; + if(t<0) return (a.mant >> (-t)) - b.mant ; + else return a.mant - (b.mant >> t); +} + +static inline SoftFloat av_add_sf(SoftFloat a, SoftFloat b){ + int t= a.exp - b.exp; + if(t<0) return av_normalize1_sf((SoftFloat){b.exp, b.mant + (a.mant >> (-t))}); + else return av_normalize1_sf((SoftFloat){a.exp, a.mant + (b.mant >> t )}); +} + +static inline SoftFloat av_sub_sf(SoftFloat a, SoftFloat b){ + return av_add_sf(a, (SoftFloat){b.exp, -b.mant}); +} + +//FIXME sqrt, log, exp, pow, sin, cos + +static inline SoftFloat av_int2sf(int v, int frac_bits){ + return av_normalize_sf((SoftFloat){ONE_BITS-frac_bits, v}); +} + +/** + * + * rounding is to -inf + */ +static inline int av_sf2int(SoftFloat v, int frac_bits){ + v.exp += frac_bits - ONE_BITS; + if(v.exp >= 0) return v.mant << v.exp ; + else return v.mant >>(-v.exp); +} diff --git a/contrib/ffmpeg/libavutil/tree.c b/contrib/ffmpeg/libavutil/tree.c new file mode 100644 index 000000000..c929e4819 --- /dev/null +++ b/contrib/ffmpeg/libavutil/tree.c @@ -0,0 +1,151 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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" +#include "log.h" +#include "tree.h" + +typedef struct AVTreeNode{ + struct AVTreeNode *child[2]; + void *elem; + int state; +}AVTreeNode; + +void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ + if(t){ + unsigned int v= cmp(t->elem, key); + if(v){ + if(next) next[(v>>31)^1]= t->elem; + return av_tree_find(t->child[v>>31], key, cmp, next); + }else{ + return t->elem; + } + } + return NULL; +} + +void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b)){ + AVTreeNode *t= *tp; + if(t){ + unsigned int v= cmp(t->elem, key); + if(v){ + int i= v>>31; + AVTreeNode **child= &t->child[i]; + void *ret= av_tree_insert(child, key, cmp); + if(!ret){ + t->state -= ((int)v>>31)|1; + if(!(t->state&1)){ + if(t->state){ + if((*child)->state*2 == t->state){ + *tp= *child; + *child= (*child)->child[i^1]; + (*tp)->child[i^1]= t; + t->state= 0; + }else{ + *tp= (*child)->child[i^1]; + (*child)->child[i^1]= (*tp)->child[i]; + (*tp)->child[i]= *child; + *child= (*tp)->child[i^1]; + (*tp)->child[i^1]= t; + + i= (*tp)->state > 0; + (*tp)->child[i ]->state= 0; + (*tp)->child[i^1]->state= -(*tp)->state; + } + (*tp)->state=0; + } + return key; + } + } + return ret; + }else{ + return t->elem; + } + }else{ + *tp= av_mallocz(sizeof(AVTreeNode)); + (*tp)->elem= key; + return NULL; + } +} + +void av_tree_destroy(AVTreeNode *t){ + av_tree_destroy(t->child[0]); + av_tree_destroy(t->child[1]); + av_free(t); +} + +#if 0 +void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){ + int v= f(opaque, t->elem); + if(v>=0) av_tree_enumerate(t->child[0], opaque, f); + if(v<=0) av_tree_enumerate(t->child[1], opaque, f); +} +#endif + +#ifdef TEST + +static int check(AVTreeNode *t){ + if(t){ + int left= check(t->child[0]); + int right= check(t->child[1]); + + if(left>999 || right>999) + return 1000; + if(right - left != t->state) + return 1000; + if(t->state>1 || t->state<-1) + return 1000; + return FFMAX(left, right)+1; + } + return 0; +} + +static void print(AVTreeNode *t, int depth){ + int i; + for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " "); + if(t){ + av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem); + print(t->child[0], depth+1); + print(t->child[1], depth+1); + }else + av_log(NULL, AV_LOG_ERROR, "NULL\n"); +} + +int cmp(const void *a, const void *b){ + return a-b; +} + +int main(){ + int i,j,k; + AVTreeNode *root= NULL; + + for(i=0; i<10000; i++){ + int j= (random()%863294); + if(check(root) > 999){ + av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); + print(root, 0); + return -1; + } + av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); + av_tree_insert(&root, (void*)(j+1), cmp); + } + return 0; +} +#endif diff --git a/contrib/ffmpeg/libavutil/tree.h b/contrib/ffmpeg/libavutil/tree.h new file mode 100644 index 000000000..be1735858 --- /dev/null +++ b/contrib/ffmpeg/libavutil/tree.h @@ -0,0 +1,58 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +/** + * @file tree.h + * A tree container. + * @author Michael Niedermayer <michaelni@gmx.at> + */ + +#ifndef TREE_H +#define TREE_H + +struct AVTreeNode; + +/** + * Finds an element. + * @param root a pointer to the root node of the tree + * @param next If next is not NULL then next[0] will contain the previous + * element and next[1] the next element if either does not exist + * then the corresponding entry in next is unchanged. + * @return An element with cmp(key, elem)==0 or NULL if no such element exists in + * the tree. + */ +void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]); + +/** + * Finds a element for which cmp(key, elem)==0, if no such element is found key + * is inserted into the tree. + * @param rootp A pointer to a pointer to the root node of the tree. Note that + * the root node can change during insertions, this is required + * to keep the tree balanced. + * + * @return If no insertion happened, the found element. + * If an insertion happened, then either key or NULL will be returned. + * Which one it is depends on the tree state and the implementation. You + * should make no assumptions that it's one or the other in the code. + */ +void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b)); +void av_tree_destroy(struct AVTreeNode *t); + +#endif /* TREE_H */ diff --git a/contrib/ffmpeg/libavutil/x86_cpu.h b/contrib/ffmpeg/libavutil/x86_cpu.h new file mode 100644 index 000000000..67d4cd9aa --- /dev/null +++ b/contrib/ffmpeg/libavutil/x86_cpu.h @@ -0,0 +1,64 @@ +/* + * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> + * + * 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 + */ + +#ifndef AVUTIL_X86CPU_H +#define AVUTIL_X86CPU_H + +#ifdef ARCH_X86_64 +# define REG_a "rax" +# define REG_b "rbx" +# define REG_c "rcx" +# define REG_d "rdx" +# define REG_D "rdi" +# define REG_S "rsi" +# define PTR_SIZE "8" + +# define REG_SP "rsp" +# define REG_BP "rbp" +# define REGBP rbp +# define REGa rax +# define REGb rbx +# define REGc rcx +# define REGSP rsp + +#else + +# define REG_a "eax" +# define REG_b "ebx" +# define REG_c "ecx" +# define REG_d "edx" +# define REG_D "edi" +# define REG_S "esi" +# define PTR_SIZE "4" + +# define REG_SP "esp" +# define REG_BP "ebp" +# define REGBP ebp +# define REGa eax +# define REGb ebx +# define REGc ecx +# define REGSP esp +#endif + +#if defined(ARCH_X86_64) || (defined(ARCH_X86_32) && defined(CONFIG_EBX_AVAILABLE) && defined(CONFIG_EBP_AVAILABLE)) +# define CONFIG_7REGS 1 +#endif + +#endif /* AVUTIL_X86CPU_H */ |