A few days ago I wrote a post about how to not go about writing an arbitrary precision data type in C to calculate pi. If you read the article, I talked about how a friend and I were trying to accomplish that task in 24 hours. Needless to say, it didn’t work and I resorted to using a library that was already available. Namely, MPFR. After a little research on Wikipedia about the best approximations to pi, and a couple of days of off and on work, I had a pretty good solution up and running.

First, let’s talk about the math behind this. There are a bunch of approximations to pi; some older, some newer, some faster, some slower. At first, I used Newton’s approximation to calculate pi.

This worked, but was slow (I didn’t record exact execution times). As everyone knows, factorials are huge numbers and grow very rapidly. In this case, the numbers were just too big to efficiently accomplish the task at hand. Could have I done something like Sterling’s approximation? Sure, but there’s better ways to calculate pi. No use in wasting time.

Next up, I gave the cubic convergence version of Borwein’s algorithm mainly because there were no factorials in it. This worked pretty well actually. It calculated pi within a reasonable amount of time (more details below), but because it was a recurrance, I would not be able to multithread it.

Now with multithreading in mind, I turned my attention to the 1993 version of Borwein’s algorithm, which was a summation.

On the up side, it was a summation, which is easy to multithread. On the downside, look at all those factorials. Long story short, I hit the same with this approach as I did with Newton’s approximation above; it worked, it was just too slow.

This past weekend was HackPSU, a typical 24 hour hackathon at Penn State. Without any better idea, my friend, Gage Ames and I decided to break the mold of the typical hackathon projects of games, websites, and mobile apps, and doing something much more nerdy: creating our own arbitrary precision data type in C so we could calculate pi (or any other irrational number) to as many digits as our computers could handle.

About one year earlier I attempted the same project, but with even less success than this time around. My previous solution was to use very large arrays to store the digits of pi in. Obviously, allocating huge amounts of memory for this purpose was a bad idea. That, coupled with a general lack of experience with memory management in C++ led to a complete and utter failure. However, this time around, I tried to learn from these mistakes and took a different approach. After discussing it with Gage, we decided on using pure C rather than any other that fancy C++ stuff, and to use a linked list rather than an array to the store our data. Sounds good so far, but here’s where we made our first fatal mistake. We originally would have liked to use a doubly-linked list as it would have made our adding algorithm simpler. At this stage, I was very concerned with using as little memory as possible though and using a doubly-linked list would have nearly doubled the memory needed to store a digit. As a small digression, knowing that each digit in a node could not be greater than 9, we used a char to save 3 bytes over using a 4 byte integer for each digit. Then, we needed a pointer to the next digit in the list, which was 8 bytes (on our 64bit laptops). There’s no getting around that, but a doubly-linked list would require another pointer to the previous digit, which was another 8 bytes. This brought the total memory needed for a digit to 17 bytes per digit for a doubly-linked list or 9 bytes per digit for a singly-linked list. After a little experimentation, we determined that our adding algorithm would work just fine with a singly-linked list if we represented the digits as the least significant digit at the head of the list. In short, a few hours later we realized that using a singly-linked list and representing the digits in what accounted to little endian was just too darn slow and tedious. But enough talk, let’s look at this horribly flawed code.

Note: As of February 2013, these instructions have been tested with GitLab 4.1. GitLab evolves very rapidly and I do not use it anymore so these instructions will quickly become outdated.

I’ve been looking for a good git manager website that I could install on my own server. A few days ago I found GitLab, which does everything I need it to do and more. The only problem is that the setup guides use Nginx as a webserver. I’m cheap and only have one server, which runs Apache. I also have this Wordpress (this blog) already running on my server so I would like have to install GitLab to a subdirectory too.

Part 1: Running GitLab on Apache

First, let’s talk about running GitLab from Apache. Everything to get Gitlab running on Apache is exactly the same if you’re following the install guides for GitLab, up until the point of installing Nginx. So, if you haven’t started install GitLab yet, go do that and stop when you get to installing Nginx.

I assume you already have Apache installed and up and running, if not, there are more than enough guides floating around on how to do this. I won’t add another to the fray.

GitLab is a Ruby on Rails application and to run it on Apache we need to install the Passenger module.

1
2
$ sudo gem install passenger
$ sudo passenger-install-apache2-module

As you’re not aware, a few months ago I wrote a simple server/client for changing Alsa volumes from another computer, or an Android phone. I’ve been extremely slowly working on adding encryption to it, but unfortunately, jobs and school come before hacking away at projects. Regardless, one downfall of the project has always been that I could change the volume, but I couldn’t play/pause music. All the programs I’ve seen to do this have been media player plugins that are, obviously, specific to that media player only. As someone that changes media players somewhat frequently I didn’t want to go down the road of writing a plugin for one player. Then it hit me, why not have my server simulate media key presses from the keyboard in X11? This would work for any media player that supported media keys and since I already have the server written, it’s only a matter of modifying the protocol to accept more commands and add a function to simulate key presses. However, first I needed to figure out how to simulate key presses. It turns out it’s very easy. Let’s jump right into the code.

Disclaimer: I am NOT a crypto expert. Don’t take the information here as 100% correct; you should verify it yourself. You are dangerously bad at crypto.

This post details the EVP functions for RSA. If you’re looking for a pure RSA implementation or want something in C rather than C++, see my other post on this.

In my seemingly endless side project to implement RSA and AES encryption to my Alsa Server project, I wrote a while ago about doing simple RSA encryption with OpenSSL. Now, I’m here to say that I was doing it all wrong. In my first post about RSA encryption and OpenSSL my code was using the low level RSA functions when I should have been using the high level EVP (envelope) functions, which are much nicer to work with once you get the hang of them.

Being that this code is eventually going to be merged in my Alsa server project, I went ahead and also implemented AES encryption/decryption and put everything in an easy to use C++ class.

I assume that readers are familiar with encryption and OpenSSL terminology (things like IV, key lengths, public vs private keys, etc.). If not, look it up since there are much better explanations out there than I could write.

Why use the EVP (envelope) functions for RSA encryption rather than the actual RSA functions? Becasue the EVP functions don’t actually encrypt your data with RSA. Rather, they encrypted a symmetric key with RSA and then encrypt your data with the symmetric key. There’s a few reasons for this. The main one being that RSA has a max length limit to how much data can be encrypted at once. Symmetric ciphers do not have this limit. If you want pure RSA, see my post about that, otherwise, you probably want to be using the EVP functions.