#include <windows.h> enum {W=800, H=600}; HBITMAP hBmp; HWND hwnd; HDC hdc, hdcMem; UCHAR* pic; //將 c1 與 c2 以 nc1:nc-nc1 比例混色, 傳回 BGR 格式 inline int mixColor (int c1, int c2, int nc1, int nc) { int a = nc - nc1; typedef UCHAR U; int r = (U(c1>>16)*nc1 + U(c2>>16)*a)/ nc; int g = (U(c1>>8) *nc1 + U(c2>>8) *a)/ nc; int b = (U(c1) *nc1 + U(c2) *a)/ nc; return (b<<16)|(g<<8)|r; } //在 (tx, ty) 處秀出字型=face, 大小=size 的文字 s, 顏色由 c1 過渡到 c2, void show_text (int tx, int ty, wchar_t* s, int c1, int c2, int size=24, wchar_t* face = L"標楷體") { static int bits = GetDeviceCaps (hdc, BITSPIXEL) * GetDeviceCaps (hdc, PLANES); HFONT font = CreateFont (size,0,0,0,FW_BOLD,0,0,0,0,0,0,0,0,face); HGDIOBJ oldFont = SelectObject (hdcMem, font); SetBkColor (hdcMem,0); SetTextColor (hdcMem, 93); TextOut (hdcMem, 0,0, s, wcslen(s)); SelectObject (hdcMem, oldFont); DeleteObject (font); int p,x,y, h = size, w = size * wcslen(s); if (w > W) w = W; if (h > H) h = H; BITMAPINFO info0 = {{40, w, h, 1, bits, 0,0,0,0,0,0}, {{0}}}; GetDIBits (hdcMem, hBmp, 0, h, pic, &info0, DIB_RGB_COLORS); if (bits == 32) { int *o = (int*) pic; for (p=y=0; y<h; ++y, p+=w) for (x=0; x<w; ++x) if (RGB(0,0,93) == o[p+x]) o[p+x] = mixColor (c1,c2, y,h); else o[p+x] = 0; } BITMAPINFO info = {{40, w, h, 1, bits, 0,0,0,0,0,0}, {{0}}}; SetDIBitsToDevice (hdc, tx,ty,w,h, 0,0,0,h, pic, &info, DIB_RGB_COLORS); } void init() { SetConsoleTitle (L"Conso"); SMALL_RECT size = {0, 0, W-1, H-1}; SetConsoleWindowInfo (GetStdHandle (STD_OUTPUT_HANDLE), TRUE, &size); hdc = GetDC (hwnd = FindWindowW (0, L"Conso")); hdcMem = CreateCompatibleDC (hdc); hBmp = CreateCompatibleBitmap (hdc, W, H); pic = new UCHAR[W*H]; SelectObject (hdcMem, hBmp); } void free() { delete[] pic; ReleaseDC (hwnd, hdc); DeleteObject (hBmp); DeleteDC (hdcMem); } int main (/* daviddr 081104 */) { init(); show_text (30,80, L"漸層字!", RGB(255,10,10), RGB(255,250,50)); show_text (30,120, L"這是48號字體", RGB(55,10,220), RGB(255,90,90), 48); system ("pause"); free(); return 0; }
2009年10月31日 星期六
漸層字
反編譯
「由執行檔轉回 C++ 碼!?」
欲取 VC 資源可用 eXeScope 一類的東西，
欲得知原始碼大略寫法的話:
Dcc，EXE2C，REC，Boomerang，都是 for C...
IDA pro 的 plugin Hex-Rays 可轉出類似 C 的語法。
或許 SourceForge 上有其他更瘋狂的東西 XD
原理是先將 binary code 反組譯 (形如 sourcer、dumpbin、
IDA pro、w32dasm)，再將 asm 解釋成 C。
但...
假設無 platform, endianness 等問題，反編譯仍是困難重重。
由於符號表可能不存在，code 可能因 optimization 或 (C++的)
inline 而變更佈局，且反編譯為一對多映射，C++ 另有 mangle,
vtbl, 模版代換 等問題，產生的結果將比 Perl2C 還難懂 ==;
對 C++ 而言，與其 decompile，不若 rewrite 之。
若是 C# 就容易多了，他的 MSIL 和 Java 的 b-code 一樣，
原始資訊盡在其中 (這樣才能被 interpreter 正確解譯)。
一堆工具如 Ildasm, Reflector, salamande 都可以反編譯出可讀性高的碼。
求根
以下程式輸出為：
0.962398
-0.040659
預測值已跨出區間!
0.000000
-0.040659
預測值已跨出區間!
0.000000
前兩者在 [0,1] 「附近」找過零點，並不保證不越區。
此函式在那附近正好有兩個： 0.962398 與 -0.040659
Secant 根據給出的初始域，往 -0.040659 靠。
至於 Newton-Raphson 就更不可靠了，因發生越區而傳回 0。
若將初始域放大， Newton-Raphson 便可找到根值。
typedef double DF; //double float typedef DF (*FP)(DF); DF abs (DF f) {if (f<0) f=-f; return f;} //以精確度 accuracy, 在 loop 次迭代內求 f 在 [x1,x2] 中的根, //注意! 參數需滿足 x2>x1, 且 [x1,x2] 中至少包含一根 DF false_pos (FP f, DF x1, DF x2, DF accuracy, int loop=64) { DF acc, x,y, y1 = f(x1), y2 = f(x2); for (int i=0; i<loop; ++i) { y = f (x = x1 + (x2-x1) * y1/(y1-y2)); if (y < 0) acc=x1-x, x1=x, y1=y; else acc=x2-x, x2=x, y2=y; if (abs(acc) < accuracy || 0==y) return x; } puts ("root not be found!"); return 0; } DF secant (FP f, DF x1, DF x2, DF accuracy, int loop=64) { DF acc, dx, x = x2, y1 = f(x1), y = f(x2); if (abs(y1) < abs(y)) x=x1, x1=x2, dx=y1, y1=y, y=dx; for (int i=0; i<loop; ++i) { dx = (x1-x) * y/(y-y1); x1 = x; y1 = y; x += dx; y = f (x); if (abs(dx) < accuracy || 0==y) return x; } puts ("root not be found!"); return 0; } //df 為 f 的導函數 DF newton (FP f, FP df, DF x1, DF x2, DF accuracy, int loop=64) { DF acc, dx, x = (x1+x2)*.5; for (int i=0; i<loop; ++i) { x -= dx = f(x) / df(x); if ((x1-x)*(x-x2) < 0) {puts("\n預測值已跨出區間!"); return 0;} if (abs(dx) < accuracy) return x; } puts ("root not be found!"); return 0; } DF f (DF x) { return (((230*x+18)*x+9)*x-221)*x-9; } DF df(DF x) { return ((230*x+18)*x+9)*x-221; } int main() { printf ("\n%f", false_pos (f, 0,1, 1e-6)); printf ("\n%f", secant (f, 0,1, 1e-6)); printf ("\n%f", newton (f, df, 0,1, 1e-6)); return 0; }
Fractal
底下秀出 4 種圖：
1.Koch curve
2.Sierpinski’s Gasket
3.Tree curve
4.Julia set
其中，sierpinski 外緣線需自行接上，
Julia set 觀察窗需手動調整：
#include <windows.h> #include <math.h> #include <complex> #define RGB(r,g,b) (b<<16)|(g<<8)|r enum {W=800, H=600}; HDC hdc; HANDLE hwnd, hIn, hOut; namespace Turtle { //--------------------- 作圖 ----------------------- const float rd = 3.1415927/180.0; int* pic, X, Y, A, ang, step, C; //定義: 畫布, 座標, 角度, 步距, 顏色 float scale; float branch; void clear () { int i = W*H; while (i--) pic[i] = 0; } void show () //注意: 顯示器色彩格式需為 32-bits { BITMAPINFO info = {{40, W, -H, 1,32,0,0,0,0,0,0}, {{0}}}; SetDIBitsToDevice (hdc, 0,0,W,H, 0,0,0,H, pic, &info, DIB_RGB_COLORS); } void set (int x, int y, int d=0, int a=0) {X=x; Y=y; ang=a; step=d;} void setxy (int x, int y) {set(x,y);} void pixel (int x, int y, int c) //繪點 { if (x<0 || y<0 || x>=W || y>=H) return; pic[y*W+x] = c; } void line (int x, int y, int x2, int y2, int c=0xffffff) { int dx= x2-x, dy= y2-y, dirx=1, diry=1, b=0; if (dx < 0) {dx = -dx; dirx= -1;} if (dy < 0) {dy = -dy; diry= -1;} pixel (x,y,c); if (dx<=1 && dy<=1) return; //兩點間隔太小,不予處理 if (dx < dy) { //以Y軸為基準繪製線段 int hy= dy>>1, dotn= dy-2, n=1; do {b += dx; if (b > hy) {b -= dy; x += dirx;} y += diry; pixel (x,y,c); n++; }while (dotn--); }else{ //以X軸為基準繪製線段 int hx= dx>>1, dotn= dx-2, n=1; do {b += dy; if (b > hx) {b -= dx; y += diry;} x += dirx; pixel (x,y,c); n++; }while (dotn--); } } void move (int n, int c=0xffffff) { int x = n* cos (rd*A), y = n* sin (rd*A); line (X, Y, X+x, Y+y, c); X+=x; Y+=y; } void mov (int c=0xffffff) {move (step,c);} void turn (int a) { A+=a; if (A>360) A-=360; else if (A<360) A+=360; } //--------------------- 碎形 ----------------------- void koch (int n) { if (0==n) {mov(); return;} koch (n-1); turn (-60); koch (n-1); turn (120); koch (n-1); turn (-60); koch (n-1); } void sierpinski (int n) { if (0==n) {mov(); return;} sierpinski (n-1); turn(-120); sierpinski (n-1); turn(120); sierpinski (n-1); turn(120); sierpinski (n-1); turn(-120); sierpinski (n-1); } void tree (int n, int x, int y, float len, float ang) { if (0==n) return; setxy(x,y); A=-ang; move(len); x=X; y=Y; tree (n-1, x,y, len/scale, ang-branch); tree (n-1, x,y, len/scale, ang+branch); } void julia (int n) { // z = x+iy, F(z) = z^2+C, |F(z)| = x^2+y^2 int i, k; float v,xp,yp, x0,y0,x1,y1,x,y,z,cx,cy; cx=-0.5; cy=0.5; for (x0=-2.0; x0<=2.0; x0+=0.005) for (y0=-2.0; y0<=2.0; y0+=0.005){ for (x = x0, y = y0, k = 0; x*x+y*y<4.0 && k<n; ++k){ //迭代 n 次,直到數列發散 x1 = x*x - y*y + cx; y1 = 2*x*y + cy; x = x1; y = y1; } xp = W/4*x0+W/2; yp = -H/4*y0+H/2; v = x*x + y*y; if (v < 4.0) { i = v*64; pixel (xp, yp, RGB (100,220,i)); }else pixel (xp, yp, RGB (30,100,200)); } } }; using namespace Turtle; int main (/* daviddr 081020 */) { SetConsoleTitle (L"Conso"); hdc = GetDC (FindWindowW (0, L"Conso")); hIn = GetStdHandle (STD_INPUT_HANDLE); hOut = GetStdHandle (STD_OUTPUT_HANDLE); SMALL_RECT size = {0, 0, W-1, H-1}; SetConsoleWindowInfo (hOut, TRUE, &size); //變更視窗大小 Turtle::pic = new int[W*H]; //畫布 clear (); set (20,380, 8); koch (4); show (); system ("pause"); clear (); set (20,380, 8); sierpinski (5); show (); system ("pause"); clear (); scale = 1.3; branch = 23; tree (8, 200,380, 64, 80); show (); system ("pause"); clear(); julia(32); show (); system ("pause"); delete [] Turtle::pic; DeleteDC (hdc); CloseHandle (hIn); CloseHandle (hOut); return 0; }sierpinski 外緣線由小而大逐次爬行的作法，
很難排除累計誤差，無法形成正三角。
可改為由外而內，用內插方式來算落點：
private: void sierpinski (int n, int x1, int y1, int x2, int y2, int x3, int y3) { if (0 == n) { setxy (x1, y1); mov(); turn (-120); mov(); turn (-120); mov(); turn (-120); return; } sierpinski (n-1, x1,y1, x3,y1, (x1+x3)/2, (y1+y3)/2); sierpinski (n-1, x3,y1, x2,y2, (x2+x3)/2, (y2+y3)/2); sierpinski (n-1, (x1+x3)/2, (y1+y3)/2, (x2+x3)/2, (y2+y3)/2, x3, y3); } public: void sierpin2 (int n) //自頂至底 { int d = step * (1<<n); sierpinski (n, X,Y, X+d,Y, X+d/2, int(float(Y)-1.72384*d/2)); }
下面是呼叫 koch (4), sierpin2 (5), tree (8,..) 的結果：
1除以0
Y=1/X, X 趨近0時, Y 是多少?
if x -> +0 then 1/x = +∞
if x -> -0 then 1/x = -∞
but +∞ ≠ -∞ , paradox
If take it as unsigned infinity, 1/0 = ∞
但此處的「0」意指「無窮小量」，與 1 的「位階」不同。
由於「1」非無窮小，故結果為 ∞
這種定義有個好處是，在 plane of complex numbers z=x+iy
上加入無窮遠點 ∞ = 1/0，則 z 可在球面上表達出來。
也就是說，在 complex plane C 上，
令 S = C∪{∞}
f(z) = z, z ∈ {∞}
g(z) = 1 / z, z ∈ {0}
並定義 1/∞ = 0
則 { f, g } 為 S 之相容圖集，且 S 形成球面。
由於 C 是一種 Riemann surface (1D complex manifold)
此球面便稱為 Riemann sphere。
Riemann sphere 是緊致的，
相當於閉合且有界的歐幾裡德空間子集，
緊空間可以某種方式類似於有限集合，
且定義在緊集上的連續實值函數一致連續，
因而可施以微積分運算。
唉呀我到底在說啥..XD
JPEG編碼流程
若不牽扯到 Jpeg2000 或 Progressive JPEG，只針對 JFIF 基礎標準，
或是只採用 YCbCr + Baseline 模式 + Huffman 編碼的 TIFF 標準，
其作法可簡述如下:
將圖的長寬 zero padding 成 8 的倍數，
以 8x8 區塊為處理單位，理由是:
1. 做成晶片時省材料費 (開玩笑的?)，
2. 程式師偏好 2 的冪次方以利記憶體對齊並加速運算 (半開玩笑的..)，
3. 一般圖像的連續色調常侷限於 17x17 的區塊裡...
將 RGB 轉到均勻色彩空間 YCbCr (最常用的 YUV 一族)，
由於綠光在可見光譜中所佔範圍較大，導致人視網膜上紅藍細胞較少，
加上柱狀細胞占多數，因此我們可保留 Y，而捨棄一些 Cb Cr 訊息，
Jpeg 可施行 4:4:4、4:2:2、4:2:0 3 種 downsampling (三選一)。
之後，將 Y、Cb、Cr 值正規化至 -128~127 (一般，Y 要扣掉 128)，
再分別進行 Forward DCT 變換該矩陣的底基向量
(這部份有許多加速法，例如將 8x8 DCT 分解成 x, y 方向的兩個 1D DCT，
或是用 AA&N 並搭配他們的量化表)，然後將各值除以quantization table
（如 CCIR 601）中對應的值，再取 round。
採用 DCT 而不用 FFT，是因為他能以較少的係數來逼近連續性資料。
(圖釋: http://www.cs.cf.ac.uk/Dave/Multimedia/node231.html)
為了將盡可能多的 0 靠在一起，以利壓縮資料，
需將量化後表中的 AC 值以 Zig-Zag 順序重新編排，
(相當於從低頻排到高頻) 以 EOB 標籤 (1010) 取代尾端那些 0。
至於中間的 0，可用 RLE 壓縮掉，
RLE 中每組值分成 high 4-bits 與 low n-bits 兩部分，
high 4-bits 表示 0 的連續個數，(這和 Jpeg 標籤採用 4-bits 有關)
low bits 表示接在連續 0 後的值，以 Huffman 編碼表之。
low bits 表示的值有可能是 0，因為 high 4-bits 最多只能紀錄
15 個連續的 0，若有 15 個以上的連續 0，low bits 便是 0 了。
因為相鄰兩方塊的平均色彩 (也就是 DC 值) 一般很接近，
也就是說他們的差值很小，可用少量 bits 表示，
便以 DPCM 對區塊間的 DC 值進行 Predictive coding。
最後在各資料前頭貼標籤，存檔。
處理 jpg 檔中的眾多標籤也是件麻煩工作。
如何正確做 Jpeg Canonical Huffman Code 對應的說法很雜，
你可以用 ISO/IEC 10918-1 中給出的 DC, AC 預設編碼表試試看。
Jpeg codec 要寫的完善是件苦工喔...
簡單說來，對 8x8 區塊裡的 63 個 AC 值，以及區塊間 DC 的差值，
分別使用不同的 Huffman 表去編碼。而且 Y 與 CbCr 各有其編碼表，
所以總共有 4 份碼表。
以 Y 成分的 DC 差值為例，將每組差值表示成如下形式：
(Huffman識別碼, 差值的 binary code)
底下用「HI」簡稱「Huffman識別碼」，
用「DL」簡稱「差值 binary code 的長度」。
其碼表為：
若現在 Y 成分有 3 個區塊，其 DC 值分別是 58, 50, 53DL HI長度 HI ----------------------- 0 2 00 1 3 010 2 3 011 3 3 100 4 3 101 5 3 110 6 4 1110 7 5 11110
安插 0 到最前端，便利差值運算，形成 0, 58, 50, 53。
將串列中元素，後者減前者，得差值為:
58 -8 3
差值為負時，先取絕對值，再將位元反相，故得:
111010 0111 11
111010 長度是 7，對照碼表得 HI 為 11110，故編碼成 11110 111010
0111 長度是 4，對照碼表得 HI 為 101，故編碼成 101 0111
11 長度是 2，對照碼表得 HI 為 00，故編碼成 00 11
最後寫入:
11110 111010 + 63個AC編碼
101 0111 + 63個AC編碼
00 11 + 63個AC編碼
為何要安插1個0到最前端做運算?
因為解碼時需要知道第一個 DC 值，才能將之後的 DC 值還原回來，
否則只憑 -8, 3，並無法還原回 58, 50, 53，之後的 IDCT 亦會出錯。
進制轉換
10進位小數轉2進位：
//這種版本是刻意為之的 :-) char* float_to_binary (float f) //進制轉換 { const int N = 128; static char s[N]; char *p = s; int b=0, i=N, n=f; //b 將指向整數部分 //最右端的位置 while (i--) s[i] = '0'; if (f < 0) {++b; *p++='-'; n= f= -f;} //處理負數 if (n == 0) {++b; p++;} //若是 0 if (n) { //算整數部分 i = n; while (i>>=1) ++b; p = s + b; i = n; do *p--+= i&1; while (i>>=1); p = s + b + 1; } *p++ = f-n ?'.': 0; //是否加小數點 while (f -= n) *p+++= n = f*=2; //算小數部分 *p = 0; return s; } int main() { cout << float_to_binary (-20.375); }若不處理小數：
#include <stdio.h> int main () { for (int m,i=0; i<257 && printf("\n%3d\t",i); ++i) for (m=512; m=m>>1; putchar(i&m?49:48)); }或者這樣：(注意: 在不同環境裡會有 Big/Little Endian 與 bit align 問題)
#include <stdio.h> int main() { union { unsigned n; struct {unsigned a:1,b:1,c:1,d:1,e:1,f:1,g:1,h:1,i:1;}; void pnt() { printf ("\n%3d\t%d%d%d%d%d%d%d%d%d", n,i,h,g,f,e,d,c,b,a); } } b = {0}; while (++b.n<257) b.pnt(); }
訂閱：
文章 (Atom)
