GCD tuần tự (Euclid bằng phép trừ): đầu vào 0 làm treo mạch

Ước chung lớn nhất là câu phỏng vấn "viết một khối tuần tự có giao tiếp start/done" kinh điển: thuật toán thì ai cũng biết, nhưng phần điều khiển (khi nào nhận lệnh, khi nào dừng, giữ kết quả thế nào) mới là thứ được chấm.

module gcd8 (
  input  logic       clk,
  input  logic       rst_n,    // reset bất đồng bộ, tích cực mức thấp
  input  logic       start,
  input  logic [7:0] a,
  input  logic [7:0] b,
  output logic       busy,
  output logic       done,
  output logic [7:0] g
);

Giao tiếp:

1. Khi busy = 0 và start = 1 tại một cạnh lên, mạch chốt a, b và bật busy ngay sau cạnh đó. Sau cạnh đó a, b có thể đổi tuỳ ý.
2. start đến lúc busy = 1 bị bỏ qua.
3. Khi tính xong: trong đúng một nhịp, done = 1, busy = 0 và g = gcd(a, b).
4. g giữ kết quả gần nhất cho đến khi có kết quả mới, kể cả trong lúc đang tính lệnh sau. Sau reset g = 0.
5. Quy ước: gcd(x, 0) = gcd(0, x) = x, và gcd(0, 0) = 0.
6. Mỗi lệnh phải xong trong 400 nhịp.

Ví dụ: gcd(12, 18) = 6, gcd(17, 5) = 1, gcd(0, 9) = 9.