2.4 감소(decrese)
1만큼 감소시키는 함수이다.
1을 증가시키는 increse의 경우에도 add를 사용할 수도 있으나 효율성을 생각해서 별도 구현을 했듯이, decrese함수도 subtract함수로 구현할 수 있으나, 별도로 구현한다.
기본 원리는, 주어진 BIGINT값에 대해 가장 작은 자릿수를 -1해주고, 만약에 borrow가 있을 경우 그 윗 자릿수값을 -1하면서 가장 큰 자릿수까지 이동한다.
이 때, 음수를 2의 보수로 처리하기에 그대로 -1을 해주면, 주어진 수가 양수이든 음수이든 제대로 계산이 된다. 단, 주어진 수가 BIGINT의 최소값(음수로서 절대값이 가장 큰 값)의 경우는 -1을 하면 양수가 되어버린다.(2의 보수 특성) 따라서, 이 경우는 underflow 처리한다.
아래표와 같이 한 자릿수 수체계로 생각해보면 이해하기 쉽다.
| 입력 값(A) | Decresed | 비고 | ||
| Hex | Dec | Hex | Dec | |
| 00 | 0 | FF | -1 | 0 -> -1 |
| 01 | 1 | 00 | 0 | 1 -> 0 |
| ... | ||||
| 7F | 127 | 7E | 126 | 127 -> 126 |
| 80 | -128 | 7F | 127 | -128 -> 127 (Underflow) |
| ... | ||||
| FF | -1 | FE | -2 | -1 -> -2 |
이제 이렇게 되도록 구현 해보자.
/***************************************************************************************
1을 뺌
input: BIGINT A
output: BIGINT A = A - 1
return: OK - if all ok
E_Underflow - 1을 뺀 값이 음수인 경우
****************************************************************************************/
int decrese(BIGINT A){
INT *a, *ae;
DINT borrow = MAX_DINT;
subtract와 달리 1개 인자만 받아서, 그 BIGINT값을 1 감소 시킨다.
*a, *ae는 BIGINT A의 값을 따라가기 위한 포인터
borrow는 subtract함수와 달리 DINT로 선언했음에 유의. subtract에서 계산 중간값을 저장하기 위해 사용되었던 역할까지 담당해야하므로 INT의 두 배 DINT사용.
//01. A가 zero의 경우
if(*A == (INT)0){
setmax(A); // -1
return OK;
}
만약 A가 zero이면, 1을 감소시킨 값은 -1
BIGINT 수 전체를 순환 구조로 보면, 0의 오른쪽은 0x000...01이, 왼쪽은 0xFFFF..FF가 된다. -1을 한다는 것은 왼쪽으로 이동시킨다는 의미와도 같은 것으로써, 0에서 -1을 하면 FF..FFFF가 되어 -1이 된다.
//02. A에 대한 포인터 얻기
a = A +1;
ae = A + SIZE(A);
//03. loop
while( (a <= ae) && (borrow == MAX_DINT)){
*a = (INT)(borrow = (DINT)*a - 1);
a++;
} A값을 따라갈 수 있게 a와 ae를 지정하고, (a <= ae) 범위내에서 루프를 돌린다.
처음 루프에 들어와서 A의 가장 작은 자릿수 값을 -1한다.
borrow = (DINT)*a - 1
이 때, 빌림수가 발생하는 경우는 *a가 0인 경우이다. 따라서 borrow는 (0 - 1)이기에 음수값 -1이 된다. DINT형 변수에 대해서 -1은 0xffffffff이고 이는 unsigned형으로 생각했을 때 DINT형 변수의 최대값이다. 그러므로, borrow가 발생했는지의 여부는 borrow가 MAX_DINT인지 확인해보면 된다.
while( (a <= ae) && (borrow == MAX_DINT))
//04. remove zeroes
REMOVE_ZERO(A);만약 borrow가 있어서 계속해서 빼 나간경우 앞 자리 수가 zero로 된 경우가 발생한다. 이 zero값을 없애준다.
//05. if(A == 음의 최소값) -> -1이면 underflow if((SIZE(A) == MAX_INT_LEN) && (A[MAX_INT_LEN] == ((INT)MAX_POSITIVE))){ ae = A+SIZE(A)-1; while((*ae == (INT)MAX_INT) && (--ae > A)); //모두 ff라면 if(ae == A) return E_Underflow; } return OK;}
BIGINT의 가장 작은값(음수)에서 -1을 빼면, BIGINT로는 처리할 수 없는 결과값이 된다. 따라서, 이 경우에는 Underflow처리한다. 1바이트 수체계의 예로 생각해 보면, 가장 작은 값은 -128=0x80이고, 여기서 -1을 빼면 -129가 아닌 0x7F=127이되어 버려, underflow처리를 하는 것이다.
BIGINT의 경우는 -1을 했을 때 length가 최대이고, 가장 큰 자릿수의 값이 7FFFFFFF(4바이트의 경우)이며 나머지 자리에는 모두 FFFFFFFF가 채워져 있는 경우이다.
지금가지 설명한 decrese함수에 대한 전체 소스는 다음과 같다.
/*************************************************************************************** 1을 뺌 input: BIGINT A output: BIGINT A = A - 1 return: OK - if all ok E_Underflow - 1을 뺀 값이 BIGINT의 음의 최소값을 벗어난 경우 ****************************************************************************************/ int decrese(BIGINT A){ INT *a, *ae; DINT borrow = MAX_DINT;//01. A가 zero의 경우 if(*A == (INT)0){ setmax(A); // -1 return OK; }//02. A에 대한 포인터 얻기 a = A +1; ae = A + SIZE(A); //03. loop while( (a <= ae) && (borrow == MAX_DINT)){ *a = (INT)(borrow = (DINT)*a - 1); a++; } //04. remove zeroes REMOVE_ZERO(A); //05. if(A == 음의 최소값) -> -1이면 underflow if((SIZE(A) == MAX_INT_LEN) && (A[MAX_INT_LEN] == ((INT)MAX_POSITIVE))){ ae = A+SIZE(A)-1; while((*ae == (INT)MAX_INT) && (--ae > A)); //모두 ff라면 if(ae == A) return E_Underflow; } return OK; }
테스트
작성된 decrese함수에 대해서는 다음과 같은 테스트를 한다.
[Decrese에 대한 테스트]
1. decrese from 0
2. decrese from 1
3. 일반적인 BIGINT에 대한 decrese
4. borrow가 계속 발생하는 decrese
5. MAX에 대한 decrese
6. MIN에 대한 decrese --> underflow
테스트 함수 소스는 다음과 같다.
int test_decrese(){ BIGINT a; BIGINT expected; int result=-1; int i;//1. decrese from 0 a[0] = 0; decrese(a); setmax(expected); result = compare_big(a,expected); if(result != 0) return result; //2. decrese from 1 a[0] = 1; a[1] = 1; decrese(a); expected[0]=0; result = compare_big(a,expected); if(result != 0) return result;
//3. 일반적인 BIGINT에 대한 decrese hexstr2bigint("ff112233445566778899aabbcc",a); decrese(a); hexstr2bigint("ff112233445566778899aabbcb",expected); result = compare_big(a,expected); if(result != 0) return result;
//4. borrow가 계속발생하는 decrese hexstr2bigint("10000000000000000000000000000000",a); decrese(a); hexstr2bigint("fffffffffffffffffffffffffffffff",expected); result = compare_big(a,expected); if(result != 0) return result;
//5. MAX에 대한 decrese setmax(a); decrese(a); setmax(expected); expected[1]= (MAX_INT-1); result = compare_big(a,expected); if(result != 0) return result;
//6. MIN에 대한 decrese --> underflow a[0] = MAX_INT_LEN; for(i=1;i<MAX_INT_LEN;i++){ a[i] = 0; } a[MAX_INT_LEN] = (INT)MAX_POSITIVE+1; result = decrese(a); if(result != E_Underflow){ return -1; }
return OK; }
프로젝트 파일
위 테스트코드 및 decrese함수를 포함한 프로젝트 파일
004.Decrese.zip
위 프로젝트를 로드하고 실행하면 다음과 같다.
'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글
| 012. 제곱(square) (0) | 2013.07.31 |
|---|---|
| 011. 곱셈(multiply) (0) | 2013.07.30 |
| 009. 뺄셈(subtract) (0) | 2013.07.30 |
| 008. 테스트: 덧셈, 증가 (0) | 2013.07.30 |
| 007. 증가(increse) (0) | 2013.07.29 |