UVa 128 Software CRC-平芜编程栈

题目描述

你在一家大量使用个人电脑的公司工作。老板Penny Pincher\texttt{Penny Pincher}Penny Pincher博士一直想将这些电脑连接起来，但又不愿意花钱购买你建议的以太网卡。你无意中提到每台PC\texttt{PC}PC都自带一个异步串行口（无需额外费用），于是老板抓住机会，让你编写必要的软件来实现PC\texttt{PC}PC间的通信。

你了解到通信过程中容易出错，典型的解决方案是在每条消息末尾附加错误校验信息，以便接收程序能检测到传输错误（大多数情况下）。经过研究，你决定采用**CRC\texttt{CRC}CRC（循环冗余校验）**作为错误校验机制，并向老板提交了如下方案：

CRC\texttt{CRC}CRC生成机制

待传输的消息被视为一个很长的正二进制数。消息的第一个字节是该二进制数的最高有效字节，第二个字节是次高有效字节，依此类推。这个二进制数称为mmm（message\texttt{message}message）。实际传输的不是mmm，而是一个新消息m2m_2m2，它由mmm和紧随其后的两字节CRC\texttt{CRC}CRC值组成。

CRC\texttt{CRC}CRC值的选取原则是：m2m_2m2除以某个161616位值ggg（生成器）的余数为000。这样接收程序只需将收到的消息除以ggg，若余数为000就认为没有发生传输错误。

你在书中发现大多数建议的ggg值都是奇数，但没有其他明显规律，因此你选择了g=34943g = 34943g=34943（十进制）作为生成器。

你的任务是设计一个算法，计算任意待发送消息对应的CRC\texttt{CRC}CRC值，并编写程序进行测试。

输入格式

每行输入包含不超过102410241024个ASCII\texttt{ASCII}ASCII字符（每行字符不包括换行符）。
输入以第一列为#的行结束。

输出格式

对每个输入行，计算该行消息的CRC\texttt{CRC}CRC值，并以十六进制形式输出两个字节的CRC\texttt{CRC}CRC值（中间用空格分隔）。
注意每个CRC\texttt{CRC}CRC值应在000到349423494234942（十进制）范围内。

题目分析与解题思路

本题的核心是计算给定消息的161616位CRC\texttt{CRC}CRC校验码，使得附加CRC\texttt{CRC}CRC后的整个消息（视为一个大整数）能被g=34943g = 34943g=34943整除。

数学模型

设消息mmm由kkk个字节组成：bk−1,bk−2,…,b0b_{k-1}, b_{k-2}, \dots, b_0bk−1,bk−2,…,b0（其中bk−1b_{k-1}bk−1是最高有效字节）。
将mmm视为一个256256256进制的数，即：

m=bk−1⋅256k−1+bk−2⋅256k−2+⋯+b0⋅2560 m = b_{k-1} \cdot 256^{k-1} + b_{k-2} \cdot 256^{k-2} + \dots + b_0 \cdot 256^0m=bk−1⋅256k−1+bk−2⋅256k−2+⋯+b0⋅2560

附加两字节CRC\texttt{CRC}CRC值ccc（0≤c<655360 \le c < 655360≤c<65536）后，得到新消息：

m2=m⋅65536+c m_2 = m \cdot 65536 + cm2=m⋅65536+c

要求m2mod g=0m_2 \mod g = 0m2modg=0，即：

(m⋅65536+c)mod g=0 (m \cdot 65536 + c) \mod g = 0(m⋅65536+c)modg=0

因此：

c=(g−(m⋅65536)mod g)mod g c = (g - (m \cdot 65536) \mod g) \mod gc=(g−(m⋅65536)modg)modg

注意ccc应输出为两个字节，即ccc在000到655356553565535之间，但题目保证g=34943g = 34943g=34943，所以c<gc < gc<g，自然满足。

算法设计

直接计算mmm可能非常大（最多102410241024字节，即281922^{8192}28192量级），必须边读边模ggg运算。

我们可以从最低有效字节开始计算mmod gm \mod gmmodg：

设当前余数为rrr（初始为000），逐个处理字节bib_ibi（从最后一个字节开始向前）：

r=(r+bi⋅256i)mod g r = (r + b_i \cdot 256^i) \mod gr=(r+bi⋅256i)modg

但256i256^i256i也会很大，需要预先计算256imod g256^i \mod g256imodg的模幂值。

可以预先计算了一个数组modular[i]，其中：

modular[i] = (65536 * 256^i) mod g

注意这里65536 = 256^2，是因为在计算m⋅65536m \cdot 65536m⋅65536时，相当于将mmm左移161616位（即乘以655366553665536）。代码中从最低字节开始累加时，直接使用了modular[j]，其中jjj是当前字节的索引（从000开始）。

计算步骤

预处理modular[0..1024]，其中modular[0] = 65536 mod g，modular[i] = (modular[i-1] * 256) mod g。
对每个输入行（非空且不以#开头）：
- 从字符串末尾开始向前遍历（即从最低有效字节向最高有效字节）。
- 对于位置jjj（从000开始）的字符line[i]，累加(line[i] * modular[j]) mod g到余数residue。
- 遍历完成后，residue即为(m⋅65536)mod g(m \cdot 65536) \mod g(m⋅65536)modg。
- 计算c = (g - residue) mod g。
- 将c转换为两个字节的十六进制输出。

边界情况

空行：CRC\texttt{CRC}CRC值为00 00。
输入结束：第一列为#的行。

代码实现

// Software CRC// UVa ID: 128// Verdict: Accepted// Submission Date: 2015-12-01// UVa Run Time: 0.352s//// 版权所有（C）2015，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMOD_BASE=34943;intmodular[1030];// 预处理 modular 数组：modular[i] = (65536 * 256^i) % MOD_BASEvoidgenerateModular(){modular[0]=65536%MOD_BASE;for(inti=1;i<=1024;i++)modular[i]=(modular[i-1]*256)%MOD_BASE;}// 将16位CRC值转换为两个字节的十六进制形式输出voidintToHex(intresidue){string hex="0123456789ABCDEF";cout<<hex[residue/256/16];cout<<hex[residue/256%16];cout<<" ";cout<<hex[(residue%256)/16];cout<<hex[residue%256%16];cout<<endl;}// 计算一行消息的CRC并输出voidsoftwareCRC(string line){intresidue=0;// 从最低有效字节开始累加for(inti=line.length()-1,j=0;i>=0;i--,j++)residue+=(line[i]*modular[j]%MOD_BASE);// 计算CRC值residue=(MOD_BASE-residue%MOD_BASE)%MOD_BASE;intToHex(residue);}intmain(intac,char*av[]){generateModular();string line;while(getline(cin,line)){if(line.length()==0){cout<<"00 00"<<endl;continue;}if(line[0]=='#')break;softwareCRC(line);}return0;}