2009年10月30日 星期五

開根號

 
算平方根:
inline float sqrt (register float f)
{
    _asm {
        fld f
        fsqrt
        fstp f
    }
    return f;
}

算任意方根:
用 Newton-Raphson 求 root:
將 y = x 的 n 次方
化成 f(r) = r^n - y , r = 初始預測值
令逼近根 r' = r+e,取 Taylor Expansion:

        0 = f (r+e) = f (r) + e*f'(r) + e*e*f"(r)/2 + ...
        0 = f'(r+e) = f'(r) + e*f"(r) + ...

用前兩項來預測:

        f(r) + e*f'(r) = 0
        e = -f(r)/f'(r)

得出新的根
     
        r' = r - f(r)/f'(r)  
寫成 code 便是:
double root (double m, double n)
{      
    for (double x,d,r=m, e=1; e>5e-6; m-=e=(d*m-r)/(n*d))      
        for (d=m, x=1; x<n-1; ++x) d*=m;
    return m;
}

int main (/* daviddr 081225 */)
{
     float x, n;
     scanf ("%f %f", &x, &n);         
     printf ("%f\n", root (x,n));
}

唯讀字串


char *p = "hello world!"; 
    p[0] = 'H'; 
此段程式首先將 p 指向一個唯讀字串 (const char [13]) 的起始位址,
此字串在 VC++ Debug Mode 下,位於記憶體的唯讀區段中,如下所示:
(在 Release Mode 下,某些版本會放在可讀寫的 .DATA 中)
.686P
        .XMM
        .model  flat

CONST   SEGMENT
$SG18132 DB 'hello world!', 00H     ;<-----位於此處
CONST   ENDS

_TEXT   SEGMENT
_main   PROC
        push    ebp
        mov ebp, esp
        push    ecx
        mov DWORD PTR _p$[ebp], OFFSET $SG18132
        mov eax, DWORD PTR _p$[ebp]
        mov BYTE PTR [eax], 72          ;'H'
        xor eax, eax
        mov esp, ebp
        pop ebp
        ret 0
_main   ENDP
_TEXT   ENDS
CONST SEGMENT 對應到的 Page Table Entry,其 R/W 旗標設為 0,
使索引到的內容可讀不可寫,一旦指令變更此段記憶體的內容,
會發生存取違規。

若是用 g++ 編,則會置於唯讀 .rdata 區段
.section .rdata,"dr"
LC0:
    .ascii "hello world!\0"
    .text
    .align 2
.globl _main
    .def    _main;  .scl 2; .type 32;   .endef
_main:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $8, %esp            #播出一塊空間放 p
    movl    $LC0, -4(%ebp)      #p = "hello world!"
    movl    -4(%ebp), %eax      #eax = p
    movb    $72, (%eax)         #p[0] = 'H'
    movl    $0, %eax
    leave
    ret


改成 char p[] = "hello world!"; 
或 char p[] = {"hello world!"}; 後,
程式分配 16Bytes 的堆疊空間給 p[],
並將 "hello world!" 由常數區複印一份到此空間中。
此堆疊區段可讀、可寫、可執行,故之後 p[0]='H' 時,
便不會因寫入常數區段而發生存取違規。 

_TEXT   SEGMENT
        _p$ = -16                        ; size = 13, 對齊 4k 邊界後為 16
_main   PROC
        push    ebp
        mov ebp, esp
        sub esp, 16                      ;挪出可容納 13 Byte 的堆疊空間 
        mov eax, DWORD PTR $SG18132      ;將 eax 指向 $SG18132 開始拷貝字串       
        mov DWORD PTR _p$[ebp], eax      ;拷貝hell
        mov ecx, DWORD PTR $SG18132+4
        mov DWORD PTR _p$[ebp+4], ecx    ;拷貝o wo
        mov edx, DWORD PTR $SG18132+8
        mov DWORD PTR _p$[ebp+8], edx    ;拷貝rld!
        mov al, BYTE PTR $SG18132+12
        mov BYTE PTR _p$[ebp+12], al     ;拷貝\0
        mov BYTE PTR _p$[ebp], 72        ;令 p[0] = 'H'
        xor eax, eax
        mov esp, ebp
        pop ebp
        ret 0
_main   ENDP
_TEXT   ENDS

g++ 下,亦生成類似的拷貝動作,只是拷貝方向不同:
_main:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $40, %esp
    movl    LC0, %eax
    movl    %eax, -24(%ebp)
    movl    LC0+4, %eax
    movl    %eax, -20(%ebp)
    movl    LC0+8, %eax
    movl    %eax, -16(%ebp)
    movzbl  LC0+12, %eax
    movb    %al, -12(%ebp)
    movb    $72, -24(%ebp)
    movl    $0, %eax
    leave
    ret

欲在 Intel 保護模式下存取唯讀區段,可建立一個 segment descriptor,
將第 9 bit 置為 1,再指向該區段,進行分頁存取。

Linux 下可使用 mprotect
#include <sys/mman.h>
#include <limits.h>
.....
if (-1 != mprotect (p, strlen(p), PROT_WRITE)) 
    p[0] = 'H';
Win32 下可使用 VirtualProtect
#include <windows.h>
.....
DWORD oldFlag;
if (VirtualProtect (p, strlen(p), PAGE_READWRITE, &oldFlag))
    p[0] = 'H';

再來比較 "\0" 與 '\0':

\x 是指將 x 映射成 ASCII 或其他指定碼表中索引為 x 的字元。
'\0' 一般被編譯成 .asm 中的常數定字,成為組語指令的「一部份」。

"\0" 則佔有 2 個字元碼寬,位於 Stack 常數保護區中,
其 asm code 視被 assign 的對象以及編譯器類型而有所不同,
Visual Studio 2008 實作方法為:

char b;
    char ch = '0';       //mov  byte ptr [ch],30h 

    char a[] = "\0";     //mov  ax,word ptr ["\0" (428978h)] 
                         //mov  word ptr [a], ax 

    char *p = "\0";      //mov  dword ptr [p], offset "\0" (428978h) 
    char *c;

    c = a;               //lea  eax,[a] 
                         //mov  dword ptr [c],eax 

    c = p;               //mov  eax,dword ptr [p] 
                         //mov  dword ptr [c],eax 

    b = ch;              //mov  al,byte ptr [ch] 
                         //mov  byte ptr ,al 

'\0' 成為定字 0x30,可直接編成機器碼:C6 45 EF 30
此處,array 的配置較 pointer 繁瑣,多了 3 Byte:
array 機器碼:66 A1 78 89 42 00 66 89 45 E0 pointer 機器碼:C7 45 D4 78 89 42 00
但使用上能以較快的微指令來實作 (lea 一般占 1-cycle,
可勝出大部分 mov 家族) 來實作,故速度較快。

魔方陣

 
N 階奇數魔方陣:
void magic (int n)
{   
    int m [9*9] = {0};
    int i=0, o=n-1, r=0, c=n/2;

    while (i < n*n) {
        m [r*n+c] = ++i; 
        i%n? (r?--r:r=o), c-o?++c: c=0: ++r;
    }
    while (i--) 
        printf ("%3d%c", m[i], i%n?' ':'\n');  
    puts ("");                              
}

int main (/* daviddr 081224 */)
{    
    return magic(5), getch();
}

針對(2k+1)*(2k+1)方陣,傳統製作方法是: 1. 以 (k,0) 做為起點。 ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │ │ │ │ ├─┼─┼─┤ │ │ │ │ └─┴─┴─┘ 2. 朝右上方移動 (令x++,y--),遇到邊緣則繞捲。 ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │ │ │ │ ├─┼─┼─┤ │ │ │2│ (2由上往下繞捲到此處) └─┴─┴─┘ ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │3│ │ │ (3由右往左繞捲到此處) ├─┼─┼─┤ │ │ │2│ └─┴─┴─┘ 3. 當(x,y)處的右上方已有數字時,便往下放在(x,y+1) 放置時遇到邊緣則繞捲。 ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │3│ │ │ ├─┼─┼─┤ │4│ │2│ └─┴─┴─┘ 4. 重複此法填到最後一個數字。

簡易電子琴

 
按 zxcvbnmasdfghjqwertyu 發音,
按 0~7 變更樂器,樂器種類可在 prog[] 裡自行變更。
樂器編號有點忘了,印象中是 0~127,可自行改變。
有些樂器如法國號等,聲音很吵,拉的很長,這部分程式未做處理;
pitchs[] = {0,2,4,5,7,9,11} 用來跳過 {1,3,6,8,10}
等 5 筆黑鍵音,因為鍵盤的編排很難將黑鍵安插進來。
#pragma comment(lib, "winmm.lib")
#include <conio.h>  
#include <stdio.h>  
#include <windows.h>
#include <mmsystem.h>

#define DO(s) if (MMSYSERR_NOERROR != s) {\
            printf ("Error in %s: %d",__FILE__,__LINE__);\
            getch(); exit(1);\
        }

HMIDIOUT midi;   

void play (int state, int d1=0, int d2=0)
{
    UCHAR data[4] = {state, d1, d2, 0};
    DO (midiOutShortMsg (midi, *(DWORD*)data));            
}

UCHAR get_pitch (char ch)
{
    static char *p, key[] = "zxcvbnmasdfghjqwertyu";
    static UCHAR pitchs[] = {0,2,4,5,7,9,11};
    for (p=key; *p && ch^*p; ++p);
    return (60-12) + 12*((p-key)/7) + pitchs [(p-key)%7];
}
int main (/* daviddr 081223 */)
{
    int  ch, prog[] = {0,13,24,15,7,73,46,53}; //樂器編號
    DO (midiOutOpen (&midi, 0,0,0, CALLBACK_NULL));
    while (VK_ESCAPE != (ch = getch()))         
        if ('0'<=ch && ch<='7') 
            play (0xC0, prog[ch-'0']);
        else {
            play (0x80); 
            play (0x90, get_pitch(ch), 100);
        }         
    midiOutReset (midi);
    midiOutClose (midi);
    return 0;
}

影片播放器


#pragma comment (lib, "comctl32.lib") 
#pragma comment (lib, "dxguid.lib")
#pragma comment (lib, "strmiids.lib")
#ifndef UNICODE
#define UNICODE
#endif
#define daviddr 090430
#include <windows.h>
#include <commctrl.h>
#include <dshow.h>

#include <cstdio>
extern"C" WINBASEAPI HWND WINAPI GetConsoleWindow();
#define MsgBox(s) MessageBox (0,s,0,MB_OK)

WCHAR e_str[256];
void cdecl MsgBox_ (wchar_t* fmt, ...)
   {swprintf_s (e_str, 256, fmt, (char*)(&fmt+1)); MsgBox(e_str);}

namespace FileDlg
{
    WCHAR title[256] = L"*.*";
    WCHAR filter[256] = 
        L"AVI File (*.avi)\0*.avi\0"   
        L"MPEG File (*.mpg)\0*.mpg\0"   
        L"Mp3 File (*.mp3)\0*.mp3\0"   
        L"Wave File (*.wav)\0*.wav\0"   
        L"All Files (*.*)\0*.*\0\0";
    WCHAR file_name[512], init_dir[512], exe_path[512]={0}, *fname;
    OPENFILENAME ofn = {
            sizeof(OPENFILENAME), 0, 0, (LPCWSTR)filter,0,0,1, title, 
            512, file_name, 512, init_dir, 0, 6, 0,1, L"", 0,0,0
    };
    LPWSTR open (HWND hwnd)
    {
        ofn.hwndOwner    = hwnd;
        ofn.lpstrTitle   = L"開檔"; 
        ofn.lpstrFilter  = filter;
        ofn.Flags        = 6; 
        ofn.lpstrFile[0] = 0;               //若開檔後仍為0表示按了[Cancel]

        if (!GetOpenFileName (&ofn)) { 
            if(*ofn.lpstrFile) 
                MsgBox_ (L"Fail to open: %d", CommDlgExtendedError()); 
            return 0;
        }
        return fname = ofn.lpstrFile;       //取個短名字        
    }
}


#define DO(b) if (FAILED(b)) \
              {MsgBox_(L"fail in %s line %d",__FILE__,__LINE__);}


struct Player
{
    bool bPlaying; 
    long evCode;
    LONGLONG pos, duration;           
    IMediaEvent*   pEvent;
    IGraphBuilder* pGraph;
    IMediaControl* pCtrl;
    IVideoWindow*  pVideo;
    IMediaSeeking* pSeek;

    void init()
    {
        bPlaying = false;
        DO (CoCreateInstance (CLSID_FilterGraph, 0, CLSCTX_INPROC, 
                        IID_IGraphBuilder, (void**) &pGraph));
        DO (pGraph->QueryInterface (IID_IMediaControl, (void**) &pCtrl));
        DO (pGraph->QueryInterface (IID_IVideoWindow,  (void**) &pVideo));
        DO (pGraph->QueryInterface (IID_IMediaEvent,   (void**) &pEvent));
        DO (pGraph->QueryInterface (IID_IMediaSeeking, (void**) &pSeek));
    }
    void free()
    {
        if (bPlaying) {
            setTimeInfo (0);
            pCtrl->Stop();
        }
        pVideo->put_Visible (OAFALSE);
        pVideo->put_Owner (0);
        pSeek->Release();
        pCtrl->Release();
        pGraph->Release();        
    }
    void run (WCHAR* path, HWND hwnd)
    {
        bPlaying = true;
        DO (pGraph->RenderFile (path, 0));
        DO (pVideo->put_Owner ((OAHWND)hwnd));
        resize (hwnd);
        DO (pCtrl->Run());
    }
    void resize (HWND hwnd)
    {
        if (!bPlaying) return;
        RECT rc; GetClientRect (hwnd, &rc);
        DO (pVideo->put_WindowStyle (WS_CHILD| WS_CLIPSIBLINGS));
        DO (pVideo->SetWindowPosition (0, 0, rc.right, rc.bottom-20));
    }
    void getTimeInfo()
    {
        pSeek->GetCurrentPosition (&pos);
        pSeek->GetDuration (&duration);   
    }
    void setTimeInfo (double pos_)
    {
        LONGLONG duration = 1;
        pSeek->GetDuration (&duration);
        duration *= pos_;
        pSeek->SetPositions (&duration,
            AM_SEEKING_AbsolutePositioning,
            NULL, AM_SEEKING_NoPositioning);
    }
    void pause (bool b) {b?pCtrl->Pause():pCtrl->Run();}
};

//-------------------------- 主程式 -------------------------------

HINSTANCE  e_hInst;

LRESULT CALLBACK WndProc (HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    static enum {ID_TIMER, ID_OPEN, ID_PAUSE, ID_SLIDER};
    static bool bPause;
    static int w,h;
    static Player player;
    static HMENU  hMenu;  
    static HWND   hSlider;             //scroll handle
    
    switch (msg)
    {
      case WM_CREATE:
           hMenu = (HMENU) CreateMenu();
           AppendMenu (hMenu, MF_STRING, ID_OPEN,  L"開檔");
           AppendMenu (hMenu, MF_STRING, ID_PAUSE, L"暫停");
           SetMenu (hwnd, hMenu);
           hSlider = CreateWindow (TRACKBAR_CLASS, L"",
                     WS_CHILD| WS_VISIBLE| TBS_AUTOTICKS, 216,4,256,16,
                     hwnd, (HMENU)ID_SLIDER, e_hInst, 0);
           SendMessage (hSlider, TBM_SETRANGE, TRUE, MAKELONG(1,1000));
           SendMessage (hSlider, TBM_SETPOS, TRUE, 1);
           return 0;

      case WM_CLOSE:           
           if (player.bPlaying) {
               player.free();
               KillTimer (hwnd, ID_TIMER);                   
           }
           PostQuitMessage(0);
           return 0;  

      case WM_SIZE:
           player.resize (hwnd);
           w = LOWORD (lParam);
           h = HIWORD (lParam);
           MoveWindow (hSlider, 2, h-20, w-4, 20, TRUE);     
           return 0;

      case WM_KEYDOWN:
           switch (wParam) {
             case VK_ESCAPE: SendMessage (hwnd, WM_CLOSE, 0, 0); break;
             case VK_RETURN: player.pause (bPause = !bPause); break;
           }
           return 0;

      case WM_HSCROLL:
           player.setTimeInfo (
               double(SendMessage (hSlider, TBM_GETPOS, 0, 0))/1000);
           return 0;

      case WM_TIMER:
           player.getTimeInfo();
           SendMessage (hSlider, TBM_SETPOS, TRUE,
               player.pos * 1000 / player.duration);
           return 0;

      case WM_COMMAND:
           if (ID_OPEN == LOWORD(wParam)) {           
               if (FileDlg::open (hwnd)) {               //若開檔成功
                   if (player.bPlaying) {                //關閉計時器
                       player.free();
                       KillTimer (hwnd, ID_TIMER);
                   }
                   bPause = false;
                   swprintf_s (e_str, L"%s", FileDlg::fname);
                   SetWindowText (hwnd, e_str);   
                   player.init();           
                   player.run (FileDlg::fname, hwnd);
                   SetTimer (hwnd, ID_TIMER, 20, 0);     //啟動計時器
               }    
           }else if (ID_PAUSE == LOWORD(wParam))           
               player.pause (bPause = !bPause);
           return 0;
          
      default: return  DefWindowProc (hwnd, msg, wParam, lParam);
    }
    return 0;          
}

int WINAPI WinMain (HINSTANCE hInst, HINSTANCE, PSTR, int nShow)
{
    CoInitialize (0);            
    WNDCLASSEX wc = {0x30,3,WndProc,0,0,hInst,0,0,(HBRUSH)1,0,L"DS",0};
    if (!RegisterClassEx(&wc)) return 0;  
    HWND hwnd = CreateWindow (L"DS",L"Player",
        13565952,100,50,560,500,0,0,hInst,0);
    if (!hwnd) return 0;  
    e_hInst = hInst;
    MSG msg; ShowWindow (hwnd, nShow);
    while (GetMessage (&msg, 0,0,0)) {
        TranslateMessage (&msg);
        DispatchMessage (&msg);
    }
    CoUninitialize();
    return msg.wParam;
}

OOXX

 
無 AI 版本,在框框內按滑鼠左鍵落子。
#include <windows.h>
#include <stdio.h>
extern "C" WINBASEAPI HWND WINAPI GetConsoleWindow();

int main (/* 090701 */)
{
    short pos, x, y, ch = 0, rnd = 0, c[11] = {0}; 
    short win[] = {7,56,73,84,146,273,292,448,0}, *w;
    char  map[] = "□ □ □\n□ □ □\n□ □ □";
    COORD coor  = {0,0};        
    POINT p; puts (map); 
   
    while (rnd < 9) {
        GetCursorPos (&p);
        ScreenToClient (GetConsoleWindow(), &p);
        pos = (x=p.x-2)/21 + ((y=p.y-2)/15)*3;
        if (x<0 || x>60 || y<0 || y>42 || c[pos] ||
            GetAsyncKeyState (1)>=0) continue;
        SetConsoleCursorPosition 
            (GetStdHandle (STD_OUTPUT_HANDLE), coor);
        map[pos*3]   = "○╳"[ch*2  ];
        map[pos*3+1] = "○╳"[ch*2+1];
        puts (map);
        c[ch+9] |= (c[pos] = 1) << pos;
        for (w=win; *w; *w==(c[ch+9]&*w)? rnd=99, w=win+8: w++);                
        if (rnd != 99) ch = !ch, rnd++;
    }
    system ("pause"+ !printf (9==rnd? "\n平手":"\n%c 獲勝", "OX"[ch]));
}

彈跳球



#undef  UNICODE
#undef _UNICODE
#pragma comment (lib, "msimg32.lib")
#define daviddr_2009_7_1

#include <windows.h>
#include <cmath>
#include <time.h>
#define ID_TIMER 1

const int cW = 640, cH = 480;           //記錄視窗真實邊界

int bW = cW - 2*GetSystemMetrics (SM_CXSIZEFRAME); 
int bH = cH - 2*GetSystemMetrics (SM_CYSIZEFRAME)-
                GetSystemMetrics (SM_CYCAPTION);                  
HDC hdcMem;

struct Ball
{
    COLORREF c;
    float x, y, vx, vy, r;

    float vlen() {
        return sqrt (vx*vx + vy*vy);
    }
    void draw() {
        SetDCBrushColor (hdcMem, c);
        Ellipse (hdcMem, x-r, y-r, x+r, y+r);
    }
    void move() {                    
        x += vx;  y += vy;
        if (x<=r)   x=r+1,  vx=-vx; 
        if (x>bW-r) x=bW-r, vx=-vx;
        if (y<=r)   y=r+1,  vy=-vy;  
        if (y>bH-r) y=bH-r, vy=-vy;            
    }
}; 

void collide_test (Ball& a, Ball& b)
{
    if (&a == &b) return;                   //不可能和自身碰撞
    float dot, 
          dx = b.x-a.x, 
          dy = b.y-a.y,
          r  = a.r + b.r, 
          d  = dx*dx + dy*dy;

    if (d < r*r && (d = sqrt (d)) &&         
        0 < (dx*a.vx + dy*a.vy)/(a.vlen()*d)){
        dx /= d; 
        dy /= d;      
        dot = b.vx*dx - a.vx*dx + b.vy*dy - a.vy*dy;
        dx *= dot; 
        dy *= dot;
        a.vx += dx; a.vy += dy;  
        b.vx -= dx; b.vy -= dy;        
    }
}


LRESULT CALLBACK WndProc (HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    static PAINTSTRUCT ps;
    static HBITMAP     hBmp;
    static HDC         hdc;
    static int i, j;
    static const int DELAY = 16;
    static const int nBall = 22;
    static Ball ball[nBall];
    static GRADIENT_RECT grect = {0,1};
    #define RC (rand()%256)<<8 
    static TRIVERTEX vtx[2] = {{0,0,RC,RC,RC,0},{bW,bH,RC,RC,RC,0}};
    
    switch (msg) 
    {
       case WM_CREATE:    
            hdc    = GetDC (hwnd);
            hdcMem = CreateCompatibleDC (hdc);
            hBmp   = CreateCompatibleBitmap (hdc, cW, cH);
            ReleaseDC (hwnd, hdc);
            SelectObject (hdcMem, hBmp);
            DeleteObject (hBmp);
            SelectObject (hdcMem, GetStockObject(DC_BRUSH));
            SetTimer (hwnd, ID_TIMER, DELAY, 0);
            for (i=0; i<nBall; ++i) {
                ball[i].c  = RGB(rand()%256,rand()%256,rand()%256);
                ball[i].x  = rand()%cW;
                ball[i].y  = rand()%cH;
                ball[i].r  = 10+rand()%36;
                ball[i].vx = float (4+rand()%8);
                ball[i].vy = float (4+rand()%8);                
            }
            return 0;
            
       case WM_DESTROY:
            KillTimer (hwnd, ID_TIMER);
            DeleteDC (hdcMem);
            PostQuitMessage (0);
            return 0; 
            
       case WM_PAINT:
            hdc = BeginPaint (hwnd, &ps);
            GradientFill (hdcMem, vtx, 2, &grect, 1, 1);
            for (i=0; i<nBall; ++i) ball[i].draw();
            BitBlt (hdc, 0,0, cW, cH, hdcMem, 0,0, SRCCOPY);
            EndPaint (hwnd, &ps);
            return 0; 
    
       case WM_TIMER:       
            for (i=0; i<nBall; ++i) {
                ball[i].move(); 
                for (j=0; j<nBall; ++j)
                    collide_test (ball[i], ball[j]);
            }
            InvalidateRect (hwnd, 0, false);
            return 0;
    }
    return DefWindowProc (hwnd, msg, wParam, lParam);    
}

int WINAPI WinMain (HINSTANCE hInst, HINSTANCE, PSTR, int nShow)
{
    srand ((UINT)time(0));            
    WNDCLASSEX wc = {0x30,3,WndProc,0,0,hInst,0,0,(HBRUSH)1,0,"T",0};
    if (!RegisterClassEx(&wc)) return 0; 
    HWND hwnd = CreateWindow ("T"," ",13565952,100,50,cW,cH,0,0,hInst,0);
    if (!hwnd) return 0;  
    MSG msg;  
    ShowWindow (hwnd, nShow);
    while (GetMessage (&msg, 0,0,0)) {
        TranslateMessage (&msg);
        DispatchMessage (&msg);
    }
    return msg.wParam;
}