Finals Begin!

It's finals week here at Florida Tech. Today was the start of hell week for me. I took my Formal Languages exam today, so 1 down! but 5 more left :S. I'm going back home Saturday to spend about 9 days with my girlfriend and family. After the ten days I leave for Seattle. This summer I'm going back to Microsoft to do another internship with the ASP.NET developer team. Wish me luck this week!!!

Coding in Haskell

Programming Language class is alot of fun (sometimes). I spent part of the weekend studying for exams and playing with haskell. I realized I missed one part of the assignment after I submitted, but it was an interesting formatting issue. What's most interesting about functional languages is how concise the code is for some complex problem. Consider the following problem:

I have a list of strings and I want to put an element o after every n elements in the list, then convert the list to one space delimited string.

Lets try to do it in C++ :

string insertEvery(int n, string o, vector<string> & vs) {
	string res = "";
	int pos = 0;
	for(vector<string>::iterator it = vs.begin(); it != vs.end(); ++it) {
		res += *it;
		if(++pos % n == 0) {
			res += " " + o + " ";
		}
		else {
			res += " ";
		}
	}
	return res;
}

Next up C# (Kind of a different approach):

string insertEvery(int n, string o, List<string> list) {		
	for (int i = n; i < list.Count; i+=n) {
		list.Insert( i++, o );			
	}
	return string.Join( " ", list.ToArray() ).Replace( " " + o + " ", o );
}

And the winner...Haskell :

insertEvery n y [] = []
insertEvery n y x = (take n x) ++ [y] ++ insertEvery n y (drop n x)
insertEveryToString n y x = concat $ intersperse " " $ insertEvery n y x

I love the concise function definitions. Thinking totally recursive is hard at first, but once you get it everything just pieces together...

Microsoft Interviews

Last week , a couple of my friends had Microsoft phone interviews. Since I got my internship last summer, they have been coming to me for advice and interview "training". In coming up with some questions to give my friends, I remembered the isPalindrome function I saw a while back and came up with this question:

	bool isPalindrome(int x) {
	}

x is guaranteed to be a positive number, and single digit numbers are palindromes.  By the way converting to a string is not an option :D nice try.

Software Engineering Project

My team for the Software Engineering class had to develop a website. check it out.

Windows Systems Programming

My last assignment was Dll Injection. We had to take a random process ID and if the application had winsock loaded, we were to intercept functions connect, recv, send, and closesocket and print the parameters.

After trying various methods and failing, e.g overwriting the IAT(Import Address Table) etc. I deceided to go the hard ,fickle way.

Here was the process described by a Microsoft research paper i found.

Create 2 functions,  a Trampoline function and a Detour function.

• Create a Trampoline function
• Copy the first 5 bytes of the real function to the Trampoline function
• Add an unconditional jmp to the 6th byte of the real function
• Overwrite the real function with an unconditional jmp to your Detour function.
• At the end of your Detour function jump to the trampoline function.

Sounds kinda confusing. If you think that's bad look some of the code i wrote.

void CopyToTrampoline( LPVOID lpTargetFunction,  LPVOID lpTrampoline , int offset ) {
	DWORD old;				

	PBYTE pbActual = (PBYTE)lpTargetFunction;
	PBYTE pbTramp = (PBYTE)lpTrampoline;

	//make page writable
	VirtualProtect( lpTrampoline, 5 + offset, PAGE_WRITECOPY, &old );
				
	for(int i = 0; i < offset; ++i) {					
		*pbTramp++ = *pbActual++;
	}	
	pbActual = (PBYTE)lpTargetFunction;

	//set jump
	*pbTramp++ = 0xe9;

	*((DWORD*)pbTramp) = (pbActual + offset) - (pbTramp + 4);

	//restore protections
	VirtualProtect( lpTrampoline, 5 + offset, PAGE_EXECUTE, &old);
}

void Redirect(PVOID lpTargetFunction, PVOID lpDetourFuntion) {
	DWORD old;

	VirtualProtect( lpTargetFunction, 5, PAGE_WRITECOPY, &old);
	//copy unconditional jump
	*((PBYTE)lpTargetFunction) = 0xe9;

	//copy the next 4 bytes
	*((DWORD*)((PBYTE)lpTargetFunction+1)) = PtrToUlong(lpDetourFuntion) - (PtrToUlong(lpTargetFunction) + 5);

	//restore
	VirtualProtect( lpTargetFunction, 5, PAGE_EXECUTE, &old);
}

The worst thing about getting help online if when they show you a function but not how to use it, but i will not do the same :).

	
void Intercept(PVOID lpTargetFunction, PVOID lpTrampoline,  LPVOID lpDetourFuntion, int offset) {
	
	CopyToTrampoline( lpTargetFunction, lpTrampoline , offset);
	
	Redirect( lpTargetFunction, lpDetourFuntion );
	// Flush the instruction cache to make sure 
	// the modified code is executed.
	FlushInstructionCache(GetCurrentProcess(), NULL, NULL);

}

//Intercepting connect function in winsock
//get winsock2 module
HMODULE hWinSock = GetModuleHandleA("ws2_32.dll");
if(hWinSock) {
	Intercept( connect, ConnectTrampoline, MyConnect, 5 );
}

The ConnectTrampoline and MyConnect are both naked.

Technorati tags: Api Hooking, Hooks, Winsock, C++/C, Win32

Camping out

My school has this weird tradition, where students that wish to sign up for the on campus apartment have to "camp out" outside of the housing office until its opened. This is all because of the first come first serve policy. The signup for Southgate apartments are this Sunday, yet I am in a tent from Wednesday because of the crazy attitude of Americans wanting to be the first. This kinda thing isn't uncommon in here though. Just last year there were millions in line waiting for the playstation 3 and nintendo wii so I'm not very surprised. The tent isn't all bad though except the the fact that as summer in Florida approaches the days are getting warmer.. and by warmer I mean 25 degrees Celsius with no wind.. So I sit patiently between classes in my tent waiting until Sunday to attempt to get a single room for my last 2 semesters at Florida Tech.

Programming the Atmel16

So like I said I got my hands wet programming an LCD. The initial code written by the computer engineers to display the characters to the screen was something like:

  UDR = 0xFE; //tell the port we want to send
  UDR = 0x01; // clear the LCD
  UDR = 'L';
  delay_ms(120);
  UDR = 'u';
  delay_ms(120);
  .... etc

This code hurt me, so I was determined to improve it :P. First of all notice the magic numbers 0xFE and 0x01, the comments do help us understand what they mean but they are not very clear. Better to do this :

 #define CLEAR(port) { port = 0xFE; port = 0x01; }
 #define SETPOS(port, pos) { port = 0xFE; port = 0x80; port = pos }
 ...
 typedef unsigned char byte;

 void print_to_lcd(char* buffer) {
      .... check the string size and for NULL
      CLEAR(UDR); //clear LCD
      SETPOS(UDR, 0) // start at first position of LCD
      byte* p = (byte*)buffer; //the serial port wants bytes
      while(*p) {
        UDR = *p++;
        delay_ms(120);
      }
 }

This was only the beginning improvement. Everyday programming paradigm, write a function for something we want to reuse throughout the program. Now they could just call print_to_lcd("Lunar Raiders") and we get the same effect as before with less code. But I had a funny feeling inside that I was reinventing the wheel, which is not always a bad thing, but I did a little research. They are C functions like printf, fopen ..etc that print characters or bytes to the stdout. Since the hardware has no notion of a console, maybe there was a way to redirect the stdout to mean the UDR(uart port) on the board. After a little research this is what I found:

init() {
 ... initialize board

// associate uart output function with stdio 
  fdevopen(uart_putchar, NULL,0);                        
} 

int uart_putchar(char c) { 
   if (c == '\n') 
      uart_putchar('\r');
   loop_until_bit_is_set(UCSRA, UDRE); 
   UDR = c; 
   return 0;
}

Knowing what to search for is sometimes harder that knowing what to do. After finding this code I could use printf("%s %d", "this is cool" ,4 + 5); and like normal and it would print to the LCD.

 

del.icio.us tags: Atmel, C++/C, Embedded, Hardware

Senior Design Showcase

Yesterday, from 11am to 5pm seniors and juniors showed projects they were working and will be working on for the next year. Three projects in particular appealed to me. Wakeup Word Speech Recognition, Lunar Raiders Autonomous Robot, and Eye Tracking software. All three are computer engineering projects and one of the benefits of senior design at this school is the ability to cross majors to work on projects allow you to broaden you skills. Yesterday was the first time I ever programmed any piece of hardware. It was an LCD on the Lunar Raiders dev board, now I am hooked.. The speech recognition is an area of research done by Dr. Veton Kepsuka here at Florida Tech, and it still could use some work. What I would propose maybe is a generic API in .NET/C++ which allows you to easily integrate his speech into your existing program. Anyways I'll try to make my decision and see how it goes from there.

Senior Design Blues

It's senior year for me at university and I have to decide on a "big project" that all/most seniors complete and present before they graduate. Last Friday students starting their senior design next semester were gathered, and professors showed what "interesting" things they were doing, research wise. Its kinda hard to decide if I should try to come up with my own project or join another team. If you have any suggestions on something I can "build"(application wise) or maybe some useful device let me know.

Answer!

Yesterday a few people were asking about possible solutions to the problem. Here is my solution.

	if(!printf("hello")) {
		printf("hello");
	}
	else {
		printf("world");
	}

At a glance it seems impossible. There is no way to take both paths in an if statement.Therefore we need a 
function that returns false and prints hello.If you know C/C++ really well you'd know that printf returns the number of 
characters printed to stdout and if you negate that, you get zero. I welcome any other solutions that you come up with.

printf reference

Best Google interview question

A few weeks ago, a friend approached me with a set of google interview questions. There was one that i found particularly interesting, and really creative.

	if(condition) {
		printf("hello");
	}
	else {
		printf("world");
	}

What condition prints "helloworld"?

i'll post the solution tomorrow.

Technorati tags: google, interview, interview questions, C/C++

Top Coder Open

I've been into programming for a while, but not competitively(I mean it's not like it's a sport :) ) , until I came to this school. Topcoder is a competitive programming/development site where young or old programmers can participate in a series of contest which test different skill set. I prefer the algorithm competition. Even though my rating is not that high, I enjoy participating alot. Recently I qualified for the TCO, that's the Top Coder Open tournament. I'm really excited to be a part of this tournament with some of the worlds best programmers! I'm Round 1B on Tuesday wish me luck.

First Post

Hey guys this is my first post. Welcome to David's Place. I'm a computer scientist at Florida Institute of Technology from Barbados(not Jamaica) , its in the Caribbean for those who don't know. Its a small island most easterly of all the Caribbean.