天津北京网站建设公司,宁波网络营销方式,vs2015 做网站,app制作平台免费版下载简介
lz4是目前综合来看效率最高的压缩算法#xff0c;更加侧重压缩解压速度#xff0c;压缩比并不是第一。在当前的安卓和苹果操作系统中#xff0c;内存压缩技术就使用的是lz4算法#xff0c;及时压缩手机内存以带来更多的内存空间。本质上是时间换空间。
压缩原理
lz…简介
lz4是目前综合来看效率最高的压缩算法更加侧重压缩解压速度压缩比并不是第一。在当前的安卓和苹果操作系统中内存压缩技术就使用的是lz4算法及时压缩手机内存以带来更多的内存空间。本质上是时间换空间。
压缩原理
lz4压缩算法其实很简单举个压缩的栗子
输入abcde_bcdefgh_abcdefghxxxxxxx
输出abcde_(5,4)fgh_(14,5)fghxxxxxxx其中两个括号内的便代表的是压缩时检测到的重复项(5,4) 代表向前5个byte匹配到的内容长度有4即bcde是一个重复。当然也可以说cde是个重复项但是根据算法实现的输入流扫描顺序我们取到的是第一个匹配到的并且长度最长的作为匹配。
1.压缩格式
压缩后的数据是下面的格式 输入abcde_bcdefgh_abcdefghxxxxxxx
输出tokenabcde_(5,4)fgh_(14,5)fghxxxxxxx
格式[token]literals(offset,match length)[token]literals(offset,match length)....其他情况也可能有连续的匹配
输入fghabcde_bcdefgh_abcdefghxxxxxxx
输出fghabcde_(5,4)(13,3)_(14,5)fghxxxxxxx
格式[token]literals(offset,match length)[token](offset,match length)....
这里(13,3)长度3其实并不对match length匹配的长度默认是4Literals指没有重复、首次出现的字节流即不可压缩的部分Match指重复项可以压缩的部分Token记录literal长度match长度。作为解压时候memcpy的参数
2.压缩率
可以想到如果重复项越多或者越长压缩率就会越高。上述例子中bcde在压缩后用(5,4)表示即从4个bytes压缩成了3个bytes来表示其中offset 2bytes, match length 1byte能节省1个byte。
3.压缩算法实现
大致流程压缩过程以至少4个bytes为扫描窗口查找匹配每次移动1byte进行扫描遇到重复的就进行压缩。 由于offset用2bytes表示只能查找到到2^16(64kb)距离的匹配对于压缩4Kb的内核页只需要用到12位。 扫描的步长1byte是可以调整的即对应LZ4_compress_fast机制步长变长可以提高压缩解压速度减少压缩率。 我们来看下apple的lz4实现
//src是输入流dst是输出还需要使用一个hash表记录前面一段距离内的字符串用来查找之前是否有匹配
void lz4_encode_2gb(uint8_t ** dst_ptr,size_t dst_size,const uint8_t ** src_ptr,const uint8_t * src_begin,size_t src_size,lz4_hash_entry_t hash_table[LZ4_COMPRESS_HASH_ENTRIES],int skip_final_literals)
{uint8_t *dst *dst_ptr; // current output stream positionuint8_t *end dst dst_size - LZ4_GOFAST_SAFETY_MARGIN;const uint8_t *src *src_ptr; // current input stream literal to encodeconst uint8_t *src_end src src_size - LZ4_GOFAST_SAFETY_MARGIN;const uint8_t *match_begin 0; // first byte of matched sequenceconst uint8_t *match_end 0; // first byte after matched sequence
//苹果这里使用了一个early abort机制即输入流扫描到lz4_do_abort_eval位置的时候仍然没有匹配则认为该输入无法压缩提前结束不用全部扫描完
#if LZ4_EARLY_ABORTuint8_t * const dst_begin dst;uint32_t lz4_do_abort_eval lz4_do_early_abort;
#endifwhile (dst end){ptrdiff_t match_distance 0;//for循环一次查找到一个match即跳出到EXPAND_FORWARDfor (match_begin src; match_begin src_end; match_begin 1) {const uint32_t pos (uint32_t)(match_begin - src_begin);//苹果这里实现比较奇怪还在思考为何同时查找连续四个bytes的匹配const uint32_t w0 load4(match_begin);//该位置4个bytes的内容const uint32_t w1 load4(match_begin 1);const uint32_t w2 load4(match_begin 2);const uint32_t w3 load4(match_begin 3);const int i0 lz4_hash(w0);const int i1 lz4_hash(w1);const int i2 lz4_hash(w2);const int i3 lz4_hash(w3);const uint8_t *c0 src_begin hash_table[i0].offset;const uint8_t *c1 src_begin hash_table[i1].offset;const uint8_t *c2 src_begin hash_table[i2].offset;const uint8_t *c3 src_begin hash_table[i3].offset;const uint32_t m0 hash_table[i0].word;//取出hash表中以前有没有一样的值const uint32_t m1 hash_table[i1].word;const uint32_t m2 hash_table[i2].word;const uint32_t m3 hash_table[i3].word;hash_table[i0].offset pos;hash_table[i0].word w0;hash_table[i1].offset pos 1;hash_table[i1].word w1;hash_table[i2].offset pos 2;hash_table[i2].word w2;hash_table[i3].offset pos 3;hash_table[i3].word w3;match_distance (match_begin - c0);//比较hash表中的值和当前指针位置的hash值if (w0 m0 match_distance 0x10000 match_distance 0) {match_end match_begin 4;goto EXPAND_FORWARD;}match_begin;match_distance (match_begin - c1);if (w1 m1 match_distance 0x10000 match_distance 0) {match_end match_begin 4;goto EXPAND_FORWARD;}match_begin;match_distance (match_begin - c2);if (w2 m2 match_distance 0x10000 match_distance 0) {match_end match_begin 4;goto EXPAND_FORWARD;}match_begin;match_distance (match_begin - c3);if (w3 m3 match_distance 0x10000 match_distance 0) {match_end match_begin 4;goto EXPAND_FORWARD;}#if LZ4_EARLY_ABORT//DRKTODO: Evaluate unrolling further. 2xunrolling had some modest benefitsif (lz4_do_abort_eval ((pos) LZ4_EARLY_ABORT_EVAL)) {ptrdiff_t dstd dst - dst_begin;//到这仍然没有匹配放弃if (dstd 0) {lz4_early_aborts;return;}/* if (dstd pos) { */
/* return; */
/* } */
/* ptrdiff_t cbytes pos - dstd; */
/* if ((cbytes * LZ4_EARLY_ABORT_MIN_COMPRESSION_FACTOR) pos) { */
/* return; */
/* } */lz4_do_abort_eval 0;}
#endif}//到这整个for循环都没有找到match直接把整个src拷贝到dst即可if (skip_final_literals) { *src_ptr src; *dst_ptr dst; return; } // do not emit the final literal sequence// Emit a trailing literal that covers the remainder of the source buffer,// if we can do so without exceeding the bounds of the destination buffer.size_t src_remaining src_end LZ4_GOFAST_SAFETY_MARGIN - src;if (src_remaining 15) {*dst (uint8_t)(src_remaining 4);memcpy(dst, src, 16); dst src_remaining;} else {*dst 0xf0;dst lz4_store_length(dst, end, (uint32_t)(src_remaining - 15));if (dst 0 || dst src_remaining end) return;memcpy(dst, src, src_remaining); dst src_remaining;}*dst_ptr dst;*src_ptr src src_remaining;return;EXPAND_FORWARD:// Expand match forward 查看匹配是否能向前扩展扩大匹配长度{const uint8_t * ref_end match_end - match_distance;while (match_end src_end){size_t n lz4_nmatch(LZ4_MATCH_SEARCH_LOOP_SIZE, ref_end, match_end);if (n LZ4_MATCH_SEARCH_LOOP_SIZE) { match_end n; break; }match_end LZ4_MATCH_SEARCH_LOOP_SIZE;ref_end LZ4_MATCH_SEARCH_LOOP_SIZE;}}// Expand match backward 查看匹配是否能向后扩展扩大匹配长度{// match_begin_min max(src_begin match_distance,literal)const uint8_t * match_begin_min src_begin match_distance;match_begin_min (match_begin_min src)?src:match_begin_min;const uint8_t * ref_begin match_begin - match_distance;while (match_begin match_begin_min ref_begin[-1] match_begin[-1] ) { match_begin - 1; ref_begin - 1; }}// Emit match 确定好match的offset和length以后编码成压缩后的格式dst lz4_emit_match((uint32_t)(match_begin - src), (uint32_t)(match_end - match_begin), (uint32_t)match_distance, dst, end, src);if (!dst) return;// Update statesrc match_end;// Update return values to include the last fully encoded match//刷新src和dst位置回到while重新开始for循环*dst_ptr dst;*src_ptr src;}
}
安卓内存中压缩的实例
该例子是一个起址0xffffffc06185f000的4K页大部分是0和1由于length或者offset超长多了一些特殊处理这部分可以看安卓的lz4源码发现两个匹配压缩后的数据为31bytes压缩后概览如下
09-15 14:35:06.821 3[138, kswapd0][ 638.194336] src 0xffffffc06185f000 literallen 1
09-15 14:35:06.821 3[138, kswapd0][ 638.194349] src 0xffffffc06185f000 (1,219) #(offset,match length)
09-15 14:35:06.821 3[138, kswapd0][ 638.194359] src 0xffffffc06185f000 literallen 1
09-15 14:35:06.821 3[138, kswapd0][ 638.194386] src 0xffffffc06185f000 (3044,7)
09-15 14:35:06.821 3[138, kswapd0][ 638.194400] src 0xffffffc06185f000 count 2 compressed 31
---------------------------对应压缩后的原始数据-----------------------------
第一个匹配
09-15 14:35:06.821 3[138, kswapd0][ 638.194411] 0xffffffc06185f000 31 #token:0001 1111 前四位是literal长度1低4位15表示matchlength长度溢出要看后面
09-15 14:35:06.821 3[138, kswapd0][ 638.194422] 0xffffffc06185f000 0 #literal
09-15 14:35:06.821 3[138, kswapd0][ 638.194433] 0xffffffc06185f000 1 #offset 小端序01
09-15 14:35:06.821 3[138, kswapd0][ 638.194444] 0xffffffc06185f000 0 #offset
09-15 14:35:06.821 3[138, kswapd0][ 638.194459] 0xffffffc06185f000 255 #matchLength begin
09-15 14:35:06.821 3[138, kswapd0][ 638.194469] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194483] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194494] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194505] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194551] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194565] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194579] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194590] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194602] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194612] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194624] 0xffffffc06185f000 219 #matchLength end: 219255*11 3024
第二个匹配
09-15 14:35:06.822 3[138, kswapd0][ 638.194635] 0xffffffc06185f000 31 #Token:0001 1111 前四位是literal长度1
09-15 14:35:06.822 3[138, kswapd0][ 638.194646] 0xffffffc06185f000 1 #literal
09-15 14:35:06.822 3[138, kswapd0][ 638.194657] 0xffffffc06185f000 228 #offset
09-15 14:35:06.822 3[138, kswapd0][ 638.194667] 0xffffffc06185f000 11 #offset 228(1110 0100) 11(1011) 改为小端序(1011 1110 0100)即3044
09-15 14:35:06.822 3[138, kswapd0][ 638.194678] 0xffffffc06185f000 255 #matchLength begin
09-15 14:35:06.822 3[138, kswapd0][ 638.194689] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194701] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194712] 0xffffffc06185f000 255
09-15 14:35:06.822 3[138, kswapd0][ 638.194747] 0xffffffc06185f000 7 #matchLength end:255*47 1027解压算法
压缩理解了其实解压也很简单
输入[token]abcde_(5,4)[token]fgh_(14,5)fghxxxxxxx
输出abcde_bcdefgh_abcdefghxxxxxxx根据解压前的数据流取出token内的lengthliterals直接复制到输出即memcpy(src,dst,length) 遇到match在从前面已经拷贝的literals复制到后面即可
