ivorykite

x64: a short illustration of encoding simple instructions

The output of gen predicted the output of gas. ie. gen illustrates how to construct the REX and MODRM bytes

$ cat gen.c
typedef unsigned char C, *S;
typedef int I;
I printf (S, ...);
I
e (C x)
{
  printf ("%x ", x);
}

I
a (C i, I x, I y, I z)
{
  C m[] = "ma", o[] = { 0x89, 0x01, 0 };
  C rex (C x, C y)
  {
    return 0x48 + (x > 7) * 4 + (y > 7);
  }
  C modrm (C x, C y)
  {
    return 0xc0 + (x & 7) * 8 + (y & 7);
  }
  I ins (I i, C x, C y)
  {
    return e (rex (x, y)), e (o[i]), e (modrm (x, y));
  }
  ins (i, x, y);
  printf ("\n");
}
S r[] = { "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", 0 };

int
main ()
{
  printf ("\tmov %%%s,%%%s            # the assembler will emit: ", r[5], r[9]);
  a (0, 5, 9, 0);
  printf ("\tadd %%%s,%%%s             # the assembler will emit: ", r[9], r[9]);
  a (1, 9, 9, 0);
}

$ cat gen.c

typedef unsigned char C, *S;

typedef int I;

I printf (S, ...);

e (C x)

{

printf ("%x ", x);

}

a (C i, I x, I y, I z)

{

C m[] = "ma", o[] = { 0x89, 0x01, 0 };

C rex (C x, C y)

{

return 0x48 + (x > 7) * 4 + (y > 7);

}

C modrm (C x, C y)

{

return 0xc0 + (x & 7) * 8 + (y & 7);

}

I ins (I i, C x, C y)

{

return e (rex (x, y)), e (o[i]), e (modrm (x, y));

}

ins (i, x, y);

printf ("\n");

}

S r[] = { "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", 0 };

int

main ()

{

printf ("\tmov %%%s,%%%s # the assembler will emit: ", r[5], r[9]);

a (0, 5, 9, 0);

printf ("\tadd %%%s,%%%s # the assembler will emit: ", r[9], r[9]);

a (1, 9, 9, 0);

}

$ gcc gen.c -o gen
$ ./gen > out.s
$ cat out.s
	mov %rbp,%r9            # the assembler will emit: 49 89 e9 
	add %r9,%r9             # the assembler will emit: 4d 1 c9 
$ as out.s -o out
$ objdump -d out |tail -2
   0:	49 89 e9             	mov    %rbp,%r9
   3:	4d 01 c9             	add    %r9,%r9

$ gcc gen.c -o gen

$ ./gen > out.s

$ cat out.s

mov %rbp,%r9 # the assembler will emit: 49 89 e9

add %r9,%r9 # the assembler will emit: 4d 1 c9

$ as out.s -o out

$ objdump -d out |tail -2

0: 49 89 e9 mov %rbp,%r9

3: 4d 01 c9 add %r9,%r9

the output of gen predicted output of gas. ie. gen illustrates how to construct the REX and MODRM bytes

general parser for k

i wrapped up an earley parser, “yaep”, into a k .so here: http://www.ivorykite.com/ear/ear.tgz

earley parsers are known for their tolerance of ambiguity (first match – like PEG) and of both left and right recursion. here’s the demo that ear.tgz includes:

$ LD_LIBRARY_PATH=/home/jack/q/l32 q k.k
KDB+ 3.4 2016.06.14 Copyright (C) 1993-2016 Kx Systems
l32/ 4()core 6936MB jack g50 127.0.1.1 NONEXPIRE

parsing k using an earley parser
"E:E;e|e e:nve|te| t:n|v v:tA|V n:t[E]|(E)|{E}|N"
"  x y x   yxZ xY    x x   yx x   x y   x  xy  x"

"N;;NN;NVN;NVNVN;NA;N[N];VAN;VAAN;{NVN}[N;N]"
("N";();"NN";"VNN";("V";"N";"VNN");"AN";"NN";("AV";"N");(("A";"AV");"N");(("{";"VNN");"NN"))

lexing, classing and parsing k
(("/";("/,";("\\:";"@")));("\\,";("'";("<";",";"<:");"=:")))

native grammar
"E: E ';' e #E0(0 2)| e #E1(0);e: n v e #e0(1 0 2)| t e #e1(0 1)|#e2();t: n #t0(0)| v #t1(0);v: t 'A'#v0(1 0)|'V'#v1(0);n: t '[' E ']'#n0(0 2)|'(' E ')'#n..

native output
(`E1;(`e1;(`t1;(`v0;6;(`t0;(`n1;(`E1;(`e1;(`t1;(`v0;2;(`t0;(`n3;1))));(`e1;(`t1;(`v0;4;(`t1;(`v1;3))));,`e2)))))));(`e1;(`t1;(`v0;8;(`t0;(`n3;7))));(`e0;(`v1..
q)

$ LD_LIBRARY_PATH=/home/jack/q/l32 q k.k

l32/ 4()core 6936MB jack g50 127.0.1.1 NONEXPIRE

parsing k using an earley parser

"E:E;e|e e:nve|te| t:n|v v:tA|V n:t[E]|(E)|{E}|N"

" x y x yxZ xY x x yx x x y x xy x"

"N;;NN;NVN;NVNVN;NA;N[N];VAN;VAAN;{NVN}[N;N]"

("N";();"NN";"VNN";("V";"N";"VNN");"AN";"NN";("AV";"N");(("A";"AV");"N");(("{";"VNN");"NN"))

lexing, classing and parsing k

(("/";("/,";("\\:";"@")));("\\,";("'";("<";",";"<:");"=:")))

native grammar

native output

(`E1;(`e1;(`t1;(`v0;6;(`t0;(`n1;(`E1;(`e1;(`t1;(`v0;2;(`t0;(`n3;1))));(`e1;(`t1;(`v0;4;(`t1;(`v1;3))));,`e2)))))));(`e1;(`t1;(`v0;8;(`t0;(`n3;7))));(`e0;(`v1..

64bit RPN compiler in q

Adapted from 64-bit reverse polish JIT compiler

The call to execute the compiled expression is unimplemented as my personal edition of kdb+ is 32bit and don’t want to write the 32bit to long mode and back again hack.

$ q r.q
KDB+ 3.4 2016.06.14 Copyright (C) 1993-2016 Kx Systems
0x4889e548b8ffffffffffffff7f48b80100000000000000585b4801d8504889ecc3

/save rsp, push literals, if op, pop twice and addq, subq.. and push
c:{raze 0x4889e5,(d each x),0x4889ec,0xc3}
d:{$[102-type x;0x48b8,x;0x58,0x5b,((0x4801d8;0x4829d8;0x480fafc3;0x4899,0x4889ec)(+;-;*;%)?x),0x50]}
j:-8#-8!7h$
t:{@[x;;j]where 0<>102 -7h?(type')x:(value'){x where not (1#" ")~/:x}@-4!x}
c t"9223372036854775807 1 +"

/save rsp, push literals, if op, pop twice and addq, subq.. and push

c:{raze 0x4889e5,(d each x),0x4889ec,0xc3}

d:{$[102-type x;0x48b8,x;0x58,0x5b,((0x4801d8;0x4829d8;0x480fafc3;0x4899,0x4889ec)(+;-;*;%)?x),0x50]}

j:-8#-8!7h$

t:{@[x;;j]where 0<>102 -7h?(type')x:(value'){x where not (1#" ")~/:x}@-4!x}

c t"9223372036854775807 1 +"

64-bit reverse polish JIT compiler

Here’s a 64-bit JIT compiler for the RPN calculator. Each expression entered in a REPL is compiled by cc() in-memory and then called with a single instruction in exe().

You can see 64-bit overflow:

$ gcc r.c -o r
$ ./r
>9223372036854775807 1 +
-9223372036854775808

//RPN compiler: E:EEf|n f:[+-*/] n:[0-9]+
#include<stdio.h>
#include<stdlib.h>
#include<sys/mman.h>
typedef long long I;typedef char C,*S;
#define O(x...) printf(x),fflush(stdout)
#define R return
#define Z static
#define CASE(x,y...) case x:{y;}break;
#define PE(x) if((x)<0)perror("pe"),exit(2)
S m,m0;
I exe(){m=m0;asm("call *%0;"::"g"(m0):);}
S repl()
{I c=' ';I d(){R c==EOF?exit(1),0:(c=getchar());}
 I sp(){while(c==' ')d();}
 I no(){I i=0,k=0;while(c>='0'&&c<='9')k=1,i=i*10+c-'0',d();R k?i:-1;}
 I wi(I x){*(I*)m=x;m+=8;}
 I ws(S x){while(*x)*m++=*x++;}
 I cc()
 {ws("\x48\x89\xe5");
  while(c!='\n')
  {I i;sp();
   if((i=no())>=0)ws("\x48\xb8"),wi(i);else
   {ws("\x58\x5b");
    switch(c){CASE('+',ws("\x48\x01\xd8"))
              CASE('-',ws("\x48\x29\xd8"))
              CASE('*',ws("\x48\x0f\xaf\xc3"))
              CASE('/',ws("\x48\x99\x48\x89\xec"))
              default:O("'lex\n"),exit(1);
             }d();
   }ws("\x50");sp();
  }ws("\x48\x89\xec");ws("\xc3");
 }

 while(O(">"),d(),c!=EOF){cc();O("%lld\n",exe());}
}

I main(I c,S*v)
{I n=1<<20;PE(m0=m=mmap(NULL,n,7,0x22,0,0));repl();}

//RPN compiler: E:EEf|n f:[+-*/] n:[0-9]+

#include<stdio.h>

#include<stdlib.h>

#include<sys/mman.h>

typedef long long I;typedef char C,*S;

#define O(x...) printf(x),fflush(stdout)

#define R return

#define Z static

#define CASE(x,y...) case x:{y;}break;

#define PE(x) if((x)<0)perror("pe"),exit(2)

S m,m0;

I exe(){m=m0;asm("call *%0;"::"g"(m0):);}

S repl()

{I c=' ';I d(){R c==EOF?exit(1),0:(c=getchar());}

I sp(){while(c==' ')d();}

I no(){I i=0,k=0;while(c>='0'&&c<='9')k=1,i=i*10+c-'0',d();R k?i:-1;}

I wi(I x){*(I*)m=x;m+=8;}

I ws(S x){while(*x)*m++=*x++;}

I cc()

{ws("\x48\x89\xe5");

while(c!='\n')

{I i;sp();

if((i=no())>=0)ws("\x48\xb8"),wi(i);else

{ws("\x58\x5b");

switch(c){CASE('+',ws("\x48\x01\xd8"))

CASE('-',ws("\x48\x29\xd8"))

CASE('*',ws("\x48\x0f\xaf\xc3"))

CASE('/',ws("\x48\x99\x48\x89\xec"))

default:O("'lex\n"),exit(1);

}d();

}ws("\x50");sp();

}ws("\x48\x89\xec");ws("\xc3");

}

while(O(">"),d(),c!=EOF){cc();O("%lld\n",exe());}

}

I main(I c,S*v)

{I n=1<<20;PE(m0=m=mmap(NULL,n,7,0x22,0,0));repl();}

reverse polish calculator in gcc

gcc makes it possible to code this RPN interpreter more compactly than C89..C11

//RPN calculator: E:EEf|n f:[+-*/] n:[0-9]
typedef int I;typedef long J;typedef char C,*S;typedef J(*F)(J*);I printf(S,...);I(*O)(S,...)=printf;
#define R return
#define W(x,y...) while(x){y;}
#define K(m) m(+)m(-)m(*)m(/)
#define L(o) ""#o
#define M(o) ({J _f(J*x){R x[0] o x[1];}_f;}),
I main(I c,S*v)
{if(c!=2)R O("use: %s 12+3-\n",*v);
 J s[99],*t=s;;J push(J x){R *t++=x;}J*pop(I n){R t-=n;}J jsc(S s,C c){S t=s;W(*t&&c!=*t,t++)R t-s;}
 C o[]=K(L);F f[]={K(M)0};S e=v[1];W(*e,push(*e>47?*e-'0':f[jsc(o,*e)](pop(2))),e++)R O("%ld\n",*pop(1));
}

//RPN calculator: E:EEf|n f:[+-*/] n:[0-9]

typedef int I;typedef long J;typedef char C,*S;typedef J(*F)(J*);I printf(S,...);I(*O)(S,...)=printf;

#define R return

#define W(x,y...) while(x){y;}

#define K(m) m(+)m(-)m(*)m(/)

#define L(o) ""#o

#define M(o) ({J _f(J*x){R x[0] o x[1];}_f;}),

I main(I c,S*v)

{if(c!=2)R O("use: %s 12+3-\n",*v);

J s[99],*t=s;;J push(J x){R *t++=x;}J*pop(I n){R t-=n;}J jsc(S s,C c){S t=s;W(*t&&c!=*t,t++)R t-s;}

C o[]=K(L);F f[]={K(M)0};S e=v[1];W(*e,push(*e>47?*e-'0':f[jsc(o,*e)](pop(2))),e++)R O("%ld\n",*pop(1));

}

call functions on the run – x86_64

It doesn’t take much to call an x86_64 function by its address and an array of arguments. The technique is useful for implementing interpreters or responding to remote procedure calls. Supports 4 args, but can be completed by adding rcx, r8, r9. Extend using XMM floating point registers.

//x86_64 ABI - include this file for call and vcall.  gcc -DTEST x.c && ./a.out  (c) 2016 jack andrews
#define _GNU_SOURCE 
#include<stdarg.h>
#include<stdio.h>
#include<stdlib.h>
#define R return
#define _ static inline
typedef int I;typedef long J;typedef void V;typedef char*S;
_ J call(V*f,J n,V*a)
{J r;switch(n)
#define M(x,b) case x:asm ("movq %0,%%r"#b";"::"g"(((J*)a)[x-1]):"%r"#b)
 {M(4,cx);M(3,dx);M(2,si);M(1,di);case 0:asm ("push %%rbp;call *%1;pop %%rbp":"=a"(r):"g"(f):);break;default: R *(J*)0;
}}
_ J vcall(V*f,V*x,V*y,...){J r;va_list l;va_start(l,y);V*a[]={x,y,l};r=call(f,3,a);va_end(l);R r;}
#ifdef TEST
#define A(x,y) {I r;if(x!=(r=y))exit(fprintf(stderr,"line %d ?%d\n",__LINE__,r));}
J O2(S x,S y){R (J)fprintf(stdout,x,y);}
I main()
{S t;I x=call(atol,1,(S[]){"32"});
 A(2,vcall(vasprintf,&t,"%ld",x))
 A(3,call(O2,2,(S[]){"%s\n",t})) /*expect 32*/
 free(t);R 0;
}
#endif

#define _GNU_SOURCE

#include<stdarg.h>

#include<stdio.h>

#include<stdlib.h>

#define R return

#define _ static inline

typedef int I;typedef long J;typedef void V;typedef char*S;

_ J call(V*f,J n,V*a)

{J r;switch(n)

#define M(x,b) case x:asm ("movq %0,%%r"#b";"::"g"(((J*)a)[x-1]):"%r"#b)

{M(4,cx);M(3,dx);M(2,si);M(1,di);case 0:asm ("push %%rbp;call *%1;pop %%rbp":"=a"(r):"g"(f):);break;default: R *(J*)0;

}}

_ J vcall(V*f,V*x,V*y,...){J r;va_list l;va_start(l,y);V*a[]={x,y,l};r=call(f,3,a);va_end(l);R r;}

#ifdef TEST

#define A(x,y) {I r;if(x!=(r=y))exit(fprintf(stderr,"line %d ?%d\n",__LINE__,r));}

J O2(S x,S y){R (J)fprintf(stdout,x,y);}

I main()

{S t;I x=call(atol,1,(S[]){"32"});

A(2,vcall(vasprintf,&t,"%ld",x))

A(3,call(O2,2,(S[]){"%s\n",t})) /*expect 32*/

free(t);R 0;

}

#endif

June 2017
M	T	W	T	F	S	S
« May
			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