- SectorC, được viết bằng hợp ngữ x86-16, là một trình biên dịch C siêu nhỏ có thể nằm gọn trong boot sector (512 byte) của máy x86, và hỗ trợ một tập con của ngôn ngữ C đủ để viết các chương trình thực sự có thể chạy được
- Nó bao gồm biến toàn cục, hàm, câu lệnh if/while, toán tử, giải tham chiếu con trỏ, chú thích, hợp ngữ nội tuyến, cho phép thực thi các chương trình hoàn chỉnh chỉ với cấu trúc tối thiểu
- Để đơn giản hóa tokenizer, tác giả đã thiết kế ngôn ngữ Barely C với token hóa dựa trên khoảng trắng và hàm băm dùng
atoi(), qua đó vẫn giữ được cú pháp C hiện có đồng thời đạt mức cắt giảm kích thước cực đoan
- Trong quá trình tối ưu mã, nhiều kỹ thuật nén ở cấp hợp ngữ đã được áp dụng như loại bỏ jump, hợp nhất lời gọi, tận dụng offset 8 bit, sử dụng
stosw/lodsw, giúp giảm từ 468 byte xuống 303 byte
- Kết quả là một trình biên dịch C hoàn chỉnh bao gồm tokenizer, parser, bộ sinh mã và runtime đều nằm trong 512 byte, cho thấy một ví dụ cực hạn về việc tối giản phần mềm
Tổng quan về SectorC
- SectorC là một trình biên dịch C được viết bằng hợp ngữ x86-16, nằm trọn vẹn trong boot sector 512 byte
- Kho lưu trữ GitHub: xorvoid/sectorc
- Ngôn ngữ được hỗ trợ là một tập con của C ở mức đủ để viết chương trình thực tế
- Các tính năng được hỗ trợ bao gồm biến toàn cục, hàm, câu lệnh điều khiển (if/while), nhiều toán tử, giải tham chiếu con trỏ, hợp ngữ nội tuyến, chú thích
- Một chương trình ví dụ được đưa ra là mã vẽ hoạt ảnh sóng sin trong chế độ VGA
Bối cảnh thiết kế và cách tiếp cận
- Vì tokenizer C truyền thống quá lớn để nhét vào 512 byte, tác giả buộc phải đơn giản hóa chính cấu trúc ngôn ngữ
- Ý tưởng lớn #1: áp dụng cấu trúc token phân tách bằng khoảng trắng giống ngôn ngữ Forth để thiết kế một biến thể tên là “Barely C”
- Ví dụ:
int(main)(){while(!done){ được xử lý như một “mega-token”
- Trong các trình biên dịch C hiện có, nó vẫn được nhận là mã C hợp lệ
- Ý tưởng lớn #2: dùng hàm
atoi() như một hàm băm để chuyển token thành số
- Số nguyên literal, từ khóa và định danh đều được xử lý thông qua kết quả của
atoi()
- Định danh được truy cập như chỉ mục của một mảng 64K
Triển khai Barely C
- Bản triển khai đầu tiên có kích thước 468 byte, với cấu trúc parser đệ quy xuống dùng token dựa trên
atoi
- Không có bảng ký hiệu, mà truy cập trực tiếp segment 64K bằng giá trị băm
- Bộ sinh mã dùng phong cách OTCC, với thanh ghi
ax làm nơi lưu kết quả
- Sau đó tác giả thử nghiệm byte-threaded code để áp dụng cấu trúc kiểu Forth, nhưng trong giới hạn 512 byte thì cách này lại kém hiệu quả hơn nên bị loại bỏ
Kỹ thuật tối giản mã
- Quay lại cấu trúc tuyến tính, kích thước được giảm từ 468 byte → 303 byte
- Sử dụng các kỹ thuật như loại bỏ jump (fall-through), tail-call, hợp nhất lời gọi (call fusion), tận dụng
stosw/lodsw, duy trì offset jump 8 bit
- Giải phóng được 207 byte không gian trống để bổ sung tính năng
Mở rộng thành tính năng C hoàn chỉnh
- Thêm 200 byte để đạt được hỗ trợ cú pháp C hoàn chỉnh
- Các khối
if/while lồng nhau, nhiều *toán tử nhị phân (+, -, , &, |, ^, <<, >>, ==, !=, <, >, <=, >=)
- Hỗ trợ định nghĩa hàm và gọi đệ quy, hợp ngữ nội tuyến (
asm), chú thích một dòng/nhiều dòng
- Thông qua bảng toán tử (
binary_oper_tbl), mỗi toán tử được định nghĩa trong 4 byte, xử lý 14 toán tử chỉ với 56 byte
Cấu trúc cú pháp
- Toàn bộ ngữ pháp gồm
program, var_decl, func_decl, statement, expr v.v.
- Hỗ trợ cả chú thích
// và /* */
- Phần văn bản định nghĩa ngữ pháp tự nó đã dài 704 byte, còn lớn hơn cả phần triển khai thực tế
Hợp ngữ nội tuyến và runtime
- Thông qua cú pháp
asm, có thể chèn trực tiếp mã máy x86-16
- Đây là tính năng thiết yếu để xử lý I/O
- Runtime (
rt/) gồm hai tệp được viết bằng C
rt/lib.c: các routine thư viện dựa trên hợp ngữ nội tuyếnrt/_start.c: điểm vào chương trình _start()
Chương trình ví dụ
examples/hello.c: in trực tiếp văn bản vào bộ nhớ 0xB8000examples/sinwave.c: hiển thị hoạt ảnh sóng sin ở chế độ VGA 0x13examples/twinkle.c: phát “Twinkle Twinkle Little Star” qua loa PC (có cảnh báo âm thanh)
Kết luận
- SectorC là một trình biên dịch C siêu nhỏ hiện thực hóa một mục tiêu tưởng như bất khả thi, đồng thời cho thấy một ví dụ cực hạn về tối giản phần mềm và thiết kế ngôn ngữ đầy sáng tạo
- Phần cuối bài viết khép lại bằng các lựa chọn hài hước kiểu “bạn đã học được gì”, nhấn mạnh theo lối châm biếm về tinh thần thách thức điều tưởng như không thể và giá trị của việc đơn giản hóa phần mềm
1 bình luận
Ý kiến trên Hacker News
Các trình biên dịch tối ưu hóa của những năm 2000 thậm chí có thể đã tối ưu những token đó thành no-op 😉
Làm game boot sector thật sự là một trải nghiệm đầy ma thuật và gợi hoài niệm. Nó làm tôi nhớ về thời lập trình còn thực sự vui
Trong thời đại AI bây giờ, thật tiếc khi những dự án như thế này bị đánh giá thấp quá nhiều
Link dự án của tôi
Dự án của bạn có vẻ có một tùy chọn để sinh mã cho boot sector.
Cả hai đều thú vị, nhưng điểm chung chỉ cỡ ‘boot sector’, ‘C’, ‘compiler’ mà thôi
Nên tôi có cảm giác mình không còn đặc biệt nữa
Chúng ta cứ chồng thêm các lớp trừu tượng, đến mức chỉ để chạy “Hello World” cũng cần 200MB node_modules
Trong khi đó lại có người nhét được một trình biên dịch C vào 512 byte
Không phải ai cũng nên viết mã boot sector, nhưng đọc những dự án như thế này thật sự là một trải nghiệm khiến mình khiêm tốn hơn. Giá trị giáo dục của nó cũng rất lớn
Dự án này cho thấy cấu trúc cốt lõi của C đơn giản đến mức nào.
Thật thú vị khi C phát triển từ ngôn ngữ B, và B lại phát triển từ một phiên bản rút gọn của Fortran
Suy cho cùng trong assembly cũng chỉ có jmp thôi mà.
Và nên viết là “chose your own adventure” chứ không phải “choose your own adventure” :)
Tôi yêu chủ nghĩa tối giản
Kiểu bắt đầu từ một binary rất nhỏ dành riêng cho nền tảng rồi dần dần tạo ra các công cụ và trình biên dịch phức tạp hơn
Có thể tham khảo các dự án mishmashvm và tcc_bootstrap_alt làm ví dụ
Cuộc thảo luận khi đó ở đây
SectorC: A C Compiler in 512 bytes - link - tháng 5 năm 2023 (80 bình luận)
Còn dự án này chỉ xử lý được một phần của C
Nói cách khác, đây không hẳn là một trình biên dịch C đầy đủ mà là trình biên dịch cho một tập con của C.
Mã có thể biên dịch bằng trình biên dịch này thì cũng biên dịch được bằng trình biên dịch C thật, nhưng chiều ngược lại thì không
May là chắc tôi đã không dùng nhiều ký hiệu đến mức gặp va chạm 32-bit
Nhân tiện, vẫn còn 21 byte chỗ trống trong khoảng 0x01e0~0x01fd. Có khi còn nhét thêm được gì đó ;)
Nhưng nếu tôi nhớ không nhầm thì atoi() được định nghĩa là trả về 0 với đầu vào không hợp lệ
Khi chạy trên Linux thì chỉ cần đổi lệnh gọi qemu từ coreaudio sang alsa
Tôi đã gửi một pull request lên GitHub cho việc này. Nếu tác giả thấy ổn với phong cách shell script verbose của tôi thì có thể sẽ merge
Có lẽ giờ là lúc thử thêm một trình biên dịch C vào đó
Link dự án OS của tôi