Understanding Memory: Part 2

In Part 1, we demonstrated a basic memory model and how in order to modify variables, one must know the variable’s address. In this section, we will talk about pointers vs arrays, and introduce the heap and stack.

Pointers vs Arrays

You may have heard already that pointers are arrays and arrays are pointers. First, consider the difference between value arithmetic and pointer arithmetic:

int var = 5;                 // var is 4 bytes starting at 0x10
var = var + 1;               // var is now 6

int* ptr = &var;             // ptr is 8 bytes starting at 0x14
                             // containing the value 0x10
ptr = ptr + 1;               // ptr now contains the value 0x14

What on earth happened here? Pointer arithmetic operates in address space; the basic unit is the size of the pointed-to type. In this case the size of an int is 4, so ptr + 1 means “advance ptr by the size of 1 int.”

When we think of arrays, we typically picture:

int arr[4] = {1, 2, 3, 4};   // 4 ints starting at 0x20
                             // note that arr is an int*, 8 bytes at 0x18

We can then use the subscript operator, [] to access individual elements:

arr[3] = 6;                  // arr is now {1, 2, 3, 6}

But the subscript operator doesn’t apply to “arrays”, it applies to pointers! The following are all equivalent ways to access the memory at 0x28:

arr[2] = 10;                // subscript operator
*(arr + 2) = 10;            // dereference offset pointer (by 2) 

The subscript operator combines offsetting, the size of the pointed-to type, and a pointer dereference into a single operation. The following equality holds:

*(arr + 1) == arr[1] == 2   // second element in array
(arr + 1) == &arr[1] == 0x24 // address of second element in array

The type of arr may be int[4] but this type decays to int* which means it can be used anywhere an int* is allowed. Note that the reverse is not true; an int* is not usable, for example, as an argument to a function taking an int[4], because the compiler cannot determine that the length of data pointed to is of length 4.

Stack vs Heap

So far we have been using arrays allocated on the stack, a region of memory whose creation and destruction is managed by the compiler. This memory is extremely fast to use as its allocation is static (compile time) instead of dynamic (run time) and does not incur memory allocation overhead. Also, the compiler can often significantly optimize stack allocated memory as it has more information on object lifetimes. Typically, splitting up a complicated expression into several intermediate variables does not incur a runtime performance penalty as the compiler can determine the limited scope of the intermediate variable and simply substitute the value directly into the next expression.

The other type of memory available is the heap, a set of dynamically (runtime) allocated regions of memory made available to your program by the OS’s kernel. This chain of allocation from your program to the kernel and CPU is incredibly complicated (but super cool) and so won’t be included here. The size of the stack varies, but ~8MB is typical. The heap on a modern computer is typically 1000x larger.

Lets see now how to make use of the heap:

int* darr;
darr = malloc(sizeof(*darr) * 5);   // create memory for 5 * sizeof(int)

// use the memory for something

// free the memory region
// note that darr still points to the same address
// (which is now invalid). This is called a "dangling pointer"
free(darr);                                 

The C standard library function malloc() takes a size argument as the number of bytes to allocate, and returns a pointer to the first byte. In C, the return value is an untyped void * that can be assigned directly to a typed pointer, such as darr, allowing the memory to be interpreted as the desired data type. Usage of heap allocated memory is no different that of stack allocated regions. The same subscript and pointer arithmetic operations are valid.

The difference is the lifetime of the memory: stack allocated memory is implicitly managed by the compiler whereas heap allocated memory is managed explicitly by the programmer. As you can allocate memory using malloc(), you can deallocate with free(). This fundamental difference yields a whole aspect of software design that impacts everything from CPU design to application architectures: Memory Management. Significant engineering and theory work has been done to make memory management fast, safe, and easy to use. As an exercise to the reader, consider that the free function does not take a size argument, only the original address and what this must mean about the implementation of malloc() and free().

The code sample above mentions a dangling pointer. This is a pointer whose memory has been free’d but the address is still known and the pointer can be dereferenced. The results of this are undefined; the address may be completely out of bounds and any access would cause application termination, or the address may reside in another valid region due to subsequent allocations. These type of memory errors can be very difficult to track down without proper tools.

Fundamentally, memory manipulation is the principle underlying all runtime operations of a program. In all but trivial cases, application designers must be aware of how memory is allocated, used, and destroyed and must carefully balance runtime performance vs memory utilization, especially in resource-constrained environments. Much of data structure design is based on how to manipulate memory efficiently. A solid understanding of the computer memory model and utilization of memory in an application is absolutely critical. Being able to conceptualize a routine in terms of the memory requirements, usage, and layout aids understanding and enables complex algorithm design.

Posted in Software | Leave a comment

Shifting My Own Bits – Part 3

In Part 2 I explained the central conundrum I’m facing:

TL;DR: Participating in life makes me feel like a fraud, but I need to participate in life in order to be happy.

I have made some progress in understanding the origins of this position.

In late June I read Atlas Shrugged and was fascinated by the prolific discussions of morality. As I pondered, I realized that I don’t have a well-defined moral code. Morality here answers the question of “why live.” I wasn’t brought up religiously, so I don’t have a third-party morality instilled into me. I was always a good kid (mostly) growing up and wasn’t into drugs, acting out, or rebelling, and so never had an drastic event that made me stop and consider morals — a common scenario in many coming-of-age movies. I was able to obtain approval from parents, teachers, and supervisors easily due to my talents and didn’t stray far enough from the path early on to have to stop and determine my course.

I have always been exploring and tinkering, likely due to how I was brought up. Early on in my schooling I had an attitude of “I must be more interested in this since I’m doing the extra credit and others are not”. Over time, this shifted to “I’m doing extra credit because I can and others cannot”, to “I’m doing extra credit because I am better than others,” and finally to “I am intrinsically better than others.”

The last leap is critical and requires additional explanation. At school, I was able to obtain recognition for superior results on assignments despite whether I put in more, equivalent, less, or almost no effort; whether I was interested in, neutral about, or bored by the subject; and whether I knew a lot, no more, or nothing about the material beforehand relative to others. There are many explanations for this: assignments that were very easy, awards that were handed out plentifully, or my natural talents.

The conclusion I came to at the time was that I was intrinsically smart; I wasn’t simply good at a particular subject to the detriment of others, I wasn’t simply good at learning new things, and I didn’t simply have knowledge above and beyond what was required. Morally this meant that pride in my identity, the will and desire to live, came from this belief that I was just better, intrinsically, than others, and I could use this to ability obtain the success, approval, and love that I desired. Through this lens I interpreted events in interesting ways. If I did well on an assignment, or received an award, it recognized an ability I had, rather than something I had learned. If I did poorly (which did happen on occasion), it meant that I just wasn’t really trying.

When I got to the point of my life where I was really thinking about the future, likely when I started thinking about college, I began to wonder what I could be. I began to explore media that showed some potentials; I was particularly attracted to characters that appeared initially to be normal, yet not quite fit in. These characters would later on demonstrate some extraordinary, innate ability that appeared as as result of achieving their potential when certain events caused them to give their all in a way they were unable to normally. I started to identify strongly with these characters and begin to incorporate the idea that I had some innate hidden ability that was waiting for the right moment to appear. I would get all the success, appreciation, and love I could ever want if I could just release this inner ability.

I began to crave this feeling of potential power, in the way that the anticipation of a thing is sometimes more gratifying than the thing itself, and sought out this feeling in the fantasies of movies, comics, and music. My favorites were the ones that made me feel an anticipation of power to achieve. When working on a task, I could transform initial interest into exuberance by convincing myself that the task was too difficult for mere mortals, but that I was going to do it. It wasn’t the task itself that was meaningful, but the belief that I could do it as no one else could that resonated with my moral core and became little glimpses of happiness.

This lust for potential power continued into my college years, where it ran headlong into my inability to breeze through assignment as I had in high school. Far from being recognized for extra credit work, I wasn’t even achieving A’s on the normal assignments first quarter first year. I figured I just wasn’t trying, but after trying harder and harder and still failing, I could no longer make that excuse. I expected my abilities to come forth, to be able to transform any task into one at which I could succeed, but this didn’t happen. My moral code couldn’t handle this new situation: I suddenly didn’t have the ability to excel and achieve recognition.

Going to study sessions or asking profs for help as did most people in my situation felt wrong — I had to force myself to ask for help, despite the knowledge that I would benefit immediately from doing so. Unknowingly at the time, I began to have to perform actions that went against my moral code and in doing so began to lose sight of my identity. If I was no longer better than others, gifted with an innate ability just waiting to come out, then who was I?

With this uncertainty in my identity and moral code, I began to drift; I was going rapidly between pride in my accomplishments and self loathing at my failures, unable to account for the events in conflict with who I thought I was. The inability to recognize these as moral issues led to an increasingly confused, insecure definition of self that compounded with each new event. I was stuck. I would feel bad for doing certain things and bad for not doing other things, but I didn’t recognize the pattern. It became a pain that wouldn’t go away because I didn’t know its source. I could escape it for a little while but I could never be at peace with it.

I’ve been slowly searching for a way to understand this pain over the last 8 years. I understand now why this journey has been so difficult; my moral code does not permit me to ask for help or to discuss these issues with anyone. The conclusion of Part 2 was that despite knowing what I need to do, doing it feels wrong; the conclusion I make here is that my moral code is corrupt, does not reflect who I really am, and is preventing me from achieving my goals. I choose now to recognize and reject this corrupt code and determine instead a conscious definition of morality that accurately reflects my unconscious self.

I’ll start with something like this:

  1. I exist
  2. I choose to live as a rational being
  3. I choose to hold my life as the basis of my values; that which preserves life is good, that which destroys is evil
  4. I choose to hold reason, purpose, and self-esteem as my ruling values; reason, as my tool for knowledge, purpose, as my choice of happiness that my reason must achieve, and self-esteem as the certainty that my mind is competent and I am worthy of happiness, worthy of life.

This is the basic, objectivist morality proposed in Atlas Shrugged. The three primary values then require all of the virtues: honesty, integrity, rationality, independence, justice, productiveness, and pride. I like that it starts with a fact (existance) and then builds upon it with a set of choices, rather than commandments. Fully realizing these choices for my self will be a good start, but will only be the first step in the journey; I will have to come to terms with the actions of my past, repair my self-esteem with forgiveness, and repair what hurt I have caused others. I don’t know how long it will take, but I expect it to proceed efficiently; if I am working in accordance with my values, then I can begin to feel pride in earning my values, and in doing so, experience the happiness that is the result of using the mind’s fullest power, rather than the joy of escaping the mind.

Posted in Self | Leave a comment

Shifting My Own Bits: Part 2

TL;DR: Participating in life makes me feel like a fraud, but I need to participate in life in order to be happy.

A year-and-a-half ago I wrote Part 1 of my foray into understanding myself, at the time coming up with several explanations for my attitudes. Unfortunately, knowledge is only half the battle; understanding that my attitude doesn’t match reality doesn’t make it easy to change, to reinvent myself. It’s easy to follow advice and take a step in the right direction, to “go out and do something today!”, but the momentum doesn’t last. It’s like pouring water on sand — no matter how much water you pour on, no matter how much the water pools and aggregates, it will always drain through.

Even while out my old attitudes persist. I’m there looking for a chance to excel, to prove how superior I am, to feed off the love and admiration of others. It’s like a drug. If I can’t find that opportunity, or if I fail, I tune out. I’m no longer participating, just biding my time until I can leave. I don’t project a bubbly, happy personality, and so no one talks to me; I in turn talk to no one as I’m so afraid of that awkward moment when I have nothing to say except the thousand things I can’t, so afraid of being identified as boring and empty. I’m a puzzle piece trying to fit into the wrong puzzle.

Listening to others conversations, I realize I would have nothing to say even if I was part of them; I can’t relate to the social experiences of others because I am not social. I didn’t go to that event last week, I didn’t see that TV show, I didn’t hear that song, I didn’t have that relationship, I didn’t feel those things at all. How can I cheerfully interact with others’ happiness when I’m in a constant state of denial over my own? When I spend my Friday nights trying to understand myself, trying to alter the attitude that keeps me unhappy. How can I relate to anyone without these flaws, except on a peripheral basis?

These outings leave me broken, an overwhelming mix of feelings I can’t understand, parse, or organize. The high from having overcome anxiety and actually gone, the rush from brief positive interactions and the hope they will turn into my cure, the deep funk of failure as reality sets in. Each of these is an experience, but not a lasting one. My perspectives and attitudes remain unaltered, I make no friends and start no relationships; I’m not participating in life.

This is not to say I do nothing; I really enjoy my work and I do several sports to at least maintain my mind and body. I can also overcome anxiety in certain circumstances; I interact with people when I need to. While others have found success by making a plan and sticking to it, I need to understand what’s holding me back before I can move forward. I need to understand the difference between the cases where I can engage with society and when I can’t, to develop an attitude that allows me to connect personally with social interactions instead of remaining aloof, to get to a state where I don’t look upon yesterday with regret.

But how? Such introspection is hard, and sometimes painful. It’s easy to get distracted, to run and hide. Perhaps the “go and do it” approach would work for me too, but I can’t shake the feeling that it’s all fake; I’d be a fraud, trying to be someone I’m not. In my dreams I find someone who is also broken; together we work through the pain and come out victorious. But so far that seems to just be more wishful thinking. Movies and books portray growth shaped by friends and acquaintances which certainly sounds good, but I’d have to engage socially — and openly — for that approach to work for me.

Posted in Self | Leave a comment

Understanding Memory: Part 1

This article is meant for programmers who have some familiarity with writing and compiling simple code in C/C++. It assumes the reader knows basic data types like int and double and how to define and use variables and functions. This article will then expose the reader to a basic memory model, explain how the use of variables interacts with this memory, and introduce addresses and pointers.

On a modern platform, memory is presented to a program as byte-addressable blocks. Each byte in this block has an associated integer address; this address is used to identify to the computer which piece of memory to operate on. For this demonstration, let us assume our program has a block of memory with the first byte at address 0×10. Each variable we declare in our program must occupy some of this memory. The compiler we’re using will use this memory to store variables we define. Different data types can be different sizes: an int type is commonly 4 bytes, while a double is usually 8.

int cakes = 10; // 4 bytes starting at 0x10.
double level = 11.5; // 8 bytes starting at 0x14.

To manipulate these variables, we simply assign a value to their symbols, since their addresses have been managed for us by the compiler:

cakes = 15; // the compiler knows where "cakes" is stored in memory

Addresses and Pointers

Now, we would like to modify the values of these variables from an external function. This function does not know about the variables we have declared here because it exists at a different scope. We need two things to accomplish this. First, we need a way to obtain the address of our cakes variable in memory. For this, we can use the address of operator, &. Second, we need a variable into which this address can be stored; this is the pointer type, specified by a data type and a *. The size of the pointer type on this platform is 8 bytes, allowing for a 64-bit address space.

int *ptr_to_cakes; // 8 bytes starting at 0x18.
ptr_to_cakes = &cakes; // the value of ptr_to_cakes is 0x10

To modify the value through the pointer, we dereference, using the * operator.

*ptr_to_cakes = 25; // there are now 25 cakes

Lets go ahead and modify this value in our function.

/* Function takes a pointer to an int, allowing it to modify the value */
void get_num_cakes(int* how_many_cakes) {
    *how_many_cakes = 17;
}

get_num_cakes(ptr_to_cakes); // sets cakes to 17.
get_num_cakes(&cakes); // can pass address directly.

The next extension to this happens when we would like someone to modify the value of ptr_to_cakes, so that its value contains a different address. The principle of course is the same: to modify a variable, one must know its address.

void set_cake_ptr(int** cake_ptr_ptr, int* new_cake_ptr) {
    *cake_ptr_ptr = new_cake_ptr;
}

int another_cake = 1; // 4 bytes at 0x1C
set_cake_ptr(&ptr_to_cakes, &another_cake); // ptr_to_cakes is now 0x1C

Posted in Software | Tagged , | Leave a comment

Shifting My Own Bits: Part 1

Refactoring plays an important role in the software development lifecycle — an opportunity to incorporate lessons learned, improve code quality, and lay down a solid framework going forward. The entropy decay of code over time that necessitates refactoring plays a role in other places as well, such as our minds. We can apply the principles of science and engineering to ourselves, allowing us to control who we are with rigorous analysis and study. This rather long essay won’t be appealing to those who came here looking for code snippets, but I want to share some refactorings I have recently undergone in the hope that they can help others who are suck as I was.

If we accept as a primary goal the maximization of happiness, we can thus analyze our actions, state of mind, and thoughts to determine what causes us to be unhappy. For me, this was simple: people were out doing cool stuff and I wasn’t out doing it. It would have been simple to just go out and do these things, except for some reason, it didn’t feel right. There were times when I would go out and be social, usually at a friends request, but the urge to enjoy society declined when these friends weren’t around. I enjoyed these outings, so I didn’t see myself as someone who fundamentally doesn’t like the company of others. It was time for some root cause analysis.

This yielded some fruit: from the basic human need to feel love and appreciation, to matter, I was able to obtain this from an early age by being smart — I was rewarded in school and at home for being the smart kid, the A student, the one who worked hard and always went the extra mile. Because of this, I was also the special kid — as a nerd from an early age, I was never popular, never had a large group of friends, never really obtained appreciation from social interactions. This special-status became a drug: at first I was pleased to receive, then I was used to it, expectant, demanding.

“Of course I’m special” became the mantra; being smart became my identity.

Excelling on a project was no longer an action, it was who I was. I begin to enter situations with the expectation that I would be treated specially, assuming the regular rules didn’t apply to me, that there was always an exception. Through high school, this was mostly correct — I received a steady supply of alternate assignments, privileges, and modifications to my courses. This has ultimately lead to a very successful career track, which I’m ultimately grateful for, but at the expense of social development.

In college, I hit a wall right away. I was no longer the smart kid. No one knew me, I was a stranger in a town on the other side of the country with a bunch of other strangers who had better educational backgrounds. Right away I began to receive assignments that were actually hard! I could no longer just breeze through them, or demonstrate to the instructor that I required something more interesting — I was to do just the regular assignment with no possibility of praise for an exceptional effort. It wasn’t that I didn’t know how to ask for help, or where to find resources should I have needed them, but asking for help just wasn’t something I did. I was supposed to know how to do it, and if not, certainly wasn’t supposed to be seen showing weakness by asking for help.

I wasn’t that I couldn’t fail because someone would express disapproval, I couldn’t fail because success was my identity — without it, who was I?

My system broke. I could no longer attain the steady flow of appreciation I had become addicted to by working hard. I flipped back and forth between different temporary explanations — maybe stress due to new environment, maybe that class was just hard, maybe I need a break — but none really stuck. One of the major side effects of the appreciation addiction was coming to bear — without the steady reward trail, the path forward was no longer there. I didn’t know what to do. With each failed assignment returned to me (<A was failure), I decayed further. Was I stupid? How come others weren’t having these problems? Why didn’t I know how to do this? What the fuck is wrong with me? I began to blame myself and started a cycle of negative reinforcement, adding more stress to what I had from complete lack of financial stability.

There was enough logic left in me to know that dropping out of college was a terrible plan, so I pulled through it somehow and managed to graduate and get a job that I enjoy. I had more direction at this point certainly, and the job offered the effort/reward cycle that I excelled at easily. Outside of work, however, little progress had been made. With a fresh start in a new city, a car (didn’t have one during most of college), and no more financial worries, I should have been set free. But instead of abundant social interaction, I stayed inside. Part of the internal expectation that I was to know all things was causing a block on learning new things necessary to increasing social interaction — finding things to do, places to go, etc. This was accentuated by living with a roommate who actually did know all things (a lot of things, at least) and was quite adept at pointing out failures in a way that made me feel pretty shitty for not being right. I began to dread pronouncing any discovery of knowledge, for fear that I would get shot down for not knowing the critical flaw or a better way. I also became hypersensative to critical remarks and stressed during situations when I wasn’t performing on a high level. It became easier to restrict myself to activities I already did or just do nothing.

But as the months went by, this became increasingly unacceptable. My friends were out living their dreams (or at least doing what they wanted) and I was stuck inside, barricaded by my fears. I went through several bouts of depression (I guess, never clinically diagnosed/treated) and began to waste large amounts of time browsing the internet, anything to get away from this problem I couldn’t solve. I was searching for a solution that would grant sudden clarity to my situation — I was expecting something to happen to me that would make it all make sense. After all, I was special — whoever was in charge of special people like needed to get on over here and fix it.

That was seriously the attitude I had — I certainly wasn’t wrong, I couldn’t possibly have wasted all these years with this flawed understanding of myself, there had to be something I was missing, some wormhole through which people like myself could jump and get ahead of everyone else, be recognized for our superiority.

Perhaps I was supposed to meet someone randomly (that was my strategy for meeting girls…) perhaps I would go to some place on a whim, receive some correspondence that would save me from my plight.

Looking back now, that attitude seems ridiculous. The world doesn’t give a fat fuck how “special” you think you are. There is no magical system that guides you, the entire effort/reward cycle is a technique used for training pets for obedience. To think of that as anything approaching a replacement for love is flawed. My whole world view was wrong — it had to go. Of course I had heard the saying “you can be anything you want to be” as a kid, but it didn’t really sink in what that meant. I had gotten so used to the appreciation drug that I had forgotten what it meant to do something just because I liked doing it. This world view had to go.

Posted in Self | Leave a comment

Enable WordPress Automatic Updates on a Debian Server

I attempted to get WordPress to update plugins automatically on my Debian server today, and found it a bit less than trivial due to the number of configuration gotchas.

[Update August 2014: Please create the ftpsecure user with -s /usr/sbin/nologin, otherwise it can log in over ssh!]

Assuming you’re running a Debian server (I have 6.0 Squeeze), on which WordPress is installed in /var/www/site/public_html:

1) Install required packages. I used vsftpd.

sudo apt-get install vsftpd openssl

2) Configure vsftpd. I set the following options in /etc/vsftpd.conf

# Enable only local users, no anonymous
anonymous_enable=NO
local_enable=YES
write_enable=YES
local_umask=022

# Allow only our special FTP user
userlist_enable=YES
userlist_deny=NO
userlist_file=/etc/vsftpd.allow_list

# Here's the security trick -- listen only on the local interface to 
# prevent external connections
listen_address=127.0.0.1

# Enable debugging until everything works :)
log_ftp_protocol=YES

3) Add a user for ftp access

# Add the user
sudo useradd ftpsecure -d /var/www -s /usr/sbin/nologin

# Set a password. Since vsftpd is only listening on localhost, the 
# security of this password isn't too important.
sudo passwd ftpsecure

# Add to the vsftpd allow list
echo "ftpsecure" | sudo tee -a /etc/vsftpd.allow_list

4) Turn on vsftpd:

sudo /etc/init.d/vsftpd restart

5) Set permissions for ftpsecure to access your wordpress files. I use access control lists (ACLs), but you could use chown/chmod if you want. These may seem like a bit to permissive — keep in mind that the only way ftpsecure can log in is from your server.

setfacl -m u:ftpsecure:r-x /var/www/site/

# The updater needs access to the root site
setfacl -R -m u:ftpsecure:rwx /var/www/site/public_html
setfacl -R -d -m u:ftpsecure:rwx /var/www/site/public_html

7) Tell WordPress about your FTP credentials. In /var/www/site/public-html/wp-config.php:

define('FTP_HOST', 'localhost');
define('FTP_USER', 'ftpsecure');
define('FTP_PASS', '<password>');

6) Run an update. If WordPress asks for the connection type, choose FTP. Try getting WordPress to update a plugin or the entire site. If it fails, view the log with

tail -f /var/log/vsftpd.log

and run the update again. You’ll be able to tell from the log if there was a permission problem.

7) Disable logging. Remove the line

log_ftp_protocol=YES

in /etc/vsftpd.conf

8) You’re done!

Comment below if these steps didn’t work for you.

For reference, I used:

Posted in Software | Tagged , | 6 Comments

When you need std::remove_const

I ran across an interesting case where I needed to use std::remove_const to ensure a template parameter wasn’t const by default. I had something like this:

const Matrix<4> m4 = Identity;
Vector<3> v3 = project(m4[3]);

With the library I was using, TooN 2.0.0 beta8, this resulted in a compile error. The error stated that when the vector returned from project() was being created, the compiler couldn’t invoke assign to a read only location. A simplified declaration of project() looks as follows:

template <int Size, typename Precision, typename Base>
Vector<Size-1,Precision> project(const Vector<Size, Precision, Base>& v);

What the project() function returns is not important; what is important is the use of the template parameter Precision in both the argument type and the return type. When I invoke operator[] on a const Matrix object, the returned vector’s precision inherits the const.

template <int Rows, int Cols, class Precision>
class Matrix {
...
Vector<Cols, const Precision, Slice> Matrix::operator[](int row) const;
};

When this vector is passed to the project() function above, the function tries to create and return a Vector<3, const double> which can only be initialized with a constexpr. Assigning to it via operator= or a constructor will not work to copy the data from the other vector.

There are several ways one can fix this, all of them involving removing the const qualifier from the Precision type on the returned vector.

It may seem like a simple solution would work:

template <int Size, typename Precision, typename Base, typename P2>
Vector<Size-1, P2> project(const Vector<Size, Precision, Base>& v);

Unfortunately, this requires the function be invoked as project<Size, Precision, Base, P2>(v); which is undesirable.

Solution #1

The first solution is simple, but tedious if you have several functions with similar signatures:

template <int Size, typename Precision, typename Base>
Vector<Size-1, typename std::remove_const<Precision>::type > 
project(const Vector<Size, Precision, Base>& v);

std::remove_const<T>::type is a type expression equal to the original type T, but with any const qualifiers removed. In this way, const double becomes simply double.

Solution #2

Another solution is to prevent the creation of a Vector object with a const precision, the idea that a non-slice vector with const data isn’t very useful — you can’t even construct one properly. Generally the only time you would actually want a vector with const data is when that data is pointing to some already existing area in memory (a slice).

Consider the following toy code for a vector class:

#define DECLARE_TYPES(T) \
    typedef typename std::remove_const<T>::type PlainType; \
    typedef const T ConstPlainType; \
    typedef typename std::remove_const<T>::type& ReferenceType; \
    typedef const T& ConstReferenceType

struct StackBase {
template <int Size, typename P>
class Layout { 
public:
    DECLARE_TYPES(P);
    PlainType data[Size];
};
};

struct SliceBase {
template <int Size, typename P>
class Layout {
public:
    P* data;
};
};

template <int Size, typename P = double, typename B = StackBase >
class Vector : public B::template Layout<Size, P> {
public:
    DECLARE_TYPES(P);
    using B::template Layout<Size, P>::data;

    ConstReferenceType operator[](int i) const { return data[i]; }
    ReferenceType operator[](int i) { return data[i]; }
};

When the Vector object is backed by owned storage (StackBase), the data is declared explicitly to be of a non-const type. Similarly, the return types of operator[] are defined to be the const and non-const reference types. The SliceBase, which handles references to un-owned data, retains the original templated type to allow pointing to constant data.

While this method prevents the creation of Vector objects with const owned data, it also means you don’t have to augment functions that interface with these objects to correct the return type.

Posted in Software | Tagged , | Leave a comment

Correcting Message Order with Courier

Recently I moved some local messages from my machine (previously downloaded with pop3) onto the server so I could use imap. I used Mail.app on Mac OS X 10.5.8 to do this.

For some reason, the messages in this example were uploaded in a way that caused them to be loaded in the wrong order on iOS 5.0.1. Since I run the mailserver myself, I took a look at the message files to see if I could deduce the cause of the issue. I noticed a series of messages on the mail server that looked like this:

1324697191.M91227P15574V000000000000CA00I0004B07D_556.hostname,S=5622:2,S
1324697192.M322096P15574V000000000000CA00I0004B07F_557.hostname,S=225691:2,RS
1324697196.M144018P15574V000000000000CA00I0004B081_558.hostname,S=7702:2,RS
1324697197.M715598P15574V000000000000CA00I0004B083_559.hostname,S=15741:2,S
1324697199.M327587P15574V000000000000CA00I0004B085_560.hostname,S=8744:2,RS

The received times of these messages, in the same order as listed above, are:

01/15/2010
01/09/2009
07/13/2010
02/21/2010
05/06/2010

It turns out that due to the messages in this example having a modification date that doesn’t match their receive timestamp the messages appear in the wrong order on an iOS device, where the mail application assumes the order of the messages it gets from the imap server is already sorted by date. This isn’t a problem with desktop mail clients — they simply fetch all the messages, sort them, and everything is fine. Several google searches on this subject yielded threads where people were trying to get their messages in the correct order and the suggested remedy was “sort them on the client side.”

To fix this, I wrote a perl script script to read the message headers, determine the receive time, and update the file name and modification date to match.

Use the script like this:

perl rename.pl cur/*

When you’re convinced it will do the right thing:

perl rename.pl cur/* --output-dir cur_renamed

After ensuring the rename was correct, I swapped the cur and cur_renamed directories, deleted the courierimapuiddb file, and restarted courier-imap. I also had to quit Mail.app on OS X and delete and re-add the mail account on the iOS device to get the messages to come in in the correct order.

Posted in General | Tagged , , | Leave a comment

Google Authenticator Backup Woes

TL;DR: Google Authenticator doesn’t backup on iOS; before erasing your old device, make sure to re-configure Google Authenticator on your new one.

I use the Google Authenticator app on iOS for 2-factor authentication into Google’s services. Recently, I was transitioning to a new phone after giving my existing one to my mom for Christmas. I did the standard backup -> restore plan which put most of my settings on my new device without issues. Fortunately, before I erased the old device, I made sure all my apps worked, including the authenticator.

Apparently, the data the authenticator app stores is not backed up for whatever reason, which means that instead of being able to generate the keys needed to access my accounts, the authenticator was prompting me to set up a new account. The smart folks over here recommend taking a screenshot of the QR code Google’s site gives you when you set up 2-factor authentication.

Questions:

To Google: Why doesn’t the authenticator back up its data? Seems this could be a nasty surprise for someone.
To Android users: Does this happen on Android as well?

Posted in General | Tagged , | 1 Comment

Cubic Spline Interpolation

Cubic spline interpolation is a simple way to obtain a smooth curve from a set of discrete points (knots). It has both C1 (first derivative) and C2 (second derivative) continuity, enabling it to produce a continuous piecewise function given a set of data points.

From the algorithm detailed here I have implemented a clamped cubic spline class in C++. It is templated on the type of X and Y, allowing for use of scalar or vector types. It requires only that X and Y define the operators +, -, *, and /, and that Y have a constructor that takes a single scalar argument, initializing all elements to the supplied value.

Usage is very simple. For example, to interpolate a 2D location over time, try this:

#import "glm.hpp"
#import <vector>

std::vector<float> times;
std::vector<glm::vec2> points;
times.push_back(0);
points.push_back(glm::vec2(0));
times.push_back(.5f);
points.push_back(glm::vec2(-303, -572));
times.push_back(1);
points.push_back(glm::vec2(-250, -980));

/* Create the spline interpolating the position over time */
Spline<float, glm::vec2> sp(times, points);

/* Compute the interpolated position at time 0.75f */
glm::vec2 value(sp[.75f]);

The code for the spline class is below:

Continue reading

Posted in Computer Vision, Software | Tagged , , , , | 7 Comments