用 Python 跑 Multi-threading 版 PNG 最佳化

我一直有收大圖的習慣，每次看到有人貼的高解析度的圖，雖然檔案很大，也幾乎沒辦法光以 22 吋螢幕就能一覽全圖而必須拖曳觀看或者以螢幕最適大小縮放觀看，但是這些圖幾乎都是直接以掃描器掃描下來的圖，沒有經過太多破壞 (頂多去紋理、去字、去摺痕、連接空白等等)，十分不錯。前幾個月前偶然發現 PNG 檔可以經由再一次的最佳化運算來縮小檔案尺寸而不破壞原圖 (其他軟體如 pngnq, pngquant 是真的會針對原圖進行減色的最佳化方式，我使用的只針對壓縮流最佳化，應無此種問題)，這對於硬碟中有許多張超大體積的 PNG 檔可真是福音，為它們減個肥日後也才能塞更多XD

首先我發現的是 OptiPNG 這套軟體，能夠將 PNG 檔的壓縮流給重新整理後最佳化，需要的是 CPU 的運算能力，非常耗時間。原本以為一套就夠了，誰知道找下去又發現還有 PNGOUT，這玩意兒我在 IrfanView 看圖軟體裡面有見過，在另存 png 時可以選擇啟用它以進行最佳化。這套軟體強在它可以進行非常多次的暴力極限運算，一次次的降低檔案大小。只要你給它時間，它就能給你不斷縮小的檔案大小。不過這耗費時間真是非常可觀，只能以龜速形容。更何況我相信這絕對會有個極限的，不過是逐步逼近，看著這一次的長久運算只省下了 1024 bytes 的空間，你確定還要繼續下去？

好吧，有這兩套應該就完美了吧，你錯了。經過我深入研究，其實還有許多發展空間，其中 RT 對這方面的研究似乎還滿透徹的，無意間在 MozTW.org 被我發現相關討論串，還在外國的某交流論壇發現 RT hack 過的 OptiPNG，可以進行更好的最佳化。似乎沒發現有其他人有這樣作，看起來 RT 這方面還挺行的。離題了，他在這篇討論串提到他都是使用多套軟體交互運算以取得最佳結果，其中許多套都套用 hack 過 zlib 函式庫或其他地方，加了更多更好的算法，比起原官方程式來說更能得出好結果。他也提供自己所編的檔案跟使用的批次檔，非常有價值。

@ECHO OFF<br /> FOR %1 %%i IN (*.png) DO (<br /> touch.exe -r "%%~i" "%%~i.time"<br /> optipng.exe -zw32k -zc9 -zm9 -zs0,3 -f0,5 -i0 "%%~i"<br /> advdef.exe -z -4 "%%~i"<br /> deflopt.exe -b "%%~i"<br /> pngout /y /b0 "%%~i"<br /> IF NOT ERRORLEVEL 2 (<br /> advdef.exe -z -4 "%%~i"<br /> deflopt.exe -b "%%~i"<br /> )<br /> touch.exe -r "%%~i.time" "%%~i"<br /> IF EXIST "%%~i.time" del "%%~i.time"<br /> )
我對他作了修正，以讓我能夠不僅處理相同目錄下的 PNG 檔，更可以指定單一 PNG 或是目錄來進行處理，這樣就非常方便了。
@ECHO OFF<br /> SETLOCAL<br /> SET BASE=%~dp0<br /> IF /I "%~x1" == ".PNG" (<br /> REM Specified File<br /> SET PATN="%~f1"<br /> ) ELSE (<br /> REM Folder<br /> CD /D %~f1<br /> SET PATN="*.png"<br /> )<br /> <br /> FOR %%i IN (%PATN%) DO (<br /> %BASE%\touch -r "%%~i" "%%~i.time"<br /> <br /> REM OptiPNG Optimized<br /> %BASE%\optipng_c2d -zw32k -zc9 -zm9 -zs0,3 -f0,5 -i0 "%%~i"<br /> %BASE%\advdef_rthack -z -4 "%%~i"<br /> %BASE%\deflopt -b "%%~i"<br /> <br /> REM PNGOut Optimized<br /> %BASE%\pngout /y /b0 "%%~i"<br /> IF NOT ERRORLEVEL 2 (<br /> %BASE%\advdef_rthack -z -4 "%%~i"<br /> %BASE%\deflopt -b "%%~i"<br /> )<br /> <br /> %BASE%\touch -r "%%~i.time" "%%~i"<br /> IF EXIST "%%~i.time" del "%%~i.time"<br /> )<br /> ENDLOCAL<br /> PAUSE
這樣還不夠。雖然已經是非常方便了，但是前面提到這些軟體所進行的運算是非常耗費 CPU 資源的一項工作，所以要是有許多超高解析 PNG 大檔，不算個幾小時可能不會全部完成。打開工作管理員你會吐血：這些最佳化程式沒有一個是原生支援多核心處理的！換言之以我的 Core2 Duo E6300 來說，常常都是跑在 50% 的地方，剩下的 50% 永遠吃不到，這是不支援多執行緒程式的一大弱點。雖然多執行緒可以很有效的加快速度，但是這些演算法是否有針對多核心的處理方式？搞的不好還會發生非同步化問題讓速度有減無增，資源都耗在結果的同步上了，這樣也不是好選擇。總之不管為什麼 WinRAR, 7-Zip 等軟體的壓縮演算法都支援多執行緒，而此 PNG 最佳化竟然沒有，有沒有其他方法呢？

當然有，如果沒有我還要繼續打嗎？不知道你有沒有用過 foobar2000 轉過音樂的經驗？LAME 這一套 MP3 編碼器同樣不具備原生支援多執行緒功能 (好像有其他非官方 hack 實作出來，不管他)，但是當你的 CPU 支援，foobar2000 可以一次執行多個 LAME 實體分別轉換不同首音軌，以達成多核心運用的最佳方式。反正每一個 LAME 實體只要負責自己分配到的那首音軌就好，就沒有非同步化的問題，看起來就像多了好幾位工人分別處理不同事務一樣，不互相影響。

所以我的想法出來了，之前都是一個 Batch 批次檔在進行處理，我可不可以以類似的想法，同時自動產生多個處理行程？這樣我的 CPU 多核心就能發揮最大效用。昨天剛學會的 Python 似乎已經有原生 Multi-Threading 支援 (Java 也有，以前好像是 Green threads 現在不知改原生了沒；Ruby 則還是 Green threads)，讓我們學會寫多執行緒程式來榨乾 CPU 效能吧！

在 Google 搜尋「Python threading」可以找到前人的成果，我看了快樂過活@資料無限大，能力無限大: [Python]Threading這篇網誌的介紹跟引用，了解了基本的觀念。簡單來說 Python 採用 Queue 佇列跟 Threading 的配合來解決同步問題，你只要在一開始將要處理的東西推進佇列裡面，接下來隨意開幾個執行緒，這些工人們就會自己去抓來處理，無須你煩心囉。我直接先把我的成果貼上來：
#!/usr/bin/env python<br /> import Queue<br /> import threading<br /> import os, sys, glob<br /> <br /> queue = Queue.Queue()<br /> <br /> def Processlet():<br /> while True:<br /> file = queue.get()<br /> print 'Processing: ' + file + "\n"<br /> os.system('opti-one.bat "%s"' % file)<br /> queue.task_done()<br /> <br /> def main():<br /> for i in range(2):<br /> t = threading.Thread(target=Processlet)<br /> t.setDaemon(True)<br /> t.start()<br /> <br /> if len(sys.argv) == 1:<br /> print """OptiPNG Suite (Milti-Threading Implementation)<br /> Usage: mt.py [Folder]<br /> """<br /> sys.exit(0)<br /> <br /> dir = glob.glob(sys.argv[1] + '\\*.png')<br /> for f in dir:<br /> queue.put(f)<br /> <br /> queue.join()<br /> <br /> if __name__ == '__main__':<br /> main()<br />
這個簡單的 Python 程式使用了 threading, Queue 來達成多執行緒架構，然後我為了其他的需求而引了其他函式庫。os 用來呼叫外部程式用的，sys 用來抓命令列參數，glob 則是方便我簡單的下萬用字元就能搜尋符合的 PNG 檔案。

首先我建立了一個叫做 Processlet 的函式 (#8-14)，這個就是我的執行緒要執行的內容 (工人)，他會不斷的執行我指定的要求 (有個 while 迴圈包住了)。然後是 main 程式進入點 (#15-32)，我在這邊使用 for 迴圈產生了兩個執行緒 (因為我的 CPU 是雙核心)，這邊使用委任的方式直接呼叫 threading.Thread 包住我的 Processlet 函式，產生一個執行緒。網路上有些人是用繼承的方式繼承一個執行緒類別再撰寫內容，但我的程式簡單，使用此種委任方式也很直覺。

#21-26 是處理沒有輸入參數的情況，顯示的預設說明訊息。此訊息清楚的說明我的程式是這樣呼叫的：mt.py [資料夾路徑]，比方說 mt.py "B:\"。當我取得了目錄位置後我使用 glob 來下查詢，得到此目錄下的所有 png 檔案絕對位置 (#27-30)。這下子終於可以把它們推到佇列，準備進行我們的工作囉。

#31 要做的事只有一個，把佇列關起來。同時告訴執行緒工作開始了！這跟搭乘遊樂區的雲霄飛車設施一樣，人都就座了服務員就會關門，不讓其他人進入搗亂，同時代表刺激的旅程要開始了。

讓我們再回到 #10-13，Processlet 的核心。當佇列關閉同時代表可以開始的同時，剛才產生的數個執行緒就會爭先恐後的開始工作，誰也不會等誰，因此工作的分配使用佇列來管理是十分妥善的。這邊主要要做的是取出處理檔案名稱、執行外部程式和告知此工作完成三個，剛好一人一行。從 Queue 中 get 出檔案位置後，我利用 os 提供的 system 函式來呼叫剛才寫好的 bat 檔案，為何不寫在 py 檔案的原因是我已經有寫好的 bat 了，一來套用方便，二來可以分開維護 (py 負責多執行緒，bat 負責最佳化 PNG；跟 foobar2000 負責多執行緒，LAME 負責轉檔相同)。等漫長的 BAT 執行完成後，要告訴執行緒我們已經完成一項工作，以便再取得新的工作內容，有 task_done() 這個函式可以用。

---

以上就是全部的架構，當我執行 mt.py 同時在命令列參數指定目錄時，Python 就會產生兩個執行緒，以外部批次檔去處理我的 PNG 檔案了。這時候再打開工作管理員 (或者功能更強的 Process Explorer) 你就可以看到 CPU 被吃滿的情況了 (Process Explorer 更能看到 python.exe 有兩個 cmd.exe 子行程，呼叫一堆 exe 在處理檔案)。速度是變快了，但是這樣就不能邊轉換邊上網了，很頓啊 XDDD

初學 Python - 寫一個 BT 熱烈度偵測器

我發現要學習程式語言，一定得有個目標作為動力(或是推力)，學的才會快。比如說我的同學學習 Java，是為了修過物件導向程式設計這門課，無不努力的加以學習，就怕被當XD 前次學習 Ruby 我個人認為成效非常不彰，到現在還沒摸過 RoR 程式，也只會雕蟲小技罷了。不過倒是為了修改 HoneyComing (HERE) 而勉強學了一些。

這一次又學了 Python 其實跟兩件事有關：Google App Engine 跟 BitTorrent，我就慢慢說明。

Google App Engine (GAE) 已經公開申請一段時間了，Google 提供各種資源讓你在上面開發網路應用程式，而且目前是免費的！只可惜支援的程式語言目前僅有 Python (因為 Python 之父 Guido van Rossum 在 Google 工作的關係吧)。雖然計畫未來會支援更多語言 (也許會有 Ruby, PHP, Java？) 但是在那一刻還沒到來之前，這麼爽的東西竟然因為我不會 Python 而不能痛快遊玩感到可惜。一方面前幾個月 Pixmicat! 開發討論版上面有個人做了一個 Python 版的移植 (雖然看起來是移植 futaba 祭典版)，感覺很有趣，我想該是接觸新知識的時候了，於是就去下載了 GAE 的 SDK 和安裝 Python 環境。

看了一下 GAE 還是有些限制的，SDK 提供了一個範例，我看了一下似乎提供了一些整合 Framework，但是我連基本的都不會了，要我用什麼 Framework 呢？剛好又看到 GAEO 這個專門為 GAE 撰寫的 Framework，這還是台灣人 ericsk 主導的。當然要玩這些的大前提就是先會懂 Python。

另一個竟然是 BitTorrent，有沒有搞錯？沒搞錯，BitTorrent 原本就是使用 Python 開發的 (在還沒併購 μTorrent 之前，現在的已經是用 C++)。我記得以前有一個 TorrentSpy 軟體，可以幫助使用者在新增下載之前，先查看熱烈度 (Seeder/Leecher 人數)，不然萬一早就沒人了豈不是白搭 (尤其是挖了很久以前的 torrent 檔更需要)。但是隨著時代的改變，BT 的通訊協定改變越來越大，2004 年後即停止開發的軟體早就跟不上時代，現在都已經支援多個 Tracker 查詢了，但是此軟體仍只能針對一組作查詢不太便利 (根據這篇修訂紀錄來看也是2008年才成為標準，不能怪他)，目前好像也沒看到其他什麼可以取代的軟體，不如自己寫吧。

簡單了解一下我如果要做到一樣的效果，必須要先解析 *.torrent 檔案的結構。這不難，已經有完整的 Spec Wiki 可以看。首先要面對的是 BT 最常用到的 Bencode 編碼法 (念作 Bee encode)。

---

一般字串: (n:XXXX)

範例: 10:HelloWorld。冒號前面是字串長度，後面則是字串本身

數字: (iNNNNe)

範例: i10e。使用i(integer)...e來包住

列表: (lAAABBBe)

範例: l10:HelloWorldi10ee。使用l(list)...e來包住。
以虛擬碼來說是 ["HelloWorld", 10]

字典: (dXXXAAAYYYBBBe)

範例: d10:HelloWorldi10e4:test4:truee。使用d(dictionary)...e來包住。
以虛擬碼來說是 {"HelloWorld": 10, "test": "true"}，注意數字不能做索引鍵，必須使用字串

所以像是

{"info":
　{
　　"1" : {"date": 20090204203645, "file": ["A", "B", "C"]},
　　"2" : {"date": 20090203123559, "file": ["01.jpg", "2.png", "3333.txt"]}
　}
}

這種結構也能輕易的變成Bencode:

d4:infod1:1d4:datei20090204203645e4:filel1:A1:B1:Cee1:2d4:datei20090203123559e4:filel6:01.jpg5:2.png8:3333.txteeee

藉由官方的Bencode套件我們馬上就可以省去這些繁複的動作，剩下的便是看 Spec 取出適當的資訊組合之後向 Tracker 要求目前的熱烈度如何即可。

又，Tracker得知熱烈度的方法是 GET /scrape?info_hash=XXX 的方法，info_hash是啥碗糕？其實就是 Torrent 檔案內 info 項目的 Bencode 資料經過 SHA-1 後的 20 bytes 資料。這邊利用 Python 提供的 hashlib 函式庫 sha1 方法來達成，至於要抓 info 的原始 bencode 資料也不會很難，我是直接再把解析完的 info 再 bencode 一次，不過照理說直接從檔案中抓效率可能比較好。

Tracker 回傳的格式一樣是 bencode，結構簡單多了。我們需要的正是 complete, incomplete 這兩項。downloaded 是已下載完成的人次，可作為一種熱門參考，但前面兩個值對下載比較重要。

import sys # Command line arguments<br />from bencode import * # BitTorrent Bencode/decode<br />from hashlib import sha1 # SHA1<br />from urllib import * # HTTP GET<br /><br /># 開啟命令列指定 Torrent 檔解 Bencode，如果沒有指定就顯示使用說明<br />if len(sys.argv) == 1:<br /> print "Usage: ", sys.argv[0], "file"<br /> sys.exit(2)<br /><br />data = open(sys.argv[1], "rb").read()<br />torrent = bdecode(data)<br /><br /># 計算 info_hash SHA-1 值 (自 info Bencode 計算) 並經過 urlencode 編碼以便於要求<br />info_hash = sha1(bencode(torrent['info'])).digest()<br />query = '?' + urlencode({'info_hash': info_hash})<br /><br /># 'announce-list' 是 Tracker 列表，逐一取出要求<br />for a_url in torrent['announce-list']:<br /> try:<br /> #print a_url[0].replace('announce', 'scrape') + query<br /> print 'link to', a_url[0]<br /> # urlopen 送出 HTTP GET，讀取內容後解 Bencode 碼<br /> scraped = bdecode(urlopen(a_url[0].replace('announce', 'scrape') + query).read())<br /> # 確保回傳內容是可用的 (dict 型態)<br /> if type(scraped) == dict:<br /> torrinfo = scraped['files'][info_hash]<br /> # 列印熱烈度資料<br /> print "- Seeder: %d\tLeecher: %d\tDownloaded: %d" % (torrinfo['complete'], torrinfo['incomplete'], torrinfo['downloaded'])<br /> else:<br /> print '- No data'<br /> except (IOError, SyntaxError):<br /> # HTTP Connection Error / Bdecode Error<br /> print '- No data'<br />

經過解析後的 torrent 檔案，我們需要 announce-list 列表中的 Tracker 作查詢，另外 info 需要被作成 SHA-1 hash 來和 Tracker 聯繫。剩下的便是一一向 Tracker "Scrape" 目前的下載情形 (/announce 改成 scrape 就可以了)，將 HTTP GET 的內容給解碼後，就可以抓 'complete', 'incomplete', 'downloaded' 三個有用資料。如此向每一個 Tracker 要求之後就可以得知熱烈度，藉以決定值不值得一試。

最後感謝網際網路的便利性，讓我很快地找到需要的資料：

• Python 教學文件
  中文翻譯版的教學，將我不懂的語言語法直接列出來可以看，很不錯
• BitTorrentSpecification - TheoryOrg
  Torrent 檔案解析、Bencode、scrape 呼叫法跟回傳的內容都介紹的很清楚
• [bittorrent] 从http tracker 获取peers - 倚天龍記 - CSDNBlog
  搜尋得來有關 info_hash 如何產生的說明及程式碼範例

---
02/05: 修正程式碼中有關 scrape 回傳的 Bencode 偵測問題，有的 Tracker 只回傳 i0e (0) 會導致原本的判斷錯誤，現改用判斷型態為 dict 才作處理。