---
libavutil/crc.c | 77 ++++++++++---------
libavutil/lfg.c | 35 +++++----
libavutil/log.c | 88 ++++++++++++----------
libavutil/random_seed.c | 36 +++++-----
libavutil/rational.c | 114 +++++++++++++++-------------
libavutil/tree.c | 194 +++++++++++++++++++++++++----------------------
6 files changed, 292 insertions(+), 252 deletions(-)
diff --git a/libavutil/crc.c b/libavutil/crc.c
index 44719ff..fadb05e 100644
--- a/libavutil/crc.c
+++ b/libavutil/crc.c
@@ -56,32 +56,34 @@ static AVCRC av_crc_table[AV_CRC_MAX][257];
* @param ctx_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 av_crc_init(AVCRC *ctx, int le, int bits, uint32_t poly, int ctx_size)
+{
unsigned i, j;
uint32_t c;
- if (bits < 8 || bits > 32 || poly >= (1LL<<bits))
+ if (bits < 8 || bits > 32 || poly >= (1LL << bits))
return -1;
- if (ctx_size != sizeof(AVCRC)*257 && ctx_size != sizeof(AVCRC)*1024)
+ 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)));
+ 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) );
+ c = (c << 1) ^((poly << (32-bits)) & (((int32_t)c) >> 31));
ctx[i] = av_bswap32(c);
}
}
- ctx[256]=1;
+ ctx[256] = 1;
#if !CONFIG_SMALL
- if(ctx_size >= sizeof(AVCRC)*1024)
+ 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 ];
+ 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;
@@ -92,15 +94,16 @@ int av_crc_init(AVCRC *ctx, int le, int bits, uint32_t
poly, int ctx_size){
* @param crc_id ID of a standard CRC
* @return a pointer to the CRC table or NULL on failure
*/
-const AVCRC *av_crc_get_table(AVCRCId crc_id){
+const AVCRC *av_crc_get_table(AVCRCId crc_id)
+{
#if !CONFIG_HARDCODED_TABLES
- if (!av_crc_table[crc_id][FF_ARRAY_ELEMS(av_crc_table[crc_id])-1])
+ if (!av_crc_table[crc_id][FF_ARRAY_ELEMS(av_crc_table[crc_id]) - 1])
if (av_crc_init(av_crc_table[crc_id],
av_crc_table_params[crc_id].le,
av_crc_table_params[crc_id].bits,
av_crc_table_params[crc_id].poly,
- sizeof(av_crc_table[crc_id])) < 0)
- return NULL;
+ sizeof(av_crc_table[crc_id])) < 0)
+ return NULL;
#endif
return av_crc_table[crc_id];
}
@@ -112,46 +115,50 @@ const AVCRC *av_crc_get_table(AVCRCId crc_id){
*
* @see av_crc_init() "le" parameter
*/
-uint32_t av_crc(const AVCRC *ctx, uint32_t crc, const uint8_t *buffer, size_t
length){
- const uint8_t *end= buffer+length;
+uint32_t av_crc(const AVCRC *ctx, uint32_t crc,
+ const uint8_t *buffer, size_t length)
+{
+ const uint8_t *end = buffer + length;
#if !CONFIG_SMALL
- if(!ctx[256]) {
- while(((intptr_t) buffer & 3) && buffer < end)
- crc = ctx[((uint8_t)crc) ^ *buffer++] ^ (crc >> 8);
+ if (!ctx[256]) {
+ while (((intptr_t) buffer & 3) && buffer < end)
+ crc = ctx[((uint8_t)crc) ^ *buffer++] ^(crc >> 8);
- while(buffer<end-3){
- crc ^= av_le2ne32(*(const 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) )];
+ while (buffer < end - 3) {
+ crc ^= av_le2ne32(* (const 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);
+ while (buffer<end)
+ crc = ctx[((uint8_t)crc) ^ *buffer++] ^(crc >> 8);
return crc;
}
#ifdef TEST
#undef printf
-int main(void){
+int main(void)
+{
uint8_t buf[1999];
int i;
- int p[4][3]={{AV_CRC_32_IEEE_LE, 0xEDB88320, 0x3D5CDD04},
- {AV_CRC_32_IEEE , 0x04C11DB7, 0xC0F5BAE0},
- {AV_CRC_16_ANSI , 0x8005, 0x1FBB },
- {AV_CRC_8_ATM , 0x07, 0xE3 },};
+ int p[4][3] = { { AV_CRC_32_IEEE_LE, 0xEDB88320, 0x3D5CDD04 },
+ { AV_CRC_32_IEEE , 0x04C11DB7, 0xC0F5BAE0 },
+ { AV_CRC_16_ANSI , 0x8005 , 0x1FBB },
+ { AV_CRC_8_ATM , 0x07 , 0xE3 }
+ };
const AVCRC *ctx;
- for(i=0; i<sizeof(buf); i++)
- buf[i]= i+i*i;
+ for (i = 0; i < sizeof(buf); i++)
+ buf[i] = i + i * i;
- for(i=0; i<4; i++){
+ for (i = 0; i < 4; i++){
ctx = av_crc_get_table(p[i][0]);
- printf("crc %08X =%X\n", p[i][1], av_crc(ctx, 0, buf, sizeof(buf)));
+ printf("crc %08X = %X\n", p[i][1], av_crc(ctx, 0, buf, sizeof(buf)));
}
return 0;
}
diff --git a/libavutil/lfg.c b/libavutil/lfg.c
index 7fab806..a6dfc3f 100644
--- a/libavutil/lfg.c
+++ b/libavutil/lfg.c
@@ -27,19 +27,20 @@
#include "intreadwrite.h"
#include "attributes.h"
-void av_cold av_lfg_init(AVLFG *c, unsigned int seed){
- uint8_t tmp[16]={0};
+void av_cold av_lfg_init(AVLFG *c, unsigned int seed)
+{
+ uint8_t tmp[16] = { 0 };
int i;
- for(i=8; i<64; i+=4){
- AV_WL32(tmp, seed); tmp[4]=i;
- av_md5_sum(tmp, tmp, 16);
- c->state[i ]= AV_RL32(tmp);
- c->state[i+1]= AV_RL32(tmp+4);
- c->state[i+2]= AV_RL32(tmp+8);
- c->state[i+3]= AV_RL32(tmp+12);
+ for(i = 8; i < 64; i += 4) {
+ AV_WL32(tmp, seed); tmp[4] = i;
+ av_md5_sum(tmp, tmp, 16);
+ c->state[i ] = AV_RL32(tmp);
+ c->state[i + 1] = AV_RL32(tmp + 4);
+ c->state[i + 2] = AV_RL32(tmp + 8);
+ c->state[i + 3] = AV_RL32(tmp + 12);
}
- c->index=0;
+ c->index = 0;
}
void av_bmg_get(AVLFG *lfg, double out[2])
@@ -47,9 +48,9 @@ void av_bmg_get(AVLFG *lfg, double out[2])
double x1, x2, w;
do {
- x1 = 2.0/UINT_MAX*av_lfg_get(lfg) - 1.0;
- x2 = 2.0/UINT_MAX*av_lfg_get(lfg) - 1.0;
- w = x1*x1 + x2*x2;
+ x1 = 2.0 / UINT_MAX * av_lfg_get(lfg) - 1.0;
+ x2 = 2.0 / UINT_MAX * av_lfg_get(lfg) - 1.0;
+ w = x1 * x1 + x2 * x2;
} while (w >= 1.0);
w = sqrt((-2.0 * log(w)) / w);
@@ -61,9 +62,9 @@ void av_bmg_get(AVLFG *lfg, double out[2])
#include "log.h"
#include "timer.h"
-int main(void)
+int main(void)
{
- int x=0;
+ int x = 0;
int i, j;
AVLFG state;
@@ -71,8 +72,8 @@ int main(void)
for (j = 0; j < 10000; j++) {
START_TIMER
for (i = 0; i < 624; i++) {
-// av_log(NULL,AV_LOG_ERROR, "%X\n", av_lfg_get(&state));
- x+=av_lfg_get(&state);
+// av_log(NULL,AV_LOG_ERROR, "%X\n", av_lfg_get(&state));
+ x += av_lfg_get(&state);
}
STOP_TIMER("624 calls of av_lfg_get");
}
diff --git a/libavutil/log.c b/libavutil/log.c
index 4d2b539..1e2bfb8 100644
--- a/libavutil/log.c
+++ b/libavutil/log.c
@@ -35,129 +35,139 @@ static int flags;
#if defined(_WIN32) && !defined(__MINGW32CE__)
#include <windows.h>
-static const uint8_t color[] = {12,12,12,14,7,7,7};
+static const uint8_t color[] = { 12, 12, 12, 14, 7, 7, 7 };
static int16_t background, attr_orig;
static HANDLE con;
#define set_color(x) SetConsoleTextAttribute(con, background | color[x])
#define reset_color() SetConsoleTextAttribute(con, attr_orig)
#else
-static const uint8_t color[]={0x41,0x41,0x11,0x03,9,9,9};
-#define set_color(x) fprintf(stderr, "\033[%d;3%dm", color[x]>>4, color[x]&15)
+static const uint8_t color[] = { 0x41, 0x41, 0x11, 0x03, 9, 9, 9 };
+#define set_color(x) fprintf(stderr, "\033[%d;3%dm", color[x] >> 4,
color[x]&15)
#define reset_color() fprintf(stderr, "\033[0m")
#endif
-static int use_color=-1;
+static int use_color =- 1;
#undef fprintf
-static void colored_fputs(int level, const char *str){
- if(use_color<0){
+static void colored_fputs(int level, const char *str)
+{
+ if (use_color < 0) {
#if defined(_WIN32) && !defined(__MINGW32CE__)
CONSOLE_SCREEN_BUFFER_INFO con_info;
con = GetStdHandle(STD_ERROR_HANDLE);
- use_color = (con != INVALID_HANDLE_VALUE) && !getenv("NO_COLOR") &&
!getenv("AV_LOG_FORCE_NOCOLOR");
+ use_color = (con != INVALID_HANDLE_VALUE) && !getenv("NO_COLOR")
+ && !getenv("AV_LOG_FORCE_NOCOLOR");
if (use_color) {
GetConsoleScreenBufferInfo(con, &con_info);
attr_orig = con_info.wAttributes;
background = attr_orig & 0xF0;
}
#elif HAVE_ISATTY
- use_color= !getenv("NO_COLOR") && !getenv("AV_LOG_FORCE_NOCOLOR") &&
+ use_color = !getenv("NO_COLOR") && !getenv("AV_LOG_FORCE_NOCOLOR") &&
(getenv("TERM") && isatty(2) || getenv("AV_LOG_FORCE_COLOR"));
#else
- use_color= getenv("AV_LOG_FORCE_COLOR") && !getenv("NO_COLOR") &&
!getenv("AV_LOG_FORCE_NOCOLOR");
+ use_color = getenv("AV_LOG_FORCE_COLOR") && !getenv("NO_COLOR")
+ && !getenv("AV_LOG_FORCE_NOCOLOR");
#endif
}
- if(use_color){
+ if (use_color) {
set_color(level);
}
fputs(str, stderr);
- if(use_color){
+ if (use_color) {
reset_color();
}
}
-const char* av_default_item_name(void* ptr){
- return (*(AVClass**)ptr)->class_name;
+const char* av_default_item_name(void* ptr)
+{
+ return (* (AVClass**) ptr)->class_name;
}
void av_log_default_callback(void* ptr, int level, const char* fmt, va_list vl)
{
- static int print_prefix=1;
+ static int print_prefix = 1;
static int count;
static char prev[1024];
char line[1024];
static int is_atty;
- AVClass* avc= ptr ? *(AVClass**)ptr : NULL;
- if(level>av_log_level)
+ AVClass* avc = ptr ? *(AVClass**)ptr : NULL;
+ if (level>av_log_level)
return;
- line[0]=0;
+ line[0] = 0;
#undef fprintf
- if(print_prefix && avc) {
+ if (print_prefix && avc) {
if (avc->parent_log_context_offset) {
- AVClass** parent= *(AVClass***)(((uint8_t*)ptr) +
avc->parent_log_context_offset);
- if(parent && *parent){
- snprintf(line, sizeof(line), "[%s @ %p] ",
(*parent)->item_name(parent), parent);
+ AVClass** parent = *(AVClass***)(( (uint8_t *) ptr)
+ + avc->parent_log_context_offset);
+ if (parent && *parent) {
+ snprintf(line, sizeof(line), "[%s @ %p] ",
+ ( *parent )->item_name(parent), parent);
}
}
- snprintf(line + strlen(line), sizeof(line) - strlen(line), "[%s @ %p]
", avc->item_name(ptr), ptr);
+ snprintf(line + strlen(line), sizeof(line) - strlen(line), "[%s @ %p]
",
+ avc->item_name(ptr), ptr);
}
vsnprintf(line + strlen(line), sizeof(line) - strlen(line), fmt, vl);
- print_prefix = strlen(line) && line[strlen(line)-1] == '\n';
+ print_prefix = strlen(line) && line[strlen(line) - 1] == '\n';
#if HAVE_ISATTY
- if(!is_atty) is_atty= isatty(2) ? 1 : -1;
+ if (!is_atty) is_atty= isatty(2) ? 1 : -1;
#endif
- if(print_prefix && (flags & AV_LOG_SKIP_REPEATED) && !strncmp(line, prev,
sizeof line)){
+ if (print_prefix && (flags & AV_LOG_SKIP_REPEATED)
+ && !strncmp(line, prev, sizeof line)) {
count++;
- if(is_atty==1)
+ if (is_atty == 1)
fprintf(stderr, " Last message repeated %d times\r", count);
return;
}
- if(count>0){
+ if (count > 0) {
fprintf(stderr, " Last message repeated %d times\n", count);
- count=0;
+ count = 0;
}
- colored_fputs(av_clip(level>>3, 0, 6), line);
+ colored_fputs(av_clip(level >> 3, 0, 6), line);
av_strlcpy(prev, line, sizeof line);
}
-static void (*av_log_callback)(void*, int, const char*, va_list) =
av_log_default_callback;
+static void ( *av_log_callback)(void* , int, const char* , va_list)
+ = av_log_default_callback;
void av_log(void* avcl, int level, const char *fmt, ...)
{
- AVClass* avc= avcl ? *(AVClass**)avcl : NULL;
+ AVClass* avc = avcl ? *(AVClass**)avcl : NULL;
va_list vl;
va_start(vl, fmt);
- if(avc && avc->version >= (50<<16 | 15<<8 | 2) &&
avc->log_level_offset_offset && level>=AV_LOG_FATAL)
- level += *(int*)(((uint8_t*)avcl) + avc->log_level_offset_offset);
+ if (avc && avc->version >= (50 << 16 | 15 << 8 | 2) &&
+ avc->log_level_offset_offset && level>=AV_LOG_FATAL)
+ level += *( int* )(( (uint8_t *) avcl) + avc->log_level_offset_offset);
av_vlog(avcl, level, fmt, vl);
va_end(vl);
}
-void av_vlog(void* avcl, int level, const char *fmt, va_list vl)
+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)
+int av_log_get_level(void)
{
return av_log_level;
}
-void av_log_set_level(int level)
+void av_log_set_level(int level)
{
av_log_level = level;
}
-void av_log_set_flags(int arg)
+void av_log_set_flags(int arg)
{
- flags= arg;
+ flags = arg;
}
-void av_log_set_callback(void (*callback)(void*, int, const char*, va_list))
+void av_log_set_callback(void ( *callback )(void*, int, const char*, va_list))
{
av_log_callback = callback;
}
diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
index ee71542..8fc0cfb 100644
--- a/libavutil/random_seed.c
+++ b/libavutil/random_seed.c
@@ -25,39 +25,39 @@
#include "timer.h"
#include "random_seed.h"
-static int read_random(uint32_t *dst, const char *file)
+static int read_random(uint32_t *dst, const char *file)
{
int fd = open(file, O_RDONLY);
int err = -1;
if (fd == -1)
return -1;
- err = read(fd, dst, sizeof(*dst));
+ err = read(fd, dst, sizeof( *dst ));
close(fd);
return err;
}
-static uint32_t get_generic_seed(void)
+static uint32_t get_generic_seed(void)
{
- clock_t last_t=0;
- int bits=0;
- uint64_t random=0;
+ clock_t last_t = 0;
+ int bits = 0;
+ uint64_t random = 0;
unsigned i;
- float s=0.000000000001;
+ float s = 0.000000000001;
- for(i=0;bits<64;i++){
- clock_t t= clock();
- if(last_t && fabs(t-last_t)>s || t==(clock_t)-1){
- if(i<10000 && s<(1<<24)){
- s+=s;
- i=t=0;
- }else{
- random= 2*random + (i&1);
+ for (i = 0;bits < 64; i++) {
+ clock_t t = clock();
+ if (last_t && fabs(t-last_t)>s || t == (clock_t) - 1) {
+ if (i < 10000 && s < (1 << 24)) {
+ s += s;
+ i = t = 0;
+ } else {
+ random = 2 * random + (i&1);
bits++;
}
}
- last_t= t;
+ last_t = t;
}
#ifdef AV_READ_TIME
random ^= AV_READ_TIME();
@@ -65,12 +65,12 @@ static uint32_t get_generic_seed(void)
random ^= clock();
#endif
- random += random>>32;
+ random += random >> 32;
return random;
}
-uint32_t av_get_random_seed(void)
+uint32_t av_get_random_seed(void)
{
uint32_t seed;
diff --git a/libavutil/rational.c b/libavutil/rational.c
index ac5111b..89df749 100644
--- a/libavutil/rational.c
+++ b/libavutil/rational.c
@@ -33,75 +33,83 @@
#include "mathematics.h"
#include "rational.h"
-int av_reduce(int *dst_num, int *dst_den, int64_t num, int64_t den, int64_t
max){
- AVRational a0={0,1}, a1={1,0};
- int sign= (num<0) ^ (den<0);
- int64_t gcd= av_gcd(FFABS(num), FFABS(den));
-
- if(gcd){
- num = FFABS(num)/gcd;
- den = FFABS(den)/gcd;
+int av_reduce (int *dst_num, int *dst_den,
+ int64_t num, int64_t den, int64_t max)
+{
+ AVRational a0 = { 0, 1 }, a1 = { 1, 0 };
+ int sign = (num < 0) ^ (den < 0);
+ int64_t gcd = av_gcd(FFABS(num), FFABS(den));
+
+ if (gcd) {
+ num = FFABS(num) / gcd;
+ den = FFABS(den) / gcd;
}
- if(num<=max && den<=max){
- a1= (AVRational){num, den};
- den=0;
+ if (num <= max && den <= max) {
+ a1 = (AVRational){ num, den };
+ den = 0;
}
- while(den){
- uint64_t x = num / den;
- int64_t next_den= num - den*x;
- int64_t a2n= x*a1.num + a0.num;
- int64_t a2d= x*a1.den + a0.den;
+ while (den) {
+ uint64_t x = num / den;
+ int64_t next_den = num - 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 (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) > num*a1.den)
- a1 = (AVRational){x*a1.num + a0.num, x*a1.den + a0.den};
+ if (den* (2 *x *a1.den + a0.den) > num *a1.den)
+ a1 = (AVRational){x * a1.num + a0.num, x * a1.den + a0.den};
break;
}
- a0= a1;
- a1= (AVRational){a2n, a2d};
- num= den;
- den= next_den;
+ a0 = a1;
+ a1 = (AVRational){ a2n, a2d };
+ num = den;
+ den = next_den;
}
av_assert2(av_gcd(a1.num, a1.den) <= 1U);
*dst_num = sign ? -a1.num : a1.num;
*dst_den = a1.den;
- return den==0;
+ 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);
+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_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);
+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_sub_q(AVRational b, AVRational c)
+{
+ return av_add_q(b, (AVRational){ -c.num, c.den });
}
-AVRational av_d2q(double d, int max){
+AVRational av_d2q(double d, int max)
+{
AVRational a;
#define LOG2 0.69314718055994530941723212145817656807550013436025
int exponent;
int64_t den;
if (isnan(d))
- return (AVRational){0,0};
+ return (AVRational){ 0,0 };
if (isinf(d))
- return (AVRational){ d<0 ? -1:1, 0 };
+ return (AVRational){ d<0 ? -1 : 1, 0 };
exponent = FFMAX( (int)(log(fabs(d) + 1e-20)/LOG2), 0);
den = 1LL << (61 - exponent);
av_reduce(&a.num, &a.den, (int64_t)(d * den + 0.5), den, max);
@@ -109,7 +117,7 @@ AVRational av_d2q(double d, int max){
return a;
}
-int av_nearer_q(AVRational q, AVRational q1, AVRational q2)
+int av_nearer_q(AVRational q, AVRational q1, AVRational q2)
{
/* n/d is q, a/b is the median between q1 and q2 */
int64_t a = q1.num * (int64_t)q2.den + q2.num * (int64_t)q1.den;
@@ -124,30 +132,32 @@ int av_nearer_q(AVRational q, AVRational q1, AVRational
q2)
return ((x_up > q.num) - (x_down < q.num)) * av_cmp_q(q2, q1);
}
-int av_find_nearest_q_idx(AVRational q, const AVRational* q_list)
+int av_find_nearest_q_idx(AVRational q, const AVRational* q_list)
{
int i, nearest_q_idx = 0;
- for(i=0; q_list[i].den; i++)
- if (av_nearer_q(q, q_list[i], q_list[nearest_q_idx]) > 0)
+ for(i = 0; q_list[i].den; i++)
+ if (av_nearer_q(q, q_list[i], q_list[nearest_q_idx]) > 0)f
nearest_q_idx = i;
return nearest_q_idx;
}
#ifdef TEST
-int main(void)
+int main(void)
{
AVRational a,b;
- for(a.num=-2; a.num<=2; a.num++){
- for(a.den=-2; a.den<=2; a.den++){
- for(b.num=-2; b.num<=2; b.num++){
- for(b.den=-2; b.den<=2; b.den++){
- int c= av_cmp_q(a,b);
- double d= av_q2d(a) == av_q2d(b) ? 0 : (av_q2d(a) -
av_q2d(b));
- if(d>0) d=1;
- else if(d<0) d=-1;
- else if(d != d) d= INT_MIN;
- if(c!=d) av_log(0, AV_LOG_ERROR, "%d/%d %d/%d, %d %f\n",
a.num, a.den, b.num, b.den, c,d);
+ for (a.num = -2; a.num <= 2; a.num++) {
+ for (a.den = -2; a.den <= 2; a.den++) {
+ for (b.num = -2; b.num <= 2; b.num++) {
+ for (b.den = -2; b.den <=2 ; b.den++) {
+ int c = av_cmp_q(a,b);
+ double d = av_q2d(a) == av_q2d(b) ? 0 :
+ (av_q2d(a) - av_q2d(b));
+ if (d > 0) d = 1;
+ else if (d < 0) d = -1;
+ else if (d != d) d = INT_MIN;
+ if (c != d) av_log(0, AV_LOG_ERROR, "%d/%d %d/%d, %d %f\n",
+ a.num, a.den, b.num, b.den, c,d);
}
}
}
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 067e5b0..7a8eab0 100644
--- a/libavutil/tree.c
+++ b/libavutil/tree.c
@@ -21,24 +21,26 @@
#include "log.h"
#include "tree.h"
-typedef struct AVTreeNode{
+typedef struct AVTreeNode {
struct AVTreeNode *child[2];
void *elem;
int state;
-}AVTreeNode;
+} AVTreeNode;
const int av_tree_node_size = sizeof(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(key, t->elem);
- if(v){
- if(next) next[v>>31]= t->elem;
- return av_tree_find(t->child[(v>>31)^1], key, cmp, next);
- }else{
- if(next){
- av_tree_find(t->child[0], key, cmp, next);
- av_tree_find(t->child[1], key, cmp, next);
+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(key, t->elem);
+ if (v) {
+ if (next) next[v >> 31] = t->elem;
+ return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next);
+ } else {
+ if (next) {
+ av_tree_find (t->child[0], key, cmp, next);
+ av_tree_find (t->child[1], key, cmp, next);
}
return t->elem;
}
@@ -46,34 +48,36 @@ void *av_tree_find(const AVTreeNode *t, void *key, int
(*cmp)(void *key, const v
return NULL;
}
-void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const
void *b), AVTreeNode **next){
- AVTreeNode *t= *tp;
- if(t){
- unsigned int v= cmp(t->elem, key);
+void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key,
+ const void *b), AVTreeNode **next)
+{
+ AVTreeNode *t = *tp;
+ if (t) {
+ unsigned int v = cmp(t->elem, key);
void *ret;
- if(!v){
- if(*next)
+ if (!v) {
+ if (*next)
return t->elem;
- else if(t->child[0]||t->child[1]){
- int i= !t->child[0];
+ else if (t->child[0] || t->child[1]){
+ int i = !t->child[0];
void *next_elem[2];
av_tree_find(t->child[i], key, cmp, next_elem);
- key= t->elem= next_elem[i];
- v= -i;
- }else{
- *next= t;
- *tp=NULL;
+ key = t->elem = next_elem[i];
+ v = -i;
+ } else {
+ *next = t;
+ *tp = NULL;
return NULL;
}
}
- ret= av_tree_insert(&t->child[v>>31], key, cmp, next);
- if(!ret){
- int i= (v>>31) ^ !!*next;
- AVTreeNode **child= &t->child[i];
- t->state += 2*i - 1;
-
- if(!(t->state&1)){
- if(t->state){
+ ret = av_tree_insert(&t->child[v >> 31], key, cmp, next);
+ if (!ret) {
+ int i = (v >> 31) ^ !! *next;
+ AVTreeNode **child = &t->child[i];
+ t->state += 2 * i - 1;
+
+ if (!(t->state&1)) {
+ if (t->state) {
/* The following code is equivalent to
if((*child)->state*2 == -t->state)
rotate(child, i^1);
@@ -92,54 +96,58 @@ void *av_tree_insert(AVTreeNode **tp, void *key, int
(*cmp)(void *key, const voi
}
but such a rotate function is both bigger and slower
*/
- if((*child)->state*2 == -t->state){
- *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;
-
- (*tp)->child[0]->state= -((*tp)->state>0);
- (*tp)->child[1]->state= (*tp)->state<0 ;
- (*tp)->state=0;
- }else{
- *tp= *child;
- *child= (*child)->child[i^1];
- (*tp)->child[i^1]= t;
- if((*tp)->state) t->state = 0;
- else t->state>>= 1;
- (*tp)->state= -t->state;
+ if ((*child)->state * 2 == -t->state) {
+ *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;
+
+ ( *tp )->child[0]->state = -(( * tp)->state > 0);
+ ( *tp )->child[1]->state = ( * tp)->state < 0;
+ ( *tp )->state = 0;
+ } else {
+ *tp = *child;
+ *child = ( *child )->child[i ^ 1];
+ ( *tp )->child[i ^ 1] = t;
+ if (( *tp )->state) t->state = 0;
+ else t->state >> = 1;
+ ( *tp )->state = -t->state;
}
}
}
- if(!(*tp)->state ^ !!*next)
+ if (!( *tp )->state ^ !!*next)
return key;
}
return ret;
- }else{
- *tp= *next; *next= NULL;
- if(*tp){
- (*tp)->elem= key;
+ } else {
+ *tp = *next;
+ *next = NULL;
+ if ( *tp ) {
+ ( *tp )->elem = key;
return NULL;
- }else
+ } else
return key;
}
}
-void av_tree_destroy(AVTreeNode *t){
- if(t){
+void av_tree_destroy(AVTreeNode *t)
+{
+ if (t) {
av_tree_destroy(t->child[0]);
av_tree_destroy(t->child[1]);
av_free(t);
}
}
-void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque,
void *elem), int (*enu)(void *opaque, void *elem)){
- if(t){
- int v= cmp ? cmp(opaque, t->elem) : 0;
- if(v>=0) av_tree_enumerate(t->child[0], opaque, cmp, enu);
- if(v==0) enu(opaque, t->elem);
- if(v<=0) av_tree_enumerate(t->child[1], opaque, cmp, enu);
+void av_tree_enumerate(AVTreeNode *t, void *opaque, int ( *cmp )(void *opaque,
+ void *elem), int ( *enu )(void *opaque, void *elem))
+{
+ if (t) {
+ int v = cmp ? cmp(opaque, t->elem) : 0;
+ if (v >= 0) av_tree_enumerate(t->child[0], opaque, cmp, enu);
+ if (v == 0) enu(opaque, t->elem);
+ if (v<=0) av_tree_enumerate(t->child[1], opaque, cmp, enu);
}
}
@@ -147,64 +155,68 @@ void av_tree_enumerate(AVTreeNode *t, void *opaque, int
(*cmp)(void *opaque, voi
#include "lfg.h"
-static int check(AVTreeNode *t){
- if(t){
- int left= check(t->child[0]);
- int right= check(t->child[1]);
+static int check(AVTreeNode *t)
+{
+ if (t) {
+ int left = check(t->child[0]);
+ int right = check(t->child[1]);
- if(left>999 || right>999)
+ if (left>999 || right>999)
return 1000;
- if(right - left != t->state)
+ if (right - left != t->state)
return 1000;
- if(t->state>1 || t->state<-1)
+ if (t->state>1 || t->state<-1)
return 1000;
- return FFMAX(left, right)+1;
+ return FFMAX(left, right) + 1;
}
return 0;
}
-static void print(AVTreeNode *t, int depth){
+static void print(AVTreeNode *t, int depth)
+{
int i;
- for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
- if(t){
+ for (i = 0; i < depth * 4; i++) av_log(NULL, AV_LOG_ERROR, " ");
+ if (t) {
av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
- print(t->child[0], depth+1);
- print(t->child[1], depth+1);
- }else
+ print(t->child[0], depth + 1);
+ print(t->child[1], depth + 1);
+ } else
av_log(NULL, AV_LOG_ERROR, "NULL\n");
}
-static int cmp(void *a, const void *b){
- return (uint8_t*)a-(const uint8_t*)b;
+static int cmp(void *a, const void *b)
+{
+ return ( uint8_t* )a - ( const uint8_t* )b;
}
-int main(void){
+int main (void)
+{
int i;
void *k;
- AVTreeNode *root= NULL, *node=NULL;
+ AVTreeNode *root = NULL, *node = NULL;
AVLFG prng;
av_lfg_init(&prng, 1);
- for(i=0; i<10000; i++){
+ for (i = 0; i < 10000; i++) {
int j = av_lfg_get(&prng) % 86294;
- if(check(root) > 999){
+ 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);
- if(!node)
- node= av_mallocz(av_tree_node_size);
- av_tree_insert(&root, (void*)(j+1), cmp, &node);
+ if (!node)
+ node = av_mallocz(av_tree_node_size);
+ av_tree_insert(&root, ( void* )(j + 1), cmp, &node);
j = av_lfg_get(&prng) % 86294;
{
- AVTreeNode *node2=NULL;
+ AVTreeNode *node2 = NULL;
av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
- av_tree_insert(&root, (void*)(j+1), cmp, &node2);
- k= av_tree_find(root, (void*)(j+1), cmp, NULL);
- if(k)
+ av_tree_insert(&root, (void*)(j + 1), cmp, &node2);
+ k = av_tree_find(root, (void*)(j + 1), cmp, NULL);
+ if (k)
av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
}
}
--
1.7.1
_______________________________________________
libav-devel mailing list
libav-devel@libav.org
https://lists.libav.org/mailman/listinfo/libav-devel
