Random Number Seed
Posted in Code
First dog watch, 2 bells (5:17 pm)

I have been running in to an error based on the ages-old method of seeding random generators with time(NULL), the number of seconds since the UNIX epoch. When this process runs in parallel with itself, the RNG gets the same seed because the time resolution isn't fine enough. There are other ways to seed based on hardware RNGs, reading from /dev/random or /dev/urandom, but I'm afraid I may call the function too often and deplete the entropy and make it less useful. Plus, cryptographic-level randomness is not one of my requirements. In talking with coworkers, we came up with adding the number of microseconds to the end of the UNIX timestamp to get a non-repeating number that will only get a duplicate seed during the same microsecond (i.e. highly unlikely).

Since the machine I'm poking around on doesn't have C++11, but does have Boost libraries, we came up with the following code:

#include 
...
int main(int argc, char **argv) {
...
    boost::posix_time::ptime epoch(boost::gregorian::date(1970,1,1));

    boost::posix_time::ptime now = boost::posix_time::microsec_clock::local_time();

    boost::uint64_t x = (now - epoch).total_microseconds();
...

This function will work until we overflow the boost::uint64_t type (an unsigned long long), or roughly at 8:01:49 am on Wednesday January 19, 586524. After that it's someone else's problem.

6 Comments »
Arduino Ingress Hack Timer
Posted in Code, Hobbies, Tech
Forenoon watch, 7 bells (11:58 am)

I've been enjoying playing Ingress lately, but found myself in need of a 5-minute cool-down timer whilst hacking portals. Not wanting to exit the app and launch a separate timer on my Nexus 4, I went to my Arduino for an answer and came up with this solution: a 5-minute timer with a bare Arduino.

That's it, no extra parts necessary.

Using the Arduino's built-in LED on pin 13, After 3 minutes I start turning the LED off and on about once per second. At 4 minutes the blinking speeds up. At 4:30 it speeds up again. At 5 minutes the LED is on steady. Hit the reset button when you hack the portal and start over!

Plug the Arduino in and compile/upload the following code:

const int ledPin = 13;
int ledState = LOW;

unsigned long lastBlink = 0;

void toggleLEDState() {
  if(ledState == LOW) {
    ledState = HIGH;
  } else {
    ledState = LOW;
  }
}

void setup() {
  pinMode(ledPin, OUTPUT);
}

void loop() {
  unsigned long nowMillis = millis();
  
  if(nowMillis > 300000) {
    ledState = HIGH;
  } else if(nowMillis > 270000) {
    if(nowMillis - lastBlink > 200) {
      toggleLEDState();
      lastBlink = nowMillis;
    }
  } else if(nowMillis > 240000) {
    if(nowMillis - lastBlink > 500) {
      toggleLEDState();
      lastBlink = nowMillis;
    }
  } else if(nowMillis > 180000) {
    if(nowMillis - lastBlink > 1000) {
      toggleLEDState();
      lastBlink = nowMillis;
    }
  }
  
  digitalWrite(ledPin, ledState);
}
Leave a Comment »
Using the yaml-cpp Library
Forenoon watch, 7 bells (11:57 am)

I've been using the yaml-cpp library for a while now, and I have to say that overall I'm greatly pleased by how well it works.

As I was making some adjustments to my I/O last night I ran across a bit of documentation that I never noticed before. Of course, it could be newly added. Anyway, I've found the most convenient way to parse my documents (I have many thousands of them to read and write), is to access them by node-name. For example:

node["location"]["name"] >> mObjectLocation.location;

The information I read last night, however, may convince me to change this behavior.

Apparently, named-node access in yaml-cpp is order-n2 complex over the entire document. Put simply, every time you access a node like this the library loops through all nodes looking for a match. Personally, I think a hashed table lookup would have been much faster, and perhaps they'll add that later.

Overall, I wouldn't normally worry about it because my documents tend to only have a few dozen nodes. But I do have 20,000 documents to parse. And to top that off, as they are used they become more complex. And as more items are added, the node size will grow geometrically. I can easily envision a future where a single document contains hundreds of nodes, and it's starting to scare me.

The solution? Well, I can honestly say I don't have a good one yet. I think perhaps if I enforce the order things are written, which already only happens in one way, I can then read in linearly instead of by node-name. The problem with that is if a file is edited by hand and the order is accidentally changed. So by renaming my current solution to readCompatible() and writing a new linear read() function, I should cut down on a lot of extra unnecessary processing.

But I'm still not sure that's the best solution. Any smart people out there have a better idea?

Leave a Comment »
Boost::Spirit 2 Redux
Last dog watch, 8 bells (8:27 pm)

Well if you stopped by yesterday you may have read my post about Boost::Spirit 2 and the trouble I had converting to the new Spirit 2 library. Fortunately, Hartmut Kaiser, one of the Boost::Spirit authors must have a Google blog notification when Spirit is mentioned in a blog, because he left a comment with a suggestion for me earlier!

Unfortunately, I still can't seem to get qi::phrase_parse to work right. The problem is that I'm trying to match one of a set of increasingly complicated grammar structures (perhaps starting at the most complicated and working backwards would fix this issue…). So, here is my problem in gruesome detail:

I'm implementing a get command for a MUD, an online text-only game system. Since I'm writing it from scratch, I decided to use some of the most up-to-date tools I could find to do so, and Boost has some terrific libraries that make this possible. As far as I can discern, the get command can come in the following forms:

  1. get hammer
  2. get 20 nails
  3. get hammer 2 (the second hammer)
  4. get 20 nails 3 (20 of the 3rd type of nails visible)
  5. get hammer from toolbelt
  6. get 20 nails from bucket
  7. get hammer from toolbox 2 (the hammer from the second toolbox)
  8. get 20 nails from bucket 3 (you get the idea)
  9. get hammer 3 from toolbox 2
  10. get 20 nails 2 from bucket 3

The problem comes when using phrase_parse with an empty space skip-parser. Given the two rules:

bool res = qi::phrase_parse(first, str.end(),
				(
					+qi::alpha
				),
				' ',
				item
);

And

bool res = qi::phrase_parse(first, str.end(),
					(
						+qi::alpha
						>> "from"
						>> +qi::alpha
					),
					' ',
					item,
					container
);

If I check the phrase get hammer from bucket it matches rule one, because after you remove all the spaces from the string it's just one long word! This is an unexpected result, and even if I check rule two before rule one I only match rule one!

And now I'm really lost. I imagine there's a better way to do this, but I can't seem to figure it out. Also, since my allergies are going crazy, I've got to take the night off anyway. Anybody out there know of a solution?

3 Comments »
Boost::Spirit 2
Last dog watch, 1 bell (6:34 pm)

Last year I added Boost::Spirit to my MUD project. A few weeks ago I learned that all of the work I had done was deprecated in the new Spirit 2 library. I could still use "Spirit classic," but it is deprecated and may be removed at some point in the future. So I spent some time today figuring out how to convert my grammar rules.

For example, in Spirit classic, I had this rule to handle the most complex rule for my get command. In this case, it handles a command like get 20 items 2 from container 3:

rule6 = int_p[assign_a(mNumberToGet)] >> ' ' >>
			(+alpha_p)[assign_a(mItemToFind)] >> ' ' >>
			int_p[assign_a(mItemNumber)] >> ' ' >>
			str_p("from") >> ' ' >>
			(+alpha_p)[assign_a(mContainerToLookIn)] >> ' ' >>
			int_p[assign_a(mContainerNumber)];

which could be tested by the following code: if(parse(str.c_str(), rule6).full)

Here is the equivalent code in Spirit 2

	std::string::iterator first = str.begin();

	bool r = qi::parse(first, str.end(),
					(
						qi::int_ >> ' '
						>> +(~qi::char_(' ')) >> ' '
						>> qi::int_ 	>> ' '
						>> qi::lit("from") >> ' '
						>> +(~qi::char_(' ')) >> ' '
						>> qi::int_
					),
					mNumberToGet,
					mItemToFind,
					mItemNumber,
					mContainerToLookIn,
					mContainerNumber
	);

	if(r && first == command.end()) {
		return true;
	}

In many ways, the new Spirit 2 library is better, and purports to be much faster as well. The parse function has certainly been made somewhat more convenient. Overall, I'd rather not have had to spend time on this, but the only other option is to lock in with an old version of Boost that may hamper me in the future.

5 Comments »
Post Project Endorphins
Posted in Code
Afternoon watch, 5 bells (2:53 pm)

I'm just wrapping up a project I've had on my plate for months, and I'm feeling the happy brain feeling of finishing up something I've worried about for a long time.

It wasn't terribly complicated, but was subject to constant interruption and upheaval while other projects came along. (FYI in case you don't know, my work requires a great deal of multi-tasking).

My code is compiling fine now, and should be fairly complete. Some more walk-throughs today and testing tomorrow, and it'll be off my shoulders completely. Until testing finds a bug, anyway. And I'll finally be able to say "I've finished it" at my weekly status meeting.

Leave a Comment »
New C++ MySQL Wrapper
Posted in Code
First dog watch, 1 bell (4:53 pm)

I've been writing a replacement C++ wrapper class using the MySQL API. The previous method worked, but was prone to memory overwrites. The syntax is much better now, too. Just include the two header files and:

boost::shared_ptr<MySQL_Server> server = boost::shared_ptr<MySQL_Server>(new MySQL_Server("localhost", "user", "password", "database"));

boost::shared_ptr<Query> = boost::shared_ptr<Query>(new Query(server));

query->setQuery("UPDATE table SET var=val");

if(query->execute()) {
  std::cout << query->getNumberOfAffectedRows();
} else {
  std::cout << query->getError();
}

SELECT query results can be stepped through with the following:

for(unsigned int i=0; i < query->getNumberOfResultRows(); ++i) {
  std::vector<std::string> row = query->getNextRow();
  ...
}

I think I'm going to like this new class a lot more than the old one!

Leave a Comment »
Code Question
Posted in Code
First watch, 4 bells (10:21 pm)

Anybody know why I can't do this?

Given:

class Room {
  typedef boost::shared_ptr<Room> RoomPointer;
  typedef std::map<std::string, RoomPointer> RoomList;
 ...
}

And in another object, reference it like this:

RoomList mRoomList;
if((Room::RoomList::iterator it = mRoomList.find("name")) != mRoomList.end()) {
   return it->second;
}

I always get error: ‘::iterator’ has not been declared back from the compiler.

If I do this, it works fine:

Room::RoomList::iterator it = mRoomList.find("name");
if(it != mRoomList.end()) {
   return it->second;
}

I ask because Nicolai Josuttis (in The C++ Standard Library) recommends comparing the iterator against the end() condition on the same line because of type conversion of various unsigned types that may be used.

1 Comment »
Boost::format
Posted in Code
First dog watch, 2 bells (5:09 pm)

It's official, I really like boost::format!

Forget all that old-school variable argument C-style code with the ellipsis(…), boost::format is where it's at!

Leave a Comment »
Best Compiler Error EVER!
Posted in Code
Afternoon watch, 8 bells (4:23 pm)

I had this happen just a little while ago, and busted up laughing after I read it. I had to walk away from the computer!

Error on line 404: function prototype not found

I thought it quite profound that the error about not finding the function prototype happened on line 404.

FTW!

Turns out I changed the header file but forgot to make it an unsigned int in the cpp file.

Leave a Comment »
Qt and OpenGL
Posted in Code
First watch, 3 bells (9:49 pm)

About a year ago, I started poking around with OpenGL, and began to write a program to display majiang tiles.

Well, with all the Qt I've been writing lately, I thought I'd move it into their API. I have to admit, Qt makes it easy to incorporate OpenGL into your program. Texture loading was really easy, once I realized I forgot to add a call to glEnable(GL_TEXTURE_2D);.

Anyway, tonight I gimped up a quick image to map on to the cube. Here is the result:

OpenGL majiang tile

Leave a Comment »
Trigonometry Lesson
Posted in Code
First dog watch, 3 bells (5:44 pm)

Today I went to one of our resident math geniuses for a trig lesson. Yes, trig—that thing you swore in high school was stupid and you'd never use it again.

The problem was I'm drawing a pie chart and needed to find when the mouse was inside any one of the wedges.
pie chart

So here's how you find whether a mouse click was inside a wedge of a pie chart:
pie wedge trigonometry
Given that the circle is inscribed in a bounding box 200x200 pixels and a mouse click happened at (130,50), here's how you check it:

First, check the distance from the center of the circle to the click coordinates. If this distance is greater than the radius of the circle, you need not go any further. This part was easy and I remembered it from high school.

The center of the circle lies at (100, 100). The distance of the click at (130, 50) is:
sqrt((130-100)^2 + (50-100)^2), or the square root of the square of the difference between the x-coordinates plus the square of the difference between the y-coordinates. If this value is greater than 100 (the radius of our circle), the click is outside the circle and no more math is required.

Next comes the tricky part. If the click was inside the circle, you need to find the angle of the click. In the diagram, you should know angles a, b, c, and d because you already drew them. Depending on your API, you may have them in degrees, or sixteenths of degrees like I did.

So you start by normalizing the x and y coordinates. This means translate it to (0, 0), or more simply subtract the x and y value of the center from the x and y value of the click. In my case this means my translated-x (tx) and translated-y (ty) are (30, -50) (130-100 and 50-100).

The tangent of the angle θ is the opposite over the adjacent side, which are your translated x and y coordinates. To find the angle you need to use tan-1 ty / tx, or atan(ty/tx) if you include cmath. This result is in radians. Make sure tx is non-zero or you will have some problems here.

This part is important! If tx was negative, you must add π to the radians to make sure you get the angle into the negative-x side of the graph! If you don't do this you'll have even more problems.

To convert θ to degrees, multiply the radians by 180 / π.

In my API (I'm using Qt), the degrees go in the opposite direction, so I had to invert the angle.

Compare this result to angles a-d and you have your wedge!

Leave a Comment »
Rookie Mistake
Posted in Code
Last dog watch, 1 bell (6:56 pm)

Today I found I made a rookie mistake in my code project at work. I've been tracking down an error for an hour or so when I finally realized it was due to an uninitialized pointer. I feel so stupid. It shouldn't have happened.

Leave a Comment »
Linking Error
Posted in Code
First dog watch, 3 bells (5:31 pm)

I just solved an annoying linking error in Linux. I have a program I'm writing that has two subdirectories in its source directory, and inside those two directories, two static libraries are built. In the parent directory, all objects are built fine, and everything's shiny until it tries to link the final binary, when I get all these undefined reference to `class::class()`, etc. The constructor, destructor, and other functions seem to have disappeared when I link the library to the main application!

Using nm I can see that the library has those symbols defined! What's going on?

Turns out it was a problem with my Makefile where I set up the linking. I was adding the link path and libraries before the object files of the parent directory. I didn't think there was a problem with this as long as everything was on the same command line. Well it looks like I was wrong. When I changed my linking from

g++ -o program_name -Lpath1 -Lpath2 -lstaticlib1 -lstaticlib2 object1.o object2.o ...

to

g++ -o program_name object1.o object2.o ... -Lpath1 -Lpath2 -lstaticlib1 -lstaticlib2

everything worked perfectly! Sheesh, picky linker!

PS Technically I'm using Makefile variables, so it's easier to read. The actual line looks like this:
$(CC) -o program_name $(OBJ) $(LINK)
but I expanded them for clarity.

Leave a Comment »
Code Day
Posted in Code
First watch, 2 bells (9:11 pm)

I had a very productive day at work today. It's not often I get to work on real coding projects, but right now I have a big one looming over me. Though challenging, I find this one of my favorite parts of my job. I started with nothing today, but ended the day with a good database, a server program with excellent security, and probably 25% or so of the access functionality it needs to have—all in one day! Now that the groundwork is laid, I should be able to accomplish even more tomorrow, and I'm looking forward to it.

Leave a Comment »