[FFmpeg-devel] [RFC] integer.h overhaul
Michael Niedermayer
michaelni at gmx.at
Fri Oct 12 04:31:50 CEST 2012
On Thu, Oct 11, 2012 at 10:47:36AM +0200, Stefano Sabatini wrote:
> On date Tuesday 2012-10-09 19:52:12 +0200, Michael Niedermayer encoded:
> > On Tue, Oct 09, 2012 at 07:15:37PM +0200, Stefano Sabatini wrote:
> > > On date Tuesday 2012-10-09 18:45:12 +0200, Michael Niedermayer encoded:
> > > > On Tue, Oct 09, 2012 at 05:01:28PM +0200, Stefano Sabatini wrote:
> > > > > Hi,
> > > > >
> > > > > I needed to extend big integer support to make it able to contain up
> > > > > to 2304 bits (144 16-bits words), so I re-worked the API to avoid to
> > > > > pass huge arrays by value.
> > > >
> > > > why do you need to work with such large integers ?
> > >
> > > > please explain the algorithm you try to implement
> > >
> > > Check the xface patch, it encodes a 48x48 bitmap as a big integer (so
> > > it is 48x48 bits = 144 16-bits words, integer.c supports up to 8).
> > >
> > > Another possibility would be to implement custom routines in the xface
> > > code, but I thought sharing code with libavutil was a good thing.
> > >
> > > > why do you remove the pass by value ?
> > > > multiplying 2 such numbers will take probably around a million
> > > > cpu cyles, with the current implementation that was not designed for
> > > > this, copying such a number in pass by value will take maybe around
> > > > hundread cpu cyles.
> > >
> > > > so this isnt making it faster but it makes its interface quite
> > > > awkward to use IMHO
> > >
> > > Yes, indeed I was not so sure about it. I can change that and/or
> > > ripristinate the old interface (or leave it as it was), my only
> > > problem is to raise the maximum number of supported digits (that's why
> > > I published this as an RFC).
> >
> > iam not sure whats the best thing to do, one would be simply to move
> > all to the header and use code like:
> >
> > #define AV_INTEGER_SIZE 123
> > #include "libavutil/integer.h"
> >
> > another would be to switch to references as you do but drop the upper
> > limit. so that the size of each number is decided when its allocated
> > but it seems overkill, we dont need these features currently ...
>
> Implemented the first suggestion (which has the nice property that no
> API/ABI is even exposed). Problem is, the code is too slow, xface
> takes several seconds to encode an image, which is not acceptable.
> --
> FFmpeg = Faithless and Fabulous Muttering Plastic Ermetic Genius
> Makefile | 1
> integer.c | 128 ------------------------------------------------------
> integer.h | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
> 3 files changed, 135 insertions(+), 139 deletions(-)
> 2f2fb85fba18f0b071cee86b15eb6b74ed335995 0001-lavu-integer-make-all-functions-static-inline.patch
> From 876138da203c8b65b60297c1904e83e9bfdfc657 Mon Sep 17 00:00:00 2001
> From: Stefano Sabatini <stefasab at gmail.com>
> Date: Wed, 10 Oct 2012 12:08:59 +0200
> Subject: [PATCH] lavu/integer: make all functions static inline
>
> Allow to specify a maximum number of words to work with, before including
> the file.
> ---
> libavutil/Makefile | 1 +
> libavutil/integer.c | 128 ---------------------------------------------
> libavutil/integer.h | 145 +++++++++++++++++++++++++++++++++++++++++++++++----
> 3 files changed, 135 insertions(+), 139 deletions(-)
>
> diff --git a/libavutil/Makefile b/libavutil/Makefile
> index 96eada8..4be27af 100644
> --- a/libavutil/Makefile
> +++ b/libavutil/Makefile
> @@ -115,6 +115,7 @@ TESTPROGS = adler32 \
> eval \
> file \
> fifo \
> + integer \
> lfg \
> lls \
> md5 \
> diff --git a/libavutil/integer.c b/libavutil/integer.c
> index 5bcde0d..6aee462 100644
> --- a/libavutil/integer.c
> +++ b/libavutil/integer.c
> @@ -29,134 +29,6 @@
> #include "integer.h"
> #include "avassert.h"
>
> -AVInteger av_add_i(AVInteger a, AVInteger b){
> - int i, carry=0;
> -
> - for(i=0; i<AV_INTEGER_SIZE; i++){
> - carry= (carry>>16) + a.v[i] + b.v[i];
> - a.v[i]= carry;
> - }
> - return a;
> -}
> -
> -AVInteger av_sub_i(AVInteger a, AVInteger b){
> - int i, carry=0;
> -
> - for(i=0; i<AV_INTEGER_SIZE; i++){
> - carry= (carry>>16) + a.v[i] - b.v[i];
> - a.v[i]= carry;
> - }
> - return a;
> -}
> -
> -int av_log2_i(AVInteger a){
> - int i;
> -
> - for(i=AV_INTEGER_SIZE-1; i>=0; i--){
> - if(a.v[i])
> - return av_log2_16bit(a.v[i]) + 16*i;
> - }
> - return -1;
> -}
> -
> -AVInteger av_mul_i(AVInteger a, AVInteger b){
> - AVInteger out;
> - int i, j;
> - int na= (av_log2_i(a)+16) >> 4;
> - int nb= (av_log2_i(b)+16) >> 4;
> -
> - memset(&out, 0, sizeof(out));
> -
> - for(i=0; i<na; i++){
> - unsigned int carry=0;
> -
> - if(a.v[i])
> - for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){
> - carry= (carry>>16) + out.v[j] + a.v[i]*b.v[j-i];
> - out.v[j]= carry;
> - }
> - }
> -
> - return out;
> -}
> -
> -int av_cmp_i(AVInteger a, AVInteger b){
> - int i;
> - int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1];
> - if(v) return (v>>16)|1;
> -
> - for(i=AV_INTEGER_SIZE-2; i>=0; i--){
> - int v= a.v[i] - b.v[i];
> - if(v) return (v>>16)|1;
> - }
> - return 0;
> -}
> -
> -AVInteger av_shr_i(AVInteger a, int s){
> - AVInteger out;
> - int i;
> -
> - for(i=0; i<AV_INTEGER_SIZE; i++){
> - unsigned int index= i + (s>>4);
> - unsigned int v=0;
> - if(index+1<AV_INTEGER_SIZE) v = a.v[index+1]<<16;
> - if(index <AV_INTEGER_SIZE) v+= a.v[index ];
> - out.v[i]= v >> (s&15);
> - }
> - return out;
> -}
> -
> -AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){
> - int i= av_log2_i(a) - av_log2_i(b);
> - AVInteger quot_temp;
> - if(!quot) quot = "_temp;
> -
> - av_assert2((int16_t)a.v[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b.v[AV_INTEGER_SIZE-1] >= 0);
> - av_assert2(av_log2_i(b)>=0);
> -
> - if(i > 0)
> - b= av_shr_i(b, -i);
> -
> - memset(quot, 0, sizeof(AVInteger));
> -
> - while(i-- >= 0){
> - *quot= av_shr_i(*quot, -1);
> - if(av_cmp_i(a, b) >= 0){
> - a= av_sub_i(a, b);
> - quot->v[0] += 1;
> - }
> - b= av_shr_i(b, 1);
> - }
> - return a;
> -}
> -
> -AVInteger av_div_i(AVInteger a, AVInteger b){
> - AVInteger quot;
> - av_mod_i(", a, b);
> - return quot;
> -}
> -
> -AVInteger av_int2i(int64_t a){
> - AVInteger out;
> - int i;
> -
> - for(i=0; i<AV_INTEGER_SIZE; i++){
> - out.v[i]= a;
> - a>>=16;
> - }
> - return out;
> -}
> -
> -int64_t av_i2int(AVInteger a){
> - int i;
> - int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1];
> -
> - for(i= AV_INTEGER_SIZE-2; i>=0; i--){
> - out = (out<<16) + a.v[i];
> - }
> - return out;
> -}
> -
> #ifdef TEST
>
> const uint8_t ff_log2_tab[256]={
> diff --git a/libavutil/integer.h b/libavutil/integer.h
> index 45f733c..32f8257 100644
> --- a/libavutil/integer.h
> +++ b/libavutil/integer.h
> @@ -29,58 +29,181 @@
> #define AVUTIL_INTEGER_H
>
> #include <stdint.h>
> +#include "avassert.h"
> #include "common.h"
>
> +#ifndef AV_INTEGER_SIZE
> #define AV_INTEGER_SIZE 8
> +#endif
>
> typedef struct AVInteger{
> uint16_t v[AV_INTEGER_SIZE];
> } AVInteger;
>
> -AVInteger av_add_i(AVInteger a, AVInteger b) av_const;
> -AVInteger av_sub_i(AVInteger a, AVInteger b) av_const;
> +static inline AVInteger av_add_i(AVInteger a, AVInteger b)
> +{
> + int i, carry=0;
> +
> + for(i=0; i<AV_INTEGER_SIZE; i++){
> + carry= (carry>>16) + a.v[i] + b.v[i];
> + a.v[i]= carry;
> + }
> + return a;
> +}
> +
> +static inline AVInteger av_sub_i(AVInteger a, AVInteger b)
iam not sure its a good idea that they are all inline functions
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Many things microsoft did are stupid, but not doing something just because
microsoft did it is even more stupid. If everything ms did were stupid they
would be bankrupt already.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20121012/8869b656/attachment.asc>
More information about the ffmpeg-devel
mailing list