Archive for the ‘Development’ Category

C++ Loop Challenge

Saturday, April 22nd, 2017

I received a C++ challenge in the RIT Game Design & Development group on Facebook, so I decided to chart my iterative approach to solving it in hopes that I learn a few things and can share.

Here is the challenge I was given:

Program a counter that goes from 0 to 15, and then at 16 loops back to 0, going on forever. The counter itself is within a function, and it increments every time the function is called.
You are no longer allowed to use:
-Branching (which includes try catch, if statements, switches)
-The & operator
-Modulus (%)
-Overflowing a bitfield
-Overflowing any other data type
-Compare operators (==, < , etc) -Bit shifting to create any of the operators not allowed here (bit shifting in general is fine, but no doing & with bit shifting) -MOV instructions to create any of the operators not allowed here (you can recreate every instruction out of mov's) -Assembly instructions in general to create any of the operators not allowed here. -Looped linked lists. -Hardwiring a circuit explicitly for this purpose. -Overflowing a buffer with zero's to write over the parts of the counter that go above 16. -Using lookup tables -Unrolling the loop -Never-ending streams of interns -Webcam related number-recognition

There’s a lot to check off here, but I decided to start with a basic implementation first and then handle each restriction until all have been met. With that, here’s the basic first step:

“Program a counter that goes from 0 to 15, and then at 16 loops back to 0, going on forever.”

So I put that together and here’s what we have:

#include

int main()
{
int counter = 0;
do
{
++counter;
std::cout < < counter << std::endl; if (counter > 15)
{
counter = 0;
}
} while(counter != 0);//true);

return 0;
}

(see it at http://cpp.sh/2pjsh)
I of course modified my do/while loop so I could verify that it is counting up without it running forever and simply commented out the code that would do so.

Next we have “The counter itself is within a function, and it increments every time the function is called.”. This has two parts: (1) counter is defined within a function and (2) the counter increments every time the functioned is called. With slight adjustments, here’s what I came up with:


#include

int PerformCounter()
{
static int counter = 0;
return ++counter;
}

int main()
{
int counter = 0;
do
{
counter = PerformCounter();
std::cout < < counter << std::endl; if (counter > 15)
{
counter = 0;
}
} while(counter != 0);//true);

return 0;
}


(see it at http://cpp.sh/3thj3)

With this, we have our variable created within the PerformCounter function (there’s no rule about static or not!) and incremented in the function.

Now we start hitting the list of restrictions. The first one we have is “Branching (which includes try catch, if statements, switches)”. This is a bit harder! However, we have C++ on our side. Thinking of ideas around this, I came up with a crazy idea: lambdas!


#include
#include
#include

const int MAX_NUMBER = 16;
std::array, MAX_NUMBER+1> incrementers;

int PerformCounter()
{
static int counter = 0;
return incrementers[counter](counter);
}

int main()
{
// Construct the array of lambdas
incrementers.fill([](int &v)
{
return ++v;
});
incrementers.back() = [](int &v)
{
return v = 0;
};

// Perform the counting
int counter = 0;
do
{
counter = PerformCounter();
std::cout < < counter << std::endl; } while(counter != 0);//true); return 0; }

(see it at http://cpp.sh/3f2b)

My idea here was not only to have each number increment the same except the final, but also to allow the list to be dynamic (why not!?). Looking through the list, this fulfills all of the restrictions! Although, one might argue that this still conflicts with the "Lookup table" restriction. I might revisit this at a later time when I dig into std::enable_if and template metaprogramming a bit more.

What do you think? What would your solution be?

Hadoop & Flume: Log Crunching

Thursday, December 15th, 2011

I’ve recently been experimenting with log crunching. Specifically, taking the log files of a handful of Apache servers and stuffing them all in a single location, perchance to make a nicer interface for scanning them for notable errors. Wouldn’t that be nice?

Nonetheless, one of the first steps in conquering this was to setup an area where all the logs would go. One could think of an NFS share or an ever-growing RAID volume like XFS or ZFS, but let’s think: what if instead of a handful of Apache servers, we had a few thousand of them? That RAID setup would be filled very quickly! Enter Hadoop – this system supports Map-Reduce functionality, where nodes of machines will map out a function to multiple machines and reduce it by computing each part, and HDFS (the “Hadoop File System”).

The Hadoop Elephant Logo

The Hadoop Elephant Logo

Particularly, I was looking into HDFS for now; this fancy filesystem is a distributed filesystem in that it will span across multiple machines, let alone across multiple disks if you place it atop a RAID setup. Not only will this save an immense number of log files, but replicate them and allow for a map-reduce functionality for parsing them. Awesome!

I started this by crabbing Cloudera’s hadoop package. I’ve followed a few papers and articles done by Cloudera and they seem pretty dependable, especially since they have their own github page even, so the world can view their source. Nonetheless, I snagged their hadoop binaries and extracted them on my linux box. I then setup a new hadoop user (via useradd -m in a root terminal) and changed the permissions so that this new hadoop user owned said directory (standard chown -R hadoop:hadoop /opt/hadoop/, since I extracted the hadoop binary package into /opt/hadoop/).

After this, it was surprisingly smooth sailing to a functioning single-server hadoop node. I created environmental variables for my hadoop user by editing its ~/.profile file and adding:

export HADOOP_HOME=/opt/hadoop
export PATH=$PATH:$HADOOP_HOME/bin

Afterwards, sourcing the file again so that my changes took effect (source ~/.profile). This allowed me to run the hadoop binaries from my bash shell without having to hop around.

I then edited the “core-site.xml” file under the hadoop configuration directory (normally $HADOOP_HOME/conf/core-site.xml). This file might not exist, but no worries. Here’s what I put into mine:

<configuration>
  <property>
    <name>fs.default.name</name>
    <value>hdfs://my.hostname.here:9000</value>
  </property>
  <property>
    <name>dfs.data.dir</name>
    <value>/mnt/hdfs/data</value>
  </property>
  <property>
    <name>dfs.name.dir</name>
    <value>/mnt/hdfs/name</value>
  </property>
</configuration>

After setting this up, I then had to create & provide the correct permissions for the directories that our HDFS storage would be using, so from a root terminal:

mkdir -p /mnt/hdfs/data
mkdir -p /mnt/hdfs/name
sudo chown -R hadoop:hadoop /mnt/hdfs

Alright! So now we have all of our filesystems and configuration files taken care of… now just to format the HDFS set and start it up! So, switch to the hadoop user and run:

hadoop namenode -format

This will format our HDFS storage (namely, what we had in /mnt/hdfs/). You can imagine that this is like formatting your hard disk for a filesystem. The last piece of the puzzle, of course, is running the HDFS service so that our files can be replicated over and all that good stuff, so again as the hadoop user:

start-dfs.sh
This is a script stored in the $HADOOP_HOME/bin/ directory, “just in case” if you are unable to find it.

Now, onto Flume. This is where things started to crumble a bit sadly. I won’t go through a guide for this since it still remains unsuccessful and I don’t want to guide anyone into a brick wall.

Flume’s core is that it is able to pipe data. My circumstance specifically was 3 layers: Apache logs -> aggregate -> hadoop storage. I’d have a few (let’s pretend tends of thousands, but in reality only a handful) apache servers running, piping bits of information into its error and access logs. A flume process running on each apache server would simply be tailing the error logs at first (and add the access logs later after I got errors working) and pipe that into the aggregate. The aggregate flume process would, in turn, take all of these logs and drop them into the hadoop storage layer, allowing me to horde them forever and ever; a single node would be dedicated to this task. Sounds pretty simple, right?

Well, not so much. Flume’s configuration, surprisingly, wasn’t too difficult once you wrapped your head around the idea of sources and sinks (sources being the origin of the data and the sinks being the destination). You could easily pipe sources and sinks of data together with flume processes. The flume processes running on the Apache servers were haplessly sending data to the aggregate which was perfect. However, I think I hit what was a flume bug: FLUME-757, where there’s a race condition, so Flume spits out null usage errors. This put a rut in my plan, although it might have simply been user error (however I am pretty sure it was the bug ;)).

Further developments will be trying out fluentd, a similar data piping application, instead of flume to see if that provides excellent aggregate & piping functionality for my needs. Needless to say, I’ve been able to have my HDFS Hadoop layer working, now I simply have to either find the right solution or work out the bugs & kinks in the actual piping of data. Hopefully I’ll be able to make another post or an update to this with great success soon!

Android Threads

Wednesday, March 3rd, 2010


For the past few weeks, I have been looking into development for the Android mobile device operating system. Development for this operating system requires the use of the Java programming language with additional libraries provided by the publicly available Android SDK. As such, I’ve ventured back into the world of Java, as well.

Hopping into Android development is very easy by utilizing the provided Android Tutorials. However, there are a few tricks here & there that one does not easily find, which brings me to the current blog post.

Threading in Android one would believe would be identical to how one creates and handles threading in Java. However, there are a few intricacies that one must obey in Android whereas in Java they need not be required. For example, in the following Java class, it displays a simple text field that a thread updates with the current UNIX timestamp:

import javax.swing.JFrame;
import javax.swing.JTextField;

import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;

public class TestJava extends JFrame implements Runnable {
	
	private JTextField textField = null;
	private boolean runThread = true;
	
	public TestJava() {
		this.textField = new JTextField();
		this.add(this.textField);
		this.setTitle("Testing Java");
		this.addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent we) {
				runThread = false;
				System.exit(0);
				return;
			}
		});
		Thread counterThread = new Thread(this);
		counterThread.start();
		this.pack();
		this.setVisible(true);
		return;
	}
	
	public void run() {	
		while(runThread) {
			this.textField.setText("" + System.currentTimeMillis());
		}
		return;
	}
	
	public static void main(String[] args) {
		TestJava test = new TestJava();
		return;
	}
}

This is pretty straight-forward, modifying the JTextField from within the run function. However, in Android, only the thread that owns the UI interface can update said interface, which causes a few complications. The following class in Android will perform (roughly) the exact same as the prior class did within the standard Java libraries:

package com.andrewmkane.test;

import android.app.Activity;
import android.os.Bundle;
import android.os.Handler;
import android.os.Message;
import android.widget.TextView;

public class ThreadActivity extends Activity implements Runnable {
	
	private TextView textview = null;
	private boolean performThread = false;
	
	protected void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		textview = new TextView(this);
		this.setContentView(textview);
		return;
	}
	
	protected void onStart() {
		super.onStart();
		this.performThread = true;
		Thread counterThread = new Thread(this);
		counterThread.start();
		return;
	}
	
	protected void onStop() {
		this.performThread = false;
		super.onStop();
		return;
	}

	public void run() {
		while(performThread) {
			handler.sendEmptyMessage(0);
		}
		return;
	}
	
	private Handler handler = new Handler() {
		public void handleMessage(Message msg) {
			textview.setText("" + System.currentTimeMillis());
			return;
		}
	};
}

In the class above, you’ll notice that instead of setting the text of the TextView (akin to a JTextField), we set the value within the private Handler object. This is done because the run function is housed within a separate thread, while the Handler object is held within the primary UI thread.

This way, our secondary thread sends a message to the Handler located in the primary thread. The primary thread, which has access to the UI, then is able to modify the TextView without being denied access, whereas the secondary thread (within the run function) would have been. It’s a bit complicated, but makes sense – limiting the UI to a single thread allows developers to run processes in the background without accidentally mucking up the UI all the while making sure the UI has a dedicated thread to maintain decent performance.

Parsing QR Codes

Thursday, April 16th, 2009

For a class I am currently taking, we started to explore various ways of ensuring that a user has visited or is visiting a certain location, utilizing the common cellular phone. Our first thought of utilizing the phone’s geo-locating device, but quickly realized the amount of legal issues that would probably arise from such an endeavorer. We then thought of an alternate way: pictures! Most modern cellular phones have a camera built in and, worst possible case, a user surely has a camera of some sort at their disposal. Our idea consisted of utilizing QR Codes to ensure that a user had visited or is currently visiting a certain location.

Good Humorous Example of a QR Code

Good Humorous Example of a QR Code

QR Codes contain data in a 2D matrix, similar to our everyday barcodes which are simply 1D. Therefore, QR Codes can contain more data and simply look much cooler! Our plan is to simply encode a brief message into a QR Code and place it at said location for users to photograph and upload later if they do not have a camera-enabled phone, otherwise they would be able to take a picture of it and forward it to us via MMS message or e-mail.

The issue after this, however, was how to identify their QR Codes as being correct from a technology stand point. I figured that my current LAMP server would serve as an ideal testing grounds for this and I slowly was able to put together a sample QR Code parser. However, oddly enough, I was completely unable to discover a simple PHP QR Code decoder/parser. Instead of recoding the wheel per-say, I found an excellent Japanese QR Code decoder written in Java. Utilizing this, I was able to rig my PHP script up for excellent QR Code parsing! The fancy script I ended up with is below.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
	<title>QR Code Testing</title>
	<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
	<div id="qrcode_text">
<?php
	if(isset($_FILES["qrcode"]) && isset($_FILES["qrcode"]["name"]) && strlen($_FILES["qrcode"]["name"]) > 0) {
		$img_file = mt_rand(0000, 9999) . $_FILES["qrcode"]["name"];
		if(move_uploaded_file($_FILES["qrcode"]["tmp_name"], "./temp/" . $img_file)) {
			$output = shell_exec("java -jar qrcode-cui.jar ./temp/" . $img_file . " 2>/dev/null");
			exec("rm -rf ./temp/" . $img_file);
			if(!$output || strlen($output) <= 0)
				echo "<b>Error</b><br/>It seems the QR Code was invalid or did not have any content";
			else
				echo "<b>QR Code Content</b><br/>" . $output;
		}
	} else if(isset($_POST["qrcode_url"])) {
			$qr_url = str_replace("`", "\`", str_replace("\\", "\\\\", str_replace(";", "", str_replace("&", "\&", $_POST["qrcode_url"]))));
			$output = shell_exec("java -jar qrcode-cui.jar \"" . $qr_url . "\" 2>/dev/null");
			if(!$output || strlen($output) <= 0)
				echo "<b>Error</b><br/>It seems the QR Code was invalid or did not have any content";
			else
				echo "<b>QR Code Content</b><br/>" . $output;
	}
?>
	</div>
	<div id="qrcode_form">
		<form action="#" method="post" enctype="multipart/form-data">
			<p style="display: none;"><input type="hidden" name="MAX_FILE_SIZE" value="2048000" /></p>
			<p><label for="qrcode">QR Code Image</label> <input type="file" id="qrcode" name="qrcode" /></p>
			<p><b>OR</b></p>
			<p><label for="qrcode_url">QR Code Image URL</label> <input type="text" id="qrcode_url" name="qrcode_url" /></p>
			<p><input type="submit" value="Check QR Code" /></p>
		</form>
	</div>
	<div>
		<p>Don't know what a QR Code is? Here's an example!</p>
		<img src="./qrcode_test.png" alt="A Sample QR Code" width="268" height="268" />
		<p>QR Codes are 2D barcodes! They hold much more information than our common 1 dimensional barcodes</p>
	</div>
</body>
</html>

So far, so good. If you have any questions or comments, feel free to comment below! You are also free to use the source code I have provided.