키흐

풀다가 너무 고생하여 진행상황을 적는다.

문제는 2가지 파일이 있다. WindowsKernel.exe , WinKer.sys

WindowsKernel.exe 와 WinKer.sys가 DeviceIoControl 함수를 통해 통신함.

PW 체크 루틴은 WinKer.sys 에 있는 듯 하다.

WinKer.sys 는 IDA pro에서 디컴파일이 가능하다. Windbg로 디버깅도 된다는데 아직 디버깅 환경 구성은 못했다.

체크루틴을 찾은거 같은데 READ_PORT_UCHAR 함수의 리턴값 -> 특정 포트에서 읽어온 바이트라고

레퍼런스에 적혀있다. 근데 이게 바이트 값인데 case에서 비교부분을 보면 비교 값들이 하나같이 음수이다.

처음엔 리턴값이 당연히 아스키 코드일줄 알았는데 아니라고 사료됨.

하..

----------------

windbg로 디버깅 하는게 빠를거 같다 구축해야지..

----------------

해결!! 결국 windbg 환경 구축은 완료 했으나 그냥

IDA 정적 분석으로 문제 해결했다.

뭐 키워드만 하나 던지자면 Keyboard scan code 를 이용해 문제를 풀었다.

ps. 답은 'lowercase'로 인증해야하는 것을 잊으면 안됨

 이거때매 하루종일 고생중. x&(-x)가 무엇이냐 부터 힘들었다.

read 연산

int read(int idx)
{
   int sum = 0;
   while (idx > 0){
      sum += tree[idx];
      idx -= (idx & -idx);
   }
   return sum;
}

update 연산

int tree[20];
#define MaxVal 16
void update(int idx ,int val)
{
   while (idx <= MaxVal){
      tree[idx] += val;
      idx += (idx & -idx);
   }
}

일단 read가 처음부터 idx까지의 구간 합을 구하는 함수고

update는 idx번째 아이템의 값을 갱신하는 함수이다. 이렇게 되면 

read도 log(n), update도 log(n)으로 쿼리가 m개면 m*log(n)으로 해결 된다.

여기서 idx를 갱신할 때 2가지 방법을 쓸 수 있다.

1. x&(-x)

 이것은 x의 약수 중 2의 제곱수만 빼면 된다. ex) 4 : 4, 5 : 1, 6 : 2

그러므로 idx -= (idx& -idx) 이런식.

2. x&(x-1)

 이것은 x 이하의 수 중 가장 큰 2의 배수를 리턴. ex) 4 : 4, 5 : 4, 6 : 6, 15 : 14

그러므로 idx = (idx&(idx-1))

참고 사이트 : http://59.23.113.171/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree

예제 문제 : https://www.acmicpc.net/problem/2042 - 구간 합치기

가장 전형적인 문제로 BIT를 '사용하기만하면' 풀어진다.

아래는 위 문제의 소스코드

#include <stdio.h>
long long int tr[1000001];
long long int val[1000001];
int n;
long long int read(long long int idx){
   long long int sum = 0;
   while (idx > 0){
      sum += tr[idx];
      idx -= (idx & -idx);
   }
   return sum;
}
void update(long long int idx ,long long int val){
   while (idx <= n){
      tr[idx] += val;
      idx += (idx & -idx);
   }
}
int main(){
	int m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(long long int i=1;i<=n;i++){
		scanf("%lld",&val[i]);
		update(i,val[i]);
	}
	for(int i=0;i<m+k;i++){
		long long int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		if(a==1){
			update(b,c-val[b]);
			val[b] = c;
		}
		else{
			printf("%lld\n",read(c)-read(b-1));
		}
	}
	return 0;
}