꿈꾸는 소년 (Code Lab)

SP 과제...
먼저 입력값을 그룹별로 나눠야 할 필요성이 있기에.. 크게 3가지 그룹으로 분리..

1. 랜덤한 인풋

그럼 성능 비교 시작..


이런 이런.. 별반 차이가 없군..
그냥 최대 허용 노드수만 늘리면 장땡..

2. 순차적 인풋

성능은 뭐가 더 좋을까나!?..

그렇군열~ MRU 승..
간단히 머리 굴려보면..
계속해서 다른 수가 들어오는 것이 아니라, 어느 정도 들어온 다음에 다시 이전의 값에서부터 시작하고, MRU로 자료를 유지했다면 앞부분의 자료만 변했기에, 다시 예전의 값에서 시작할 때 Update가 호출되기땜시 승.. LRU면.. 예전께 남아 있을리 만무..

3. 말로 표현하기 힘든 인풋.. (펄스는 아니고.. 뭐라고 하지 ㅡ_ㅡ??..)

성능비교 시작..


이번엔 LRU 승..
빈번하게 들어오는 입력값이 많으니..
기존 리스트에 있는 Data에 대한 Update 함수의 호출이 많아질 것이고..
Update 함수를 자주 사용한다면, 빈번히 호출되는 자료를 리스트의 앞쪽에 보관하게 될꺼고..
상대적으로 적게 사용되는 것들을 끝으로 밀어서 새로운 자료가 들어왔을 때..
안쓰는 것들을 지워야 효율적일테고..
위의 말 종합하면..LRU 쓰삼이란 뜻이고..
그래서 LRU의 승리고..
뭐.. 그렇고 그런 이야기 ㅡ_ㅡ..

그럼.. 코드 구현은 어떻게!??..

#include 
#include 
#include 
#include 

#ifndef TABLESIZE
#define TABLESIZE	10
#endif
#define HASH(a) ((a) % TABLESIZE)

typedef struct Node {
	int data;
	struct Node *right;
	struct Node *next;
} Node;

Node *head, HashTable[TABLESIZE];
int MaxItem, ItemCounter;

int _Insert(int data);
int Insert(int data, char* policy);
Node* Search(int data, Node** end);
void Update(Node* node);
void func_select(char* policy, Node* p);
void UnlinkMRU(Node* temp);
void UnlinkLRU(Node* temp);
void Delete(Node* node);
char* print(Node* p)
{
	static char buf[1024], t[16];
	for (	memset(buf,'\0',sizeof(char) * 1024);
		p != NULL;
		sprintf(t, "%d ", p->data), strcat(buf, t), p=p->right ) ;
	return buf;
}

void printTable()
{
	int i;
	Node* p;
	for (i=0; inext)
			printf("%d ", p->data);
		putchar('\n');
	}
}
int main(int argc, char* argv[])
{
	int data, ret;
	char mode[4];
	FILE* fp;

	if (argc != 3) exit(1);
	if ((MaxItem = atoi(argv[1])) == 0) exit(1);
	if ((fp = fopen(argv[2],"r")) == NULL) exit(1);

	memset((head=(Node*) malloc(sizeof(Node))), 0x00, sizeof(Node));

	while (!feof(fp) && fscanf(fp, "%3s %d", mode, &data))
	{
#ifdef DEBUG
		printf("input : %3s, %d\n", mode, data);
		printf("before entity list : %s\n", !ItemCounter ? "empty" : print(head->right));
#endif
		ret = Insert(data, mode);
#ifdef DEBUG
		printf("%d is %s in the list.\n", data, ret ? "missing" : "found");
		printf("after entity list : %s\n", print(head->right));
		printTable();
		putchar('\n');
#endif
	}

	printf("final entity list : %s\n", print(head->right));
	printTable();
	return 0;
}
// 실제 데이터를 리스트에 추가
int _Insert(int data)
{
	Node* temp;
	memset((temp = (Node*) malloc(sizeof(Node))), 0x00, sizeof(Node));

	temp->data = data; // 해시 테이블 연결부
	temp->next = HashTable[HASH(data)].next;
	HashTable[HASH(data)].next = temp;

	temp->right = head->right; // 우선순위 리스트 연결부
	head->right = temp;

	return ++ItemCounter;
}
// 선택적 삽입을 위한 분기점
int Insert(int data, char* policy)
{
	Node *temp, *end;

	if ((temp = Search(data, &end)) == NULL && ItemCounter < MaxItem)
		return _Insert(data); // 없는 자료 & 공간 존재

	else if (temp == NULL && ItemCounter >= MaxItem)
	{
		func_select(policy, end);
		return _Insert(data); // 없는 자료 & 공간 무
	}

	else // 이미 있는 자료일때
		return Update(temp), 0;
}
// 자료를 찾아서 존재한다면 바로 전 노드를 반환 (해시 테이블)
Node* Search(int data, Node** p)
{	// p 포인터는 RefCount를 줄여보기 위한 발악
	for (*p=HashTable+HASH(data); (*p)->next != NULL; *p=(*p)->next)
		if ((*p)->next->data == data)
			return (*p)->next;

	return NULL;
}
// 넘어온 노드의 우선순위리스트 전까지 이동해서 수정 (우선순위 리스트)
void Update(Node* node)
{
	Node *p, *target;
	if (head->right == node)
		return ;

	for (p=head; p->right != node; p=p->right) ;
	target = p->right;

	p->right = p->right->right;
	target->right = head->right;
	head->right = target;
}
// Delete 방법 호출 판단 및 레퍼런스 카운트 줄이기 대작전
void func_select(char* policy, Node* p) // 우선순위 리스트의 값
{
	static void (*fp[2])(Node*) = { &UnlinkLRU, &UnlinkMRU };
	int mode = !strcmp(policy, "MRU");
	if (!mode && p->right == NULL)
		p = (p->right != NULL && p->right->next != NULL) ? p->right : head;

	(fp[mode])(p);
}
// 앞의 노드를 삭제 -- 해시 테이블도 조절해야함 (우선순위 리스트)
void UnlinkMRU(Node* temp)
{	//여기 temp는 안씀
	temp = head->right;
	head->right = head->right->right;
	Delete(temp);
}
// 넘어오는 p의 위치에서 부터 찾도록 수정 (우선순위 리스트)
void UnlinkLRU(Node* p)
{	// 그나마 처음부터 검색하지 않게 하기 위함
	for (; p->right!=NULL; p=p->right)
		if (p->right->right == NULL)
			break;

	Delete(p->right);
	p->right = NULL; // 윗쪽에 1번 더 카운팅 되기에 여기선 안함
}
// 넘어오는노드 전까지 이동해서 삭제 (해시테이블)
void Delete(Node* node)
{
	Node *p;
	for (p=HashTable+HASH(node->data); p->next != node; p=p->next) ;
	p->next = p->next->next;
	free(node);
}

더블 리스트 쓰지 말라니.. 닥치고 쓰지 말아야지 ㅡ_ㅡ..
말을 참 잘 듣는 착한 학생..

지난 10월에..
DRM기술때문에 골아파 했던적이 있다..

내 Disk로 Data를 복사하려 하면..
자동으로 Encrypt Module이 Crypt 해버려서..
복사 하면 Decrypt가 불가능 했다..
(내 머리론 아직 analyzing skill이 부족하다..)

Program을 Filter Driver로 구현해서..
Ctrl + Alt + Del 키로 Process를 죽이는 것 만으로는 해결 할 수 없었다..
(Process 조차도.. API Hooking으로 숨겨 버렸다.. OTL..)

그래서 Services Registry Key를 지우는 방법으로..
Windows 시작시 Starting Key를 읽지 못하도록 하는 방법을 생각했다..

그런데 이 망할 나비씨는..
Registry 관련 API 조차 Hooking해서 접근이 불가능하게 막아버린게 아닌가!!..

이대로 물러서야 하는건가에 대해 열심히 고민하던 도중..
나 역시 그들처럼..
윈도우 시작시 Filter Driver나, Native Application으로 Registry에 접근후..
Key를 지워버리는 방식을 사용하기로 했다..

Windows에서 SMSS.exe를 생성한 다음..
Native Application을 시작 할 때는 Trust된 Windows의 일부로 인식하기에..
아무 이상 없이 잘 될거라 믿고 Unloader를 제작했다..

사실 이렇게 실전으로 Native Application을 개발하는건.. 처음이었다..
그래서 착오도 많았고..

...

Format도 많이 했다..(!?)
(사실 VM을 이용해서 그다지 힘들진 않았다..)

여튼..
최종 코드는 아래처럼 완성되었다..

간단하게 Registry Key를 지우는 거라..
극!! 초보적인 코드이다..

이런거로 고민했던 내가 좀 한심했긴 했지만..
어쨌든..
완성판을보니..
나름 뿌듯함도 있었다..

#include "ntddk.h"
#include "NativeAPI.h"

BOOLEAN RegDeleteKey(WCHAR* pwszKey);
BOOLEAN RegOpenKey(HANDLE* phKey, WCHAR* pwszSubKey);
BOOLEAN RemoveDataFromRegValue(
 WCHAR* pwszSubKey,
 WCHAR* pwszValue,
 WCHAR* pwszData
);

void NtProcessStartup(PSTARTUP_ARGUMENT Argument)
{
 ULONG i;
 UNICODE_STRING uString;

 WCHAR Buffer[128];
 WCHAR RootKey[] = L"Services＼＼";
 WCHAR targetKey[][16] = {
  L"FDDec",  // FDDec : SAFASOFT Encrpty Mobile Driver
  L"FileHook", // FileHook : SAFASOFT File System Filter
  L"ProcHide", // ProcHide : ProcHide Driver
  L"SDFA",  // SDFA  : SDFA Driver
  L"SFMouse",  // SFMouse : SAFASOFT Mouse Filter
  L"SFReg",  // SFReg : SAFASOFT Registry Filter
  L"SFRes",  // SFRes : SAFASOFT Resource Driver
  L"SFfolder", // SFfolder : SAFASOFT Encrpty Folder Driver
  L"SFkbd",  // SFkbd : SAFASOFT Keyboard Filter
  L"Safandrv", // Safandrv : Streams Drivers
  L"WWC",   // WWC  : Ww Client for NT
  L"WwHook",  // WwHook : WwHook Driver
  -1
 };

 RtlInitUnicodeString(&uString, L"Starting WwcNT Unloader..\n");
 NtDisplayString(&uString);

 RemoveDataFromRegValue(
  L"Control\\Session Manager",
  L"BootExecute",
  L"unloader"
 );
 RemoveDataFromRegValue(
  L"Control\\Class\\{4D36E96F-E325-11CE-BFC1-08002BE10318}",
  L"UpperFilters",
  L"SFMouse"
 );
 RemoveDataFromRegValue(
  L"Control\\Class\\{4D36E96B-E325-11CE-BFC1-08002BE10318}",
  L"UpperFilters",
  L"SFKbd"
 );

 for (i=0; *targetKey[i] != -1; i++) {
  wcscpy(Buffer, RootKey);
  wcscat(Buffer, targetKey[i]);
  RegDeleteKey(Buffer);
 }

 NtTerminateProcess(NtCurrentProcess(), 0);
}

BOOLEAN RegDeleteKey(WCHAR* pwszKey)
{
 HANDLE hKey, hReg;
 WCHAR szTemp[128], szKeyBuffer[1024] = {0,};

 ULONG uIndex=0, uRetSize=0;
 PVOID pBuffer[1024] = {0,};

 PKEY_BASIC_INFORMATION pKeyInfo = NULL;

 if (!RegOpenKey(&hKey, pwszKey))
  return FALSE;

 wcscpy(szTemp, pwszKey);
 wcscat(szTemp, L"＼＼");

 while (1)
 {
  wcscpy(szKeyBuffer, szTemp);
  RtlZeroMemory(pBuffer, 1024);

  switch (NtEnumerateKey(
    hKey,
    uIndex++,
    KeyBasicInformation,
    pBuffer, 1024, &uRetSize))
  {
  case STATUS_SUCCESS:
   pKeyInfo = (PKEY_BASIC_INFORMATION)pBuffer;
   wcscat(szKeyBuffer, pKeyInfo->Name);

   if (RegOpenKey(&hReg, szKeyBuffer)) {
    NtDeleteKey(hReg);
    NtClose(hReg);
    uIndex--;
   }

   pKeyInfo = NULL;
   break;

  case STATUS_NO_MORE_ENTRIES:
   NtDeleteKey(hKey);
   NtClose(hKey);
   return TRUE;

  default:
   NtClose(hKey);
   return FALSE;
  }
 }
}

BOOLEAN RemoveDataFromRegValue(
 WCHAR* pwszSubKey,
 WCHAR* pwszValue,
 WCHAR* pwszData )
{
 HANDLE hReg;
 UNICODE_STRING ustrValue;

 PVOID pBuffer[1024] = {0,};
 ULONG uRetSize;

 WCHAR *pStr, szBuffer[1024] = {0,};
 ULONG uStr=0, sIndex=0, uBuffer=0;

 PKEY_VALUE_PARTIAL_INFORMATION pValue = NULL;

 if (RegOpenKey(&hReg, pwszSubKey)) {
  RtlInitUnicodeString(&ustrValue, pwszValue);

  if (NtQueryValueKey(
   hReg,
   &ustrValue,
   KeyValuePartialInformation,
   pBuffer, 1024, &uRetSize) != STATUS_SUCCESS)
  {
   NtClose(hReg);
   return FALSE;
  }

  pValue = (PKEY_VALUE_PARTIAL_INFORMATION)pBuffer;

  if (pValue->Type == REG_MULTI_SZ) {
   pStr = (WCHAR*)pValue->Data;

   while (1) {
    uStr = wcslen(&pStr[sIndex]) + 1;
    if (uStr < 2)
     break;

    if (wcscmp(&pStr[sIndex], pwszData) != 0) {
     memcpy(
      &szBuffer[uBuffer],
      &pStr[sIndex],
      uStr*sizeof(WCHAR)
     );
     uBuffer += uStr;
    }

    sIndex += uStr;
   }

   szBuffer[++uBuffer] = 0;
   NtSetValueKey(
    hReg,
    &ustrValue,
    0,
    REG_MULTI_SZ,
    szBuffer, uBuffer*sizeof(WCHAR)
   );
  }

  NtClose(hReg);
  return TRUE;
 }

 return FALSE;
}

BOOLEAN RegOpenKey(HANDLE* phKey, WCHAR* pwszSubKey)
{
 UNICODE_STRING ustrKeyName;
 WCHAR Buf[1024] = L"\\Registry\\Machine\\SYSTEM\\CurrentControlSet＼＼";
 OBJECT_ATTRIBUTES ObjectAttributes;

 wcscat(Buf, pwszSubKey);
 RtlInitUnicodeString(&ustrKeyName, Buf);
 InitializeObjectAttributes(
  &ObjectAttributes,
  &ustrKeyName,
  OBJ_CASE_INSENSITIVE,
  NULL,
  NULL
 );

 return ((!NT_SUCCESS(
   NtOpenKey(
    phKey,
    KEY_ALL_ACCESS,
    &ObjectAttributes)
   )
  ) ? FALSE : TRUE );
}