Statistics
| Branch: | Revision:

ffmpeg / libavutil / integer.c @ 80a07f6e

History | View | Annotate | Download (5.06 KB)

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 libavutil/integer.c
24
 * arbitrary precision integers
25
 * @author Michael Niedermayer <michaelni@gmx.at>
26
 */
27

    
28
#include "common.h"
29
#include "integer.h"
30

    
31
AVInteger av_add_i(AVInteger a, AVInteger b){
32
    int i, carry=0;
33

    
34
    for(i=0; i<AV_INTEGER_SIZE; i++){
35
        carry= (carry>>16) + a.v[i] + b.v[i];
36
        a.v[i]= carry;
37
    }
38
    return a;
39
}
40

    
41
AVInteger av_sub_i(AVInteger a, AVInteger b){
42
    int i, carry=0;
43

    
44
    for(i=0; i<AV_INTEGER_SIZE; i++){
45
        carry= (carry>>16) + a.v[i] - b.v[i];
46
        a.v[i]= carry;
47
    }
48
    return a;
49
}
50

    
51
int av_log2_i(AVInteger a){
52
    int i;
53

    
54
    for(i=AV_INTEGER_SIZE-1; i>=0; i--){
55
        if(a.v[i])
56
            return av_log2_16bit(a.v[i]) + 16*i;
57
    }
58
    return -1;
59
}
60

    
61
AVInteger av_mul_i(AVInteger a, AVInteger b){
62
    AVInteger out;
63
    int i, j;
64
    int na= (av_log2_i(a)+16) >> 4;
65
    int nb= (av_log2_i(b)+16) >> 4;
66

    
67
    memset(&out, 0, sizeof(out));
68

    
69
    for(i=0; i<na; i++){
70
        unsigned int carry=0;
71

    
72
        if(a.v[i])
73
            for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){
74
                carry= (carry>>16) + out.v[j] + a.v[i]*b.v[j-i];
75
                out.v[j]= carry;
76
            }
77
    }
78

    
79
    return out;
80
}
81

    
82
int av_cmp_i(AVInteger a, AVInteger b){
83
    int i;
84
    int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1];
85
    if(v) return (v>>16)|1;
86

    
87
    for(i=AV_INTEGER_SIZE-2; i>=0; i--){
88
        int v= a.v[i] - b.v[i];
89
        if(v) return (v>>16)|1;
90
    }
91
    return 0;
92
}
93

    
94
AVInteger av_shr_i(AVInteger a, int s){
95
    AVInteger out;
96
    int i;
97

    
98
    for(i=0; i<AV_INTEGER_SIZE; i++){
99
        unsigned int index= i + (s>>4);
100
        unsigned int v=0;
101
        if(index+1<AV_INTEGER_SIZE) v = a.v[index+1]<<16;
102
        if(index  <AV_INTEGER_SIZE) v+= a.v[index  ];
103
        out.v[i]= v >> (s&15);
104
    }
105
    return out;
106
}
107

    
108
AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){
109
    int i= av_log2_i(a) - av_log2_i(b);
110
    AVInteger quot_temp;
111
    if(!quot) quot = &quot_temp;
112

    
113
    assert((int16_t)a[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b[AV_INTEGER_SIZE-1] >= 0);
114
    assert(av_log2(b)>=0);
115

    
116
    if(i > 0)
117
        b= av_shr_i(b, -i);
118

    
119
    memset(quot, 0, sizeof(AVInteger));
120

    
121
    while(i-- >= 0){
122
        *quot= av_shr_i(*quot, -1);
123
        if(av_cmp_i(a, b) >= 0){
124
            a= av_sub_i(a, b);
125
            quot->v[0] += 1;
126
        }
127
        b= av_shr_i(b, 1);
128
    }
129
    return a;
130
}
131

    
132
AVInteger av_div_i(AVInteger a, AVInteger b){
133
    AVInteger quot;
134
    av_mod_i(&quot, a, b);
135
    return quot;
136
}
137

    
138
AVInteger av_int2i(int64_t a){
139
    AVInteger out;
140
    int i;
141

    
142
    for(i=0; i<AV_INTEGER_SIZE; i++){
143
        out.v[i]= a;
144
        a>>=16;
145
    }
146
    return out;
147
}
148

    
149
int64_t av_i2int(AVInteger a){
150
    int i;
151
    int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1];
152

    
153
    for(i= AV_INTEGER_SIZE-2; i>=0; i--){
154
        out = (out<<16) + a.v[i];
155
    }
156
    return out;
157
}
158

    
159
#ifdef TEST
160
#undef NDEBUG
161
#include <assert.h>
162

    
163
const uint8_t ff_log2_tab[256]={
164
        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,
165
        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,
166
        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,
167
        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,
168
        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,
169
        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,
170
        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,
171
        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
172
};
173

    
174
int main(void){
175
    int64_t a,b;
176

    
177
    for(a=7; a<256*256*256; a+=13215){
178
        for(b=3; b<256*256*256; b+=27118){
179
            AVInteger ai= av_int2i(a);
180
            AVInteger bi= av_int2i(b);
181

    
182
            assert(av_i2int(ai) == a);
183
            assert(av_i2int(bi) == b);
184
            assert(av_i2int(av_add_i(ai,bi)) == a+b);
185
            assert(av_i2int(av_sub_i(ai,bi)) == a-b);
186
            assert(av_i2int(av_mul_i(ai,bi)) == a*b);
187
            assert(av_i2int(av_shr_i(ai, 9)) == a>>9);
188
            assert(av_i2int(av_shr_i(ai,-9)) == a<<9);
189
            assert(av_i2int(av_shr_i(ai, 17)) == a>>17);
190
            assert(av_i2int(av_shr_i(ai,-17)) == a<<17);
191
            assert(av_log2_i(ai) == av_log2(a));
192
            assert(av_i2int(av_div_i(ai,bi)) == a/b);
193
        }
194
    }
195
    return 0;
196
}
197
#endif