Quartz 🪬

File Allocation Table

4 min read

File Allocation Table (FAT) là một bảng chứa thông tin về trạng thái của các cluster trong vùng dữ liệu.

  • Thường thì mỗi phân vùng sẽ có hai FAT (một bản dự phòng).
  • FAT được tổ chức thành các entries theo mô hình danh sách liên kết (xem thêm File Allocation), mỗi entry cho biết trạng thái của khối dữ liệu (cluster) tương ứng. Một tập tin có thể nằm ở nhiều cluster, do đó nó có thể chiếm nhiều entry trong một FAT, tương ứng với nhiều khối dữ liệu trong vùng nhớ.
  • Tùy từng loại FAT khác nhau mà mỗi entry trong FAT sẽ có một kích thước nhất định. Ví dụ, mỗi entry của FAT16 sẽ có kích thước là 16 bits (2 bytes), của FAT32 là 32 bits (4 bytes).
  • Các entry của một FAT có chỉ số bắt đầu từ 0.

Bảng giá trị của các entry: ![[FAT entry values.webp| x-small]]

Các entry sẽ được lưu dưới dạng little endian. Tức là, nếu entry có giá trị là 0xF8FF, thì giá trị thực sự của nó sẽ là 0xFFF8.

Số lượng cluster của từng loại FAT:

  • FAT12: tối đa 4078 (0x2 - 0xFEF) clusters
  • FAT16: tối đa 65518 (0x2 - 0xFFEF) clusters
  • FAT32: nhiều hơn 65518 clusters

Entry Chain

Xét ví dụ sau:

Có thể thấy, cluster bắt đầu của tập tin TTin2.txt là cluster số 6. Khi tra trong FAT ở entry số 6 thì ta được giá trị là số 7, đây là giá trị của cluster tiếp theo. Tương tự, khi tra giá trị của cluster số 7 thì ta được cluster số 9. Ở cluster số 9, giá trị của entry là EOF, chuỗi các cluster kết thúc tại đây. Như vậy, tập tin TTin2.txt chiếm 3 cluster trong vùng dữ liệu, lần lượt là 6, 7 và 9.

Một ví dụ khác, xét FAT sau đây:

Có thể thấy, entry số 2 có giá trị là entry số 3, entry số 3 có giá trị là entry số 4. Tương tự, ta suy ra được chuỗi các cluster từ một entry đầu tiên. Riêng entry số 7 không có entry nào trỏ đến và đồng thời có giá trị là FFFF (giá trị EOF của FAT16), nên tập tin File3 chỉ chiếm duy nhất một cluster.

Entry of FAT12

Ta đã biết với FAT16/32 thì mỗi entry sẽ chiếm tương ứng 2 hoặc 4 bytes. Và do các giá trị trong FAT có đơn vị nhỏ nhất là 1 byte nên việc tìm giá trị của entry thứ k bất kỳ sẽ là chuyện đơn giản. Ta chỉ cần tìm giá trị của cụm 2 hoặc 4 bytes rồi đảo ngược giá trị (little endian) là xong.

Tuy nhiên, làm thế nào tìm được giá trị của entry thứ k theo FAT12?

Xét ví dụ sau:

Do mỗi entry chiếm 12 bit, tương đương với 1.5 byte, nên entry đó sẽ bắt đầu tại vị trí i = k * 1.5.

Đặt:

  • HSB1 và LSB1 lần lượt là 4 bit cao và 4 bit thấp của byte thứ i. Xem thêm về bit cao và bit thấp.
  • HSB2 và LSB2 lần lượt là 4 bit cao và 4 bit thấp của byte thứ i + 1. Nếu:
  • k chẵn:
    • Byte thứ i lấy toàn bộ byte.
    • Byte thứ i + 1 lấy 4 bit thấp (LSB2).
    • Kết hợp tạo thành giá trị: LSB2 - HSB1 - LSB1
  • k lẻ:
    • Byte thứ i lấy 4 bit cao (HSB1).
    • Byte thứ i + 1 lấy toàn bộ byte.
    • Kết hợp tạo thành giá trị: HSB2 - LSB2 - HSB1

Giả sử ta cần tìm giá trị cho entry thứ 3, là số lẻ. Ta tính được i = 3 * 1.5 = 4.5 ~ 4.

  • Byte thứ 4: 40
  • Byte thứ 5: 00
  • Giá trị của entry thứ 3 sẽ là: 004

Xét ví dụ khác, ta cần tìm giá trị cho entry thứ 6, là số chẵn. Ta tính được i = 6 * 1.5 = 9.

  • Byte thứ 9: AB
  • Byte thứ 10: CD
  • Giá trị của entry thứ 6 sẽ là: DAB

Backlinks