ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Mai Thanh Minh

XÂY DỰNG NGƠN NGỮ LẬP TRÌNH VÀ
TRÌNH BIÊN DỊCH CHO MÁY ẢO XỬ LÝ
DỮ LIỆU TRONG TẬP TIN LƯU TRỮ

LUẬN VĂN THẠC SĨ
Ngành: Công nghệ thông tin

HÀ NỘI - 2021


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Mai Thanh Minh

XÂY DỰNG NGƠN NGỮ LẬP TRÌNH VÀ
TRÌNH BIÊN DỊCH CHO MÁY ẢO XỬ LÝ
DỮ LIỆU TRONG TẬP TIN LƯU TRỮ

LUẬN VĂN THẠC SĨ
Ngành: Công nghệ thông tin

Cán bộ hướng dẫn: TS. Võ Đình Hiếu

HÀ NỘI - 2021

VIETNAM NATIONAL UNIVERSITY, HA NOI
UNIVERSITY OF ENGINEERING AND TECHNOLOGY

Mai Thanh Minh

BOX: PROGRAMMING LANGUAGE
FOR FORWARD–COMPATIBLE
ARCHIVE FORMAT

MASTER’S THESIS
Major: Software Engineering

Supervisor: Dr. Vo Dinh Hieu

HANOI - 2021


LỜI CẢM ƠN
Đầu tiên, tôi xin gửi lời cảm ơn chân thành và sâu sắc tới thầy giáo TS. Võ
Đình Hiếu – người đã trực tiếp hướng dẫn tận tình và đóng góp những ý kiến
quý báu trong suốt quá trình học tập, nghiên cứu của tơi cũng như trong q
trình tơi thực hiện luận văn tốt nghiệp này, những người đã cho tôi nhiều lời
động viên, những kiến thức quý báu giúp tôi trưởng thành hơn trong cuộc sống.
Tôi xin gửi lời cảm ơn tới những người bạn trong tập thể lớp – những người
đã luôn đồng hành cùng tôi suốt bốn năm qua trên mọi nẻo đường, giúp đỡ tơi
mỗi khi khó khăn, chia sẻ cùng tơi mọi chuyện trong học tập và cuộc sống và
góp ý cho tôi những lời khuyên chân thành giúp tôi học tập tốt hơn và hồn
thành khóa luận này.
Tiếp theo tơi xin gửi lời cảm ơn đến các thầy cô giảng viên Trường Đại học

Công Nghệ - Đại Học Quốc Gia Hà Nội – những người đã tận tâm truyền đạt
những kiến thức quý báu làm nền tảng để tôi tiếp tục đi xa hơn nữa trong lĩnh
vực công nghệ thông tin. Tôi xin được cảm ơn cha mẹ, anh chị và người thân,
những người đã khơng quản khó khăn, vất vả ni con ăn học để con có thể
phấn đấu trở thành người có ích cho xã hội. Tơi cũng xin được cảm ơn những
hỗ trợ từ đề tài CN21.01 của Trường Đại học Công Nghệ - Đại Học Quốc Gia
Hà Nội đã giúp tơi hồn thành luận văn này.

i


LỜI CAM ĐOAN
Tôi xin cam đoan rằng những nghiên cứu về ngôn ngữ cho máy ảo phục vụ
xử lý dữ liệu trong tập tin lưu trữ được trình bày trong luận văn này là của tôi
và chưa từng được nộp như một báo cáo luận văn tại trường Đại học Công Nghệ
– Đại học quốc gia Hà Nội hoặc bất kỳ trường đại học khác. Những gì tơi viết ra
khơng sao chép từ các tài liệu, không sử dụng các kết quả của người khác mà
khơng trích dẫn cụ thể. Tơi xin cam đoan cơng cụ tơi trình bày trong luận văn
là do tôi tự phát triển, không sao chép mã nguồn của người khác. Nếu sai tơi
hồn tồn chịu trách nhiệm theo quy định của trường Đại Học Công Nghệ - Đại
Học Quốc Gia Hà Nội.
Hà Nội, ngày 24 tháng 12 năm 2021
Học viên

Mai Thanh Minh

ii


Mục lục

Danh sách bảng

v

Danh sách hình vẽ

v

Danh sách mã nguồn

vi

Chương 1

Đặt vấn đề

1

Chương 2

Kiến thức cơ sở

3

2.1

2.2

2.3


Một số tập tin lưu trữ phổ biến . . . . . . . . . . . . . . . . . .

3

2.1.1

ZIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.2

TAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.3

RAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.1.4

7z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

Các thuật toán xử lý dữ liệu trong tập tin lưu trữ . . . . . . . .


10

2.2.1

Các thuật toán nén dữ liệu . . . . . . . . . . . . . . . . .

11

2.2.2

Các thuật tốn mã hóa dữ liệu . . . . . . . . . . . . . .

12

2.2.3

Các thuật toán phát hiện và sửa lỗi dữ liệu . . . . . . . .

13

Máy ảo thực thi . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

Chương 3

Ngôn ngữ lập trình mới

3.1 Xây dựng yêu cầu và ràng buộc thiết kế của ngơn ngữ lập trình
3.1.1


Sự cần thiết và yêu cầu của định dạng mới . . . . . . . .

iii

16
16
16


3.1.2

Yêu cầu của định dạng mới và ràng buộc liên quan của
ngơn ngữ lập trình đính kèm . . . . . . . . . . . . . . . .

18

Lựa chọn ngơn ngữ lập trình đính kèm . . . . . . . . . .

20

3.2

Ký pháp mô tả ngữ pháp ngôn ngữ . . . . . . . . . . . . . . . .

20

3.3

Các thành phần cơ bản của ngôn ngữ lập trình Box . . . . . . .


21

3.4

Các kiểu dữ liệu trong ngơn ngữ lập trình Box . . . . . . . . . .

23

3.5

Biểu thức trong ngơn ngữ lập trình Box . . . . . . . . . . . . .

25

3.5.1

Các biểu thức cơ bản . . . . . . . . . . . . . . . . . . . .

26

3.5.2

Các biểu thức số học và đại số . . . . . . . . . . . . . . .

28

3.5.3

Các biểu thức trên bit . . . . . . . . . . . . . . . . . . .


29

3.5.4

Các biểu thức so sánh và logic . . . . . . . . . . . . . . .

29

3.6

Các định nghĩa trong ngơn ngữ lập trình Box . . . . . . . . . .

31

3.7

Các câu lệnh trong ngơn ngữ lập trình Box . . . . . . . . . . . .

32

3.1.3

Chương 4
4.1

Công cụ và thử nghiệm

Cài đặt trình biên dịch . . . . . . . . . . . . . . . . . . . . . . .


4.2 Thử nghiệm ngơn ngữ mới sử dụng trình biên dịch
4.3

36
36

. . . . . . .

38

Ưu điểm và nhược điểm của ngôn ngữ Box . . . . . . . . . . . .

42

Chương 5

Kết luận

43

Tài liệu tham khảo

44

iv


Danh sách bảng
3.1


Giới hạn của các kiểu dữ liệu cơ bản . . . . . . . . . . . . . . .

24

Danh sách hình vẽ
2.1

Cấu trúc tập tin ZIP . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Cấu trúc tập tin TAR . . . . . . . . . . . . . . . . . . . . . . .

7

3.1 Tương thích ngược và tương thích xuôi . . . . . . . . . . . . . .

18

4.1

37

Giao diện dịng lệnh của trình biên dịch . . . . . . . . . . . . . .

v



Danh sách mã nguồn
4.1

Mã nguồn ANTLR mô tả cú pháp định nghĩa của Box . . . . .

38

4.2

Mã nguồn Box của hàm đệ quy tính tốn số Fibonacci . . . . .

40

4.3

Mã nguồn Java của hàm đệ quy tính tốn số Fibonacci . . . . .

40

4.4

Mã nguồn Box của hàm tính số Fibonacci sử dụng vịng lặp . .

40

4.5

Mã nguồn Java của hàm tính số Fibonacci sử dụng vòng lặp . .

40


4.6

Mã nguồn Box của hàm sắp xếp nhanh . . . . . . . . . . . . . .

41

4.7

Mã nguồn Java của hàm sắp xếp nhanh . . . . . . . . . . . . . .

41

4.8

Mã nguồn Box của hàm đánh mã số học nhị phân . . . . . . . .

42

4.9

Mã nguồn Java của hàm đánh mã số học nhị phân . . . . . . .

42

vi


Chương 1


Đặt vấn đề
Trong thời đại kỹ thuật số, dữ liệu là một nguồn tài nguyên vô cùng quan
trọng. Việc lưu trữ và vận chuyển dữ liệu một cách hiệu quả sẽ tối đa hóa khả
năng khai thác nguồn tài ngun đó. Một trong những cơng cụ hỗ trợ đắc lực
cho việc lưu trữ và vận chuyển dữ liệu chính là tập tin lưu trữ. Tập tin lưu trữ là
một lớp các định dạng tập tin được thiết kế với khả năng đóng gói nhiều tập tin
cùng các thơng tin mô tả của chúng thành một tập tin lưu trữ duy nhất, cũng
như nén, mã hoá và bổ sung các thông tin khôi phục cần thiết trong trường hợp
tập tin lưu trữ khơng cịn tồn vẹn. Việc sử dụng tập tin lưu trữ có thể làm giảm
dung lượng các tập tin cần lưu trữ và truyền tải cũng như đảm bảo tính bảo
mật cũng như tính tồn vẹn của thơng tin trong q trình lưu trữ và truyền tải.
Có rất nhiều định dạng tập tin lưu trữ khác nhau đã được thiết kế, nhưng
trong thực tế chỉ có một số định dạng được dùng phổ biến như ZIP[6, 7], TAR[9],
RAR[10, 11] và 7z[12]. Việc sinh ra nhiều định dạng lưu trữ khác nhau gây khó
khăn trong q trình chia sẻ thông tin, nhất là khi hiện nay việc chia sẻ các tập
tin qua internet trở nên dễ dàng hơn, và nhu cầu chia sẻ thông tin khi làm việc
cũng cao hơn. Nguyên nhân dẫn đến việc phát sinh các định dạng mới thường
do các định dạng sẵn có khơng hỗ trợ cho các hệ điều hành cũng như các hệ
thông lưu trữ tập tin khác nhau, hoặc các định dạng này thiếu những tính năng
cần thiết như mã hố hay sửa lỗi, hoặc do các định dạng này không được cập
nhật hỗ trợ những thuật tốn nén, mã hóa và sửa lỗi mới tốt hơn.
Để một định dạng tập tin lưu trữ có thể thay thế các định dạng tập tin
1


lưu trữ khác nhau, định dạng đó cần phải có khả năng mở rộng và nâng cấp
trong tương lai mà khơng làm mất đi sự tương thích giữa các phiên bản khác
nhau của tập tin nén đó, cả theo chiều tương thích xi và tương thích ngược.
Điều này rất khó có thể thực hiện được nếu sử dụng các phương pháp và các
định dạng hiện tại, do các thuật toán nén, mã hố và sửa lỗi (hoặc chí ít là định

danh của chúng) được định nghĩa cùng với định dạng tập tin lưu trữ, khiến cho
một trình đọc tập tin lưu trữ cũ có khả năng khơng thể giải mã được tập tin
lưu trữ mới do tập tin này sử dụng một thuật tốn mới mà trình đọc tập tin
cũ khơng biết đến. Một phương pháp mới có thể được áp dụng để giải quyết
khó khăn này là thay vì định nghĩa thuật toán, định dạng tập tin lưu trữ có thể
định nghĩa ra một phương thức mơ tả thuật tốn và đính kèm thuật tốn này
trong chính các tập tin lưu trữ. Với phương pháp này, các thuật toán nén, mã
hố và sửa lỗi mới có thể được sử dụng mà khơng làm ảnh hưởng đến khả năng
tương thích của tập tin lưu trữ.
Luận văn này nhằm mục đích giải quyết một phần bài toán định dạng tập
tin lưu trữ chung thơng qua giải quyết bài tốn mơ tả thuật tốn sử dụng trong
định dạng tập tin đó. Trong luận văn này, tôi đề xuất một ngôn ngữ lập trình
mới tên là Box, ngơn ngữ này được thiết kế với mục tiêu để có thể mơ tả một
cách hiệu quả các thuật toán xử lý dữ liệu trong tập tin lưu trữ.
Các phần còn lại của luận văn được cấu trúc như sau. Chương 2 trình bày
sơ lược về các tập tin lưu trữ đang được sử dụng phổ biến cũng như các thuật
toán nén, mã hoá và sửa lỗi dữ liệu thường được sử dụng trong thực tế cũng
như các thuật tốn mới hiện đại nhất. Ngồi ra, chương này cũng trình bày sơ
lược về các ngơn ngữ lập trình có sử dụng máy ảo thực thi có hỗ trợ đa nền
tảng đang được sử dụng trong thực tế. Chương 3 đưa ra các ràng buộc thiết kế
và mơ tả của ngơn ngữ lập trình mới được đề xuất. Ở Chương 4, ngơn ngữ lập
trình mới sẽ được sử dụng để cài đặt và thực thi thử nghiệm với các thuật toán
nén, mã hoá và sửa lỗi đã được trình bày trong chương 2. Cuối cùng, Chương 5
là kết luận của toàn bộ luận văn, chương này cũng trình bày các cơng việc tiếp
theo cần thực hiện.

2


Chương 2


Kiến thức cơ sở
Ở chương này, các tập tin lưu trữ đang được sử dụng phổ biến ở thời điểm
hiện tại sẽ được mô tả và so sánh để làm rõ ưu và nhược điểm của chúng. Chương
này cũng liệt kê và mơ tả sơ lược các thuật tốn nén, mã hoá và sửa lỗi dữ liệu
thường được sử dụng trong thực tế cũng như các thuật toán mới hiện đại nhất ở
thời điểm hiện tại. Ngoài ra, chương này cũng trình bày sơ lược các máy ảo thực
thi ngơn ngữ phổ biến có hỗ trợ đa nền tảng đang được sử dụng trong thực tế
để làm rõ các nhu cầu cũng như các vấn đề phát sinh khi tiếp cận việc đính kèm
mơ tả thuật tốn thơng qua mã nguồn chương trình bên trong tập tin lưu trữ.

2.1

Một số tập tin lưu trữ phổ biến

2.1.1

ZIP

Zip[6, 7] là một định dạng tập tin lưu trữ phổ biến. Định dạng này được
thiết kế để trao đổi dữ liệu đa nền tảng và lưu trữ dữ liệu hiệu quả cho một
tập hợp các tệp liên quan. Định dạng này hiện tại là một định dạng tiêu chuẩn
được sử dụng rộng rãi, kể cả trong công nghiệp. Định dạng này được PKWARE
duy trì và phát triển, các tài liệu mơ tả của định dạng được công bố công khai.
Định dạng này ban đầu được tạo vào năm 1989 và lần đầu tiên được triển khai
trong tiện ích PKZIP của PKWARE với mục tiêu thay thế cho định dạng nén
ARC xuất hiện trước đó. Định dạng này sau đó nhanh chóng được hỗ trợ bởi
3



nhiều phần mềm tiện ích khác ngồi PKZIP, một số ví dụ đáng kể có thể nêu
ra là việc Microsoft đã tích hợp khả năng đọc và tạo tập tin lưu trữ ZIP (dưới
tên "thư mục nén") trong các phiên bản của Microsoft Windows kể từ năm 2000.
Apple đã tích hợp hỗ trợ định dạng tập tin lưu trữ ZIP kể từ phiên bản Mac
OS X 10.3 và mới hơn (thơng qua tiện ích mà bây giờ được biết đến với tên gọi
Công cụ lưu trữ). Hầu hết các hệ điều hành miễn phí đều được tích hợp sẵn hỗ
trợ đọc và ghi tập tin lưu trữ định dạng ZIP theo cách tương tự như Windows
và Mac OS X. Qua nhiều năm, định dạng này đã được PKWARE mở rộng để
thích ứng với kỳ vọng mới của người dùng và thay đổi công nghệ, chẳng hạn
như cho phép các phương pháp cải tiến để nén và mã hóa, để hỗ trợ kích thước
tệp lớn hơn và để hỗ trợ UNICODE UTF-8 cho tên tệp. Định dạng này vẫn
được sử dụng phổ biến ở thời điểm hiện tại, cũng như vẫn được cập nhật các
tính năng mới để phù hợp hơn. Phiên bản mới nhất cho đến thời điểm hiện tại
là phiên bản 6.3.9, ra mắt vào tháng 7 năm 2020, 31 năm sau khi ra mắt.
ZIP là sự kết hợp của khả năng nén dữ liệu, quản lý tệp và mã hóa dữ liệu
trong một định dạng lưu trữ di động. Tệp tin ZIP là một dạng tập tin đóng gói
có chứa một hoặc nhiều tệp, thường được nén và đơi khi được mã hóa. Định
dạng ZIP sử dụng các "chữ ký"với độ dài 4 byte cụ thể để biểu thị các cấu trúc
khác nhau trong tệp. Mỗi mục nhập tệp được đánh dấu bằng một chữ ký cụ thể.
Phần cuối của bản ghi thư mục trung tâm được chỉ định bằng chữ ký cụ thể
của nó và mỗi mục nhập trong thư mục trung tâm bắt đầu bằng chữ ký tiêu đề
tệp trung tâm 4 byte. Cấu trúc cơ bản bao gồm một chuỗi các phần bao gồm
"tiêu đề tệp cục bộ", mỗi phần này được đánh dấu bằng một chữ ký cụ thể, một
đoạn thông tin mô tả về tên, kích thước, thuật tốn nén cũng như mã hóa được
sử dụng, tiếp đến là dữ liệu tệp (sau khi nén và/hoặc mã hóa). Ở cuối tập tin
là một đoạn được gọi là "thư mục trung tâm", thành phần này liệt kê các tệp
trong gói cùng với các thơng tin mô tả cơ bản cũng như các thông tin bổ sung
để hỗ trợ trích xuất và giải mã tập tin đã được đóng gói bên trong tập tin ZIP.
Điều này cho phép một danh sách tệp của kho lưu trữ được thực hiện tương
đối nhanh chóng, vì tồn bộ kho lưu trữ không cần phải đọc để xem danh sách

tệp. Vì các tệp ZIP có thể được nối vào, chỉ các tệp được chỉ định trong thư
mục trung tâm ở cuối tệp mới hợp lệ. Việc quét tệp ZIP cho tiêu đề tệp cục

4


bộ là không hợp lệ (ngoại trừ trường hợp tệp lưu trữ bị hỏng thư mục trung
tâm), vì thư mục trung tâm có thể thơng báo rằng một số tệp đã bị xóa và các
tệp khác đã được cập nhật. Thứ tự của các mục tệp trong thư mục trung tâm
không được trùng với thứ tự của các mục tệp trong kho lưu trữ.
Mặc dù đặc tả định dạng tệp tin ZIP ghi lại nhiều phương pháp nén dữ liệu
như Lưu trữ (không nén), Deflate/Deflate64, bzip2, LZMA và PPMd, trong thực
tế, phương pháp nén được sử dụng phổ biến nhất (và là phương pháp nén duy
nhất được định nghĩa trong các văn bản tiêu chuẩn quốc tế) là Deflate/Deflate64,
được mô tả trong IETF RFC 1951.
ZIP hỗ trợ một hệ thống mã hóa đối xứng dựa trên mật khẩu đơn giản
thường được gọi là ZipCrypto. ZipCrypto đã được chứng minh là khơng an tồn,

Hình 2.1: Cấu trúc tập tin ZIP

5


đặc biệt thuật tốn mã hóa này dễ bị tấn cơng bằng phương thức bản rõ. Các
thuật tốn mã hóa mới đã được bổ sung trong các bản cập nhật của đặc tả định
dạng tệp ZIP kể từ phiên bản 5.2, như thuật tốn mã hóa mở AES. Mặc dù vậy,
WinZip sử dụng một thuật toán tự phát triển "AE-x", thuật toán này cũng được
hỗ trợ bởi 7-Zip, nhưng một số nhà cung cấp sử dụng các định dạng khác. Hầu
hết các công cụ hỗ trợ tập tin ZIP đi kèm trong các hệ điều hành như Thư mục
nén của Windows hay Công cụ lưu trữ trên Mac OS đều chỉ hỗ trợ thuật tốn

mã hóa ZipCrypto mà khơng hỗ trợ các thuật tốn mã hóa AES, khiến cho việc
sử dụng các thuật tốn mã hóa tốt trên tập tin ZIP gặp rất nhiều khó khăn.
Mã hóa tên tệp được cơng bố trong đặc tả phiên bản 6.2, mã hóa siêu dữ
liệu được lưu trữ trong phần Thư mục trung tâm của kho lưu trữ, nhưng các
phần Tiêu đề cục bộ vẫn chưa được mã hóa. Các trình lưu trữ tuân thủ đặc tả
này có thể làm sai lệch dữ liệu Tiêu đề cục bộ khi sử dụng Mã hóa thư mục
trung tâm. Tuy nhiên, các trường thông tin về Phương pháp nén và Kích thước
nén trong Tiêu đề cục bộ khơng bị mã hóa.

2.1.2

TAR

Tệp TAR[9] là một kho lưu trữ được tạo bởi tar, một tiện ích xuất hiện lần
đầu trên hệ điều hành Unix vào năm 1979. Tệp TAR được sử dụng để đóng gói
các tệp lại với nhau cho mục đích sao lưu hoặc phân phối. Nó chứa nhiều tệp
được lưu trữ nguyên trạng cùng với siêu dữ liệu về kho lưu trữ. Do không hỗ trợ
nén dữ liệu hay mã hóa, các tệp TAR thường được nén hoặc/và mã hóa bởi các
cơng cụ khác, phổ biến có thể kể đến việc sử dụng các cơng cụ nén gzip/bzip2/xz
để nén tập tin TAR tạo thành TAR.GZ (TGZ), TAR.BZ (TBZ) hoặc TAR.XZ
(TXZ) tương ứng.
Định dạng TAR được giới thiệu cùng với tiện ích tar vào năm 1979 để ghi
dữ liệu vào ổ băng, đây là thiết bị lưu trữ dữ liệu sẽ đọc và ghi dữ liệu trên băng
từ. Tên TAR bắt nguồn từ “Tape ARchive” hay “Định dạng lưu trữ trên băng
từ”, vì ban đầu nó được phát triển để ghi dữ liệu vào các thiết bị đọc ghi tuần
tự khơng có hệ thống tệp của riêng chúng, phổ biến nhất là băng từ. Ở thời
điểm hiện tại, định dạng TAR vẫn được sử dụng phổ biến trên các hệ thống

6



Unix và Linux để đóng gói nhiều tệp tin thành một tệp TAR duy nhất, đó cũng
là lý do mà các tệp TAR thường được gọi là “tarball”.
Các tarball thường được sử dụng cho việc đóng gói và vận chuyển nhiều
tệp đến một vị trí khác, ví dụ như gửi chúng qua email chẳng hạn. Ngoài ra,
nhờ vào việc lưu trữ đầy đủ các thông số hệ thống tệp khác nhau, chẳng hạn
như tên, các mốc thời gian tạo mới/đọc lần cuối/sửa đổi lần cuối, quyền sở hữu,
quyền truy cập tệp và tổ chức thư mục cho các hệ thống tổ chức tập tin được
sử dụng trên các hệ điều hành Unix/Linux, tập tin TAR đặc biệt hữu ích trong
việc đóng gói ứng dụng cũng như sao lưu các hệ thống chạy các hệ điều hành
này.
Một tập tin lưu trữ TAR bao gồm một loạt các đối tượng tệp, mỗi đối

Hình 2.2: Cấu trúc tập tin TAR
7


tượng tệp bao gồm một bản ghi tiêu đề với độ dài 512 byte, theo sau là dữ liệu
của tệp tin được đóng gói. Dữ liệu tệp này được ghi ngun trạng ngoại trừ độ
dài của nó được làm trịn lên bội số 512 byte, phần khoảng trống thừa dư ra sẽ
được lấp đầy bằng các ký tự null. Phần cuối của kho lưu trữ được đánh dấu
bằng ít nhất hai bản ghi không điền liên tiếp. Nguồn gốc của kích thước bản
ghi của TAR là các sector đĩa 512 byte được sử dụng trong hệ thống tệp Unix.
Khối cuối cùng của kho lưu trữ được đệm bằng các số không. Nhờ vào cách tổ
chức dữ liệu này, tập tin TAR có khả năng thêm tập tin vào cuối của nó mà
khơng cần phải dựng lại tồn bộ tập tin lưu trữ.

2.1.3

RAR


RAR[10, 11] là định dạng tệp tin lưu trữ độc quyền hỗ trợ nén dữ liệu, khôi
phục lỗi và mở rộng tệp. Cái tên RAR bắt nguồn từ viết tắt của Roshal ARchive,
đây là một định dạng tệp độc quyền được tạo ra bởi Eugene Roshal vào năm
1995, một kỹ sư phần mềm người Nga. RAR là một định dạng độc quyền, cùng
với các ứng dụng nén và thư viện của RAR cho Alexander Roshal, anh trai của
Eugene Roshal. Tệp RAR là định dạng gốc cho phần mềm WinRAR và chỉ có
thể được tạo thơng qua cơng cụ này, mặc dù có một số tùy chọn để mở tệp RAR
do mã nguồn của công cụ đọc tệp tin RAR đã được cơng bố (mặc dù khơng
hồn tồn miễn phí). Có ít nhất sáu phiên bản chính và phiên bản phụ của định
dạng RAR khác nhau, nhưng được sử dụng phổ biến nhất là RAR4 và RAR5.
Tương tự như các tệp tin ZIP, tệp tin lưu trữ RAR là các vùng chứa dữ
liệu trong đó một hoặc nhiều tệp được lưu trữ ở dạng nén. Về mặt cấu trúc, tệp
RAR bao gồm các khối có độ dài thay đổi của dữ liệu bắt buộc và tùy chọn. Về
cốt lõi, tệp RAR bao gồm khối đánh dấu hoặc khối giới thiệu, khối lưu trữ bao
gồm tiêu đề tệp lưu trữ và tiêu đề tệp và khối đóng bao gồm các nhận xét bổ
sung hoặc thông tin khác cần thiết để xử lý tệp một cách chính xác. Thứ tự
của các khối này có thể khác nhau, nhưng khối đầu tiên phải là khối đánh dấu,
theo sau là khối tiêu đề.Các khối tiêu đề có độ phức tạp cao vì nó chứa các tiêu
đề cho chính tệp lưu trữ cũng như các tiêu đề tệp tin đang được lưu trữ. Khối
tiêu đề chính có chứa một số các cài đặt của tệp tin lưu trữ, một trong số đó là
thẻ Định vị tùy chọn để nhanh chóng truy cập vị trí của các khối dịch vụ khác
8


nhau mà khơng cần qt tồn bộ kho lưu trữ. Sau tiêu đề chính nhưng vẫn nằm
trong khối lưu trữ có một hoặc nhiều tiêu đề tệp tin, mỗi tiêu đề tương ứng với
một tệp tin được chứa trong tệp tin lưu trữ. Các tiêu đề tệp được theo sau bởi
các tiêu đề Dịch vụ tùy chọn. Dấu kết thúc lưu trữ theo sau Tiêu đề tệp cuối
cùng để đóng khối lưu trữ, sau tiêu đề đóng này các dữ liệu không được định

nghĩa, điều này cho phép các công cụ của bên thứ ba thêm các thông tin bổ
sung như chữ ký điện tử cho tập tin lưu trữ chẳng hạn.
RAR hỗ trợ mã hóa AES tùy chọn, một loại mật mã khối sử dụng thuật
tốn mã hóa dữ liệu trên cơ sở mỗi khối. Có nhiều dạng khác nhau của tiêu
chuẩn AES và việc triển khai được RAR sử dụng đã thay đổi theo các phiên
bản khác nhau của định dạng. RAR5 sử dụng AES-256, thay cho AES-128 được
sử dụng trong RAR4.
Có một số phần mềm ứng dụng có sẵn cho Windows, Linux và MacOS để
đọc và trích xuất các tệp RAR. Phần mềm WinRAR, của RARLab, là tiện ích
lưu trữ tệp phần mềm chia sẻ (miễn phí trong 40 ngày) cho nền tảng Microsoft
Windows; phần mềm đã được chuyển sang Linux (chỉ dưới dạng trình giải nén)
bởi cùng tác giả, Eugene Roshal.

2.1.4

7z

7z[12] là một định dạng tệp lưu trữ hỗ trợ một số thuật toán nén, mã hóa
và tiền xử lý dữ liệu khác nhau. Định dạng 7z ban đầu xuất hiện như được triển
khai bởi trình lưu trữ 7-Zip, đặc tả định dạng tệp 7z được phân phối cùng với
mã nguồn của 7-Zip. Định dạng 7z cung cấp nhiều tính năng khác biệt với các
định dạng tệp lưu trữ khác. Kiến trúc mô-đun mở của 7z cho phép sử dụng
nhiều lớp thuật toán tiền xử lý, nén hay mã hóa dữ liệu cùng nhau để đạt được
hiệu ứng mong muốn.
Cấu trúc dữ liệu của định dạng 7z bao gồm 4 khối dữ liệu chính, khối tiêu
đề mở đầu, khối dữ liệu đóng gói, khối thơng tin về các tệp tin được đóng gói,
và cuối cùng là khối kết thúc. Trong các khối này, khối tiêu đề mở đầu và khối
kết thúc là hai khối đơn giản vì chúng chỉ được sử dụng như những đánh dấu.
Khối tiêu đề mở đầu chứa chữ ký của định dạng và một con trỏ đến khối kết
9



thúc. Tương tự, khối kết thúc chỉ chứa một con trỏ đến khối thơng tin các tệp
được đóng gói. Khối thơng tin các tệp được đóng gói chứa đầy đủ các thơng tin
về các tệp được đóng gói như tên tệp tin, kích thước, các dấu thời gian của tệp
tin và mã băm CRC để kiểm tra toàn vẹn dữ liệu. Ngồi ra, chúng cịn chứa các
thơng tin để có thể đọc và giải nén tệp tin đó như con trỏ đến khối dữ liệu nén
cũng như các thuật toán nén đã được áp dụng lên khối dữ liệu nén đó.
Do định dạng 7z khơng lưu trữ các quyền của hệ thống tệp (trên các hệ
thống lưu trữ tệp có phân quyền), định dạng này khơng thích hợp cho các mục
đích sao lưu hệ thống. Định dạng 7z cũng khơng cho phép trích xuất một "tệp
bị hỏng"do mất mát dữ liệu, ví dụ điển hình là khi chỉ một phần tập tin 7z
được khơi phục cũng khó có thể xác định được các luồng dữ liệu do các bản ghi
thông tin về các thuật toán để mở các luồng dữ liệu này có thể khơng hiện hữu.
Tương tự ZIP, định dạng 7z cũng thiếu các bản ghi khôi phục, khiến nó dễ bị
suy giảm dữ liệu trừ khi được sử dụng cùng với các giải pháp bên ngoài, như
một hệ thống lưu trữ tệp có khả năng sửa lỗi mạnh mẽ.
Định dạng 7z hỗ trợ mã hóa bằng thuật tốn AES với khóa 256-bit. Khóa
được tạo từ cụm mật khẩu do người dùng cung cấp bằng cách sử dụng thuật
toán dựa trên hàm băm SHA-256. Định dạng 7z cũng cung cấp tùy chọn mã
hóa tên tệp của kho lưu trữ 7z, khiến cho các thông tin về các tệp đã được đóng
gói trong tệp 7z khơng thể được đọc khi khơng có mật khẩu. Ngồi ra, kiến trúc
mở của định dạng 7z cho phép việc mở rộng và bổ sung thêm các thuật tốn
nén hay mã hóa bổ sung trong tương lai vào tiêu chuẩn mà không phải sửa đổi
định dạng tập tin.

2.2

Các thuật toán xử lý dữ liệu trong tập tin
lưu trữ

Có ba loại thuật tốn xử lý dữ liệu chính: Nén dữ liệu, mã hố dữ liệu và

sửa lỗi dữ liệu. Một đặc điểm đáng chú ý của một số thuật toán xử lý dữ liệu
này là mặc dù có thể được mơ tả hồn tồn bằng các lệnh đơn vị cơ bản trong
các ngơn ngữ lập trình, việc có hỗ trợ các phép tốn trên bit và hỗ trợ tính tốn

10


đơn lệnh đa dữ liệu (SIMD) có thể làm các cài đặt của các thuật tốn này có
tốc độ xử lý cao hơn nhiều trên các môi trường hỗ trợ chúng.

2.2.1

Các thuật toán nén dữ liệu

Các thuật toán phục vụ nén dữ liệu là một lớp các thuật tốn có thể được
áp dụng để chuyển đổi chuỗi bit của tệp tin đó thành một chuỗi bit khác ngắn
hơn, qua đó làm giảm kích thước của một tệp dữ liệu, nhưng vẫn đảm bảo có
thể khơi phục được (một phần hoặc tồn phần) thơng tin trong tệp tin ban đầu.
Có hai dạng nén dữ liệu là nén dữ liệu không mất mát và nén dữ liệu có mất
mát. Việc nén dữ liệu mà không làm tổn hao đến lượng thông tin ban đầu (tức
là có thể khơi phục tồn bộ tệp tin ban đầu thông qua giải nén dữ liệu) được gọi
là nén dữ liệu không mất mát. Ngược lại, nén dữ liệu có mất mát sử dụng cơ
chế loại bỏ các thơng tin khơng cần thiết hoặc ít quan trọng hơn để làm giảm
dung lượng của tệp tin. Ở trong phạm vi xem xét của tập tin lưu trữ đa dụng,
luận văn chỉ đề cập đến các thuật toán nén dữ liệu khơng mất mát.
Bài tốn nén dữ liệu là sự kết hợp của bài tốn mơ hình hóa và bài tốn
đánh mã, do đó, các thuật tốn nén dữ liệu được chia làm hai loại chính: các
thuật tốn đánh mã và các thuật tốn mơ hình hóa.

Đánh mã là việc gán các chuỗi bit thành các ký hiệu sao cho các chuỗi có
thể được giải mã một cách rõ ràng để khôi phục dữ liệu ban đầu. Một bản mã
tối ưu cho một ký hiệu với xác suất gặp là p sẽ có độ dài là log2 p1 bit. Một số
thuật tốn mã hóa hiệu quả đã được biết đến, có thể kể đến là thuật tốn đánh
mã Huffman[13], thuật toán đánh mã số học[14], thuật toán đánh mã nhị phân
khơng đối xứng[15].
Mơ hình hóa là việc ước tính về sự phân bố xác suất của dữ liệu đầu vào
cho một máy nén. Thuật tốn mơ hình hóa là thuật toán đưa ra dự đoán về sự
phân bố xác suất của ký hiệu tiếp theo với đầu vào là chuỗi các ký hiệu ngay
trước đó làm ngữ cảnh. Bài tốn mơ hình hóa là vấn đề khó trong q trình
nén dữ liệu, và khơng có phương pháp nào để xác định một mơ hình là tốt nhất,
điều này đã được chứng minh bởi Kolmogorov[16].
Một mơ hình có thể được phân loại là mơ hình tĩnh hoặc mơ hình thích
11


ứng, tùy vào cách xây dựng mơ hình trong q trình nén dữ liệu. Một mơ hình
tĩnh được xây dựng bằng cách phân tích dữ liệu đầu vào và tính tốn phân phối
xác suất cho các ký hiệu của nó, và để đảm bảo có thể giải mã được dữ liệu
sau khi đã đánh mã theo mơ hình được xây dựng, trình giải nén cần phải có cả
thơng tin để xây dựng lại mơ hình này. Một mơ hình động được xây dựng bằng
cách dựa vào các dữ liệu đầu vào trong quá khứ để đưa ra dự đoán về ký hiệu
tiếp theo, điều này khiến cho mơ hình có thể được phục dựng trong q trình
giải mã mà khơng cần thêm bất kỳ thông tin nào ngoại trừ dữ liệu đã được giải
mã.

2.2.2

Các thuật tốn mã hóa dữ liệu


Mã hóa dữ liệu là q trình chuyển đổi biểu diễn ban đầu của thông tin,
được gọi là bản rõ, thành một dạng thay thế được gọi là bản mã dựa trên một
hoặc nhiều đoạn thơng tin gọi là khóa, với mục tiêu lý tưởng là đảm bảo rằng
chỉ có thể giải mã và truy cập được thông tin ban đầu khi sử dụng khóa phù
hợp. Trong thực tế, các thuật tốn mã hóa dữ liệu được thiết kế để việc giải mã
khi có khóa là khơng phức tạp, nhưng việc giải mã mà khơng có khóa, mặc dù
trên lý thuyết là có thể, thường tốn rất nhiều tài ngun tính tốn và khơng
khả thi trên thực tế. Do sức mạnh tính tốn của máy tính liên tục tăng lên, các
thuật tốn mã hóa dữ liệu cũng khơng ngừng phát triển để chống lại việc bị giải
mã khơng cần khóa.
Có hai loại mã hóa chính tương ứng với hai loại khóa mà chúng sử dụng:
mã hóa sử dụng khóa đối xứng và mã hóa sử dụng khóa cơng khai (cịn được
gọi là khóa bất đối xứng).
Trong mã hóa với khóa đối xứng, khóa mã hóa và khóa giải mã giống nhau;
thuật tốn giải mã đơn giản thường chính là đảo ngược của thuật tốn mã hóa.
Một số thuật tốn mã hóa đối xứng thường được sử dụng là AES, DES/3DES,
IDEA, Blowfish, Twofish/Threefish, RC4/RC5/RC6; trong đó thuật tốn được
sử dụng phổ biến nhất là thuật tốn mã hóa đối xứng AES với độ dài khóa 256
bit.
Ngược lại, trong mã hóa với khóa cơng khai, khóa sử dụng để mã hóa và

12


khóa sử dụng để giải mã là hai khóa khác nhau, sử dụng cùng nhau trong q
trình sử dụng. Thơng thường, khóa mã hóa sẽ được cơng khai để người gửi có
thể mã hóa thơng tin, và khóa giải mã sẽ được người nhận giữ bí mật để đảm
bảo chỉ người nhận có thể giải mã và đọc được các thơng tin từ người gửi. Trong
các thuật tốn mã hóa bất đối xứng, thuật tốn RSA với độ dài khóa là 4096
bit thường được sử dụng.


2.2.3

Các thuật toán phát hiện và sửa lỗi dữ liệu

Phát hiện và sửa lỗi dữ liệu là một lớp các kỹ thuật và thuật toán để đảm
bảo tính tồn vẹn của dữ liệu, nhất là khi dữ liệu được lưu trữ hoặc truyền tải
qua các môi trường không đảm bảo hoặc không đáng tin cậy. Trong thực tế,
việc lưu trữ hoặc truyền tải thông tin ln có khả năng phát sinh những sai lệch
do yếu tố mơi trường. Các thuật tốn phát hiện lỗi cho phép phát hiện những
sai lệch này, cịn các thuật tốn sửa lỗi cho phép xây dựng lại dữ liệu ban đầu
dựa vào trong nhiều trường hợp.
Việc phát hiện lỗi thông thường được thực hiện bằng cách sử dụng một
thuật toán băm dữ liệu phù hợp với tính chất của lỗi cần phát hiện. Khi sử
dụng hàm băm, dữ liệu ban đầu sẽ được đính kèm một giá trị băm có độ dài cố
định trước khi được lưu trữ hoặc truyền tải. Dựa vào việc tính tốn lại giá trị
băm trên dữ liệu nhận được thực tế và so sánh với giá trị băm đi kèm trong dữ
liệu nhận được, người nhận có thể xác định dữ liệu nhận được có lỗi hay không
(với một độ chắc chắn nhất định). Các thuật toán băm dữ liệu thường được sử
dụng là các thuật tốn băm mật mã như MD5 hay SHA1/SHA2/SHA3. Ngồi
ra, một số thuật tốn sửa lỗi dữ liệu cũng có khả năng phát hiện lỗi, vì vậy đơi
khi khơng cần sử dụng một thuật toán phát hiện lỗi riêng biệt trong q trình
lưu trữ hay truyền tải thơng tin.
Các thuật toán sửa lỗi dữ liệu thường được sử dụng trong lưu trữ và truyền
dữ liệu là thuật toán sửa lỗi dữ liệu chuyển tiếp. Thuật toán này thêm một
lượng dữ liệu dư thừa (như mã sửa lỗi chẳng hạn) vào dữ liệu ban đầu, hoặc
biến đổi dữ liệu đầu vào thành một đoạn dữ liệu mới lớn hơn và có khả năng
chịu được lỗi trước khi lưu trữ hay truyền tải. Người nhận đoạn dữ liệu đã biến

13



đổi có thể khơi phục được dữ liệu ban đầu ngay cả khi có một số lỗi trong q
trình lưu trữ hay truyền tải tùy thuộc vào khả năng chịu lỗi của thuật tốn.
Trong thực tế, ngồi các ứng dụng trong phát sóng hay giao tiếp tầng thấp, các
thuật tốn sửa dữ liệu chuyển tiếp còn được sử dụng ở trong lưu trữ dữ liệu
trên các phương tiện lưu trữ như CD, DVD, các thiết bị nhớ di động, thậm chí
cả trên HDD, SSD và RAM. Do các phương tiện lưu trữ ngày càng hiện đại và
có độ tin cậy ngày càng cao, có khá ít các ứng dụng của thuật tốn sửa lỗi dữ
liệu cịn được sử dụng trong việc lưu trữ dữ liệu, một ứng dụng điển hình có thể
kể đến là phân vùng khơi phục trong định dạng tập tin lưu trữ RAR cho phép
khôi phục và trích xuất dữ liệu ngay cả khi tập tin lưu trữ bị lỗi.

2.3

Máy ảo thực thi
Một máy ảo nói chung là sự ảo hóa hoặc mơ phỏng của một hệ thống máy

tính. Máy ảo được thiết kế dựa trên kiến trúc máy tính và cung cấp chức năng
của một máy tính vật lý. Có hai loại máy ảo khác nhau về chức năng của chúng,
đó là máy ảo hệ thống và máy ảo thực thi. Máy ảo hệ thống hay máy ảo tồn
phần là một máy ảo mơ phỏng một hệ thống vật lý ở mức thấp, một máy ảo
toàn phần cung cấp đầy đủ các chức năng để có thể thực thi một hệ điều hành
phù hợp với phần cứng mà nó mơ phỏng.
Máy ảo thực thi, hay cịn được gọi là máy ảo tiến trình, là các máy ảo được
thiết kế để thực thi các chương trình máy tính trong một mơi trường độc lập
với nền tảng phần cứng hay hệ điều hành mà nó thực thi trên. Máy ảo thực thi
khởi chạy như một ứng dụng bình thường bên trong hệ điều hành chủ của nó,
máy ảo này khơng chỉ cung cấp một mơi trường lập trình độc lập với phần cứng
hay hệ điều hành của máy chủ, ngồi ra máy ảo thực thi cịn trừu tượng hóa

các chi tiết của phần cứng hoặc hệ điều hành bên dưới, cho phép một chương
trình thực thi theo cùng một cách trên bất kỳ nền tảng nào.

14


Tiểu kết Chương 2
Chương 2 của luận văn đã khảo sát sơ lược về các tập tin lưu trữ và trình
bày các kiến thức cơ sở về các thuật tốn thường được sử dụng trong tập tin lưu
trữ. Chương này cũng đã trình bày sơ lược về định nghĩa máy ảo thực thi và
khảo sát một số các máy ảo thực thi của các ngôn ngữ phổ biến. Trong chương
tiếp theo, luận văn sẽ sử dụng những thông tin khảo sát cùng với kiến thức đã
được trình bày để đưa ra một ngơn ngữ mới phị hợp với mục đích mơ tả các
thuật tốn sử dụng trong tập tin lưu trữ.

15


Chương 3

Ngơn ngữ lập trình mới
Trong Chương 2, luận văn đã khảo sát về các định dạng tập tin lưu trữ
phổ biến, các thuật tốn thơng dụng trong tập tin lưu trữ cũng như khảo sát
một số ngôn ngữ sử dụng máy ảo thực thi thông dụng. Trong chương này, luận
văn đưa ra các ràng buộc thiết kế và mô tả về ngơn ngữ lập trình được đề xuất.

3.1

Xây dựng yêu cầu và ràng buộc thiết kế
của ngôn ngữ lập trình


3.1.1

Sự cần thiết và yêu cầu của định dạng mới

Hiện tại có rất nhiều các định dạng tập tin lưu trữ đang tồn tại, nhưng chỉ
một số ít trong số chúng được sử dụng rộng rãi như một định dạng tiêu chuẩn.
Một trong những nguyên nhân dẫn đến thực tế này là do việc sử dụng nhiều
loại tập tin lưu trữ khác nhau sẽ gây ra nhiều khó khăn trong quá trình trao
đổi tập tin lưu trữ, như việc đảm bảo cả hai phía gửi và nhận cần có một trình
đóng gói và trình đọc tương thích với định dạng tập tin lưu trữ đã gửi. Việc sử
dụng một (hoặc một vài) định dạng tập tin lưu trữ phổ biến và được hỗ trợ
rộng rãi có thể làm giảm được độ phức tạp cho người gửi và người nhận khi
thao tác với tập tin lưu trữ, làm giảm thời gian truyền và nhận thơng tin của cả
hai phía. Ngồi ra, người gửi khi đóng gói và gửi tập tin lưu trữ dưới một định
dạng tiêu chuẩn thì có thể phần nào đảm bảo người nhận có sẵn cơng cụ để mở
16