热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

python累加算法_如何理解这段校验和算法Python代码?

这段代码我可以跟你解释,是个经典代码了,刚好我也刚看过,我这是长这个样子的:defchecksum(data):iflen(

这段代码我可以跟你解释,是个经典代码了,刚好我也刚看过,我这是长这个样子的:

def checksum(data):

if len(data) % 2:

data += b'\x00'

s = sum(array.array('H',data))

s = (s & 0xffff) + (s >> 16)

s += (s >> 16)

return _socket.ntohs(~s & 0xffff)我们首先要理解RFC当中对checksum的定义:

Header Checksum: 16 bits

A checksum on the header only. Since some header fields change

(e.g., time to live), this is recomputed and verified at each point

that the internet header is processed.

The checksum algorithm is:

The checksum field is the 16 bit one's complement of the one's

complement sum of all 16 bit words in the header. For purposes of

computing the checksum, the value of the checksum field is zero.

这段话中,one's complement是反码的意思。也就是说:

首先将checksum字段置为0

将所有的数据理解成一系列的反码word(双字节数)

将所有的反码求和,再取反,得到checksum

反码是指一种表示正负数的方式:最高位表示正或者负,正数用原码,负数用绝对值取反。我们通常使用的正负数表示系统为补码,双字下,1对应0x0001,-1对应0xffff;而反码下,1对应0x0001,-1对应0xfffe。把反码相加,最后的结果再次取反,就是校验和。

那么你一定要问,为什么程序会变成这个奇怪的样子呢?

由于我们的CPU使用的是补码,我们需要考虑反码求和与补码求和运算的不同之处。反码和原码有类似的溢出规则,但是反码有两个0的表示方式(0x0000和0xffff),所以在产生溢出时有一些差异:如果是两个正数,由于都是原码表示,反码相加与补码相加相同。

一正一负,结果为正时,例如-2 + 3,用反码表示为0xfffd和3,按无符号规则相加原本应等于0,由于绕过了0,因此需要额外加1来处理这个溢出的情况,也就是0x0001

一正一负,结果为负时,例如-3 + 2,用反码表示为0xfffc和2,相加为0xfffe,为-1,与无符号相加相同

两负,例如(-2) + (-3),用反码表示为0xfffd和0xfffc,按无符号相加本来应该是0xfff9,同样由于经过了0xffff,需要额外加1,也就是0xfffa,反码的-5。

我们可以把反码相加的规则总结如下:

把反码当作无符号16位整数相加, 如果产生了进位,则需要额外加1

这就是我们有时会在别的地方看到的反码求和的定义:无符号相加,将最高位的进位补到低位再次相加。

所以我们相应应该写出的程序是:

def checksum(data):

data_array = array.array('H',data)

s = 0

for d in data_array:

s += d

s = (s & 0xffff) + (s >> 16)

return (~s & 0xffff)

注意任意两个无符号16位整数的和,在产生进位的情况下,最大的结果是0xfffe(也就是0xffff加上0xffff),因此补加上额外的进位时,不会再次产生进位。

等等!我们并没有讨论大端小端的问题。

所谓大端,是指CPU处理多字节数据的时候,认为高位在前,低位在后。比如0x1234,表示成两个字节,就是0x12 0x34。而小端格式,在处理多字节数据的时候,低位在前,高位在后,0x1234会被表示成0x34 0x12。网络包规定的是按照大端格式解析,而你这句

array.array('H',data)

在Intel的CPU上,明明就是按小端解析的,算出来的结果能正确吗?

有意思的是&#xff0c;反码求和时&#xff0c;我们不需要考虑这些word是按大端存储的还是按小端存储的。我们按大端去读取求出的反码和&#xff0c;交换两个字节&#xff0c;正好与我们按小端去读取求出的反码和相等。证明很简单&#xff0c;考虑两个word相加&#xff0c;第一个word可以写作(a <<8) &#43; b&#xff0c;第二个word写作(c <<8) &#43; d&#xff0c;

则求和为(a &#43; c) <<8 &#43; (b &#43; d)

额外的进位为a &#43; c的8位加法产生的进位&#xff0c;会由反码求和规则加到低8位上&#xff1b;同时b &#43; d的8位加法会加到高8位上。也就是说&#xff0c;恰好低8位的进位加到了高8位上&#xff0c;而高8位的进位加到了低8位上。

如果按小端格式解析&#xff0c;两个数会变成(b <<8) &#43; a和(d <<8) &#43; c&#xff0c;不难发现高位变成了b &#43; d加低位的进位&#xff0c;而低位为a &#43; c加高位的进位&#xff0c;恰好是刚才的结果交换高8位与低8位。

正是因为反码加法的这个特性所以将这个算法选为了checksum的算法&#xff0c;这样无论是大端格式的CPU还是小端格式的CPU&#xff0c;都可以有效计算出相同的checksum。不过由于规定网络包中的数值按照大端格式存储&#xff0c;我们通常将算出的checksum统一转换为大端格式&#xff0c;也就是前面代码中最后的ntohs的作用。

接下来的问题是&#xff0c;为什么我们写的程序不是前面第二段&#xff0c;而是最早的第一段呢&#xff1f;

我们来重新考虑这个加上进位的操作&#xff0c;由于加法是可以交换的&#xff0c;我们可以把进位单独求和&#xff0c;然后最后一起加到16位数上&#xff1a;

def checksum(data):

data_array &#61; array.array(&#39;H&#39;,data)

s &#61; 0

s2 &#61; 0

for d in data_array:

s &#43;&#61; d

s2 &#43;&#61; (s >> 16)

s &#61; (s & 0xffff)

s &#43;&#61; s2

s &#61; (s & 0xffff) &#43; (s >> 16)

return (~s & 0xffff)将进位单独求和然后再加回16位数的过程也适用反码加法的规则&#xff0c;由于这个加法有可能产生新的进位&#xff0c;因此有一次额外的将进位累加回来的操作。当我们累加的word的数量小于65536时&#xff0c;进位单独累加的范围也在16位之内。由于限制IP报文的长度小于65536个字节&#xff0c;IP头更是需要小于64个字节&#xff0c;这个条件是很容易满足的。

我们用一个更聪明的办法&#xff0c;直接用32位无符号整数的高16位来存储这个进位的累加&#xff0c;这样只需要将16位的无符号加法直接变成32位的无符号加法&#xff0c;则我们刚才的s2就刚好是结果中32位的高16位&#xff0c;代码就可以进一步改写成&#xff1a;

def checksum(data):

data_array &#61; array.array(&#39;H&#39;,data)

s &#61; 0

for d in data_array:

s &#43;&#61; d

s &#61; (s & 0xffff) &#43; (s >> 16)

s &#61; (s & 0xffff) &#43; (s >> 16)

return (~s & 0xffff)考虑到最后取反的时候已经有截取16位整数的操作了&#xff0c;最后的第二次累积进位操作中可以不把高位置成0&#xff0c;留给最后的截取16位整数处理(在C中这个通过强制将32位数转换为16位数完成)&#xff1a;

def checksum(data):

data_array &#61; array.array(&#39;H&#39;,data)

s &#61; 0

for d in data_array:

s &#43;&#61; d

s &#61; (s & 0xffff) &#43; (s >> 16)

s &#43;&#61; (s >> 16)

return (~s & 0xffff)把for循环用sum函数改写&#xff0c;再加上额外单字节的处理和大端小端的处理&#xff0c;就成了最早的那段代码。仔细观察就会发现你这段代码除了笨重一点以外&#xff0c;和我这段代码的功能是相同的。

&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;

其实有个RFC专门写了这个算法

RFC 1071 - Computing the Internet checksum



推荐阅读
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 最近团队在部署DLP,作为一个技术人员对于黑盒看不到的地方还是充满了好奇心。多次咨询乙方人员DLP的算法原理是什么,他们都以商业秘密为由避而不谈,不得已只能自己查资料学习,于是有了下面的浅见。身为甲方,虽然不需要开发DLP产品,但是也有必要弄明白DLP基本的原理。俗话说工欲善其事必先利其器,只有在懂这个工具的原理之后才能更加灵活地使用这个工具,即使出现意外情况也能快速排错,越接近底层,越接近真相。根据DLP的实际用途,本文将DLP检测分为2部分,泄露关键字检测和近似重复文档检测。 ... [详细]
  • 本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]
  • 毕业设计:基于机器学习与深度学习的垃圾邮件(短信)分类算法实现
    本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程,并提供了具体的代码示例和实验结果。 ... [详细]
  • 深入解析Android自定义View面试题
    本文探讨了Android Launcher开发中自定义View的重要性,并通过一道经典的面试题,帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识,还提供了实际操作建议。 ... [详细]
  • 本文深入探讨了 Java 中的 Serializable 接口,解释了其实现机制、用途及注意事项,帮助开发者更好地理解和使用序列化功能。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
  • 本文介绍了如何在C#中启动一个应用程序,并通过枚举窗口来获取其主窗口句柄。当使用Process类启动程序时,我们通常只能获得进程的句柄,而主窗口句柄可能为0。因此,我们需要使用API函数和回调机制来准确获取主窗口句柄。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 尽管使用TensorFlow和PyTorch等成熟框架可以显著降低实现递归神经网络(RNN)的门槛,但对于初学者来说,理解其底层原理至关重要。本文将引导您使用NumPy从头构建一个用于自然语言处理(NLP)的RNN模型。 ... [详细]
  • 探索1000以内的完美数:因数和等于自身
    本文探讨了如何在1000以内找到所有完美数,即一个数的因数(不包括自身)之和等于该数本身。例如,6是一个完美数,因为1 + 2 + 3 = 6。通过编程实现这一过程,可以更好地理解完美数的特性。 ... [详细]
author-avatar
能P开普票j专G票q903095933
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有