Building a (not so) simple RPN Calculator
Building a (not so) simple RPN Calculator
The full source for the program is available at the end of this post
At work my team has recently started an (optional) team building exercise where we work on a codewars kata once a week, and share our solutions during our team building events on Fridays. For the most part the problems we work on are simple. Although participation is optional, it’s nice to have easy problems that someone who is busy can knock out in a few minutes so that they still get to participate. It also unlocks a lot of space for people to focus on things adjacent to the core problem and get creative.
People express creativity in different ways: Some people enjoy writing the solution in different languages each week, or trying to code golf their solutions as much as possible. One person has created a sort of metagame of looking for ever more creative ways to avoid solving the problem by breaking out of the test harness. For me, it’s an opportunity to pick up one of my favorite forms of artistic expression: Writing the most accursed unhinged implementations of things I can think of.
Our most recent kata was to implement an RPN Calculator and while it may not be the most unhinged code I’ve written, my solution was unhinged enough that I was inspired to write it up so the rest of the world could look on in whatever combination of awe and horror they deem appropriate.
Reverse Polish Notation (RPN)
Reverse Polish Notation (RPN) is a stack based notation for arithmatic operations. It has something of a cult following, especially among the kind of people who have strong sentimental attachments to certain brands of calculators. For our purposes, it’s also a great problem because the implementation is extremely simple.
In an RPN notation expression, each numeric value pushes a value onto a
stack. An operator pops two values off of the stack and then pushes the result
of the binary operation back onto the stack. For example, if we had an
expression like 2 1 1 + * 3 - we’d get a value of 1:
| input | stack | description |
|---|---|---|
| 2 | [2] | push 2 |
| 1 | [1,2] | push 1 |
| 1 | [1,1,2] | push 1 |
| + | [2,2] | pop 1, pop 1, push (1 + 1) |
| * | [4] | pop 2, pop 2, push (2 * 2) |
| 3 | [3,4] | push 3 |
| - | [1] | pop 3, pop 4, push (4 - 3) |
This is a perfect problem for an unhinged solution because it’s simple enough to understand and solve in a straighforward manner that we can put all of our energy into over-complicating things for fun.
Solution Overview
I decided to implement the solution in C, because it allows us to do a lot of creative, if wildly dangerous, things in our solution. For this particular problem I wanted to pull out a technique that has been lurking around in the back of my mind for the last 15 years without much of a concrete use-case: context swapping.
Context swapping is an older part of the POSIX api. It’s deprecated now, and not supported on a lot of platforms, but it does work with GCC on Linux. The idea is that it lets us treat function execution contexts as ordinary data. It’s intended for building cooperative multitasking systems or implementing conccurrency and threading libraries. We’re going to misuse it for flow control.
At a high level, we’re going to treat each item in the RPN stack as a sort of thunk represented by a context. We can pass continuations by passing around pointers to contexts from one thunk to another. Arguments are placed directly into the saved registers that will be loaded when we start executing a context. We’ll dynamically modify the control flow by passing around continuations as we encounter parts of our RPN expression. When we get to the last operator in the expression we’ll print out the result of the final computation and then exit.
This is a toy program and so we won’t concern ourselves with freeing memory or anything else you’d want to do in a real program- in fact this entire program is something you wouldn’t want to do in a real program, but it’s still fun.
Part 1: Parsing
The first thing that we need to do is tokenize our input string and get it into
a form that we can use later. We’ll store the RPN program as a doubly linked
list of tokens that can be either values or operators. Values are stored as a
double, and operators are stored as a character: '+', '-', '*', '/'. We
could have mapped these to a number or something, but using the characters makes
debugging easier because we can trivially print out a human readable expression.
Since this is just a demo we won’t worry too much about safety or memory leaks. Otherwise, the parsing step of our application is pretty normal and should look familiar to anyone who has done a bit of C (or parsing in similar languages for that matter). We’ll start by defining a type to hold our parsed token:
Parser Types
// You can put these macros at the top of your source file,
// or in a header file if you prefer.
#define INPUT_TYPE_OPERATOR 0
#define INPUT_TYPE_VALUE 1
typedef struct {
uint8_t input_type;
union {
double value;
char operator;
} input_token;
} rpn_input_t;An rpn_input_t value stores a single token, along with a tag. A 0 value in
input_type tells us we’re dealing with an operator, and we should access the
operator field of our union. A 1 value tells us we have a numeric value, and
should access the value field instead. We’ve also added a couple of macros to
help make the tag values more memorable.
Since our calculator will presumably need to deal with more than just a single constant value, let’s also define a struct to let us keep a list of them. Since RPN evaluation works with a stack, it’s easy to foresee that we might need to go backwards in the list, so let’s be proactive and make this a doubly linked list.
If you don’t want to write a linked list from scratch, POSIX has one you can use
by importing <sys/queue.h>. It’s also fairly straightforward to write your own
more generic linked list structure by putting the next and prev pointers in
their own struct that you can embed inside of some other struct. Using an ad-hoc
list is fine for our purposes.
typedef struct token_list {
rpn_input_t *token;
struct token_list *next;
struct token_list *prev;
} token_list_t;While we’re at it, let’s also go ahead and add some helper functions to wlrk with our list. We don’t need a complete implementation here, but we’ll want a function that let’s us go to the last element of a list, and one that let’s us append a new token to the end of the list:
token_list_t* token_list_last(token_list_t* list_head) {
if (NULL == list_head) {
return NULL;
}
while (NULL != list_head->next) {
list_head = list_head->next;
}
return list_head;
}
token_list_t* append_token_list(token_list_t *list_head, rpn_input_t *token) {
token_list_t *head = list_head;
token_list_t *last = malloc(sizeof(token_list_t));
last->token = token;
last->next = 0;
last->prev = 0;
if (NULL == list_head) {
return last;
}
while (NULL != head->next) { head = head->next; }
head->next = last;
last->prev = head;
return list_head;
}Parsing a Single Element
Now that we have our types defined, let’s move on to our parsing. We’ll start by parsing an individual element of our RPN expression.
If we have a string that represents an individual token, we can parse it into an
rpn_input_t easily by looking at the first character of the token. Our
operators are all single characters, so the first character is sufficient to
identiy the correct operator. Otherwise, we assume we’re dealing with a
value. The tokenization process will strip out any spaces. If someone passes in
a null token, or some non-numeric values, well, you should never do this in
production anyway.
int parse_rpn_input_token(const char *in_token, rpn_input_t *out_token) {
out_token->input_type = INPUT_TYPE_OPERATOR;
switch (*in_token) {
case '+': { out_token->input_token.operator = OPERATOR_PLUS; return 0; }
case '-': { out_token->input_token.operator = OPERATOR_MINUS; return 0; }
case '*': { out_token->input_token.operator = OPERATOR_MULT; return 0; }
case '/': { out_token->input_token.operator = OPERATOR_DIV; return 0; }
default: {
double val;
out_token->input_type = INPUT_TYPE_VALUE;
sscanf(in_token,"%lf", &val);
out_token->input_token.value = val;
return 0;
}
}
}Parsing an RPN Expression
Now that we have a way to parse individual tokens, we can move on to parsing the
entire RPN expression. Thankfully most of the work is done for us with
strtok_r. If you haven’t written a lot of C before, one of the quirks is that
you call this function the first time with the string you want to start
tokenizing. For subsequent calls you pass in NULL to tell the function you
want to continue with the string you’ve already started tokenizing. Eventually
we’ll get back a NULl value when there aren’t any tokens left.
token_list_t* parse_rpn(char *restrict input) {
char *saveptr;
char *tokptr;
token_list_t *parsed_tokens = 0;
tokptr = strtok_r(input, " ", &saveptr);
while (NULL != tokptr) {
rpn_input_t *tok = malloc(sizeof(rpn_input_t));
parse_rpn_input_token(tokptr, tok);
parsed_tokens = append_token_list(parsed_tokens, tok);
tokptr = strtok_r(NULL, " ", &saveptr);
}
return parsed_tokens;
}For each token that we get, we use parse_rpn_input_token to get a parsed token
value, and we add tha into our overall list of parsed tokens. When we’re done,
we’re ready to move on and start evaluating the expression.
Part 2: Executing a Token list
Before we start working on a completely unhinged version of program, let’s take a moment to build a more traditional implementation. This will let us have something sensible we can test against, and it’ll help us see the overall outline of how our calculator should work so that we can better understand the much more confusing version later.
To start, we’ll want an easy way to evaluate an operation. Let’s add a small helper. We can re-use this later in our second implementation.
double run_operation(double a, double b, char op) {
switch(op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
default: return a / b;
}
}We’ll also need to add some helper functions to make it easier for us to treat
our token_list_t like a stack. Let’s write a pair of functions so we can push
and pop values:
token_list_t* pop_token_list(token_list_t *token_list, rpn_input_t** out) {
if (NULL == token_list) { return NULL; }
*out = token_list->token;
return token_list->next;
}
token_list_t* push_token_list(token_list_t *token_list, rpn_input_t* token) {
token_list_t *node = malloc(sizeof(token_list_t));
node->next = token_list;
node->prev = 0;
node->token = token;
return node;
}Finally, we can write our simple interpreter. To do this we’ll walk through our list of tokens. Whenever we encounter an ordinary value, we’ll push it onto a new stack. When we encounter an operator, we’ll pop two values off the stack and use them as operands, then push the result back onto the stack. When we get to the end of the list of tokens we’ll return the last value we computed.
double execute_token_list(token_list_t* token_list) {
double operation_result = 0;
rpn_input_t *current_token = 0;
token_list_t *value_stack = NULL;
while (NULL != token_list) {
token_list = pop_token_list(token_list, ¤t_token);
if (INPUT_TYPE_VALUE == current_token->input_type) {
value_stack = push_token_list(value_stack, current_token);
} else {
char operation = current_token->input_token.operator;
rpn_input_t *operand1 = 0;
rpn_input_t *operand2 = 0;
rpn_input_t *result_input = malloc(sizeof(rpn_input_t));
value_stack = pop_token_list(value_stack, &operand2);
value_stack = pop_token_list(value_stack, &operand1);
double op1 = operand1->input_token.value;
double op2 = operand2->input_token.value;
operation_result = run_operation(op1, op2, operation);
result_input->input_type = INPUT_TYPE_VALUE;
result_input->input_token.value = operation_result;
value_stack = push_token_list(value_stack, result_input);
}
}
return operation_result;
}If you want to run this before moving on, this is a good time to add a main
function. The example also includes a list of includes that you should add at
the top of your file:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
// include your other functions here
int main(int argc, char** argv) {
char *raw_input = NULL;
size_t input_size = 0;
if (-1 == getline(&raw_input, &input_size, stdin)) {
printf("no input\n");
return 0;
}
token_list_t *parsed_tokens = parse_rpn(raw_input);
printf("traditional parser: %g\n", execute_token_list(parsed_tokens));
return 0;
}Part 3: Getting Unhinged
Now that we have a normal interpreter, let’s move onto the unhinged version. The core idea for this approach is that instead of writing a loop that iterates through each token and computes the value, we’ll turn each token into a context that will push values into registers for the next stage of computation, then swap program flow over to it.
The Basics of Contexts
The only real trick to the way our program works is to know about the
makecontext and swapcontext functions that are defined in <ucontext.h> and
a willingness to dig into opaque platform specific values defined in
<sys/ucontext.h>. In order to help you follow along, let’s start with a quick
primer on contexts.
A ucontext_t value represents the execution context of a function. It has all
of the information needed to start executing a function, including the stack, a
list of registers to to restore and their values, and a pointer to a context
that we should start executing when the current context is finished running.
We can construct a context that will begin executing some function as in the example:
// create a new context value
ucontext_t ctx;
// allocate stack space and zero it out
char *stack = malloc(STACK_SIZE);
memset(stack, 0, STACK_SIZE);
// initiailize the context
getcontext(&ctx);
// Set up the stack
ctx.uc_stack.ss_sp = stack;
ctx.uc_stack.ss_size = STACK_SIZE;
// If uc_link is set, we'll start executing it when the ctx exits
ctx.uc_link = &the_next_context;
// Initialize platform specific registers
ctx.uc_mcontext.gregs[REG_RDI] = (uint64_t)0x123;
// create the context and point it at func, which takes no arguments
makecontext(&ctx, func, 0);Once we have a context, we can begin executing it by calling swapcontext. To
do that, we’ll need to also create another context variable that represents the
current point in the program that we can pick up from when the context
exits. Here’s an example:
// No need to initialize this, swapcontext will handle that
ucontext_t parent_context;
// Swap control over the ctx
swapcontext(&parent_context, &ctx);A Handful of Contexts
Unlike the earlier example where we had a few fixed contexts, for our RPN calculator we’ll need to build up a list of contexts dynamically based on our parsed tokens. We’ll save the construction of the list for later, but for now let’s define a new doubly linked list of contexts. We’ll also add a field to help us keep track of whether a particular context is associated with a value or an operator.
typedef struct rpn_context_list {
ucontext_t ctx;
uint8_t ctx_type;
struct rpn_context_list *next;
struct rpn_context_list *prev;
} rpn_context_list_t;While we’re here, let’s add a helper function that will let us search a list for the next operator in a context list. It’ll be clear why we need this later on.
rpn_context_list_t* next_operator_ctx(rpn_context_list_t *list) {
while(NULL != list) {
if (list->ctx_type == INPUT_TYPE_OPERATOR) { return list; }
list = list->next;
}
return list;
}Contexts for Values
Now that we understand contexts and we have a data structure defined to store
them, let’s start work on constructing individual contexts. First, we’ll need to
define the function that the context should start running. makecontext allows
us to pass in ordinary function arguments. This will use the normal platform
calling conventions to pass arguments using registers and the stack. We can also
put values directly into the stack by writing into our
context.uc_stack.ss_sp. For our implementation, we’ll pass values using
registers.
You have to be careful when using registers with contexts. The ABI defines what registers are saved and which ones are clobbered during a function call. You can only use caller-saved registers, and even those could be clobbered if you call any other functions before saving a copy of the register values.
void value_func() {
register uint64_t r_val asm("rdi");
register uint64_t r_ctx_ptr asm("r8");
register uint64_t r_reg_offset asm("rdx");
register uint64_t r_ctx_next asm("rsi");
ucontext_t ret;
uint64_t val = r_val;
ucontext_t* ctx = (ucontext_t*)r_ctx_ptr;
ucontext_t* next_ctx = (ucontext_t*)r_ctx_next;
uint64_t register_offset = r_reg_offset;
ctx->uc_mcontext.gregs[register_offset] = val;
swapcontext(&ret, next_ctx);
};Our value_func pulls 4 arguments out of registers. You’ll notice that one of
the first things we do is take a copy of each of the register values into an
ordinary stack-allocated variable. Otherwise any functions we call (including
calling printf to debug our program) could clobber the registers.
Aside from saving a copy of the register values, this function doesn’t do
much. We only have a single value, so there’s not much we can actually
calculate. Instead, we push the value we’re getting out of rdi into a register
of some other context. The context we want to push the register to, and the
register itself, are both passed into us. Finally, we swap control over to some
new context that as passed in through rsi.
This function alone doesn’t do us much good though. We need to create a new context that will start executing the function. To do that, let’s add a helper function that will take the value for the value node and initialize a new context. We don’t yet know where we need to push the value, or what context we should enter next, so we’ll leave those registers unset. This is perfectly fine since we’re not going to execute the context until we have that information.
ucontext_t mk_value_context(double val) {
ucontext_t ctx;
char *stack = malloc(STACK_SIZE);
getcontext(&ctx);
memset(stack, 0, STACK_SIZE);
ctx.uc_stack.ss_sp = stack;
ctx.uc_stack.ss_size = STACK_SIZE;
ctx.uc_mcontext.gregs[REG_RDI] = (uint64_t)val;
makecontext(&ctx, value_func, 0);
return ctx;
}Contexts for Operators
Operators contexts need to do quite a bit more work than value contexts. At a high level, our operator context needs to do a few things:
- Create a new “join” context that represents the actual computation
- Find the value contexts for the operands to our computation
- Set the appropriate registers for the join and value contexts
- Begin executing the first operand context
As before, we’ll accept arguments to our function using registers. In this case,
we only need two arguments. We’ll pass the operator token in rdi and we’ll
pass a pointer to the current rpn_context_list_t node in r8.
After saving a copy of our register values on the stack, we’ll create a new context and a stack for that context. We’ll use the pointer to the current node as a starting point so that we can go backwards to get to the two previous nodes. Those are the operands we’ll need to execute. Finally, we’ll construct our new contexts and swap into the first operand:
void operator_func() {
register uint64_t r_op asm("rdi");
register uint64_t r_ctx_ptr asm("r8");
char operator = (char)r_op;
rpn_context_list_t *ctx_list = (rpn_context_list_t*)r_ctx_ptr;
char *stack = malloc(STACK_SIZE);
ucontext_t *join_ctx = malloc(sizeof(ucontext_t));
rpn_context_list_t *arg1 = ctx_list->prev->prev;
rpn_context_list_t *arg2 = ctx_list->prev;
ucontext_t ret;
rpn_context_list_t *prev_ptr = 0;
if (ctx_list && ctx_list->prev && ctx_list->prev->prev) {
prev_ptr = ctx_list->prev->prev->prev;
}
getcontext(join_ctx);
join_ctx->uc_stack.ss_sp = stack;
join_ctx->uc_stack.ss_size = STACK_SIZE;
join_ctx->uc_mcontext.gregs[REG_RDX] = (uint64_t)operator;
join_ctx->uc_mcontext.gregs[REG_RSI] = (uint64_t)prev_ptr;
join_ctx->uc_mcontext.gregs[REG_R9] = (uint64_t)ctx_list->next;
makecontext(join_ctx, join_func, 0);
arg1->ctx.uc_mcontext.gregs[REG_R8] = (uint64_t)(join_ctx);
arg1->ctx.uc_mcontext.gregs[REG_RDX] = (uint64_t)(REG_RDI);
arg1->ctx.uc_mcontext.gregs[REG_RSI] = (uint64_t)&(arg2->ctx);
arg2->ctx.uc_mcontext.gregs[REG_R8] = (uint64_t)(join_ctx);
arg2->ctx.uc_mcontext.gregs[REG_RDX] = (uint64_t)(REG_R8);
arg2->ctx.uc_mcontext.gregs[REG_RSI] = (uint64_t)(join_ctx);
swapcontext(&ret, &(arg1->ctx));
}You’ll notice in this code that we’re setting up our join_ctx context to call
out to a function we haven’t defined yet, join_fun. Let’s take a look at it
now.
The Join Function
The join function is the core of our application. It both performs the
arithmetic to compute our answer and modifies the list of contexts to ensure
that we’re executing things correctly. The function works by taking the two
operand values that each of the value contexts pushed into it’s registers, along
with the operator pushed into rdx by the operator function. It calls the same
run_operation function we used in our simple implementation, but this time it
creates a new value context to hold the result.
Once we have a new value context, we need to rewire the list of contexts that
we’re working against so that our new value replaces the operator and operands
we’ve just computed. We do that by adjusting the prev and next pointers for
the values before and after the nodes we’ve just used.
Finally, if we have another operator that we need to evaluate we pass control onto it’s context. Otherwise, we can print our answer to the screen and exit the program.
void join_func() {
register uint64_t r_a asm("rdi");
register uint64_t r_b asm("r8");
register uint64_t r_op asm("rdx");
register uint64_t r_prev asm("rsi");
register uint64_t r_next asm("r9");
double a = (double)r_a;
double b = (double)r_b;
char op = r_op;
rpn_context_list_t *prev = (rpn_context_list_t*)r_prev;
rpn_context_list_t *next = (rpn_context_list_t*)r_next;
double result = run_operation(a,b,op);
ucontext_t result_ctx = mk_value_context(result);
ucontext_t ret;
rpn_context_list_t *node = malloc(sizeof(rpn_context_list_t));
node->ctx = result_ctx;
node->prev = prev;
node->next = next;
node->ctx_type = INPUT_TYPE_VALUE;
if (NULL != next) {
next->prev = node;
}
rpn_context_list_t *next_exec_node = next_operator_ctx(node);
if (NULL != prev) { prev->next = node; }
if (NULL != next_exec_node) {
swapcontext(&ret, &(next_exec_node->ctx));
}
printf("%g\n", result);
exit(0);
}Constructing Operator Contexts
Although the work we need to do in our operator and join contexts is significantly more complex than what we needed to do in our value context, creating a new operator context is still straightforward. This function needs to take the operator we want to run, and the current element of the context list. From there it can create a new context and set the relevant registers so we’re ready to start executing:
ucontext_t mk_operator_context(char op, rpn_context_list_t *rpn_ctx_ptr) {
ucontext_t ctx;
char *stack = malloc(STACK_SIZE);
rpn_context_list_t *next_operator = next_operator_ctx(rpn_ctx_ptr);
getcontext(&ctx);
memset(stack, 0, STACK_SIZE);
ctx.uc_stack.ss_sp = stack;
ctx.uc_stack.ss_size = STACK_SIZE;
ctx.uc_mcontext.gregs[REG_RDI] = (uint64_t)op;
ctx.uc_mcontext.gregs[REG_R8] = (uint64_t)next_operator;
makecontext(&ctx, operator_func, 0);
return ctx;
}Creating a Context List
Now that we can create our individual contexts, we need to create an overall list of contexts. We can do this using our already created token parser. In this example we’re working from the end of the token list backwards, incrementally creating a new value or operator context depending on the underlying token type.
rpn_context_list_t* mk_rpn_context_list(token_list_t *tokens) {
token_list_t *last_token = tokens;
token_list_t *current_token = 0;
rpn_context_list_t *ctx_list = 0;
rpn_context_list_t *next_ctx_list = 0;
last_token = token_list_last(tokens);
current_token = last_token;
while(NULL != current_token) {
ctx_list = malloc(sizeof(rpn_context_list_t));
if(INPUT_TYPE_OPERATOR == current_token->token->input_type) {
ctx_list->ctx_type = INPUT_TYPE_OPERATOR;
ctx_list->next = next_ctx_list;
ctx_list->prev = 0;
if(NULL != next_ctx_list) {
next_ctx_list->prev = ctx_list;
}
ctx_list->ctx = mk_operator_context(current_token->token->input_token.operator, ctx_list);
} else {
ctx_list->ctx_type = INPUT_TYPE_VALUE;
ctx_list->next = next_ctx_list;
ctx_list->prev = 0;
if(NULL != next_ctx_list) {
next_ctx_list->prev = ctx_list;
}
ctx_list->ctx = mk_value_context(current_token->token->input_token.value);
}
next_ctx_list = ctx_list;
current_token = current_token->prev;
}
return next_ctx_list;
}Running Our Context Execution Machine
Now that we can create a list of contexts, we can update our main function to
start executing our new context based evaluator:
int main(int argc, char** argv) {
ucontext_t main_ctx;
char *raw_input = NULL;
size_t input_size = 0;
if (-1 == getline(&raw_input, &input_size, stdin)) {
printf("no input\n");
return 0;
}
token_list_t *parsed_tokens = parse_rpn(raw_input);
printf("traditional parser: %g\n", execute_token_list(parsed_tokens));
rpn_context_list_t* ctx_list = mk_rpn_context_list(parsed_tokens);
rpn_context_list_t* first_operator_context = next_operator_ctx(ctx_list);
swapcontext(&main_ctx, &first_operator_context->ctx);
return 0;
}You’ll notice that instead of starting to execute at the first node we skip to the first operator node. If you look back at our definition of it’s clear why this has to be the case. Our operator context is responsible for populating the registers in the value context. If we try to run a value context outside of an operator context, we won’t have a valid join context to push a value into, nor a valid join context pointer to swap into.
Appendix A: Complete Source
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <ucontext.h>
#include <sys/ucontext.h>
#define INPUT_TYPE_OPERATOR 0
#define INPUT_TYPE_VALUE 1
#define OPERATOR_PLUS '+'
#define OPERATOR_MINUS '-'
#define OPERATOR_MULT '*'
#define OPERATOR_DIV '/'
#define STACK_SIZE 655360 // 640k out to be enough for anyone
typedef struct {
uint8_t input_type;
union {
double value;
char operator;
} input_token;
} rpn_input_t;
typedef struct token_list {
rpn_input_t *token;
struct token_list *next;
struct token_list *prev;
} token_list_t;
typedef struct rpn_context_list {
ucontext_t ctx;
uint8_t ctx_type;
struct rpn_context_list *next;
struct rpn_context_list *prev;
} rpn_context_list_t;
token_list_t* token_list_last(token_list_t* list_head) {
if (NULL == list_head) {
return NULL;
}
while (NULL != list_head->next) {
list_head = list_head->next;
}
return list_head;
}
double run_operation(double a, double b, char op) {
switch(op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
default: return a / b;
}
}
rpn_context_list_t* next_operator_ctx(rpn_context_list_t *list) {
while(NULL != list) {
if (list->ctx_type == INPUT_TYPE_OPERATOR) { return list; }
list = list->next;
}
return list;
}
token_list_t* pop_token_list(token_list_t *token_list, rpn_input_t** out) {
if (NULL == token_list) { return NULL; }
*out = token_list->token;
return token_list->next;
}
token_list_t* push_token_list(token_list_t *token_list, rpn_input_t* token) {
token_list_t *node = malloc(sizeof(token_list_t));
node->next = token_list;
node->prev = 0;
node->token = token;
return node;
}
double execute_token_list(token_list_t* token_list) {
double operation_result = 0;
rpn_input_t *current_token = 0;
token_list_t *value_stack = NULL;
while (NULL != token_list) {
token_list = pop_token_list(token_list, ¤t_token);
if (INPUT_TYPE_VALUE == current_token->input_type) {
value_stack = push_token_list(value_stack, current_token);
} else {
char operation = current_token->input_token.operator;
rpn_input_t *operand1 = 0;
rpn_input_t *operand2 = 0;
rpn_input_t *result_input = malloc(sizeof(rpn_input_t));
value_stack = pop_token_list(value_stack, &operand2);
value_stack = pop_token_list(value_stack, &operand1);
double op1 = operand1->input_token.value;
double op2 = operand2->input_token.value;
operation_result = run_operation(op1, op2, operation);
result_input->input_type = INPUT_TYPE_VALUE;
result_input->input_token.value = operation_result;
value_stack = push_token_list(value_stack, result_input);
}
}
return operation_result;
}
void value_func() {
register uint64_t r_val asm("rdi");
register uint64_t r_ctx_ptr asm("r8");
register uint64_t r_reg_offset asm("rdx");
register uint64_t r_ctx_next asm("rsi");
ucontext_t ret;
uint64_t val = r_val;
ucontext_t* ctx = (ucontext_t*)r_ctx_ptr;
ucontext_t* next_ctx = (ucontext_t*)r_ctx_next;
uint64_t register_offset = r_reg_offset;
ctx->uc_mcontext.gregs[register_offset] = val;
swapcontext(&ret, next_ctx);
};
ucontext_t mk_value_context(double val) {
ucontext_t ctx;
char *stack = malloc(STACK_SIZE);
getcontext(&ctx);
memset(stack, 0, STACK_SIZE);
ctx.uc_stack.ss_sp = stack;
ctx.uc_stack.ss_size = STACK_SIZE;
ctx.uc_mcontext.gregs[REG_RDI] = (uint64_t)val;
makecontext(&ctx, value_func, 0);
return ctx;
}
void join_func() {
register uint64_t r_a asm("rdi");
register uint64_t r_b asm("r8");
register uint64_t r_op asm("rdx");
register uint64_t r_prev asm("rsi");
register uint64_t r_next asm("r9");
double a = (double)r_a;
double b = (double)r_b;
char op = r_op;
rpn_context_list_t *prev = (rpn_context_list_t*)r_prev;
rpn_context_list_t *next = (rpn_context_list_t*)r_next;
double result = run_operation(a,b,op);
ucontext_t result_ctx = mk_value_context(result);
ucontext_t ret;
rpn_context_list_t *node = malloc(sizeof(rpn_context_list_t));
node->ctx = result_ctx;
node->prev = prev;
node->next = next;
node->ctx_type = INPUT_TYPE_VALUE;
if (NULL != next) {
next->prev = node;
}
rpn_context_list_t *next_exec_node = next_operator_ctx(node);
if (NULL != prev) { prev->next = node; }
if (NULL != next_exec_node) {
swapcontext(&ret, &(next_exec_node->ctx));
}
printf("%g\n", result);
exit(0);
}
void operator_func() {
register uint64_t r_op asm("rdi");
register uint64_t r_ctx_ptr asm("r8");
char operator = (char)r_op;
rpn_context_list_t *ctx_list = (rpn_context_list_t*)r_ctx_ptr;
char *stack = malloc(STACK_SIZE);
ucontext_t *join_ctx = malloc(sizeof(ucontext_t));
rpn_context_list_t *arg1 = ctx_list->prev->prev;
rpn_context_list_t *arg2 = ctx_list->prev;
ucontext_t ret;
rpn_context_list_t *prev_ptr = 0;
if (ctx_list && ctx_list->prev && ctx_list->prev->prev) {
prev_ptr = ctx_list->prev->prev->prev;
}
getcontext(join_ctx);
join_ctx->uc_stack.ss_sp = stack;
join_ctx->uc_stack.ss_size = STACK_SIZE;
join_ctx->uc_mcontext.gregs[REG_RDX] = (uint64_t)operator;
join_ctx->uc_mcontext.gregs[REG_RSI] = (uint64_t)prev_ptr;
join_ctx->uc_mcontext.gregs[REG_R9] = (uint64_t)ctx_list->next;
makecontext(join_ctx, join_func, 0);
arg1->ctx.uc_mcontext.gregs[REG_R8] = (uint64_t)(join_ctx);
arg1->ctx.uc_mcontext.gregs[REG_RDX] = (uint64_t)(REG_RDI);
arg1->ctx.uc_mcontext.gregs[REG_RSI] = (uint64_t)&(arg2->ctx);
arg2->ctx.uc_mcontext.gregs[REG_R8] = (uint64_t)(join_ctx);
arg2->ctx.uc_mcontext.gregs[REG_RDX] = (uint64_t)(REG_R8);
arg2->ctx.uc_mcontext.gregs[REG_RSI] = (uint64_t)(join_ctx);
swapcontext(&ret, &(arg1->ctx));
}
ucontext_t mk_operator_context(char op, rpn_context_list_t *rpn_ctx_ptr) {
ucontext_t ctx;
char *stack = malloc(STACK_SIZE);
rpn_context_list_t *next_operator = next_operator_ctx(rpn_ctx_ptr);
getcontext(&ctx);
memset(stack, 0, STACK_SIZE);
ctx.uc_stack.ss_sp = stack;
ctx.uc_stack.ss_size = STACK_SIZE;
ctx.uc_mcontext.gregs[REG_RDI] = (uint64_t)op;
ctx.uc_mcontext.gregs[REG_R8] = (uint64_t)next_operator;
makecontext(&ctx, operator_func, 0);
return ctx;
}
rpn_context_list_t* mk_rpn_context_list(token_list_t *tokens) {
token_list_t *last_token = tokens;
token_list_t *current_token = 0;
rpn_context_list_t *ctx_list = 0;
rpn_context_list_t *next_ctx_list = 0;
last_token = token_list_last(tokens);
current_token = last_token;
while(NULL != current_token) {
ctx_list = malloc(sizeof(rpn_context_list_t));
if(INPUT_TYPE_OPERATOR == current_token->token->input_type) {
ctx_list->ctx_type = INPUT_TYPE_OPERATOR;
ctx_list->next = next_ctx_list;
ctx_list->prev = 0;
if(NULL != next_ctx_list) {
next_ctx_list->prev = ctx_list;
}
ctx_list->ctx = mk_operator_context(current_token->token->input_token.operator, ctx_list);
} else {
ctx_list->ctx_type = INPUT_TYPE_VALUE;
ctx_list->next = next_ctx_list;
ctx_list->prev = 0;
if(NULL != next_ctx_list) {
next_ctx_list->prev = ctx_list;
}
ctx_list->ctx = mk_value_context(current_token->token->input_token.value);
}
next_ctx_list = ctx_list;
current_token = current_token->prev;
}
return next_ctx_list;
}
int parse_rpn_input_token(const char *in_token, rpn_input_t *out_token) {
out_token->input_type = INPUT_TYPE_OPERATOR;
switch (*in_token) {
case '+': { out_token->input_token.operator = OPERATOR_PLUS; return 0; }
case '-': { out_token->input_token.operator = OPERATOR_MINUS; return 0; }
case '*': { out_token->input_token.operator = OPERATOR_MULT; return 0; }
case '/': { out_token->input_token.operator = OPERATOR_DIV; return 0; }
default: {
double val;
out_token->input_type = INPUT_TYPE_VALUE;
sscanf(in_token,"%lf", &val);
out_token->input_token.value = val;
return 0;
}
}
}
token_list_t* append_token_list(token_list_t *list_head, rpn_input_t *token) {
token_list_t *head = list_head;
token_list_t *last = malloc(sizeof(token_list_t));
last->token = token;
last->next = 0;
last->prev = 0;
if (NULL == list_head) {
return last;
}
while (NULL != head->next) { head = head->next; }
head->next = last;
last->prev = head;
return list_head;
}
void print_token_list(token_list_t *list_head) {
if (NULL == list_head) {
return;
}
if (INPUT_TYPE_OPERATOR == list_head->token->input_type) {
printf("%c", list_head->token->input_token.operator);
} else {
printf("%g", list_head->token->input_token.value);
}
if (NULL != list_head->next) {
printf(" ");
return (print_token_list(list_head->next));
}
}
token_list_t* parse_rpn(char *restrict input) {
char *saveptr;
char *tokptr;
token_list_t *parsed_tokens = 0;
tokptr = strtok_r(input, " ", &saveptr);
while (NULL != tokptr) {
rpn_input_t *tok = malloc(sizeof(rpn_input_t));
parse_rpn_input_token(tokptr, tok);
parsed_tokens = append_token_list(parsed_tokens, tok);
tokptr = strtok_r(NULL, " ", &saveptr);
}
return parsed_tokens;
}
int main(int argc, char** argv) {
ucontext_t main_ctx;
char *raw_input = NULL;
size_t input_size = 0;
if (-1 == getline(&raw_input, &input_size, stdin)) {
printf("no input\n");
return 0;
}
token_list_t *parsed_tokens = parse_rpn(raw_input);
printf("traditional parser: %g\n", execute_token_list(parsed_tokens));
rpn_context_list_t* ctx_list = mk_rpn_context_list(parsed_tokens);
rpn_context_list_t* first_operator_context = next_operator_ctx(ctx_list);
swapcontext(&main_ctx, &first_operator_context->ctx);
return 0;
}