RFC1071 日本語訳
1071 Computing the Internet checksum. R.T. Braden, D.A. Borman, C.Partridge. September 1988. (Format: TXT=54941 bytes) (Updated by RFC1141) (Status: UNKNOWN)
プログラムでの自動翻訳です。
RFC一覧
英語原文
Network Working Group R. Braden
Request for Comments: 1071 ISI
D. Borman
Cray Research
C. Partridge
BBN Laboratories
September 1988
コメントを求めるワーキンググループR.ブレーデン要求をネットワークでつないでください: 1071 ISI D.ボーマンクレイリサーチC.ヤマウズラBBN研究所1988年9月
Computing the Internet Checksum
インターネットチェックサムを計算します。
Status of This Memo
このメモの状態
This memo summarizes techniques and algorithms for efficiently computing the Internet checksum. It is not a standard, but a set of useful implementation techniques. Distribution of this memo is unlimited.
このメモは効率的にインターネットチェックサムを計算するためのテクニックとアルゴリズムをまとめます。 それは規格ではなく、1セットの役に立つ実現のテクニックです。 このメモの分配は無制限です。
1. Introduction
1. 序論
This memo discusses methods for efficiently computing the Internet checksum that is used by the standard Internet protocols IP, UDP, and TCP.
このメモは効率的に標準のインターネットのプロトコルIP、UDP、およびTCPによって使用されるインターネットチェックサムを計算するための方法について議論します。
An efficient checksum implementation is critical to good performance. As advances in implementation techniques streamline the rest of the protocol processing, the checksum computation becomes one of the limiting factors on TCP performance, for example. It is usually appropriate to carefully hand-craft the checksum routine, exploiting every machine-dependent trick possible; a fraction of a microsecond per TCP data byte can add up to a significant CPU time savings overall.
効率的なチェックサム実現は望ましい市場成果に重要です。 実現のテクニックにおける進歩がプロトコル処理の残りを能率化するのに従って、チェックサム計算は例えば、TCP性能のときに限定因子の1つになります。 通常、それが慎重に適切である、ハンドクラフト、可能なあらゆるマシン依存トリックを利用するチェックサムルーチン。 TCPデータ・バイトあたり1マイクロセカンドの何分の一は全体的に見て重要なCPU時間貯蓄を意味できます。
In outline, the Internet checksum algorithm is very simple:
アウトラインでは、インターネットチェックサムアルゴリズムは非常に簡単です:
(1) Adjacent octets to be checksummed are paired to form 16-bit
integers, and the 1's complement sum of these 16-bit integers is
formed.
(1) checksummedされるべき隣接している八重奏は16ビットの整数を形成するために対にされます、そして、これらの16ビットの整数の1の補数合計は形成されます。
(2) To generate a checksum, the checksum field itself is cleared,
the 16-bit 1's complement sum is computed over the octets
concerned, and the 1's complement of this sum is placed in the
checksum field.
(2) チェックサムを発生させるように、チェックサム分野自体はクリアされます、そして、16ビットの1の補数合計は関する八重奏の上に関して計算されます、そして、この合計の1の補数はチェックサム分野に置かれます。
(3) To check a checksum, the 1's complement sum is computed over the
same set of octets, including the checksum field. If the result
is all 1 bits (-0 in 1's complement arithmetic), the check
succeeds.
(3) チェックサムをチェックするために、1の補数合計は同じセットの八重奏に関して計算されます、チェックサム分野を含んでいて。 結果が1ビット(1の補数演算の-0)すべてなら、チェックは成功します。
Suppose a checksum is to be computed over the sequence of octets
チェックサムが八重奏の系列に関して計算されることであると仮定してください。
Braden, Borman, & Partridge [Page 1] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[1ページ]RFC1071
A, B, C, D, ... , Y, Z. Using the notation [a,b] for the 16-bit
integer a*256+b, where a and b are bytes, then the 16-bit 1's
complement sum of these bytes is given by one of the following:
A、B、C、D… , Y、Z.Using、16ビットの整数a*256+bのための記法[a、b]、次に、以下の1つでこれらのバイトの16ビットの1の補数合計を与えます:(そこでは、aとbがバイトです)。
[A,B] +' [C,D] +' ... +' [Y,Z] [1]
'+ '[A、B][C、D]+'… '+'[Y、Z][1]
[A,B] +' [C,D] +' ... +' [Z,0] [2]
'+ '[A、B][C、D]+'… '+'[Z、0][2]
where +' indicates 1's complement addition. These cases
correspond to an even or odd count of bytes, respectively.
'+が'では、1のものを示す添加の補足となってください。 これらのケースはそれぞれバイトの同等の、または、変なカウントに対応しています。
On a 2's complement machine, the 1's complement sum must be
computed by means of an "end around carry", i.e., any overflows
from the most significant bits are added into the least
significant bits. See the examples below.
2マシンの補数ものの上では、「エンドアラウンドキャリー」によって1の補数合計を計算しなければなりません、すなわち、最も重要なビットからのどんなオーバーフローも最下位ビットに追加されます。 以下の例を見てください。
Section 2 explores the properties of this checksum that may be
exploited to speed its calculation. Section 3 contains some
numerical examples of the most important implementation
techniques. Finally, Section 4 includes examples of specific
algorithms for a variety of common CPU types. We are grateful
to Van Jacobson and Charley Kline for their contribution of
algorithms to this section.
セクション2は計算を促進するのに利用されるかもしれないこのチェックサムの特性を探ります。 セクション3は最も重要な実現のテクニックのいくつかの数字の例を含みます。 最終的に、セクション4はさまざまな一般的なCPUタイプのための特定のアルゴリズムに関する例を含めます。 私たちはこのセクションへのアルゴリズムの彼らの貢献にヴァン・ジェーコブソンとCharleyクラインに感謝しています。
The properties of the Internet checksum were originally
discussed by Bill Plummer in IEN-45, entitled "Checksum Function
Design". Since IEN-45 has not been widely available, we include
it as an extended appendix to this RFC.
ビル・プラマーは元々、「チェックサム機能デザイン」の権利を与えられたIEN-45でインターネットチェックサムの特性について議論しました。 IEN-45が広く利用可能でないので、私たちは拡張付録としてこのRFCにそれを入れます。
2. Calculating the Checksum
2. チェックサムについて計算します。
This simple checksum has a number of wonderful mathematical
properties that may be exploited to speed its calculation, as we
will now discuss.
この簡単なチェックサムで、計算を促進するのに私たちが現在利用されるつもりであるように利用されるかもしれない多くの素晴らしい数学的な性質が議論します。
(A) Commutative and Associative
(A)交換可能であって、結合しやすいです。
As long as the even/odd assignment of bytes is respected, the
sum can be done in any order, and it can be arbitrarily split
into groups.
バイトの同等の、または、変な課題が尊敬される限り、順不同に合計できます、そして、任意にそれをグループに分けることができます。
For example, the sum [1] could be split into:
例えば、合計[1]を以下に分けることができました。
( [A,B] +' [C,D] +' ... +' [J,0] )
'(+ [A、B]'+ [C、D]'…+'[J、0])
+' ( [0,K] +' ... +' [Y,Z] ) [3]
'+ '+ [0、K]'…+'[Y、Z)[3]
Braden, Borman, & Partridge [Page 2] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[2ページ]RFC1071
(B) Byte Order Independence
(B) バイトオーダー独立
The sum of 16-bit integers can be computed in either byte order.
Thus, if we calculate the swapped sum:
どちらのバイトオーダーでも16ビットの整数の合計を計算できます。 したがって、私たちであるなら、交換された合計について計算してください:
[B,A] +' [D,C] +' ... +' [Z,Y] [4]
'+ '[B、A][D、C]+'… '+'[Z、Y][4]
the result is the same as [1], except the bytes are swapped in
the sum! To see why this is so, observe that in both orders the
carries are the same: from bit 15 to bit 0 and from bit 7 to bit
8. In other words, consistently swapping bytes simply rotates
the bits within the sum, but does not affect their internal
ordering.
結果はバイトを除いた[1]と合計で交換されていた状態で同じです! これがなぜそうであるかを確認するには、両方の命令では、桁上げが同じであることを観測してください: ビット15からビット0までビット7からビット8まで。 言い換えれば、一貫して単にバイトを交換する場合、ビットが合計の中で回転しますが、それらの内部の注文は影響されません。
Therefore, the sum may be calculated in exactly the same way
regardless of the byte order ("big-endian" or "little-endian")
of the underlaying hardware. For example, assume a "little-
endian" machine summing data that is stored in memory in network
("big-endian") order. Fetching each 16-bit word will swap
bytes, resulting in the sum [4]; however, storing the result
back into memory will swap the sum back into network byte order.
したがって、合計は下盛ハードウェアのバイトオーダー(「ビッグエンディアン」か「リトルエンディアン」)にかかわらずまさに同じように計算されるかもしれません。 例えば、ネットワーク(「ビッグエンディアン」)オーダーにメモリに格納されるデータをまとめる「少ないエンディアン」マシンを仮定してください。 それぞれの16ビットの単語をとって来ると、合計[4]をもたらして、バイトは交換されるでしょう。 しかしながら、結果をメモリに格納して戻すと、合計はネットワークバイトオーダーと交換して戻されるでしょう。
Byte swapping may also be used explicitly to handle boundary
alignment problems. For example, the second group in [3] can be
calculated without concern to its odd/even origin, as:
また、境界合せ問題を扱うのに明らかにバイトスワッピングを使用するかもしれません。例えば、以下として変であるか同等の起源への関心なしで[3]における2番目のグループについて計算できます。
[K,L] +' ... +' [Z,0]
'+ '[K、L]… +' [Z、0]
if this sum is byte-swapped before it is added to the first
group. See the example below.
この合計が以前バイトと交換されているなら、それは最初のグループに追加されます。 以下の例を見てください。
(C) Parallel Summation
(C) 平行な足し算
On machines that have word-sizes that are multiples of 16 bits,
it is possible to develop even more efficient implementations.
Because addition is associative, we do not have to sum the
integers in the order they appear in the message. Instead we
can add them in "parallel" by exploiting the larger word size.
16ビットの倍数である語長を持っているマシンでは、さらに効率的な実現を開発するのは可能です。 添加が結合しやすいので、私たちはそれらがメッセージで見えるオーダーにおける整数をまとめる必要はありません。 代わりに、私たちは、より大きい語長を利用することによって、「平行に」それらを加えることができます。
To compute the checksum in parallel, simply do a 1's complement
addition of the message using the native word size of the
machine. For example, on a 32-bit machine we can add 4 bytes at
a time: [A,B,C,D]+'... When the sum has been computed, we "fold"
the long sum into 16 bits by adding the 16-bit segments. Each
16-bit addition may produce new end-around carries that must be
added.
平行なチェックサムを計算するには、マシンの本来語サイズを使用することで単にメッセージの1の補数添加をしてください。 例えば、32ビットのマシンの上では、私たちは一度に4バイトを加えることができます: '+ '[A、B、C、D]… 合計を計算してあるとき、私たちは、16ビットのセグメントを加えることによって、長い合計を16ビットに「折り重ねます」。 加えなければならない添加が作り出すかもしれない各16ビットの新しいエンドアラウンドは運ばれます。
Furthermore, again the byte order does not matter; we could
instead sum 32-bit words: [D,C,B,A]+'... or [B,A,D,C]+'... and
then swap the bytes of the final 16-bit sum as necessary. See
the examples below. Any permutation is allowed that collects
その上、一方、バイトオーダーは重要ではありません。 私たちは代わりに32ビットの単語をまとめることができました: '+ '[D、C、B、A]…か[B、A、D、C]+'… そして、ベスト16ビットのバイトが必要に応じてまとめるスワッピング。 以下の例を見てください。 集まるどんな順列も許容されています。
Braden, Borman, & Partridge [Page 3] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[3ページ]RFC1071
all the even-numbered data bytes into one sum byte and the odd-
numbered data bytes into the other sum byte.
1合計バイトへのすべての偶数のデータ・バイトともう片方への変な番号付のデータ・バイトはバイトをまとめます。
There are further coding techniques that can be exploited to speed up the checksum calculation.
さらに、チェックサム計算を早くするために開発できるコーディング技法があります。
(1) Deferred Carries
延期された(1)は運びます。
Depending upon the machine, it may be more efficient to defer
adding end-around carries until the main summation loop is
finished.
マシンによって、メイン足し算の輪が完成するまでエンドアラウンドが運ばれると言い足しながら、それは延期するために、より効率的であるかもしれません。
One approach is to sum 16-bit words in a 32-bit accumulator, so
the overflows build up in the high-order 16 bits. This approach
typically avoids a carry-sensing instruction but requires twice
as many additions as would adding 32-bit segments; which is
faster depends upon the detailed hardware architecture.
1つのアプローチが32ビットのアキュムレータに16ビットの単語をまとめることであるので、オーバーフローは高位16ビットで増します。 このアプローチは、感じを運んでいる指示を通常避けますが、32ビットのセグメントを加えるように2倍の追加を必要とします。 どちらが、より速いかは詳細なハードウェア構造によります。
(2) Unwinding Loops
(2) 解くことは輪にされます。
To reduce the loop overhead, it is often useful to "unwind" the
inner sum loop, replicating a series of addition commands within
one loop traversal. This technique often provides significant
savings, although it may complicate the logic of the program
considerably.
輪のオーバーヘッドを下げるために、内側の合計輪が「解く」であることはしばしば役に立ちます、1つの輪の縦断の中で一連の添加命令を模写して。 プログラムの理論をかなり複雑にするかもしれませんが、このテクニックはしばしば重要な貯蓄を提供します。
(3) Combine with Data Copying
(3) コピーされるデータに結合してください。
Like checksumming, copying data from one memory location to
another involves per-byte overhead. In both cases, the
bottleneck is essentially the memory bus, i.e., how fast the
data can be fetched. On some machines (especially relatively
slow and simple micro-computers), overhead can be significantly
reduced by combining memory-to-memory copy and the checksumming,
fetching the data only once for both.
checksummingするように、1つの記憶域から別の記憶域までデータをコピーすると、1バイトあたりのオーバーヘッドは伴われます。 どちらの場合も、ボトルネックは本質的にはメモリバス、すなわち、どう速く、データをとって来ることができるかということです。 いくつかのマシン(特に比較的遅くて簡単なマイクロコンピュータ)では、メモリからメモリへのコピーとchecksummingを結合することによって、オーバーヘッドをかなり下げることができます、両方のために一度だけデータをとって来て。
(4) Incremental Update
(4) アップデート増加
Finally, one can sometimes avoid recomputing the entire checksum
when one header field is updated. The best-known example is a
gateway changing the TTL field in the IP header, but there are
other examples (for example, when updating a source route). In
these cases it is possible to update the checksum without
scanning the message or datagram.
最終的に、1つは、時々1つのヘッダーフィールドをアップデートするとき、全体のチェックサムを再計算するのを避けることができます。 最もよく知られている例はIPヘッダーのTTL分野を変えるゲートウェイですが、他の例があります(例えば送信元経路をアップデートするとき)。 これらの場合では、メッセージかデータグラムをスキャンしないでチェックサムをアップデートするのは可能です。
To update the checksum, simply add the differences of the
sixteen bit integers that have been changed. To see why this
works, observe that every 16-bit integer has an additive inverse
and that addition is associative. From this it follows that
given the original value m, the new value m', and the old
チェックサムをアップデートするには、単に変えられた16ビットの整数の違いを加えてください。 これがなぜ働くかを確認するには、あらゆる16ビットの整数に加法に関する逆元があって、添加が結合しやすいのを観測してください。 'これから、オリジナルの値のm、新しい値のmを考えて、それに続く'、および老人
Braden, Borman, & Partridge [Page 4] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[4ページ]RFC1071
checksum C, the new checksum C' is:
'チェックサムC、新しいチェックサムC'は以下の通りです。
C' = C + (-m) + m' = C + (m' - m)
'C'はC+(-m)+mと等しいこと'がC+と等しいです。'、(m、'、--、m)
3. Numerical Examples
3. 数字の例
We now present explicit examples of calculating a simple 1's complement sum on a 2's complement machine. The examples show the same sum calculated byte by bye, by 16-bits words in normal and swapped order, and 32 bits at a time in 3 different orders. All numbers are in hex.
私たちは現在、2マシンの補数ものの上で簡単な1の補数合計について計算する明白な例を提示します。 例は同じ合計がさようなら16ビットの単語で標準でバイトについて計算して、一度に3つの異なった命令で注文する、および32ビットスワップしたのを示します。 十六進法にはすべての数があります。
Byte-by-byte "Normal" Swapped
Order Order
バイトごとの「標準」はオーダー命令を交換しました。
Byte 0/1: 00 01 0001 0100
Byte 2/3: f2 03 f203 03f2
Byte 4/5: f4 f5 f4f5 f5f4
Byte 6/7: f6 f7 f6f7 f7f6
--- --- ----- -----
Sum1: 2dc 1f0 2ddf0 1f2dc
バイト0/1: 00 01 0001 0100バイト2/3: f2 03f203 03f2バイト4/5: f4 f5 f4f5 f5f4バイト6/7: f6 f7 f6f7 f7f6--- --- ----- ----- Sum1: 2dc 1f0 2ddf0 1f2dc
dc f0 ddf0 f2dc
Carrys: 1 2 2 1
-- -- ---- ----
Sum2: dd f2 ddf2 f2dd
dc f0 ddf0 f2dc Carrys: 1 2 2 1 -- -- ---- ---- Sum2: dd f2 ddf2 f2dd
Final Swap: dd f2 ddf2 ddf2
最終的なスワッピング: dd f2 ddf2 ddf2
Byte 0/1/2/3: 0001f203 010003f2 03f20100
Byte 4/5/6/7: f4f5f6f7 f5f4f7f6 f7f6f5f4
-------- -------- --------
Sum1: 0f4f7e8fa 0f6f4fbe8 0fbe8f6f4
バイト0/1/2/3: 0001f203 010003f2 03f20100バイト4/5/6/7: f4f5f6f7 f5f4f7f6 f7f6f5f4-------- -------- -------- Sum1: 0f4f7e8fa 0f6f4fbe8 0fbe8f6f4
Carries: 0 0 0
運びます: 0 0 0
Top half: f4f7 f6f4 fbe8
Bottom half: e8fa fbe8 f6f4
----- ----- -----
Sum2: 1ddf1 1f2dc 1f2dc
上半分: f4f7 f6f4 fbe8 Bottom半分: e8fa fbe8 f6f4----- ----- ----- Sum2: 1ddf1 1f2dc 1f2dc
ddf1 f2dc f2dc
Carrys: 1 1 1
---- ---- ----
Sum3: ddf2 f2dd f2dd
ddf1 f2dc f2dc Carrys: 1 1 1 ---- ---- ---- Sum3: ddf2 f2dd f2dd
Final Swap: ddf2 ddf2 ddf2
最終的なスワッピング: ddf2 ddf2 ddf2
Braden, Borman, & Partridge [Page 5] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[5ページ]RFC1071
Finally, here an example of breaking the sum into two groups, with the second group starting on a odd boundary:
最終的に、ここで、2番目のグループが変な境界を始めていて、合計を2に細かく分ける例は分類されます:
Byte-by-byte Normal
Order
バイトごとの通常のオーダー
Byte 0/1: 00 01 0001
Byte 2/ : f2 (00) f200
--- --- -----
Sum1: f2 01 f201
バイト0/1: 00 01 0001バイト2/: f2(00)f200--- --- ----- Sum1: f2 01f201
Byte 4/5: 03 f4 03f4
Byte 6/7: f5 f6 f5f6
Byte 8/: f7 (00) f700
--- --- -----
Sum2: 1f0ea
バイト4/5: 03 f4 03f4バイト6/7: f5 f6 f5f6バイト8/: f7(00)f700--- --- ----- Sum2: 1f0ea
Sum2: f0ea
Carry: 1
-----
Sum3: f0eb
Sum2: f0ea Carry: 1 ----- Sum3: f0eb
Sum1: f201
Sum3 byte swapped: ebf0
-----
Sum4: 1ddf1
Sum1: f201 Sum3バイトはスワップされました: ebf0----- Sum4: 1ddf1
Sum4: ddf1
Carry: 1
-----
Sum5: ddf2
Sum4: ddf1 Carry: 1 ----- Sum5: ddf2
Braden, Borman, & Partridge [Page 6] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[6ページ]RFC1071
4. Implementation Examples
4. 実現の例
In this section we show examples of Internet checksum implementation algorithms that have been found to be efficient on a variety of CPU's. In each case, we show the core of the algorithm, without including environmental code (e.g., subroutine linkages) or special- case code.
このセクションで、私たちは、CPUのさまざまなところに見つけられたインターネットチェックサム実現アルゴリズムの例が効率的であることを示します。 その都度、私たちはアルゴリズムのコアを示しています、環境コード(例えば、サブルーチンリンケージ)か特別なケースコードを含んでいなくて。
4.1 "C"
4.1 「C」
The following "C" code algorithm computes the checksum with an inner loop that sums 16-bits at a time in a 32-bit accumulator.
以下の「C」コードアルゴリズムは一度に32ビットのアキュムレータに16ビットをまとめる内側の輪があるチェックサムを計算します。
in 6
{
/* Compute Internet Checksum for "count" bytes
* beginning at location "addr".
*/
register long sum = 0;
6、/*は位置の"addr" */レジスタで始まる「カウント」長さバイト*の合計=0のためにインターネットChecksumを計算します。
while( count > 1 ) {
/* This is the inner loop */
sum += * (unsigned short) addr++;
count -= 2;
}
(カウント>1)をゆったり過ごしてください。より多くのinの/*は*/合計+=*(無記名のショート)addr++を輪にします; カウント-=2
/* Add left-over byte, if any */
if( count > 0 )
sum += * (unsigned char *) addr;
/*は残りのバイトを加えて、+はどんな*/であるならも(>0を数えます)合計であるなら*(無記名の炭*)addrと等しいです。
/* Fold 32-bit sum to 16 bits */
while (sum>>16)
sum = (sum & 0xffff) + (sum >> 16);
16ビット*/への/*折り目の32ビットの合計は(合計>>16)合計である間、(合計と0xffff)+(合計>>16)と等しいです。
checksum = ~sum;
}
チェックサムは~合計と等しいです。 }
Braden, Borman, & Partridge [Page 7] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[7ページ]RFC1071
4.2 Motorola 68020
4.2 モトローラ68020
The following algorithm is given in assembler language for a Motorola 68020 chip. This algorithm performs the sum 32 bits at a time, and unrolls the loop with 16 replications. For clarity, we have omitted the logic to add the last fullword when the length is not a multiple of 4. The result is left in register d0.
モトローラ68020チップのためにアセンブラ言語で以下のアルゴリズムを与えます。 このアルゴリズムは、合計を一度に32ビット実行して、16の模写で輪を広げます。 明快ために、私たちは長さが4の倍数でないときに最後のfullwordを加える論理を省略しました。 結果はレジスタd0に残されます。
With a 20MHz clock, this routine was measured at 134 usec/kB summing random data. This algorithm was developed by Van Jacobson.
20MHzの時計で、このルーチンは無作為のデータをまとめる134usec/kBで測定されました。 このアルゴリズムはヴァン・ジェーコブソンによって開発されました。
movl d1,d2
lsrl #6,d1 | count/64 = # loop traversals
andl #0x3c,d2 | Then find fractions of a chunk
negl d2
andb #0xf,cc | Clear X (extended carry flag)
movl d1、d2 lsrl#6、d1| カウント/64=#輪の縦断andl#0x3c、d2| そして、塊negl d2 andb#0xfの部分、ccを見つけてください。| 明確なX(拡張キャリーフラグ)
jmp pc@(2$-.-2:b,d2) | Jump into loop
jmp pc@(2$-.-2: b、d2)| 輪に飛びついてください。
1$: | Begin inner loop...
1$: | 内側の輪を始めてください…
movl a0@+,d2 | Fetch 32-bit word
addxl d2,d0 | Add word + previous carry
movl a0@+,d2 | Fetch 32-bit word
addxl d2,d0 | Add word + previous carry
movl a0@+、d2| 32ビットの単語addxl d2、d0をとって来てください。| 単語+前のキャリーmovl a0@+、d2を加えてください。| 32ビットの単語addxl d2、d0をとって来てください。| 単語+前のキャリーを加えてください。
| ... 14 more replications
2$:
dbra d1,1$ | (NB- dbra doesn't affect X)
| ... もう14の模写2ドル: dbra d1、1ドル| (ネブラスカdbraはXに影響しません)
movl d0,d1 | Fold 32 bit sum to 16 bits
swap d1 | (NB- swap doesn't affect X)
addxw d1,d0
jcc 3$
addw #1,d0
3$:
andl #0xffff,d0
movl d0、d1| 16ビットのスワッピングd1への折り目の32ビットの合計| (ネブラスカスワッピングはXに影響しません) addxw d1、d0 jcc3ドルaddw#1、d0 3$: andl#0xffff、d0
Braden, Borman, & Partridge [Page 8] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[8ページ]RFC1071
4.3 Cray
4.3 クレイ
The following example, in assembler language for a Cray CPU, was contributed by Charley Kline. It implements the checksum calculation as a vector operation, summing up to 512 bytes at a time with a basic summation unit of 32 bits. This example omits many details having to do with short blocks, for clarity.
クレイCPUへのアセンブラ言語では、以下の例はCharleyクラインによって寄付されました。 それはベクトル演算としてチェックサム計算を実行します、32ビットの基本的な足し算の単位で一度に最大512バイトをまとめて。 この例は明快ために短ブロックと関係がある多くの詳細を省略します。
Register A1 holds the address of a 512-byte block of memory to checksum. First two copies of the data are loaded into two vector registers. One is vector-shifted right 32 bits, while the other is vector-ANDed with a 32 bit mask. Then the two vectors are added together. Since all these operations chain, it produces one result per clock cycle. Then it collapses the result vector in a loop that adds each element to a scalar register. Finally, the end-around carry is performed and the result is folded to 16-bits.
レジスタA1はメモリの512バイトのブロックのアドレスをチェックサムとして保持します。 まず最初に、データのコピー2部は2つのベクトルレジスタに積み込まれます。 1つはベクトルによって右の32ビット移行されていますが、もう片方が32ビットのマスクがあるベクトル-ANDedです。 そして、2つのベクトルが合計されます。 これらのすべての操作が鎖を作るので、それは1クロック周期あたり1つの結果を生みます。 そして、それは各要素をスカラのレジスタに追加する輪の結果ベクトルを潰します。 最終的に、エンドアラウンドキャリーは実行されます、そして、結果は16ビットに折り重ねられます。
EBM
A0 A1
VL 64 use full vectors
S1 <32 form 32-bit mask from the right.
A2 32
V1 ,A0,1 load packet into V1
V2 S1&V1 Form right-hand 32-bits in V2.
V3 V1>A2 Form left-hand 32-bits in V3.
V1 V2+V3 Add the two together.
A2 63 Prepare to collapse into a scalar.
S1 0
S4 <16 Form 16-bit mask from the right.
A4 16
CK$LOOP S2 V1,A2
A2 A2-1
A0 A2
S1 S1+S2
JAN CK$LOOP
S2 S1&S4 Form right-hand 16-bits in S2
S1 S1>A4 Form left-hand 16-bits in S1
S1 S1+S2
S2 S1&S4 Form right-hand 16-bits in S2
S1 S1>A4 Form left-hand 16-bits in S1
S1 S1+S2
S1 #S1 Take one's complement
CMR At this point, S1 contains the checksum.
EBM A0 A1 VL64は右から完全なベクトルS1<32のフォームの32ビットのマスクを使用します。 A2 32V1、A0、V2の32ビットのV1 V2 S1&V1 Form右手への1つの負荷パケット。 V3 V1の>のA2 Formの左手の32ビットのV3。 V1 V2+V3は2を合計します。 スカラまで崩れるA2 63Prepare。 S1 0 S4<16は右から16ビットのマスクを形成します。 A4 16CKドルのLOOP S2 V1、S2 JAN CK$LOOP S2 S1&S4 Form A2 A2 A2-1 A0 A2 S1 S1+右手のS2 S1 S1>A4 Formの16ビットの左手の16ビットのS1 S1 S1+S2 S2 S1、およびS4 FormはS2 S1 S1のA4 Formの左手のS1 S1 S1+S2 S1の16ビットの#S1 Take>1の補数における16ビットのCMR Atにこのポイントを権利で手渡して、S1はチェックサムを含んでいます。
Braden, Borman, & Partridge [Page 9] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[9ページ]RFC1071
4.4 IBM 370
4.4 IBM370
The following example, in assembler language for an IBM 370 CPU, sums the data 4 bytes at a time. For clarity, we have omitted the logic to add the last fullword when the length is not a multiple of 4, and to reverse the bytes when necessary. The result is left in register RCARRY.
IBM370CPUへのアセンブラ言語では、以下の例はデータを一度に4バイトまとめます。 必要であるときに、明快ために、私たちは長さが4の倍数でないときに、最後のfullwordを加えて、バイトを逆にする論理を省略しました。 結果はレジスタRCARRYに残されます。
This code has been timed on an IBM 3090 CPU at 27 usec/KB when summing all one bits. This time is reduced to 24.3 usec/KB if the trouble is taken to word-align the addends (requiring special cases at both the beginning and the end, and byte-swapping when necessary to compensate for starting on an odd byte).
すべての1ビットをまとめるとき、このコードは27usec/KBの3090年のIBM CPUの上に調節されました。 加数(補うのに必要であるときに、始めと終わりとバイトスワッピングの両方で特別なケースを必要とします1奇数バイトが始めである)がわざわざ単語で並べられるなら、今回は24.3usec/KBまで減少します。
* Registers RADDR and RCOUNT contain the address and length of
* the block to be checksummed.
*
* (RCARRY, RSUM) must be an even/odd register pair.
* (RCOUNT, RMOD) must be an even/odd register pair.
*
CHECKSUM SR RSUM,RSUM Clear working registers.
SR RCARRY,RCARRY
LA RONE,1 Set up constant 1.
*
SRDA RCOUNT,6 Count/64 to RCOUNT.
AR RCOUNT,RONE +1 = # times in loop.
SRL RMOD,26 Size of partial chunk to RMOD.
AR RADDR,R3 Adjust addr to compensate for
S RADDR,=F(64) jumping into the loop.
SRL RMOD,1 (RMOD/4)*2 is halfword index.
LH RMOD,DOPEVEC9(RMOD) Use magic dope-vector for offset,
B LOOP(RMOD) and jump into the loop...
*
* Inner loop:
*
LOOP AL RSUM,0(,RADDR) Add Logical fullword
BC 12,*+6 Branch if no carry
AR RCARRY,RONE Add 1 end-around
AL RSUM,4(,RADDR) Add Logical fullword
BC 12,*+6 Branch if no carry
AR RCARRY,RONE Add 1 end-around
*
* ... 14 more replications ...
*
A RADDR,=F'64' Increment address ptr
BCT RCOUNT,LOOP Branch on Count
*
* Add Carries into sum, and fold to 16 bits
*
ALR RCARRY,RSUM Add SUM and CARRY words
BC 12,*+6 and take care of carry
* レジスタのRADDRとRCOUNTはアドレスを含んでいます、そして、*の長さはchecksummedされるべきブロックを含んでいます。 * * (RCARRY、RSUM) 同等の、または、変なレジスタ対はそうであるに違いありませんか? * (RCOUNT、RMOD) 同等の、または、変なレジスタ対はそうであるに違いありませんか? * CHECKSUM SR RSUM、RSUM Clearの働きは登録されます。 SR RCARRY、RCARRY LA RONE、一定の1への1Set。 * SRDA RCOUNT、RCOUNTへの6カウント/64。 輪の#AR RCOUNT、RONE+1=回。 SRL RMOD、RMODへの部分的な塊の26Size。 AR RADDR(S RADDRを補うR3 Adjust addr)は、(64) 輪に飛びつきながら、Fと等しいです。 SRL RMOD、1(RMOD/4)*2がhalfwordインデックスです。 LH RMOD、DOPEVEC9(RMOD)が、オフセット、B LOOP(RMOD)に魔法のドーピングベクトルを使用して、輪に飛びつきます… * * 内側の輪: * LOOP AL RSUM、0(RADDR)はLogical fullword紀元前12年を加えて、*+6 支店はいいえならAR RCARRYを運んで、RONE Add1エンドアラウンドAL RSUM、4(RADDR)はLogical fullword紀元前12年を加えて、*+6 支店はいいえならAR RCARRYを運びます、RONE Add1エンドアラウンド**… もう14の模写… * '= RADDR、F64年'Incrementアドレスptr BCT RCOUNT、Count**のLOOP支店は合計にキャリーを加えて、16ビット*ALR RCARRY、RSUM Add SUM、およびCARRY単語紀元前12年まで折り重なって、+6と撮影が気にかける*は運ばれます。
Braden, Borman, & Partridge [Page 10] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[10ページ]RFC1071
AR RCARRY,RONE
SRDL RCARRY,16 Fold 32-bit sum into
SRL RSUM,16 16-bits
ALR RCARRY,RSUM
C RCARRY,=X'0000FFFF' and take care of any
BNH DONE last carry
S RCARRY,=X'0000FFFF'
DONE X RCARRY,=X'0000FFFF' 1's complement
'AR RCARRY、RONE SRDL RCARRY、SRL RSUMへの16のFoldの32ビットの合計、16 16ビットのALR RCARRY(RSUM C RCARRY)はX'0000FFFF'と等しく、S RCARRYが最後に運ぶことにどんなBNH DONEにも注意します、=X'0000FFFF'DONE X RCARRY、=X'0000FFFF'1の補数
Braden, Borman, & Partridge [Page 11] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[11ページ]RFC1071
IEN 45
Section 2.4.4.5
IEN45部2.4 .4 .5
TCP Checksum Function Design
TCPチェックサム機能デザイン
William W. Plummer
ウィリアム・W.プラマー
Bolt Beranek and Newman, Inc.
50 Moulton Street
Cambridge MA 02138
ボルトBeranekとニューマンInc.50モールトン通りケンブリッジMA 02138
5 June 1978
1978年6月5日
Braden, Borman, & Partridge [Page 12] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[12ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
1. Introduction
1. 序論
Checksums are included in packets in order that errors
encountered during transmission may be detected. For Internet
protocols such as TCP [1,9] this is especially important because
packets may have to cross wireless networks such as the Packet
Radio Network [2] and Atlantic Satellite Network [3] where
packets may be corrupted. Internet protocols (e.g., those for
real time speech transmission) can tolerate a certain level of
transmission errors and forward error correction techniques or
possibly no checksum at all might be better. The focus in this
paper is on checksum functions for protocols such as TCP where
the required reliable delivery is achieved by retransmission.
チェックサムは、トランスミッションの間に遭遇する誤りを検出できるようにパケットに含まれています。 TCP[1、9]などのインターネットプロトコルにおいて、パケットがPacket Radio Network[2]や大西洋Satellite Network[3]などのワイヤレス・ネットワークをパケットが崩壊するかもしれないところに越えなければならないかもしれないので、これは特に重要です。 インターネットプロトコル(例えば、リアルタイムのスピーチ送信のためのそれら)はあるレベルの伝送エラーを許容できます、そして、前進型誤信号訂正のテクニックにもかかわらず、ことによると全くどんなチェックサムもより良くないかもしれません。 この紙の焦点が必要な信頼できる配信が「再-トランスミッション」によって達成されるTCPなどのプロトコルのためのチェックサム機能にあります。
Even if the checksum appears good on a message which has been
received, the message may still contain an undetected error. The
probability of this is bounded by 2**(-C) where C is the number
of checksum bits. Errors can arise from hardware (and software)
malfunctions as well as transmission errors. Hardware induced
errors are usually manifested in certain well known ways and it
is desirable to account for this in the design of the checksum
function. Ideally no error of the "common hardware failure" type
would go undetected.
チェックサムが受け取られたメッセージで良く見えても、メッセージはまだ非検出された誤りを含んでいるかもしれません。 この確率は2時までに**(-C) Cがチェックサムビットの数であるところで境界があります。 誤りは伝送エラーと同様にハードウェア(そして、ソフトウェア)不調から起こることができます。 通常、ハードウェアの誘発された誤りはあるよく知られている方法で表されます、そして、チェックサム機能のデザインでこれを説明するのは望ましいです。 理想的に「一般的なハードウェアの故障」タイプの誤りは全く察知されずにいないでしょう。
An example of a failure that the current checksum function
handles successfully is picking up a bit in the network interface
(or I/O buss, memory channel, etc.). This will always render the
checksum bad. For an example of how the current function is
inadequate, assume that a control signal stops functioning in the
network interface and the interface stores zeros in place of the
real data. These "all zero" messages appear to have valid
checksums. Noise on the "There's Your Bit" line of the ARPANET
Interface [4] may go undetected because the extra bits input may
cause the checksum to be perturbed (i.e., shifted) in the same
way as the data was.
現在のチェックサム機能が首尾よく扱う失敗に関する例はネットワーク・インターフェース(または、入出力荷舟、メモリ・チャンネルなど)で少し回復しています。 これはいつもチェックサムを悪くするでしょう。 流れ関数がどう不十分であるかに関する例に関しては、制御信号が、ネットワーク・インターフェースで機能するのを止めて、インタフェースが本当のデータに代わってゼロを格納すると仮定してください。 「すべてのゼロ」が通信させるこれらは有効なチェックサムを持っているように見えます。「あなたのビットがある」というアルパネットInterface[4]の台詞における雑音は、データと同様に余分なビット入力でチェックサムを混乱させるかもしれないので(すなわち、移行します)、察知されずにいるかもしれません。
Although messages containing undetected errors will occasionally
be passed to higher levels of protocol, it is likely that they
will not make sense at that level. In the case of TCP most such
messages will be ignored, but some could cause a connection to be
aborted. Garbled data could be viewed as a problem for a layer
of protocol above TCP which itself may have a checksuming scheme.
非検出された誤りを含むメッセージが時折より高いレベルのプロトコルに通過されるでしょうが、それらはおまけに、レベルを理解できそうにないでしょう。 TCPの場合では、そのようなほとんどのメッセージが無視されるでしょうが、或るもので、接続を中止できました。 プロトコルの層のための問題としてchecksuming計画を持っているかもしれないTCP自身の上で誤り伝えられたデータを見なすことができました。
This paper is the first step in design of a new checksum function
for TCP and some other Internet protocols. Several useful
properties of the current function are identified. If possible
この紙はTCPのための新しいチェックサム機能とある他のインターネットプロトコルのデザインで第一歩です。 流れ関数の数個の役に立つ特性が特定されます。 できれば
- 1 -
- 1 -
Braden, Borman, & Partridge [Page 13] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[13ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
these should be retained in any new function. A number of
plausible checksum schemes are investigated. Of these only the
"product code" seems to be simple enough for consideration.
これらはどんな新しい機能でも保有されるべきです。 多くのもっともらしいチェックサム計画が調査されます。 これらだけでは、「製品コード」は考慮に十分簡単であるように思えます。
2. The Current TCP Checksum Function
2. 現在のTCPチェックサム機能
The current function is oriented towards sixteen-bit machines
such as the PDP-11 but can be computed easily on other machines
(e.g., PDP-10). A packet is thought of as a string of 16-bit
bytes and the checksum function is the one's complement sum (add
with end-around carry) of those bytes. It is the one's
complement of this sum which is stored in the checksum field of
the TCP header. Before computing the checksum value, the sender
places a zero in the checksum field of the packet. If the
checksum value computed by a receiver of the packet is zero, the
packet is assumed to be valid. This is a consequence of the
"negative" number in the checksum field exactly cancelling the
contribution of the rest of the packet.
流れ関数をPDP-11などの16ビットのマシンに向かって適応しますが、他のマシン(例えば、PDP-10)の上で容易に計算できます。 パケットは一連の16ビットのバイトとして考えられます、そして、チェックサム機能はそれらのバイトの1の補数合計(エンドアラウンドで、運ぶように言い足す)です。 それはTCPヘッダーのチェックサム分野に格納されるこの合計の1の補数です。 チェックサム値を計算する前に、送付者はパケットのチェックサム分野にゼロを置きます。 パケットの受信機によって計算されたチェックサム値がゼロであるなら、パケットが有効であると思われます。 これはチェックサム分野の「否定的な」数がまさにパケットの残りの貢献を中止する結果です。
Ignoring the difficulty of actually evaluating the checksum
function for a given packet, the way of using the checksum
described above is quite simple, but it assumes some properties
of the checksum operator (one's complement addition, "+" in what
follows):
与えられたパケットのために実際にチェックサム機能を評価するという困難を無視して、上で説明されたチェックサムを使用する方法はかなり簡単ですが、チェックサムオペレータ(1の補数添加、続くことにおける「+」)のいくつかの特性を仮定します:
(P1) + is commutative. Thus, the order in which
the 16-bit bytes are "added" together is
unimportant.
(P1) +は交換可能です。 したがって、16ビットのバイトが一緒に「加えられる」オーダーは重要ではありません。
(P2) + has at least one identity element (The
current function has two: +0 and -0). This
allows the sender to compute the checksum
function by placing a zero in the packet checksum
field before computing the value.
(P2)+には、少なくとも1つのアイデンティティ要素があります。(流れ関数に、2があります:、+0と-0) これで、送付者は、値を計算する前にパケットチェックサム分野にゼロを置くことによって、チェックサム機能を計算できます。
(P3) + has an inverse. Thus, the receiver may
evaluate the checksum function and expect a zero.
(P3) +には、逆があります。 したがって、受信機は、チェックサム機能を評価して、ゼロを期待するかもしれません。
(P4) + is associative, allowing the checksum field
to be anywhere in the packet and the 16-bit bytes
to be scanned sequentially.
(P4) +は結合しやすいです、連続してスキャンされるためにチェックサム分野がパケットと16ビットのバイトでどこでもあるのを許容して。
Mathematically, these properties of the binary operation "+" over
the set of 16-bit numbers forms an Abelian group [5]. Of course,
there are many Abelian groups but not all would be satisfactory
for use as checksum operators. (Another operator readily
数学的に、16ビットの数のセットのブール演算「+」のこれらの特性はアーベル群[5]を形成します。 もちろん、多くのアーベル群がありますが、使用において、すべてがチェックサムオペレータとして満足できるというわけではないでしょう。 (別のオペレータ、容易
- 2 -
- 2 -
Braden, Borman, & Partridge [Page 14] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[14ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
available in the PDP-11 instruction set that has all of these
properties is exclusive-OR, but XOR is unsatisfactory for other
reasons.)
これらの特性のすべてを持っているPDP-11命令セットで利用可能であるのが、排他的論理和ですが、XORは他の理由で不十分です。)
Albeit imprecise, another property which must be preserved in any
future checksum scheme is:
不正確ですが、どんな将来のチェックサム計画でも保持しなければならない別の特性は以下の通りです。
(P5) + is fast to compute on a variety of machines
with limited storage requirements.
(P5) +はさまざまなマシンの上で限られた格納要件で計算するのにおいて速いです。
The current function is quite good in this respect. On the
PDP-11 the inner loop looks like:
流れ関数はこの点でかなり良いです。 PDP-11では、内側の輪に似ています:
LOOP: ADD (R1)+,R0 ; Add the next 16-bit byte
ADC R0 ; Make carry be end-around
SOB R2,LOOP ; Loop over entire packet.
以下を輪にしてください。 R0、+を加えてください(R1)。 次の16ビットのバイトADC R0を加えてください。 エンドアラウンドがSOB R2、LOOPであったなら、運ばせます。 全体のパケットの上で輪にしてください。
( 4 memory cycles per 16-bit byte )
(16ビットのバイトあたり4メモリサイクル)
On the PDP-10 properties P1-4 are exploited further and two
16-bit bytes per loop are processed:
PDP-10所有地の上では、P1-4はさらに利用されます、そして、1輪あたり16ビットの2バイトは処理されます:
LOOP: ILDB THIS,PTR ; Get 2 16-bit bytes
ADD SUM,THIS ; Add into current sum
JUMPGE SUM,CHKSU2 ; Jump if fewer than 8 carries
LDB THIS,[POINT 20,SUM,19] ; Get left 16 and carries
ANDI SUM,177777 ; Save just low 16 here
ADD SUM,THIS ; Fold in carries
CHKSU2: SOJG COUNT,LOOP ; Loop over entire packet
以下を輪にしてください。 ILDB、これ、PTR。 ADD SUM、THISを16ビットの2バイト手に入れてください。 現在の合計JUMPGE SUM、CHKSU2に加えてください。 LDB THIS、[POINT20、SUM、19]をジャンプは8未満であるなら運びます。 16に残されて、ANDI SUM、177777を運びます。 ここでちょうど低い16を救ってください、ADD SUM、THIS。 折り目は中までCHKSU2を運びます: SOJGは数えて、輪にしてください。 全体のパケットの上で輪にしてください。
( 3.1 memory cycles per 16-bit byte )
(16ビットのバイトあたり3.1メモリサイクル)
The "extra" instruction in the loops above are required to
convert the two's complement ADD instruction(s) into a one's
complement add by making the carries be end-around. One's
complement arithmetic is better than two's complement because it
is equally sensitive to errors in all bit positions. If two's
complement addition were used, an even number of 1's could be
dropped (or picked up) in the most significant bit channel
without affecting the value of the checksum. It is just this
property that makes some sort of addition preferable to a simple
exclusive-OR which is frequently used but permits an even number
of drops (pick ups) in any bit channel. RIM10B paper tape format
used on PDP-10s [10] uses two's complement add because space for
the loader program is extremely limited.
上の輪における「余分な」指示が、桁上げがエンドアラウンドであることを作ることによって1の補数へのADD指示が加える2の補数を変換するのに必要です。 それが等しくすべてのビット位置の誤りに敏感であるので、1の補数演算は2の補数より良いです。 2の補数添加が使用されるなら、チェックサムの値に影響しないで、最も重要な噛み付いているチャンネルで1の偶数を落とすことができるでしょう(または、拾われます)。 それはただある種の頻繁に使用される簡単な排他的論理和より望ましい添加にもかかわらず、どんなビットの偶数の数の低下(拾う)もチャネルを開設する許可証を作るこの特性です。 荷物を積む人プログラムのためのスペースが非常に限られているので、[10]が使用する10PDP-年代の2の補数で使用されるRIM10B紙テープ書式は加えます。
- 3 -
- 3 -
Braden, Borman, & Partridge [Page 15] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[15ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
Another property of the current checksum scheme is:
現在のチェックサム計画の別の特性は以下の通りです。
(P6) Adding the checksum to a packet does not change
the information bytes. Peterson [6] calls this a
"systematic" code.
(P6) チェックサムを加えて、パケットに、情報バイトは変化していません。 ピーターソン[6]は、これを「系統的な」コードと呼びます。
This property allows intermediate computers such as gateway
machines to act on fields (i.e., the Internet Destination
Address) without having to first decode the packet. Cyclical
Redundancy Checks used for error correction are not systematic
either. However, most applications of CRCs tend to emphasize
error detection rather than correction and consequently can send
the message unchanged, with the CRC check bits being appended to
the end. The 24-bit CRC used by ARPANET IMPs and Very Distant
Host Interfaces [4] and the ANSI standards for 800 and 6250 bits
per inch magnetic tapes (described in [11]) use this mode.
この特性で、最初にパケットを解読する必要はなくて、ゲートウェイマシンなどの中間的コンピュータは分野(すなわち、インターネットDestination Address)に影響できます。 エラー修正に使用される周期的なRedundancy Checksは系統的ではありません。 しかしながら、CRCsのほとんどのアプリケーションが、修正よりむしろ誤り検出を強調する傾向があって、その結果、変わりがない状態でメッセージを送ることができます、終わりまでCRCチェックビットを追加していて。 24ビットのCRCはアルパネットでIMPsを使用しました、そして、Very Distant Host Interfacesは[4]と800と6250のビット/インチ磁気テープのANSI規格を使用しました。([11]) 使用で、このモードを説明しました。
Note that the operation of higher level protocols are not (by
design) affected by anything that may be done by a gateway acting
on possibly invalid packets. It is permissible for gateways to
validate the checksum on incoming packets, but in general
gateways will not know how to do this if the checksum is a
protocol-specific feature.
より高い平らなプロトコルの操作が(故意に)ことによると無効のパケットに影響するゲートウェイでするかもしれないことで影響を受けないことに注意してください。 ゲートウェイが入って来るパケットの上でチェックサムを有効にするのが、許されていますが、一般に、ゲートウェイはチェックサムがプロトコル特有の特徴であるならこれをする方法を知らないでしょう。
A final property of the current checksum scheme which is actually
a consequence of P1 and P4 is:
実際にP1とP4の結果である現在のチェックサム計画の最終的な特性は以下の通りです。
(P7) The checksum may be incrementally modified.
(P7) チェックサムは増加して変更されるかもしれません。
This property permits an intermediate gateway to add information
to a packet, for instance a timestamp, and "add" an appropriate
change to the checksum field of the packet. Note that the
checksum will still be end-to-end since it was not fully
recomputed.
この特性は、中間ゲートウェイがパケット、例えば、タイムスタンプに情報を追加して、パケットのチェックサム分野に適切な変化を「加えること」を可能にします。 それが完全に再計算されたというわけではないのでチェックサムがまだ終わらせる終わりになっていることに注意してください。
3. Product Codes
3. 製品コード
Certain "product codes" are potentially useful for checksuming
purposes. The following is a brief description of product codes
in the context of TCP. More general treatment can be found in
Avizienis [7] and probably other more recent works.
ある「製品コード」は潜在的にchecksuming目的の役に立ちます。 ↓これはTCPの文脈で、製品コードの簡単な説明です。 Avizienis[7]とたぶん他の、より多くの近作で、より一般的な処理を見つけることができます。
The basic concept of this coding is that the message (packet) to
be sent is formed by transforming the original source message and
adding some "check" bits. By reading this and applying a
(possibly different) transformation, a receiver can reconstruct
このコード化に関する基本概念は送られるべきメッセージ(パケット)が一次資料メッセージを変えて、いくつかの「チェック」ビットを加えることによって形成されるということです。 これと(ことによると異なる)の変化を適用する受信機が再建できる読書で
- 4 -
- 4 -
Braden, Borman, & Partridge [Page 16] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[16ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
the original message and determine if it has been corrupted
during transmission.
オリジナルは、通信して、それがトランスミッションの間、腐敗しているかどうか決定します。
Mo Ms Mr
Moさんさん
----- ----- -----
| A | code | 7 | decode | A |
| B | ==> | 1 | ==> | B |
| C | | 4 | | C |
----- |...| -----
| 2 | check plus "valid" flag
----- info
----- ----- ----- | A| コード| 7 | 解読してください。| A| | B| ==>| 1| ==>| B| | C| | 4 | | C| ----- |...| ----- | 2 | そのうえ、「有効な」旗をチェックしてください。----- インフォメーション
Original Sent Reconstructed
再建されていた状態で送られたオリジナル
With product codes the transformation is Ms = K * Mo . That is,
the message sent is simply the product of the original message
Mo and some well known constant K . To decode, the received
Ms is divided by K which will yield Mr as the quotient and
0 as the remainder if Mr is to be considered the same as Mo .
製品コードで、変化は=Mo K*さんです。すなわち、送られたメッセージは単にオリジナルのメッセージMoと何らかのよく知られている一定のKの製品です。解読するために、さんがMoであると同じようにみなされるつもりであるなら、商と0としてさんをもたらすKは残りとして容認されたさんに割られます。
The first problem is selecting a "good" value for K, the "check
factor". K must be relatively prime to the base chosen to
express the message. (Example: Binary messages with K
incorrectly chosen to be 8. This means that Ms looks exactly
like Mo except that three zeros have been appended. The only
way the message could look bad to a receiver dividing by 8 is if
the error occurred in one of those three bits.)
第1の問題はK、「チェック要素」のために「良い」値を選択しています。 メッセージを言い表すために選ばれて、Kはベースに比較的主要でなければなりません。 3つのゼロを追加したのを除いて、さんはちょうどMoに似ています。(例: メッセージが8によって分割される受信機に悪く見えることができた唯一の方法が誤りがそれらの3ビットの1つに発生したかどうかということであるというKが8 この手段になるように不当に選ばれている2進のメッセージ)。
For TCP the base R will be chosen to be 2**16. That is, every
16-bit byte (word on the PDP-11) will be considered as a digit of
a big number and that number is the message. Thus,
TCPにおいて、ベースRは、2**16になるように選ばれるでしょう。 すなわちあらゆる16ビットのバイト(PDP-11では、言い表す)が大きい数のケタであるとみなされるでしょう、そして、その数はメッセージです。 このようにして
Mo = SIGMA [ Bi * (R**i)] , Bi is i-th byte
i=0 to N
MoがSIGMAと等しく[2*(R**i)]、Biがある、i、-、Nへのバイト第i=0
Ms = K * Mo
さんはK*Moと等しいです。
Corrupting a single digit of Ms will yield Ms' = Ms +or-
C*(R**j) for some radix position j . The receiver will compute
Ms'/K = Mo +or- C(R**j)/K. Since R and K are relatively prime,
C*(R**j) cannot be any exact multiple of K. Therefore, the
division will result in a non-zero remainder which indicates that
Ms' is a corrupted version of Ms. As will be seen, a good
choice for K is (R**b - 1), for some b which is the "check
length" which controls the degree of detection to be had for
-さんの一桁を崩壊させて、利回りさんの=さんに+を望んでください。さもないと、何らかの基数のためのC*(R**j)はjを置きます。または、受信機がさんのもの/Kの=Mo+を計算する、-、C(R**j)/K。 RとKが比較的主要であるので、C*(R**j)はK.Thereforeのどんな正確な倍数であるはずがありません、意志が持つために検出の度合いを制御する「チェックの長さ」であるいくつかのbのためにさんのものがAsさんの崩壊したバージョンが目にふれる、Kのための良い選択があるということであることを示す(R**b--1)非ゼロ残りに結果になる分割
- 5 -
- 5 -
Braden, Borman, & Partridge [Page 17] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[17ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
burst errors which affect a string of digits (i.e., 16-bit bytes)
in the message. In fact b will be chosen to be 1, so K will
be 2**16 - 1 so that arithmetic operations will be simple. This
means that all bursts of 15 or fewer bits will be detected.
According to [7] this choice for b results in the following
expression for the fraction of undetected weight 2 errors:
メッセージの一連のケタ(すなわち、16ビットのバイト)に影響するバースト誤り。 事実上、bが1になるように選ばれるので、Kは四則演算が簡単になるための2**16--1でしょう。 これは、15か、より少ないビットのすべての炸裂が検出されることを意味します。 [7]によると、bのためのこの選択は非検出された重さ2の誤りの部分のための以下の表現をもたらします:
f = 16(k-1)/[32(16k-3) + (6/k)] where k is the message length.
kがメッセージ長であるf=16(k-1)/[32(16k-3)+(6/k)]。
For large messages f approaches 3.125 per cent as k goes to
infinity.
大きいメッセージに関しては、kが無限で行くのに応じて、fは3.125パーセントにアプローチします。
Multiple precision multiplication and division are normally quite
complex operations, especially on small machines which typically
lack even single precision multiply and divide operations. The
exception to this is exactly the case being dealt with here --
the factor is 2**16 - 1 on machines with a word length of 16
bits. The reason for this is due to the following identity:
複数の精度乗法と分割は、通常かなり複雑な操作、特に小さいところでは、単精度さえ通常欠いているマシンが増えるということであり、操作を分割します。 これへの例外はまさにここで対処されているケースです--要素はマシンの16ビットの語長がある2**16--1です。 この理由は以下のアイデンティティのためです:
Q*(R**j) = Q, mod (R-1) 0 <= Q < R
Q*(R**j)はQと等しく、モッズ(R-1)0<はQ<Rと等しいです。
That is, any digit Q in the selected radix (0, 1, ... R-1)
multiplied by any power of the radix will have a remainder of Q
when divided by the radix minus 1.
基数が1を引いて割られるとき、選択された基数のどんなパワーも掛けられた基数(0、1、…R-1)のすなわちどんなケタQにも、Qの残りがあるでしょう。
Example: In decimal R = 10. Pick Q = 6.
例: 小数R=10で。 Q=6を選んでください。
6 = 0 * 9 + 6 = 6, mod 9
60 = 6 * 9 + 6 = 6, mod 9
600 = 66 * 9 + 6 = 6, mod 9 etc.
6 = 0 *9+6 = 6、モッズ9 60 = 6*9+6 = 6、モッズモッズ9 9 600 = 66*9+6 = 6など
More to the point, rem(31415/9) = rem((30000+1000+400+10+5)/9)
= (3 mod 9) + (1 mod 9) + (4 mod 9) + (1 mod 9) + (5 mod 9)
= (3+1+4+1+5) mod 9
= 14 mod 9
= 5
より肝心のレム(31415/9)=レム((30000+1000+400+10+5)/9)=、(3のモッズ風の9)+、(1人のモッズ9)+、(4のモッズ風の9)+、(1人のモッズ9)+、(5モッズ9)=(3+1+4+1+5)モッズ9 = 14モッズ9 = 5
So, the remainder of a number divided by the radix minus one can
be found by simply summing the digits of the number. Since the
radix in the TCP case has been chosen to be 2**16 and the check
factor is 2**16 - 1, a message can quickly be checked by summing
all of the 16-bit words (on a PDP-11), with carries being
end-around. If zero is the result, the message can be considered
valid. Thus, checking a product coded message is exactly the
same complexity as with the current TCP checksum!
それで、単に数のケタをまとめることによって、基数が1を引いて割られた数の残りを見つけることができます。 TCP場合における基数が2**16になるように選ばれて、チェック要素が2**16--1であるので、16ビットの単語(PDP-11の)のすべてをまとめることによって、すぐにメッセージをチェックできます、エンドアラウンドである桁上げで。 ゼロが結果であるなら、有効であるとメッセージを考えることができます。 したがって、製品のコード化されたメッセージをチェックするのは、現在のTCPチェックサムのようにまさに同じ複雑さです!
- 6 -
- 6 -
Braden, Borman, & Partridge [Page 18] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[18ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
In order to form Ms, the sender must multiply the multiple
precision "number" Mo by 2**16 - 1. Or, Ms = (2**16)Mo - Mo.
This is performed by shifting Mo one whole word's worth of
precision and subtracting Mo. Since carries must propagate
between digits, but it is only the current digit which is of
interest, one's complement arithmetic is used.
さんを形成するために、送付者は2**16--1を複数の精度「数」Moに掛けなければなりません。 または、さんはMoと等しいです(2**16)--ミズーリ州 これは、Mo1全体の単語の精度の価値を移行させて、ミズーリ州を引き算することによって、実行されます。 桁上げがケタの間で伝播されなければなりませんが、唯一のそれが興味がある現在のケタであるので、1の補数演算は使用されています。
(2**16)Mo = Mo0 + Mo1 + Mo2 + ... + MoX + 0
- Mo = - ( Mo0 + Mo1 + ......... + MoX)
--------- ----------------------------------
Ms = Ms0 + Ms1 + ... - MoX
(2**16) MoはMo0+Mo1+Mo2+と等しいです… + MoX+0--Mo=--(Mo0+Mo1+………+MoX)--------- ---------------------------------- さんはMs0+Ms1+と等しいです… - MoX
A loop which implements this function on a PDP-11 might look
like:
LOOP: MOV -2(R2),R0 ; Next byte of (2**16)Mo
SBC R0 ; Propagate carries from last SUB
SUB (R2)+,R0 ; Subtract byte of Mo
MOV R0,(R3)+ ; Store in Ms
SOB R1,LOOP ; Loop over entire message
; 8 memory cycles per 16-bit byte
PDP-11でこの機能を実行する輪に似るかもしれません: 以下を輪にしてください。 金属酸化物バリスタ-2(R2)、R0。 (2**16)Mo SBC R0の次のバイト。 R0、最後のSUB SUB(R2)+から桁上げを伝播してください。 Mo金属酸化物バリスタR0、(R3)+のバイトを引き算してください。 さんにお涙頂戴のR1を格納してください、そして、輪にしてください。 全体のメッセージの上で輪にしてください。 16ビットのバイトあたり8メモリサイクル
Note that the coding procedure is not done in-place since it is
not systematic. In general the original copy, Mo, will have to
be retained by the sender for retransmission purposes and
therefore must remain readable. Thus the MOV R0,(R3)+ is
required which accounts for 2 of the 8 memory cycles per loop.
それが系統的でないので適所でコード化手順をしないことに注意してください。 一般に、原本(Mo)は、「再-トランスミッション」目的のために送付者によって保有されなければならなくて、したがって、読み込み可能なままで残らなければなりません。 したがって、MOV R0であり、1輪あたり8メモリサイクルのうち2を占める(R3)+が必要です。
The coding procedure will add exactly one 16-bit word to the
message since Ms < (2**16)Mo . This additional 16 bits will be
at the tail of the message, but may be moved into the defined
location in the TCP header immediately before transmission. The
receiver will have to undo this to put Ms back into standard
format before decoding the message.
コード化手順は、<Moさん(2**16)この追加16ビットがメッセージのテールにあるのでまさに1つの16ビットの単語をメッセージに追加しますが、トランスミッションの直前TCPヘッダーの定義された位置に動かされるかもしれません。 受信機は、メッセージを解読する前に標準の形式にさんを戻すためにこれを元に戻さなければならないでしょう。
The code in the receiver for fully decoding the message may be
inferred by observing that any word in Ms contains the
difference between two successive words of Mo minus the carries
from the previous word, and the low order word contains minus the
low word of Mo. So the low order (i.e., rightmost) word of Mr is
just the negative of the low order byte of Ms. The next word of
Mr is the next word of Ms plus the just computed word of Mr
plus the carry from that previous computation.
さんのどんな単語も前の単語からの桁上げ、およびミズーリ州の少ない単語を引いた含有という下位の単語を引いてMoの2つの連続した単語の違いを含むのを観測することによって、メッセージを完全に解読するための受信機のコードは推論されるかもしれません。 したがって、さんの下位(すなわち、一番右の)の単語はまさしくさんの下位バイトの否定的です。さんの次の単語はさんの次の単語です、そして、正当はその前の計算からさんの単語とキャリーを計算しました。
A slight refinement of the procedure is required in order to
protect against an all-zero message passing to the destination.
This will appear to have a valid checksum because Ms'/K = 0/K
手順のわずかな気品が、オールゼロメッセージ・パッシングから目的地に守るのに必要です。 これはさんのもの/Kが0/Kと等しいので有効なチェックサムを持っているように見えるでしょう。
- 7 -
- 7 -
Braden, Borman, & Partridge [Page 19] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[19ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
= 0 with 0 remainder. The refinement is to make the coding be
Ms = K*Mo + C where C is some arbitrary, well-known constant.
Adding this constant requires a second pass over the message, but
this will typically be very short since it can stop as soon as
carries stop propagating. Chosing C = 1 is sufficient in most
cases.
= 0 0残りで。 気品はさんが=K*であったならコード化を作ることです。Cが何らかの任意の、そして、周知の定数である折り+C。 この定数を加えるのはメッセージに関して2番目のパスを必要としますが、通常、これは、停止伝播を運ぶのと同じくらいすぐ止まることができるので、非常に短くなるでしょう。 多くの場合、Chosing C=1は十分です。
The product code checksum must be evaluated in terms of the
desired properties P1 - P7. It has been shown that a factor of
two more machine cycles are consumed in computing or verifying a
product code checksum (P5 satisfied?).
必要な特性のP1に関して製品コードチェックサムを評価しなければなりません--P7。 もう2マシンの要素がコンピューティングで消費されるか、または製品コードチェックサムについて確かめながら循環するのが(P5は満足させましたか?)示されました。
Although the code is not systematic, the checksum can be verified
quickly without decoding the message. If the Internet
Destination Address is located at the least significant end of
the packet (where the product code computation begins) then it is
possible for a gateway to decode only enough of the message to
see this field without having to decode the entire message.
Thus, P6 is at least partially satisfied. The algebraic
properties P1 through P4 are not satisfied, but only a small
amount of computation is needed to account for this -- the
message needs to be reformatted as previously mentioned.
コードは系統的ではありませんが、メッセージを解読しないで、すぐにチェックサムについて確かめることができます。 インターネットDestination Addressがパケット(製品コード計算が始まるところ)の最も重要でない端に位置しているなら、ゲートウェイが全体のメッセージを解読する必要はなくてこの分野を見るメッセージを十分だけ解読するのは、可能です。 したがって、P6は少なくとも部分的に満足しています。 少量の計算だけがこれを説明するのに必要です--代数的な特性のP1からP4は満足していませんが、メッセージは、以前に言及されているとして再フォーマットされる必要があります。
P7 is satisfied since the product code checksum can be
incrementally updated to account for an added word, although the
procedure is somewhat involved. Imagine that the original
message has two halves, H1 and H2. Thus, Mo = H1*(R**j) + H2.
The timestamp word is to be inserted between these halves to form
a modified Mo' = H1*(R**(j+1)) + T*(R**j) + H2. Since K has
been chosen to be R-1, the transmitted message Ms' = Mo'(R-1).
Then,
P7は付記された言葉を説明するために製品コードチェックサムを増加してアップデートできて、満足しています、手順はいくらかかかわりますが。 オリジナルのメッセージには2つの半分、H1、およびH2があると想像してください。 + H1*(R**j)その結果、Mo=H2。 + H1*(R**(j+1))+ T*(R**j)'タイムスタンプ単語は変更されたMoを形成するためにこれらの半分の間に挿入されることです'=H2。 'KがR-1になるように選ばれたので、伝えられたさんのメッセージものはMoと等しい'(R-1)。 そして
Ms' = Ms*R + T(R-1)(R**j) + P2((R-1)**2)
さんのものは+ *T P2R+さん(R-1)(R**j)と等しいです。((R-1)**2)
= Ms*R + T*(R**(j+1)) + T*(R**j) + P2*(R**2) - 2*P2*R - P2
= + *T*+ T*(R**j)P2*R+さん(R**(j+1))(R**2)--2*P2*R--P2
Recalling that R is 2**16, the word size on the PDP-11,
multiplying by R means copying down one word in memory. So,
the first term of Ms' is simply the unmodified message copied
down one word. The next term is the new data T added into the
Ms' being formed beginning at the (j+1)th word. The addition is
fairly easy here since after adding in T all that is left is
propagating the carry, and that can stop as soon as no carry is
produced. The other terms can be handle similarly.
Rが2**16であると思い出すPDP-11の語長、Rで増えるのはメモリの1つの単語を写すことを意味します。 それで、さんの前期は単に1つの単語の下側にコピーされた変更されていないメッセージです。 次期がTがさんが形成始めになるまで加えた新しいデータである、(j+1)、第単語。 コネTを加えた後に、左がキャリーを伝播していて、キャリーが全く生産されないとすぐに、それが止まることができるので、添加はここでかなり簡単です。 他の用語は同様にハンドルであるかもしれません。
- 8 -
- 8 -
Braden, Borman, & Partridge [Page 20] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[20ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
4. More Complicated Codes
4. より複雑なコード
There exists a wealth of theory on error detecting and correcting
codes. Peterson [6] is an excellent reference. Most of these
"CRC" schemes are designed to be implemented using a shift
register with a feedback network composed of exclusive-ORs.
Simulating such a logic circuit with a program would be too slow
to be useful unless some programming trick is discovered.
コードを検出して、修正する誤りの豊富な理論が存在しています。 ピーターソン[6]は素晴らしい参照です。 これらの"CRC"計画の大部分は、排他的なORsで構成されるフィードバックネットワークと共にシフトレジスタを使用することで実行されるように設計されています。 何らかのプログラミングトリックが発見されない場合、プログラムでそのような論理回路をシミュレートするのは役に立つように思えないほど遅いでしょう。
One such trick has been proposed by Kirstein [8]. Basically, a
few bits (four or eight) of the current shift register state are
combined with bits from the input stream (from Mo) and the result
is used as an index to a table which yields the new shift
register state and, if the code is not systematic, bits for the
output stream (Ms). A trial coding of an especially "good" CRC
function using four-bit bytes showed showed this technique to be
about four times as slow as the current checksum function. This
was true for both the PDP-10 and PDP-11 machines. Of the
desirable properties listed above, CRC schemes satisfy only P3
(It has an inverse.), and P6 (It is systematic.). Placement of
the checksum field in the packet is critical and the CRC cannot
be incrementally modified.
そのようなトリックの1つはカースタイン[8]によって提案されました。 基本的に、現在のシフトレジスタ状態の数ビット(4か8)が入力ストリーム(Moからの)からのビットに結合されます、そして、結果は新しいシフトレジスタ状態をもたらすテーブルへのインデックスと出力ストリーム(Ms)のためのコードが系統的でないときにビットとして使用されます。 4ビットのバイトを使用すると示された特に「良い」CRC機能のトライアルコード化は、このテクニックが現在のチェックサム機能のおよそ4倍遅いのを示しました。 PDP-10とPDP-11マシンの両方に、これは本当でした。 上に記載された望ましい特性では、CRC計画はP3(それには、逆があります。)、およびP6だけを満たします(それは系統的です。)。 パケットのチェックサム分野のプレースメントは批判的です、そして、CRCは増加して変更できません。
Although the bulk of coding theory deals with binary codes, most
of the theory works if the alphabet contains q symbols, where
q is a power of a prime number. For instance q taken as 2**16
should make a great deal of the theory useful on a word-by-word
basis.
コード化理論の大半が2進コードに対処しますが、理論作品の大部分はアルファベットであるならqシンボルを含んでいます。そこでは、qが素数のパワーです。 例えば、2**16としてみなされたqは多くの理論をaで役に立つようにするべきです。一語一語基礎。
5. Outboard Processing
5. 船外の処理
When a function such as computing an involved checksum requires
extensive processing, one solution is to put that processing into
an outboard processor. In this way "encode message" and "decode
message" become single instructions which do not tax the main
host processor. The Digital Equipment Corporation VAX/780
computer is equipped with special hardware for generating and
checking CRCs [13]. In general this is not a very good solution
since such a processor must be constructed for every different
host machine which uses TCP messages.
かかわったチェックサムを計算などなどの機能が大規模な処理を必要とするとき、1つの解決策は船外のプロセッサにその処理を入れることです。 「メッセージをコード化してください」と「メッセージを解読してください」のためのこのように、メインホスト処理装置に税をかけないただ一つの指示になってください。 DEC VAX/780コンピュータはCRCs[13]を発生して、チェックするための特別なハードウェアを装備しています。 一般に、TCPメッセージを使用するあらゆる異なったホスト・マシンのためにそのようなプロセッサを組み立てなければならないので、これは非常に良い解決策ではありません。
It is conceivable that the gateway functions for a large host may
be performed entirely in an "Internet Frontend Machine". This
machine would be responsible for forwarding packets received
大きいホストのためのゲートウェイ機能が完全に「インターネットフロントエンドマシン」で実行されるのが想像できます。 このマシンはパケットが受けた推進に原因となるでしょう。
- 9 -
- 9 -
Braden, Borman, & Partridge [Page 21] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[21ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
either from the network(s) or from the Internet protocol modules
in the connected host, and for reassembling Internet fragments
into segments and passing these to the host. Another capability
of this machine would be to check the checksum so that the
segments given to the host are known to be valid at the time they
leave the frontend. Since computer cycles are assumed to be both
inexpensive and available in the frontend, this seems reasonable.
ネットワークかインターネットから、接続ホストと、インターネット断片をセグメントに組み立て直して、これらをホストに渡すためのモジュールを議定書の中で述べてください。 このマシンの別の能力はチェックサムをチェックするだろうことです、したがって、フロントエンドを残すときホストに与えられたセグメントが有効であることが知られています。 安価であって、かつコンピュータサイクルがフロントエンドで利用可能であると思われるので、これは妥当に思えます。
The problem with attempting to validate checksums in the frontend
is that it destroys the end-to-end character of the checksum. If
anything, this is the most powerful feature of the TCP checksum!
There is a way to make the host-to-frontend link be covered by
the end-to-end checksum. A separate, small protocol must be
developed to cover this link. After having validated an incoming
packet from the network, the frontend would pass it to the host
saying "here is an Internet segment for you. Call it #123". The
host would save this segment, and send a copy back to the
frontend saying, "Here is what you gave me as #123. Is it OK?".
The frontend would then do a word-by-word comparison with the
first transmission, and tell the host either "Here is #123
again", or "You did indeed receive #123 properly. Release it to
the appropriate module for further processing."
フロントエンドにおけるチェックサムを有効にするのを試みることに関する問題は終わりから終わりへのチェックサムのキャラクタを滅ぼすということです。 どちらかと言えば、これはTCPチェックサムの最も強力な特徴です! 終わりから終わりへのチェックサムでホストからフロントエンドへのリンクを覆わせている方法があります。 このリンクを覆うために別々の、そして、小さいプロトコルを開発しなければなりません。 ネットワークから入って来るパケットを有効にした後に、フロントエンドは「ここに、あなたのためのインターネットセグメントがあります」と言うホストにそれを渡すでしょう。 「それを#123と呼んでください。」 ホストは、このセグメントを救って、「ここに、私への#123としてのものがあります」と言うフロントエンドにコピーを送り返すでしょう。 「それはOKですか?」? 次に、フロントエンドがするだろう、一語一語比較、最初のトランスミッション、「ここに、#123、が再びある」か、または「本当に、適切に#123、を受けのどちらかであったこと」をホストに言ってください。 「さらなる処理のための適切なモジュールにそれをリリースしてください。」
The headers on the messages crossing the host-frontend link would
most likely be covered by a fairly strong checksum so that
information like which function is being performed and the
message reference numbers are reliable. These headers would be
quite short, maybe only sixteen bits, so the checksum could be
quite strong. The bulk of the message would not be checksumed of
course.
The reason this scheme reduces the computing burden on the host
is that all that is required in order to validate the message
using the end-to-end checksum is to send it back to the frontend
machine. In the case of the PDP-10, this requires only 0.5
memory cycles per 16-bit byte of Internet message, and only a few
processor cycles to setup the required transfers.
ホストフロントエンドリンクを越えるメッセージのヘッダーは、機能が実行されている情報とメッセージ参照番号が信頼できるように、たぶんかなり強いチェックサムで覆われているでしょう。 これらのヘッダーはかなり脆いでしょう、したがって、多分16ビットだけに、チェックサムがかなり強いかもしれません。 メッセージの大半がもちろんchecksumedされないでしょう。 この計画がホストでコンピューティング負担を減少させる理由は終わりから終わりへのチェックサムを使用することでメッセージを有効にするのに必要であるすべてがフロントエンドマシンにそれを送り返すことであるということです。 PDP-10の場合では、これは、必要な転送をセットアップするためにインターネットメッセージの16ビットのバイトあたり0.5メモリサイクル、およびプロセッサほんの数サイクルだけを必要とします。
6. Conclusions
6. 結論
There is an ordering of checksum functions: first and simplest is
none at all which provides no error detection or correction.
Second, is sending a constant which is checked by the receiver.
This also is extremely weak. Third, the exclusive-OR of the data
may be sent. XOR takes the minimal amount of computer time to
generate and check, but is not a good checksum. A two's
complement sum of the data is somewhat better and takes no more
チェックサム機能の注文があります: 1番目で最も簡単であるのは、全く誤り検出か修正を全く提供しないなにもです。 2番目は受信機によってチェックされる定数を送ることです。また、これも非常に弱いです。 3番目に、データの排他的論理和を送るかもしれません。 XORは発生して、チェックするコンピュータ時間の最少量を取りますが、良いチェックサムではありません。 データの2の補数合計は、いくらか良く、それ以上取りません。
- 10 -
- 10 -
Braden, Borman, & Partridge [Page 22] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[22ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
computer time to compute. Fifth, is the one's complement sum
which is what is currently used by TCP. It is slightly more
expensive in terms of computer time. The next step is a product
code. The product code is strongly related to one's complement
sum, takes still more computer time to use, provides a bit more
protection against common hardware failures, but has some
objectionable properties. Next is a genuine CRC polynomial code,
used for checking purposes only. This is very expensive for a
program to implement. Finally, a full CRC error correcting and
detecting scheme may be used.
計算するコンピュータ時間。 黙秘権は現在TCPによって使用されることである1の補数合計です。 それはコンピュータ時間でわずかに高価です。 次のステップは製品コードです。 製品コードには、強く1の補数合計に関連されますが、まして、コンピュータ時間を使用にかけますが、一般的なハードウェアの故障に対してもう少しの保護を提供しますが、いくつかの好ましくない特性があります。 次に、目的だけをチェックするのに使用される本物のCRC多項式コードがあります。 プログラムが実行するように、これは非常に高価です。 最終的に、完全なCRCエラー修正と検出方式は使用されるかもしれません。
For TCP and Internet applications the product code scheme is
viable. It suffers mainly in that messages must be (at least
partially) decoded by intermediate gateways in order that they
can be forwarded. Should product codes not be chosen as an
improved checksum, some slight modification to the existing
scheme might be possible. For instance the "add and rotate"
function used for paper tape by the PDP-6/10 group at the
Artificial Intelligence Laboratory at M.I.T. Project MAC [12]
could be useful if it can be proved that it is better than the
current scheme and that it can be computed efficiently on a
variety of machines.
TCPとインターネットアプリケーションにおいて、製品コード計画は実行可能です。 それに、主にそれらを進めることができるように中間ゲートウェイでメッセージを解読しなければならなくて(少なくとも部分的に)、苦しみます。 改良されたチェックサム、既存の計画への何らかのわずかな変更が選ぶかもしれないように製品コードを選ばないなら、可能であってください。 それが現在の計画より良く、さまざまなマシンの上で効率的に計算できると立証できるなら、例えば「加えてください、そして、回転してください」という紙テープにマサチューセッツ工科大学Project MAC[12]のArtificial Intelligence研究所のPDP-6/10グループによって使用された機能は役に立つかもしれません。
- 11 -
- 11 -
Braden, Borman, & Partridge [Page 23] RFC 1071 Computing the Internet Checksum September 1988
ブレーデン、ボーマン、およびインターネットチェックサム1988年9月に計算するヤマウズラ[23ページ]RFC1071
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
インターネット実験注意45 1978年6月5日のTCPチェックサム機能デザインウィリアム・W.プラマー
References
参照
[1] Cerf, V.G. and Kahn, Robert E., "A Protocol for Packet Network
Communications," IEEE Transactions on Communications, vol.
COM-22, No. 5, May 1974.
[1] サーフとV.G.とカーン、ロバートE.、「パケット網コミュニケーションのためのプロトコル」、Communications、vol.COM-22、No.5(1974年5月)のIEEE Transactions。
[2] Kahn, Robert E., "The Organization of Computer Resources into
a Packet Radio Network", IEEE Transactions on Communications,
vol. COM-25, no. 1, pp. 169-178, January 1977.
[2] カーン、ロバートE.、「パケット無線ネットワークへのコンピュータリソースの組織」、Communications、vol.COM-25、No.1、ページのIEEE Transactions 169-178と、1977年1月。
[3] Jacobs, Irwin, et al., "CPODA - A Demand Assignment Protocol
for SatNet", Fifth Data Communications Symposium, September
27-9, 1977, Snowbird, Utah
[3] ジェイコブズ、アーウィン、他、「CPODA--AはSatNetについて課題プロトコルを要求します」、黙秘権Data Communications Symposium、1977年9月27日〜9日、Snowbird、ユタ
[4] Bolt Beranek and Newman, Inc. "Specifications for the
Interconnection of a Host and an IMP", Report 1822, January
1976 edition.
[4] BeranekとニューマンInc.をボルトで締めてください。「ホストと悪童のインタコネクトのための仕様」、Report1822(1976年1月の版)。
[5] Dean, Richard A., "Elements of Abstract Algebra", John Wyley
and Sons, Inc., 1966
[5] ディーン、リチャードA.、「抽象代数学のElements」ジョンWyley、および息子Inc.、1966
[6] Peterson, W. Wesley, "Error Correcting Codes", M.I.T. Press
Cambridge MA, 4th edition, 1968.
[6] ピーターソン、W.ウエスリー、「誤り検出方式」、マサチューセッツ工科大学PressケンブリッジMA、4番目の版、1968。
[7] Avizienis, Algirdas, "A Study of the Effectiveness of Fault-
Detecting Codes for Binary Arithmetic", Jet Propulsion
Laboratory Technical Report No. 32-711, September 1, 1965.
[7] Avizienis、Algirdas、「2進の演算のための欠点検出コードの有効性の研究」、ジェット推進委研究所技術報告書No.32-711、1965年9月1日。
[8] Kirstein, Peter, private communication
[8] カースタイン、ピーター、私信
[9] Cerf, V. G. and Postel, Jonathan B., "Specification of
Internetwork Transmission Control Program Version 3",
University of Southern California Information Sciences
Institute, January 1978.
[9] サーフとV.G.とポステル、ジョナサンB.、「何3インチも、南カリフォルニア大学情報科学が1978年1月に設けるインターネットワーク転送管理プログラムバージョンの仕様。」
[10] Digital Equipment Corporation, "PDP-10 Reference Handbook",
1970, pp. 114-5.
[10]DEC、「PDP-10参照ハンドブック」、1970、ページ 114-5.
[11] Swanson, Robert, "Understanding Cyclic Redundancy Codes",
Computer Design, November, 1975, pp. 93-99.
[11] スワンソン、ロバート、「理解の周期的な冗長コード」、コンピュータDesign、1975年11月、ページ 93-99.
[12] Clements, Robert C., private communication.
[12] クレメンツ、ロバートC.、私信。
[13] Conklin, Peter F., and Rodgers, David P., "Advanced
Minicomputer Designed by Team Evaluation of Hardware/Software
Tradeoffs", Computer Design, April 1978, pp. 136-7.
[13] コンクリン、ピーターF.とロジャーズ、デヴィッドP.、「ハードウェア/ソフトウェア見返りのチーム評価で設計された高度なミニコンピュータ」、コンピュータDesign、1978年4月、ページ 136-7.
- 12 -
- 12 -
Braden, Borman, & Partridge [Page 24]
ブレーデン、ボーマン、およびヤマウズラ[24ページ]
一覧
スポンサーリンク
