FFmpeg
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 }
out
FILE * out
Definition: movenc.c:54
av_log2_16bit
int av_log2_16bit(unsigned v)
Definition: intmath.c:31
b
#define b
Definition: input.c:41
av_i2int
int64_t av_i2int(AVInteger a)
Convert the given AVInteger to an int64_t.
Definition: integer.c:158
av_log2_i
int av_log2_i(AVInteger a)
Return the rounded-down value of the base 2 logarithm of the given AVInteger.
Definition: integer.c:54
avassert.h
av_int2i
AVInteger av_int2i(int64_t a)
Convert the given int64_t to an AVInteger.
Definition: integer.c:147
s
#define s(width, name)
Definition: cbs_vp9.c:257
av_cmp_i
int av_cmp_i(AVInteger a, AVInteger b)
Return 0 if a==b, 1 if a>b and -1 if a<b.
Definition: integer.c:85
av_add_i
AVInteger av_add_i(AVInteger a, AVInteger b)
Definition: integer.c:34
index
int index
Definition: gxfenc.c:89
av_mul_i
AVInteger av_mul_i(AVInteger a, AVInteger b)
Definition: integer.c:64
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
av_shr_i
AVInteger av_shr_i(AVInteger a, int s)
bitwise shift
Definition: integer.c:97
av_assert2
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:64
AVInteger::v
uint16_t v[AV_INTEGER_SIZE]
Definition: integer.h:37
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
AVInteger
Definition: integer.h:36
common.h
zero_i
static const AVInteger zero_i
Definition: integer.c:32
av_div_i
AVInteger av_div_i(AVInteger a, AVInteger b)
Return a/b.
Definition: integer.c:141
av_mod_i
AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b)
Return a % b.
Definition: integer.c:111
av_sub_i
AVInteger av_sub_i(AVInteger a, AVInteger b)
Definition: integer.c:44
integer.h
AV_INTEGER_SIZE
#define AV_INTEGER_SIZE
Definition: integer.h:34