RFC1071 - Computing the Internet checksum
계산해야 할 바이트가 A, B, C, D, ... , Y, Z 이렇게 있다고 가정하고, [a, b] 표기를 a * 256 + b인 16비트 정수로 정의하자. 그리고 +' 기호를 1의 보수 덧셈이라고 하면, 체크썸 계산은 아래와 같이 표현할 수 있다.
[A, B] +' [C, D] +' ... +' [Y, Z] (짝수 개인 경우)
[A, B] +' [C, D] +' ... +' [Z, 0] (홀수 개인 경우)
(IP 헤더 길이는 4바이트 단위로 표현되니 실제로는 짝수 개만 쓰겠지만)
(1) 교환, 결합 가능
위의 계산을 임의로 묶거나 순서를 바꿔서 수행해도 결과는 바뀌지 않는다.
가령 ([A, B] +' [C, D] +' ... [J, 0]) +' ([0, K] +' ... +' [Y, Z])
(2) 바이트 순서 독립성
[B, A] +' [D, C] +' ... +' [Z, Y] 로 나온 결과도 바이트 순서만 바뀔 뿐 동일하게 계산된다.
(3) 병렬 연산
1의 보수 덧셈이 교환 가능하므로 원래 [A, B] +' [C, D] +' [E, F] +' [G, H] 하던 것을
[A, B, C, D] +' [E, F, G, H] 하고 절반으로 접어서 다시 +' 해도 동일하게 계산된다.
여기에 2번 특성까지 더 하면 아무 순서대로 섞어서 머신 워드 단위로 계산할 수 있게 된다.
이쯤 되면 놀랍기도 하고 머리가 아프다 -_-..
못 믿겠다 싶으면 수식을 전개해보거나 RFC1071에 있는 예제를 들여다보시라..
이제 체크썸 계산을 아래와 같은 기법으로 빠르게 할 수 있다.
(1) 캐리 미루기
기계에 따라서는 덧셈부터 모조리 끝내고 캐리를 나중에 더하는게 효율적이다. 16비트 워드를 32비트 변수에 누적시켜서 계산을 해버리면 오버플로우는 상위 16비트에 쌓인다. 32비트 단위로 계산하는 것에 비해 2배로 계산을 해야하긴 하지만 오히려 이게 빠를 수 있다.
(2) 루프 풀기
코드가 좀 너절해 보일 수 있으나 루프 오버헤드를 줄이려고 내부의 덧셈을 풀어서 쓰기도 한다. 요새는 컴파일러가 해줄 수 있으니 확인 필요하겠다.
(3) 데이터 복사 묶기
특정 메모리에서 값을 복사하는 것도 버스가 느린 경우 심각한 오버헤드가 되는데 한 번에 두 개씩 처리해서 줄일 수 있다.
(4) 부분 업데이트
TTL처럼 일부 헤더값만 바뀌는 경우 부분 업데이트가 가능하다.
자세한 내용은 RFC1624를 참고한다. (+0, -0 으로 인해 주의할 경계 조건이 있음)
----
그런고로 아래와 같은 C 코드가 나오게 된 것이니..
while( count > 1 ) {
/* This is the inner loop */
sum += * (unsigned short) addr++;
count -= 2;
}
/* Add left-over byte, if any */
if( count > 0 )
sum += * (unsigned char *) addr;
/* Fold 32-bit sum to 16 bits */
while (sum>>16)
sum = (sum & 0xffff) + (sum >> 16);
checksum = ~sum;
while이 왜 들어갔나 생각할 수 있는데, 접어서 더하고 난 뒤 캐리가 나오면 다시 더해야 하기 때문에 그렇다. IP 체크썸을 검증할 때는 IP 헤더를 다 더 해서 -0 (0xFFFF)이 나오게 된다. (보수를 저장했으므로)
요새는 NIC가 체크썸 계산을 오프로딩 해주기 때문에 별 생각 없이 넘기고 있었다 (..) 왜 굳이 1의 보수로 만들었나 했는데 흠..
계산해야 할 바이트가 A, B, C, D, ... , Y, Z 이렇게 있다고 가정하고, [a, b] 표기를 a * 256 + b인 16비트 정수로 정의하자. 그리고 +' 기호를 1의 보수 덧셈이라고 하면, 체크썸 계산은 아래와 같이 표현할 수 있다.
[A, B] +' [C, D] +' ... +' [Y, Z] (짝수 개인 경우)
[A, B] +' [C, D] +' ... +' [Z, 0] (홀수 개인 경우)
(IP 헤더 길이는 4바이트 단위로 표현되니 실제로는 짝수 개만 쓰겠지만)
(1) 교환, 결합 가능
위의 계산을 임의로 묶거나 순서를 바꿔서 수행해도 결과는 바뀌지 않는다.
가령 ([A, B] +' [C, D] +' ... [J, 0]) +' ([0, K] +' ... +' [Y, Z])
(2) 바이트 순서 독립성
[B, A] +' [D, C] +' ... +' [Z, Y] 로 나온 결과도 바이트 순서만 바뀔 뿐 동일하게 계산된다.
(3) 병렬 연산
1의 보수 덧셈이 교환 가능하므로 원래 [A, B] +' [C, D] +' [E, F] +' [G, H] 하던 것을
[A, B, C, D] +' [E, F, G, H] 하고 절반으로 접어서 다시 +' 해도 동일하게 계산된다.
여기에 2번 특성까지 더 하면 아무 순서대로 섞어서 머신 워드 단위로 계산할 수 있게 된다.
이쯤 되면 놀랍기도 하고 머리가 아프다 -_-..
못 믿겠다 싶으면 수식을 전개해보거나 RFC1071에 있는 예제를 들여다보시라..
이제 체크썸 계산을 아래와 같은 기법으로 빠르게 할 수 있다.
(1) 캐리 미루기
기계에 따라서는 덧셈부터 모조리 끝내고 캐리를 나중에 더하는게 효율적이다. 16비트 워드를 32비트 변수에 누적시켜서 계산을 해버리면 오버플로우는 상위 16비트에 쌓인다. 32비트 단위로 계산하는 것에 비해 2배로 계산을 해야하긴 하지만 오히려 이게 빠를 수 있다.
(2) 루프 풀기
코드가 좀 너절해 보일 수 있으나 루프 오버헤드를 줄이려고 내부의 덧셈을 풀어서 쓰기도 한다. 요새는 컴파일러가 해줄 수 있으니 확인 필요하겠다.
(3) 데이터 복사 묶기
특정 메모리에서 값을 복사하는 것도 버스가 느린 경우 심각한 오버헤드가 되는데 한 번에 두 개씩 처리해서 줄일 수 있다.
(4) 부분 업데이트
TTL처럼 일부 헤더값만 바뀌는 경우 부분 업데이트가 가능하다.
자세한 내용은 RFC1624를 참고한다. (+0, -0 으로 인해 주의할 경계 조건이 있음)
----
그런고로 아래와 같은 C 코드가 나오게 된 것이니..
while( count > 1 ) {
/* This is the inner loop */
sum += * (unsigned short) addr++;
count -= 2;
}
/* Add left-over byte, if any */
if( count > 0 )
sum += * (unsigned char *) addr;
/* Fold 32-bit sum to 16 bits */
while (sum>>16)
sum = (sum & 0xffff) + (sum >> 16);
checksum = ~sum;
while이 왜 들어갔나 생각할 수 있는데, 접어서 더하고 난 뒤 캐리가 나오면 다시 더해야 하기 때문에 그렇다. IP 체크썸을 검증할 때는 IP 헤더를 다 더 해서 -0 (0xFFFF)이 나오게 된다. (보수를 저장했으므로)
요새는 NIC가 체크썸 계산을 오프로딩 해주기 때문에 별 생각 없이 넘기고 있었다 (..) 왜 굳이 1의 보수로 만들었나 했는데 흠..
