암호화프로그래밍/(Old)C-BIGINT

016. 비트연산

산을좋아한라쯔 2013. 8. 12. 13:06
반응형

2.10 비트 연산(bitwise operation)

BIGINT의 비트별 연산함수를 만들어 본다.

비트별 연산은 다음과 같다.

 

  • bit_and
  • bit_or
  • bit_xor
  • shiftleft
  • shitright

 

비트별 논리연산인 and, or, xor는 두 BIGINT의 각 비트값에 따라 아래와 같은 결과값을 가진다.

p q and or xor
0 0 0 1 0
0 1 0 1 1
1 0 0 1 1
1 1 1 0 0

 

두 BIGINT의 길이가 서로 다른 경우는, 길 길이의 수를 기준으로 해서 계산하고 이때 작은 길의의 수에 해당하는 부분은 0으로 놓고 계산한다.

즉, A=0xFF000000FF000000, B=0xFF000001이고, INT가 u32일 때, A의 길이는 2이고 B는 1이다. 따라서 A[1]인 0xFF000000에 대응하는 B의 값이 없으므로 0x00000000을 가정하고 계산된다. 따라서 결과값은 다음과 같이 된다.

  • A and B = 0x00000000 FF000000
  • A or B   = 0xFF000000 FF000001
  • A xor B = 0x00FFFFFF 00000001

bit_and

/**************************************************************************
두 BIGINT값에 대한 비트별 AND연산을 수행한다.
Input: @A, @B = 입력값	   
Output:@C = 입력값 A, B에 대한 bitwise and 결과. 
            C의 길이는, A, B중에서 길이가 큰 쪽이 된다.
Returns: 
		OK : no error	
Comment:
		
***************************************************************************/
int bit_and(BIGINT A, BIGINT B, BIGINT C){
	INT *p,*q,*r;
	INT *pLast, *qLast;

두 BIGINT A, B에 대해서 bit별 and연산을 하고 그 결과를 C에 저장한다.

 

포인터변수 p는 큰 수를, q는 작은 수, 그리고 r은 결과값을 따라가게 된다.

pLast는 큰 수의 가장 마지막 주소인 가장 큰 자릿수를, qLast는 작은 수의 가장 큰 자릿수를 가리키게 된다.

 

        //길이가 큰 쪽 수를 p로 둠 /
	if(SIZE(A) >= SIZE(B)){
		p = A + 1; //large or equal
		q = B + 1;
		pLast = A + SIZE(A);
		qLast = B + SIZE(B);
		C[0] = SIZE(A); //length가 큰 쪽 크기 따라감
	}else{
		p = B +1; 
		q = A + 1;
		pLast = B + SIZE(B);
		qLast = A + SIZE(A);
		C[0] = SIZE(B);
	}
	r = C + 1;

A,B중 자릿수 크기가 긴 쪽을 p가 가리키게 하고, 작은 수는 q가 가리키게 한다.

결과값 C의 크기는 A,B중 큰 수의 자릿수에 의해 결정된다.

 

        // A & 0 = 0 & B = 0
	if((A[0] == 0) || (B[0] == 0)) {
		C[0] = 0;
		return OK;
	}

and연산에서는, 한 쪽 비트값이 0의 경우는 다른 쪽 비트값에 상관없이 0이므로, A 혹은 B가 0인 경우 결과값 C는 0이다.

 

 

        //큰 길이의 수 범위내에서 계산
	while(p <= pLast){
		if(q <= qLast){
			*r++ = *p++ & *q++;
		}else{ 
			*r++ = 0;  //r = p & 0 = 0
			*p++;
		}
	}
	REMOVE_ZERO(C);
	return OK;
}

큰 수의 범위내에서 비트별 연산이 진행된다. 이 때, 큰수의 자릿수에 대항하는 작은 수의 비트값이 없을 수 있는데, 이 때는 0으로 놓고 계산한다.

 

bit_or

/**************************************************************************
두 BIGINT값에 대한 비트별 OR연산을 수행한다.
Input: @A, @B = 입력값	   
Output:@C = 입력값 A, B에 대한 bitwise or 결과. 
            C의 길이는, A, B중에서 길이가 큰 쪽이 된다.
Returns: 
		OK : no error	
Comment:
		
***************************************************************************/
int bit_or(BIGINT A, BIGINT B, BIGINT C){
	INT *p,*q,*r;
	INT *pLast, *qLast;
	// 0 | B = B
	if(A[0] == 0) {
		copy_big(C,B);
		return OK;
	}
	// A | 0 = A
	if(B[0] == 0){
		copy_big(C,A);
		return OK;
	}
	//길이가 큰 쪽 수를 p로 둠 /
	if(SIZE(A) >= SIZE(B)){
		p = A + 1; //large or equal
		q = B + 1;
		pLast = A + SIZE(A);
		qLast = B + SIZE(B);
		C[0] = SIZE(A); //length가 큰 쪽 크기 따라감
	}else{
		p = B +1; 
		q = A + 1;
		pLast = B + SIZE(B);
		qLast = A + SIZE(A);
		C[0] = SIZE(B);
	}
	r = C + 1;
	//큰 길이의 수 범위내에서 계산
	while(p <= pLast){
		if(q <= qLast){
			*r++ = *p++ | *q++;
		}else{ 
			*r++ = *p++;  //r = p | 0 = p			
		}
	}
	REMOVE_ZERO(C);
	return OK;
}

앞에서 설명한 bit_and와 유사하다.

 

다른 것은, or 연산의 경우 한 쪽이 0인 경우 결과값은 다른 쪽값이 되는 것(A or 0 = A)

또한, 어느 한 쪽이 모두 1인 경우 결과값은 1이 되는데, BIGINT에서 모든 비트가 1이 되는 경우도 드물거니와, 0인지를 검사하는 것은 0번째 값을 보고 결정하면 되지만, 전 비트가 1인 것은 모든 값을 확인해야하기에, 모든 비트가 1인 경우에 대해서 별도 처리 하지 않는것이 좋을 것이다.

 

bit_xor

xor는 두 비트가 같을 때는 0, 다를 때는 1이다.

루틴은, 위에 설명한 and, or와 유사하다.

/**************************************************************************
두 BIGINT값에 대한 비트별 XOR연산을 수행한다.
Input: @A, @B = 입력값	   
Output:@C = 입력값 A, B에 대한 bitwise xor 결과. 
            C의 길이는, A, B중에서 길이가 큰 쪽이 된다.
Returns: 
		OK : no error	
Comment:
		
***************************************************************************/
int bit_xor(BIGINT A, BIGINT B, BIGINT C){
	INT *p,*q,*r;
	INT *pLast, *qLast;
	if((A[0] ==0) && (B[0] == 0)){
		C[0] = 0;
		return OK;
	}
	//길이가 큰 쪽 수를 p로 둠 /
	if(SIZE(A) >= SIZE(B)){
		p = A + 1; //large or equal
		q = B + 1;
		pLast = A + SIZE(A);
		qLast = B + SIZE(B);
		C[0] = SIZE(A); //length가 큰 쪽 크기 따라감
	}else{
		p = B +1; 
		q = A + 1;
		pLast = B + SIZE(B);
		qLast = A + SIZE(A);
		C[0] = SIZE(B);
	}
	r = C + 1;
	//큰 길이의 수 범위내에서 계산
	while(p <= pLast){
		if(q <= qLast){
			*r++ = *p++ ^ *q++;
		}else{ 
			*r++ = *p++ ^ 0;  
		}
	}
	REMOVE_ZERO(C);
	return OK;
}

shift연산

왼쪽과 오른쪽으로 비트를 이동하는 연산을 구현한다.

왼쪽으로 n 비트 이동하는 것은 2n만큼을 곱하는 것과 같은 효과를 나타낸다. 반대로 오늘쪽으로 n비트 이동하는 것은 2n으로 나누는 것과 같다. 

 

BIGINT에서의 shift연산은, BIGINT를 구성하는 배열의 단위가 INT로 2바이트 혹은 4바이트로 가변이고, 배열의 첫 번째에는 길이정보가, 그리고 실제 값 데이터는 주소가 작은 쪽부터 작은 값을 적어 나가는 형태이기에, 구현이 쉽지 않다.

 

실제 구현하기에 앞서 shift연산관련 몇 가지 규칙을 정해보고 검토해 보자.

  • 왼쪽 쉬프트했을 경우, 오른편 끝 쪽에 새롭게 채워지는 값은 0로 한다.
  • 오른쪽 쉬프트했을 경우, 왼쪽 끝 쪽에 새롭게 채워지는 값은, 원래 값이 양수의 경우는 0, 음수였던 경우는 1로 채워진다.
    • 오른쪽 쉬프트는 2n으로 나누는 효과와 같기에, 만약 -4를 1비트만큰 오른쪽으로 쉬프트하면 -2가 되야 한다. 이것을 INT타입이 u32의 경우에 표현해 보면, -4 = FFFFFFFF...FFFFFFFC이고 이것을 1로 채우면서 1비트 쉬프트하면 FFFFFFFF...FFFFFFE가 되어 -2가 됨을 알 수 있다.
  • 왼쪽 쉬프트에서, BIGINT범위의 값을 넘어서서 쉬프트를 해야하는 경우, BIGINT의 범위를 벗어난 값은 무시한다. (에러 리턴 안 함)
    • overflow가 발생하는 경우다. 2n을 곱했을 때 결과값이 BIGINT범위를 벗어나는 것과 동일하다. multiply함수의 경우 결과값이 BIGINT의 범위를 벗어나는 경우 E_Overflow를 리턴하도록 설계했지만, 비트연산에서는 체크하지 않도록 하자. 비트 연산의 경우는 비트를 이동시키는 것에 그 목적이 있다고 보기 때문이고, 따라서 shiftleft함수를 multiply함수 대용으로 쓰고자 할 때는 overflow에 주의하도록 하자  
  • BIGINT의 최대 비트수(MAX_BIT_LEN)보다 더 크게 왼쪽 혹은 오른쪽 쉬프트하는 경우, 결과값은 0가 된다.

 

비트 쉬프트 연산을 설계함에 있어 가장 쉽게 생각할 수 있는 것은, shiftleft의 경우는 가장 작은 자릿수부터 모든 자리값에 대해 왼쪽으로 1만큼 쉬프트시키고 이 때 각 자리에서 발생하는 carry를 더 큰 자리로 이관시키는 과정을 요구되는 shift수만큼 수행하는 것이다.

 

 

 

 

위 예에서 보면, 0x0000 0000 4000 0001 8000 0001을 왼쪽으로 3만큼 쉬프트시키는데, 1비트씩 이동시키면서 해당 자리 범위를 벗어나는 것은 다음자리로 옮기면서 진행된다.

 

그런데, 만약 수 천비트를 이동시키는 것이라면 이렇게 한 비트씩 옮기는 것은 너무 비효율적일것이다.

해서, INT 한 단위 보다 큰 수 만큼 이동시킬 때는, INT 비트 단위만큼 한 번에 옮기고 나머지 부분을 미세하게 옮기게 해보자.

그림으로 개념화 해보면 다음과 같다.

 

 

 

 INT가 u32의 경우 100비트를 왼쪽으로 쉬프트시키는 경우이다.

100비트는 3개의 INT와 4비트로 나타낼 수 있다. 따라서, 100비트를 이동하는 것은 3개의 INT만큼 이동 후 4비트를 이동하는 것과 같다.

 

해서, shift함수는 먼저 INT의 배수만큼 이동 시키고, 남는 비트 수만큼을 이동시키는 것으로 설계하도록 하자.

 

먼저, INT범위내에서 n비트 이동시키는 shiftleft_INT와 shiftright_INT함수의 구현을 보자.

 

shiftleft_INT함수

/**************************************************************************
BIGINT에 대해 주어진 INT범위내 자릿수 만큼 bitwise left shift연산을 한다.
이동시키려는 수가 INT의 비트수보다 크면 에러리턴하고 종료.

 
 
가장 오른쪽 비트는, 왼쪽으로 값이 shift되면서 새롭게 0으로 채워진다.
입력값이 양수였으나 왼쪽으로 shift한 결과가 BIGINT의 양수최대값을 넘어서서 
음수로 되는 경우도 그대로 shift 처리하고 no error

 
 
(2^n)을 곱한 것과 같은 효과

 
 
Input: @A = 입력값	
       @n = shift할 비트 수. should be less than sizeof(INT) * 8
Output:@A = shift한 결과

 
 
Returns: 
		OK : no error	
		E_WrongFormat
Comment:
		
***************************************************************************/
int shiftleft_INT(BIGINT A, int n){
	INT *a,*aLast;
	DINT t;
	INT k; //carry
	short bitNumOfINT;

INT형 변수의 비트수보다 작은 수 만큼 이동할 때 사용하는 함수이다. 범용으로 사용되는 왼쪽 이동 함수는 shiftleft이고, 이 shiftleft함수내에서 이 shiftleft_INT함수를 호출하는 구조이다.

 

포인터 변수 a는 BIGINT값 A의 처음부터 마지막 주소까지의 값을 나타내게 될 것이고, aLast는 A의 가장 마지막 주소를 가르키게 된다. 

t는 INT형 배열값에서 n만큼 shift한 결과를 저장하는 임시값으로 사용되고, 따라서 INT형보다 두 배 큰 DINT로 선언된다.

k는 n만큼 shift했을 때 한 칸 왼쪽 배열로 넘겨야할 carry로 사용된다.

bitNumOfInt = sizeof(INT) x 8로, INT가 u32의 경우 32를 값으로 가진다.

 

        //Case1. INT의 총비트수보다 더 큰 이동을 요구하면 에러 
	bitNumOfINT = sizeof(INT) * 8;
	if(n > bitNumOfINT)
		return E_WrongFormat;

 
 
	//Case 2. 0을 이동하면 0
	if(A[0] == 0) return OK;

 
 
	//Case 3. 0만큼 이동하면 그대로 A
	if(n == 0) return OK;

 
 
	//Case 4. n이 음수이면 shiftright
	if(n < 0){		
		return shiftright_INT(A,n * -1);
	}

 

 

Case1. shiftleft_INT함수는 (sizeof(INT) x 8)이하 만큼 비트를 왼쪽으로 이동할 수 있는 함수이다. 이 보다 큰 수의 이동은 shiftleft함수가 사용되고, shiftleft함수에서 다시 shiftleft_INT함수가 호출되는 구조이다.

 

Case2. BIGINT값이 0인 경우, 이동을 해도 0

 

Case3. 0만큼 이동하라는 것은 이동안한 것과 동일하다. 따라서, 결과값은 원래 A값 그대로 불변

 

Case4. n이 음수인 경우에는 오른쪽 이동 함수 호출

        //Case 5. otherwise
	a = A + 1;
	aLast = A + SIZE(A);
	k = 0;
	while(a <= aLast){
		t = ((DINT)*a << n) | (DINT)k;
		*a = (INT)t;
		k = (INT)(t >> bitNumOfINT);
		a++;
	}
	if(k>0){
		if( (SIZE(A) + 1) > MAX_INT_LEN){
			//최대자릿수를 넘어선 부분은 그냥 무시
			REMOVE_ZERO(A);			
		}else{
			//size를 1 증가시킴
			SET_SIZE(A,SIZE(A) + 1);
			*a = k;
		} 
	}
	return OK;
}

 

Case 4까지의 특별한 경우가 아닌 일반적인 경우의 비트 이동 루틴을 보자.

 

포인터변수 a로 BIGINT값 A의 가장작은 값(=가장 낮은 주소)부터 왼쪽 쉬프트연산을 하면서, 발생한 carry를 그 다음값으로 이동하는 것을, A의 끝 값(=가장 큰 주소)까지 반복하면 진행한다. 이 때 t에는 INT형 변수값을 쉬프트한 값이 들어가기에, t 변수 크기는 INT형 변수의 2배크기로 잡아야 한다. 이 때, n < sizeof(INT) * 8 이기에 2배 크기로 했을 때 overflow가 발생하지 않음이 보장된다.

 

쉬프트연산을 하면서 A의 가장 큰 값(=가장 오른쪽 address)까지 계산하고, 다시 carry가 발생했을 경우, BIGINT값 범위 내에 있으면 A의 size를 1 증가 시킨다. shift연산에 의해 크기가 증가된 것이다. 만약 길이를 증가시켜야하는데 그렇게 할 경우 BIGINT값범위를 벗어난다면, 그냥 벗어난 범위에 해당하는 carry를 무시하고 에러를 리턴하지 않는다.

이와 비슷하게 carry가 발생한 경우 add. multiply함수에서는 BIGINT범위를 벗어났다고 에러를 리턴했었는데, 비트 연산에서는 에러를 리턴하지 않도록 하자.

 

shiftright_INT함수

/**************************************************************************
BIGINT에 대해 주어진 INT범위내 자릿수 만큼 bitwise rigth shift연산을 한다.
 

이동시키려는 수가 INT의 비트수보다 크면 에러리턴하고 종료.
가장 왼쪽 비트는 오른쪽으로 값이 shift되면서,
양수의 경우는 새롭게 0으로 채워지고,
음수의 경우는 1로 채워진다.

 
 
A = floor(A / (2^n))과 같은 효과

 
 
Input: @A = 입력값	
       @n = shift할 비트 수. should be less than sizeof(INT) * 8
Output:@A = shift한 결과
Returns: 
		OK : no error	
		E_WrongFormat: in case of n is larger than sizeof(INT) * 8
Comment:
		
***************************************************************************/
int shiftright_INT(BIGINT A, int n){
	INT *a,*aFirst;
	DINT t;
	INT k; //carry
	short bitNumOfINT;
	u8 negaFlag;
	INT mask;
	int i;

 

 

INT형 변수의 비트수 범위내에서 오른쪽으로 비트 쉬프트하는 함수이다. 범위 제한 없이 오른쪽 쉬프트하는 함수는 shiftright이고, 이 shiftright함수 내에서 다시 shiftright_INT함수가 호출되는 구조를 가진다.

 

포인터변수 a는 BIGINT A의 값을 따라가면서 가르키는 변수이고, aFirst는 A의 가장 작은 값(=가장 왼쪽 주소)을 가르키게 된다.

t는 INT형 배열값을 쉬프트연산한 결과를 임시 저장하는 변수로 사용되고, 따라서 INT의 두 배 크기인 DINT형 변수로 선언된다.

k는 쉬프트했을 때 발생하는 carry를 저장하기 위해 사용.

bitNumOfINT = sizeof(INT) x 8 로 INT가 u32의 경우 32를 값으로 가진다.

negaFlag는 BIGINT A가 음수인지를 나타내는 flag로 사용되는데, A가 음수의 경우 오른쪽 쉬프트에 의해서 가장 왼쪽에 채워지는 값이 1이 되게 하기 위해 사용된다.

mask는 A가 음수이고 왼쪽 채움을 1로 해야할 때 마스크로 사용된다.

 

        //Case1. INT의 총비트수보다 더 큰 이동을 요구하면 에러 
	bitNumOfINT = sizeof(INT) * 8;
	if(n > bitNumOfINT)
		return E_WrongFormat;

 
 
	//Case 2. 0을 이동하면 0
	if(A[0] == 0) return OK;

 
 
	//Case 3. 0만큼 이동하면 그대로 A
	if(n == 0) return OK;

 
 
	//Case 4. n이 음수이면 shiftleft
	if(n < 0){		
		return shiftleft_INT(A,n * -1);
	}

 

 

Case1. shiftright_INT함수는 sizeof(INT) x 8보다 작은 n값에 대해서만 오른쪽 쉬프트할 수 있다. 더 큰 값을 쉬프트하는 일반적인 경우는 shiftright함수를 사용해야하고, shiftright함수내에서 다시 shiftright_INT함수가 호출된다.

 

Case2. 0을 이동하면 그대로 0

 

Case3. 0만큰 이동하는 것은 이동안하는 것과 동일하기에 원래 A값 그대로 불변

 

Case4. n이 음수이면 왼쪽으로 이동하라는 것과 같고, shiftleft_INT함수 이용

 

위에서 열거한 4가지 Case외 일반적인 경우에 대한 오른쪽 쉬프트 루틴을 살펴보자.

       
        //Case 5. otherwise
	a = A + SIZE(A);
	aFirst = A + 1;
	k = 0;
	if(isPositive(A) == 1){ //양수
		while(a >= aFirst){
			t = ((DINT)*a << (bitNumOfINT-n)) | (DINT)k;
			*a = (INT)(t >> bitNumOfINT);
			k = (INT)t;
			a--;
		}
	}

쉬프트 할 때, A가 음수인지 양수인지에 따라 루틴이 달라진다. 음수의 경우 쉬프트하면서 생기는 왼쪽 자릿수 채움을 1로 해야하기 때문이다.

 

먼저 양수의 경우를 보자.

포인터변수 a를 처음에 A의 가장 오른쪽 주소인 가장 큰 값을 가리키도록하고, A의 가장 왼쪽 주소인 aFirst가 될 때까지 a의 주소를 감소시키면서 각 배열값에 대해 n 만큼 오른쪽으로 쉬프트 시킨다.

 

이때, 오른쪽으로 n만큼 쉬프트하는 것을 (bitNumOfINT-n)만큼 왼쪽 쉬프트하는 것처럼 보이는데 이는,  INT형 값을 n만큼 오른쪽으로 쉬프트하면 DINT형으로 캐스팅하더라도 오른쪽 쉬프트에 의해서 정보가 사라지는 문제를 없애기 위함이다. 

 

위의 예를 보면, (...111100001100)을 u64의 D_INT형으로 캐스팅하고 오른쪽으로 4만큼 쉬프트하는 경우, 제일 오른쪽에 있는 (1100)이 손실되고 있다.

정보손실이 발생되지 않게 하기 위해서는, D_INT형으로 캐스팅하고 (sizeof(INT) x 8)만큼 왼쪽 쉬프트시킨 후 n만큼 오른쪽 쉬프트하면 된다. 이는 D_INT형으로 캐스팅하고 [(sizeof(INT) x 8) - n]만큼 왼쪽으로 쉬프트하는 것과 동일하다.

따라서, a를 bitNumOfINT-n만큼 왼쪽으로 쉬프트한 값에, 아랫 자릿수에서 올라온 carry를 더한 값을 D_INT형 t에 넣고, 다시 t를 bitNumOfINT만큼 오른쪽으로 쉬프트해서 원 위치한 값을 a로, t의 하위 INT부분을 carry로 한 후, a의 주소를 감소기키면서 반복 계산한다.

                t = ((DINT)*a << (bitNumOfINT-n)) | (DINT)k;
		*a = (INT)(t >> bitNumOfINT);;
		k = (INT)t;
		a--;

 

음수의 경우는 오른쪽 쉬프트에 의해서 가장 왼쪽자리 수 채움을 1로 해야하기에 좀 복잡하다.

	}else{ //음수
		//음수를 나타내는 0xffffffff로 채워지고 난 다음, 실제 value가 나타나는 곳 찾음
		while(a >= aFirst){
			if(*a == MAX_INT){
				a--;
				continue;
			}else{ //의미있는 num value 시작
				t = ((DINT)*a << (bitNumOfINT-n)) | (DINT)k;
				//shift한 만큼 1로 채워줌
				mask = (DINT)((INT)MAX_POSITIVE+1) << (sizeof(INT) * 8); //0x8000...
				for(i=0;i<n;i++){
					t |= mask;
					mask >>= 1;
				}
				*a = (INT)(t >> bitNumOfINT);
				k = (INT)t;
				a--;
				break; 
			}
		}
		//여기서부터는 쉬프트해서 생기는 공간을 1로 채울필요 없음.
		while(a >= aFirst){
			t = ((DINT)*a << (bitNumOfINT-n)) | (DINT)k;
			*a = (INT)(t >> bitNumOfINT);;
			k = (INT)t;
			a--;	
		}
	}

 

 

 

BIGINT에서 음수의 표기를 2의 보수법으로 하고 있다, 따라서 A=-2라면 16진수로 0xFFFF....FFFE이고, BIGINT 배열의 표현으로는 A[0]=MAX_INT_LEN A[1]=0XFFFF FFFE A[2]=0XFFFF FFFF A[3]=0XFFFF FFFF ...A[MAX_INT_LEN]=0XFFFF FFFF이다.

따라서, FFFF FFFF가 아닌 값을 가지고 있는 첫번째 배열값을 이하 값들을 제외하고는 오른쪽 쉬프트를 해도 그대로 FFFF FFFF이므로, 첫번째 FFFF FFFF(=MAX_INT)가 아닌 값이 나올때까지는 값을 그대로 놔둔다.

			if(*a == MAX_INT){
				a--;
				continue;
			}

 

MAX_INT가 아닌 값이 처음 발견되면, 이 배열값을 오른쪽 쉬프트하는데 이 때 왼쪽편에 1로 채워넣는다.

			}else{ //의미있는 num value 시작
				t = ((DINT)*a << (bitNumOfINT-n)) | (DINT)k;
				//shift한 만큼 1로 채워줌
				mask = (DINT)((INT)MAX_POSITIVE+1) << (sizeof(INT) * 8); //0x8000...
				for(i=0;i<n;i++){
					t |= mask;
					mask >>= 1;
				}
				*a = (INT)(t >> bitNumOfINT);
				k = (INT)t;
				a--;
				break; 
			}

 

첫번째 의미있는 값을 쉬프트하면서 1로 채워넣은 후 그 다음에 있는 수들은 정상적으로 쉬프트하면서 왼쪽자리에서 받은 carry를 더하는 형태로 A의 끝자리까지 계산한다.

//여기서부터는 쉬프트해서 생기는 공간을 1로 채울필요 없음.
		while(a >= aFirst){
			t = ((DINT)*a << (bitNumOfINT-n)) | (DINT)k;
			*a = (INT)(t >> bitNumOfINT);;
			k = (INT)t;
			a--;	
		}

 

계산을 완료했으면, 앞부분 zero가 있는지 확인해서 없애고 함수를 종료한다.

	REMOVE_ZERO(A);
	return OK;
}

 

 

 

shiftleft

이제 INT형 비트수 범위내에서의 이동만이 아닌, 더 큰 자리 이동에도 처리할 수 있는 완전한 함수를 만들자.

/**************************************************************************
BIGINT에 대해 주어진 자릿수 만큼 bitwise left shift연산을 한다.
가장 오른쪽 비트는, 왼쪽으로 값이 shift되면서 새롭게 0으로 채워진다.
입력값이 양수였으나 왼쪽으로 shift한 결과가 BIGINT의 양수최대값을 넘어서서 
음수로 되는 경우도 그대로 shift 처리하고 no error
(2^n)을 곱한 것과 같은 효과
Input: @A = 입력값	
       @n = shift할 비트 수
Output:@A = shift한 결과
Returns: 
		OK : no error
Comment:
		
***************************************************************************/
int shiftleft(BIGINT A, int n){
	BIGINT_D R;  //overflow방지위해 BIGINT_D로 선언
	INT *a,*aStart, *r, *rStart;	
	short bitNumOfINT;
	short p,q;

 

이름은 shifleft로 하고, 필요한 변수들을 선언 한다.

 

//Case 1. 0을 이동하면 0
	if(A[0] == 0) return OK;
	//Case 2. 0만큼 이동하면 그대로 A
	if(n == 0) return OK;
	//case 3. n이 MAX_BIT_LEN보다 크면 zero
	if(n > MAX_BIT_LEN) {
		A[0] = 0;
		return OK;
	}
	//Case 4. n이 음수이면 shiftright
	if(n < 0){		
		return shiftright(A,n * -1);
	}
	// Case 5. n이 INT 비트수보다 작으면
	bitNumOfINT = sizeof(INT) * 8;
	if(n < bitNumOfINT)
		return shiftleft_INT(A,n);

 

Case1. 이동할 BIGINT값이 0이라면, 이 수를 아무리 비트 이동해도 결과는 0이다.

Case2. 이동시킬 비트거리가 0이면, 원래 그대로의 BIGINT값이 된다.

Case3. 왼쪽으로 이동시킬 비트거리가, BIGINT의 최대비트수를 넘어선다면, 이동한 결과는 모든 비트가 0인 zero가 된다.

Case4. 이동시킬 n값이 음수이면, 왼쪽 이동이 아니라 오른쪽 이동이므로, shiftright함수를 이용한다. 이 때 n값을 양수로 만들어 준다.

Case5. 이동시킬 비트거리가 INT형 비트수보다 작다면, 이미 작성된 shiftleft_INT함수를 한 번 호출해서 계산한다.

 

위 5가지 경우가 아닌 일반적인 경우에 대해서 아래와 같이 처리한다.

      
	//Case 6. otherwise & (n >= bitNumOfINT)
	//1. n = p x bitNumOfINT + q
	p = (short)(n / bitNumOfINT);
	q = (short)(n % bitNumOfINT);

 
 
	//2. shift amount of p
	a = A + SIZE(A);
	aStart = A + 1;

 
 
	SET_SIZE(R,SIZE(A) + p);
	r = R + SIZE(R);
	rStart = R + 1;

 
 
	while( a >= aStart){
		*r-- = *a--;
	}

 
 
	while( r >= rStart){
		*r-- = 0;
	}

 
 
	//3. BIGINT범위내로 맞춤. 벗어낫것은 무시해버림
	if(SIZE(R) > MAX_INT_LEN){
		SET_SIZE(R,MAX_INT_LEN);
	}

먼저 이동시킬 INT단위의 갯수를 나타내는 p와, INT내에서의 미세 이동거리를 나타내는 q를 구한다. 예를들어 INT형이 u32이고 이동시킬 n값이 34이라면, INT형 배열값 1개와 배열내에서 2비트를 이동하면 된다. 이것을 p와 q로 나타내면, p=1 이고 q = 2

 

먼저 p만큼 INT형 배열만큼 이동한다.

p만큼 이동하게 되면 배열의 length는 p만큼 커지므로 Size를 조정한다.

	SET_SIZE(R,SIZE(A) + p);
	r = R + SIZE(R);
	rStart = R + 1;

 

그리고 이동시킬 값 A의 자릿수보다 p만큼 더 큰 위치의 R배열에 값들을 복사한다.

        while( a >= aStart){
		*r-- = *a--;
	}

 

왼쪽으로 이동했들 때 생기는 오른쪽 편 공간에는 0을 채워 넣는다.

	while( r >= rStart){
		*r-- = 0;
	}

 

만약 이동한 만큼 size값을 증대시킨 것이, BIGINT의 최대 자릿수를 넘어서는 것이라면, size를 MAX_INT_LEN로 조정한다. 이렇게 하면 MAX_INT_LEN를 넘어서서 왼쪽 쉬프트된 값들은 무시되는 것이다.

 

이제 p만큼은 이동을 했고, INT내에서의 미세 쉬프트인 q만큼 이동시키자.

	//4. shift remained amount of q
	shiftleft_INT(R,q);

 
 
	//5. copy R to A
	copy_big(A,R);

 
 
	return OK;
}

 

INT범위내에서의 비트이동이므로 이미 작성된 shiftleft_INT함수를 사용하면 되겠다.

 

이제 다 이동을 했으므로, 원래 BIGINT값에 이동된 값을 복사하고 함수 종료한다.

 

shirtrigth

shiftleft와 유사하게, INT형 비트범위만이 아닌 큰 번위내에서 오른쪽 쉬프트하는 함수를 만들어 보자.

/**************************************************************************
BIGINT에 대해 주어진 자릿수 만큼 bitwise rigth shift연산을 한다.
가장 왼쪽 비트는 오른쪽으로 값이 shift되면서,
양수의 경우는 새롭게 0으로 채워지고,
음수의 경우는 1로 채워진다.
A = floor(A / (2^n))과 같은 효과
Input: @A = 입력값	
       @n = shift할 비트 수
Output:@A = shift한 결과
Returns: 
		OK : no error	
		E_WrongFormat
Comment:
		
***************************************************************************/
int shiftright(BIGINT A, int n){
	BIGINT R; //right shift의 경우는 수가 더 작아지므로 right의 경우처럼 BIGINT_D선언필요 없음
	INT *a,*aStart, *r, *rStart;	
	short bitNumOfINT;
	short p,q;

 

함수명은 shiftright이고, 변수들이 선언되었다.

 

	//Case 1. 0을 이동하면 0
	if(A[0] == 0) return OK;
	//Case 2. 0만큼 이동하면 그대로 A
	if(n == 0) return OK;
	//case 3. n이 MAX_BIT_LEN보다 크면 zero
	if(n > MAX_BIT_LEN) {
		A[0] = 0;
		return OK;
	}
	//Case 4. n이 음수이면 shiftright
	if(n < 0){		
		return shiftright(A,n * -1);
	}

 
 
	// Case 5. n이 INT 비트수보다 작으면
	bitNumOfINT = sizeof(INT) * 8;
	if(n < bitNumOfINT)
		return shiftright_INT(A,n);

 

Case1. 이동할 BIGINT값이 0이라면, 이 수를 아무리 비트 이동해도 결과는 0이다. (shiftleft와 동일)

Case2. 이동시킬 비트거리가 0이면, 원래 그대로의 BIGINT값이 된다. (shiftleft와 동일)

Case3. 오른쪽으로 이동시킬 비트거리가, BIGINT의 최대비트수를 넘어선다면, 이동한 결과는 모든 비트가 0인 zero가 된다. (shiftleft와 동일)

Case4. 이동시킬 n값이 음수이면, 오른쪽 이동이 아니라 왼쪽 이동이므로, shiftleft함수를 이용한다. 이 때 n값을 양수로 만들어 준다.

Case5. 이동시킬 비트거리가 INT형 비트수보다 작다면, 이미 작성된 shiftrigth_INT함수를 한 번 호출해서 계산한다.

 

위 5가지 경우가 아닌 일반적인 경우에 대해서 아래와 같이 처리한다.

	//Case 6. otherwise & (n >= bitNumOfINT)
	//1. n = p x bitNumOfINT + q
	p = (short)(n / bitNumOfINT);
	q = (short)(n % bitNumOfINT);

 
 
	//2. shift amount of p
	a = A + SIZE(A);
	aStart = A + 1;
	if(isPositive(A) == -1){ //음수
		SET_SIZE(R,MAX_INT_LEN); 
		r = R + SIZE(R);
		rStart = R + SIZE(R) - p + 1;
		while(r >= rStart){  //p-1만큼 0xFFFF... 채움
			*r-- = MAX_INT;
		}
		rStart = R + 1;
		while(r >= rStart){
			*r-- = *a--;
		}
	}else{ //양수
		SET_SIZE(R,SIZE(A) - p); 
		r = R + SIZE(R);
		rStart = R + 1;
		while( r >= rStart){
			*r-- = *a--;
		}
	}

 

먼저 shiftleft함수에서와 마찬가지로, 이동시킬 INT단위의 갯수를 나타내는 p와, INT내에서의 미세 이동거리를 나타내는 q를 구한다. 예를들어 INT형이 u32이고 이동시킬 n값이 34이라면, INT형 배열값 1개와 배열내에서 2비트를 이동하면 된다. 이것을 p와 q로 나타내면, p=1 이고 q = 2

먼저 p만큼 INT형 배열만큼 이동한다. 이 때, shiftleft함수와 달리 양수일때와 음수일때의 양상이 다른다. 양수의 경우는 오른쪽 이동에 의해서 생기는 왼쪽 빈 공간에 0이 채워지는데, 음수의 경우는 1로 채워지게 된다.

 

음수의 경우를 보면, 음수의 size는 항상 MAX_INT_LEN이고 이 음수를 오른쪽으로 아무리 이동해도 size는 MAX_INT_LEN으로 불변.

p만큼 이동해서 생기는 왼쪽 빈 공간을 FFFFFFFF로 채우고, 원래값 A의 각 자리의 값을, 원래값 A의 자릿수보다 p만큼 오른쪽 위치의 R배열로 카피한다.

		while(r >= rStart){  //p-1만큼 0xFFFF... 채움
			*r-- = MAX_INT;
		}

 
		rStart = R + 1;
		while(r >= rStart){
			*r-- = *a--;

 

양수의 경우는 오른쪽 쉬프트에 의해서 생기는 왼쪽 빈공간이 0으로 채워지면 되는데, 0으로 채운다는 것은 실제로는 자릿수가 짧아지는 것이기에, p만큼 size를 작게 조정한다. 

	}else{ //양수
		SET_SIZE(R,SIZE(A) - p); 
		r = R + SIZE(R);
		rStart = R + 1;
		while( r >= rStart){
			*r-- = *a--;
		}
	}

 

p만큼 이동하는 것을 했기에, 이제 남은 것은 INT크기내에서 q만큼 이동하는 것이다. 이는 위에서 만들어 놓은 shiftright_INT함수를 이용하면 되겠다.

	//4. shift remained amount of q
	shiftright_INT(R,q);
	//5. copy R to A
	copy_big(A,R);
	return OK;

 

테스트

비트연산인 bit_and, bit_or, bit_xor, shiftleft, shiftright에 대한 테스트는 아래 프로젝트 소스 직접 참조.

 

프로젝트 파일

 

 

010.bitwise.zip

 

 

010.bitwise.zip
0.64MB
반응형
저작자표시 비영리 변경금지

'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글

018. 거듭제곱  (0) 2013.08.26
017. 비트 수 세기  (0) 2013.08.22
015. 최대공약수(gcd)  (0) 2013.08.09
014. 나머지(mod)  (0) 2013.08.08
013. 나눗셈(divide)  (0) 2013.08.02

'암호화프로그래밍/(Old)C-BIGINT'의 다른글

  • 현재글016. 비트연산

관련글

댓글

티스토리툴바