文档章节

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

lilbedwin
 lilbedwin
发布于 2014/06/12 15:16
字数 455
阅读 55
收藏 0

    接上篇贴的代码,开头的for循环,for后面括号里的3项很有信息量。FirstMatchingBlockInline,这个函数找到第一块匹配的block,即从链表头开始找,找到第一个完全match的block;TooManyMatches防止大量的block全相同导致性能受损。而NextMatchingBlock表示之前已经有match的block了,接着找,它的逻辑是沿着链表往回找。相关代码:

inline int BlockHash::FirstMatchingBlockInline(uint32_t hash_value,
                                               const char* block_ptr) const {
  return SkipNonMatchingBlocks(hash_table_[GetHashTableIndex(hash_value)],
                               block_ptr);
}

int BlockHash::NextMatchingBlock(int block_number,
                                 const char* block_ptr) const {
  if (static_cast<size_t>(block_number) >= GetNumberOfBlocks()) {
    VCD_DFATAL << "NextMatchingBlock called for invalid block number "
               << block_number << VCD_ENDL;
    return -1;
  }
  return SkipNonMatchingBlocks(next_block_table_[block_number], block_ptr);
}

inline int BlockHash::SkipNonMatchingBlocks(int block_number,
                                            const char* block_ptr) const {
  int probes = 0;
  while ((block_number >= 0) &&
         !BlockContentsMatchInline(block_ptr,
                                   &source_data_[block_number * kBlockSize])) {
    if (++probes > kMaxProbes) {
      return -1;  // Avoid too much chaining
    }
    block_number = next_block_table_[block_number];
  }
  return block_number;
}

inline bool BlockHash::TooManyMatches(int* match_counter) {
  ++(*match_counter);
  return (*match_counter) > kMaxMatchesToCheck;
}

    回到前一篇的FindBestMatch代码,关注for的循环体。这里的逻辑即之前提到的上下文扩展,分别向前、向后进行匹配,直到找到尽可能多的匹配到内容。最后一句:

 best_match->ReplaceIfBetterMatch(match_size,
                                     source_match_offset + starting_offset_,
                                     target_match_offset);

   这里变量best_match只保存最长的一段match,这个变量是一个输出参数,带给上层函数:VCDiffEngine::EncodeCopyForBestMatch。

   为了有始有终,再看一下向用户暴露的结束编码接口,StreamingEncoder::FinishEncoding函数,还是之前的风格,传递给函数FinishEncodingToInterface,进而再调用impl_,最终到coder_完成底层的二进制输出,代码: 

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

inline bool VCDiffStreamingEncoderImpl::FinishEncoding(
    OutputStringInterface* out) {
  if (!encode_chunk_allowed_) {
    VCD_ERROR << "FinishEncoding called before StartEncoding" << VCD_ENDL;
    return false;
  }
  encode_chunk_allowed_ = false;
  coder_->FinishEncoding(out);
  return true;
}

    以上代码,实现输出一个二进制编码的tail,整个编码过程结束。

    全文完。

© 著作权归作者所有

共有 人打赏支持
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
23
0
[差量更新系列2]Xdelta3原理学习笔记

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

Jr小王子
2016/11/07
29
0
FFmpeg命令行工具学习(五):FFmpeg 编解码 API 分析

在上一篇文章 FFmpeg命令行工具学习(四):FFmpeg API 介绍与通用 API 分析 中,我们简单的讲解了一下FFmpeg 的API基本概念,并分析了一下通用API,本文我们将分析 FFmpeg 在编解码时使用的A...

灰色飘零
07/20
0
0
ffmpeg中MPEG2 TS 流解码的流程分析

一、FFMPEG 中MPEG2 TS 流解码的流程分析 说道具体的音频或者视频格式,一上来就是理论,那是国内混资历的所谓教授的做为, 对于我们,不合适,还是用自己的方式理解这些晦涩不已的理论吧。 ...

地狱的烈火
2013/06/21
0
0
FFmpeg命令行工具学习(四):FFmpeg API 介绍与通用 API 分析

一、FFmpeg 相关术语 1. 容器/文件(Container/File):即特定格式的多媒体文件,比如MP4,flv,mov等。 2. 媒体流(Stream):表示在时间轴上的一段连续的数据,比如一段声音数据、一段视频...

灰色飘零
07/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

AOSP Build System —— Soong

Soong Soong is the replacement for the old Android make-based build system. It replaces Android.mk files with Android.bp files, which are JSON-like simple declarative descriptio......

雪落青山
23分钟前
1
0
C# lock关键字和mutex类的坑

Unity 5.6 环境下的 lock关键字,在特定的多线程环境下会死锁 崩溃 其中一种情况: 异步socket 操作,由于内部是一个线程池回调的异步回调,操作同一个对象时 lock关键字会概率出现死锁 闪退...

梦想游戏人
34分钟前
0
0
redis-hash

哈希类型是指健值本身又是一个键值对结构 基本命令: hset key field value 设置值 hget(获取),hdel(删除),hlen(计算field个数),hmget(批量设置),hexists(是否存在),hkeys(获取所有的...

拐美人
51分钟前
2
0
简单的svm例子

数据来源:https://github.com/oumiga1314/Coursera-ML-AndrewNg-Notes/blob/master/code/ex6-SVM/data/ex6data1.mat import pandas as pd import numpy as np import scipy.io as sio impor......

南桥北木
55分钟前
1
0
android 关于View的一些整理

1、Button text的值为英文时,会自动转换成大写。如需取消,设置android:textAllCaps="false" 2、控件的可见性 可以在layout的配置文件中,配置android:visibility属性 调用setVisibility()...

西米小娅
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部