文档章节

open-vcdiff流式编码过程分析(二)

lilbedwin
 lilbedwin
发布于 2014/06/12 13:42
字数 1738
阅读 126
收藏 0
点赞 0
评论 0

    接上篇,本篇开始关注StreamingEncoder的实际工作过程,首先是构造函数,代码:

VCDiffStreamingEncoder::VCDiffStreamingEncoder(
    const HashedDictionary* dictionary,
    VCDiffFormatExtensionFlags format_extensions,
    bool look_for_target_matches)
    : impl_(new VCDiffStreamingEncoderImpl(dictionary,
                                           format_extensions,
                                           look_for_target_matches)) { }

    以上代码,第一个参数是之前构造好的HashedDictionary;第二个参数是表示二进制输出格式的选项,正如前文描述,open-vcdiff为了sdch应用,对rfc3284进行了部分扩充,扩充的部分可以在这个参数里体现;第三个布尔型参数,表示在编码过程中寻找字符串匹配时,是否在target内容自身中寻找匹配的block(如果sdch配合gzip一起使用,第三个参数可以传递false,并不影响最终的压缩效率)。结下来,代码调用VCDiffStreamingEncoderImpl的构造函数初始化指针变量impl_,构造函数的代码如下:

inline VCDiffStreamingEncoderImpl::VCDiffStreamingEncoderImpl(
    const HashedDictionary* dictionary,
    VCDiffFormatExtensionFlags format_extensions,
    bool look_for_target_matches)
    : engine_(dictionary->engine()),
      format_extensions_(format_extensions),
      look_for_target_matches_(look_for_target_matches),
      encode_chunk_allowed_(false) {
  if (format_extensions & VCD_FORMAT_JSON) {
    coder_.reset(new JSONCodeTableWriter());
  } else {
    // This implementation of the encoder uses the default
    // code table.  A VCDiffCodeTableWriter could also be constructed
    // using a custom code table.
    coder_.reset(new VCDiffCodeTableWriter(
        (format_extensions & VCD_FORMAT_INTERLEAVED) != 0));
  }
}

    上述代码初始化通过构造函数初始化列表,初始化一系列内部变量,注意engine_变量的赋值,这个类同样聚集了类VCDiffEngine,参考之前的UML图。在函数正文中对coder_进行reset,coder_是采用std::auto_ptr包装的成员变量,其定义如下:

std::auto_ptr<CodeTableWriterInterface> coder_;

     而VCDiffCodeTableWriter是一个底层的二进制输出接口,将编码逻辑的语义输出,转化为二进制表示,以下是部分代码摘录。可以看到,其具体的功能包括添加编码头,编码尾,编码ADD,COPY,RUN指令,增加checksum等,这部分主要涉及二进制数据的拼接,我们不再深入研究。

class VCDiffCodeTableWriter : public CodeTableWriterInterface {
 public: 
  virtual void WriteHeader(OutputStringInterface* out,
                           VCDiffFormatExtensionFlags format_extensions);
 
  // Encode an ADD opcode with the "size" bytes starting at data
  virtual void Add(const char* data, size_t size);
 
  // Encode a COPY opcode with args "offset" (into dictionary) and "size" bytes.
  virtual void Copy(int32_t offset, size_t size);
 
  // Encode a RUN opcode for "size" copies of the value "byte".
  virtual void Run(size_t size, unsigned char byte);
 
  virtual void AddChecksum(VCDChecksum checksum) {
    add_checksum_ = true;
    checksum_ = checksum;
  }
 
  virtual void FinishEncoding(OutputStringInterface* /*out*/) {}
};

    接下来,看下一三个实际编码操作的函数VCDiffStreamingEncoder::StartEncoding,EncodeChunk,以及FinishEncoding。首先是StartEncoding,这个函数主要拼一份VCDiff的头出来。这个函数会调用EncodeChunkToInterface,然后是impl_->StartEncoding,代码一并贴出来: 

template<class OutputType>
bool StartEncoding(OutputType* output) {
    OutputString<OutputType> output_string(output);
    return StartEncodingToInterface(&output_string);
}
  
bool VCDiffStreamingEncoder::StartEncodingToInterface(
    OutputStringInterface* out) {
  return impl_->StartEncoding(out);
}

inline bool VCDiffStreamingEncoderImpl::StartEncoding(
    OutputStringInterface* out) {
  if (!coder_->Init(engine_->dictionary_size())) {
    VCD_DFATAL << "Internal error: "
                  "Initialization of code table writer failed" << VCD_ENDL;
    return false;
  }
  coder_->WriteHeader(out, format_extensions_);
  encode_chunk_allowed_ = true;
  return true;
}

    以上代码的逻辑比较简单,层层调用后,最终采用coder_->WriteHeader()函数,这个前文介绍过,就是底层的二进制拼接,不再深究。

    然后是EncodeChunk函数,终于开始编码了,函数的2个参数分别是待编码数据的指针与长度。同样的风格,首先调用EncodeChunkToInterface,然后是impl_->EncodeChunk(),代码如下: 

template<class OutputType>
bool EncodeChunk(const char* data, size_t len, OutputType* output) {
    OutputString<OutputType> output_string(output);
    return EncodeChunkToInterface(data, len, &output_string);
}
  
bool VCDiffStreamingEncoder::EncodeChunkToInterface(
    const char* data,
    size_t len,
    OutputStringInterface* out) {
  return impl_->EncodeChunk(data, len, out);
}

inline bool VCDiffStreamingEncoderImpl::EncodeChunk(
    const char* data,
    size_t len,
    OutputStringInterface* out) {
  if (!encode_chunk_allowed_) {
    VCD_ERROR << "EncodeChunk called before StartEncoding" << VCD_ENDL;
    return false;
  }
  if ((format_extensions_ & VCD_FORMAT_CHECKSUM) != 0) {
    coder_->AddChecksum(ComputeAdler32(data, len));
  }
  engine_->Encode(data, len, look_for_target_matches_, out, coder_.get());
  return true;
}

   在上面的impl_->EncodeChunk中,会check是否设置了VCD_FORMAT_CHECKSUM,如果设置了,需要在二进制中补充checksum,这个特性是open-vcdiff为sdch做的扩展。最后会把数据交给engine_->Encode进行处理,还记得之前的UML图吗,这个engine_与HashedDictionary里聚集的是同一个。我们来看一下VCDiffEngine::Encode的代码实现:

void VCDiffEngine::Encode(const char* target_data,
                          size_t target_size,
                          bool look_for_target_matches,
                          OutputStringInterface* diff,
                          CodeTableWriterInterface* coder) const {
  if (look_for_target_matches) {
    EncodeInternal<true>(target_data, target_size, diff, coder);
  } else {
    EncodeInternal<false>(target_data, target_size, diff, coder);
  }
}

    其中look_for_target_matches即是VCDiffStreamingEncoder构造函数的第三个参数赋的值,其作用之前介绍过了,一般我们设为fasle。我们继续看EncoderInternal函数,先贴部分代码:    

template<bool look_for_target_matches>
void VCDiffEngine::EncodeInternal(const char* target_data,
                                  size_t target_size,
                                  OutputStringInterface* diff,
                                  CodeTableWriterInterface* coder) const {
  if (!hashed_dictionary_) {
    VCD_DFATAL << "Internal error: VCDiffEngine::Encode() "
                  "called before VCDiffEngine::Init()" << VCD_ENDL;
    return;
  }
  if (target_size == 0) {
    return;  // Do nothing for empty target
  }
  // Special case for really small input
  if (target_size < static_cast<size_t>(BlockHash::kBlockSize)) {
    AddUnmatchedRemainder(target_data, target_size, coder);
    FinishEncoding(target_size, diff, coder);
    return;
  }
  RollingHash<BlockHash::kBlockSize> hasher;
  BlockHash* target_hash = NULL;
  if (look_for_target_matches) {
    // Check matches against previously encoded target data
    // in this same target window, as well as against the dictionary
    target_hash = BlockHash::CreateTargetHash(target_data,
                                              target_size,
                                              dictionary_size());
    if (!target_hash) {
      VCD_DFATAL << "Instantiation of target hash failed" << VCD_ENDL;
      return;
    }
  }
  ......

    首先如果target数据的长度,不够一个block,直接AddUnmatchedRemainder,我们看一下这个函数的代码:

inline void VCDiffEngine::AddUnmatchedRemainder(
    const char* unencoded_target_start,
    size_t unencoded_target_size,
    CodeTableWriterInterface* coder) const {
  if (unencoded_target_size > 0) {
    coder->Add(unencoded_target_start, unencoded_target_size);
  }
}

   这里直接采用VCDIFF的ADD指令进行了编码,从增量压缩的角度,相当于没有进行压缩,直接原文拷贝。所以说,进行流式压缩时,要避免这种每次传递给编码器数据过短的情况。然后FinishEncoding,把编码的数据写入到输出接口,代码如下:

inline void VCDiffEngine::FinishEncoding(
    size_t target_size,
    OutputStringInterface* diff,
    CodeTableWriterInterface* coder) const {
  if (target_size != static_cast<size_t>(coder->target_length())) {
    VCD_DFATAL << "Internal error in VCDiffEngine::Encode: "
                  "original target size (" << target_size
               << ") does not match number of bytes processed ("
               << coder->target_length() << ")" << VCD_ENDL;
  }
  coder->Output(diff);
}

   接着,我们回到VCDiffEngine::EncodeInternal的代码继续分析,其中if(look_for_target_matchs)里的部分,会对参数传递来的target数据像之前的dict数据一样,分block建立哈希表,供后续匹配用,我们先忽略这段逻辑,看下面的字符串匹配编码过程。   

   介绍下面的代码前,首先阐述一下原理。对于target数据,采用block size(16bytes)为窗口,从起始字节开始采用之前对dict分段hash相同的算法计算该窗口内数据的哈希值。采用该哈希值检索dict哈希表,看该16个bytes是否在dict中能找到一个完全相同的block。如果没有找到,窗口向后移动一个byte,重新计算哈希值,继续在哈希表中寻找。

    如果找到一个完全相同的block,则check该block在dict中的上下文,以及当前窗口覆盖的target数据的上下文,即把匹配的16byte数据分别向前、向后扩展,匹配尽可能多的字符。找到这段尽可能长的match bytes后,并不会直接编码为COPY,因为当前窗口覆盖的16个bytes,或许可以匹配到另外一个block,从这个block进行上下文扩展匹配,或许可以做到更长的match bytes。因此,这里会继续向后寻找可以匹配的block,代码实现上,沿着同哈希那个拉链表向后寻找即可。如果能找到新的匹配的block,同样检查它的上下文,进行扩展。重复这个过程,直至找到最长的一段match,编码为COPY。再窗口移动过程中被skip的byte,编码为ADD。

    未完,请参考下一篇。

© 著作权归作者所有

共有 人打赏支持
lilbedwin
粉丝 1
博文 5
码字总数 5937
作品 0
朝阳
程序员
Google的一些开源软件

代码分析 classp 语法解析器。C++。 shlex 小词法器。Shell Lexer也。Go。 streamhtmlpars 流式HTML分析器。C。 9年。 shipshap 源代码静态分析工具。Go & Java。1年。 infact 轻量级别的C++...

shengjuntu ⋅ 2016/11/21 ⋅ 0

[差量更新系列2]Xdelta3原理学习笔记

Xdelta3是一种优秀的、被广泛使用的差量更新算法,它在操作上既有对新文件(targetfile)和旧文件(sourcefile)的差分(differencing)又有对产生的patch包进行压缩(compression),我们将...

Jr小王子 ⋅ 2016/11/07 ⋅ 0

《Nodejs开发加密货币》之二十六:轻松从Js文件生成UML类图

前言 上一篇《函数式编程入门经典》,罗嗦了很长,很多小伙伴看得云里雾里。这里提供一个实例,让大家切身感受函数式编程的奥妙和趣味。当然,仅仅为了举例而写代码就没有什么意义了,本书提...

imfly ⋅ 2016/09/03 ⋅ 0

iOS直播类APP开发流程解析(内附源码详解)

前言 个人认为要想把直播从零开始做出来,绝对是牛逼中的牛逼,大牛中的大牛,因为直播中运用到的技术难点非常之多,视频/音频处理,图形处理,视频/音频压缩,CDN分发,即时通讯等技术,每一...

_小迷糊 ⋅ 05/09 ⋅ 0

OSI七层模型和TCP/IP参考模型

要知道,数据在网络之间的传输过程是非常复杂的,因此应首先建立分层模型,分层模型是一组用于开发网络协议的设计方法,就是把网络之间各个节点通信这个复杂的问题分层若干个相对简单的问题,...

杨书凡 ⋅ 2017/07/17 ⋅ 0

基于Hi3516A的H265 IPC LIVE555 开发基本原理

转载于http://m.blog.csdn.net/faihung/article/details/73008742,如有侵权,请告知删除。 1 系统工作原理 系统以Hi3516A开发平台(由高分辨率1080 p的AR0330摄像头模块和带千兆以太网功能的...

oqqHuTu12345678 ⋅ 01/02 ⋅ 0

JAVA之编码/解码 -- 各种环境下可能会发生的乱码问题及解决方案

工作中经常遇到java编码问题,由于缺乏研究,总是无法给出确切的答案,这个周末在网上查了一些资料,在此做些汇总。 问题一:在java中读取文件时应该采用什么编码? Java读取文件的方式总体可...

roockee ⋅ 2013/10/22 ⋅ 0

从外部编码的角度再议Java乱码问题

从外部编码的角度再议Java乱码问题 石 琎 2017 年 12 月 07 日发布 在实际项目中,由于系统的复杂性,乱码的根源往往不容易快速定位,乱码问题不见得一定能通过在 Java 内部编解码的方式解决...

石 琎 ⋅ 2017/12/07 ⋅ 0

x264源代码简单分析:x264命令行工具(x264.exe)

===================================================== H.264源代码分析文章列表: 【编码 - x264】 x264源代码简单分析:概述 x264源代码简单分析:x264命令行工具(x264.exe) x264源代码...

leixiaohua1020 ⋅ 2015/05/08 ⋅ 0

[通信] ITU-T G.729 8kb/s CS—ACELP简介

国际电信联盟(ITU-T)于1995年11月正式通过了G.729。 ITU-T建议G.729也被称作“共轭结构代数码本激励线性预测编码方案”(CS-ACELP),它是当前较新的一种语音压缩标准。96年ITU-T又制定了G.7...

AlphaJay ⋅ 2010/07/22 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

来自一个优秀Java工程师的简历

写在前面: 鉴于前几天的一份前端简历,虽然带着很多不看好的声音,但却帮助了很多正在求职路上的人,不管评论怎么说,我还是决定要贴出一份后端的简历。 XXX ID:357912485 目前正在找工作 ...

颖伙虫 ⋅ 22分钟前 ⋅ 0

Confluence 6 恢复一个站点有关使用站点导出为备份的说明

推荐使用生产备份策略。我们推荐你针对你的生产环境中使用的 Confluence 参考 Production Backup Strategy 页面中的内容进行备份和恢复(这个需要你备份你的数据库和 home 目录)。XML 导出备...

honeymose ⋅ 今天 ⋅ 0

JavaScript零基础入门——(九)JavaScript的函数

JavaScript零基础入门——(九)JavaScript的函数 欢迎回到我们的JavaScript零基础入门,上一节课我们了解了有关JS中数组的相关知识点,不知道大家有没有自己去敲一敲,消化一下?这一节课,...

JandenMa ⋅ 今天 ⋅ 0

火狐浏览器各版本下载及插件httprequest

各版本下载地址:http://ftp.mozilla.org/pub/mozilla.org//firefox/releases/ httprequest插件截至57版本可用

xiaoge2016 ⋅ 今天 ⋅ 0

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 今天 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

PXE/KickStart 无人值守安装

导言 作为中小公司的运维,经常会遇到一些机械式的重复工作,例如:有时公司同时上线几十甚至上百台服务器,而且需要我们在短时间内完成系统安装。 常规的办法有什么? 光盘安装系统 ===> 一...

kangvcar ⋅ 昨天 ⋅ 0

使用Puppeteer撸一个爬虫

Puppeteer是什么 puppeteer是谷歌chrome团队官方开发的一个无界面(Headless)chrome工具。Chrome Headless将成为web应用自动化测试的行业标杆。所以我们很有必要来了解一下它。所谓的无头浏...

小草先森 ⋅ 昨天 ⋅ 0

Java Done Right

* 表示难度较大或理论性较强。 ** 表示难度更大或理论性更强。 【Java语言本身】 基础语法,面向对象,顺序编程,并发编程,网络编程,泛型,注解,lambda(Java8),module(Java9),var(...

风华神使 ⋅ 昨天 ⋅ 0

Linux系统日志

linux 系统日志 /var/log/messages /etc/logrotate.conf 日志切割配置文件 https://my.oschina.net/u/2000675/blog/908189 logrotate 使用详解 dmesg 命令 /var/log/dmesg 日志 last命令,调......

Linux学习笔记 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部