📄 compression.html
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//ZH_CN">
<!-- http://linux-ntfs.sourceforge.net/ntfs/concepts/compression.html -->
<html lang="zh_cn">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="description" content="NTFS Documentation">
<link rel="stylesheet" type="text/css" href="../style/ntfsdoc.css">
<link rel="start" type="text/html" href="../index.html" title="NTFS Documentation">
<title>Compression - Concept - NTFS Documentation</title>
</head>
<body>
<table border="0" class="toolbar" summary="" cellspacing="0">
<tr>
<td class="toolbar"><div class="toolbar"><a accesskey="1" class="toolbar" href="../index.html">主页</a></div></td> <td class="toolbar"><div class="toolbar"><a accesskey="2" class="toolbar" href="../files/index.html">文件</a></div></td> <td class="toolbar"><div class="toolbar"><a accesskey="3" class="toolbar" href="../attributes/index.html">属性</a></div></td> <td class="toolbar"><div class="toolbar"><a accesskey="4" class="toolbar" href="../concepts/index.html">概念</a></div></td> <td class="toolbar"><a accesskey="5" class="toolbar" href="../help/glossary.html">词汇</a></td>
</tr>
</table>
<h1>概念 - Compression</h1>
<a class="prevnext" accesskey="," href="collation.html">前一页</a>
<a class="prevnext" accesskey="." href="data_runs.html">后一页</a>
<h2>概述</h2>
<p>
这里有此机制的一个短小摘要：
用改进的LZ77运算法则进行压缩。以前看到的模块子串被压缩时参考串而不再提及它。
例如，考虑下面的纯文本：
</p>
<pre>
#include <ntfs.h>\n
#include <stdio.h>\n
</pre>
<p>
这是压缩到
#include <ntfs.h>\n
(-18,10)stdio(-17,4)
</p>
<p>
因此运算法则承认从当前位置开始的-18字节，它已经看到文本 '#include <'。
那么stdio是新的，但在这之前看到了'.h>\n'。
</p>
<p>
有趣的细节在哪？如何把数组(-18,10)编码？如何把它和纯文本串混合？
第一个要弄清的是：这样的数组记录在两个字节里。因为一个后向介绍占用了两个字节，
在后向介绍里没有一或两个字节的子串。这就意味着最短的子串是3，也就是说长度值0，
1，2是不可能的，所以在把它编码之前可以把长度减3；
同样，介绍总是后向的而且从不为0，所以可以把它们存储为正数并减一。
第一个后向介绍存为(17,7),第二个存为(16,1).
</p>
<p>
如果一个模块大小是4096，也许需要12比特来编码后向介绍。这意味着对于允许的最大19的长度，
只有四个比特用来编码长度。 把压缩比限制到1：19是不想要的。如果当前偏移量是123，
一个-512的后向介绍是不可能的。一些聪明的MS工程师决定动态分配更多的比特给后向介绍，
更少的比特给长度。准确的分裂写成一个表格或者象
</p>
<pre>
for(i=clear_pos-1,lmask=0xFFF,dshift=12;i>=0x10;i>>=1){
lmask >>= 1; /* bit mask for length */
dshift--; /* shift width for delta */
}
</pre>
<p>
现在可以把一个（偏移量，长度）数组编码为两个字节，我们还必须知道一个象征是后向介绍还是纯文本。
每个象征有一个比特。八个象征组在一起，在标签字节之前，所以这个群组
</p>
<pre>
>\n(18,10)stdio
</pre>
<p>
被编码为
</p>
<pre>
00000100 > \n 0A 90 s t d i o
</pre>
<p>
(1比特指示后向说明). 作为一个极端情况, 所有空格的模块 (' ') 被压缩为
</p>
<pre>
00000010 ' ' FC 0F
</pre>
<p>
或 ' ' (-1,4095). 这样操作是因为你总是读取刚存储的数据。
一个压缩单元由16个簇组成，它一般包含多于一个模块。
如果要访问第二个模块就得费时间解压缩第一个模块，每个模块前有一个2字节的长度，
低的12比特是长度，高的4比特用途未知。
</p>
<pre>
FIXME: 在属性标题里的压缩单元大小为2<sup>4</sup>
压缩方式基于独立压缩X个簇的模块，这里的X是从非常驻属性记录标题找到的压缩单元
值确定的(更精确为：X = 2^压缩单元簇数)。
在WINDOWS NT/2K上，X总为16簇（压缩单元＝4）。
1) 模块中数据全零（一个稀少模块）：
在运转列表里存储为一个稀少模块，例如，运转列表项长度＝X，LCN＝-1。映射数
组队列实际上使用一个长度为0的delta_lcn值，如delta_lcn根本不存在，由驱动
器翻译成LCN=1。
注意：即使在NTFS3.0卷上的未压缩文件可以是稀少的，也要应用上述的同一原则，
除非长度不受限可是任何特定的值。
2) 模块中的数据未压缩：
当压缩没有减少模块的簇数时会发生这种情况。如，压缩影响很小以至于压缩数据仍
然占用了X簇，那么未压缩数据就会存储在模块里。
这种情况成为事实时，运转列表项长度＝X，LCN >= 0。映射数组队列用运转长
度为0和一些特定的delta_lcn把它正常存储。必须存在delta_lcn。
3) 模块中的数据被压缩：
一般情况。当运转列表项长度 L < X 并且 lcn >= 0时，就是这种情况。
映射数组队列用运转长度X和一些特定delta_lcn把它正常存储，必须存在delta_lcn。
这个运转列表项后面紧跟一个长度＝X-L和lcn = -1的稀少项。后面的项用于补足VCN
来计算整个压缩模块大小X。
实际上，由于同一类型的邻近项可以接合，具体情况更复杂。这意味着必须保持对簇数的操作且
在X簇是一个模块的基础上。例如：如果长度L>X就意味着这个特殊的运转列表项包含一个长度
为X的模块和一个或更多模块的长度L-X部分。例如：如果长度L<X就不一定表示模块被压缩，
因为它可能是LCN在模块内部改变从而使跟着的运转列表项描述了潜在压缩模块的延长部分。如果
跟着的运转列表项描述了至少X-L个稀少簇则模块被压缩，压缩模块长度的组成如上面第3点所述。
（当然，这里也可能有几个小长度的运转列表项，因此稀少项不跟在包含长度<X的项的第一个
数据后面）。
注意：在压缩属性值的结尾，很可能不只是组成压缩模块的数据的正确数量，因此不要尝试去压缩
此数据，它只存储为is。
</pre>
<p>
如果你看了运算法则，就会注意到它并不总是减小数据的大小。如果没有模块说明，
模块字节的纯文本就会保持为is。但是每一个8字节在插入了一个标签比特后就会变为零。
所以最坏的情况是，一个模块可以增长到4610个字节（模块长度计算在内）。
如果模块增大就会以未压缩形式存储。一个长度为4095字节的模块就很能说明这种情况。
还有可能是把跟着的模块更好的压缩以减小这一大块的整体大小。如果不是这样，那么整个大块都会以未压缩的形式存储，这些在运转列表里有所说明。
</p>
<p>
每个模块都以一个2字节的长度开头，低12比特是长度，高4比特用途未知。
</p>
<p>
比特0x8000是指定模块压缩的标记，压缩码在0xB000（如果压缩），但是解压缩码只能在比特0x8000看到。
</p>
<p>
同样，长度实际上在低12比特存为（n－3），如果不计算用于存储自身长度的两个字节，实际上是（n-1）。
因此一个未压缩模块的长度存为0xFFF，就是说包括自身长度在内的长度为4096＋2。
</p>
<p>
一个长度为0x1000的模块压缩到长度为0x500，需要0x502字节，公示长度为0x4FF。
</p>
<p>
What I don't know is whether a 16 cluster file that doesn't compress
at all requires 17 clusters to store, in order to accommodate the extra
2 bytes per block.
</p>
<p>
I believe it will take only 16 clusters. The fact that it is not
compressed will be expressed in the run list. For example, the
compressed file will look like
</p>
<pre>
(1000 A) (0 6) //(rel.VCN length)
</pre>
<p>
whereas the uncompressable file will look like
</p>
<pre>
(1000 10)
</pre>
<p>
or
</p>
<pre>
(1000 A) (1040 6)
</pre>
<p>
IOW, if you don't have any runs with VCN==0 in the 16 clusters, the
chunk is entirely uncompressed and plain.
Given the compression algorithm, it is fairly easy to create such a
file:
</p>
<pre>
s=""
for i in range(0,16): #adjust to clusters >512 if necessary
s=s+chr(i)+chr(j)
open("uncompressable","w").write(s)
</pre>
<br>
<a class="contact" href="http://linux-ntfs.sourceforge.net/ntfs/concepts/compression.html">Online</a>
<a class="contact" href="http://www.reddragonfly.org/ntfs/concepts/compression.html">中文在线</a>
<!-- The two validators will only work if this page is visible on the web -->
<a class="contact" href="http://validator.w3.org/check/referer">Validate HTML</a>
<a class="contact" href="http://jigsaw.w3.org/css-validator/check/referer">Validate CSS</a>
<a class="contact" href="mailto:webmaster@flatcap.org">$Id: compression.html,v 1.8 2001/07/11 11:04:05 flatcap Exp $</a>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -