CS144 Lab1

2026-01-21

CS144 Minnow

Lab1 Start

这一个实验要实现两个功能

Wrapping Integers

这里要实现32位seqno和64位abs_seqno进行相互转换

这里有一个很形象的比喻

32位seqno就像是一圈400米跑道，它只能精确到当前400米中的某个位置

但是在tcp中32位seqno每(2 ^ 31 - 1)就会循环一次，于是给出一个seqno就无法确认是上一圈位置还是当前圈位置

于是64位abs_seqno就是确认具体哪一圈的400米

简单来讲，32位seqno就是一个循环的圆圈，64位abs_seqno就是一个直线，能够精确定位数据包位置

我们来分析两个函数作用

Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point );

功能：将64位abs_seqno转化为32位seqno

uint64_t n是64位abs_seqno，它便于管理，是从0开始计数

那么我们就知道zero_point就是为了解决tcp中使用随机32位seqno，但是64位abs_seqno是从0开始的问题

zero_point就是起始的随机32位seqno

所以这里的实现也十分简单，只需要将n丢掉高32位，和zero_point相加即可

Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point ) {
  return Wrap32 { zero_point.raw_value_ + static_cast<uint32_t>( n ) };
}

下一个函数：

uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const;

功能：将32位seqno转化为64位abs_seqno

这里有一个问题就是一个seqno对应着无数个abs_seqno

这里就用checkpoint来定位

uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const {
  uint32_t offset = raw_value_ - zero_point.raw_value_;
  // 选定一个候选值，还没有将其和checkpoint处理
  uint64_t candidate = ( checkpoint & 0xFFFFFFFF00000000 ) + static_cast<uint64_t>( offset );
  uint64_t ret = candidate;
  // 定义一个uint32_t循环周期
  uint64_t step = 1ULL << 32; // 1ULL代表字面量为1的unsigned long long

  // 找到离checkpoint更近的位置
  if ( candidate < checkpoint ) {
    if ( checkpoint - candidate > ( step / 2 ) ) {
      ret = candidate + step;
    }
  } else {
    if ( candidate - checkpoint > ( step / 2 ) && candidate >= step ) {
      ret = candidate - step;
    }
  }
  return ret;
}

[!IMPORTANT]

这里提醒：checkpoint内容是通过获取当前缓冲区中已缓冲字节数来确定的，这样就自然而然能确定abs_seqno

Reassembler

流重组器是tcp协议中十分核心的内容

在这里，选择合适的数据结构十分重要，我看到有很多选择std::map，因为map可以存储键值

但是std::map和其他数据结构都需要实现向前/后合并已排序数据块的过程

std::vector< std::optional<> >这个数据结构就有着天然优势

每次插入新数据的时候，只往vector中的空值中填char即可，如果vector中已经有char，则跳过

这样就避免了再次实现向前/后合并的逻辑，而且加快了程序运行速度

// 写入ByteStream
void Reassembler::flush()
{
  size_t length = 0;
  while ( length < buffer_.size() && buffer_[length].has_value() ) {
    ++length;
  }
  if ( length == 0 )
    return;

  string out {};
  out.reserve( length );
  for ( size_t i = 0; i < length; ++i ) {
    out.push_back( *buffer_[i] );
  }
  output_.writer().push( out );

  next_index_ += length;
  unassembler_bytes_ -= length;

  vector<optional<char>> newbuf( buffer_.size() );
  for ( size_t i = length; i < buffer_.size(); ++i ) {
    newbuf[i - length] = buffer_[i];
  }
  buffer_.swap( newbuf );
}

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )
{
  assert( !buffer_.empty() ); // 添加断言，调试用
  if ( is_last_substring ) {
    eof_ = true;
    eof_index_ = first_index + data.size();
  }

  auto start = std::max( next_index_, first_index );
  auto end = std::min( first_index + data.size(), next_index_ + output_.writer().available_capacity() );

  if ( start >= end ) {
    flush();
    if ( eof_ && next_index_ == eof_index_ )
      output_.writer().close();
    return;
  }

  // 遍历vector
  for ( auto i = start; i < end; ++i ) {
    size_t offset = static_cast<size_t>( i - next_index_ );
    size_t di = static_cast<size_t>( i - first_index );
    if ( !buffer_[offset].has_value() ) { // 判断对应vector位置中是否为空
      buffer_[offset] = data[di];
      unassembler_bytes_++;
    }
  }
  flush();
  if ( eof_ && next_index_ == eof_index_ ) {
    output_.writer().close();
  }
}