/* fxor.c :                coded by isaku@pb4.so-net.ne.jp 2009/1/4
乱数 Xorshift のSSE2を使わない高速化

論文に書いてある128ビット Xorshift( xor128() )をコンパイラに
かけるとレジスタの割り当てが無駄になることが多い。

そこで、機械語命令とCのステートメントを1対1に対応したプログラム
( fxor128() )を書き、割り当てが無駄にならないようにした。

Xorshift が使用するレジスタが少なくなることで、
コンパイラがインライン展開したときに、
静的変数や関数の外の変数をより多くレジスタに割り当てることができる。
インライン展開しない場合でも、
関数呼び出しのときにプッシュするレジスタが減り高速になる。

コンパイルオプションを適切にしないと、うまく最適化されないので注意。
例えば VC++ なら /O2 オプションにしないと、かえって遅くなる。

また、16ビットコンパイラでは32ビット演算は、
関数呼び出しをする場合が多いので非常に遅くなる。
そこで16ビットコンパイラの場合は、32ビットの演算をできるだけ
避けて乱数を生成するように fxor128() を書いた。
10倍前後高速になる。

以下のプログラムは xor128() , fxor128() のそれぞれについて、
10億個×10の乱数を足し合わせて、最速の実行時間を比較する。
( 16ビットコンパイラでは10億個ではなく1億個 )

*/

#include <stdio.h>
#include <time.h>
#include <limits.h>

#if INT_MAX == 32767
#define UINT32 unsigned long
#define __inline
#define N 100000000L
#else
#define UINT32 unsigned
#define N 1000000000
#endif

#ifdef LSI_C
#undef CLOCKS_PER_SEC
#endif

#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 100
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl+t.h.dh*100L+t.h.cl*6000L+t.h.ch*360000L;
}
#endif

/* 論文に書いてあった 128 bit Xorshift。 */
__inline UINT32 xor128(void) {
    static UINT32
        x=123456789UL,y=362436069UL,z=521288629UL,w=88675123UL;
    UINT32 t=x^(x<<11);
    x=y; y=z; z=w; return w^=(w>>19)^t^(t>>8);
}

#if INT_MAX != 32767

/* 機械語命令とCのステートメントを1対1にした Xorshift。*/
/* 一見無駄に見えるが、こちらのほうが速いことが多い。*/
__inline UINT32 fxor128(void) {
    static UINT32
        a=123456789UL,b=362436069UL,c=521288629UL,d=88675123UL;
    UINT32 t=a,r=t; t<<=11; t^=r; r=t; r>>=8; t^=r;
    r=b;a=r; r=c;b=r; r=d;c=r; t^=r; r>>=19; r^=t; d=r; return r;
}

#else

/* 16ビットコンパイラ向けの fxor128() */
__inline UINT32 fxor128(void) {
    static UINT32
        a=123456789UL,b=362436069UL,c=521288629UL,d=88675123UL;
    unsigned short tl=(unsigned short)a,th=(unsigned short)(a>>16);
    unsigned short wl=(unsigned short)d,wh=(unsigned short)(d>>16);
    th^=(th<<11)|(tl>>5); tl^=tl<<11;
    tl^=(th<< 8)|(tl>>8); th^=th>> 8; a=b; b=c; c=d;
    wl^=wh>>3; wl^=tl; wh^=th;
    return d=((UINT32)wh<<16)|wl;
}

#endif

int main(void) {
    unsigned long lap,min1,min2,i,sum; int k;

    min1=999999999L; sum=0;
    for (k=0;k<10;k++) {
        lap=clock();
        for (i=0;i<N;i++) sum+=xor128();
        lap=clock()-lap; printf(" %3lu",lap);
#ifdef __GNUC__
        fflush(stdout);
#endif
        if (lap<min1) min1=lap;
    }
    printf("(%lu)%08lx\n",min1,sum);

    min2=999999999L; sum=0;
    for (k=0;k<10;k++) {
        lap=clock();
        for (i=0;i<N;i++) sum+=fxor128();
        lap=clock()-lap; printf(" %3lu",lap);
#ifdef __GNUC__
        fflush(stdout);
#endif
        if (lap<min2) min2=lap;
    }
    printf("(%lu)%08lx ",min2,sum);
    if (min2<=min1)
         printf("%.2f%%fast\n",100.0*(min1-min2)/min1);
    else printf("%.2f%%slow\n",100.0*(min2-min1)/min1);
    return 0;
}