交換誰的禮物?

在我們剛剛舉辦完的部門聚餐中, 有個交換禮物的活動. 雖然只是價值 300 元以下的獎品, 不過真的玩起來還是挺驚險刺激的. 除了抽獎的本身, 遊戲規則也是我感興趣的, 想著想著就睡不著了. 

如果每個人的禮物都編了號, 大家都去摸彩箱抽號碼牌, 那麼有一定的機率抽中自己的禮物. 在我們這次活動中, 一共有 26 個人, 第一個人抽中自己的機率是 1/26, 愈後面抽機會愈大.

因此得把規則修改一下, 每個人抽出另外一個人, 並且得到他的禮物, 這個規則幾乎可以保證 “不會抽到自己的禮物". 因為自己的那張籤已經被上一個人抽出來了.

第一個要考慮的狀況是: 第一張籤是主持人抽的, 而我們不能保證他/她不會抽到自己, 這個機率同樣有 1/26. 假設主持人沒有抽到自己, 又或者任何人抽到主持人的話, 應該直接予以無視, 他/她可以再抽一個號碼 – 獲得禮物、繼續遊戲. 並且我們規定最後一張被抽出的人 (如 Daniel) 要拿主持人 (如 Alice) 的禮物. 這樣似乎就不會有問題, 下面的流程圖是 4 個人的例子. 

如果沒有強迫最後一個人拿主持人 Alice 的禮物, 那麼只有很低的機率, 直到最後一個人才抽到主持人 Alice (如下圖). 基本上, 如此完美的經典畫面可說是人間少有. 

更合理的狀況是, 早早就有某人把 Alice 抽出來了, 並且此籤有效 – 他/她獲得主持人的禮物. 那麼這些人將成為一個中籤者集團, 讓另一些人變成未中籤者集團. 舉四個人的例子來說, 當 Cash 抽到 Alice, Daniel 和他的禮物就可憐地落單了 – 他只能選自己的禮物. 很可能未中籤者集團並不只一個人, 所以中籤者集團這個問題可以多次復發. 此時, 我們還得重新幫他們起個頭, 也就是製造出第二、第三個 “主持人". 

好! 我想我可以解決主持人例外的問題了. 或許這不是最佳的解決方案. 不過我們有更棘手的問題要想. 

這次的遊戲當中, 除了上述的正常卡片之外, 還有兩種特殊卡. 包括可以指定和某人交換禮物的 “搶奪卡", 和只能和某一家交換禮物的 “交換卡". 如果抽到特殊卡, 就必須再抽到一張號碼卡, 才能找出下一棒. 此時得到的禮物因為 “搶奪卡" 的關係將變成別人的. 為了讓參加遊戲的人懊悔不已, 我們應該讓他/她先選擇搶誰, 然後再抽下一張號碼卡. 當然, 同一個人連續抽到特殊卡這件事應該被禁止掉, 以無效重抽來處理. 

搶奪卡要不要考慮哪些對象不能搶呢? 如果我搶已經中籤的人, 看來沒問題. 如果我搶未中籤的人, 對方可能又抽到 “搶奪卡", 或是 “交換卡", 那麼就有指令順序逆轉的問題. 因為對方如果不完成他/她的動作, 我的動作就無法完成. 況且, 我行搶的對方要是遲遲不中籤, 那個等待被搶的人, 甚至搶人的人慢慢就會淡定掉了. 為了讓遊戲維持緊張刺激, 規定只能搶已經中籤的人比較明快.

再來是交換卡的狀況, 如果規定只能和下一家交換, Alice 抽到交換卡後, 又抽到 Barry, 於是他要拿 Barry 的禮物和 Barry 抽到的 Cash 的禮物交換. 雖然 Alice 得到 Cash 的禮物, 而 Barry 竟然會得到自己的禮物. 於是我們只好改成 “交換卡是和下下一家交換". Alice 拿著 Barry 的禮物, 和 Cash 抽到的 Daniel 的禮物交換. 最後 Alice 得到 Daniel 的禮物, Barry 得到 Cash 的禮物, 而 Cash 得到 Barry 的禮物. 

考慮遊戲的 boundary, 我們回去看第一張圖. 倒數第二個人 Cash 若是抽到交換卡, 他的下下一家可以視為 Alice, 因為 Daniel 拿了 Alice 的禮物. 對於這樣一個健康的迴圈, 似乎一切都合理.

那麼可以鼓勵往上遊換嗎? 往上一家換的話, 就會直接拿到自己的禮物, 所以我們只能考慮換上上一家. 可是對第一、二個遊戲者來說, 上上一家本來就不存在. 我們又要發明一些規則來處理例外, 不如就讓它和下下一家換吧!

萬一抽到交換卡的人, 他/她的下一家或是下下一家也抽到特殊卡呢? 我們應該等先抽到特殊卡的人完成指令 (first in first out – FIFO)? 還是後進先出 (last in first out – LIFO) 比較合理呢? 讓我們繼續看下去..., 呃, 我想 就直接選  LIFO 吧!  後發生的先做完, 它的輸出才能當作先發生者的輸入!

在此趕快做個小小的結論, 讓我可以順利睡著吧! 要是漏洞太多, 我可能會半夜驚醒吧…

1. 主持人抽出第一個人, 並獲得他/她的禮物.

2. 任何人抽到主持人一律無視, 此籤無效.

3. 最後一個被抽到的人拿主持人的禮物.

4. 搶奪卡建議搶已經抽中禮物的人.

5. 交換卡和下下一家交換, 以迴圈的方式考慮最後一個人的下一家就是主持人.

6. 同一個人連續抽到特殊卡無效.

7. 如果特殊卡事件連續發生, 以 “後發生的先完成" 處理.

8. 如有未盡事宜, 由主持人解釋之.

Android 的人對 GPU 的說法

由於很多人都認為 Android 3.0 以前, Android 只用軟體畫圖, 所以 Android  的人跑出來澄清. 雖然這篇文章已經有點久了, 正好可以呼應我上一篇的貼文. 有興趣的人可以去看原版 Dianne Hackborn 的 Google+, . 我在這邊只摘要幾個重點.

1. Android 從 1.0 版就使用硬體加速視窗的的疊加 (all window compositing to the display has been done with hardware), 當然有的時候會用軟體. 下圖共包含四層視窗 (windows): Wall Paper, Launcher, Menu, Status Bar. 如果使用者操作 menu, 只有 menu 會用軟體重畫. 而疊加 (overlay) 的部分和整張畫面滑動的效果則是用硬體做.

2. Android 3.0 開始全部由硬體加速, 4.0 也是一樣. 只不過 Android 3.0 會檢查 App 在 manifest 裡面的 “android:handwareAccelerated="true" 這行 , 以決定是否用硬體加速. 而 Android 4.0 預設就是全部用硬體加速. 這麼一來, 原本只需要局部 UI 更新的狀況也不再交給比較有效率的軟體來執行了; 如此一來導致了一些副作用.  

3. 其他用硬體加速的缺點包括浪費記憶體, Imagination Tech 的繪圖驅動程式基本上要吃掉 8MB RAM. 剩餘的 RAM 變少了, 其它的背景程式就會變慢. 因此, status bar 其實不需要用 OpenGL (GPU) 來畫. Android 4.0 就把這部分單獨用軟體處理.

4. 蘋果的 IOS 怎麼做呢? 以瀏覽器為例, IOS 把網頁的畫面以 display list 的方式來畫, 因此沒有什麼更新區域的概念, 整個頁面都要重畫. 這麼做的優點是捲動或試放大縮小的時候不會看見破圖 (artifact) – 假如畫面是分成幾個區塊 (title) 來分別渲染的話, 就可以會有 artifact. 後者恰好就是 Android 的做法, 它比較能夠對抗複雜的頁面而不致於變慢, 因此光是用軟體就可以在 Nexus S2 畫出每秒 60 楨 (60 fps). 作者說他相信 IOS 也是用軟體畫的.

5. 為了解決 GPU 不夠力的問題, Android 還是有用 HW overlay, 而且把底圖 (backgound) 放的比螢幕還大. 這樣一來, 使用者捲動畫面的時候, 底圖就不需要重畫, 只是改個座標 (offset) 而已.

6. 當我們用 CPU 畫 UI 的時候, 多核心並沒有幫助. 因為幫一個 app 繪製 UI 的時候, 沒辦法做平行處理. 這就是為什麼 Android 要用 GPU 加速. 在去年年底 Galaxy S2 出來的時候, ARM 的 CPU (大約是 CA9 1GHz) 還不能畫到 720×1280 的 UI (60 fps), 因此更細緻的解析度都必須仰賴 GPU 來畫.

以下再補充更多的觀點:

7.  Android 官網的說法: GPU 擅長放大縮小, 旋轉,  平移, 但是不擅長畫直線和曲線. 所以要多用其長, 少用其短.

8. Qualcomm 說 Android 在他們的 Snapdragon 可以用 GPU 做 composition (也就是不用 HW overlay):

如果 graphic UI (user interface) 和 video 沒有同步, 那麼一般人腦海中的狀況是這樣:

 Qualcomm 說: video 可以當作圖形處理中的紋理 (texture), 所以簡單多了. 

HW Overlay 小檔案

看到這個題目在 wiki 只有英文和韓文, 忍不住想寫一個中文的精簡版. 不過寫著寫著就偏離主題, 變成了 Android 為何不全面支持 HW Overlay?

我們在 Windows 螢幕上看到的畫面, 基本上是由視窗疊加而成的, 前景擋住後景, 就成了我們看到的模樣. 在其他有視訊輸出的產品中, 同樣會有物件互相遮蔽的現象, 例如: 字幕浮現在電影上, 這樣就是兩個個物件. 如果再加上進度條 (progress bar), 就變成 3 個物件. 當繪圖系統需要依序畫出這三個物件時, 可以用軟體去檢查前後順序, 只把需要的部份畫出. 在 Android 系統中, Surface Flinger 就在做這件事 [註1].

既然有軟體的解法, 硬體解法會不會更快更有效率呢？是的, HW overlay 就是這個硬體的解法. 當每個物件都畫在自己的記憶體, 最後再依據每個物件的先後順序和透明度 (alpha blending) 一次疊加, 那麼每個物件就不用等來等去, 只要各畫各的就好. 如此一來, 雖然浪費了好幾塊記憶體, 控制卻變得很簡單. 特別是物件的更新速率差異很大時, 互等會導致大量浪費頻寬 – 例如電影 (30~60Hz) 與字幕 (大約 0.2~0.5 Hz).

Surface Flinger HW Overlay

上面這張圖有個小問題, 就是把 SurfaceFlinger 和 Overlay 畫成兩個獨立的模組. 實際上, 在 Android 中, HW Overlay 和 Surface Flinger 關係密切. HW Overlay 算是 SurfaceFlinger 的一個特例 [註 2]. 請參考下圖.

現在的 IC 幾乎都有 HW overlay 的能力, 應該沒甚麼好討論的, 可惜故事還沒有完. 大家如果把玩手上的 Android 手機或是平板, 可能會在設定裡面看到 “停用硬體重疊圖層" 這個選項. 既然 HW overlay 看起來比較好, 幹嘛把它停用呢？ 每一個 OpenGL 的 process 都需要 2~8MB 的 RAM, 浪費記憶體就不用說了. GPU 還要挺高檔才行 [註 3].

每秒可以畫 1000 M pixel/second 的 200MHz SGX544, 在 1920×1080@60FPS (frame per second) 的輸出螢幕上, 能在每個 pixel render 8.0375 次. 若是換成了 SGX531就只能 render 4 次 [註 4]. 這  4 次如果用來畫一層背景, 一層電影. 一層進度條和 OSD (on screen display), 一層字幕, 就已經達到 GPU 的硬體極限. 此時只是做到 HW overlay 的水準而已, 但什麼 3D 動畫效果都畫不出來了.

以上都是說 Android 的壞話, 但 Google 卻可以藉著不支援 HW Overlay 來統一硬體的差異, copybit 不就在 Android 4.0 上被拔掉了嗎? 若是放任每一家廠商製作的 HW Overlay 都不相同, 當然就限制了 APP (跨平台的) 的互通性. 再者, GPU 只要聰明地用, 不要常常 redraw 沒用的畫面, 效率還是不會太差 [註 3]. 按照 Android 的官方說法, 全部的畫面都能進入 GPU 的話, 使用者將可以得到更多樂趣! 至於 GPU 的計算能力….當然必須夠, 這不是 Android 的責任範圍, 它只是個做軟體的. [註5]

Media effects for transforming images and video

A set of high-performance transformation filters let developers apply rich effects to any image passed as an OpenGL ES 2.0 texture. Developers can adjust color levels and brightness, change backgrounds, sharpen, crop, rotate, add lens distortion, and apply other effects. The transformations are processed by the GPU, so they are fast enough for processing image frames loaded from disk, camera, or video stream.

[註]

1.  Android Display (surfaceflinger and Overlay)

2. Android 显示系统

3. The truth about hardware acceleration on Android

4. PowerVR

5. Ice Cream Sandwich

RFC 2119 小整理

RFC (Request For Comments) 是指網路上標準的討論草案. 每個編號都代表一個獨立的文件, 像是 RFC3261 專門講 SIP (Session Initiation Protocol) 的規範等等. 發行 RFC 的單位是 IETF (Internet Engineering Task Force). 由於 IETF 只是一個鬆散的組織, 背後由 The Internet Society 提供支援. 因此 RFC 文件的 copyright 屬於 The Internet Society 所擁有.

相較於每份標準要賣百塊瑞士法郎的 ISO/IEEE, The Internet Society 的文件都可以免費地由網站上取得. 其中 RFC2119 很特別地不是講技術, 而是講規格中幾個常用詞的定義. SHALL 可以例外嗎? MAY 到底是有規定還是沒規定?

如果我們以光譜來看, 最左邊是一定要, 最右邊是一定不要. MUST 和 SHALL 都是同級的, 表示最強烈的意思. 退而求其次就是 SHOULD, 它允許有例外. MAY 的話, 就有點不置可否了. 很有趣地, RFC 2119 這本規格就只講了這些.

絕對肯定 —————————————————————————————絕對否定
MUST

REQUIRED

SHALL

 SHOULD

RECOMMENDED

 MAY

OPTIONAL

 SHOULD NOT

NOT RECOMMENDED

 MUST NOT

SHALL NOT
絕對要 一般要, 可以有例外 可以做, 也可以不做 一般不可以, 可以例外 絕對不可以

不能備份 Windows 的問題

先前試了幾次, 好像都沒辦法按照 Windows  提供的步驟完成備份. 啟用光碟和憑證的備份倒是都順便生出好幾份了. 本來我猜測 Windows 有 2TB 的大小限制, 否則為何每次失敗的訊息都一樣. 所以上次重灌時, 我還特地把 Windows 灌到小小的 SSD 上面. 結果還是不行! 因為那顆 SSD 太小了, 放不下的 program files 還是得安裝在大顆硬碟那邊, 大硬碟的問題依然存在.

前陣子不死心地又找了一下錯誤碼, 才知道中文版的解答很少, 但是有英文版的. Error 0X807800B4 not able to backup files in Windows 7. 和 Backup fails in Windows 7 when trying to create a system image.

前者不能備份是因為磁碟有問題. 按照此連結上面的說明, 首先要叫出 “系統檔案檢查員". 使用 「 系統檔案檢查員 」 工具 (SFC.exe) 來判斷哪些檔案造成這個問題, 接著以正確的檔案取代壞掉的檔案。

  1. 在命令提示字元中，輸入下列命令，並按 ENTER：
    sfc /scannow
  2.  如果 sfc 發現問題, 參考上面的連結可以解決此問題.

但是如果完全沒有發現問題呢? 大概就是第二個連結所講的: Microsoft 的限制. Windows 最多只認得 2TB 的虛擬硬碟 (virtual hard disk), 而其實際容量只有 2097152MB – 2MB – 8192MB = 2088958 MB, 這就是上面錯誤訊息視窗上所寫的數字. 把任何大於 2088958MB 的東西拿來備份都會失敗.

當我在設定備份內容時, 如果勾選了製作系統映像 (system image), Windows 就會認為它要還原整個硬碟. 即便是沒有勾選所有的目錄, 只要勾到左下角那個紅圈圈的 box 就算.

當然, 把映像存起來, 未來才可以完整地還原電腦. 若是這裡不圈選, 就等於只備份了檔案. 想要完整地備份大於 2TB 的系統, 唯一的方法是把大硬碟切小. 內容參考這篇 Shrink a Basic Volume. 基本上它講到如何用 Windows 介面或是命令列去修改 partition. 不過用第三方的免費軟體或許還比較可靠.

總之, 2TB 的限制的確存在. 想要做系統映像檔, 必須先把開機硬碟切到 2088958 MB 以下.