Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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. AVInteger av_add_i(AVInteger a, AVInteger b){
  33.     int i, carry=0;
  34.  
  35.     for(i=0; i<AV_INTEGER_SIZE; i++){
  36.         carry= (carry>>16) + a.v[i] + b.v[i];
  37.         a.v[i]= carry;
  38.     }
  39.     return a;
  40. }
  41.  
  42. AVInteger av_sub_i(AVInteger a, AVInteger b){
  43.     int i, carry=0;
  44.  
  45.     for(i=0; i<AV_INTEGER_SIZE; i++){
  46.         carry= (carry>>16) + a.v[i] - b.v[i];
  47.         a.v[i]= carry;
  48.     }
  49.     return a;
  50. }
  51.  
  52. int av_log2_i(AVInteger a){
  53.     int i;
  54.  
  55.     for(i=AV_INTEGER_SIZE-1; i>=0; i--){
  56.         if(a.v[i])
  57.             return av_log2_16bit(a.v[i]) + 16*i;
  58.     }
  59.     return -1;
  60. }
  61.  
  62. AVInteger av_mul_i(AVInteger a, AVInteger b){
  63.     AVInteger out;
  64.     int i, j;
  65.     int na= (av_log2_i(a)+16) >> 4;
  66.     int nb= (av_log2_i(b)+16) >> 4;
  67.  
  68.     memset(&out, 0, sizeof(out));
  69.  
  70.     for(i=0; i<na; i++){
  71.         unsigned int carry=0;
  72.  
  73.         if(a.v[i])
  74.             for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){
  75.                 carry= (carry>>16) + out.v[j] + a.v[i]*b.v[j-i];
  76.                 out.v[j]= carry;
  77.             }
  78.     }
  79.  
  80.     return out;
  81. }
  82.  
  83. int av_cmp_i(AVInteger a, AVInteger b){
  84.     int i;
  85.     int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1];
  86.     if(v) return (v>>16)|1;
  87.  
  88.     for(i=AV_INTEGER_SIZE-2; i>=0; i--){
  89.         int v= a.v[i] - b.v[i];
  90.         if(v) return (v>>16)|1;
  91.     }
  92.     return 0;
  93. }
  94.  
  95. AVInteger av_shr_i(AVInteger a, int s){
  96.     AVInteger out;
  97.     int i;
  98.  
  99.     for(i=0; i<AV_INTEGER_SIZE; i++){
  100.         unsigned int index= i + (s>>4);
  101.         unsigned int v=0;
  102.         if(index+1<AV_INTEGER_SIZE) v = a.v[index+1]<<16;
  103.         if(index  <AV_INTEGER_SIZE) v+= a.v[index  ];
  104.         out.v[i]= v >> (s&15);
  105.     }
  106.     return out;
  107. }
  108.  
  109. AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){
  110.     int i= av_log2_i(a) - av_log2_i(b);
  111.     AVInteger quot_temp;
  112.     if(!quot) quot = &quot_temp;
  113.  
  114.     av_assert2((int16_t)a.v[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b.v[AV_INTEGER_SIZE-1] >= 0);
  115.     av_assert2(av_log2_i(b)>=0);
  116.  
  117.     if(i > 0)
  118.         b= av_shr_i(b, -i);
  119.  
  120.     memset(quot, 0, sizeof(AVInteger));
  121.  
  122.     while(i-- >= 0){
  123.         *quot= av_shr_i(*quot, -1);
  124.         if(av_cmp_i(a, b) >= 0){
  125.             a= av_sub_i(a, b);
  126.             quot->v[0] += 1;
  127.         }
  128.         b= av_shr_i(b, 1);
  129.     }
  130.     return a;
  131. }
  132.  
  133. AVInteger av_div_i(AVInteger a, AVInteger b){
  134.     AVInteger quot;
  135.     av_mod_i(&quot, a, b);
  136.     return quot;
  137. }
  138.  
  139. AVInteger av_int2i(int64_t a){
  140.     AVInteger out;
  141.     int i;
  142.  
  143.     for(i=0; i<AV_INTEGER_SIZE; i++){
  144.         out.v[i]= a;
  145.         a>>=16;
  146.     }
  147.     return out;
  148. }
  149.  
  150. int64_t av_i2int(AVInteger a){
  151.     int i;
  152.     int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1];
  153.  
  154.     for(i= AV_INTEGER_SIZE-2; i>=0; i--){
  155.         out = (out<<16) + a.v[i];
  156.     }
  157.     return out;
  158. }
  159.  
  160. #ifdef TEST
  161.  
  162. const uint8_t ff_log2_tab[256]={
  163.         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,
  164.         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,
  165.         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,
  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.         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,
  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. };
  172.  
  173. int main(void){
  174.     int64_t a,b;
  175.  
  176.     for(a=7; a<256*256*256; a+=13215){
  177.         for(b=3; b<256*256*256; b+=27118){
  178.             AVInteger ai= av_int2i(a);
  179.             AVInteger bi= av_int2i(b);
  180.  
  181.             av_assert0(av_i2int(ai) == a);
  182.             av_assert0(av_i2int(bi) == b);
  183.             av_assert0(av_i2int(av_add_i(ai,bi)) == a+b);
  184.             av_assert0(av_i2int(av_sub_i(ai,bi)) == a-b);
  185.             av_assert0(av_i2int(av_mul_i(ai,bi)) == a*b);
  186.             av_assert0(av_i2int(av_shr_i(ai, 9)) == a>>9);
  187.             av_assert0(av_i2int(av_shr_i(ai,-9)) == a<<9);
  188.             av_assert0(av_i2int(av_shr_i(ai, 17)) == a>>17);
  189.             av_assert0(av_i2int(av_shr_i(ai,-17)) == a<<17);
  190.             av_assert0(av_log2_i(ai) == av_log2(a));
  191.             av_assert0(av_i2int(av_div_i(ai,bi)) == a/b);
  192.         }
  193.     }
  194.     return 0;
  195. }
  196. #endif
  197.