Binding Keys to Function Pointers

BlitzMax Forums/BlitzMax Programming/Binding Keys to Function Pointers

zoqfotpik

(Posted 2014) [#1]

Here's an interesting little piece of code that does exactly what it says on the label.

This is a simple way of handling runtime key definition (for remappable keys) and tends to clean up the main loop...

' bindkey - binds key to function
Global functions()[256]  '  This is an array of function pointers, one for each ascii keycode.
						 '  Not all of these will be initialized...
Graphics 320,200

Function bind(key:Int, func())  ' Binds a key to a function pointer.
	functions[key]=func
End Function

Function thing1()  ' Example functions.  These could be anything...
DrawText "thing1", 10, 10
End Function

Function thing2()
DrawText "thing2", 10, 10
End Function

Function bail()
End
End Function

bind(KEY_1,thing1)  ' These are the binding statements.
bind(KEY_2,thing2)
bind(KEY_ESCAPE,bail)

While(1)
For i = 0 To 256 ' Iterate this every tick
' To make this faster you would make a list of keys you've bound in this
' manner and iterate over that instead
	If KeyHit(i) And functions[i] 
		Cls
		functions[i]
		' ^^ is the corresponding pointer non-null?  If so, execute it
		Flip
	EndIf
	
Next
Wend

Hardcoal

(Posted 2014) [#2]

Small and nice! I didn't even know you can array functions...
Omg there is no end for the complexity of blitzmax?

what else can you do when passing a function as a variable to another function?

Derron

(Posted 2014) [#3]

Now extend it to allow "CTRL + KEY" or "SUPER + KEY" :p

@Harcoal
If your functions need a varying amount of params you will have to take care - as the array only accepts functions with the same definition.

To avoid this, you could have a

Global functions(params:object)[256]

function x(params:object)
end function

if you want to store multiple objects in this param object, you need a wrapper object (a type containing an array of objects).
Another option is to have "params:object[]" - and then for single functions call it in [ ] brackets like when adding to arrays (arr :+ [newEntry]).
x([myparam])

passing functions to other functions is used for connecting eventlisteners in event systems, or to bind specific functions to events ("onClick" etc.).
My event system at
https://github.com/GWRon/Dig/blob/master/base.util.event.bmx
uses such a simple approach + wrapper objects (each event has a data-property which is a flexible data container type).

bye
Ron

BlitzSupport

(Posted 2014) [#4]

Pretty cool idea!

zoqfotpik

(Posted 2014) [#5]

Originally I had it as

If KeyHit(i) And functions[i] functions[i]

I wish there were a way to compose functions, but I suppose that's for languages that are a meta-level above Blitzmax, and slower.

Kryzon

(Posted 2014) [#6]

I'm not so fond of that obligatory 256 iteration loop, so I would do it with an event hook.

AddHook( EmitEventHook, keyHook )

Function keyHook:Object( id:Int, data:Object, context:Object )

	Local event:TEvent = TEvent( data )

	If event Then

		'Remember to use brackets if the function returns a value.

		If event.id = EVENT_KEYDOWN Then If functions[ event.data ] Then functions[ event.data ]()
 
	EndIf

	Return data 'Important to return the event to the other hooks.

End Function

You would need to use a PollSystem() loop if it's a game, or use a WaitEvent() loop if it's a generic application.

zoqfotpik

(Posted 2014) [#7]

I'm not so fond of that obligatory 256 iteration loop

Push them onto a stackarray as you bind them and loop over that.

Kryzon

(Posted 2014) [#8]

Indeed, that's another way.

If someone is using this function-binding for time-dependent applications (music software, for instance), I believe that events are the most accurate solution as you call the function at the moment that the key is pushed down (when your program receives the event from the OS).

zoqfotpik

(Posted 2014) [#9]

About iterating over 256 array elements, wouldn't branch prediction make that extremely fast?

Hardcoal

(Posted 2014) [#10]

Thanks Derron for the extra guidance..
I need to experiment with that..

btw I also dislike the 256 iteration loop doesnt it slow everything?

zoqfotpik

(Posted 2014) [#11]

What I think is that because of branch prediction, since the vast majority of the values are going to be null, it will be very fast, but I haven't tested it... Either way it's lazy and the values should be pushed onto a stack or other data structure so that you are only iterating over the number of keys that you have... Another possibility to make it faster still would be to use some flag for "anykeyhit" but I'm not sure what that would be, probably the event hook method above would be best... the combination of that and putting them into a stack as they are bound will probably make it very fast.

Initially I wrote this for key handling in my simple GUI so I wasn't that concerned about speed. I am very interested in the branch prediction question... But I think I see how to do it easily with a raw array of 256 where they are pushed onto the tail of the array as they are bound, I will futz with it tonight.

Derron

(Posted 2014) [#12]

I always thought the problem is the autopolling and PollSystem-call in KeyHit/KeyDown

If you open "polledinput.bmx" you already see the "global keyStates[256]"
Just make them "public" and you can directly access them without adding another function on top (eventhook or keyHit() call)

So branch prediction might decrease access times to array entries, but the workload will come from the KeyHit() or KeyDown() overhead.

If KeyHit(i) And functions[i] functions[i]

That is why someone invented verbosity and that little word "then" (I stated this in another thread on the monkey website as functions[i] could be a function having a default parameter so "functions[i] functions[i] functions[i]" could be avalid code snippet without saying which is the "then"-part and which one belongs to the "if"-part).

Do you guys have an idea how to implement that function binding in combination with special keys (ctrl alt super) - without having some wrapping object. Think 256 more entries for each special key will be too much.

bye
Ron

zoqfotpik

(Posted 2014) [#13]

Ok, now it polls getchar() and tries to do a function, then continues to do so until the getchar() buffer is exhausted (to allow more than one keyhit per tick).

' bindkey - binds key to function
Global functions()[256]  '  This is an array of function pointers, one for each ascii keycode.
						 '  Not all of these will be initialized...
Graphics 320,200
Function bind(key:Int, func())  ' Binds a key to a function pointer.
	functions[key]=func
End Function

Function thing1()  ' Example functions.  These could be anything...
DrawText "thing1", 10, 10
End Function

Function thing2()
DrawText "thing2", 10, 10
End Function

Function bail()
End
End Function

bind(KEY_1,thing1)  ' These are the binding statements.
bind(KEY_2,thing2)
bind(KEY_ESCAPE,bail)

While(1)
	Repeat
		char% = GetChar()
		If char And functions[Int(char)] clsdothingflip(functions[Int(char)])
	Until char=Null
Wend

Function clsdothingflip(func())
	Cls;func;Flip
End Function

Who was John Galt?

(Posted 2014) [#14]

That is why someone invented verbosity and that little word "then"

A tactical pair of brackets should suffice for those of us who despise that four letter word.

Kryzon

(Posted 2014) [#15]

Do you guys have an idea how to implement that function binding in combination with special keys (ctrl alt super) - without having some wrapping object. Think 256 more entries for each special key will be too much.

Perhaps you can supply the modifiers as parameters to the function.

Function keyHook:Object( id:Int, data:Object, context:Object )

	Local event:TEvent = TEvent( data )
	If Not event then Return data

	Select event.id

		Case EVENT_KEYDOWN

			If functionsDown[ event.data ] Then functionsDown[ event.data ]( event.mods )

		Case EVENT_KEYUP

			If functionsUp[ event.data ] Then functionsUp[ event.data ]( event.mods )

	End Select

	Return data

End Function

Yasha

(Posted 2014) [#16]

I am very interested in the branch prediction question...

Branch prediction is an internal implementation detail of the CPU and as a result there's no single answer that will apply to every system supporting BlitzMax (technically there's no requirement for an x86 system to support branch prediction at all; it would just be rather slow). You should also never listen to anyone (especially me) on this topic; because it's a hidden factor, the only way to know for sure whether your program is affected by it and where is to use a profiling tool like Intel VTune.

Prediction is (on ~2000 - ~2010 archs) usually one level deep (the last function pointer called will be predicted to be called again). On newer systems it is often two levels deep (obviously not for control structures since they only describe two paths). Either way, on production CPUs it is extremely simplistic and does not take data into account: it isn't able to see "this is iteration 58, where we branched true previous loop"; it is able to see only which path was taken on iteration 57. Counter-intuitively, i the case of function pointers, it's also not able to look at the actual register about to be called through and see what function pointer is really loaded there. While more advanced algorithms are possible in theory (and have been built in practice), they're too complicated to be worth the effort, either physically or because the actual prediction ends up taking too long. (They can be very interesting though.)

(Also, ret instructions have a near-100% accuracy rate because they do take data into account and maintain a separate prediction stack, due to their importance)

Therefore you will have a misprediction at both the If for pointers that need to be called through, and at the call itself if it's not the same call as last time. You may as well lose the secondary If and use some kind of And operation instead for that, so it doesn't need a second branch.

You could achieve near-perfect prediction by unrolling the loop and replacing the false branch of the "If" with calls to a dummy function that does nothing, although this is a dumb idea for several reasons (reason 1 being that it makes your code look horrible; it's probably also much slower than sucking up the odd mispredict thanks to the tremendous bloat, unless you severely limited the number of bindings. Actually wait, you could limit the size of it quite severely since only a few keyhits can actually be returned each frame...).

In practice I'd be surprised if a loop of a mere 256 elements was slow enough to measurably affect anything at the top level of the main loop, even if it mispredicted on every single branch. Neither mispredicts nor the loop itself are going to be your bottlenecks here.

@post #2: function pointers are awesome. You can actually implement literally every other new feature of BlitzMax (since Blitz3D) in terms of them! They can do anything.

zoqfotpik

(Posted 2014) [#17]

I figured you would chime in here.

unless you severely limited the number of bindings. Actually wait, you could limit the size of it quite severely since only a few keyhits can actually be returned each frame...).

Also if you have a user who can hit 256 keys per tick, you have bigger problems to worry about. The way I have it now with getchar() it doesn't walk the array at all, it just uses getchar() to pop characters off the buffer until there aren't anymore.

@post #2: function pointers are awesome. You can actually implement literally every other new feature of BlitzMax (since Blitz3D) in terms of them! They can do anything.

I have this really tantalizing feeling about them, that I can almost but not quite implement a LISP because of them, but I can't because I just don't know enough about computer science. I should really get disciplined and work through SICP. Or at least chew off another chapter. Right now I am studying math very hard to scrape off the rust on things I haven't done for decades, and I'm thinking about going for a master's in that or at the very least a bs. I guess SICP is technically really close to math anyway...

I also just don't understand how pointers are handled in Blitz. I can't say it was a mistake to obscure/elide them the way they are, it's certainly easier than C this way. Maybe I should just be diving into it more, but if you look at my cellular automaton explorer that I posted a few days ago you will notice that I am copying a large 2D array rather than just twiddling a pointer.

Couple of questions:

1) Is it possible to implement generics in Max the same way it is in C? That is to say, passing data size to the function as well as the data itself.

2) How do you do pointer arithmetic in Blitz?

Here is a bit of code related to function pointers that I hacked out last night.

' From Function to Int and Back Again

Local func1()

Function test1()
	Print "test1"
End Function

Function functoint:Int(func())
	Return Int(Byte Ptr func)
End Function

Function inttofunc:Byte Ptr(a:Int)
	Return Byte Ptr(a)
End Function

func1=test1
Local testfunc()=inttofunc(functoint(func1))

testfunc()

This seems to be of dubious use, but then I'm really pushing the boundaries of my limited knowledge here. Studying this stuff makes me feel like a kid in a candy store.

zoqfotpik

(Posted 2014) [#18]

Hm, double post...

Yasha

(Posted 2014) [#19]

SICP is a great work, but if you need something simpler/closer to the metal, you might find Scheme 9 from Empty Space easier reading. (Do look at the rest of the site for other goodies!)

I also just don't understand how pointers are handled in Blitz.

A pointer in BlitzMax is fundamentally the same thing it is in C: a primitive numeric type with very restricted operations. You can cast between the different pointer and integer types freely, you can add and subtract integers to/from pointers, and in addition pointers can be subscripted to dereference them. There is no dedicated deref operator, but subscripting the 0th element is the same thing.

Pointer arithmetic is as in C: adding to a pointer of type `T Ptr` adds `sizeof(T)` to its underlying address value. Subscripting is exactly as in C:

Local p:Int Ptr = ...
p[5]  ==  (p + 5)[0]  ==  (Byte Ptr(p) + 5 * sizeof(Int))[0]

Local d:Int Ptr = Int Ptr(MemAlloc(SizeOf(0) * 2))
d[0] = 42 ; d[1] = 47
Print ((d + 1)[0])    'Prints 47

Note that Byte Ptr is analogous to char*, not void*, and can be dereferenced if you're not careful to yield a Byte value (rarely what you want).

Other things to consider:

-- just because you can cast between ints and pointers doesn't make it a good idea. This relies completely on assumptions about the underlying representation (that will change if the 64-bit compiler gets off the ground) - just because pointers happen to be represented as ints doesn't mean they actually are ints, conceptually

-- you can get "raw" data blocks to play with using MemAlloc and MemFree, analogous to malloc and free (not the same and not compatible though - if you manipulate data from a C library, do not free it with MemFree or vice versa)

-- casting an object to Byte Ptr gives you the address of the start of the data contained in the object (e.g. if you had a simple type with fields x%, y%, z%, then casting an object to Byte Ptr would give you the address of x). This is not the same as the value BlitzMax uses as a typed object reference in normal code; that's another hidden implementation detail (it's ptr - 8 in the current compiler, but this will change)

Derron

(Posted 2014) [#20]

Kryzon: Perhaps you can supply the modifiers as parameters to the function

Appending a generic "param:object = null" is always a good idea (except for performance gains as casts cost time). But this means, a function then has multiple possible actions it kicks off (depending on the "special key").

In an OOP-style-manner this means, you cannot just "override" (CTRL+C without also writing code for "C", "ALT+C", "SUPER+C" as an) portions of the code.

If you want to reduce amount of "keys" we could do it with a TMap - but this lowers access times way more. Maybe a mix is then the best way:

array[maxKeycodeOfKeyboardKeys] for simple key presses.
Tmap for every other key press (or keycombination) one might be interested in.

If the array does not contain the key check tmap. So for normal typing only the "if key exists"-check is added to gain more flexibility.

Will this add too much additional workload?

bye
Ron

zoqfotpik

(Posted 2014) [#21]

Maybe check if a mod key is down first, then check the Tmap?

Another thing you could do that I think would speed it up tremendously in situations where you had a lot of keys mapped would be to cache eg. the last 8 keys hit or so and check those first and if the key isn't in there then it falls through and checks the rest, or perhaps the next list of 8 keys. You could also have it keep a running histogram of keys hit and sort the list in order of hit frequency.

These methods would drastically increase speed in most common use situations, unless you are writing a word processor or something where semi random key hits over a large space was common for some reason.

Check key last hit first, then most frequent key, then last 8 keys, then down the frequencies, then on to the more obscure keys.