自动搬运

查看原文

来自洛谷，原作者为

	MrPython waac_tXKCMem1dAph0gg0

搬运于2025-08-24 22:57:06，当前版本为作者最后更新于2024-04-12 10:44:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

续 上题题解。

这一次用到 T1 提供的 IP 和 MAC 地址了！快快用 map 存下来方便查找：

template<typename T,size_t n> const auto array_hash=[](std::array<T,n> const& f){
    return std::_Hash_impl::hash(f.data(),f.size());
};

std::unordered_map<std::array<uint8_t,4>,std::array<uint8_t,6>,
    decltype(array_hash<uint8_t,4>)> const eths({
        {{10,2,1,1},{0x98,0x01,0x29,0x00,0x00,1}},
        {{10,2,2,1},{0x98,0x01,0x29,0x00,0x00,2}},
        {{10,2,3,1},{0x98,0x01,0x29,0x00,0x00,3}},
        {{10,2,4,1},{0x98,0x01,0x29,0x00,0x00,4}},
        {{10,2,5,1},{0x98,0x01,0x29,0x00,0x00,5}},
        {{10,2,6,1},{0x98,0x01,0x29,0x00,0x00,6}},
        {{10,2,7,1},{0x98,0x01,0x29,0x00,0x00,7}},
        {{10,2,8,1},{0x98,0x01,0x29,0x00,0x00,8}},
        {{10,2,9,1},{0x98,0x01,0x29,0x00,0x00,9}},
        {{10,2,10,1},{0x98,0x01,0x29,0x00,0x00,10}},
        {{10,2,11,1},{0x98,0x01,0x29,0x00,0x00,11}},
        {{10,2,12,1},{0x98,0x01,0x29,0x00,0x00,12}},
        {{10,2,13,1},{0x98,0x01,0x29,0x00,0x00,13}},
        {{10,2,14,1},{0x98,0x01,0x29,0x00,0x00,14}},
        {{10,2,15,1},{0x98,0x01,0x29,0x00,0x00,15}},
        {{10,2,16,1},{0x98,0x01,0x29,0x00,0x00,16}},
    #ifndef ONLINE_JUDGE
        {{10,2,12,82},{0x98,0x01,0x29,0x00,0x00,114}},
    #endif
    },16,array_hash<uint8_t,4>);

里面的 ifdef 是干什么的？“由于提供样例会大幅降低本题难度，故不提供样例”，我们需要自己生成样例调试。

好消息是，使用 Wireshark 调试上一题时我们发现有一个目标 IP 为 10.2.12.82 的 ARP 请求，我们可以直接使用上一题的样例。因此，添加一个 ifdef，里面包含了本样例的 IP 与一个虚构的 MAC 地址方便调试，提交时自动删除。

题目需要我们自己构造包了，我们添加一些构造函数和转换为二进制的成员函数：

struct Throwable{};
struct PackageCheckError:Throwable{};
struct UnknownTargetError:Throwable{};

pcap_hdr::pcap_hdr(void):magic_number(0xA1B2C3D4),version_major(2),
    version_minor(4),thiszone(0),sigfigs(0),snaplen(262144),
    network(1){}
pcaprec_hdr::pcaprec_hdr(size_t len):ts_sec(),ts_usec(),incl_len(len),orig_len(len){}
pcaprec(std::vector<uint8_t> const& d):
    header(d.size()),data(d){}
pcap::pcap(void):header(),data(){}
pcap::pcap(pcap_hdr const& p):header(p),data(){}
ethernet_frame::ethernet_frame(std::array<uint8_t,6> const& _desMAC,std::array<uint8_t,6> const& _srcMAC,EtherType _t,std::vector<uint8_t> const& _d):
    destinationMAC(_desMAC),sourceMAC(_srcMAC),etherType(_t),data(_d),fcs(){ // getbuffer 中直接取了 fcs 的值，直接调用初始化访问未分配内存产生 UB
    fcs=get_fcs(tobuffer());
}
std::vector<uint8_t> ethernet_frame::tobuffer(void){
    std::vector<uint8_t> res{
        destinationMAC[0],destinationMAC[1],destinationMAC[2],destinationMAC[3],destinationMAC[4],destinationMAC[5],
        sourceMAC[0],sourceMAC[1],sourceMAC[2],sourceMAC[3],sourceMAC[4],sourceMAC[5],
        uint8_t(uint16_t(etherType)>>8),uint8_t(uint16_t(etherType)>>0)
    };
    res.insert(res.end(),data.begin(),data.end());
    while (res.size()<64-4) res.push_back(0);  // 长度至少为 64
    res.insert(res.end(),{uint8_t(fcs>>24),uint8_t(fcs>>16),uint8_t(fcs>>8),uint8_t(fcs>>0)});
    return res;
}

另外，构造以太网帧需要计算 FCS，因此我们将该过程从 check 函数中提出来：

static uint64_t ethernet_frame::query_fcs_byte(uint8_t x){
    static std::array<uint64_t,256> mem={};
    static constexpr int64_t G=0b100000100110000010001110110110111;
    if (mem[x]) return mem[x];
    if (x==0) return 0;
    uint8_t y=x;
    for (uint8_t i=7;i<8;--i) if ((x>>i)&1)
        x^=uint8_t(G<<i>>32),
        mem[y]^=G<<i;
    return mem[y];
}
static uint32_t ethernet_frame::get_fcs(std::vector<uint8_t> f){
    std::fill_n(f.end()-4,4,0);
    for (uint8_t& i:f) i=bitreverse(i);
    f[0]=~f[0],f[1]=~f[1],f[2]=~f[2],f[3]=~f[3];
    for (size_t i=4;i<f.size();++i){
        int64_t x=query_fcs_byte(f[i-4]);
        f[i-4]^=uint8_t(x>>(40-8)),
        f[i-3]^=uint8_t(x>>(40-16)),
        f[i-2]^=uint8_t(x>>(40-24)),
        f[i-1]^=uint8_t(x>>(40-32)),
        f[i-0]^=uint8_t(x>>(40-40));
    }
    uint32_t res=~(
        (bitreverse((uint32_t)f.rbegin()[3])<<24u)+
        (bitreverse((uint32_t)f.rbegin()[2])<<16u)+
        (bitreverse((uint32_t)f.rbegin()[1])<<8u)+
        (bitreverse((uint32_t)f.rbegin()[0])<<0u)
    );
    return res;
}
bool ethernet_frame::check(void){return fcs==get_fcs(tobuffer());}

ARP 的结构体和 main 函数相当好写，远小于上一题难度了。比葫芦画瓢就好，真没啥可说的。注意一下构造 Response 时到底应该填什么 IP 或 MAC 就可以。

struct arp{
    uint16_t hardware_type; // 总是 1
    uint16_t protocol_type; // 总是 0x0800
    uint8_t hlen; // 总是 0x6
    uint8_t plen; // 总是 0x4
    enum class OPCode:uint16_t{request=1,response=2} opcode;
    std::array<uint8_t,6> sha;
    std::array<uint8_t,4> spa;
    std::array<uint8_t,6> tha;
    std::array<uint8_t,4> tpa;

    struct OPCodeNotRequest:UnknownTargetError{};
    struct IPNotFound:UnknownTargetError{};

    arp(OPCode _type,std::array<uint8_t,6> const& _sha,std::array<uint8_t,4> const& _spa,std::array<uint8_t,6> const& _tha,std::array<uint8_t,4> const& _tpa):
        hardware_type(1),protocol_type(0x0800),hlen(6),plen(4),
        opcode(_type),sha(_sha),spa(_spa),tha(_tha),tpa(_tpa){}
    arp(ethernet_frame const& f):arp(f.data.begin()){}
    arp(std::vector<uint8_t>::const_iterator beg):
        hardware_type((beg[0]<<8)+(beg[1]<<0)),
        protocol_type((beg[2]<<8)+(beg[3]<<0)),
        hlen(beg[4]),plen(beg[5]),
        opcode(OPCode((beg[6]<<8)+(beg[7]<<0))),
        sha{beg[8],beg[9],beg[10],beg[11],beg[12],beg[13]},
        spa{beg[14],beg[15],beg[16],beg[17]},
        tha{beg[18],beg[19],beg[20],beg[21],beg[22],beg[23]},
        tpa{beg[24],beg[25],beg[26],beg[27]}{
        assert(hardware_type==1&&protocol_type==0x0800&&hlen==6&&plen==4);
    }
    std::vector<uint8_t> tobuffer(void){
        return {
            uint8_t(hardware_type>>8),uint8_t(hardware_type>>0),
            uint8_t(protocol_type>>8),uint8_t(protocol_type>>0),
            hlen,plen,uint8_t((uint16_t)opcode>>8),uint8_t((uint16_t)opcode>>0),
            sha[0],sha[1],sha[2],sha[3],
            sha[4],sha[5],spa[0],spa[1],
            spa[2],spa[3],tha[0],tha[1],
            tha[2],tha[3],tha[4],tha[5],
            tpa[0],tpa[1],tpa[2],tpa[3]
        };
    }
    arp get_response(void){
        if (opcode!=OPCode::request) throw OPCodeNotRequest();
        auto it=eths.find(tpa);
        if (it==eths.end()) throw IPNotFound();
        return arp(OPCode::response,it->second,it->first,sha,spa);
    };
};
int main(void){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr),std::cout.tie(nullptr);
    std::vector<uint8_t> buf((std::istreambuf_iterator<char>(fin)),std::istreambuf_iterator<char>());
    pcap f(buf.begin(),buf.end()),g;
    for (auto const& i:f.data)
        try{
            ethernet_frame e(i);
            if (e.etherType!=ethernet_frame::EtherType::arp) continue;
            arp s(e);
            arp t(s.get_response());
            ethernet_frame f(
                t.tha,t.sha,ethernet_frame::EtherType::arp,
                t.tobuffer()
            );
            g.data.emplace_back(f.tobuffer());
        }catch (Throwable const&){} // 忽略校验错误、发送者
    fout<<g;
}

代码 共 331 行。吸氧和不吸氧差别还挺大的。 别贺了没啥意思……