Burrows Code Blog

February 19, 2011

Emailify – Internal Stylesheets to Inline Styles

Filed under: Web Development — Tags: , , , , , , , , , — burrowscode @ 8:32 pm

(Note, see the git repository for bleeding edge code)

I haven’t blogged in what seems like eons, but with outpour of emails begging me to produce content, I’ve decided to appease the masses.

This project will make more sense with some context. So context. At work I’ve been charged with implementing our HTML email alert system. As of right now all of our alerts are produced in plain text, and plain text is fucking hard to read (no matter how much eye-candy ascii art we add). One of the challenges with getting the system up and running was producing a html/css spec that would render properly in most email clients. So when our designer presented me the final spec, I shuddered when I realized that all of the styles were inline because email clients don’t really support internal stylesheets (and clearly not external stylesheets).

After reading about two lines of this madeness: <tr styles="font-weight: 400; font-size: 12px; width: 100px; height: 20px;">

I realized, SOMETHING MUST BE DONE.

Thus I looked around to see if anyone was providing a service to convert internal stylesheets to inline styles. And I found stuff like this Internal to Inline Generator and HTML Composition Thing. Those projects seemed to be a good start, so they inspired me to put together a piece of ruby code that automate the process in a way that would be useful when one’s code is using something like ActionMailer.

And the result of said inspiration and about 3 hours of work (with intermittent Reddit usage, proggit ftw) is Emailify. The code is still far from complete (the bug hunt has just begun, in particular I expect there to be issues with the way that I am handling scope, still need to read the CSS specification so that can be handled correctly) but it seems to work on simple code.

The code itself is pretty straightforward. First it parses the html document with REXML and then pulls out the relevant css section and hands those off to CssParser. We then iterate through the html document (while keeping track of our current scope, probably broke) and then applying relevant styles at each step along the way. Once the code is a bit more robust I think that I’ll throw it into a gem and release it for the greater good of web developers errrrywhere.

Most of the implementation is a chainfest, BUT THAT’S JUST HOW I ROLL.

Here’s the code for those of you too lazy to click the github link.

class Emailify
  require 'css_parser'
  require 'rexml/document'
  require 'rexml/parsers/treeparser'
  include CssParser
  include REXML

  def initialize(html_data)
    @html_data = html_data
  end

  def get_cleaned_data
    convert_internal_styles_to_inline_styles
  end

  private
  def convert_internal_styles_to_inline_styles
    html = Document.new(@html_data)
    css_parser = CssParser::Parser.new
    get_script_tags(html.elements, 'css').each {|s| css_parser.add_block!(s.text)}
    go_from_internal_to_inline!(html.elements.dup, css_parser)
  end

  def get_script_tags(data, type)
    data.map {|e| handle_script_tags(e, type)}.flatten
  end

  def handle_script_tags(e, type)
    return e if check_type(e, type) 
    return get_script_tags(e.elements, type)
  end

  def check_type(e, type)
    e.attributes['type'] == "text/#{type}"
  end

  def go_from_internal_to_inline!(data, css_parser, scope=[])
    # No map!
    data = data.map {|e| handle_all_tags!(e, css_parser, scope)}
    # puts data
    data
  end

  def handle_all_tags!(e, css_parser, scope=[])
    scope.push(get_scope_info(e))
    apply_inline_styles!(e, get_relevant_styles(css_parser, scope))

    go_from_internal_to_inline!(e.elements, css_parser, scope)
    scope.pop
    e
  end
  
  def get_scope_info(e)
    {:id => "#{e.name}##{e.attributes['id']}" || nil, :class => "#{e.name}.#{e.attributes['class']}" || nil, :tag => e.name}
  end

  def apply_inline_styles!(e, styles)
    # OUT FORMAT: [{:style => x, :value => y}, ...]
    fixed_styles = styles.inject([]) do |arr, s| 
      arr + s[:declarations].split(';').inject([]) do |sub_arr, dec| 
        sub_arr.push({:style => $1.strip, :value => $2.strip}) if dec =~ /(.+):(.+)/m
      end
    end
    
    fixed_styles.each {|s| e.attributes[s[:style]] = s[:value]}
  end

  def get_relevant_styles(css_parser, scope)
    ret = []
    css_parser.each_selector {|sel, decs, spec| ret.push({:selector => sel, :declarations => decs, :specificity => spec}) if in_scope?(sel, scope)}
    ret
  end

  def in_scope?(sel, scope)
    added, dup_scope, sels = 0, scope.dup, sel.split(' ')
    sels.reverse_each.select do |sctor| 
      if index = flatten_get_tags(dup_scope).index(sctor)
        dup_scope = dup_scope.take((index) / 3)
        added += 1
        true
      end
    end

    added == sels.length
  end

  def flatten_get_tags(scope)
    scope.map(&:to_a).flatten.reject {|s| s.is_a?(Symbol)}
  end
end

html_data = %q{
  <html>
    <head>
      <script type="text/css">
        body.test-class {color: #222}
        h1#test-id {font-size: 20px}
        body p.p-class {font-size: 25px; font-weight: 400;}
      </script>
    </head>
    <title>WHAT IT BE YO</title>
    <body class="test-class" color="#111">
      <h1 id="test-id">HEY THERE</h1>
      <p class="p-class">
        This is a bunch of text. Text is cool.
      </p>
    </body>
    <script type="text/css">
      .another-class {font-weight: 400}
    </script>
    <script type="text/javascript">
      PLACEHOLDINGNSHIT
    </script>
  </html>
}
e = Emailify.new(html_data)
puts e.get_cleaned_data

Also mad props to Alex Dunae for writing CssParser as I really didn’t want to write a css parser.

Until later.

December 16, 2010

Execute Tweets

Filed under: Web Development — Tags: , , , — burrowscode @ 8:12 pm

This post is a pretty large deviation from content that I’ve posted in the past, but it’s much more relevant to the work I’ve been doing recently. The project is designed to effectively execute and tweet the side effects of code found in mentions (this is when someone tweets a reply towards you) towards your twitter. The premise is pretty simple and all the code involves is some basic knowledge of OAuth, Twitter API, and ruby.

I will commence a brief walk through of the code. The OAuthAgent class is entirely dedicated to handling the initial security handshaking required to use the Twitter API. In short, you provide the class with your secret and key, and from there it handles the security signatures that will be attached to all communications with the Twitter server. The TwitterAgent class is very simple and currently only includes two methods. The first method simply allows tweeting and the second polls to get the most recent mentions. TweetToCompileVm is the final class and it is trivial as well. It uses a regex to parse the code from the tweet (it expects this format ) and then has another function that redirects stdout and calls eval to execute the code.

A couple of things to consider if you decide to employ the code or even just the general technique. First of all you’ll probably want to implement a true polling mechanism in TweetToCompileVm that will alert you when a new mention occurs thus allowing you to be proactive in your responses to mentions. As a side effect of this, it becomes virtually impossible to monitor the type of code that someone is trying to make your system execute. Because of this, you will need to sandbox the ruby interpreter in order to prevent people from completing malicious acts on your system.

And yes I realize that TweetToCompile is a misleading name and that TweetToRun or TweetToExecute would have been a more proper name. Here’s the code.

=begin
    TweetToCompile a project that let's you run short scripts
        using Twitter.
    Aaron Burrow (burrows@mit.edu)
=end

gem 'oauth'
require 'oauth'
require 'oauth/consumer'
require 'rexml/document'
require 'stringio'

class OAuthAgent
  attr_accessor :key, :secret, :url
  
  def initialize(key=nil, secret=nil, url=nil)
    @key, @secret, @url = key, secret, url
    if @key.nil? == @secret.nil? and @secret.nil? == @url.nil? and @url != nil
      @consumer = OAuth::Consumer.new key, secret, :site => url
    else
      @consumer = nil
    end
  end
  
  def getRequestToken
    if @consumer.nil?
      @consumer = OAuth::Consumer.new @key, @secret, :site => @url
    end
    @consumer.get_request_token
  end

  def getPin(requestToken)
    puts "Go to this URL and get the pin.\n#{requestToken.authorize_url}"
    gets.chomp
  end

  def getAccessToken
    requestToken = getRequestToken
    pin = getPin(requestToken)
    @accessToken = requestToken.get_access_token(:oauth_verifier => pin)
  end
end

class TwitterAgent < OAuthAgent
=begin
  Need to add code that will do error checking for the return of 
    RESTful requests.
=end

  def updateFeed(text)
    response = @accessToken.post '/statuses/update.xml', :status => text
  end
  
  def getMostRecentMention
    response = @accessToken.get '/statuses/mentions.xml', "count" => "1"
    doc = REXML::Document.new(response.body)
    doc.root.elements[1].elements["text"].text
  end
end

class TweetToCompileVm
  attr_accessor :accountName

  def initialize(accountName="TweetToCompile")
    @accountName = accountName
  end

  def parseTweet(tweet)
    @code = tweet.sub(/@#{@accountName}\s+/i, "")
  end

  def executeCode
    sio = StringIO.new
    oldStdout, $stdout = $stdout, sio
    eval(@code)
    $stdout = oldStdout
    sio.string
  end
end

Example usage…

agent = TwitterAgent.new key, secret, "https://api.twitter.com"
agent.getAccessToken
tweet = agent.getMostRecentMention

vm = TweetToCompileVm.new
vm.parseTweet(tweet)

Until later.

October 16, 2010

Get Master File Table Offset

Filed under: General Programming — Tags: , , , , , , — burrowscode @ 1:31 pm

During the previous summer I worked on a research project that focused heavily on data mining and interpolation. The nature of the project required data to be constantly switched from physical memory to RAM. As a result, I looked into a variety of read techniques for a variety of file systems. One piece of code I wrote used the Master File Table to directly index file locations from disk. This technique was of course completely inefficient for fast lookups, but it was useful in that it gave me a better understanding of the NTFS file system.

Anyways, I took this code and cannibalized it so that it will just read a systems volume boot sector and then give you the master file table’s byte offset. The code just uses a series of ReadFile calls to the physical drive in order to read the volume boot sector. At which point we just uses some arithmetic to determine where the master file table is located.

Once you know the location of the master file table you can iterate through the segments in order to read files on the system. I didn’t include the code that accomplishes that task as it’s simply a matter of reading headers and manipulating the offset into the disk.


// Get Master File Table Offset
// Aaron Burrow (burrows@mit.edu)

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <windows.h>
#include <tchar.h>

typedef struct _Volume_Boot_Sector {				// Offsets
	BYTE jmp_boot_ldr[3];							// 0x00
	UCHAR system_id[8];								// 0x03
	WORD bytes_per_sector;							// 0x0B
	BYTE sectors_per_cluster;						// 0x0D
	WORD reserved_sectors;							// 0x0E
	BYTE reserved1[3];								// 0x10
	WORD unused1;									// 0x13
	BYTE media_desc;								// 0x15
	WORD reserved2;									// 0x16
	WORD sectors_per_track;							// 0x18
	WORD number_of_heads;							// 0x1A
	DWORD hidden_sectors;							// 0x1C
	DWORD unused2;									// 0x20
	DWORD unused3;									// 0x24
	DWORDLONG total_sectors;						// 0x28
	DWORDLONG mft_logical_cluster_number;			// 0x30
	DWORDLONG mft_mirror_logical_cluster_number;	// 0x38
	DWORD cluters_per_file_record_seg;				// 0x40
	DWORD cluster_per_index_block;					// 0x44
	DWORDLONG volume_serial_number;					// 0x48
	DWORD checksum;									// 0x50
} __attribute__ ((__packed__)) Volume_Boot_Sector, *PVolume_Boot_Sector;

// This is just a container we use to simplify code
typedef struct _Physical_Drive_Descriptor{
	HANDLE physical_handle;
	USHORT sector_size;			// In bytes
	USHORT cluster_size;		// In bytes
} Physical_Drive_Descriptor, *PPhysical_Drive_Descriptor;

Physical_Drive_Descriptor* init_physical_drive_descriptor(VOID);
VOID cleanup_physical_drive_descriptor(Physical_Drive_Descriptor* ptr_phys_desc);
DWORD read_physical_volume(Physical_Drive_Descriptor* ptr_phys_desc, LPTSTR drive_path, BYTE** buffer);
BOOL get_volume_boot_sector(Physical_Drive_Descriptor* ptr_phys_desc, BYTE* buffer, Volume_Boot_Sector* vol_boot_sector);
LONGLONG get_master_file_table_offset(Physical_Drive_Descriptor* ptr_phys_desc, Volume_Boot_Sector vol_boot_sector);

INT main(INT argc, LPTSTR* argv)
{
	LPTSTR drive = TEXT("C");
	BYTE* buffer;
	TCHAR path[MAX_PATH + 1];
	INT size;
	LONG file_size;
	LONGLONG mft_offset;
	Physical_Drive_Descriptor* phys_desc;
	Volume_Boot_Sector vol_boot_sector;
	
	_stprintf(path, TEXT("\\\\.\\%s:"), drive);
	if ((phys_desc = init_physical_drive_descriptor())) {
		if ((size = read_physical_volume(phys_desc, path, &buffer)) > 0) {
			if (get_volume_boot_sector(phys_desc, buffer, &vol_boot_sector)) {
					mft_offset = get_master_file_table_offset(phys_desc, vol_boot_sector);
					printf("MFT Offset: %llX\n", mft_offset);
			}
			free (buffer);
		}
		cleanup_physical_drive_descriptor(phys_desc);
	}
	
	return 0;
}

Physical_Drive_Descriptor* init_physical_drive_descriptor(VOID)
{
	Physical_Drive_Descriptor* temp = calloc(1, sizeof(Physical_Drive_Descriptor));
	if (temp)
		temp->physical_handle = INVALID_HANDLE_VALUE;
	return temp;
}

VOID cleanup_physical_drive_descriptor(Physical_Drive_Descriptor* ptr_phys_desc)
{
	if (ptr_phys_desc->physical_handle != INVALID_HANDLE_VALUE)
		CloseHandle(ptr_phys_desc->physical_handle);
	free (ptr_phys_desc);
	return;
}

DWORD read_physical_volume(Physical_Drive_Descriptor* ptr_phys_desc, LPTSTR drive_path, BYTE** buffer) // Thanks to Napalm@netcore2k, he originally helped me with this function
{
	TCHAR physical_drive_path[MAX_PATH+1];
	DWORD bytes_read;
	*buffer = NULL;
	ptr_phys_desc->physical_handle = INVALID_HANDLE_VALUE;
	
	ptr_phys_desc->physical_handle = CreateFile(drive_path, GENERIC_READ, FILE_SHARE_READ | FILE_SHARE_WRITE, NULL, OPEN_EXISTING, 0, NULL);
	if (ptr_phys_desc->physical_handle == INVALID_HANDLE_VALUE)
		goto cleanup_exit;

	if (!(*buffer = calloc(512, sizeof(BYTE))))
		goto cleanup_exit;
	
	if (SetFilePointer(ptr_phys_desc->physical_handle, 0, NULL, FILE_BEGIN) == INVALID_SET_FILE_POINTER)
		goto cleanup_exit;
		
	if (!ReadFile(ptr_phys_desc->physical_handle, *buffer, 512, &bytes_read, NULL))
		goto cleanup_exit;
	
	return bytes_read;
	
cleanup_exit:
	if (ptr_phys_desc->physical_handle != INVALID_HANDLE_VALUE) {
		CloseHandle(ptr_phys_desc->physical_handle);
		ptr_phys_desc->physical_handle = INVALID_HANDLE_VALUE;
	}
	
	if (*buffer)
		free (*buffer);
		
	return -1;
}

BOOL get_volume_boot_sector(Physical_Drive_Descriptor* ptr_phys_desc, BYTE* buffer, Volume_Boot_Sector* vol_boot_sector)
{
	memcpy((void*)vol_boot_sector, (void*)buffer, sizeof(Volume_Boot_Sector));
	if (!(_tcsncmp(vol_boot_sector->system_id, TEXT("NTFS"), 4))) {
		ptr_phys_desc->sector_size = vol_boot_sector->bytes_per_sector;
		ptr_phys_desc->cluster_size = vol_boot_sector->bytes_per_sector * vol_boot_sector->sectors_per_cluster;
		return TRUE;
	}
	else
		return FALSE;
}



LONGLONG get_master_file_table_offset(Physical_Drive_Descriptor* ptr_phys_desc, Volume_Boot_Sector vol_boot_sector)
{
	return (LONGLONG)vol_boot_sector.bytes_per_sector * vol_boot_sector.sectors_per_cluster * vol_boot_sector.mft_logical_cluster_number;
}

Until later.

August 5, 2010

Injecting Code with Asynchronous Procedure Calls

Filed under: General Programming — Tags: , , , — burrowscode @ 5:49 am

Code injection is a technique that allows you to modify a remote process. In many cases dynamic link library injection suffices. However, there are times that such a technique is undesirable, particularly if the target application is monitoring the API combination generally associated with such an injection. In these cases, an alternate technique is necessary.

Asynchronous Procedure Calls (APC) give a viable alternative for code injection. APCs allow a process to queue the running of a function until the process is in an alertable state. Thus, we force an application to run our code once it enters an alertable state (example, SleepEx). When doing this you must consider that you can not rely on the IAT of the foreign process aligning with the IAT of your current process. Thus you can not directly call APIs. You will have to use a workaround such as first reading the remote processes IAT and then passing the desired API address to your APC.

In order to view the code working. Run an executable in a debugger, determine the address of some writable bytes, change the address in apc_me to that, then execute the process and watch the memory change.

The code is pretty simple, and I’m pretty tired so I’m just going to post it now and I’ll get around to writing a better explanation at a later date. Some code maintenance is also needed, such as putting the code in main into a function, actually finding the size of the function when using VirtualAllocEx and WriteProcessMemory, and other general style stuff.

But anyways here is the code.

// Code Injection using APC
// Creative Commons - Aaron Burrow

#define _WIN32_WINNT 0x501

#include <stdlib.h>
#include <stdio.h>
#include <windows.h>
#include <Tlhelp32.h>

VOID CALLBACK apc_me(ULONG_PTR param);
BOOL Get_Thread_ID(LPSTR proc_name, LPDWORD tid, LPDWORD pid);
BOOL Apply_And_Execute_APC(DWORD tid, DWORD pid, VOID CALLBACK (*function)(ULONG_PTR), ULONG_PTR arg, DWORD size);

INT main(INT argc, LPSTR* argv)
{
	DWORD data = 10, tid, pid;
	HANDLE thread_handle, process_handle;
	LPVOID addr;
	SIZE_T size;
	
	if (Get_Thread_ID("t.exe", &tid, &pid)) {
		Apply_And_Execute_APC(tid, pid, apc_me, 10, 500);
	}
	return 0;
}

// Just an example APC function
VOID CALLBACK apc_me(ULONG_PTR param)
{
	*((INT*)0x7FFD6000) = 0xDEADBEEF;
	// __asm__ ("int $0x3\n");
	return;
}

/*
	Get the thread id for some thread running in proc_name as
		well as the process id;
	@proc_name: The name of the process to get infos on.
	@tid: Stores the thread id.
	@pid: Stores the process id.
	return: FALSE on failure, TRUE on success.
*/
BOOL Get_Thread_ID(LPSTR proc_name, LPDWORD tid, LPDWORD pid)
{
	HANDLE snapshot = NULL;
	PROCESSENTRY32 proc_entry;
	THREADENTRY32 thread_entry;
	BOOL found = FALSE, test;
	
	snapshot = CreateToolhelp32Snapshot(TH32CS_SNAPPROCESS, 0);
	if (snapshot == INVALID_HANDLE_VALUE)
		goto cleanup_exit;
		
	proc_entry.dwSize = sizeof(PROCESSENTRY32);
	test = Process32First(snapshot, &proc_entry);
	if (test == FALSE)
		goto cleanup_exit;
	
	do {
		if (!(strcmp(proc_entry.szExeFile, proc_name))) {
			*pid = proc_entry.th32ProcessID;
			found = TRUE;
			break;
		}
	} while (Process32Next(snapshot, &proc_entry));
	
	if (found == FALSE)
		goto cleanup_exit;
	
	CloseHandle(snapshot);
	
	snapshot = CreateToolhelp32Snapshot(TH32CS_SNAPTHREAD, 0);
	if (snapshot == INVALID_HANDLE_VALUE)
		goto cleanup_exit;
	
	
	thread_entry.dwSize = sizeof(THREADENTRY32);
	test = Thread32First(snapshot, &thread_entry);
	if (test == FALSE)
		goto cleanup_exit;
	
	found = FALSE;
	do {
		if (thread_entry.th32OwnerProcessID == *pid) {
			*tid = thread_entry.th32ThreadID;
			found = TRUE;
			break;
		}
	} while(Thread32Next(snapshot, &thread_entry));
	
	return TRUE;
	
cleanup_exit:
	if (snapshot)
		CloseHandle(snapshot);
	return FALSE;
}

/*
	Responsible for writing the function to the remote address space
		as well as putting it into the threads APC queue.
	@tid: Thread id of the thread to execute the APC.
	@pid: Process id of the process the thread is in.
	@function: The actual APC.
	@arg: An argument to be passed to the APC.
	@size: The size of the APC.
	return: FALSE on failure, TRUE on success.
*/
BOOL Apply_And_Execute_APC(DWORD tid, DWORD pid, VOID CALLBACK (*function)(ULONG_PTR), ULONG_PTR arg, DWORD size)
{
	HANDLE thread_handle = NULL, process_handle = NULL;
	LPVOID addr;
	BOOL test;
	DWORD out_size;
	
	thread_handle = OpenThread(THREAD_ALL_ACCESS, FALSE, tid);
	if (!thread_handle)
		goto cleanup_exit;
	
	process_handle = OpenProcess(PROCESS_ALL_ACCESS, FALSE, pid);
	if (!process_handle)
		goto cleanup_exit;
		
	addr = VirtualAllocEx(process_handle, NULL, 500, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
	if (!addr)
		goto cleanup_exit;
	
	test = WriteProcessMemory(process_handle, addr, (LPCVOID)function, size, &out_size);
	if (test == FALSE)
		goto cleanup_exit;
	
	test = QueueUserAPC((PAPCFUNC)addr, thread_handle, arg);
	if (!test)
		goto cleanup_exit;
	
	CloseHandle(process_handle);
	CloseHandle(thread_handle);
	return TRUE;
	
cleanup_exit:
	if (process_handle)
		CloseHandle(process_handle);
	if (thread_handle)
		CloseHandle(thread_handle);
	return FALSE;
}

Until later.

[update] Fixed the code.

July 18, 2010

Determining If Your Process is Being Debugged

Filed under: Kernel Modules, Reverse Engineering — Tags: , , , , — burrowscode @ 9:12 pm

There are numerous situations when you may want to find out if your process is being debugged. The most notable is if you are writing a protection scheme for some software. As the ability to detect debugging can be an instrumental part of your protection. Note that the methods I am going to show you are not perfect and can be circumvented using a variety of techniques.

The first thing you can do is use the trivial IsDebuggerPresent(). This function works by checking the processes program environment block (PEB) as there is a member variable called BeingDebugged which will be set to TRUE if the process is being debugged. Thus it is simple to bypass this method by simply changing this value in the PEB.

Another way that you can check for debugging is by testing bit 8 of the FLAGS register. This is the trap flag and if set to 1 this means that the program is single stepping, a very good indication of debugging. You can accomplish this with a piece of code like this.

BOOL Is_Being_Debugged(VOID)
{
	USHORT flags;
	__asm__ (
		"pushf\n"
		"pop %0\n"
		: "=r" (flags)
		:
		: "%eax"
	);
	return ((( flags >> 8 ) & 1 ) == 1 );
}

The easiest way to circumvent this is to watch for a similar piece of code in the debugger and simply change the return value (eax). You also should be able to unset the trap flag, insert a software break point after the code, and then set the flag again.

A third way to detect when a program is being debugged involves the use of a kernel mode driver. Here we hook the system call NtCreateDebugObject(), which is used when a debugger initial attaches to a program. By intercepting this call we are able to determine when a process is attempting to debug something. I’ve included sample source for that as well.

// NtCreateDebugObject Hook
// Creative Commons - Aaron Burrow

#include "ntddk.h"

#define NTCDO_INDEX 0x37

#pragma pack(1)

typedef struct _Service_Descriptor_Entry {
	unsigned int* service_table_base;
	unsigned int* service_counter_table_base;
	unsigned int number_of_services;
	unsigned char* param_table_base;
} Service_Descriptor_Entry, *PService_Descriptor_Entry;

NTSTATUS DriverUnload(PDRIVER_OBJECT driver_object);

/* Native API */

NTSTATUS (*NtCreateDebugObject)(OUT PHANDLE, IN ACCESS_MASK,
	IN POBJECT_ATTRIBUTES, IN BOOLEAN);

NTSTATUS Hooked_Nt_CDO(OUT PHANDLE DebugObject, IN ULONG AccessRequired,
	IN POBJECT_ATTRIBUTES ObjectAttributes, IN BOOLEAN KillProcessOnExit);

extern PService_Descriptor_Entry KeServiceDescriptorTable; // SSDT
PMDL mdl; // SSDT mdl

NTSTATUS DriverEntry(PDRIVER_OBJECT driver_object, PUNICODE_STRING registry_path)
{
	unsigned int* addressable_service_table_base;

	driver_object->DriverUnload = DriverUnload;

	if (!(mdl = IoAllocateMdl(KeServiceDescriptorTable->service_table_base, KeServiceDescriptorTable->number_of_services * sizeof(unsigned int*), FALSE, TRUE, NULL)))
		return STATUS_UNSUCCESSFUL;

	MmBuildMdlForNonPagedPool(mdl);

	mdl->MdlFlags |= MDL_MAPPED_TO_SYSTEM_VA;

	// Causes a bug check on failure
	addressable_service_table_base = (PService_Descriptor_Entry)MmMapLockedPages(mdl, KernelMode);

	NtCreateDebugObject = ((PVOID*)addressable_service_table_base)[NTCDO_INDEX];
	addressable_service_table_base[NTCDO_INDEX] = (unsigned int)Hooked_Nt_CDO;
	return STATUS_SUCCESS;
}

NTSTATUS DriverUnload(PDRIVER_OBJECT driver_object)
{
	((unsigned int*)mdl->MappedSystemVa)[NTCDO_INDEX] = (unsigned int)NtCreateDebugObject;
	MmUnmapLockedPages((PVOID)mdl->MappedSystemVa, mdl);
	IoFreeMdl(mdl);
	return STATUS_SUCCESS;
}

NTSTATUS Hooked_Nt_CDO(OUT PHANDLE DebugObject, IN ULONG AccessRequired,
	IN POBJECT_ATTRIBUTES ObjectAttributes, IN BOOLEAN KillProcessOnExit)
{
	DbgPrint("Attempting to Debug!\n");
	return NtCreateDebugObject(DebugObject, AccessRequired, ObjectAttributes, KillProcessOnExit);
}

The most trivial way to defeat this method is to use an SSDT hook detection scheme.

Until later.

June 23, 2010

IDT Hooking/Unhooking Module

Filed under: Kernel Modules — Tags: , , , , — burrowscode @ 11:31 am

Been busy with work and such lately, but I took the time to put this code together. This implementation in no way represents a new concept as IDT (Interrupt Descriptor Table) hooking has been around for quite some time, but the code is clean and is a good example for those of you who are unfamiliar with the practice.

The IDT is a table that has entries referencing service routines associated with interrupts. A system can have up too 0xFF (256) such interrupts and routines, but in general most systems use less. The IDT is reponsible for handling software interrupts, hardware interrupts, and exceptions. This means that the IDT handles issues ranging from a device polling for attention to a divide by zero exception. Here are two articles to check out for more information about the IDT, Bran’s Kernel Dev on IDT and IDT Wiki.

The code is fairly straightforward, but here is a brief run down of how it works. First we attain a descriptor that will give us a virtual address referencing the IDT. We also save the current state of the IDT so that we can restore it at a later time (Note that the assembly instruction sidt simply loads a pointer to the IDT into a memory location). From here we are free to set hooks using hook_function and then remove hooks using unhook_function. Hooks are applied using a small section of assembly instructions which masks interrupts, applies the hooks, and then unmasks interrupts. There is also a function called enumerate_idt_entries that will output interrupt numbers and associated addresses for the service routines. When the driver is stopped it will also attempt to restore the IDT to the way it was when the driver first loaded.

Here is the code with some example usage.

// IDT Hooking/Unhooking Module
// Creative Commons - Aaron Burrow
#include "ntddk.h"

#pragma pack(1)

// Took these structures from Bran's Kernel Dev Tutorial
typedef struct _idt_entry
{
	USHORT base_lo;
	USHORT sel;
	UCHAR always0;
	UCHAR flags;
	USHORT base_hi;
} idt_entry, *pidt_entry;

typedef struct _idt_ptr
{
	USHORT limit;
	ULONG base;
} idt_ptr, *pidt_ptr;

VOID driver_unload(IN DRIVER_OBJECT* driver_object);
PVOID make_idt_writable(PMDL* mdl);
NTSTATUS save_original_idt(VOID);
VOID enumerate_idt_entries(VOID);
NTSTATUS hook_interrupt(PVOID writable_idt, ULONG interrupt_number, PVOID replacement_address, PVOID* old_address);
NTSTATUS unhook_interrupt(PVOID writable_idt, ULONG interrupt_number);
VOID cleanup_idt_memory(PVOID writable_idt, PMDL* mdl);

// Global Variables
// a prefix of '_' indicates a global variable that shouldn't be directly modified
pidt_entry _original_idt_vectors;
PVOID reg_call0x70;
PVOID reg_call0x71;

// Example Routines use in Hooks
__declspec(naked) hook_call0x70()
{
	__asm {
		jmp reg_call0x70;
	};
}

__declspec(naked) hook_call0x71()
{
	__asm {
		jmp reg_call0x71;
	};
}

NTSTATUS DriverEntry(IN DRIVER_OBJECT* driver_object, IN UNICODE_STRING* registry_path)
{
	PMDL mdl = NULL;
	PVOID old_address, writable_idt;
	driver_object->DriverUnload = driver_unload;
	
	if ((writable_idt = make_idt_writable(&mdl))) {
		reg_call0x70 = ((ULONG)_original_idt_vectors[0x70].base_hi << 16) | _original_idt_vectors[0x70].base_lo;
		reg_call0x71 = ((ULONG)_original_idt_vectors[0x71].base_hi << 16) | _original_idt_vectors[0x71].base_lo;
		enumerate_idt_entries();
		if (hook_interrupt(writable_idt, 0x70, (PVOID)&hook_call0x70, &old_address) == STATUS_SUCCESS) {
			if (hook_interrupt(writable_idt, 0x71, (PVOID)&hook_call0x71, &old_address) == STATUS_SUCCESS) {
				enumerate_idt_entries();
				unhook_interrupt(writable_idt, 0x70);
				unhook_interrupt(writable_idt, 0x71);
				cleanup_idt_memory(writable_idt, &mdl);
				return STATUS_SUCCESS;
			}
		}
	}
	return STATUS_UNSUCCESSFUL;
}

/*
	Get a virtual address that allows us to write to the IDT
	On success the caller is responsible for calling cleanup_idt_memory
	@mdl: The memory descriptor for the addresses referencing the IDT
	return: NULL on failure, address to IDT on success
*/
PVOID make_idt_writable(PMDL* mdl)
{
	idt_ptr p_idt;
	*mdl = NULL;
	
	if (save_original_idt() != STATUS_SUCCESS)
		return NULL;
	
	// Get a pointer to the IDT
	__asm {
		sidt p_idt 
	};
	
	if (!(*mdl = IoAllocateMdl((PVOID)p_idt.base, p_idt.limit, FALSE, FALSE, NULL)))
		return NULL;
	
	MmBuildMdlForNonPagedPool(*mdl);

	(*mdl)->MdlFlags |= MDL_MAPPED_TO_SYSTEM_VA;

	// Causes a bug check on failure
	return MmMapLockedPages(*mdl, KernelMode);
}

/*
	Cleanup all of the resources that have been allocated.
	return: None
*/
VOID cleanup_idt_memory(PVOID writable_idt, PMDL* mdl)
{
	MmUnmapLockedPages(writable_idt, *mdl);
	
	IoFreeMdl(*mdl);
	
	ExFreePoolWithTag(_original_idt_vectors, 'idt');
	return;
}

/*
	Displays information about the current IDT
	return: None
*/
VOID enumerate_idt_entries(VOID)
{
	USHORT i;
	idt_ptr p_idt;
	pidt_entry idt_vectors;
	
	// Get a pointer to the IDT
	__asm {
		sidt p_idt 
	};
	
	idt_vectors = (pidt_entry)p_idt.base;
	
	for (i = 0; i < p_idt.limit/sizeof(idt_entry); ++i) 
		DbgPrint("Interrupt #: %X Base Lo: %.4X Base High: %.4X\n", i, idt_vectors[i].base_lo, idt_vectors[i].base_hi);
	
	return;
}

/*
	Make a copy of the original IDT so that it can be restored later on
	return: STATUS_UNSUCCESSFUL on failure, STATUS_SUCCESS on success
*/
NTSTATUS save_original_idt(VOID)
{
	idt_ptr p_idt;
	
	// Get a pointer to the IDT
	__asm {
		sidt p_idt 
	};
	
	if (!(_original_idt_vectors = ExAllocatePoolWithTag(PagedPool, p_idt.limit, 'idt')))
		return STATUS_UNSUCCESSFUL;
	
	RtlCopyMemory((PVOID)_original_idt_vectors, (PVOID)(p_idt.base), p_idt.limit);
	return STATUS_SUCCESS;
	
}

/*
	Applies a hook to the specified interrupt
	A point to be made is that the function employes a caching mechanism which allows the caller
		to pass NULL for writable_idt and the function will use the last non-NULL address passed
		as that parameter.  Obviously there needs to originally be a valid address passed for the
		mechanism to work.
	@writable_idt: The virtual address to the IDT
	@interrupt_number: The number/index to the interrupt to be hooked
	@replacement_address: Address to the code to be executed instead of the interrupt service routine
	@old_address: Gives the caller the former address associated with the interrupt
	return: STATUS_SUCCESSFUL on failure, STATUS_SUCCESS on success
*/
NTSTATUS hook_interrupt(PVOID writable_idt, ULONG interrupt_number, PVOID replacement_address, PVOID* old_address)
{
	idt_ptr p_idt;
	pidt_entry idt_vectors, current_idt_entry;
	static PVOID s_writable_idt;
	
	// Get a pointer to the IDT
	__asm {
		sidt p_idt 
	};
	
	if (writable_idt) {
		// Cache the last non-Null idt virtual address in s_writable_idt
		s_writable_idt = writable_idt;
	}
	
	idt_vectors = (pidt_entry)s_writable_idt;
	
	if (!writable_idt)
		return STATUS_UNSUCCESSFUL;
	
	// Check if the interrupt number is out of range
	if (interrupt_number > p_idt.limit/sizeof(idt_entry))
		return STATUS_UNSUCCESSFUL;
	
	/*
	The following assembly code is the same thing as this 
		C code, except they force the processor to ignore 
		and then acknowledge interrupts.
	idt_vectors[interrupt_number].base_lo = replacement_address & 0xFFFF;
	idt_vectors[interrupt_number].base_hi = (replacement_address & 0xFFFF0000) >> 16;
	*/
	
	// Get the address to the idt entry we are dealing with
	current_idt_entry = &(idt_vectors[interrupt_number]);
	
	// Give the caller the old address as they'll probably need it
	*old_address = ((ULONG)current_idt_entry->base_hi << 16) | current_idt_entry->base_lo;

	__asm {
		cli							// mask interrupts
		mov eax, replacement_address 
		mov ebx, current_idt_entry
		mov [ebx], ax				// .base_lo offset = 0x0
		shr eax, 16
		mov [ebx + 0x6], ax 		// .base_hi offset = 0x6
		sti							// acknowledge interrupts
	};
	return STATUS_SUCCESS;
}

/*
	Restores an interrupt to it's original state.
	Employes the same caching mechanism as unhook_interrupt, addresses
		are shared between the functions, so a valid one must be pased
		to only one or the other
	@writable_idt: Virtual address of the IDT
	@interrupt_number: Index/Number of the IDT to be unhooked
*/
NTSTATUS unhook_interrupt(PVOID writable_idt, ULONG interrupt_number)
{
	idt_ptr p_idt;
	PVOID orig_addr, temp_addr;
	
	// Get a pointer to the IDT
	__asm {
		sidt p_idt 
	};
	
	// Check if the interrupt number is out of range
	if (interrupt_number > p_idt.limit/sizeof(idt_entry))
		return STATUS_UNSUCCESSFUL;
	
	// Make sure memory has actually been allocated for _original_idt_vectors
	if (!(_original_idt_vectors))
		return STATUS_UNSUCCESSFUL;
	
	orig_addr = ((ULONG)_original_idt_vectors[interrupt_number].base_hi << 16) | _original_idt_vectors[interrupt_number].base_lo;
	return hook_interrupt(writable_idt, interrupt_number, orig_addr, &temp_addr);
}

/*
	This function will unhook all interrupts
	@driver_object: The driver object
	return: None
*/
VOID driver_unload(DRIVER_OBJECT* driver_object)
{
	PMDL mdl = NULL;
	USHORT i;
	idt_ptr p_idt;
	PVOID writable_idt;
	
	// Get a pointer to the IDT
	__asm {
		sidt p_idt 
	};
	
	if ((writable_idt = make_idt_writable(&mdl))) {
		for (i = 0; i < p_idt.limit/sizeof(idt_entry); ++i) {
			unhook_interrupt(NULL, i);
		}
		cleanup_idt_memory(writable_idt, &mdl);
	}

	return;
}

This output represents the changes in the IDT (from unhooked, to hooked, to unhooked again) that occur on my system when running that code.

Interrupt #: 70 Base Lo: D3C0 Base High: 81C4
Interrupt #: 71 Base Lo: D3CA Base High: 81C4

Interrupt #: 70 Base Lo: 1010 Base High: AC20
Interrupt #: 71 Base Lo: 1020 Base High: AC20

Interrupt #: 70 Base Lo: D3C0 Base High: 81C4
Interrupt #: 71 Base Lo: D3CA Base High: 81C4

Until later.

June 15, 2010

User Mode Scheduler

Filed under: General Programming — Tags: , , , — burrowscode @ 12:44 am

I haven’t made a post in a while as I’ve recently been quite busy with my research and looking for a job. I did however find the time today to put something together, a user mode scheduler. For those of you who are conceptually unfamiliar with a scheduler, you may want to check out these links Wiki Scheduling and MSDN Scheduling. In general, the idea is that some program has to be responsible for deciding what thread the processor should be executing, this program is the scheduler. In the case of both Linux and Windows the scheduler is implemented in kernel mode for a number of reasons. It is however possible to implement an emulated scheduler in user mode, which is what I have done. Here you can read about Microsoft’s implementation of a user mode scheduler Microsoft User Mode Scheduler.

You may also notice some subtle changes to my coding style in this project. I chose to go with Microsoft typedefs, used goto to do a number of cleanup routines, attempted to standardize comments before functions, and in general stayed away from nested conditionals. Lately I’ve been trying some new things in my coding style in an attempt to make some slight improvements in the presentation of my code.

And now I’ll walk through some of the code. First off you’ll see init_scheduler which is responsible for first setting up a descriptor for the emulated system and finally returning a Handle to this descriptor. Primarily the function initializes memory and makes sure that the user has requested the establishment of at least one processor (a system with 0 processors won’t get too much work done).

Next there is add_thread and delete_thread which are the mechanisms for which you can adjust what code will be executed by the processor. The bulk of the add_thread function is really just determining where there is open space for a handle to the new thread. You can also see that we set the initial state of the thread to Suspended so that it won’t just begin executing without our consent. add_thread returns the id for the newly created thread and this id can be passed to delete_thread if you wish to remove the thread from the system.

After this we get the start_processing and stop_processing functions which are responsible for actually dictating the processor. In most cases, the threads will however just run to completion and end start_processing thus making stop_processing almost useless. The algorithm currently used in start_processing was just something that I through together as an example. It is in no way a production level scheduling algorithm.

Finally we have cleanup_scheduler which just takes care of all the memory and objects that we’ve taken ownership of at some point.

As usual I’ve included example usage in the code.


// Usermode Scheduler
// Creative Commons - Aaron Burrow

/*
	Notes
	1) The scheduling algorithm itself is very crude and unsophisticated
	2) These functions should all be thread safe (but calling them in certain combinations will
		cause a lock up)
	3) Attempting to directly change members in the descriptor can lead to bad behavior, especially
		after calling start_processing
*/

#include <windows.h>
#include <stdio.h>

#define MAX_THREAD_PRIORITY 10

enum Thread_State {
	SUSPENDED_THREAD,
	EXECUTING_THREAD,
	DEAD_THREAD
};

typedef struct Scheduler_Descriptor* Scheduler_Handle;
typedef UINT Thread_ID;

struct Thread_Descriptor {
	HANDLE thread;							// Thread handle
	UINT priority;							// Thread priority, the lower the number the higher the priority up to MAX_THREAD_PRIORITY
	enum Thread_State state;				// Thread state, 0 = Suspended, 1 = Executing, 2 = Dead
	Thread_ID tid;							// Unique thread id
};

struct sched_desc {
	BOOL processing;
	INT number_threads;
	INT number_processors;
	HANDLE* processor_threads;
	struct Thread_Descriptor* thread_desc;
	Thread_ID tid_counter;
};

struct Scheduler_Descriptor {
	HANDLE desc_mutex;
	struct sched_desc s_desc;
};

Scheduler_Handle init_scheduler(INT processors);
Thread_ID add_thread(Scheduler_Handle sched_handle, VOID WINAPI (*code)(LPVOID), LPVOID param, UINT priority);
BOOL start_processing(Scheduler_Handle sched_handle);
VOID stop_processing(Scheduler_Handle sched_handle);
BOOL delete_thread(Scheduler_Handle sched_handle, Thread_ID tid);
VOID cleanup_scheduler(Scheduler_Handle sched_handle);

VOID WINAPI trial_function1(LPVOID param);
VOID WINAPI trial_function2(LPVOID param);
VOID WINAPI trial_function3(LPVOID param);
VOID WINAPI trial_function4(LPVOID param);

INT main(INT argc, TCHAR** argv)
{
	// Initialize The System
	Scheduler_Handle sched_handle = init_scheduler(2);
	if (!(sched_handle))
		return 1;
		
	// Setup Threads
	INT five = 5;
	add_thread(sched_handle, trial_function1, NULL, 0);
	Thread_ID id = add_thread(sched_handle, trial_function2, NULL, 3);
	delete_thread(sched_handle, id);
	delete_thread(sched_handle, 8);
	add_thread(sched_handle, trial_function3, NULL, 1);
	add_thread(sched_handle, trial_function4, &five, 2);
	
	// Process Threads
	start_processing(sched_handle);

	// Cleanup and Exit
	cleanup_scheduler(sched_handle);
	return 0;
}

/*
	@processors: the number of concurrent processors to emulate
	return: NULL on failure, a valid handle on success
*/
Scheduler_Handle init_scheduler(INT processors)
{
	
	Scheduler_Handle h = calloc(1, sizeof(struct Scheduler_Descriptor));
	if (!h)
		goto cleanup_exit;
		
	if (processors < 1)
		goto cleanup_exit;
		
	h->s_desc.number_processors = processors;
	if (!(h->s_desc.processor_threads = calloc(processors, sizeof(HANDLE)))) 
		goto cleanup_exit;
	
	if (!(h->desc_mutex = CreateMutex(NULL, FALSE, NULL)))
		goto cleanup_exit;
	
	return h;
	
cleanup_exit:
	if (h->s_desc.processor_threads)
		free (h->s_desc.processor_threads);
	if (h)
		free (h);
	return NULL;
}

/*
	@sched_handle: the descriptor we are associating
	@code: a function pointer to the code to execute for the thread
	@param: a parameter to pass to the thread
	@priority: the importance/urgency of the thread
	return: 0 on failure, a valid thread id on success
*/
Thread_ID add_thread(Scheduler_Handle sched_handle, VOID WINAPI (*code)(LPVOID), LPVOID param, UINT priority)
{
	WaitForSingleObject(sched_handle->desc_mutex, INFINITE);
	
	// Create the thread in a suspended state so we can determine when it starts
	HANDLE h = CreateThread(0, 0, (LPTHREAD_START_ROUTINE)code, param, CREATE_SUSPENDED, NULL);
	if (!h)
		goto cleanup_exit;
	
	// Get the identifier for this thread
	UINT tid = ++sched_handle->s_desc.tid_counter;
	
	// Now we need to get thread descriptor for this thread
	// First let's find out if there are any dead threads
	INT thread_index;
	for (thread_index = 0; thread_index < sched_handle->s_desc.number_threads; thread_index++)
		if (sched_handle->s_desc.thread_desc[thread_index].state == DEAD_THREAD) break;
	if (thread_index == sched_handle->s_desc.number_threads) {
		// This means that we need to allocate a new thread descriptor
		UINT temp = sched_handle->s_desc.number_threads++;
		LPVOID temp_addr = realloc(sched_handle->s_desc.thread_desc, sched_handle->s_desc.number_threads*sizeof(struct Thread_Descriptor));
		if (!temp_addr) {
			sched_handle->s_desc.number_threads = temp;
			goto cleanup_exit;
		}
		sched_handle->s_desc.thread_desc = temp_addr;
		thread_index = temp;
	}
	// Now that we have a thread descriptor, it needs to be filled out
	sched_handle->s_desc.thread_desc[thread_index].thread = h;
	sched_handle->s_desc.thread_desc[thread_index].priority = priority;
	sched_handle->s_desc.thread_desc[thread_index].state = SUSPENDED_THREAD;
	sched_handle->s_desc.thread_desc[thread_index].tid = tid;
	
	// The last thing to do is create the mutex that allows access too sched_handle->s_desc
	ReleaseMutex(sched_handle->desc_mutex);
	return tid;

cleanup_exit:
	if (h)
		TerminateThread(h, 1);
		CloseHandle(h);
	ReleaseMutex(sched_handle->desc_mutex);
	return 0;
}

/*
	This implementation is simply meant to be an example of how to implement the scheduler algorithm
		and shouldn't _ever_ be used in production code
	@sched_handle: a handle to the descriptor we are using
	return: TRUE on success, FALSE on failure
*/

BOOL start_processing(Scheduler_Handle sched_handle)
{
	UINT active_processors, thread_index = 0;
	sched_handle->s_desc.processing = TRUE;
	BOOL any_active;
	DWORD status, sleep_time;
	UINT processor_index;
	UINT* active_threads;
	
	if (!(active_threads = calloc(sched_handle->s_desc.number_processors, sizeof(UINT)))) 
		return FALSE;
	
	while (sched_handle->s_desc.processing == TRUE) {
		any_active = FALSE;
		sleep_time = 0;
		processor_index = 0;
		active_processors = 0;
		
		WaitForSingleObject(sched_handle->desc_mutex, INFINITE);
		
		// First we need to actually get some threads executing
		for (; thread_index < sched_handle->s_desc.number_threads; thread_index++) {
			if ((active_processors < sched_handle->s_desc.number_processors) && (sched_handle->s_desc.thread_desc[thread_index].state != DEAD_THREAD)) {
				
				active_threads[active_processors] = thread_index;
				sched_handle->s_desc.processor_threads[active_processors++] = sched_handle->s_desc.thread_desc[thread_index].thread;
				ResumeThread(sched_handle->s_desc.thread_desc[thread_index].thread);
				sched_handle->s_desc.processor_threads[processor_index++] = sched_handle->s_desc.thread_desc[thread_index].thread;
				sched_handle->s_desc.thread_desc[thread_index].state = EXECUTING_THREAD;
				sleep_time += ((MAX_THREAD_PRIORITY + 1) - sched_handle->s_desc.thread_desc[thread_index].priority) * 25;
			}
			else if (active_processors >= sched_handle->s_desc.number_processors)
				break;
		}
		
		// Now give them some amount of time to execute based on their priority
		Sleep(sleep_time);
		
		// Determine the state of these threads we executed
		for (UINT i = 0; i < active_processors; i++) {
			GetExitCodeThread(sched_handle->s_desc.thread_desc[active_threads[i]].thread, &status);
			if (status != STILL_ACTIVE)
				delete_thread(sched_handle, sched_handle->s_desc.thread_desc[active_threads[i]].tid);
			else {
				// This isn't actually true yet, but it seems to be the only way
				sched_handle->s_desc.thread_desc[i].state = SUSPENDED_THREAD;
			}
		}
		
		ReleaseMutex(sched_handle->desc_mutex);
		
		// Now see if there are any active threads
		for (UINT i = 0; i < sched_handle->s_desc.number_threads; i++) {
			if (sched_handle->s_desc.thread_desc[i].state != DEAD_THREAD)
				any_active = TRUE;
		}
		
		// Break out of the loop if no active threads, else just suspend the ones we started
		if (any_active == TRUE) {
			for (UINT i = 0; i < processor_index; i++) 
				SuspendThread(sched_handle->s_desc.processor_threads[i]);
			if (thread_index == sched_handle->s_desc.number_threads)
				thread_index = 0;
		}
		else 
			break;
		
	}
	free (active_threads);
	return TRUE;
}

/*
	@sched_handle: a handle to the descriptor
	return: No return value
*/

VOID stop_processing(Scheduler_Handle sched_handle)
{
	WaitForSingleObject(sched_handle->desc_mutex, INFINITE);
	
	sched_handle->s_desc.processing = FALSE;
	
	ReleaseMutex(sched_handle->desc_mutex);
	return;
}

/*
	@sched_handle: handle to the descriptor
	@tid: the thread id for the thread slated to be deleted
	return: FALSE on error, TRUE on success
*/

BOOL delete_thread(Scheduler_Handle sched_handle, Thread_ID tid)
{
	WaitForSingleObject(sched_handle->desc_mutex, INFINITE);

	INT thread_index;
	for (thread_index = 0; thread_index < sched_handle->s_desc.number_threads; thread_index++)
		if (sched_handle->s_desc.thread_desc[thread_index].tid == tid) break;
		
	if (thread_index == sched_handle->s_desc.number_threads) {
		ReleaseMutex(sched_handle->desc_mutex);
		return FALSE;
	}
	
	TerminateThread(sched_handle->s_desc.thread_desc[thread_index].thread, 1);
	CloseHandle(sched_handle->s_desc.thread_desc[thread_index].thread);
	sched_handle->s_desc.thread_desc[thread_index].state = DEAD_THREAD;
	ReleaseMutex(sched_handle->desc_mutex);
	return TRUE;
}

/*
	@sched_handle: the handle to the descriptor we are destroying
	return: No return value
*/

VOID cleanup_scheduler(Scheduler_Handle sched_handle)
{
	WaitForSingleObject(sched_handle->desc_mutex, INFINITE);
	
	if (sched_handle) {
		if (sched_handle->s_desc.processor_threads)
			free (sched_handle->s_desc.processor_threads);
			
		if (sched_handle->s_desc.thread_desc)
			free ((sched_handle->s_desc.thread_desc));
			
		if (sched_handle->desc_mutex)
			CloseHandle(sched_handle->desc_mutex);
			
		for (UINT i = 0; i < sched_handle->s_desc.number_threads; i++) {
			if (sched_handle->s_desc.thread_desc[i].state != DEAD_THREAD) {
				// We don't want to call delete_thread here because we've taken control of the mutex
				TerminateThread(sched_handle->s_desc.thread_desc[i].thread, 1);
				CloseHandle(sched_handle->s_desc.thread_desc[i].thread);
			}
		}
		free (sched_handle);
	}
	return;
}

VOID WINAPI trial_function1(LPVOID param)
{
	printf("AAAAA\n");
	return;
}

VOID WINAPI trial_function2(LPVOID param)
{
	printf("BBBBB\n");
	return;
}

VOID WINAPI trial_function3(LPVOID param)
{
	printf("CCCCC\n");
	return;
}

VOID WINAPI trial_function4(LPVOID param)
{
	printf("D: %d\n", *(INT*)param);
	return;
}

And the output…

C:\Users\burrows\code>umode_scheduler.exe
AAAAA
CCCCC
D: 5

Until later.

May 11, 2010

Windows Clipboard Implemented as FIFO Queue

Filed under: General Programming — Tags: , , , — burrowscode @ 8:12 pm

A friend and I were recently discussing alternative ways in which the Windows Clipboard could operate and after a while we decided that a FIFO Queue would be a useful addition to normal clipboard operations. For those of you wondering what a FIFO Queue is, think of it as a data type with two general methods, push and get. These push method will add another element, and the get method returns elements in the same order that they were pushed (Queue Wiki).

This functionality comes in use when you want to copy a series of different things and then paste them. It’s more efficient to copy everything at once and then paste everything at the end, then to constantly switch between copying and pasting. My software does allow you to use traditional copy and paste as my queue versions are ‘hotkeyed’ to ALT+C and ALT+V.

Implementing the software was actually a bit more tricky than I expected. Initially I was having issues with forcing the system to invoke a copy/paste and I attempted a variety of solutions. Some attempts include the use of keybd_event() to force a CONTORL+C/CONTROL+V key combination and the use of SendMessage() with WM_COPY and WM_PASTE (which is a more proper implementation) to cause a copy/paste.

There was also the issue of allowing for proper memory protection of data supplied to the SetClipboardData function. This occurred because the function expects to take ownership of the memory (Handle) that it gets, therefore we are forced to use a series of calls to GlobalAlloc, GlobalLock, and GlobalUnlock.

Due to these problems and other issues I contacted a friend named Napalm (Netcore2k.net) for some help with the code. Initially he just remarked on what needed to be changed, but after errors continued to surface he stepped in and coded a very substantial (and by substantial I mean almost all of) part of the copypaste() function. With his help I was able to get the software working and the only obvious improvement is to implement a clipboard viewer so that we can know exactly when the clipboard is updated. I’m not going to do this right now.

And here’s the code (note the heavy use of Hungarian notation by Napalm…).

// Queue Based Clipboard
// Creative Commons - Aaron Burrow and Napalm

#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

#define Q_COPY		100
#define Q_PASTE		101

typedef struct tagGUITHREADINFO {
	DWORD cbSize;
	DWORD flags;
	HWND hwndActive;
	HWND hwndFocus;
	HWND hwndCapture;
	HWND hwndMenuOwner;
	HWND hwndMoveSize;
	HWND hwndCaret;
	RECT rcCaret;
} GUITHREADINFO, *LPGUITHREADINFO;

struct queue_model {
	long size;
	long current_elements;
	long add_more;
	char** contents;
};

void copypaste(struct queue_model* queue, int copyorpaste);

struct queue_model* queue_init(long q_size);
bool queue_put(struct queue_model* queue, char* item);
bool queue_get(struct queue_model* queue, char* item);
bool queue_get_item_length(struct queue_model* queue, size_t* length);
void queue_cleanup(struct queue_model* queue);

BOOL (WINAPI *GetGUIThreadInfo)(DWORD idThread, LPGUITHREADINFO lpgui);

int main(int argc, char** argv)
{
	struct queue_model* queue;
	MSG msg;
	
	// Using old headers
	*(FARPROC *)&GetGUIThreadInfo = GetProcAddress(GetModuleHandle("user32.dll"), "GetGUIThreadInfo");
	if (!GetGUIThreadInfo) {
		printf("Upgrade your Windows!\n");
		return 1;
	}
	if (queue = queue_init(50)) {
		if (RegisterHotKey(NULL, Q_COPY, MOD_ALT, 'C')) {
			if (RegisterHotKey(NULL, Q_PASTE, MOD_ALT, 'V')) {
				while (GetMessage(&msg, NULL, 0, 0)) {
					if (msg.message == WM_HOTKEY) {
						if (msg.wParam == Q_COPY) 
							copypaste(queue, 1);
						else if (msg.wParam == Q_PASTE)
							copypaste(queue, 0);
					}
				}
			}
		}
		queue_cleanup(queue);
	}
	return 0;
}

void copypaste(struct queue_model* queue, int copyorpaste) // Napalm (Netcore2k.net) fixed a bunch of problems and coded even more
{
	HGLOBAL hGlobal;
	LPSTR lpData, lpSaved = NULL;
	BOOL bSuccess;
	UINT uLength, uSize;
	
	// Save Clipboard
	bSuccess = FALSE;
	if(OpenClipboard(NULL)){
		hGlobal = GetClipboardData(CF_TEXT);
		if(hGlobal){
			if((lpData = (LPSTR)GlobalLock(hGlobal)) != NULL){
				uLength = strlen(lpData) + 1;
				lpSaved = (LPSTR)HeapAlloc(GetProcessHeap(), 0, uLength);
				if(lpSaved){
					strcpy(lpSaved, lpData);
					bSuccess = TRUE;
				}
				GlobalUnlock(hGlobal);
			}
		}
		CloseClipboard();
	}else{
		printf("Error: OpenClipboard() failed!\n");
	}
	if(!bSuccess){
		printf("Error: %d, failed to get clipboard data!\n", GetLastError());
		return;
	}
	
	// Do actual work
	if(bSuccess){
		GUITHREADINFO guiThread;
		DWORD dwResult;
		UINT uMsgCopyPaste = (copyorpaste) ? WM_COPY : WM_PASTE;
		
		if(!copyorpaste){
			// Update clipboard with new paste data
			bSuccess = FALSE;
			if(OpenClipboard(NULL)){
				if(queue_get_item_length(queue, &uSize)){
					hGlobal = GlobalAlloc(GMEM_MOVEABLE, uSize + 1);
					if((lpData = GlobalLock(hGlobal)) != NULL){
						GlobalUnlock(hGlobal);
						EmptyClipboard();
						queue_get(queue, lpData);
						if(SetClipboardData(CF_TEXT, lpData))
							bSuccess = TRUE;
					}
				}
				CloseClipboard();
			}else{
				printf("Error: OpenClipboard() failed!\n");
			}
			if(!bSuccess){
				printf("Warning: Could not update clipboard with new data\n");
				GlobalFree(hGlobal);
				return;
			}
		}
		
		guiThread.cbSize = sizeof(guiThread);
		if(GetGUIThreadInfo(0, &guiThread)){
			SendMessageTimeout(guiThread.hwndFocus, uMsgCopyPaste, 0, 0, SMTO_BLOCK, 100, &dwResult);
		}else{
			printf("Warning: GetGUIThreadInfo() failed!\n");
			SendMessageTimeout(GetFocus(), uMsgCopyPaste, 0, 0, SMTO_BLOCK, 100, &dwResult);
		}
		
		// TODO: IMPORTANT! - use clipboard viewer api to see when the update actually occurs
		Sleep(100);
		
		if(copyorpaste){
			// Copy new data from Clipboard
			bSuccess = FALSE;
			if(OpenClipboard(NULL)){
				hGlobal = GetClipboardData(CF_TEXT);
				if(hGlobal){
					if((lpData = (LPSTR)GlobalLock(hGlobal)) != NULL){
						queue_put(queue, lpData);
						GlobalUnlock(hGlobal);
						bSuccess = TRUE;
					}
				}else{
					printf("Warning: %d, nothing to copy from clipboard!\n", GetLastError());
				}
			}else{
				printf("Error: OpenClipboard() failed!\n");
			}
			if(!bSuccess){
				// detect if saved data == new data
				printf("Warning: No new data on clipboard\n");
			}
		}
	}
	
	// Restore Clipboard
	bSuccess = FALSE;
	if(OpenClipboard(NULL)){
		hGlobal = GlobalAlloc(GMEM_MOVEABLE, uLength);
		if((lpData = GlobalLock(hGlobal)) != NULL){
			memcpy(lpData, lpSaved, uLength);
			GlobalUnlock(hGlobal);
			if(SetClipboardData(CF_TEXT, hGlobal))
				bSuccess = TRUE;
		}else{
			printf("Error: Failed to lock\n");
		}
		CloseClipboard();
	}else{
		printf("Error: OpenClipboard() failed!\n");
	}
	if(!bSuccess){
		printf("Error: %d, failed to restore clipboard data!\n", GetLastError());
	}
	
	if(lpSaved)
		HeapFree(GetProcessHeap(), 0, lpSaved);
	
	return;
}

// A return value of NULL indicates an error
struct queue_model* queue_init(long q_size)
{
	struct queue_model* queue = NULL;
	if (queue = malloc(sizeof(struct queue_model))) {
		if (queue->contents = malloc(sizeof(q_size))) {
			queue->size = q_size;
			queue->current_elements = 0;
		}
	}
	return queue;
}

bool queue_put(struct queue_model* queue, char* item)
{
	if (queue->current_elements < queue->size) {
		if (queue->contents[queue->current_elements] = malloc(strlen(item) + 1)) {
			strcpy(queue->contents[queue->current_elements++], item);
			return true;
		}
	}
	return false;
}

bool queue_get(struct queue_model* queue, char* item)
{
	if (queue->current_elements > 0) {
		strcpy(item, queue->contents[0]);
		memmove((void*)queue->contents, (void*)&(queue->contents[1]), --queue->current_elements * sizeof(char*));
		return true;
	}
	return false;
}

bool queue_get_item_length(struct queue_model* queue, size_t* length)
{
	if (queue->current_elements > 0) {
		*length = strlen(queue->contents[0]);
		return true;
	}
	return false;
}

void queue_cleanup(struct queue_model* queue)
{
	for (int i = 0; i < queue->current_elements; i++)
		free (queue->contents[i]);
	free (queue);
	return;
}

Here is some example output.

ALT+C [hello]
ALT+C [google]
ALT+C [bye]
ALT+V [hello]
ALT+V [google]
ALT+V [bye]

Until later.

May 4, 2010

Display 24-Bit Bitmaps in the Windows Console

Filed under: General Programming — Tags: , , , , , — burrowscode @ 3:01 am

I’ve been working on some code over the past couple hours that will take a bitmap and display it in the Windows console. The code does still have one distinct fault, which I’ll remark on later in the post. My inspiration for this project was primarily Youtube’s April Fool’s Day Joke. While their algorithm is substantially more impressive than what I’ve done (their algorithm works on videos and accounts for color much better than mine), my code is a decent example of how you may go about consuming a file type in an unconventional fashion.

The bitmap file format is in general quite simple. There is a small header that describes details such as image resolution, image dimensions, and the color palette. Our code is designed to work exclusively with 24-Bit Bitmaps, this means that each pixel in the bitmap is represents by 24 bits, which in general is going to be 3 bytes (there are obviously systems that don’t have 8 bit bytes, but we will not be considering these cases). Following this header we get our actual bitmap data. For more information on the bitmap file format you should check out BMP Wiki. Something else you may be interested in is some information on the RGB Color Scheme, so RGB Wiki.

Most of the code is straightforward but I will go through and explain some of it. Initially we parse the bitmap file and setup a descriptor which allows us to more easily access important elements of the bitmap file format. After this we go through and remove the zero padding that the format allows for alignment reasons. Finally we go and actually begin creating the console representation of the bitmap. In order to do this we create a buffer that correlates color to location. Our color converting algorithm is simple, and I didn’t spend much time determining what the optimal DELTA value is (the DELTA value is used to determine if colors have similar intensities) for the application.

Now we take this buffer and pass it to our output function. This is where we have to deal with the fault that I mentioned earlier. Basically it comes out to our images being displayed flipped upside down. This occurs because bitmap data is stored from bottom to top (but still going across rows from left to right) as opposed to top to bottom. All it would really take to fix this is a small adjustment to the output function to print the information in the appropriate order. I however don’t have the time to do this right now, and don’t feel a huge desire to do it either.

The only other known issues are it takes a while to convert big bitmaps and printing colors that are very mixed (in terms of RGB) will result in nonsensical images due to the scaling of pixels to characters.

At any rate here is the code and some example translations (the code has MinGW/GCC and Windows specific segments).

//24 Bit-Bitmap to Console
// Creative Commons - Aaron Burrow

// This software is reliant on both the Win32 and the MinGW Compiler.
// It uses Windows specific functions/structures in order to use colors in the Windows console
// The software also uses the MinGW attribute packed which is only available on gcc like compilers
// On MSVC you would need to use pragma packed
// This code also relies on the the ASCII character set being used
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include <math.h>
#include <windows.h>

#define BMP_BITS 24
#define CONSOLE_WIDTH 80
#define CONSOLE_HEIGHT 25
#define NEWLINE 50
#define DELTA 20				// Adjusting this number can have a big effect on how colors are displayed
#define END_DATA 100

// Console Colors
enum Console_Colors {
	BLACK = 0,
	BLUE,
	GREEN,
	AQUA,
	RED,
	PURPLE,
	YELLOW,
	WHITE,
	GRAY,
	L_BLUE,
	L_GREEN,
	L_AQUA,
	L_RED,
	L_PURPLE,
	L_YELLOW,
	B_WHITE
};

// Header definitions taken mostly from Wikipedia, with some small changes
struct bmpfile_header {
	uint16_t magic;
	uint32_t filesz;
	uint16_t creator1;
	uint16_t creator2;
	uint32_t bmp_offset;
} __attribute__ ((packed));

struct bmp_dib_v3_header {
	uint32_t header_sz;
	uint32_t width;
	uint32_t height;
	uint16_t nplanes;
	uint16_t bitspp;
	uint32_t compress_type;
	uint32_t bmp_bytesz;
	uint32_t hres;
	uint32_t vres;
	uint32_t ncolors;
	uint32_t nimpcolors;
} __attribute__ ((packed));

struct bmp_descriptor {
	struct bmpfile_header file_hdr;
	struct bmp_dib_v3_header dib_hdr;
	unsigned char* bmp_data;
};

long read_file(char* path, char** buffer);
long setup_descriptor(char* raw_data, struct bmp_descriptor* desc);
bool create_console_version(struct bmp_descriptor desc, unsigned char* console);
bool validate_bmp(struct bmp_descriptor desc);
int convert_color(unsigned char* bmp);
void print_bmap(unsigned char* buffer);
bool close(int x, int y);
int imax(int x, int y);
int remove_padding(unsigned char* data, int len);

int main(int argc, char** argv)
{
	long file_size;
	char* buffer;
	unsigned char console_buff[25*26 + 1];
	struct bmp_descriptor desc;
	if (argc == 2) {
		if (file_size = read_file(argv[1], &buffer)) {
			if (setup_descriptor(buffer, &desc)) {
				desc.dib_hdr.bmp_bytesz = remove_padding(desc.bmp_data, desc.dib_hdr.bmp_bytesz);
				if (create_console_version(desc, console_buff)) 
					print_bmap(console_buff);
				free (desc.bmp_data);
			}
			free (buffer);
		}
	}
	else 
		printf("Proper usage: %s path.bmp\n", argv[0]);
	return 0;
}

// Using this function requires you to free the file buffer after you are done using it
long read_file(char* path, char** buffer)
{
	FILE * file;
	long size;
	if (file = fopen(path, "rb")) {
		if (!fseek(file, 0, SEEK_END)) {
			if ((size = ftell(file)) != -1L) {
				rewind(file);
				if (*buffer = calloc(size, sizeof(char) + 1)) {
					if (fread(*buffer, sizeof(char), size + 1, file)) {
						fclose(file);
						return size;
					}
					free (*buffer);
				}
			}
		}
		fclose(file);
	}
	return 0;
}

// On a successful use of this function then the caller is responsible for freeing desc->bmp_data
long setup_descriptor(char* raw_data, struct bmp_descriptor* desc)
{
	memcpy(&(desc->file_hdr), raw_data, sizeof(struct bmpfile_header));
	memcpy(&(desc->dib_hdr), (raw_data + sizeof(struct bmpfile_header)), sizeof(struct bmp_dib_v3_header));
	if (desc->bmp_data = malloc(desc->dib_hdr.bmp_bytesz)) {
		memcpy(desc->bmp_data, raw_data + desc->file_hdr.bmp_offset, desc->dib_hdr.bmp_bytesz);
		return desc->dib_hdr.bmp_bytesz;
	}
	return 0;
}

// console must have at least 25*26 writable bytes, and END_DATA needs to be accounted for
// so at least 25*25 + 1 bytes
bool create_console_version(struct bmp_descriptor desc, unsigned char* console)
{
	if (validate_bmp(desc)) {
		int active_width, active_height;
		if (desc.dib_hdr.width > desc.dib_hdr.height) {
			active_width = CONSOLE_HEIGHT;
			active_height = (int)(((float)desc.dib_hdr.height / (float)desc.dib_hdr.width) * CONSOLE_HEIGHT);
		}
		else {
			active_height = CONSOLE_HEIGHT;
			active_width = (int)(((float)desc.dib_hdr.width / (float)desc.dib_hdr.height) * CONSOLE_HEIGHT);
		}
		
		int print_pix = ceilf((float)desc.dib_hdr.width / (float)active_width), main_index = 0;
		for (int i = 0; i < desc.dib_hdr.height; i += print_pix) {
			for (int j = 0; j < desc.dib_hdr.width; j += print_pix) {
				unsigned char* loc = &(desc.bmp_data[i*(desc.dib_hdr.width)*3 + j*3]);
				console[main_index++] = convert_color(loc);
			}
			console[main_index++] = NEWLINE;
		}
		console[main_index] = END_DATA;
		return true;
	}
	return false;
}

bool validate_bmp(struct bmp_descriptor desc)
{
	return desc.dib_hdr.bitspp == BMP_BITS && desc.dib_hdr.compress_type == BI_RGB && desc.dib_hdr.ncolors == 0 && desc.dib_hdr.nimpcolors == 0;
}


// Only the first 24 bits are relevant
// Byte 1 = Blue, Byte 2 = Green, Byte 3 = Red
int convert_color(unsigned char* bmp)
{
	unsigned char blue = bmp[0], green = bmp[1], red = bmp[2];

	if (close(blue, 0) && close(green, 0) && close(red, 0))
		return BLACK;
	else if (close(blue, green) && close(blue, red))
		return WHITE;
	else if (close(blue, red)) {
		if (blue > green) 
			return PURPLE;
		else
			return GREEN;
	}
	else if (close(green, red)) {
		if (green > blue)
			return YELLOW;
		else
			return BLUE;
	}
	else if (close(blue, green)) {
		if (blue > red) 
			return AQUA;
		else
			return RED;
	}
	else {
		int m = imax(imax(blue, green), red);
		if (m == blue) return BLUE;
		else if (m == green) return GREEN;
		else return RED;
	}
		
}

bool close(int x, int y)
{
	return (x > y && (x - DELTA) <= y) || (y > x && (y - DELTA) <= x) || x == y; 
}

int imax(int x, int y)
{
	if (x > y) return x;
	else return y;
}

void print_bmap(unsigned char* buffer)
{
	HANDLE s_out;
	if ((s_out = GetStdHandle(STD_OUTPUT_HANDLE)) != INVALID_HANDLE_VALUE) {
		for (int i = 0; buffer[i] != END_DATA; i++) {
			if (buffer[i] == NEWLINE)
				putchar('\n');
			else {
				SetConsoleTextAttribute(s_out, buffer[i]);
				putchar(254);
			}
		}
	}
	SetConsoleTextAttribute(s_out, WHITE);
	fflush(stdout);
	return;
}

int remove_padding(unsigned char* data, int len)
{
	for (int i = 0; i < len; i++)
		if (data[i] == 0)
			memmove(&(data[i]), &(data[i+1]), --len - i--);
	return len;
}


Until later.

April 4, 2010

Reducing Boolean Expressions to NOR Expressions

Filed under: General Programming — Tags: , , — burrowscode @ 9:26 pm

I was bored yesterday and decided that I’d like to write some software that would take boolean expressions and then reduce them to only using the NOR operator. We are able to do this because NOR is a so-called universal operator, this means that any boolean expression can be represented using only NOR operators. This same logic follows when dealing with logic gates found in digital circuits. NAND is another example of a universal operator.

The software works like such. First it takes a boolean expression and breaks it up into a series of tokens, these tokens are then pushed onto the stack. After all tokens are on the stack, we reverse the stack so that we can pop the tokens off in the order that they appear in the expression (this was simply done so that I could think about things from left to right while coding). Once our stack is set, we move onto translation and here we have a recursive procedure that is primarily looking for three data items: the two operands to a boolean expression and the operator. It then does the translation from these expressions to their NOR equivalents (see the wikipedia page for conversions and other relevant information Logical NOR). Now we just output the new expression. Keep in mind that this current implementation requires parentheses around any compound expressions, otherwise you will get undefined results.

While coding this I didn’t have much of a focus on expandability so there are a few locations that _could_ be changed for the better. First off, both of the switch statements should probably be converted to for loops. This would mean that the structure stack_id would also need a new variable. This would be a function pointer that would handle output for the respective operator (true and false would just have a function that does nothing). The arguments to this function would be the two operands.

Another thing to consider is adding support for operators that only have one operand. In order to do this it seems you would only need to add another if statement to the translate_expression(char* translate) function. Personally I just don’t feel like taking the time to implement it. Also be aware that I didn’t take the time to implement a procedure to make sure that input was a valid boolean expression. A bad expression will more than likely crash the software.

Anyways, this code gives you a decent look at how one could go about implementing a ‘Boolean Reducer’.

//Creative Commons - Aaron Burrow

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>
#include <string.h>

#define STACK_MEMBERS 			500
#define NUMB_IDS 				6
#define MAX_EXPRESSION 			1000

/*
	true 		= t
	false 		= f
	and 		= a
	or 			= o
	nor			= n
	implies 	= i
*/

struct stack_model {
	long size;
	long current;
	char* contents;
} stack;

struct stack_id {
	char* full;
	char id;
};

bool create_stack(void);
bool stack_push(char val);
char stack_pop(void);
bool reverse_stack(void);
void cleanup_stack(void);

void parse_expression(char* exp);
bool get_id(char* t, char* c);
bool translate_expression(char* translation);
char* convert_id_to_full(char id);

struct stack_id stack_ids[] = {
	{"true", 't'},
	{"false", 'f'},
	{"and", 'a'},
	{"or", 'o'},
	{"implies", 'i'},
	{"nor", 'n'}
};

int main(int argc, char** argv)
{
	char* trial = "(((true AND false) OR (false AND true)) IMPLIES true)";
	char translation[MAX_EXPRESSION];
	if (create_stack()) {
		parse_expression(trial);
		if (reverse_stack()) {
			if (translate_expression(translation)) {
				printf("%s\n", translation);
			}
		}
		cleanup_stack();
	}
	return 0;
}

bool create_stack(void)
{
	if (stack.contents = (char*)calloc(STACK_MEMBERS, sizeof(char))) {
		stack.size = STACK_MEMBERS;
		stack.current = STACK_MEMBERS;
		return true;
	} 
	return false;
}

bool stack_push(char val)
{
	if (stack.current >= 1) {
		stack.current--;
		stack.contents[stack.current] = val;
		return true;
	}
	return false;
}

char stack_pop(void)
{
	if (stack.current < stack.size) {
		stack.current++;
		return stack.contents[stack.current - 1];
	}
	return 0;
}

bool reverse_stack(void)
{
	int numb = STACK_MEMBERS - stack.current;
	char* off;
	if (off = malloc(numb * sizeof(char))) {
		for (int i = 0; i < numb; i++) {
			off[i] = stack_pop();
		}
		for (int i = 0; i < numb; i++) {
			stack_push(off[i]);
		}
		free (off);
		return true;
	}
	return false;
}

void cleanup_stack(void)
{
	free (stack.contents);
	return;
}

void parse_expression(char* exp)
{
	static char temp[20] = {0};
	static int index = 0;
	char id;
	do {
		if (*exp == '(' || *exp == ')' || *exp == ' ' || !*exp) {
			temp[index] = 0;
			if (get_id(temp, &id)) 
				stack_push(id);
			index = 0;
			if (*exp == '(' || *exp == ')')
				stack_push(*exp);
		}
		else {
			temp[index++] = *exp;
		}
	} while (*exp++);
	return;
}

bool get_id(char* t, char * c)
{
	for (int i = 0; t[i]; i++) 
			t[i] = tolower(t[i]);
	for (int i = 0; i < NUMB_IDS; i++) {
		if (!strcmp(stack_ids[i].full, t)) {
			*c = stack_ids[i].id;
			return true;
		}
	}
	return false;
}

bool translate_expression(char* translation)
{
	char f_op[MAX_EXPRESSION] = {0}, s_op[MAX_EXPRESSION] = {0}, operator = 0;
	static int x = 0;
	while (stack.current != STACK_MEMBERS) {
		char c = stack_pop();
		if (c == '(') {
			if (!*f_op) 
				translate_expression(f_op);
			else if (!*s_op)
				translate_expression(s_op);
			else 
				continue; // This should never happen
		}
		else if (c == ')') {
			// This is the actual expression translation
			switch (operator) {
				case 'a':
					sprintf(translation, "((%s NOR %s) NOR (%s NOR %s))", f_op, f_op, s_op, s_op);
					break;
				case 'o':
					sprintf(translation, "((%s NOR %s) NOR (%s NOR %s))", f_op, s_op, f_op, s_op);
					break;
				case 'n':
					sprintf(translation, "(%s NOR %s)", f_op, s_op);
					break;
				case 'i':
					sprintf(translation, "(((%s NOR %s) NOR %s) NOR ((%s NOR %s) NOR %s))", f_op, f_op, s_op, f_op, f_op, s_op);
					break;
			}
			break;
		}
		else {
			if (!*f_op) {
				strcpy(f_op, convert_id_to_full(c));
			}
			else if (!operator) {
				// Keep operator as just a char, makes it easier to parse later
				operator = c;
			}
			else if (!*s_op) {
				strcpy(s_op, convert_id_to_full(c));
			}
		}
	}
	// I think this condition will fix empty recursions 
	if (*f_op && !*s_op && !operator) {
		strcpy(translation, f_op);
	}
	return true;
}

char* convert_id_to_full(char id)
{
	switch (id) {
		case 't':
			return "true";
		case 'f':
			return "false";
		case 'a':
			return "and";
		case 'o':
			return "or";
		case 'i':
			return "implies";
		case 'n':
			return "nor";
	}
}

C:\Users\burrows\code>nor_reduce.exe
(((((((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true))) NOR (((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true)))) NOR ((((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true))) NOR (((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true))))) NOR true) NOR ((((((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true))) NOR (((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true)))) NOR ((((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true))) NOR (((true NOR true) NOR (false NOR false)) NOR ((false NOR false) NOR (true NOR true))))) NOR true))

I spent a reasonable amount of time making sure that the NOR expressions were accurate and from what I could find they seemed to be correct. However, there may be some obscure bug so if you were to see any incorrect expressions you should let me know.

Until later.

Older Posts »

Theme: WordPress Classic. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.