LZW 壓縮

LZW 是一種 lossless dictionary-based compression，用於 GIF、TIFF、UNIX Compress、PDF 檔等。

• Dictionary is dynamically constructed in the compression and decompress process, so it does not have to be transmitted.
• This compression technique is capable of achieving respectable compression ratios, typically on the order of 50 ~ 60%, while consuming about 2K of RAM. In larger RAM memory sizes, 8K or 16K, it is possible to achieve 80% efficiency or more.

參考文獻

1. Wikipedia: LZW (中)
2. Lossless Data Compression for Embedded Systems

mmap @ user space

參考：Linux程式設計-13.記憶體對映mmap 或 GNU libc manual 13.7 Memory-mapped I/O
mmap() 將檔案當成記憶體使用，將 file 從 offset 開始、長度 length 的區塊映射到 user virtual memory 供存取。

#include
void * mmap(void *start, size_t length, int prot , int flags, int fd, off_t offset);
int munmap(void *start, size_t length);

• start：user 想要的位置，通常可不指定
• prot: protection mode (read/write/exec/none)
• flags:
  
• MAP_PRIVATE: 另外取得自用的記憶體區塊，寫入只寫到自用的記憶體區塊，不會寫回檔案。
• MAP_SHARED: 使用共用的記憶體區塊得以立即共用包括修改的部份，會寫回檔案，但可能不會立即寫回。
• MAP_FIXED: mapped exactly at ADDR (must be page-aligned), otherwise a convenient nearby address is used.
• ...
  

int msync(const void *start, size_t length, int flags);
立即寫回檔案

參考：Zero Copy I: User-Mode Perspective
在某些情況下，mmap() 可以取代 read() 減少一次將資料複製到 user space 的動作。

參考：mmap Sample Code
實體記憶體也是檔案 /dev/mem，mmap() 可以讓 user space 存取實體記憶體，例如週邊的 registers，如此便可以在 user space 設定週邊。但在 user space 要將資料寫到 kernel space 會花些時間。

延伸閱讀

1. 在驅動程式，ioremap 將 physical address 映射到 virtual address。
2. remap_page_range()：待研究

讀 Zero Copy I: User-Mode Perspective

• 使用 read(file, tmp_buf, len) 及 write(socket, tmp_buf, len) 會有四次 user/kernel context switches 及四次資料複製：hard disk -> kernel buffer -> user buffer -> socket buffer -> NIC
• 使用 tmp_buf = mmap(file, len) 及 write(socket, tmp_buf, len) 可共用 kernel buffer 及 user buffer，可減少一次複製，但需要處理 write() 的時候，file 有變更造成的錯誤
• 使用 sendfile(socket, file, len) 複製次數一樣，但 user/kernel context switches 變為兩次
• 如果 NIC 支援 gather，sendfile(socket, file, len) 可再減少一次複製，不用複製到 socket buffer 就能將資料傳給 NIC
• 有沒有可能直接 hard disk 到 NIC 呢？