文档章节

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

lilbedwin
 lilbedwin
发布于 2014/06/12 14:06
字数 1256
阅读 44
收藏 0
点赞 0
评论 0

    了解了基本原理,看代码就轻松了,把EncodeInternal的完整代码贴上来:

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;
    }
  }
  const char* const target_end = target_data + target_size;
  const char* const start_of_last_block = target_end - BlockHash::kBlockSize;
  // Offset of next bytes in string to ADD if NOT copied (i.e., not found in
  // dictionary)
  const char* next_encode = target_data;
  // candidate_pos points to the start of the kBlockSize-byte block that may
  // begin a match with the dictionary or previously encoded target data.
  const char* candidate_pos = target_data;
  uint32_t hash_value = hasher.Hash(candidate_pos);
  while (1) {
    const size_t bytes_encoded =
        EncodeCopyForBestMatch<look_for_target_matches>(
            hash_value,
            candidate_pos,
            next_encode,
            (target_end - next_encode),
            target_hash,
            coder);
    if (bytes_encoded > 0) {
      next_encode += bytes_encoded;  // Advance past COPYed data
      candidate_pos = next_encode;
      if (candidate_pos > start_of_last_block) {
        break;  // Reached end of target data
      }
 // candidate_pos has jumped ahead by bytes_encoded bytes, so UpdateHash
      // can't be used to calculate the hash value at its new position.
      hash_value = hasher.Hash(candidate_pos);
      if (look_for_target_matches) {
        // Update the target hash for the ADDed and COPYed data
        target_hash->AddAllBlocksThroughIndex(
            static_cast<int>(next_encode - target_data));
      }
    } else {
      // No match, or match is too small to be worth a COPY instruction.
      // Move to the next position in the target data.
      if ((candidate_pos + 1) > start_of_last_block) {
        break;  // Reached end of target data
      }
      if (look_for_target_matches) {
        target_hash->AddOneIndexHash(
            static_cast<int>(candidate_pos - target_data),
            hash_value);
      }
      hash_value = hasher.UpdateHash(hash_value,
                                     candidate_pos[0],
                                     candidate_pos[BlockHash::kBlockSize]);
      ++candidate_pos;
    }
  }
  AddUnmatchedRemainder(next_encode, target_end - next_encode, coder);
  FinishEncoding(target_size, diff, coder);
  delete target_hash;
}

    开头的几行,前文分析过了,从33行开始,是block匹配的逻辑。首先初始化几个变量:next_encode是为被编码的数据起点;candidate_pos是当前窗口的起点,之前介绍过,第一个16byte如果匹配不到block,窗口就会移动;target_end是本次函数调用传递进来的数据的重点,如果窗口的右端到了终点,本次编码就该结束了。

   下面是一个循环,EncodeCopyForBestMatch函数,即之前介绍的,基于当前窗口的16个byte,找到一个匹配的block,然后尽量匹配其上下文,直到找到一个匹配最长的block,然后进行COPY编码,COPY前面可能会有一个ADD。EncodeCopyForBestMatch的返回值,是找到的最佳match数据的长度。

  if (bytes_encoded>0),这个分支,表示找到的match数据,并且成功进行了编码。这里的逻辑,就是next_encode,candidate_pos分别后移,后移的值即是math数据的长度,然后检查是否已经处理完毕了,如果没完,计算新窗口的哈希。下面的if(look_for_target_matchs),表示如果需要在target数据自身里寻找match数据,那么已经编码的数据,也应该建立分段哈希,这个分段哈希称为target_hash_。

  else分支,表示没有找到match(或者找到的match太短,不值得一次COPY编码)。这里的逻辑,candidate_pos_后移1,重新计算hash。然后如果需要自身匹配,加入target_hash,这里有点迷惑性,其实并不是每移动一个byte就需要增加一个block,看AddOneIndexHash的代码就清楚了,注意下面注释部分以及if判断:

  // This function will be called to add blocks incrementally to the target hash
  // as the encoding position advances through the target data.  It will be
  // called for every kBlockSize-byte block in the target data, regardless
  // of whether the block is aligned evenly on a block boundary.  The
  // BlockHash will only store hash entries for the evenly-aligned blocks.
  //
  void AddOneIndexHash(int index, uint32_t hash_value) {
    if (index == NextIndexToAdd()) {
      AddBlock(hash_value);
    }
  }

   循环结束后,需要对最后残留的不够一block的数据,通过函数AddUnmatchedRemainder直接编码为VCDiff的ADD,然后FinishEncoding写缓冲区。

  然后再看一下之循环开头的EncodeCopyForBestMatch函数,代码:

template<bool look_for_target_matches>
inline size_t VCDiffEngine::EncodeCopyForBestMatch(
    uint32_t hash_value,
    const char* target_candidate_start,
    const char* unencoded_target_start,
    size_t unencoded_target_size,
    const BlockHash* target_hash,
    CodeTableWriterInterface* coder) const {
  // When FindBestMatch() comes up with a match for a candidate block,
  // it will populate best_match with the size, source offset,
  // and target offset of the match.
  BlockHash::Match best_match;

  // First look for a match in the dictionary.
  hashed_dictionary_->FindBestMatch(hash_value,
                                    target_candidate_start,
                                    unencoded_target_start,
                                    unencoded_target_size,
                                    &best_match);
  // If target matching is enabled, then see if there is a better match
  // within the target data that has been encoded so far.
  if (look_for_target_matches) {
    target_hash->FindBestMatch(hash_value,
                               target_candidate_start,
                               unencoded_target_start,
                               unencoded_target_size,
                               &best_match);
  }
  if (!ShouldGenerateCopyInstructionForMatchOfSize(best_match.size())) {
    return 0;
  }
  if (best_match.target_offset() > 0) {
    // Create an ADD instruction to encode all target bytes
    // from the end of the last COPY match, if any, up to
    // the beginning of this COPY match.
    coder->Add(unencoded_target_start, best_match.target_offset());
  }
  coder->Copy(best_match.source_offset(), best_match.size());
  return best_match.target_offset()  // ADD size
       + best_match.size();          // + COPY size
}

   这个函数本身没有太多信息量,首先调用FindBestMatch,找到最佳的match数据,然后就是ADD,COPY。重头戏都交给FindBestMatch了,我们来看一下这个函数的代码:

void BlockHash::FindBestMatch(uint32_t hash_value,
                              const char* target_candidate_start,
                              const char* target_start,
                              size_t target_size,
                              Match* best_match) const {
  int match_counter = 0;
  for (int block_number = FirstMatchingBlockInline(hash_value,
                                                   target_candidate_start);
       (block_number >= 0) && !TooManyMatches(&match_counter);
       block_number = NextMatchingBlock(block_number, target_candidate_start)) {
    int source_match_offset = block_number * kBlockSize;
    const int source_match_end = source_match_offset + kBlockSize;

    int target_match_offset =
        static_cast<int>(target_candidate_start - target_start);
    const int target_match_end = target_match_offset + kBlockSize;

    size_t match_size = kBlockSize;
    {
      // Extend match start towards beginning of unencoded data
      const int limit_bytes_to_left = std::min(source_match_offset,
                                               target_match_offset);
      const int matching_bytes_to_left =
          MatchingBytesToLeft(source_data_ + source_match_offset,
                              target_start + target_match_offset,
                              limit_bytes_to_left);
      source_match_offset -= matching_bytes_to_left;
      target_match_offset -= matching_bytes_to_left;
      match_size += matching_bytes_to_left;
    }
    {
      // Extend match end towards end of unencoded data
      const size_t source_bytes_to_right = source_size_ - source_match_end;
      const size_t target_bytes_to_right = target_size - target_match_end;
      const size_t limit_bytes_to_right = std::min(source_bytes_to_right,
                                                   target_bytes_to_right);
      match_size +=
          MatchingBytesToRight(source_data_ + source_match_end,
                               target_start + target_match_end,
                               static_cast<int>(limit_bytes_to_right));
    }
    // Update in/out parameter if the best match found was better
    // than any match already stored in *best_match.
    best_match->ReplaceIfBetterMatch(match_size,
                                     source_match_offset + starting_offset_,
                                     target_match_offset);
  }
}

    未完,见下篇

© 著作权归作者所有

共有 人打赏支持
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

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

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

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

leixiaohua1020 ⋅ 2015/05/08 ⋅ 0

视频的「编解码」与「传输」的那些事儿

本文来自作者 Owen Chan 在 GitChat 上分享「关于视频的编解码与传输技术,你想知道的都在这里」,「阅读原文」查看交流实录 「文末高能」 编辑 | 泰龙 一、如何编译 FFmpag 准备工作 下载 ...

gitchat ⋅ 2017/11/24 ⋅ 0

音视频封装:AVI 格式分析

AVI英文全称为Audio Video Interleaved,即音视频交错格式,AVI基于RIFF(Resource Interchange File Format 资源交换文件格式)文件结构。 一.基本数据单元 在AVI中有两种最基本的数据单元:...

li_wen01 ⋅ 2017/09/10 ⋅ 0

Hadoop源代码分析(IFile)

Mapper的输出,在发送到Reducer前是存放在本地文件系统的,IFile提供了对Mapper输出的管理。我们已经知道,Mapper的输出是<Key,Value>对,IFile以记录<key-len, value-len, key,value>的形式...

超人学院 ⋅ 2015/05/27 ⋅ 0

开源图书--《全栈增长工程师指南》

依据在《Repractise简介篇:Web开发的七天里》中所说的 Web 开发的七个步骤而展开的电子书。当然它也是一个 APP,它一本关于如何成为全栈增长工程师的指南。 简介 我们都会学习,但是有时候我...

Phodal ⋅ 2016/04/15 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 15分钟前 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 35分钟前 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 48分钟前 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

eclipse酷炫大法之设置主题、皮肤

eclipse酷炫大法 目前两款不错的eclipse 1.系统设置 Window->Preferences->General->Appearance 2.Eclipse Marketplace下载【推荐】 Help->Eclipse Marketplace->搜索‘theme’进行安装 比如......

anlve ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部