Nén dữ liệu không mất mát bằng RLE, LZW và Huffman

Ngày 21/10/2026, Node.js phát hành bản vá cho CVE-2026-111497, một lỗi trong bộ giải nén Brotli đi kèm Node.js ^[1]. Brotli là định dạng nén Google làm ra. Server dùng nó để gửi trang web nhỏ hơn cho trình duyệt, còn Node.js mang sẵn thư viện giải nén của nó trong module node:zlib.

Một file Brotli độc có thể chứa một lệnh khiến bộ giải nén cứ nối thêm byte vào một buffer 8 byte, ghi tràn sang vùng nhớ bên cạnh ^[1]. Ứng dụng nào giải nén dữ liệu Brotli do người ngoài gửi vào thì có thể bị làm sập, bị lộ bộ nhớ, hay bị chạy mã từ xa. Ngày 27/10, CISA, cơ quan an ninh mạng của Mỹ, đưa lỗi này vào danh mục lỗi đã bị khai thác ^[2].

Bộ nén là chương trình viết dữ liệu thành bản ngắn hơn, bộ giải nén là chương trình đọc bản ngắn rồi dựng lại đúng từng byte. Hai bên phải thống nhất cách viết từ trước, vì bên giải nén chỉ có trong tay bản ngắn. Bản ngắn đó là chuỗi chỉ dẫn để dựng lại dữ liệu gốc, và bộ giải nén làm theo từng chỉ dẫn một.

Nén ở đây là nén không mất mát, kiểu giải ra đúng từng byte như zip hay PNG. JPEG hay MP3 bỏ bớt chi tiết mà mắt và tai khó nhận ra, đó là chuyện khác. Bên trong zip, PNG hay Brotli là ba mẹo: gom chỗ lặp liền nhau, thay cụm đã gặp bằng một tham chiếu, cho thứ hay gặp mã ngắn hơn. Mình đếm bit từng mẹo trên cùng một sổ order.

Mã độ dài cố định

Giả sử một quán cà phê ghi lại từng ly khách gọi trong buổi sáng để cuối ngày gửi về máy tổng. Sáng nay quán bán 100 ly, 6 món:

Máy tính lưu mọi thứ bằng bit, mỗi bit là một ô chỉ nhận 0 hoặc 1. 8 bit gộp lại là một byte. Cách đơn giản nhất là cho mỗi món một dãy bit dài bằng nhau. 2 bit chỉ có 4 tổ hợp 00, 01, 10, 11, không đủ cho 6 món. 3 bit có 8 tổ hợp, đủ và còn thừa hai. Vậy mỗi ly tốn 3 bit, 100 ly tốn 300 bit.

Sữa đá 40 ly cũng tốn 3 bit mỗi ly như nước cam 5 ly.

Gom chỗ lặp liền nhau

Chiều hôm đó có hai nhóm khách, mỗi nhóm 12 người gọi trà đá, xen giữa là một khách gọi sữa đá. Sổ ghi mỗi ly một ký tự, T là trà đá, S là sữa đá, nên đoạn này dài 25 ký tự, tức 25 byte:

TTTTTTTTTTTTSTTTTTTTTTTTT

RLE, viết tắt của run-length encoding, ghi số lần lặp thay cho từng ly: 12 T, 1 S, 12 T. Mỗi cặp gồm một byte số đếm và một byte món, 3 cặp là 6 byte thay cho 25.

Đổi sang bốn khách gọi bốn món khác nhau, sữa đá, bạc xỉu, trà đá, cà phê đen, thì RLE ghi 1S 1X 1T 1D, 8 byte thay cho 4. File to gấp đôi. Mỗi đoạn tốn 2 byte, nên RLE chỉ có lợi khi trung bình mỗi đoạn dài hơn 2 ly.

Chỗ RLE được dùng thật là máy fax. Fax nhóm 3 quét mỗi dòng của trang A4 thành 1728 điểm đen hoặc trắng, rồi gửi độ dài các đoạn trắng và đen xen kẽ nhau ^[3]. Trang văn bản phần lớn là giấy trắng, nên dòng nào cũng có những đoạn trắng rất dài. Độ dài mỗi đoạn lại được tra trong một bảng mã dài ngắn khác nhau. Cả một dòng trắng 1728 điểm dùng mã 9 bit, cộng mã kết thúc 8 bit và mã xuống dòng 12 bit là 29 bit, thay cho 1728 bit.

Từ điển tự dựng của LZW

RLE chỉ thấy chỗ lặp liền nhau. Sổ order hay lặp kiểu khác: khách quen gọi cặp sữa đá và bạc xỉu, hết bàn này tới bàn khác. Lấy 9 ly gọi liên tiếp, S là sữa đá, X là bạc xỉu, T là trà đá:

S X X S X S X S T

LZW, đặt theo tên Lempel, Ziv và Welch ^[4], thay một cụm đã gặp bằng số thứ tự của cụm đó trong một từ điển. Từ điển ban đầu chỉ có 6 món, đánh số 1 tới 6, trong đó S là 1, X là 2, T là 3. Bộ nén giữ một cụm W, đọc từng ly c, và làm như sau:

• W nối c đã có trong từ điển thì lấy cụm dài hơn đó làm W, đọc ly tiếp.
• Chưa có thì ghi ra số của W, thêm cụm W nối c vào từ điển với số kế tiếp, rồi bắt đầu lại W từ c.

9 ly thành 6 số: 1, 2, 2, 7, 10, 3.

Bên giải nén không nhận từ điển. Nó bắt đầu từ cùng 6 món, đọc số 1 ra S, số 2 ra X. Từ số thứ hai trở đi, mỗi số đọc vào cho nó thêm đúng mục bên nén đã thêm ở bước trước: cụm vừa giải trước đó, nối thêm ký tự đầu của cụm vừa đọc. Bên giải nén vì vậy luôn chậm bên nén một mục.

Số 10 được bên nén tạo ra rồi dùng ngay ở bước kế tiếp. Lúc bên giải nén đọc tới số 10, từ điển của nó mới tới số 9. Nó vẫn suy ra được: mục số 10 phải bắt đầu bằng cụm vừa giải là SX, và ký tự cuối của nó là ký tự đầu của chính nó, tức S. Vậy số 10 là SXS. Bộ giải nén LZW nào cũng phải có một nhánh riêng cho trường hợp này, quên nó thì giải sai những dãy kiểu SXSXS.

Đếm bit thì từ điển giờ có 11 mục, mỗi số cần 4 bit, 6 số là 24 bit, so với 27 bit nếu ghi 9 ly bằng mã 3 bit. Lợi được 3 bit vì dãy ngắn quá, từ điển chưa kịp dày. Trên văn bản thật thì khác. Một bản LZW tự viết, mã dài dần từ 9 tới 12 bit như GIF, nén văn bản của RFC 1951 từ 36.944 byte còn 15.906 byte, tức 43,1%.

GIF dùng đúng thuật toán này ^[5]. LZW lại có bằng sáng chế của Unisys, và ngày 28/12/1994 CompuServe, công ty làm ra GIF, công bố thoả thuận với Unisys để thu phí các phần mềm hỗ trợ GIF ^[6]. Bản nháp đầu tiên của PNG đăng ngày 4/1/1995, và ngay trong tuần đó deflate được đề xuất làm cách nén thay cho LZW.

Deflate, thứ nằm trong zip, gzip và PNG, dùng LZ77, họ hàng của LZW ^[7]. LZ77 không đánh số từ điển mà ghi thẳng "lùi lại bao nhiêu, chép bao nhiêu": phần vừa giải nén chính là từ điển. Với 9 ly đó, LZ77 ghi S, X, X, S, rồi "lùi lại 2, chép 4", rồi T. Đoạn chép dài hơn khoảng lùi, nên nó chép lại cả những ly vừa chép xong.

Mã ngắn cho món hay gọi

Quay lại 100 ly. Cho sữa đá mã 1 bit thì sao?

Mã Morse làm đúng việc đó. E, chữ hay gặp nhất trong tiếng Anh ^[8], là một chấm, còn Q, một trong những chữ ít gặp nhất, là bốn ký hiệu ^[9]. Đổi lại phải có khoảng nghỉ. I là hai chấm, S là ba chấm, nên ba chấm liền nhau đọc được S, EEE, EI hay IE. Người đánh Morse phải ngừng một quãng giữa các chữ, và quãng ngừng đó thực chất là ký hiệu thứ ba ngoài chấm và gạch. Dãy bit thì không có chỗ ngừng.

Muốn khỏi cần khoảng nghỉ thì không mã nào được là phần đầu của mã khác. Mã như vậy gọi là prefix-free. Sữa đá là 0 thì mọi món khác phải bắt đầu bằng 1, và đọc từ trái sang, gặp 0 là chắc chắn sữa đá, không cần chờ bit sau. Vẽ ra thì mỗi mã là một đường đi trên cây: rẽ trái là 0, rẽ phải là 1, món nằm ở lá. Không đường đi nào đi xuyên qua một lá, nên không mã nào là đầu của mã khác.

Cây nào cho ít bit nhất? Năm 1952, David Huffman công bố cách dựng ^[10]: gộp hai món ít ly nhất thành một nút, coi nút đó là một món mới có số ly bằng tổng của hai món, rồi lặp lại tới khi chỉ còn một cây.

Sữa đá nằm ngay dưới gốc nên mã chỉ 1 bit. Bạc xỉu, trà đá, cà phê đen 3 bit, trà đào và nước cam 4 bit. Cả sổ tốn

\[\begin{aligned} &{40} \times 1 + 20 \times 3 + 15 \times 3 \\ &+ 11 \times 3 + 9 \times 4 + 5 \times 4 \\ &= 234 \text{ bit}, \end{aligned}\]

bớt 22% so với 300 bit.

Vì sao gộp hai món nhỏ nhất trước? Mỗi lần gộp, mọi ly nằm dưới nút mới dài thêm 1 bit. Gộp nước cam với trà đào thì 14 ly đó mỗi ly thêm 1 bit, tổng tăng đúng 14. Tổng bit của cả sổ vì vậy bằng tổng các nút gộp, 14 + 25 + 35 + 60 + 100 = 234. Gộp hai nhánh nhỏ nhất là cách cộng thêm ít nhất ở mỗi bước, và trong paper Huffman chứng minh cách đó cho tổng nhỏ nhất trong mọi mã prefix-free.

Giới hạn của mọi bộ nén

Muốn ít hơn 234 bit thì có một mức sàn. Năm 1948, Claude Shannon chỉ ra rằng nếu coi mỗi ly độc lập với ly trước, số bit trung bình mỗi ly không xuống được dưới một con số tính từ tần suất, gọi là entropy ^[11]. Với sổ này, sàn đó là khoảng 2,28 bit mỗi ly, 228,3 bit cho 100 ly. Huffman tốn 2,34. Phần chênh đến từ việc mã phải dài nguyên số bit: theo tần suất, bạc xỉu đáng giá khoảng 2,32 bit mà phải nhận 3.

Không bộ nén không mất mát nào làm nhỏ được mọi file. Có 256 dãy dài đúng 8 bit. Dãy ngắn hơn 8 bit, kể cả dãy rỗng, chỉ có 1 + 2 + 4 + ... + 128 = 255 dãy. Nếu một bộ nén thu nhỏ được cả 256 dãy thì sẽ có hai dãy chung một bản nén, và bộ giải nén không biết dãy nào mới là bản gốc. Bộ nén nào làm nhỏ được một số file thì cũng làm to một số file khác.

gzip nén văn bản RFC 1951 còn 30,1%, Brotli còn 24,5%. Nén lại chính file gzip đó thì ra 100,2%, to thêm 23 byte. Một ảnh chụp JPEG chỉ bớt được khoảng 1%, còn byte ngẫu nhiên thì to ra một chút. JPEG đã tự nén rồi. Byte ngẫu nhiên thì không có chỗ lặp, không có byte nào hay gặp hơn byte nào, nên cả ba mẹo đều không có gì để ăn.

Đào sâu: entropy và bất đẳng thức Kraft

Gọi \(p_i\) là tỷ lệ của món thứ \(i\) trong sổ. Entropy là

\[H = -\sum_i p_i \log_2 p_i.\]

Với sổ order, \(p\) lần lượt là \({0{,}40}\), \({0{,}20}\), \({0{,}15}\), \({0{,}11}\), \({0{,}09}\) và \({0{,}05}\), nên \(H \approx 2{,}2827\) bit mỗi ly. Món có tỷ lệ \(p\) đáng giá \(-\log_2 p\) bit: sữa đá \({1{,}32}\) bit, nước cam \({4{,}32}\) bit.

Một bộ độ dài mã \(\ell_i\) dựng được thành mã prefix-free khi và chỉ khi

\[\sum_i 2^{-\ell_i} \le 1.\]

Đây là bất đẳng thức Kraft. Mỗi mã dài \(\ell\) chiếm \({2^{-\ell}}\) của cây, vì nó khoá luôn mọi đường đi bên dưới nó. Mã Huffman của sổ order có độ dài 1, 3, 3, 3, 4 và 4, nên

\[{2^{-1}} + 3 \times 2^{-3} + 2 \times 2^{-4} = 1,\]

tức cây dùng hết chỗ, không lá nào bỏ không.

Từ Kraft suy ra hai cận của độ dài trung bình \(L\). Cận dưới, mọi mã prefix-free đều có \(L \ge H\). Cận trên, chọn \(\ell_i = \lceil -\log_2 p_i \rceil\) luôn thoả Kraft, nên luôn có mã với \(L \lt H + 1\), và Huffman không tệ hơn mã đó. Vậy

\[H \le L_{\text{Huffman}} \lt H + 1,\]

với sổ order là

\[{2{,}2827} \le 2{,}34 \lt 3{,}2827.\]

Muốn xuống sát \(H\) thì phải bỏ luật mỗi ký hiệu một mã nguyên bit. Arithmetic coding mã hoá cả dãy thành một số duy nhất, còn zstd mã hoá độ dài và khoảng lùi bằng asymmetric numeral systems ^[12]. Cả hai cho phép một ký hiệu tốn lẻ bit.

Với mọi \(n\),

\[\sum_{k=0}^{n-1} 2^k = 2^n - 1 \lt 2^n,\]

số dãy ngắn hơn \(n\) bit luôn ít hơn số dãy dài đúng \(n\) bit.

Brotli ghép các mẹo

RFC 7932 tả Brotli là định dạng nén không mất mát ghép LZ77 với mã Huffman ^[13].

Một luồng Brotli là một dãy lệnh. Mỗi lệnh nói chèn vài byte thô, rồi lùi lại một khoảng và chép một đoạn, đúng kiểu LZ77. Số byte chèn, độ dài đoạn chép, khoảng lùi và từng byte thô đều được viết bằng mã Huffman. Brotli còn cho phép mỗi loại có nhiều bảng mã. Từ khối thứ hai trở đi, một lệnh block switch báo từ đây dùng bảng mã nào, cho bao nhiêu phần tử tiếp theo. Bảng mã cho byte thô còn được chọn theo hai byte đứng ngay trước, và Brotli mang sẵn một từ điển tĩnh các từ để chép ra.

Bộ giải nén phải nhận ra lệnh vô nghĩa, chẳng hạn một lệnh block switch ở loại chỉ có một bảng mã, nơi không có bảng nào để đổi sang. Bộ nén Brotli không bao giờ sinh ra lệnh như thế, nhưng bộ giải nén nhận được mọi dãy byte, kể cả dãy không do bộ nén nào sinh ra.

Gặp một lệnh block switch sai, bộ giải nén báo "cần thêm dữ liệu" thay vì "file hỏng". Khi giải nén kiểu streaming, đọc từng mẩu như khi đang tải một trang web, nó cứ thế chờ thêm, và mỗi mẩu tới lại được nối vào buffer 8 byte kia ^[1].

Trong mã nguồn Brotli, hàm đọc lệnh block switch trước đây chỉ trả về đúng hay sai. Commit ngày 27/02/2026 đổi nó sang trả về một mã lỗi riêng cho lệnh block switch sai, để luồng như vậy bị từ chối ngay. Commit tự mô tả là phát hiện và báo luồng không hợp lệ sớm hơn ^[14].

Brotli 1.2.1, bản phát hành ghi vá CVE-2026-111497, ra cùng ngày Node.js công bố lỗi, và thay đổi code duy nhất trong đó là commit tháng 2 kia được chép sang ^[15]. Từ lúc sửa trong mã nguồn tới lúc lỗi được công bố là gần 8 tháng.

Bình