FFmpeg  2.8.17
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
integer.c
Go to the documentation of this file.
1 /*
2  * arbitrary precision integers
3  * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 
22 /**
23  * @file
24  * arbitrary precision integers
25  * @author Michael Niedermayer <michaelni@gmx.at>
26  */
27 
28 #include "common.h"
29 #include "integer.h"
30 #include "avassert.h"
31 
32 static const AVInteger zero_i;
33 
35  int i, carry=0;
36 
37  for(i=0; i<AV_INTEGER_SIZE; i++){
38  carry= (carry>>16) + a.v[i] + b.v[i];
39  a.v[i]= carry;
40  }
41  return a;
42 }
43 
45  int i, carry=0;
46 
47  for(i=0; i<AV_INTEGER_SIZE; i++){
48  carry= (carry>>16) + a.v[i] - b.v[i];
49  a.v[i]= carry;
50  }
51  return a;
52 }
53 
55  int i;
56 
57  for(i=AV_INTEGER_SIZE-1; i>=0; i--){
58  if(a.v[i])
59  return av_log2_16bit(a.v[i]) + 16*i;
60  }
61  return -1;
62 }
63 
65  AVInteger out;
66  int i, j;
67  int na= (av_log2_i(a)+16) >> 4;
68  int nb= (av_log2_i(b)+16) >> 4;
69 
70  memset(&out, 0, sizeof(out));
71 
72  for(i=0; i<na; i++){
73  unsigned int carry=0;
74 
75  if(a.v[i])
76  for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){
77  carry= (carry>>16) + out.v[j] + a.v[i]*(unsigned)b.v[j-i];
78  out.v[j]= carry;
79  }
80  }
81 
82  return out;
83 }
84 
86  int i;
87  int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1];
88  if(v) return (v>>16)|1;
89 
90  for(i=AV_INTEGER_SIZE-2; i>=0; i--){
91  int v= a.v[i] - b.v[i];
92  if(v) return (v>>16)|1;
93  }
94  return 0;
95 }
96 
98  AVInteger out;
99  int i;
100 
101  for(i=0; i<AV_INTEGER_SIZE; i++){
102  unsigned int index= i + (s>>4);
103  unsigned int v=0;
104  if(index+1<AV_INTEGER_SIZE) v = a.v[index+1]<<16;
105  if(index <AV_INTEGER_SIZE) v+= a.v[index ];
106  out.v[i]= v >> (s&15);
107  }
108  return out;
109 }
110 
112  int i= av_log2_i(a) - av_log2_i(b);
113  AVInteger quot_temp;
114  if(!quot) quot = &quot_temp;
115 
116  if ((int16_t)a.v[AV_INTEGER_SIZE-1] < 0) {
117  a = av_mod_i(quot, av_sub_i(zero_i, a), b);
118  *quot = av_sub_i(zero_i, *quot);
119  return av_sub_i(zero_i, a);
120  }
121 
122  av_assert2((int16_t)a.v[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b.v[AV_INTEGER_SIZE-1] >= 0);
123  av_assert2(av_log2_i(b)>=0);
124 
125  if(i > 0)
126  b= av_shr_i(b, -i);
127 
128  memset(quot, 0, sizeof(AVInteger));
129 
130  while(i-- >= 0){
131  *quot= av_shr_i(*quot, -1);
132  if(av_cmp_i(a, b) >= 0){
133  a= av_sub_i(a, b);
134  quot->v[0] += 1;
135  }
136  b= av_shr_i(b, 1);
137  }
138  return a;
139 }
140 
142  AVInteger quot;
143  av_mod_i(&quot, a, b);
144  return quot;
145 }
146 
148  AVInteger out;
149  int i;
150 
151  for(i=0; i<AV_INTEGER_SIZE; i++){
152  out.v[i]= a;
153  a>>=16;
154  }
155  return out;
156 }
157 
159  int i;
160  int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1];
161 
162  for(i= AV_INTEGER_SIZE-2; i>=0; i--){
163  out = (out<<16) + a.v[i];
164  }
165  return out;
166 }
167 
168 #ifdef TEST
169 
170 const uint8_t ff_log2_tab[256]={
171  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,
172  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,
173  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,
174  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,
175  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,
176  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,
177  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,
178  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
179 };
180 
181 int main(void){
182  int64_t a,b;
183 
184  for(a=7; a<256*256*256; a+=13215){
185  for(b=3; b<256*256*256; b+=27118){
186  AVInteger ai= av_int2i(a);
187  AVInteger bi= av_int2i(b);
188 
189  av_assert0(av_i2int(ai) == a);
190  av_assert0(av_i2int(bi) == b);
191  av_assert0(av_i2int(av_add_i(ai,bi)) == a+b);
192  av_assert0(av_i2int(av_sub_i(ai,bi)) == a-b);
193  av_assert0(av_i2int(av_mul_i(ai,bi)) == a*b);
194  av_assert0(av_i2int(av_shr_i(ai, 9)) == a>>9);
195  av_assert0(av_i2int(av_shr_i(ai,-9)) == a<<9);
196  av_assert0(av_i2int(av_shr_i(ai, 17)) == a>>17);
197  av_assert0(av_i2int(av_shr_i(ai,-17)) == a<<17);
198  av_assert0(av_log2_i(ai) == av_log2(a));
199  av_assert0(av_i2int(av_div_i(ai,bi)) == a/b);
200  }
201  }
202  return 0;
203 }
204 #endif
float v
const char * s
Definition: avisynth_c.h:631
const char * b
Definition: vf_curves.c:109
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
uint8_t
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:63
uint16_t v[AV_INTEGER_SIZE]
Definition: integer.h:37
int64_t av_i2int(AVInteger a)
Convert the given AVInteger to an int64_t.
Definition: integer.c:158
AVInteger av_int2i(int64_t a)
Convert the given int64_t to an AVInteger.
Definition: integer.c:147
int av_log2_i(AVInteger a)
Return the rounded-down value of the base 2 logarithm of the given AVInteger.
Definition: integer.c:54
AVInteger av_mul_i(AVInteger a, AVInteger b)
Definition: integer.c:64
simple assert() macros that are a bit more flexible than ISO C assert().
int av_cmp_i(AVInteger a, AVInteger b)
Return 0 if a==b, 1 if a>b and -1 if a
Definition: integer.c:85
AVInteger av_add_i(AVInteger a, AVInteger b)
Definition: integer.c:34
const uint8_t ff_log2_tab[256]
Definition: log2_tab.c:23
#define av_log2
Definition: intmath.h:100
int index
Definition: gxfenc.c:89
static const AVInteger zero_i
Definition: integer.c:32
#define av_log2_16bit
Definition: intmath.h:101
AVInteger av_sub_i(AVInteger a, AVInteger b)
Definition: integer.c:44
AVInteger av_shr_i(AVInteger a, int s)
bitwise shift
Definition: integer.c:97
arbitrary precision integers
AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b)
Return a % b.
Definition: integer.c:111
common internal and external API header
#define AV_INTEGER_SIZE
Definition: integer.h:34
AVInteger av_div_i(AVInteger a, AVInteger b)
Return a/b.
Definition: integer.c:141
uint8_t pi<< 24) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0f/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S16, int16_t,(*(constint16_t *) pi >>8)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0f/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S32, int32_t,(*(constint32_t *) pi >>24)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0f/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_FLT, float, av_clip_uint8(lrintf(*(constfloat *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_FLT, float, av_clip_int16(lrintf(*(constfloat *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_FLT, float, av_clipl_int32(llrintf(*(constfloat *) pi *(1U<< 31)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_DBL, double, av_clip_uint8(lrint(*(constdouble *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_DBL, double, av_clip_int16(lrint(*(constdouble *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_DBL, double, av_clipl_int32(llrint(*(constdouble *) pi *(1U<< 31))))#defineSET_CONV_FUNC_GROUP(ofmt, ifmt) staticvoidset_generic_function(AudioConvert *ac){}voidff_audio_convert_free(AudioConvert **ac){if(!*ac) return;ff_dither_free(&(*ac) ->dc);av_freep(ac);}AudioConvert *ff_audio_convert_alloc(AVAudioResampleContext *avr, enumAVSampleFormatout_fmt, enumAVSampleFormatin_fmt, intchannels, intsample_rate, intapply_map){AudioConvert *ac;intin_planar, out_planar;ac=av_mallocz(sizeof(*ac));if(!ac) returnNULL;ac->avr=avr;ac->out_fmt=out_fmt;ac->in_fmt=in_fmt;ac->channels=channels;ac->apply_map=apply_map;if(avr->dither_method!=AV_RESAMPLE_DITHER_NONE &&av_get_packed_sample_fmt(out_fmt)==AV_SAMPLE_FMT_S16 &&av_get_bytes_per_sample(in_fmt)>2){ac->dc=ff_dither_alloc(avr, out_fmt, in_fmt, channels, sample_rate, apply_map);if(!ac->dc){av_free(ac);returnNULL;}returnac;}in_planar=ff_sample_fmt_is_planar(in_fmt, channels);out_planar=ff_sample_fmt_is_planar(out_fmt, channels);if(in_planar==out_planar){ac->func_type=CONV_FUNC_TYPE_FLAT;ac->planes=in_planar?ac->channels:1;}elseif(in_planar) ac->func_type=CONV_FUNC_TYPE_INTERLEAVE;elseac->func_type=CONV_FUNC_TYPE_DEINTERLEAVE;set_generic_function(ac);if(ARCH_AARCH64) ff_audio_convert_init_aarch64(ac);if(ARCH_ARM) ff_audio_convert_init_arm(ac);if(ARCH_X86) ff_audio_convert_init_x86(ac);returnac;}intff_audio_convert(AudioConvert *ac, AudioData *out, AudioData *in){intuse_generic=1;intlen=in->nb_samples;intp;if(ac->dc){av_log(ac->avr, AV_LOG_TRACE,"%dsamples-audio_convert:%sto%s(dithered)\n", len, av_get_sample_fmt_name(ac->in_fmt), av_get_sample_fmt_name(ac->out_fmt));returnff_convert_dither(ac-> out
int main(int argc, char **argv)
Definition: main.c:22