one's complement sum 계산 방식

개요

해당 글에서는 헤더 체크섬에 주로 이용되는 one's complement계산 방식에 대해서 알아본다.

일반적인 덧셈에서는 carry가 발생하면 상위 비트의 값에 추가하지만, 해당 방식에서는 16비트를 넘어선 carry가 발생할 경우, 가장 하위 비트에 1을 더하는 식으로 처리한다. 이후, 최종 값을 비트 반전하는 것으로 계산을 마무리한다.

보수를 취하는 이유는 수신 측에서 값을 더한 후, 수신받은 checksum을 더하기만 하면 0xFFFF값을 얻을 수 있으므로 이를 간편하게 하기 위함이다.

다음과 같은 IPv4 헤더가 있다고 해보자.

0040 0000 4000 4006 4a40 c0a8 2dce 0101 0101

IPv4 헤더에서 checksum 필드만 0x0000으로 바꾸고, 16비트씩 순서대로 one's complement방식으로 계산해보겠다.

45 00
00 40
00 00
40 00
40 06
00 00   ← checksum 필드
c0 a8
2d ce
01 01
01 01

16비트 값으로 보면:

0x4500
0x0040
0x0000
0x4000
0x4006
0x0000
0xc0a8
0x2dce
0x0101
0x0101

이제 순서대로 더한다.

1)
0x0000
+ 0x4500
--------
0x4500

2)
0x4500
+ 0x0040
--------
0x4540

3)
0x4540
+ 0x0000
--------
0x4540

4)
0x4540
+ 0x4000
--------
0x8540

5)
0x8540
+ 0x4006
--------
0xC546

6)
0xC546
+ 0x0000
--------
0xC546

여기까지는 평범하지만,

이제 Source IP의 첫 16비트:

7)
0xC546
+ 0xC0A8
--------
0x185EE

16비트를 초과하게된다.

이를 다음과 같이 처리한다.

하위 16비트 = 0x85EE
carry       = 0x0001

carry를 다시 더한다.

0x85EE
+ 0x0001
--------
0x85EF

이게 one's complement addition의 특징이다.

계속:

8)
0x85EF
+ 0x2DCE
--------
0xB3BD

9)
0xB3BD
+ 0x0101
--------
0xB4BE

10)
0xB4BE
+ 0x0101
--------
0xB5BF

최종 합:

0xB5BF

이제 모든 비트를 반전한다.

0xB5BF
= 1011 0101 1011 1111
 
반전
 
= 0100 1010 0100 0000
= 0x4A40

그래서 실제 IPv4 헤더에 들어 있던:

4a 40

이 정확히 나온다.

IPv4 헤더를 16비트씩 자름
→ checksum 필드는 0으로 둠
→ 전부 one's complement 방식으로 더함
→ 16비트 overflow가 나면 carry를 다시 더함
→ 마지막 결과의 모든 비트를 반전
→ 0x4A40

이는 RFC 791의 checksum 정의와 정확히 일치한다.