snappy压缩过程详解.docx

压缩过程变量声明const char * input; 输入的待压缩的二进制串unsigned int input_size; 输入的二进制串的字节数char * output; 压缩后的数据存放位置unsigned short table[]; 存放 input_cur 之前的每个字节开始的 uint32 的偏移，其下标与前边 uint32 的 hash 值对应使用之前必须全部清 0.偏移：匹配开始位置距离串首的长度第一步：将输入串的大小input_size存储在输出串output的前1-5个字节，将输入的串分割 成32k大小的串，循环取出各块进行压缩第二步：将输出位置emit_next设置为串首，即exmit_next = input,串比较位置ip_next设置 为当前位置第三步：拿到ip_next开始的4个字节转换成uint32然后hash第四步：将emit_next加上hash值对应table的下标中的值赋给指针candidate第五步：将当前位置的偏移赋给table[hash]第六步：比较candidate处开始的四个字节转换成uint32与当前位置的uint32是否相等，若 相等，执行第七步，否者ip_next自增1,执行第三步第七步：将emit_next和ip_next之间串的长度和内容存储到output中第八步：查找当前位置开始的串与candidate开始的串的最大匹配长度matched 第九步：存储匹配信息，包括匹配长度和偏移第十步： candidate 前移 mathed 长度第十一步： 查看 candidate 处是否匹配， 若匹配， 转到第八步；否则 emit_next = candidate,ip_next = candidate,执行第十二步第十二步：检查是否到了串尾，若是则退出，否则转到第三步 压缩之后的数据存储结构输人串的总宦康|1-5 个字节输入串的总长度第一个字节的存储结构后7位存储数据的长的低了位 第一^为0表示遠是存储压缩前数膳氏度的最后 节”为]表示后边的仍然是存储数据怅度每个压缩块内的数据结构耒匹配上的串匹耒匹配上的串匹配低鼻未匹配上的串的存储结构串长 串内容串长部分的数据结构串长小于 60匹配成功的串的存储信息结构匹配长度大于 6864M110偏移的低呂位偏移的高呂位第一^节第三个字节第二住节匹配长度大于 64第二心节第三个字节60；®!10偏移的低2位傩的高创立匹配长度小于64第一4^节第二佶节第三个字节匹配故處咸110偏移的低结位偏移的高窘位对于匹配长度小于12 且偏移小于2048的匹配第二存节l^n减401偏移前低吕位/\偏移的高3位解压过程根据前边的数据存储结构，可以明确识别不同字段表示什么，直接表示串内容的输出到解压 缩串中，压缩部分根据偏移和匹配长度查找到已解压部分复制对应的内存内容到解压串中即。