open-vcdiff流式编码过程分析(四)
open-vcdiff流式编码过程分析(四)
lilbedwin 发表于4年前
open-vcdiff流式编码过程分析(四)
  • 发表于 4年前
  • 阅读 40
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: 介绍open_vcdiff::StreamingEncoder的底层工作原理,(四)

    接上篇贴的代码,开头的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,整个编码过程结束。

    全文完。

标签: open-vcdiff sdch
共有 人打赏支持
粉丝 1
博文 5
码字总数 5937
×
lilbedwin
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: