6502轻量级压缩算法

Question

6502轻量级压缩算法

11

我正在为我编写的Forth在Commodore PET上实现虚拟内存，使用双卡带机，并计划使用PET本地的192字节卡带数据文件格式。由于只有32K的RAM可用于“一切”，因此我在语言中嵌入了Woz的优秀且非常节省内存的Sweet-16解释器。一个Forth块（通常）是1024字节。将块ID的两个字节添加到其中，可将可用的虚拟地址空间限制在64兆以上，远远超出磁带的容量。其中一个设备为“播放”卡带机（设备1），另一个为“记录”卡带机（设备2），FLUSH将涉及将整个虚拟内存从一个驱动器复制到另一个驱动器。为什么要这样做？因为在过去，大多数PET机主都只有卡带机。如果您感兴趣，可以在http://github.com/chitselb/pettil找到我目前的进展。

大部分数据将是 Forth 代码的屏幕，该实现中将是 1000 字节的文本和一个 24 字节的换行表，因为我也利用了 PET ROM 屏幕编辑器。我想要的是任何可能会击败简单的行程长度编码，但没有像 Lempel-Ziv 这样复杂的 CPU 和内存开销的建议。感谢除“忘掉它”之外的所有建议。

- chitselb

你可以看一下Huffman编码. - Aadit M Shah

我只使用了https://code.google.com/p/lzfx/进行解压缩，但我认为您仍然会使用大部分/全部32K，因此它可能不够轻量级。但是，如果您看一下概念而不是实现，它是具有某些优化的运行长度编码。如果该字符串最近已经出现过，而不是一堆a字节，一个b字节，一个c字节，那么从地址current-X复制N个字节就是一条指令。 - old_timer

在StackOverflow上有一个关于轻量级嵌入式压缩的问题和答案，其中提供了其他看起来不错的建议。 - old_timer

@dwelch：你是指这个吗？ - Seki

1

如果您有许多重复序列的字符串，可以使用编码字与字典查找。它易于实现，快速，并且对于各种文本（如果确实包含各种常见字符串序列）效果很好。其思想是查看数据并了解冗余之处，从而利用它。Lempel-Ziv很“重”，因为它旨在在各种数据类型中表现良好。在这种情况下，您可能能够利用非常特定的数据类型。 - lurker

Forth 是如何处理的？在我看来，你可以存储 Forth 字典，并通过引用它来定义非注释文本 - 就像大多数微型计算机以记号化形式将其 BASIC 存储到磁带中一样。 - Tommy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AshleyF · Accepted Answer

如果您最担心的是Forth源代码，您可以将字符集限制为Chuck Moore为colorForth选择的48个字符，并使用他的Shannon编码方案，平均每个字符占用5.2位。他还声称，colorForth源代码的大小仅约为目标代码的两倍。顺便说一句，在arrayForth中，字符集似乎略有不同（请参见用户手册第47页-数字的顺序不同，撇号代替冒号等）。

当然，使用Shannon编码并不一定与彩色单词有关。如果您想一路走到底，像colorForth一样存储预解析的单词，您可以使用他在这里提供的方案。

他没有提供太多细节，但对于etherForth，他放弃了Shannon编码，并选择了一个简单的6位编码来表示相同的字符集，其中11xxxx还额外指示了一个16位标签，他用于颜色和标记，包括F18指令和一些汇编原语（begin、end、then、for）。这是一个非常棒的方案（特别是在有3个字每个词的18位F18上），非常简单而且相当紧凑。

总之，这里有一些想法。虽然不是对你的压缩问题的直接回答，但这是一些以压缩形式存储Forth源代码的方法。祝玩得开心！