Searching for ways to compute directly in hexadecimal

Help! Data Structure
1

I’m attempting to find or create a set of predicates that would allow prolog to reason directly in hexadecimal without having to convert back and forth to integers. Specifically I’m creating an application that will be reasoning over the properties of crash dumps, and thus walking stacks and working with memory locations constantly and it would probably be optimal to simply work in hex directly for a number of reasons namely; endianness, efficiency, and to build a foundation of predicates I won’t have to rewrite for trivial reasons past a certain point of maturity.

a trivial example predicate would be something like

top_of_stack(MemLoc)
where MemLoc is simply a hex value

checking hex values against facts like stack frames, pointers, etc, these are going to be the bread and butter of my application.
To be clear I will need conversion predicates/operators/whatever but I’d rather not have to build them in from the beginning and have to change that almost immediately.

I searched both the swi-prolog documentation and this forum but didn’t really find anything that directly addressed my question, thank you for your time.

EDIT: I am waiting to work through these responses and apply them to my code before I mark one (or any) as a solution. I sincerely appreciate all who took the time to respond to this question and I look forward to posting more in this forum, thank you again.

2

Interesting, I’m not sure I fully understand what you refer to as “hex values”.
How are they represented (if not as integers), as atoms?

And do you intend to do arithmetics on them?

3

Thanks for the response! I mean the values that prolog will be operating on will be hexadecimal numbers representing multiple kinds of data; characters, integers, floating point values, etc. I do indeed intend to do arithmetics on them, thank you for helping me clarify my question. Thus it would be cumbersome to represent these values as strings or integers and constantly need to convert back and forth, but if I must do that (at least for the time being) than that is what I must do!

4

I expect it’s better to just convert hex <–> dec once, and then “remember” the pair (i.e keep track of it).

Prolog’s built-in arithmetic will be faster than comparing hexadecimal “strings”.

For conversion, see e.g.:

Edit: Also: xinteger//1

?- use_module(library(dcg/basics)).

?- phrase(xinteger(N), `FF57`).
N = 65367.

?- phrase(xinteger(65367), L).
L = `ff57`.
5

thank you for the response and aggregating these for me (and others after)! I’m not sure keeping track of individual values like that would work, but it might and that could work as a crutch until I figure out something better. The problem is that the values would often be ephemeral enough or that there are simply so many of them that to track in that way would be onerous and for large enough binaries intractable or close enough to it as to make the tool useless. I should be clear I am very new to Prolog so I could be wrong on efficiency questions or other basic stuff, so please forgive me if I’m unclear or responding with an incorrect assumption.

7

It’s not clear to me what your main problem is …

  • Are you trying to parse crash dumps into data structures or Prolog facts, and then reason about them?
  • Are the crash dumps in internal form (e.g., “core” files that gdb can handle), or human-readable form?
  • Do you have questions about how to convert the crash dump form into Prolog facts or data structures, or questions about how to reason over them? (Or both?)
  • What kinds of operations do you need to do on hex values? (e.g., display the raw value as an integer / float / string / C data structure; check whether a pointer is between location X and X + 64)
  • etc.
1 Like
8

Thank you for the response. the parsing is already handled by lisp, I would prefer to give Prolog facts and rules (generated entirely by lisp) operating over hex values (I have other needs in terms of data structures but I can figure that out), without having to convert back and forth to strings or intergers. Thats it. I don’t need help with the crash dumps, or literally anything else, I simply haven’t been able to locate standard library predicates that allow one to work purely in hex, and have prolog add subtract multiply and divide purely on the hex representation. The reason I would prefer to do this in hex is so that I can build a library on top of those predicates such that as my application encounters more robust (read: larger) binaries, with potentially hundreds of thousands of facts, that this is not a bottleneck, to say nothing of the initial hassle of littering my code with conversions everywhere.

In sum: My original question was simply: are there predicates that operate on hex already extent in the SWI standard library. I’m guessing from my own searching and the responses here, other than a single conversion predicate in a crypto focused library, that that is not the case. My follow up is, simply: what would be the best way to build a set of predicates and operators such that my logic doesn’t have to dance back and forth between hex and whatever, that my code can simply ingest some (potentially quite large) list of hex values representing any number of possible data types and reason over that.

Your third question comes the closest, at the end of it, checking whether a hex value is a pointer, the beginning of a stack frame, within another stack frame, is memory that is either readable or writeable, etc, these are the inferences I would like Prolog to draw from facts (and rules!) that I will have already generated from the crashes.

9

Conversion is easy - see xinteger in my edited post above.

Converting from hex to decimal, performing whatever arithmetic you desire, then converting back to hex, is going to be far simpler, almost certainly faster, and most importantly actually achievable for a beginner who’s not used to writing performant DCGs or using difference lists.

I’m not seeing the “bottleneck” or the “littering” issues.

What’s so special about the “reasoning” mentioned?

10

An alternative, if you already have the facts in Lisp form, is to simply output the S-expressions and use a trivial DCG to read them - either output them as Prolog facts, or assertz/1 them. (If you have them as Prolog facts, and you want to load them multiple times, you can use qlf form to make the loading happen much faster)

This confuses me – hex is an external representation of an integer (or pointer, or bits, or a float, or a string, etc.). If you want to have a data structure that means “this is a thing in hex format”, then you could use a simple term of the form hex(string) - for example, hex("deadbeef") and then you can do arithmetic like this:

hex_arith(X + Y, Sum) :-
    hex_int(X, X_int),
    hex_int(Y, Y_int),
    Sum_int is X_int + Y_int,
    hex_int(Sum, Sum_int).
% similar for X - Y, X < Y, between(X, Low, High), etc.

hex_int(X, X_int), var(X) =>
    format(string(X_hex), '~16r', [X_int]),
    X = hex(X_hex).
hex_int(hex(X), X_int) =>
    string_concat("0x", X, X_hex),
    term_string(X_int, X_hex).

?- hex_arith(hex("ff") + hex("1"), Z).
Z = hex("100").
1 Like
11

The s-expression suggestion is outstanding, thank you for that. I very very much appreciate you taking the time to sketch out some code to make your point, and I will probably begin with something close to this. I would have preferred to work on the hex itself but I’ll take what I can get for now and as I deepen in my work with Prolog bend it how I feel I want it to bend. DCGs shouldn’t be too much of a problem for me to work with, I love lisp and I’m quite comfortable with grammars and little languages.

12

Perhaps I misunderstand your problem, but you don’t have to do any conversion, prolog can do it for you.

  • when you write facts from lisp write facts as: fact(0xffaa,0xaa). Prolog will do conversion and arithmetic for you.

  • when you want to see facts displayed as hex use portray/1. (prolog doesn’t care about the number format for reasoning about the numbers, they are an integer in the machine architecture after all, whatever format they came in).

    ** to use portray/1 you define a predicate user:portray(Term) :- … that outputs the term in the format you want.

Here is some sample code that shows you this:


fact(0xffaa, 0xaa).
fact(0xbfaa, 0xba).

add_one(Result) :-
	fact(X,Y),
	add_one(fact(X,Y),Result).
add_one(Fact, Result) :-
	Fact=fact(X,Y),
	X1 is X + 1,
	Y1 is Y + 1,
	Result = fact(X1,Y1).

user:portray(fact(X,Y)) :-
	format('fact(0x~16r,0x~16r)',[X,Y]).

Sample query calling adding one two times:

8 ?- add_one(R0), add_one(R0,R1).
R0 = fact(0xffab,0xab),
R1 = fact(0xffac,0xac) ;
R0 = fact(0xbfab,0xbb),
R1 = fact(0xbfac,0xbc).

Portray is enabled by default on the prolog top level, but you can also enable it by using the portray option to write_term/2:

9 ?- write($R0).
fact(49067,187)   % no portray option
R0 = fact(0xbfab,0xbb).

10 ?- write_term($R0,[portray(true)]).
fact(0xbfab,0xbb)  % with portray option
R0 = fact(0xbfab,0xbb).
3 Likes
13

As a side note, if you wanted to show all integers in hex, you would use portray this way:


user:portray(X) :-
	integer(X),
	format('0x~16r)',[X]).

Then all integers would be printed in hex:

5 ?- A is 3+10.
A = 0xd.
1 Like
14

thank you for these, I appreciate it!

15

You really need to demonstrate in some way what you really mean by this. As far as I know modern computer architectures support only binary representation of data, based on the early lesson that it is relatively easy to make electronic components with two states, and relatively difficult to make them have more than two states.

So what it this hex really?

Further up in the thread people talk about “conversion”, like:

but in fact there is no conversion happening internally. I think @peter.ludemann tried to explain this too.

You write:

I still don’t understand what this is. What is the hex? Can you show us how a hex looks like?

There is only binary representation internally. This:

0x42

will almost certainly be represented by a byte in the machine somewhere, and this byte will have 8 bits, and each of them will have one of two states. So where is the hex? What does it look like?

There is no conversion; there is reading literals and writing them back to you. We do this so that we don’t have to look at the 0s and 1s.

PS: you need four bits to represent a hexadecimal digit, since there are a total of 16 of them (0, 1, …, E, F). I don’t know of any modern architecture that has either a bit with 16 states, or a “word” of 4 bits. I might be wrong but it is usually 32 or 64 bits that are the unit of modern processors. I admit I don’t know anything about graphic card hardware though, those might be different.

16

Why not have Lisp conveniently pre-convert the hex strings into decimal strings? Sounds like the easiest method. Or have Prolog do this as a first pass.

To clarify the performance aspect I mentioned - some of the swi-prolog predicates are implemented natively in C, as shown by e.g.:

?- listing(format).
%   Foreign: system:format/3

'$syspreds':format(Fmt) :-
    format(Fmt, []).

%   Foreign: system:format/2

… as are the mathematical operations. They are far faster than interpreted Prolog code can be. This is why writing Prolog code to perform maths on hex strings as hex strings would be relatively slow.

1 Like