嵌入式系统中的内存压缩技术

项中，代替了四个地址指针。因此，一个1KB的通用块仅占用物理内存中的16字节，其压缩比率达到64：1。

压缩内存控制器中有一系列的寄存器用于监控物理内存使用。Sectors Used Register(SUR)向操作系统报告压缩内存的使用情况。The Sectors Used Threshold Registers,SUTHR和SUTLR，用于设置内存耗尽情况的中断入口点。SUTLR寄存器是PCI中断电路INTA的入口，而SUTHR寄存器是NMI中断的入口。当SUR超过了SUTLR的值，内存控制器产生一个中断，则操作系统采取措施来阻止内存消耗。

在实际地址到物理地址的转换中，一个有用的方法是快速页操作。它允许控制器仅修改CTT项的四个指针，从而将4KB的页面内容换出或清空。快速页操作通过将与4KB页面相关的CTT项全部修改通用行格式（即全为零），从而将这4KB页面的内容全部清空。同样，一对页面可以通过交换它们相关的CTT项的区域指针来交换页面内容。由于没有大量的数据移动发生，快速页面操作速度相当快。

压缩内存控制器的压缩/解压功能是基于LempelZiv算法来进行的，因此下一节将简单介绍一下该算法的思想。

3 内存压缩算法Lempel-Ziv

绝大多数的压缩算法，包括用得特别流行的Lempel-Ziv压缩算法家庭，都是基于对原子记录（Token）字符串的完全重复检测。这个算法虽然不是最好的算法，但是，Lempel-Ziv算法强调的是算法的简单与取得高压缩率的速率，因此它还是在内存压缩中得到了广泛的应用。

Lemple-Ziv算法（简称LZ）是编码时将一个位串分成词组，然后将数据流描述成一系列的对。每个对组成一个新的词组，它包含一个数字（前一个词组的标识）和一个位（被附加到前一个词组上）。这种编码方式很庞大，可是一旦应用到适合的字符串，它就是相当有效率的编码方式。下面举例说明这种算法是如何编码的。

++表示连接（010++1=0101），U=0010001101是未被压缩的字符串。C是压缩后的字符串。P（x）表示词组数x。先看一下U=0010001101发现，它可以被写为U=0++010001101，因此得到P（1）=P(0)++0。现在继续将其写为U=0++02++0001101，可得到P(2)=P（1）++1。现在我们已经将P（2）描述为上一词组和一个新的位的组合。下一步，U=0++01++00++01101，并得到P（3）=P（1）++0。现在我们注意到，有U=0++01+00+011++01，而P（4）=011=P(2)++1，最后得到P（5）=P(1)++1。运算的步骤如表1所列。

一旦创建了表1，就有了整个编码的图表。要创建Lempel-Ziv数据流，则依照公式创建对。如果公式是P(x)=P(A)++B，则每个对为（A++B）。因此P（1）=P(0)++0变为（00++0），P（2）=P(1)++0变为（01++0），依此类推，将所有这些对连接起来，就得到了最后的字符串，结果如表2所列。这样，C就变成000011010101011，看来比U要长得多。但这里由于U的长度短，因此未能看出优势，而且包含P（0）的公式都没有压缩，所以也引起了长度增加。

Lempel-Ziv字符串的解码是很简单的，就是抓住其中的对，对照表1进行重构。

表1 编码过程

步  骤 值 公  式

U

0 - P(0) 0010001101 1 0 P(1)=P(0)++0 0++010001101 2 01 P(2)=P(1)++1 0++01++00++01101 3 00 P(3)=P(1)++0 0++01++00++01101 4 011 P(4)=P(2)++1 0++01++00++011++01 5 01 P(5)=P(1)++1 0++01++00++011++01

表2 如何创建编码字符串

公  式 P(1)=P(0)++0 P(2)=P(1)++1 P(3)=P(1)++0 P(4)=P(2)++1 P(5)=P(1)++1

《嵌入式系统中的内存压缩技术(第2页)》