Chuyện biểu diễn ma trận trên máy tính

Cách đây mấy hôm mình có share cái screenshot trên Facebook, khoe linh tinh vụ mình đang viết lại cái CHIP-8 emulator bằng Rust.

viết Emulator hay code bất cứ thứ gì cũng vậy. Và trong quá trình đó thì người viết luôn phải trải qua vô số những quyết định về mặt kĩ thuật, ví dụ như nên dùng if..else hay pattern matching, viết test hay ko test , chia module hay viết 100 ngàn dòng trong 1 file,...

Một trong những quyết định đau đầu nhất của mình đó là chọn cấu trúc dữ liệu để biểu diễn ma trận hiển thị (display matrix) - tức là cái màn hình cho emulator.

như là Arduino thì đây là cả một vấn đề cực kì lớn. Đơn cử, dòng Arduino phổ biến nhất là UNO R3, sử dụng vi xử lý ATmega328P và bộ nhớ SRAM (static random access memory) của nó chỉ có đúng 2 KB.

Quèo, trên thực tế thì bạn vẫn không thể chạy trực tiếp CHIP-8 emulator trên Arduino được vì tính riêng dung lượng bộ chớ chính của nó cũng đã ngốn mất 4096 bytes rồi trong trường hợp này chúng ta cần dùng thêm một con chip khác để làm external RAM, tuy nhiên, vấn đề này nằm ngoài phạm vi bài viết, có thể mình sẽ nói tới trong một bài khác.

Dễ nhận thấy, đối với CHIP-8, màn hình hiển thị chỉ gồm 2 màu trắng đen, mỗi pixel chỉ có 2 trạng thái đó là on hoặc off, tương đương với chỉ có 2 giá trị 0 hoặc 1, vậy thì việc dùng số nguyên để biểu diễn là không cần thiết.

Kiểu dữ liệu nào chỉ có 2 trạng thái nhỉ? bool! Tuy nhiên ngay cả kiểu bool trong Rust cũng chiếm tới 1 byte (8 bits). Còn trong JavaScript thì mình chịu, không có tài liệu nào nói cụ thể, các đoạn code tính size của 1 type thì ghi nó tận 4 bytes . Mình không tin có bằng chứng thì mới tin.

Ý định dùng bool coi như cũng không có ổn. Bỏ!

Dùng bit array

Bản thân một bit có thể chứa được 2 giá trị (0 và 1), như vậy là đã thỏa mãn cho yêu cầu của một ma trận hiển thị.

Vậy thì có cách nào chỉ dùng đúng $64 \times 32 = 2048$ bits trong bộ nhớ không? Có!

Rust có hỗ trợ kiểu u64 (64-bit unsigned integer), là một kiểu số nguyên không đấu, khi khai báo một biến kiểu này tất nhiên nó sẽ chiếm 64 bits trong bộ nhớ.

.

Đọc một bit

Để đọc một bit thứ i của một số n, ta dịch phải số n một khoảng bằng i - 1 bits, và thực hiện phép AND kết quả thu được với 1:

$$
\texttt{(n >> (i - 1)) & 1}
$$

Ví dụ: Để đọc bit thứ 6 của số 0xA1, ta sử dụng công thức trên qua từng bước như sau:

Số 0xA1 biểu diễn dưới dạng nhị phân là 1010 0001. Để lấy được bit thứ 6, ta cần dịch phải 5 bit:

$$
\texttt{1010 0001 >> 5} = \texttt{0000 0101}
$$

Tiếp theo, ta thực hiện phép AND kết quả trên với số 1, thực chất có biểu diễn nhị phân là 0000 0001:

$$
\texttt{0000 0101 & 0000 0001} = \texttt{0000 0001} = \texttt{1}
$$

Kết quả thu được sẽ là 1.

Ghi một bit

Để ghi giá trị 1 vào bit thứ i của số n, ta dùng phép OR cho số n và kết quả của phép dịch trái số 1 một khoảng i - 1 bits:

$$
\texttt{n | (1 << (i - 1))}
$$

Ví dụ: Để ghi vào bit thứ 4 của số 0xA1, đầu tiên ta lấy số 1 dịch phải một khoảng 3 bit:

$$
\texttt{0000 0001 << 3} = \texttt{0000 1000}
$$

Sau đó ta thực hiện phép OR kết quả thu được với số 0xA1:

$$
\texttt{1010 0001 | 0000 1000} = \texttt{1010 1001} = \texttt{0xA9}
$$

Xóa một bit

Để xóa một bit thứ i (đưa bit đó về giá trị ban đầu, là 0) của một số n, ta làm như sau:

$$
\texttt{n & !(1 << (i - 1))}
$$

Ví dụ: Để chuyển giá trị 0xA9 thu được ở ví dụ trên về lại thành 0xA1, ta phải xóa bit thứ 4 cua số đó. Tương tự như ở ví dụ trước, đầu tiên ta sẽ dịch trái số 1 một khoảng 3 bit, lần này ta lấy giá trị nghịch đảo NOT của nó.

$$
\lnot (\texttt{0000 0001 << 3}) = \lnot (\texttt{0000 1000}) = \texttt{1111 0111}
$$

Sau đó thực hiện phép AND giữa kết quả thu được và giá trị nhị phân của số 0xA9:

$$
\texttt{1010 1001 & 1111 0111} = \texttt{1010 0001} = \texttt{0xA1}
$$

Implement

Đã thấy lợi hại chưa?

Cá nhân mình thì ko biết nữa, nhưng thấy khá là hại não tuy nhiên hiệu quả đem lại thì rất lớn, chúng ta đã tiết kiệm được một lượng lớn bộ nhớ, từ 2KB xuống còn 2048 bits.

Bây giờ thì có thể implement thành hàm hay class để dùng lại cho tiện. Ví dụ, đây là hai hàm mình viết để sử dụng trong emulator:

// Lưu ý, code này không có chính xác :v
impl Screen { ... pub fn set_pixel(&mut self, x: usize, y: usize, on: bool) { if on { self.display[y] |= 1 << x; } else { self.display[y] &= (!(1 << x)); } } pub fn get_pixel(&self, x: usize, y: usize) -> u64 { (self.display[y] >> x) & 1 } ...
}

Ngoài việc dùng cho emulator (màn hình trắng đen) ra, thì cách thể hiện ma trận dùng bit array này còn có thể được dùng cho nhiều trường hợp khác như bảng đèn điện tử (tín hiệu bật/tắt), lưu các đỉnh của một đồ thị, lưu bàn cờ hoặc các thể loại map đơn giản nếu bạn làm game, hoặc có thể cải tiến để sử dụng từng byte thay vì từng bit để lưu trữ được nhiều thông tin hơn.

Hy vọng qua bài viết này, mình đã ít nhiều chia sẽ được cho các bạn chút gì đó, mặc dù cho đến thời điểm này mình vẫn chưa biết là mình đã chia sẽ được gì

Cảm ơn các bạn đã kiên nhẫn đọc đến tận những dòng này. Nếu các bạn cảm thấy bài viết này thú vị, đừng ngại để lại comment, và nhớ subscribe vào mailing list của mình để nhận thông báo về các bài viết mới, hoặc like trang Facebook để đọc những dòng status ất ơ ngẫu nhiên của mình vào một ngày đẹp trời nào đó. Chào thân ái và quyết thắng.