WebM 初探

最近研究 WebM，尤其是其 encoder 的部份。以下說明我研究的結果：

Firefox 和 Google Chrome 都使用 WebM project 的 libvpx 函式庫來處理 WebM。WebM 包括了 video 和 audio 兩個部份，video 部份使用 VP8 video codec，audio 部份使用 Vorbis audio codec。這兩個部份被放在 container 內。Container 的設計參考了 Matroska container。

libvpx 內的 simple encoder 範例讀取了 YV12 檔案，編碼成 IVF 檔案。

YV12 是 YUV 的一種。YUV 是編譯 true color 顏色空間的種類。YUV 發明於黑白電視和彩色電視的過渡期，為了訊號能和黑白電視相容，不採用 RGB 的編碼，而採用 YUV，Y 代表明亮度，也就是給黑白電視的訊號。UV 則是色度、濃度。

IVF (Indeo Video Format) 是 Intel 開發的格式，在 1990 年代很流行，後被 MPEG 標準打敗。IVF  在 WebM 計劃中被用來傳送 raw VP8 data。

C 語言上的 Forth

三十年以上功力，我也算是 Forth 的老手了。開發了一套自己的 Forth，雖然不用 C，但它的確是建立高階語言上的。

很多人反對 C 語言上的 Forth。我想依據我的經驗，說明一下 C 語言上的 Forth 的好處，讓大家思考一下：

  1. 當您的大型專案是以 C 語言寫成，當這專案編譯成執行檔後您要如何測試這個專案的各個小零件？

反對 C 語言上的 Forth 的人會選擇 ruby, python, javascript, lua, scheme 或其他能和 C 語言連結的 scripting languages 來和這專案連結，以 scripting language 和執行檔內的副程式互動，進行測試。

贊成 C 語言上的 Forth 的人會自建 Forth，或是用別人建好的 C 語言上的 Forth，作為這專案的互動式測試工具。

 2. 如果您有兩個執行檔，他們必須溝通並且呼叫對方的某些函式。一個執行檔以 Java 寫成，另一個是以 C 寫成。請問您要如何處理這樣的問題？

反對 C 語言上的 Forth 的人可能會在 C 語言的專案中內建 lua，因為聽說 lua 是最適合內建在 C 程式中的 scripting language 了。但是 Lua 不能內建在 Java 中，所以只好在 Java 的專案內選擇 JRuby。

贊成 C 語言上的 Forth 的人會在 Java 上建一套 Forth，畢竟那是很容易的事。更偷懶的會使用別人在 Java 上建好的 Forth，配合他在 C 語言那端的 Forth。然後，用同一種語言來解決問題。

有句話，一招半式闖江湖，會上 Forth 的一招半式，可以闖闖 C 語言的江湖、Java 語言的江湖，還有 MCU 江湖。

我希望用我的經驗讓反對 C 語言上的 Forth 的 Forth 愛好者，能瞭解為什麼會有 C 語言上的 Forth。C 語言上的 Forth 不會因為別人反對而消失，因為它們以簡單的方法解決了現實中程式開發的問題，只有真正面對過這些問題的人才瞭解到它的價值。

J1 Forth CPU 研究之四：資料堆疊和返回堆疊

這是一系列文章中的第四篇，這系列的文章是要解讀 J1 CPU 的設計以及在其上的 Forth 語言的使用法。

這篇談的是 j1 CPU 的 Verilog 程式中和資料堆疊 (Data Stack) 和返回堆疊 (Return Stack) 有關的部份，請見以下檔案：

src/hardware/verilog/j1.v

一般的 CPU 在設計上只有一個堆疊，這個堆疊在副程式呼叫時有三個功能：

1. 存放副程式的的參數 (parameters)。
2. 存放副程式的返回位址。
3. 存放區域變數 (local variables)。

當副程式有回傳值時，這值會被放在一個特定的暫存器中，大多數的程式語言的副程式最多只有一個回傳值，理由在此。

Forth CPU 和的一般 CPU 在設計上有個不同之處： Forth CPU 有兩個堆疊，回傳的資料不放暫存器，而是放在堆疊上。因此可以回傳多值。這兩個堆疊的名稱及功能是：

1. 資料堆疊 (Data Stack)：存放副程式的的參數 (parameters) 以及副程式產生的資料。
2. 返回堆疊 (Return Stack)： 存放副程式的返回位址。有時會在副程式計算過程中用來暫時保存資料堆疊上的資料。

某些 Forth 會使用第三個堆疊處理區域變數，但是許多 Forth 語言的愛好者摒棄區域變數這樣的概念。J1 Forth CPU 在設計上只有兩個堆疊。

資料堆疊最上面的資料常被稱為 T (Top)，在其下的資料常被稱為 N (Next)。由於 ALU 的計算大量使用 T 和 N，許多 Forth CPU 或是 Forth virtual machine 的設計中，T 會被設計成暫存器，以加快 ALU 的計算速度。當要使用 T 時，直接讀取對應的暫存器，當要使用 N 時，讀取資料堆疊的堆疊指標指向的堆疊頂端。這使得 T 和 N 可以同時被讀取。在這樣的設計下，雖然 T 是寫 Forth 程式時的資料堆疊頂，但是以 Verilog 實作時，N 才是實作的資料堆疊的疊頂。因此要實現 Forth 程式中將數值資料推上資料堆疊的行為時，除了寫資料到 T 中，還必須把 T 中的資料推上堆疊(也就是機器碼編譯中的 T->N)。因為 Verilog 平行處理的特性，這兩個行為可以同時發生。

要注意，和資料堆疊不同，返回堆疊最上面的資料並未放在一個獨立的暫存器中，這使得將數值推上資料堆疊與推上返回堆疊的程式略有不同。以下是 Verilog 的宣告：

  reg [4:0] dsp;  // 資料堆疊指標，指向 N
  reg [4:0] _dsp;  // 下一時刻的資料堆疊指標
  reg [15:0] st0;  // T，存放 Forth 資料堆疊最頂端資料的暫存器
  reg [15:0] _st0; // 下一時刻的 T
  wire [15:0] st1; // N，Forth 資料堆疊中在 T 之下的資料，Verilog 中資料堆疊的疊頂。請參考以下程式中的 assign 敍述。
  wire _dstkW;     // D stack write

  reg [4:0] rsp; // 返回堆疊指標
  reg [4:0] _rsp; // 下一時刻的返回堆疊指標
  wire [15:0] rst0; // 返回堆疊的疊頂，請見以下程式中的 assign 敍述。
  reg _rstkW;     // R stack write
  reg [15:0] _rstkD; // 要寫入返回堆疊的資料

  reg [15:0] dstack[0:31]; // 資料堆疊，深度為 32，加上 st0，深度為 33
  reg [15:0] rstack[0:31]; // 返回堆疊，深度為 32

以下程式處理寫入堆疊的動作。在 sys_clk_i 的上升緣，如果資料堆疊寫入訊號 _dstkW 為真，則執行 T->N 的行為，把 st0 的資料寫入 dstack[_dsp]。_dsp 為下一時刻的資料堆疊指標。所以是未來的 N 的位置。同樣的，如果返回堆疊寫入訊號 _rstkW 為真，則把 _rstkD 的內容寫到返回堆疊中 _rsp 指到的位置。_rsp 為下一時刻的返回堆疊指標。
  always @(posedge sys_clk_i)  begin
    if (_dstkW)
      dstack[_dsp] = st0;
    if (_rstkW)
      rstack[_rsp] = _rstkD;
  end
  assign st1 = dstack[dsp];
  assign rst0 = rstack[rsp];

以下程式決定寫入訊號 _dstkW、_rstkW，及下一刻堆疊指標 _dsp, _rsp 的值。請參考機器碼的編碼：

其中，要寫入資料堆疊的時機(_diskW為真)是當機器碼最高位元為 1，也就是 literal 時，或是機器碼為 ALU，且第 7 位元為 1 (也就是 T->N) 時。此時都要做 T->N 的動作。

  assign _dstkW = is_lit | (is_alu & insn[7]);

以下資料決定執行 ALU 後資料堆疊和返回堆疊指標增減的量。
  wire [1:0] dd = insn[1:0];  // D stack delta
  wire [1:0] rd = insn[3:2];  // R stack delta

  always @*
  begin
    if (is_lit) begin                       // 如果是 literal，數值資料
      _dsp = dsp + 1;                  // 此時因要推資料上資料堆疊，資料堆疊指標加 1
      _rsp = rsp;                          // 返回堆疊指標不變。
      _rstkW = 0;                         // 不寫入返回堆疊
      _rstkD = _pc;                      // 因為不寫入，這行其實沒有作用。
    end else if (is_alu) begin        // 如果是 ALU 運算
      _dsp = dsp + {dd[1], dd[1], dd[1], dd};   // 依 dd 增減資料堆疊指標
      _rsp = rsp + {rd[1], rd[1], rd[1], rd};        // 依 rd 增減返回堆疊指標
      _rstkW = insn[6];                                  // 由 T->R 欄位決定要不要寫入返回堆疊
      _rstkD = st0;                                        // 如果要寫入，被寫入的資料是 T
    end else begin                      // 如果是 jump/call
      // predicated jump is like DROP
      if (insn[15:13] == 3'b001) begin    // 如果是 conditional jump，拋棄堆疊上用來做判斷的資料，因此堆疊指標減一。
        _dsp = dsp - 1;
      end else begin                              // 如果只是單純的 jump，維持原來的堆疊指標。
        _dsp = dsp;
      end
      if (insn[15:13] == 3'b010) begin    // 如果是 call，呼叫副程式
        _rsp = rsp + 1;                            // 此時把 program counter + 1 堆上返回堆疊。
        _rstkW = 1;                                 // 因此要寫入返回堆疊。
        _rstkD = {pc_plus_1[14:0], 1'b0}; // 實際上推入的值必須乘以二，轉成 byte 位址。
                                                         // 轉成 byte 位址的理由在未來討論 Xilinx 的內部 RAM 時說明。
      end else begin                    // 當以上皆非
        _rsp = rsp;                        // 不改變返回堆疊
        _rstkW = 0;
        _rstkD = _pc;
      end
    end
  end

以上總共 60 行，加上第三篇的 30 行，我們已經看懂了 j1.v 的 90/200，接近一半的程式了。

J1 Forth CPU 研究之三：系統重設和 program counter

這是一系列文章中的第三篇，這系列的文章是要解讀 J1 CPU 的設計以及在其上的 Forth 語言的使用法。

這篇要談的是 j1 CPU 的 Verilog 程式中和系統重設以及 program counter 有關的部份，請見以下檔案：

src/hardware/verilog/j1.v

在 j1.v 中，系統重設的訊號是 sys_rst_i，因此搜尋所有 sys_rst_i 出現的地方。
以下是其中一處：

  always @(posedge sys_clk_i)
  begin
    if (sys_rst_i) begin
      pc <= 0;
      dsp <= 0;
      st0 <= 0;
      rsp <= 0;
    end else begin
      dsp <= _dsp;
      pc <= _pc;
      st0 <= _st0;
      rsp <= _rsp;
    end
  end

說明如下：

1. sys_clk_i：系統的 clock 訊號
2. always @(poseedge sys_clk_i)：在系統的 clock 訊號的上升邊緣總是要執行底下 begin 至 end 的事。
3. sys_rst_i：系統的重設訊號
4. pc：program counter
5. dsp： 資料堆疊指標
6. st0： 資料堆疊頂端的暫存器
7. rsp：返回堆疊的指標

因此，這段程式是說，在系統的 clock 訊號的上升邊緣如果重設訊號為真，就把 pc, dsp, st0, rsp 都設為零。否則， pc, dsp, st0 和 rsp 會被設為 _pc, _dsp, _st0, _rsp。其中 _pc, _dsp, _st0, _rsp 這幾個值會在別處計算。

因此我們知道，這個 CPU 一被重設，就會從位址零開始執行。而且，所有的堆疊都被清空。

以下是另一處：

  always @*
  begin
    if (sys_rst_i)
      _pc = pc;
    else
      if ((insn[15:13] == 3'b000) |
          ((insn[15:13] == 3'b001) & (|st0 == 0)) |
          (insn[15:13] == 3'b010))
        _pc = insn[12:0];
      else if (is_alu & insn[12])
        _pc = rst0[15:1];                          // 注意推上返回堆疊的副程式返回位址是 8 bit 的 byte 位址，而 program counter 使用的是 16 bit 的 word 位址，因此用 rts0[15:1]，不使用 rts0[15:0]。
      else
        _pc = pc_plus_1;
  end

為了瞭解以上程式必須瞭解 J1 機器碼的編碼，請見下圖或是 J1: a small Forth CPU Core for FPGAs。

程式說明如下：

1. always @*：總是要做以下 begin 至 end 間的事。
2. insn：放的是目前要執行的機器碼。
3. 如果系統重設訊號 sys_rst_i 為真，則 _pc = pc, 不做任何改變。
4. 如果重設訊號為假，則檢查目前要執行的機器碼，
1. 如果第 13 到第 15 位元為二進制的 000, 或是 001 或是 010，分別是 j1 CPU  的 jump, conditaional jump 及 call 指令，則 program counter 被設為機器碼中 0 到 12 位元的值。
2. 如果機器碼是 alu (13到15位元為二進制的 011)，而且 12 位元為 1，則這是一個把返回堆疊頂的資料放到 program counter 的指令，就是副程式返回，就是 Forth 的 NEXT 指令啦。
3. 如果以上皆非，那麼 program counter 等於 program counter 加一，處理下一個機器碼。

程式中的 3'b000 是 Verilog 的語法，一個 3bit 的二進制數字 000。3'b001 及 3'b010 依此類推。


程式中 |st0 == 0 的 | 會把 st0 中的 bits 都 or 起來，因此，這句判斷堆疊最上面的資料是否為零。這被用在 conditional jump：如果堆疊最上面的資料為零就要 jump。


由於 jump, conditional jump 及 call 後的位址只有 0 到 12 共 13 個位元，我們知道 j1 的程式最大只有 8K。不是 8K bytes，因為 J1 是 16 位元的 CPU，每個機器碼長度為 16 bits。

這樣子，我們就瞭解了 j1 在系統重設時的行為，以及它是如何實現 jump, conditional jump, call 及 ret (NEXT) 的。 由於 j1.v 只有 200 行程式，我們已經看懂了它的 30/200 之一的程式。

不過，在看上面的程式時要注意 Verilog 的 <= 和 = 的差異，這部份比較隱晦，請閱讀相關書籍。

J1 Forth CPU 研究之二：如何以 Xilinx ISE 來 Synthesize J1 CPU

這是我有關 J1 Forth CPU 的系列文章中的第二篇，雖然，這篇其實是寫於第一篇之前，已經在符式協會論壇發表過。

以下是當初發表的內容：

因未來工作需要，決定建立 J1 Forth CPU 和 Ethernet 結合的技術。第一個步驟，就是將 WGE100 Camera 的 Firmware 以 Xilinx 的 SP601 板跑起來。

但是在改為 SP601 前，由於 WGE100 Camera 使用的是 Spartan 3E，我先以 Spartan 3E 進行 FPGA 的 Synthesis。以下說明我的經驗：

首先，以 Subversion 取得位於 https://github.com/chengchangwu/wge100_driver/blob/hydro-devel/wge100_camera_firmware 的程式。

之後，以 Xilinx ISE 開了一個新的 project，選擇 Family Spartan3E，Device XC3S500E，Package CP132，這應該就是原來的作者使用的 Device 和 Package。

然後把以下的檔案加進來：

verilog 目錄下的：

   ck_div.v  j1.v  reset_gen.v  topj1.v  trig_watchdog.v  uart.v  watchdog.v

verilog/coregen 目錄下的：

   pixfifo.xco

lib/mac 目錄下的：

   crc_chk.v  gmux.v   mac.v       reconciliation.v  rx_raw.v     tx_engine_raw.v

   crc_gen.v  greg.v   mii_mgmt.v  rx_engine_raw.v   rx_usr_if.v

   rx_pkt_fifo.v  tx_raw.v

lib/mac/xilinx/spartan3e 目錄下的：

   device_ODDR.v

lib/mac/xilinx/spartan3e/coregen 目錄下的：

   rx_pkt_fifo_sync.xco

   rxfifo.xco

   txfifo.xco

synth 目錄下的：   wge100_RevC_Camera.ucf

我並未加入所有的 .v 檔，只是先加入 topj1.v ，然後再依據 Design Hierarchy 顯示缺少的元件來加入需要的 .v 檔。當有 .v 和 .xco 檔時我選擇 .xco 檔。最後必須加入 wge100_RevC_Camera.ucf 以解決一個 Error。

如此，就可以從 Synthesis 一直做到 Design implementation 得到 bitstream。

在這之後，我想我必須依據 SP601 的硬體設計來修改 routing，以便讓 Ethernet 真的能跑起來。這樣，就可以透過 Ethernet 和 J1 CPU 上的 Forth 程式溝通了。

J1 Forth CPU 研究之一：Camera Firmware 的程式結構

這是一系列文章中的第一篇，這系列的文章是要解讀 J1 CPU 的設計以及在其上的 Forth 語言的使用法。

在這一篇文章中提及的 J1 被應用於 Camera，其 Forth 程式可以在以下目錄中找到：

https://github.com/chengchangwu/wge100_driver/blob/hydro-devel/wge100_camera_firmware/src/firmware

這個 Forth 以 Gforth 為 Host，J1 Forth CPU 為 Target。

首先，看看這個目錄裡最重要的幾個檔案：

1. main.fs：這是主程式
2. crossj1.fs：這是 J1 的 Cross compiler
3. basewords.fs：在這兒，以 j1 的 assembler 來定義了基本的 Forth 指令。

對許多初學 Forth 的人來說，Cross compiler 無疑是最神秘玄奇之物了。因此讓我們先看看它。只有 512 行，真的很短，在裡面最重要的三個命令是：

1. meta：執行 meta 後就可以開始定義 J1 的 Cross compiler (或稱為 metacompiler) 了。
2. target：執行 target 後，之後定義的指令或是資料結構最後都會被放到 target 裡，也就是 j1 16k 的 RAM 裡。
3. j1asm：執行 j1asm 後可以開始定義 j1 的 assembler。

再來，看看 main.fs 吧，在這個檔案中我們可以看出 cross compiler 是怎麼被使用的。首先，include crossj1.fs 載入了 metacompiler，再來執行 meta，定義了一些常數以及 basewords，最後執行 target，include hwwge.fs 及 boot.fs，然後開始定義 Camera 的應用程式。其中，hwwge.fs 以及位於 boot.fs 之後的程式都只是針對 camera 這個應用，在此就不詳提了，只說明 boot.fs 和在檔案尾端的 0jump。

1. boot.fs：boot loader，它使用 spi 從 flash 載入整個 Forth 系統。它佔據了記憶體 3e00H 以後的空間，從檔案尾端的 h# 3e00 org 得知它從 3e00H 處開始執行。目前我還不清楚 boot loader 又是怎麼被誰放到 RAM 的 3e00H 後的空間中。這等待以後更瞭解時再向大家報告。
2. 0jump：在 main.fs 尾端的 0jump 是主程式冷起動的位置。從之前的 0 org 可以知道它的 RAM 位址 是 0。由於有一行 h# 3e00 ubranch 被放在註解中，而 3e00H 是 boot loader 的開始位置，因此我們知道 boot loader 並沒有真的被使用。緊接在那行的是 main ubranch，所以，程式一開始會跳到 main，也就是這個 camera 的應用程式。

學習 Verilog HDL

因為工作需要使用 Xilinx FPGA，我開始學習 FPGA 以及 Verilog。
以下是我的學習過程。

我買了兩本原文書，但幫助不大。目前只讓我知道有 WebPACK 這玩意。

[2011/10/08修正：在開始閱讀我要研究的 j1 Forth CPU 後，其中的一本，Digital Dsign and Verilog HDL Fundamentals 開始有幫助，我覺得這一本寫得很清楚。不過，它缺少了 Verilog 2001 的內容，如 generate/genvar 等。對 generate/genvar 等的說明可以參考 "The IEEE Verilog 1364-2001 Standard, What's New, and Why You Need It" 一文。
]

下載 WebPACK。

閱讀 Xilinx ISE In-Depth Tutorial：
http://www.xilinx.com/support/documentation/sw_manuals/xilinx13_1/ise_tutorial_ug695.pdf

至於 Verilog，弟弟傳了 OVIVerilog HDL LRM Version 1.0 做為參考手冊。

此外，以下連結提供了許多資訊：http://www.asic-world.com/verilog/verilinks.html

以下連結中的 on-line reference guides 也很值得參考： http://www.sutherland-hdl.com/reference-guides.php 。