有关GIF数据的长度可变LZW算法

余烬之中

据说在这个区必须@，否则几个月也难被注意到
@晴兰 @fux2 @taroxd @喵呜喵5 @VIPArcher

最近突然想在RGSS中实现播放gif文件，大概的思路是新建类GIF读取文件并解压成一串Bitmap，然后添加Sprite对GIF的支持，后面这个应该没什么问题，只是在GIF压缩算法上还有点疑问

搞了两个下午，标准的LZW算法倒是已经实现了：Github，应该没有问题

对GIF的数据结构分析也完成了（大部分），只剩下图像数据块和文本数据块并没有进行Bitmap的建立（也就是难在这里了），目前的进度：Github

希望是纯ruby实现

相关资料,链接
[fold]

GIF数据压缩
下面是GIF文件的图象数据结构：

byte
    1       编码长度size                                              (LZW Code Size) LZW压缩的编码长度，也就是要压缩的数据的位数
  ……        数据块
   n          块大小         |=>    数据块（重复...）
n + 1  |=> 编码数据 | -----------------------
  ……    | ------------ | -----------------------
n + m | ------------ | -----------------------
  ……      数据块
size+1   块终结器                                                     标识一个图象的数据编码结束，固定值0

把光栅数据序列（数据流）压缩成GIF文件的图象数据（字符流）可以按下面的步骤进行：
1.定义编码长度
GIF图象数据的第一个字节就是编码长度(Code Size)，这个值是指要表现一个像素所需要的最小位数，通常就等于图象的色深；

2.压缩数据
  通过LZW压缩算法将图象的光栅数据流压缩成GIF的编码数据流。这里使用的LZW压缩算法是从标准的LZW压缩算法演变过来的，它们之间有如下的差别：

    [1]GIF文件定义了一个编码大小(Clear Code)，这个值等于2的『编码长度』次方，在从新开始一个编译表（编译表溢出）时均须输出该值，解码器遇到该值时意味着要从新初始化一个编译表；

    [2]在一个图象的编码数据结束之前（也就是在块终结器的前面），需要输出一个Clear Code+1的值，解码器在遇到该值时就意味着GIF文件的一个图象数据流的结束；

    [3]第一个可用到的编译表索引值是Clear Code+2（从0到Clear Code-1是根索引，再上去两个不可使用，新的索引从Clare Code+2开始添加）；

    [4]GIF输出的编码流是不定长的，每个编码的大小从Code Size + 1位到12位，编码的最大值就是4095（编译表需要定义的索引数就是4096），当编码所须的位数超过当前的位数时就把当前位数加1，这就需要在编码或解码时注意到编码长度的改变。

3.编译成字节序列
因为GIF输出的编码流是不定长的，这就需要把它们编译成固定的8-bit长度的字符流，编译顺序是从右往左。下面是一个具体例子：编译5位长度编码到8位字符

0        b        b        b        a        a        a        a        a
1        d        c        c        c        c        c        b        b
2        e        e        e        e        d        d        d        d
3        g        g        f        f        f        f        f        e
4        h        h        h        h        h        g        g        g
        ...
N                                                                        

打包
前面讲过，一个GIF的数据块的大小从0到255个字节，第一个字节是这个数据块的大小（字节数），这就需要将编译编后的码数据打包成一个或几个大小不大于255个字节的数据包。然后写入图象数据块中。

[/fold]
问题就是，ruby读取文件都是按字节读取，在这里就必须反编译为编码流，然后再应用长度可变LZW解压
另外长度可变LZW解压现在也暂时没有去实现，如果不能反编译的话实现了也没有什么意义

还有一个问题就是，读取出并解压了后，可以对照颜色表光栅数据什么的，应该如何建立Bitmap对象

另外还有这个，讲述解压缩的：链接
[fold]

图象数据在压缩前有两种排列格式：连续的和交织的(由图象标识符的交织标志控制(这个已经读取到了))。连续方式按从左到右、从上到下的顺序排列图象的光栅数据；交织图象按下面的方法处理光栅数据：
创建四个通道(pass)保存数据，每个通道提取不同行的数据：
第一通道(Pass 1)提取从第0行开始每隔8行的数据；
第二通道(Pass 2)提取从第4行开始每隔8行的数据；
第三通道(Pass 3)提取从第2行开始每隔4行的数据；
第四通道(Pass 4)提取从第1行开始每隔2行的数据；
下面的例子演示了提取交织图象数据的顺序：
行  通道1  通道2  通道3  通道4
0       1
1                                        4
2                             3
3                                        4
4                  2
5                                        4
6                             3
7                                        4
8       1
9                                        4
10                             3
11                                        4
12                  2
13                                        4
14                             3
15                                        4
16       1
17                                        4
18                             3
19                                        4
20                  2

[/fold]
不太清楚四个通道指的是什么（具体操作）
当然 在解压缩之前 不管几个通道都是废话 所以还是要先专注在第一个问题

喵呜喵5

四个通道就是RGB以及Alpha吧？

fux2

某截图脚本以及柳之一的bitmap类marshal范例演示了如何将bitmap对象的data塞到RM的bitmap里面。

satgo1546

把GIF的每一个像素计算出来然后一个个像素地set_pixel……
话说有个gem叫做chunky_png
LZ是要做个chunky_gif的节奏……
反正我每次读这种二进制文件结构都是失败的我也不掺合了……
我注意到了这个帖子嗯。
还有LZ你不是离开了吗？难道某个时候已经到了？（如果是我记错了请无视

---

@余烬之中 也许我还需要科普一下……
为了让用户在浏览器里看图片的时候不是从上到下一行行看见图片，出现了交错的图像，这样的话像素的顺序就是第二段引用中的顺序了。
数据传输过程是先传通道1，然后通道2，……，然后通道4。
第0次收到数据：为数据开始符，切换到GIF处理器来接收数据。
第1次收到数据：为通道1，因为是第1次，计算出对应的行数为0。于是往图像中的第0行填色。
第2次收到数据：为通道1，因为是第2次，计算出对应的行数为8。于是往图像中的第8行填色。
第3次收到数据：为通道1，因为是第3次，计算出对应的行数为16。于是往图像中的第16行填色。
第4次收到数据：为通道2，因为是第1次收到通道2的数据，计算出对应的行数为4。于是往图像中的第4行填色。
第5次收到数据：为通道2，因为是第2次收到通道2的数据，计算出对应的行数为12。于是往图像中的第4行填色。
……
……
……
第20次收到数据：为通道4，因为是第9次收到通道4的数据，计算出对应的行数为17。于是往图像中的第17行填色。
第21次收到数据：为通道4，因为是第10次收到通道4的数据，计算出对应的行数为19。于是往图像中的第19行填色。
第22次收到数据：为数据终止符，此时图像已经完全被颜色充满，完成数据传输。
实际上并非一定传输23次，不过一般会将数据当作23次……