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 <string.h>
29 
30 #include "integer.h"
31 #include "avassert.h"
32 #include "intmath.h"
33 
34 static const AVInteger zero_i;
35 
37  int i, carry=0;
38 
39  for(i=0; i<AV_INTEGER_SIZE; i++){
40  carry= (carry>>16) + a.v[i] + b.v[i];
41  a.v[i]= carry;
42  }
43  return a;
44 }
45 
47  int i, carry=0;
48 
49  for(i=0; i<AV_INTEGER_SIZE; i++){
50  carry= (carry>>16) + a.v[i] - b.v[i];
51  a.v[i]= carry;
52  }
53  return a;
54 }
55 
57  int i;
58 
59  for(i=AV_INTEGER_SIZE-1; i>=0; i--){
60  if(a.v[i])
61  return av_log2_16bit(a.v[i]) + 16*i;
62  }
63  return -1;
64 }
65 
67  AVInteger out;
68  int i, j;
69  int na= (av_log2_i(a)+16) >> 4;
70  int nb= (av_log2_i(b)+16) >> 4;
71 
72  memset(&out, 0, sizeof(out));
73 
74  for(i=0; i<na; i++){
75  unsigned int carry=0;
76 
77  if(a.v[i])
78  for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){
79  carry= (carry>>16) + out.v[j] + a.v[i]*(unsigned)b.v[j-i];
80  out.v[j]= carry;
81  }
82  }
83 
84  return out;
85 }
86 
88  int i;
89  int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1];
90  if(v) return (v>>16)|1;
91 
92  for(i=AV_INTEGER_SIZE-2; i>=0; i--){
93  int v= a.v[i] - b.v[i];
94  if(v) return (v>>16)|1;
95  }
96  return 0;
97 }
98 
100  AVInteger out;
101  int i;
102 
103  for(i=0; i<AV_INTEGER_SIZE; i++){
104  unsigned int index= i + (s>>4);
105  unsigned int v=0;
106  if (index + 1 < AV_INTEGER_SIZE) v = a.v[index + 1] * (1U << 16);
107  if (index < AV_INTEGER_SIZE) v |= a.v[index];
108  out.v[i]= v >> (s&15);
109  }
110  return out;
111 }
112 
114  int i= av_log2_i(a) - av_log2_i(b);
115  AVInteger quot_temp;
116  if(!quot) quot = &quot_temp;
117 
118  if ((int16_t)a.v[AV_INTEGER_SIZE-1] < 0) {
119  a = av_mod_i(quot, av_sub_i(zero_i, a), b);
120  *quot = av_sub_i(zero_i, *quot);
121  return av_sub_i(zero_i, a);
122  }
123 
124  av_assert2((int16_t)a.v[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b.v[AV_INTEGER_SIZE-1] >= 0);
125  av_assert2(av_log2_i(b)>=0);
126 
127  if(i > 0)
128  b= av_shr_i(b, -i);
129 
130  memset(quot, 0, sizeof(AVInteger));
131 
132  while(i-- >= 0){
133  *quot= av_shr_i(*quot, -1);
134  if(av_cmp_i(a, b) >= 0){
135  a= av_sub_i(a, b);
136  quot->v[0] += 1;
137  }
138  b= av_shr_i(b, 1);
139  }
140  return a;
141 }
142 
144  AVInteger quot;
145  av_mod_i(&quot, a, b);
146  return quot;
147 }
148 
150  AVInteger out;
151  int i;
152 
153  for(i=0; i<AV_INTEGER_SIZE; i++){
154  out.v[i]= a;
155  a>>=16;
156  }
157  return out;
158 }
159 
161  uint64_t out = a.v[3];
162 
163  for (int i = 2; i >= 0; i--)
164  out = (out << 16) | a.v[i];
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:160
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:56
avassert.h
av_int2i
AVInteger av_int2i(int64_t a)
Convert the given int64_t to an AVInteger.
Definition: integer.c:149
s
#define s(width, name)
Definition: cbs_vp9.c:198
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:87
av_add_i
AVInteger av_add_i(AVInteger a, AVInteger b)
Definition: integer.c:36
index
int index
Definition: gxfenc.c:89
av_mul_i
AVInteger av_mul_i(AVInteger a, AVInteger b)
Definition: integer.c:66
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:99
av_assert2
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:67
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:255
AVInteger
Definition: integer.h:36
zero_i
static const AVInteger zero_i
Definition: integer.c:34
av_div_i
AVInteger av_div_i(AVInteger a, AVInteger b)
Return a/b.
Definition: integer.c:143
av_mod_i
AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b)
Return a % b.
Definition: integer.c:113
U
#define U(x)
Definition: vpx_arith.h:37
av_sub_i
AVInteger av_sub_i(AVInteger a, AVInteger b)
Definition: integer.c:46
integer.h
AV_INTEGER_SIZE
#define AV_INTEGER_SIZE
Definition: integer.h:34
intmath.h