integer.c (3950B)
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 36 AVInteger av_add_i(AVInteger a, AVInteger b){ 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 46 AVInteger av_sub_i(AVInteger a, AVInteger b){ 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 56 int av_log2_i(AVInteger a){ 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 66 AVInteger av_mul_i(AVInteger a, AVInteger b){ 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 87 int av_cmp_i(AVInteger a, AVInteger b){ 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 99 AVInteger av_shr_i(AVInteger a, int s){ 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 113 AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){ 114 int i= av_log2_i(a) - av_log2_i(b); 115 AVInteger quot_temp; 116 if(!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 143 AVInteger av_div_i(AVInteger a, AVInteger b){ 144 AVInteger quot; 145 av_mod_i(", a, b); 146 return quot; 147 } 148 149 AVInteger av_int2i(int64_t a){ 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 160 int64_t av_i2int(AVInteger a){ 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 }