[FFmpeg-devel] [RFC] support encrypted asf

[Michael Niedermayer]

On Mon, Oct 08, 2007 at 08:42:56AM +0200, Reimar D?ffinger wrote:
> Hello,
> since it was such an interesting problem I could not stop myself from
> optimizing the inverse() function.
> It probably is easier to understand without algebra knowledge, but a
> bit more obfuscated for those with.
> On x86 the speed difference is only about 10%, multiplication is just
> too fast on those ;-).
> Here it is (tell me if you'd prefer an updated complete patch instead):
> 
> static uint32_t inverse(uint32_t v) {
>     uint32_t factor = 1;
>     uint32_t product = v;
>     uint32_t mask = 2;
>     do {
>       v <<= 1;
>       factor |= product & mask;
>       product += v & -(product & mask);
>       // should be mask <<= 1; but then gcc misses the
>       // optimization opportunity to use the Z-flag for the while test
>       mask += mask;
>     } while (mask);
>     return factor;
> }

interresting, btw a multiply based variant with fewer multiplies is:

static uint32_t inverse(uint32_t v) {
    uint32_t v3, v6, v12;
#define POW3(v)  v*=v; v*=v; v*=v
#define POW6(v)  POW3(v); POW3(v)
#define POW12(v) POW6(v); POW6(v)
    v3= v*v*v;
    v6=v3= v3*v3*v;
    POW3(v6);
    v12=v6= v6*v3;
    POW6(v12);
    v3=v12= v12*v6;
    POW12(v3);
    v3*=v12;
    POW6(v3);
    v3 *=v6;
    return v3*v3*v;
}

or a LUT based variant

static uint32_t inverse2(uint32_t v) {
    uint32_t a,b;
    a= inv[v&255];

    b= (a*v)>>8;
    b*= a;
    a-= b<<8;
    b= (a*v)>>16;
    b*= a;

    return a - (b<<16);
}

for(i=1; i<256; i+=2)
    inv[i]= inverse(i);

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

In a rich man's house there is no place to spit but his face.
-- Diogenes of Sinope
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20071008/2125bda1/attachment.pgp>