integer.c 3.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166
  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. * @file
  23. * arbitrary precision integers
  24. * @author Michael Niedermayer <michaelni@gmx.at>
  25. */
  26. #include "common.h"
  27. #include "integer.h"
  28. #include "avassert.h"
  29. static const AVInteger zero_i;
  30. AVInteger av_add_i(AVInteger a, AVInteger b){
  31. int i, carry=0;
  32. for(i=0; i<AV_INTEGER_SIZE; i++){
  33. carry= (carry>>16) + a.v[i] + b.v[i];
  34. a.v[i]= carry;
  35. }
  36. return a;
  37. }
  38. AVInteger av_sub_i(AVInteger a, AVInteger b){
  39. int i, carry=0;
  40. for(i=0; i<AV_INTEGER_SIZE; i++){
  41. carry= (carry>>16) + a.v[i] - b.v[i];
  42. a.v[i]= carry;
  43. }
  44. return a;
  45. }
  46. int av_log2_i(AVInteger a){
  47. int i;
  48. for(i=AV_INTEGER_SIZE-1; i>=0; i--){
  49. if(a.v[i])
  50. return av_log2_16bit(a.v[i]) + 16*i;
  51. }
  52. return -1;
  53. }
  54. AVInteger av_mul_i(AVInteger a, AVInteger b){
  55. AVInteger out;
  56. int i, j;
  57. int na= (av_log2_i(a)+16) >> 4;
  58. int nb= (av_log2_i(b)+16) >> 4;
  59. memset(&out, 0, sizeof(out));
  60. for(i=0; i<na; i++){
  61. unsigned int carry=0;
  62. if(a.v[i])
  63. for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){
  64. carry= (carry>>16) + out.v[j] + a.v[i]*(unsigned)b.v[j-i];
  65. out.v[j]= carry;
  66. }
  67. }
  68. return out;
  69. }
  70. int av_cmp_i(AVInteger a, AVInteger b){
  71. int i;
  72. int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1];
  73. if(v) return (v>>16)|1;
  74. for(i=AV_INTEGER_SIZE-2; i>=0; i--){
  75. int v= a.v[i] - b.v[i];
  76. if(v) return (v>>16)|1;
  77. }
  78. return 0;
  79. }
  80. AVInteger av_shr_i(AVInteger a, int s){
  81. AVInteger out;
  82. int i;
  83. for(i=0; i<AV_INTEGER_SIZE; i++){
  84. unsigned int index= i + (s>>4);
  85. unsigned int v=0;
  86. if(index+1<AV_INTEGER_SIZE) v = a.v[index+1]<<16;
  87. if(index <AV_INTEGER_SIZE) v+= a.v[index ];
  88. out.v[i]= v >> (s&15);
  89. }
  90. return out;
  91. }
  92. AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){
  93. int i= av_log2_i(a) - av_log2_i(b);
  94. AVInteger quot_temp;
  95. if(!quot) quot = &quot_temp;
  96. if ((int16_t)a.v[AV_INTEGER_SIZE-1] < 0) {
  97. a = av_mod_i(quot, av_sub_i(zero_i, a), b);
  98. *quot = av_sub_i(zero_i, *quot);
  99. return av_sub_i(zero_i, a);
  100. }
  101. av_assert2((int16_t)a.v[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b.v[AV_INTEGER_SIZE-1] >= 0);
  102. av_assert2(av_log2_i(b)>=0);
  103. if(i > 0)
  104. b= av_shr_i(b, -i);
  105. memset(quot, 0, sizeof(AVInteger));
  106. while(i-- >= 0){
  107. *quot= av_shr_i(*quot, -1);
  108. if(av_cmp_i(a, b) >= 0){
  109. a= av_sub_i(a, b);
  110. quot->v[0] += 1;
  111. }
  112. b= av_shr_i(b, 1);
  113. }
  114. return a;
  115. }
  116. AVInteger av_div_i(AVInteger a, AVInteger b){
  117. AVInteger quot;
  118. av_mod_i(&quot, a, b);
  119. return quot;
  120. }
  121. AVInteger av_int2i(int64_t a){
  122. AVInteger out;
  123. int i;
  124. for(i=0; i<AV_INTEGER_SIZE; i++){
  125. out.v[i]= a;
  126. a>>=16;
  127. }
  128. return out;
  129. }
  130. int64_t av_i2int(AVInteger a){
  131. int i;
  132. int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1];
  133. for(i= AV_INTEGER_SIZE-2; i>=0; i--){
  134. out = (out<<16) + a.v[i];
  135. }
  136. return out;
  137. }