libavutil/integer.c

   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 = &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(&quot, 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 }