Lua is a dynamically typed language, with only a small selection of primitive types. Any aggregate or otherwise complex types must use tables (i.e., dictionaries/associative arrays) in some form, which will significantly impact the performance of field/method access as well as the efficiency of data storage (and thus cache usage). LuaJIT’s foreign function interface (FFI) let’s us work around those limitations by offering us the ability to use C declarations to define new types with much greater control and efficiency. In this blog post, I’ll share how, for my Worldbuilder project, I used the FFI to implement a fairly performant fixed point number type. Public domain source code can be downloaded here.

The first step is to use the FFI to declare a C `struct`

which will represent our new type and store its data. We cannot simply use the primitive type directly, because LuaJIT does not allow us to attach metatables to primitive types. Therefore, wrapping the primitive value in a named `struct`

grants us the power afforded by metatables. It also improves the clarity of diagnostic messages for erroneous type conversions and such, by assigning the type a distinct name. For this example, we’ll assume that our underlying storage is a 32-bit integer. (Aside from implementing the multiplication and division operations, supporting 64-bit fixed point numbers is a trivial extension.) I’ll wrap the definition in a function, so that local variables can be used as upvalues within the type’s various functions without polluting any other namespace. I’ll also name the data field `_v`

; it’s not meant to be public, but I do not think it is possible to hide fields of a struct with LuaJIT, hence the underscore as a hint that this is hands-off for any user of the fixed point type.

1 2 3 4 5 6 7 8 9 10 11 |
local function DefineFixedPointType(fractionalBits) local integerBits = 32 - fractionalBits local typeName = "Q" .. (integerBits < 10 and "0" or "") .. tostring(integerBits) .. (fractionalBits < 10 and "0" or "") .. tostring(fractionalBits) local rawCType = ffi.typeof("int32_t"); ffi.cdef("struct " .. typeName .. " { $ _v; };", rawCType) local cType = ffi.typeof("struct " .. typeName); -- ...rest of the definition end |

The next step is to be able to construct instances of this type. We cannot just rely on using the C type produced by LuaJIT, however, because that would merely try to convert the constructor argument to an `int32_t`

, oblivious to our desired fixed point semantic. Instead, we’ll create a table to represent our type, and give it an appropriate `__call`

metamethod. (Sidenote: Take care to use the correct period (.) or colon (:) syntax when defining a function. I prefer to use the colon and implicit `self`

parameter wherever relevant.)

1 2 3 4 5 6 |
local typeTable = {} local typeMetatable = { __metatable = {} } function typeMetatable:__call(n) return n and cType(asRaw(n)) or cType() end |

I’ll get to the `asRaw(n)`

function in a moment. For now, just realize that it’s purpose is to return an `int32_t`

instance which is the fixed point representation of its parameter, and it will be used in a variety of places. Given that definition, you can see that the `__call`

metamethod will simply construct an instance of the C type using the appropriate `int32_t`

initializer value, or it will create a default initialized C type if no parameter was passed to the constructor. (Technically, this implementation allows you to also pass `nil`

or `false`

to the constructor to get a default instance, but that’s only accidental.)

Next up is to round-trip the value. Assuming `asRaw()`

has an implementation, we can construct a fixed point number given a Lua number, so it would be nice to be able to get a Lua number back, given a fixed point number. Similarly, being able to convert directly to a string would be useful too. Both of these operations will take advantage of LuaJIT’s ability to attach metatables to C types, just as we can to normal Lua tables. I’ll also include a convenience field to get the type given an instance, which can come in handy when implementing further infrastructure that utilizes a variety of types.

1 2 3 4 |
local cMetatable = { __metatable = {}, __index = {} } function cMetatable:__tostring() return tostring(rawToNumber(self._v)) end function cMetatable.__index:ToNumber() return rawToNumber(self._v) end cMetatable.__index.type = typeTable |

Like with `asRaw()`

, `rawToNumber()`

is going to be a private function that takes an `int32_t`

representation of our fixed type and converts it to a Lua number. That’s why we pass in the `_v`

field directly.

Now that we have a metatable for our C type, we might as well implement the other obvious metamethods: the mathematical and comparison operators.

1 2 3 4 5 6 7 8 |
function cMetatable.__add(lhs, rhs) return (cType(addRaw(asRaw(lhs), asRaw(rhs)))) end function cMetatable.__sub(lhs, rhs) return (cType(subRaw(asRaw(lhs), asRaw(rhs)))) end function cMetatable.__mul(lhs, rhs) return (cType(mulRaw(asRaw(lhs), asRaw(rhs)))) end function cMetatable.__div(lhs, rhs) return (cType(divRaw(asRaw(lhs), asRaw(rhs)))) end function cMetatable.__eq(lhs, rhs) return lhs and rhs and equalRaw(asRaw(lhs), asRaw(rhs)) end function cMetatable.__lt(lhs, rhs) return lessThanRaw(asRaw(lhs), asRaw(rhs)) end function cMetatable.__le(lhs, rhs) return lessThanEqualRaw(asRaw(lhs), asRaw(rhs)) end function cMetatable:__unm() return (cType(negateRaw(self._v))) end |

There are a few different things going on here to note. The first is that I have used `asRaw()`

on all of the binary operator parameters. This is so that math and comparisons between a fixed point number and a Lua number are simple and do the right thing.

Another is that I have referenced some more yet-to-be-defined private functions, one for each operation. Their definitions, along with `asRaw()`

and `rawToNumber()`

are coming up next. The five mathematical operations all return a raw `int32_t`

value, thus they are wrapped in an initializer for the C type. The three comparison functions all return a `bool`

which can be returned directly.

Third, you’ll notice that I perform what amounts to a `nil`

test for the parameters to `__eq`

. Contrary to the wording in the official Lua 5.1 documentation, LuaJIT’s documentation is clear that all binary operators apply to mixed types, including between C data and `nil`

. With the other functions, I consider it acceptable to treat a `nil`

parameter as producing undefined behavior. But for an equality comparison, checking against `nil`

is a useful operation and should have the obvious behavior. Fortunately, we don’t have to check to see if both parameters are `nil`

, because if they were, we’d never be within the body of this metamethod. So if either one of the parameters is `nil`

, then we know that the other is not, and therefore the two are not equal.

One last thing I’ll point out in this section is the extra set of parentheses around each of the C type initializers. Without the parentheses, these return statements would represent tail calls, and in Lua, tail call runtime behavior is *mandatory*, whereas in other languages it might only be an optional optimization that the compiler or interpreter is free to ignore. Due to the nature of LuaJIT’s code execution tracing, tail calls to built-in LuaJIT functions will cause the compiler to abort and fallback to the interpreter, and the initializer of a C type is indeed treated as a built-in function. Adding the extra parentheses causes the initializer to be called in the normal manner rather than as a tail call, allowing the tracing compiler to continue along merrily. It would be disastrous to performance to fallback to the interpreter whenever performing math or comparisons between numbers, so this is a subtle but crucial point to make.

Okay, now to get around to defining those private functions I’ve been referencing. These in turn will be referencing C functions defined outside of Lua, and are mostly convenience wrappers around these C functions. So I’ll start by pulling those C declarations in through the FFI, and then defining the private Lua wrappers around them.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
ffi.cdef[[ int32_t Int32_FixedFromNumber(double floatingPoint, uint32_t fractionalBits); double Int32_FixedToNumber(int32_t fixedPoint, uint32_t fractionalBits); int32_t Int32_Add(int32_t lhs, int32_t rhs); int32_t Int32_Sub(int32_t lhs, int32_t rhs); int32_t Int32_MulFixed(int32_t lhs, int32_t rhs, uint32_t fractionalBits); int32_t Int32_DivFixed(int32_t lhs, int32_t rhs, uint32_t fractionalBits); bool Int32_Equal(int32_t lhs, int32_t rhs); bool Int32_LessThan(int32_t lhs, int32_t rhs); bool Int32_LessThanEqual(int32_t lhs, int32_t rhs); int32_t Int32_Negate(int32_t number); /* and others... */ ]] local exe = ffi.C local function rawFromNumber(number) return exe.Int32_FixedFromNumber(number, fractionalBits) end local function rawToNumber(raw) return exe.Int32_FixedToNumber(raw, fractionalBits) end local function asRaw(number) return type(number) == "cdata" and number._v or rawFromNumber(number) end local function addRaw(lhs, rhs) return exe.Int32_Add(lhs, rhs) end local function subRaw(lhs, rhs) return exe.Int32_Sub(lhs, rhs) end local function mulRaw(lhs, rhs) return exe.Int32_MulFixed(lhs, rhs, fractionalBits) end local function divRaw(lhs, rhs) return exe.Int32_DivFixed(lhs, rhs, fractionalBits) end local function equalRaw(lhs, rhs) return exe.Int32_Equal(lhs, rhs) end local function lessThanRaw(lhs, rhs) return exe.Int32_LessThan(lhs, rhs) end local function lessThanEqualRaw(lhs, rhs) return exe.Int32_LessThanEqual(lhs, rhs) end local function negateRaw(raw) return exe.Int32_Negate(raw) end -- and others... |

The `asRaw()`

function expects either a fixed point instance or a Lua number. Anything else is undefined behavior. In particular, anything that is C data but is not a `struct`

with a `_v`

field will produce an error. And if it *is* a `struct`

with a `_v`

field that represents something other than this fixed point type’s raw value, then who knows what will happen further on in the code.

Also, a number of these operations require the fractional bit count in order to perform their computations, so the Lua wrapper functions capture this parameter as an upvalue. The others could be done away with, calling the exe version directly, but for consistency, I’ve left them as is.

At this point, our fixed point number type is shaping up to be fairly usable, but let’s add some extra features that will greatly extend it’s usability. I’m only going to outline a general pattern, but it can be easily extended to include similar functionality.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
local typeFunctions = {} local typeConstants = {} function typeMetatable:__index(key) local value = typeFunctions[key] if value then return value end value = typeConstants[key] if value then return value(self) end error("The type " .. typeName .. " does not contain a function or constant " .. tostring(key) .. ".", 2) end function typeMetatable:__newindex(key, value) error("The field " .. tostring(key) .. " cannot be added to the type " .. typeName .. ".") end function typeFunctions.FromNumber(number) return typeTable(number) end function typeFunctions.FromFraction(numerator, denominator) return (cType(divRaw(asRaw(numerator), asRaw(denominator)))) end function typeFunctions.Floor(number) return (cType(floorRaw(asRaw(number)))) end function typeFunctions.Ceiling(number) return (cType(ceilingRaw(asRaw(number)))) end function typeFunctions.SquareRoot(number) return (cType(squareRootRaw(asRaw(number)))) end function typeFunctions.Power(base, exponent) return (cType(powerRaw(asRaw(base), asRaw(exponent)))) end function typeFunctions.Minimum(lhs, rhs) return (cType(minimumRaw(asRaw(lhs), asRaw(rhs)))) end function typeFunctions.Maximum(lhs, rhs) return (cType(maximumRaw(asRaw(lhs), asRaw(rhs)))) end function typeFunctions.Clamp(min, number, max) return (cType(clampRaw(asRaw(min), asRaw(number), asRaw(max)))) end function cMetatable.__index:Floor() self._v = floorFixed(self._v) return self end function cMetatable.__index:Ceiling() self._v = ceilingFixed(self._v) return self end function cMetatable.__index:SquareRoot() self._v =squareRootFixed(self._v) return self end function cMetatable.__index:Power(exponent) self._v = powerFixed(self._v, asRaw(exponent)) return self end function cMetatable.__index:Min(other) self._v = minFixed(self._v, asRaw(other)) return self end function cMetatable.__index:Max(other) self._v = maxFixed(self._v, asRaw(other)) return self end function cMetatable.__index:Clamp(min, max) self._v = clampFixed(asRaw(min), self._v, asRaw(max)) return self end do local raw0 = asRaw(0) local rawPos1 = asRaw(1) local rawPosEpsilon = rawCType(1) local rawMin = exe.Int32_MinValue() local rawMax = exe.Int32_MaxValue() function typeConstants.zero() return (cType(raw0)) end function typeConstants.one() return (cType(rawPos1)) end function typeConstants.epsilon() return (cType(rawPosEpsilon)) end function typeConstants.min() return (cType(rawMin)) end function typeConstants.max() return (cType(rawMax)) end if integerBits >= 2 then local rawHalfPi = asRaw(1.5707963267948966192313216916398) function typeConstants.halfPi() return (cType(rawHalfPi)) end end if integerBits >= 3 then local rawPi = asRaw(3.1415926535897932384626433832795) function typeConstants.pi() return (cType(rawPi)) end end if integerBits >= 4 then local rawTwoPi = asRaw(6.283185307179586476925286766559) function typeConstants.twoPi() return (cType(rawTwoPi)) end end end |

The member function variants defined first are mutating and chainable functions. This allows expressions such as `Q1616(4.1):Power(3):Floor():Clamp(0, 100)`

. In my production code I’ve included the basic mathematical and comparison operations too, along with a few other helper functions like `Clone()`

and `Set()`

. For these functions that have operator equivalents (`+ - * / = == ~= < <= > >=`

), I drop the calls to `asRaw()`

, and require that their inputs already be of fixed point type. This grants the user a way to perform micro-optimizations if necessary, for example in a tight loop performing a lot of math. Why bother executing the branch contained in `asRaw()`

if you know that all values are already fixed point?

For the constants, I return a newly constructed instance each time the constant is accessed, since LuaJIT will often operate with reference semantics, not value semantics, and I don’t want something like `Q1616.pi:Sqrt()`

to suddenly change the value of pi everywhere.

I’ve glossed over an important step in defining the type; the metatables of course need to be attached to their type tables. Now that I have all the metatables and helper tables and defined, we can do that. For the type table, we’ll use the standard Lua function `setmetatable()`

, while for the C type, we’ll instead use `ffi.metatype()`

.

1 2 |
setmetatable(typeTable, typeMetatable) ffi.metatype(cType, cMetatable) |

As an added bonus, we can put together a collection of type details that can be used for reflective purposes elsewhere in code. For example, if defining a matrix type that uses fixed point numbers, the matrix definition code can request the details of its number type, and adjust its definition accordingly. In particular, it can store an array of `int32_t`

instances directly, and use the private fixed point functions defined above to implement standard matrix operations. This will avoid a lot of unnecessary overhead with C data construction and parameter type checks. I discovered that it is also necessary because LuaJIT will not compile the initialization of a C type if it is a `struct`

that contains nested `struct`

s. Thus, constructing a 2D vector of fixed point numbers that is defined as `struct { struct { int32_t _v; } _x; struct { int32_t _v; } _y; }`

will fallback to the interpreter, but if instead it is defined as `struct { int32_t _x; int32_t _y; }`

, the compiler will be able to handle that just fine.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
local typeDetails = { name = typeName, cType = cType, cSize = ffi.sizeof(cType), rawCType = rawCType, rawOperations = { rawFromNumber = rawFromNumber, rawToNumber = rawToNumber, asRaw = asRaw, addRaw = addRaw, subRaw = subRaw, -- et cetera... }, } |

The final line of our `DefineFixedPointType()`

function can return both `typeTable`

and `typeDetails`

. When we call it, we can then put the typeTable into the global namespace, or whatever other namespace we wish. We can also stuff the `typeDetails`

table into a lookup table keyed by the type itself. I’m going to put these operations in a small helper function.

1 2 3 4 5 6 7 8 |
local function AddTypeDefinition(allTypes, allTypeDetails, typeTable, typeDetails) allTypes[typeDetails.name] = typeTable allTypeDetails[typeTable] = typeDetails end local typeDetails = {} AddTypeDefinition(getfenv(0), typeDetails, DefineFixedPointType(16)) --Q1616 AddTypeDefinition(getfenv(0), typeDetails, DefineFixedPointType(30)) --Q0230 |

From this point, usage of the fixed type might look something like the following:

1 2 3 4 5 6 |
local x = Q1616(5) local y = Q1616(2.3) local lenSqr = x * x + y * y local len = Q1616.SquareRoot(lenSqr) local circumference = Q1616.pi * lenSqr * 2 print(tostring(circumference)) |

That concludes the basic definition of a 32-bit fixed point number type in LuaJIT. The full source and some basic usage can be downloaded here, with both C++ and Lua portions. The contents of this download, and all source code excerpts within this blog post, are released into the public domain. For more information, please refer to unlicense.org.

## 3 Comments

## Trackback by http://whilelimitless.com/limitless-pill/is-it-real/ — 2016/12/30 @ 19:00

http://whilelimitless.com/limitless-pill/is-it-real/Experilous: Custom Numeric Types with LuaJIT

## Trackback by http://whilelimitless.com/limitless-pill/nzt-48/ — 2017/01/04 @ 10:53

http://whilelimitless.com/limitless-pill/nzt-48/Experilous: Custom Numeric Types with LuaJIT

## Trackback by venushack.com/weight-loss/venus-factor-review/ — 2017/01/05 @ 09:44

venushack.com/weight-loss/venus-factor-review/Experilous: Custom Numeric Types with LuaJIT

## Leave a comment