The post A C++ Header Only Arena Allocator appeared first on Dillon Huff.

]]>The linked github repo is a single header file arena allocator. The allocator allocates a single chunk of memory when it is created. The chunk is deallocated when the arena_allocator object is destroyed.

Allocation consists of a incrementing a pointer and returning. In debug mode the allocator will crash with an assert if an allocation that exceeds available memory is requested.

For convenience the allocator includes a templatized allocate function that automatically determines the size of the allocated object and handles casting boilerplate for you.

The post A C++ Header Only Arena Allocator appeared first on Dillon Huff.

]]>The post A C++ Bit Vector Arithmetic Library appeared first on Dillon Huff.

]]>bsim is a header only library that provides arbitrary length bit vectors.

There are many bit vector libraries designed for representing sets, for example std::bitset. Unlike these libraries bsim was designed with hardware simulation in mind. bsim supports bit operations such as "xor", "and", and "or" as well as unsigned and twos complement arithmetic and comparisons.

bsim supports both static and dynamic bit vectors. Static bit vectors, like those provided in std::bitset, are a class template with a template argument for the length of the bit vector. They are useful for applications where the length of a bit vector is known at compile time.

Dynamic bit vectors support the same operations, but they are used when the length of the bit vector is not known at compile time.

- Bitwise logical operators: and, or, nand, nor, xor, not
- Bitwise comparisons: equal and not equal
- Reduction operations: "andr", "orr", "xorr"
- Shifts: left shifts (shl), arithmetic right shifts (ashr), and logical right shifts (lshr).
- Unsigned integer arithmetic: add, subtract, multiply, and divide
- Unsigned integer comparisons: greater, less, greater than or equal, less than or equal
- Signed integer arithmetic: add, subtract, and multiply
- Signed integer comparisons: greater, less, greater than or equal, less than or equal

I am currently working on adding support for signed division as well as signed and unsigned remainder operations.

bsim supports operating on arbitrary length bit vectors, but for operations on bit vectors with less than 65 bits the library uses conditional compilation to native instructions rather than arbitrary length algorithms.

Use of native operations comes at a slight storage cost. For example a 33 bit vector must be stored as 64 bits in order to use 64 bit operations without changing bits in memory beyond the object.

If you want to use static bit vectors then copy the file src/bit_vector.h into your project.

If you want to use dynamic bit vectors then use src/dynamic_bit_vector.h instead.

The post A C++ Bit Vector Arithmetic Library appeared first on Dillon Huff.

]]>The post A C++ 11 Header Only Convenience Function Library appeared first on Dillon Huff.

]]>Having spent several years programming in C++ every day I've had time to build up a library of functions that make programming easier. The focus of this library is on making calls to STL functionality less verbose, wrapping up common STL usage patters like calls to erase after remove, and adding a few functions that I thought were missing.

This library is not dogmatic. The only guiding principles were what I found convenient as I was programming. However, over time two themes emerged.

Lets face it, most of the time when you call an STL function that uses iterators the inputs are the begin and end iterators of the data structure.

As a general rule in any language the most frequently used words should be the shortest. This convenience library includes short functions that take in references to a data structure and operate on the entire thing.

The function calls for sorting, finding maxs and mins, and removing items from collections have short call signatures that don't require use of iterator related functions like begin and end.

Pre-C++ 11 there was no convenient way to return a data structure that had been created in a function as a value. Thanks to move semantics returning data structures as values is no longer a big deal, and this convenience library takes advantage of that.

A very common pattern in searching is to compare objects by a function that generates a value from the items being compared and then compares the generated values. afk wraps up this functionality into functions max_e and min_e.

The result is returned as a value rather than as an iterator.

Copying and selection functions

Delete functions

afk includes functions for performing intersection, union, and difference on vectors and sets.

Chain functions (apply between). Functions that operate on adjacent elements.

The post A C++ 11 Header Only Convenience Function Library appeared first on Dillon Huff.

]]>The post Quantifier Elimination Over Linear Real Arithmetic by Enumerating all Possible Root Orders appeared first on Dillon Huff.

]]>LRA includes all first order formulas whose atomic formulas consist of a linear expression and comparator. For example:

is a formula in linear real arithmetic, as is:

A formula like:

is not in LRA because the term is raised to the power of 2.

Lets eliminate the quantifier from:

Readers who are good at algebra can probably solve this problem in their heads, but to get a sense of what an algorithm for quantifier elimination over LRE would look like lets go through it in detail.

There are two linear expressions of interest:

A plot of these looks like so:

The function is negative at every point from to , is zero at and is positive at every point after .

The function is positive from to , is zero at and is negative at every point after that.

We can express this compactly in a table (called a sign table) like so:

To satisfy our original formula we need a value of where is zero and is positive. We can check if such a value exists by scanning each row of the table and checking if the column for is and the column for is . Row two, corresponding to the point satisfies this condition, so the formula is the quantifier free equivalent of the original formula.

Notice that because we know that both functions involved are lines, and because we know each line's slope the structure of the sign table is completely determined by the *ordering *of the roots of each line.

This example had only one variable, so it was possible to solve each linear equation explicitly for its root, and then use the values of the roots to determine the layout of the sign table, but nothing in our analysis changes if we replace the numerical values of the roots with symbols like and , compute the order in which the roots occur, and then use the ordering of the roots to compute the sign table.

The catch for more complex formulas is that when a problem contains more than one variable there isn't any one correct ordering of the equation's roots since the ordering of the roots depends on the values of the variables.

The solution to this problem is to compute every possible ordering of the roots and compute a sign table for each ordering. We will see how this works in the next example.

Lets eliminate the quantifier from:

This formula contains 2 linear expressions:

Since we are eliminating the quantified variable from our formula lets think of these as linear expressions in :

The first of these expressions is zero when:

And the second has a root when:

For brevity lets write:

Depending on the value of there are 3 possible orderings for these roots:

For each of these three possibilities we can construct a sign table that will break up the axis into intervals along which both of our expressions have constant signs.

For the sign table looks like:

The sign table has 5 intervals. is linear in x, has a slope of 3 in and has a root at , so it is zero at , negative at all points before and positive after . For the table is similar.

For the sign table looks like:

Notice that because we do not need separate intervals for each of them like we did in the case where .

Finally the sign table for is:

Note that given one of our 3 root order constraints we can decide if the original formula is true by table lookup. The problem is solvable if and only if and so it has a solution only if the sign table has a row where the sign of is negative and the sign of is positive or zero.

By inspection we can see that this is only true when , so the only way there is an such that our formula is satisified is if:

which can be simplified to the condition:

simplifying further:

Notice that this last expression is an expression in LRA! In fact all three of our possible root orderings can be written as formulas in linear real arithmetic.

The other crucial point is that since the real numbers are a totally ordered field one of the three orderings must be true, so we can write:

is equivalent to:

Which is equivalent to:

Now for brevity lets write:

So we have:

Now we can distribute F over the disjunction to get:

Then we can distribute the existential quantifier over each formula:

And since does not appear in any of the root order conditions this is just:

But since each of the expressions for and are just logical encodings of the possible root orders, and each root order implies a sign table that we can use to decide whether there is any such that is we can just solve F in each clause of the disjunction via the sign table.

As we already saw in the discussion of sign tables the only root ordering where there is an that makes is the condition , so our formula becomes:

Which simplifies to:

And we have eliminated the quantifier and all occurences of !

Suppose we have a quantifier free formula (QFF) in linear real arithmetic with variables .

The idea of the algorithm is to distribute over a disjunction of every possible root ordering. Then find the truth value of under that ordering. For brevity we will write as

Since the real line is totally ordered one of the possible orders of roots must be true. Suppose is the set of all possible orders, then we can write the formula as:

Distributing F we get:

Distributing the existential quantifier we get:

Now in each conjunction the root ordering holds, so we can evaluate to True or False using the root ordering:

Now the only formulas that appear are the root orderings, , which depend only on and the terms each of which is either or , so we are done.

To shorten the formula we can drop any of the formulas in the disjunction where .

One detail we glossed over is how to use the sign table to evaluate . In both of our examples we could just look at the sign tables and check, but for a computer to do this task we need a more precise procedure.

The idea is to use a recursive algorithm to walk down the formula collecting all intervals in the sign table that satisfy the conditions of the formula. If there is at least one satisfying interval then the formula evaluates to true given the root ordering.

The recursive procedure is as follows:

Where returns the set of all rows of the sign table where linear polynomial has one of the signs in the list .

The complexity of this algorithm is horrifyingly bad. We have to enumerate all possible orderings of roots to eliminate one quantifier so for a formula containing expressions it is approximately for a single quantifier.

Much faster algorithms exist. An early algorithm called the Ferrante-Rakoff method can eliminate all quantifiers from a formula with quantifiers in where is a positive constant.

Later Loos and Weispfenning invented an improved method with a smaller constant . That method is implemented in the computer algebra package redlog.

The post Quantifier Elimination Over Linear Real Arithmetic by Enumerating all Possible Root Orders appeared first on Dillon Huff.

]]>The post Generating Shape Overlap Tests via Real Quantifier Elimination appeared first on Dillon Huff.

]]>http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection

http://stackoverflow.com/questions/22093749/c-plane-sphere-collision-detection

The answers are usually given by human ingenuity, but as the answerer of the first question listed above points out algorithms to solve these kinds of shape intersection problems can be automatically invented by a procedure called *cylindrical algebraic decomposition* (CAD).

CAD is the most popular algorithm used for *real quantifier elimination* (RQE). RQE takes any problem in nonlinear real arithmetic (first order logic where all the atomic formulas are real polynomial equations and inequalities) and spits out a logically equivalent formula with no quantifiers.

To get a feel for RQE here are some formulas and their quantifier free equivalents:

is

is

is

is

This procedure can be used to generate intersection tests for 2 shapes like so: Come up with a logical formula, , that is true when the point is in shape 1. Then come up with a formula, , that is true when the point is in shape 2. To find an intersection test perform quantifier elimination on:

and transliterate the resulting formula into the programming language of your choice.

This method can automatically generate intersection tests for any number of shapes, but before we get to that lets look at an example.

A formula using quantifiers to describe whether a circle centered at point with radius , and a square with bottom left corner at and side length intersect is:

where:

Using the quantifier elimination command in redlog we can produce a new formula that is logically equivalent to the original one, but does not contain or .

Since this formula only uses known values (, , , , , and ) and has no quantifiers it can be transliterated into an executable intersection test in a programming language of the users choice.

After using redlog to eliminate quantifiers we can pretty print the resulting formula as a c++ function:

#include<cmath> bool test( const double r, const double l, const double b, const double d, const double a, const double c ) { return ( ( ( ( ( ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d >= 0.0 ) ) && ( b - d - l <= 0.0 ) ) && ( a - c - r >= 0.0 ) ) && ( a - c - l - r <= 0.0 ) ) || ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d >= 0.0 ) ) && ( b - d - l <= 0.0 ) ) && ( a - c + r >= 0.0 ) ) && ( a - c - l + r <= 0.0 ) ) ) || ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) || ( ( pow( b, 2 ) - 2.0 * b * d + pow( d, 2 ) - pow( r, 2 ) <= 0.0 ) && ( ( ( ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d >= 0.0 ) ) && ( a - c >= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + pow( d, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( b - d - l <= 0.0 ) || ( l * 2.0 * b - 2.0 * d - l >= 0.0 ) ) ) && ( ( a - c - l <= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) || ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d >= 0.0 ) ) && ( a - c - l <= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( b - d - l <= 0.0 ) || ( l * 2.0 * b - 2.0 * d - l >= 0.0 ) ) ) && ( ( a - c >= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + pow( d, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) || ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d - l <= 0.0 ) ) && ( l * 2.0 * b - 2.0 * d - l <= 0.0 ) ) && ( a - c >= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + pow( d, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( a - c - l <= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) || ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d - l <= 0.0 ) ) && ( l * 2.0 * b - 2.0 * d - l <= 0.0 ) ) && ( a - c - l <= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( a - c >= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + pow( d, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) ) ) || ( ( pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) && ( ( ( ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d >= 0.0 ) ) && ( l * 2.0 * b - 2.0 * d - l >= 0.0 ) ) && ( a - c >= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( a - c - l <= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) || ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d >= 0.0 ) ) && ( l * 2.0 * b - 2.0 * d - l >= 0.0 ) ) && ( a - c - l <= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( a - c >= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) || ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d - l <= 0.0 ) ) && ( a - c >= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( b - d >= 0.0 ) || ( l * 2.0 * b - 2.0 * d - l <= 0.0 ) ) ) && ( ( a - c - l <= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) || ( ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d - l <= 0.0 ) ) && ( a - c - l <= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( b - d >= 0.0 ) || ( l * 2.0 * b - 2.0 * d - l <= 0.0 ) ) ) && ( ( a - c >= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) ) ) || ( ( pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) && ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( a - c >= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( a - c - l <= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) || ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( a - c - l <= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( a - c >= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + pow( d, 2 ) + 2.0 * d * l + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) ) ) || ( ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( c, 2 ) + 2.0 * c * l + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) && ( ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d >= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( b - d - l <= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) || ( ( ( ( ( r != 0.0 ) && ( l != 0.0 ) ) && ( b - d - l <= 0.0 ) ) && ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d - 2.0 * b * l + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + 2.0 * d * l + 2.0 * pow( l, 2 ) - pow( r, 2 ) >= 0.0 ) ) && ( ( b - d >= 0.0 ) || ( pow( a, 2 ) - 2.0 * a * c - 2.0 * a * l + pow( b, 2 ) - 2.0 * b * d + pow( c, 2 ) + 2.0 * c * l + pow( d, 2 ) + pow( l, 2 ) - pow( r, 2 ) <= 0.0 ) ) ) ) ) ); }

As you can see, the result isn't pretty. The downside of automatically generated formulas is that there is no human intuition behind them to make them comprehensible.

In theory this method can handle just about any 3D shape. A few 3D shapes that can be handled with fairly compact formulas:

Spheres:

Axis aligned cubes and cuboids:

Axis aligned ellipses:

Below are results for several other shape intersections

RQE is extremely slow. Any algorithm for RQE is at best , though there are specialized algorithms for the linear and quadratic cases that are faster in practice than general methods.

Redlog seems capable of generating intersection tests for 2D shapes, and some simple 3D shape combinations like sphere-cube intersection.

More complicated 3D shapes like cylinders seem out of reach for Redlog since the logical formulas that can be used to represent them have more variables and higher degree polynomials (4+) that are difficult to eliminate.

The post Generating Shape Overlap Tests via Real Quantifier Elimination appeared first on Dillon Huff.

]]>The post G-code Operations MRR Histogram appeared first on Dillon Huff.

]]>To help avoid machine crashes I added a final check before emitting G-code. The system would run a simulation of the G-code, calculate the average material removal rate (in cubic inches per minute) and warn me if it was excessive.

We were cutting 6061 aluminum and I wanted to be extremely conservative since our machine is so wimpy, so I set the system to warn me about anything above 0.6 cubic inches per minute.

After a few very conservative part programs went through the simulator without incident I made some changes to the toolpath generation system to speed things up.

The first G-code program I generated with the new system caused a warning, but in a rush I ignored it, thinking it was probably not too bad. As soon as the program reached the toolpath that produced the warning it crashed.

Below is a histogram showing the MRR for each operation I ran on the mill up to and including the crashing operation (on the far right):

It's a bad idea to ignore warnings!

The post G-code Operations MRR Histogram appeared first on Dillon Huff.

]]>The post How to Write an LLDB Plugin with Python: Customized Stepping Logic appeared first on Dillon Huff.

]]>Custom commands allow you to create custom logic for inspecting the state of the target program during a break. Custom stepping logic allows you to create customized logic to determine how to progress through the target program.

As an example we will create a custom step class, FindVar, that will step through a program until it finds a variable named r1.

import lldb class FindVar: def __init__(self, thread_plan, dict): self.thread_plan = thread_plan self.start_frame = thread_plan.GetThread().GetFrameAtIndex(0) def explains_stop(self, event): res = self.thread_plan.GetThread().GetStopReason() == lldb.eStopReasonTrace return res def should_stop(self, event): frame = self.thread_plan.GetThread().GetFrameAtIndex(0) a_var = frame.FindVariable("r1") if not a_var.IsValid(): print "Havent found r1 yet" return False else: print "Found r1!" self.thread_plan.SetPlanComplete(True) return True def should_step(self): return True

The three crucial methods are explains_stop, should_stop, and should_step.

To understand explains_stop lets look at the output of an ordinary LLDB session. If you run an ordinary LLDB session tracking a program, say a.out, and create a breakpoint at the function main, then run the program you should see output like this:

bash-3.2$ lldb ./a.out (lldb) target create "./a.out" Current executable set to './a.out' (x86_64). (lldb) breakpoint set --n main Breakpoint 1: where = a.out`main + 23 at main.cpp:8, address = 0x0000000100000d77 (lldb) r

The code will hit main immediately and break, spitting out the following info:

Process 18492 launched: './a.out' (x86_64) Process 18492 stopped * thread #1: tid = 0x58329e, 0x0000000100000d77 a.out`main + 23 at main.cpp:8, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100000d77 a.out`main + 23 at main.cpp:8

Notice the text of line 6: stop reason = breakpoint 1. 1. In LLDB every stop has a reason. When the debugger stops it calls each active thread plan's explains_stop method. The first one to return true is the stop reason.

LLDB supports several stop reasons, in the python API the supported stop reasons are:

eStopReasonBreakpoint

eStopReasonException

eStopReasonExec

eStopReasonInstrumentation

eStopReasonInvalid

eStopReasonNone

eStopReasonPlanComplete

eStopReasonSignal

eStopReasonThreadExiting

eStopReasonTrace

eStopReasonWatchpoint

Our example plugin is just supposed to step through the program, so it only explains the stop if the the stop reason is eStopReasonTrace.

In the event that our plan does explain the stop we get to decide whether to return control to the user or continue execution. This decision is made by the should_stop method.

For our plugin we are trying to run the program until a variable named r1 is defined, so we search for a variable named r1 in the current frame. If it exists we return control to the user. If it does not exist we continue execution.

Once we have decided to continue execution our plan has two options. It can resume normal execution, or it can take one step. In our case we want to step through the program one instruction at a time until r1 is defined, so we always return True, saying that we want to take a single step and then stop again.

To use this plugin we first need to create an executable to use as the target. In this example we will use a simple C++ program. First enter this code into a file named contrived.cpp:

#include "contrived.h" int contrived_1(const int l, const int v, const int q, my_value my_v) { int r1 = l - v; int r2 = q*l; if (my_v.useless) { return r1 - r2; } else { return my_v.x + my_v.y + my_v.z - r1*r2; } }

Next create the corresponding contrived.h file:

struct my_value { int x; int y; int z; bool useless; }; int contrived_1(const int l, const int v, const int q, my_value my_v);

Finally create a main.cpp file:

#include <iostream> #include "contrived.h" using namespace std; int main() { int x = 2; int y = 4; int z = 9; bool useless = true; my_value v{x, y, z, useless}; int k = contrived_1(3, 4, -12, v); cout << k << endl; }

With these files created compile them with:

clang++ -g -O0 -std=c++11 contrived.cpp main.cpp

This will create an executable, a.out. With a.out created we can debug it and use our plugin.

In the directory lldb_plugin run the commands:

bash-3.2$ lldb ./a.out (lldb) target create "./a.out" Current executable set to './a.out' (x86_64). (lldb) breakpoint set --n main Breakpoint 1: where = a.out`main + 23 at main.cpp:8, address = 0x0000000100000d77 (lldb) r Process 18568 launched: './a.out' (x86_64) Process 18568 stopped * thread #1: tid = 0x58688d, 0x0000000100000d77 a.out`main + 23 at main.cpp:8, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100000d77 a.out`main + 23 at main.cpp:8 5 using namespace std; 6 7 int main() { -> 8 int x = 2; 9 int y = 4; 10 int z = 9; 11 (lldb) command script import find_var.py (lldb) thread step-scripted -C find_var.FindVar Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Havent found r1 yet Found r1! Process 18568 stopped * thread #1: tid = 0x58688d, 0x0000000100000d00 a.out`contrived_1(l=9, v=16777216, q=1, my_v=(x = 4, y = 2, z = 1606417248, useless = true)) at contrived.cpp:3, queue = 'com.apple.main-thread', stop reason = Python thread plan implemented by class find_var.FindVar. frame #0: 0x0000000100000d00 a.out`contrived_1(l=9, v=16777216, q=1, my_v=(x = 4, y = 2, z = 1606417248, useless = true)) at contrived.cpp:3 1 #include "contrived.h" 2 -> 3 int contrived_1(const int l, const int v, const int q, my_value my_v) { 4 int r1 = l - v; 5 int r2 = q*l; 6 7 if (my_v.useless) {

The post How to Write an LLDB Plugin with Python: Customized Stepping Logic appeared first on Dillon Huff.

]]>The post How to Write an LLDB Plugin with Python: New Commands appeared first on Dillon Huff.

]]>- Print each frame in the stack trace
- For each frame print all arguments and local variables

Place this code in a new directory, say lldb_plugin, in a file named custom_command.py:

import lldb import commands import optparse import shlex def my_cmd(debugger, command, result, internal_dict): target = debugger.GetSelectedTarget() process = target.GetProcess() thread = process.GetSelectedThread() for frame in thread: print str(frame) function = frame.GetFunction() print 'FUNCTION = ', function if frame.IsInlined(): print 'INLINED' else: args = frame.get_arguments() print '# of arguments = ', len(args) for arg in args: print arg vars = frame.get_all_variables() print '# of vars =', len(args) for var in vars: print var def __lldb_init_module(debugger, internal_dict): debugger.HandleCommand('command script add -f custom_command.my_cmd my_cmd') print 'The "my_cmd" python command has been installed and is ready for use.'

This code contains two functions. __lldb_init_module is boilerplate that is used to load the command during an lldb session.

The meat of the command is the my_cmd function. This function takes four arguments, but the main one we will use is debugger. debugger represents the actual debug session, we call its GetSelectedTarget method to get the target, or running program, that we are debugging. From the target we get the running process, and from the process we get the running thread.

Things get interesting inside the thread. We can check if the frame is inlined, and if not we can list all arguments, list all variables and print out information about the function itself.

To use this plugin we first need to create an executable to use as the target. In this example we will use a simple C++ program. First enter this code into a file named contrived.cpp:

#include "contrived.h" int contrived_1(const int l, const int v, const int q, my_value my_v) { int r1 = l - v; int r2 = q*l; if (my_v.useless) { return r1 - r2; } else { return my_v.x + my_v.y + my_v.z - r1*r2; } }

Next create the corresponding contrived.h file:

struct my_value { int x; int y; int z; bool useless; }; int contrived_1(const int l, const int v, const int q, my_value my_v);

Finally create a main.cpp file:

#include <iostream> #include "contrived.h" using namespace std; int main() { int x = 2; int y = 4; int z = 9; bool useless = true; my_value v{x, y, z, useless}; int k = contrived_1(3, 4, -12, v); cout << k << endl; }

With these files created compile them with:

clang++ -g -O0 -std=c++11 contrived.cpp main.cpp

This will create an executable, a.out. With a.out created we can debug it and use our plugin.

In the directory lldb_plugin run the commands:

lldb ./a.out breakpoint set --n contrived_1 r

command script import custom_command.py

After the import you should see:

The "my_cmd" python command has been installed and is ready for use.

Now run the command:

my_cmd

and you should see something like:

frame #0: 0x0000000100000d15 a.out`contrived_1(l=3, v=4, q=-12, my_v=(x = 2, y = 4, z = 9, useless = true)) + 21 at contrived.cpp:4 FUNCTION = SBFunction: id = 0x0000008d, name = contrived_1(int, int, int, my_value), type = contrived_1 # of arguments = 4 (const int) l = 3 (const int) v = 4 (const int) q = -12 (my_value) my_v = (x = 2, y = 4, z = 9, useless = true) # of vars = 4 (const int) l = 3 (const int) v = 4 (const int) q = -12 (my_value) my_v = (x = 2, y = 4, z = 9, useless = true) (int) r1 = 1606579087 (int) r2 = 1 frame #1: 0x0000000100000dc8 a.out`main + 104 at main.cpp:15 FUNCTION = SBFunction: id = 0x00008d35, name = main, type = main # of arguments = 0 # of vars = 0 (int) x = 2 (int) y = 4 (int) z = 9 (bool) useless = true (my_value) v = (x = 2, y = 4, z = 9, useless = true) (int) k = 0 frame #2: 0x00007fff9dca45ad libdyld.dylib`start + 1 FUNCTION = No value # of arguments = 0 # of vars = 0

Full documentation for the LLDB python API can be found here

The post How to Write an LLDB Plugin with Python: New Commands appeared first on Dillon Huff.

]]>The post C++ forever template appeared first on Dillon Huff.

]]>template <int N> struct forever { enum { value = forever<N-1>::value * forever<N-1>::value }; }; enum forever_res { result = forever<1>::value };

Since integer arithmetic wraps this template just expands for all time. On clang the error is pretty neat and well reported:

main.cpp:3:18: fatal error: recursive template instantiation exceeded maximum depth

of 256

enum { value = forever<N-1>::value * forever<N-1>::value };

^

main.cpp:3:18: note: in instantiation of template class 'forever<-255>' requested

here

main.cpp:3:18: note: in instantiation of template class 'forever<-254>' requested

here

main.cpp:3:18: note: in instantiation of template class 'forever<-253>' requested

here

main.cpp:3:18: note: in instantiation of template class 'forever<-252>' requested

here

main.cpp:3:18: note: in instantiation of template class 'forever<-251>' requested

here

main.cpp:3:18: note: (skipping 247 contexts in backtrace; use

-ftemplate-backtrace-limit=0 to see all)

main.cpp:3:18: note: in instantiation of template class 'forever<-3>' requested here

main.cpp:3:18: note: in instantiation of template class 'forever<-2>' requested here

main.cpp:3:18: note: in instantiation of template class 'forever<-1>' requested here

main.cpp:3:18: note: in instantiation of template class 'forever<0>' requested here

main.cpp:6:29: note: in instantiation of template class 'forever<1>' requested here

enum forever_res { result = forever<1>::value };

^

main.cpp:3:18: note: use -ftemplate-depth=N to increase recursive template

instantiation depth

enum { value = forever<N-1>::value * forever<N-1>::value };

^

1 error generated.

The post C++ forever template appeared first on Dillon Huff.

]]>The post C++ __func__ vs __PRETTY_FUNCTION__ appeared first on Dillon Huff.

]]>To see how they work you can copy and paste the following code snippet into a file, say main.cpp, and compile it with:

clang++ -std=c++11 main.cpp

#include <iostream> using namespace std; class myclass { public: string func() const { return __func__; } string pretty_function() const { return __PRETTY_FUNCTION__; } }; class otherclass { public: string func() const { return __func__; } string pretty_function() const { return __PRETTY_FUNCTION__; } }; int main() { cout << __func__ << endl; cout << __PRETTY_FUNCTION__ << endl; myclass c; cout << c.func() << endl; cout << c.pretty_function() << endl; otherclass oc; cout << oc.func() << endl; cout << oc.pretty_function() << endl; return 0; }

When you run it you should see:

main

int main()

func

string myclass::pretty_function() const

func

string otherclass::pretty_function() const

As you can see the major difference is that __PRETTY_FUNCTION__ prints more information. It shows the type signature and containing class of the function it is contained in as well as the name, while __func__ prints only the name.

The post C++ __func__ vs __PRETTY_FUNCTION__ appeared first on Dillon Huff.

]]>