Bài học và trò chơi học tập

Cấu trúc dữ liệu không cần malloc

Các container mà firmware thật dùng, mỗi byte cố định ngay khi biên dịch, gói thành một game bắn phi thuyền nhỏ trên Uno.

Cách hoạt động

Cấu trúc dữ liệu không cần malloc chạy mọi bài học trên một bàn code: một bo mạch Arduino Uno với đèn đỏ ở chân 13, đèn vàng ở chân 12, đèn xanh lá ở chân 11 và một nút nhấn ở chân 2. Mỗi bài học là một mảnh của một trò chơi: nút nhấn bắn, các đèn cho thấy cấu trúc đang làm gì, và serial monitor in ra bên trong của nó.

Mỗi bài học mở ra một sketch C chạy được. Bạn chạy nó, nhấn nút, đọc serial monitor, rồi đổi một dòng và chạy lại. Phần kiểm tra đọc đầu ra serial, nên mỗi dòng mà bài học trích dẫn đều là dòng mà bo mạch thực sự in ra.

Các bài học

  1. Ring buffer: một hàng đợi trong một mảng cố định với các chỉ số uint8_t tự chạy và một bitmask luỹ thừa của hai, "đầy" nghĩa là gì, một static_assert bắt lỗi kích thước, và các lần nhấn nút được xếp hàng đợi cho một tick của trò chơi.
  2. Pool cố định: sáu viên đạn được tạo lúc biên dịch, một danh sách rảnh xuyên qua các ô chưa dùng, alloc và release chỉ trong vài lệnh, và một khẩu súng kêu click khi pool cạn.
  3. Danh sách intrusive: các kẻ địch tự mang con trỏ next của mình, được chuyển giữa danh sách sống và danh sách chết mà không cần chép, và tháo nút bằng con trỏ tới con trỏ nên phần đầu không cần xử lý riêng.
  4. Bitset: mười sáu kẻ xâm lăng trong một uint16_t, kiểm tra và đặt bit, đếm bit theo Kernighan, và bắn con thấp nhất bằng v & (v - 1).
  5. Bảng trạng thái: các quy tắc TITLE, PLAYING, PAUSED và GAMEOVER của một trò chơi gom vào một bảng NEXT[state][event] 12 byte, các hành động khi vào trạng thái, sự kiện phát ra từ handler, và một quy tắc đổi được chỉ bằng sửa một ô.
  6. Hàng đợi ưu tiên: một binary min-heap trong một mảng 8 ô, cây không cần con trỏ, sift up và sift down, và các thời điểm uint16_t so bằng hiệu để vẫn đúng khi bị wrap.

Trùm cuối: một hàng đợi sự kiện cho một trò chơi

Bài học cuối là Mokxi Invaders. Ngắt của nút nhấn đẩy các sự kiện FIRE vào một ring, một heap bộ đếm thời gian đẩy các sự kiện MARCH và LAND vào cùng ring khi đến hạn, và loop() đưa mỗi sự kiện cho handler của trạng thái hiện tại, lấy từ một bảng hàm. Đạn lấy từ một pool gồm ba viên và đám tám kẻ xâm lăng là một bitset trong một byte: tổng cộng 43 byte hàng đợi. Bạn mở một đợt tấn công, bắn, dọn sạch, mất một mạng, và bật chế độ khó bằng một hằng số. Nút nhấn rung như nút thật, và ngắt cho thấy cách đếm một lần nhấn là một phát bắn.

Những điều bo mạch Uno làm khác

  • Chỉ có 2 KB SRAM. Một heap bị phân mảnh có thể hỏng dù còn nhiều byte rảnh, nên firmware cố định bộ nhớ ngay lúc biên dịch, nơi báo cáo bộ nhớ của bản build đếm nó.
  • Một con trỏ dài 2 byte và một int là 16 bit, nên 1 << 15 là số âm. Các sketch ghi 1u << n cho bitmask.
  • AVR không thêm padding bên trong struct, nên sizeof là tổng của các trường.
  • Chỉ chân 2 và chân 3 có ngắt ngoài. Mọi thứ mà cả ngắt và loop() cùng chạm tới đều là volatile, và loop() tắt ngắt trong khoảnh khắc nó đẩy vào ring dùng chung.
  • millis() wrap sau mỗi 49.7 ngày. So các thời điểm bằng hiệu số, không bao giờ bằng <, để vẫn chạy đúng qua cột mốc wrap.

Sau khóa học này

Toán điểm cố định và số nguyên là nửa còn lại của việc lập trình cho một chip nhỏ: phân số, co giãn và toán nhanh chỉ với số nguyên.