Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

Machine code functions: Bit Wizardry


  • Please log in to reply
144 replies to this topic
Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
As it stands now, MP_Init() needs only set up the machine code functions, stored in global variables. They only occupy a few dozen bytes, so there is no need to clear these variables: their names cannot be removed from the list of variables, anyway.

When the MP_ library is in a state to be beta tested, I will think about packaging it nicely. For this pre-alpha state a stand alone test script is good enough. Nevertheless, if anyone has a suggestion, I will consider it.

daniel2
  • Members
  • 47 posts
  • Last active: Oct 05 2008 07:05 PM
  • Joined: 23 Jul 2007
This is amazingly brillant! :D

long integer arithmetic is a perfect candidate for machine code implementation

Would encryption algorithms be another good application for this?

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005

Would encryption algorithms be another good application for this?

I am not sure. Microsoft includes AES with key management and hashing in its crypto library, which is installed automatically, at least in newer Windows versions. The necessary functions in machine code format could be several pages long, which makes the scripts ugly and slow to load.

On the other hand, XTEA (my favorite) could be coded in a couple hundred bytes, and it is secure enough for personal use. There are others, less well analyzed ciphers of even smaller code size, so your suggestion could make sense, after all.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
See here the CPUID function, which is a 27 byte AHK machine code wrapper for the CPUID command of Intel compatible processors. It tells everything about the CPU, its capabilities, version number, unique ID, etc. See here the returned values for different first parameter (the info selector).

daonlyfreez
  • Members
  • 995 posts
  • Last active: Jan 23 2013 08:16 AM
  • Joined: 16 Mar 2005
Very interesting.

It returns "AuthenticAMD" on my machine, yet no further information about Family/Model/Revision. Could this be implemented too?

8)
Posted Image mirror 1mirror 2mirror 3ahk4.me • PM or Posted Image

olfen
  • Members
  • 115 posts
  • Last active: Dec 25 2012 09:48 AM
  • Joined: 04 Jun 2005
Hi,
I compiled this XTEA c code into a dll using gcc\MinGW:
#include <stdio.h>

#ifdef BUILD_DLL
// the dll exports
#define EXPORT __declspec(dllexport)
#else
// the exe imports
#define EXPORT __declspec(dllimport)
#endif

EXPORT void XTEA_encipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long sum=0, delta=0x9E3779B9;
    for(i=0; i<num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

EXPORT void XTEA_decipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long delta=0x9E3779B9, sum=delta*num_rounds;
    for(i=0; i<num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

and to my absolute surprise (hardly knowing c or asm) it seems to work.
But does it actually do proper XTEA, the way I DllCall it?
MCode(ByRef code, hex) { ; allocate memory and write Machine Code there
   VarSetCapacity(code,StrLen(hex)//2)
   Loop % StrLen(hex)//2
      NumPut("0x" . SubStr(hex,2*A_Index-1,2), code, A_Index-1, "Char")
}


XTEA_encipher := "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745EC00000000C745E8B979379EC7"
. "45F0000000008B45F03B4508737D8B45F489C2C1E2048B45F4C1E80531D089C3035DF48B45EC83E0038D0C85000000008"
. "B55108B45EC03041189DA31C28D45F801108B55E88D45EC01108B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45"
. "ECC1E80B83E0038D0C85000000008B55108B45EC03041189DA31C28D45F401108D45F0FF00E97BFFFFFF8B550C8B45F88"
. "9028B550C83C2048B45F4890283C4145B5DC3"

XTEA_decipher := "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745ECB979379E8B45EC0FAF450889"
. "45E8C745F0000000008B45F03B4508737D8B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45E8C1E80B83E0038D0"
. "C85000000008B55108B45E803041189DA31C28D45F429108B55EC8D45E829108B45F489C2C1E2048B45F4C1E80531D089"
. "C3035DF48B45E883E0038D0C85000000008B55108B45E803041189DA31C28D45F829108D45F0FF00E97BFFFFFF8B550C8"
. "B45F889028B550C83C2048B45F4890283C4145B5DC3"

MCode(enc, XTEA_encipher)
MCode(dec, XTEA_decipher)

; 128 bit key
VarSetCapacity(k, 16, 0)
NumPut(0x11111111, k,  0, "UInt")
NumPut(0x22222222, k,  4, "UInt")
NumPut(0x33333333, k,  8, "UInt")
NumPut(0x44444444, k, 12, "UInt")


v = Tiny !!! ; 64 bit
DllCall(&enc, int,64, uint,&v, uint,&k)
MsgBox % v
DllCall(&dec, int,64, uint,&v, uint,&k)
MsgBox % v


VarSetCapacity(v, 8, 0) ;64 bit
NumPut(1122334455667788, v, 0, "Double")
MsgBox % NumGet(v, 0, "Double")
DllCall(&enc, int,64, int,&v, int,&k)
MsgBox % "Enc: " . NumGet(v, 0, "Double")
DllCall(&dec, int,64, int,&v, int,&k)
MsgBox % "Dec: " . NumGet(v, 0, "Double")


Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
This is great! I always wanted to code XTEA, but did not have time. Thanks!

Now we can have lightning fast cryptographically secure random number generators and encrypt messages, files at high speed.

I compared it to a Python implementation. A test case gave identical result, so we can be pretty certain that the code is OK.
MCode(enc, "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745EC00000000C745E8B979379EC7"
. "45F0000000008B45F03B4508737D8B45F489C2C1E2048B45F4C1E80531D089C3035DF48B45EC83E0038D0C85000000008"
. "B55108B45EC03041189DA31C28D45F801108B55E88D45EC01108B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45"
. "ECC1E80B83E0038D0C85000000008B55108B45EC03041189DA31C28D45F401108D45F0FF00E97BFFFFFF8B550C8B45F88"
. "9028B550C83C2048B45F4890283C4145B5DC3") ; #rounds, &data64, &key128

MCode(dec, "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745ECB979379E8B45EC0FAF450889"
. "45E8C745F0000000008B45F03B4508737D8B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45E8C1E80B83E0038D0"
. "C85000000008B55108B45E803041189DA31C28D45F429108B55EC8D45E829108B45F489C2C1E2048B45F4C1E80531D089"
. "C3035DF48B45E883E0038D0C85000000008B55108B45E803041189DA31C28D45F829108D45F0FF00E97BFFFFFF8B550C8"
. "B45F889028B550C83C2048B45F4890283C4145B5DC3")

MCode(k,11111111222222223333333344444444) ; 128 bit binary key <-- hex stream
v = Tiny !!!                  ; 8 Bytes = 64 bits
DllCall(&enc, int,64, uint,&v, uint,&k)
MsgBox % Bin2Hex(&v,8)        ; CF7B64A2AC2A9441
DllCall(&dec, int,64, uint,&v, uint,&k)
MsgBox % v                    ; original

k = 0123456789012345          ; key128 <-- string16
v = ABCDEFGH                  ; plaintext64 <-- string8
DllCall(&enc, int,32, uint,&v, uint,&k)
MsgBox % Bin2Hex(&v,8)        ; EA0C3D7C1C22557F: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496737
DllCall(&dec, int,32, uint,&v, uint,&k)
MsgBox % v


MCode(ByRef code, hex) { ; allocate memory and write Machine Code there
   VarSetCapacity(code,StrLen(hex)//2)
   Loop % StrLen(hex)//2
      NumPut("0x" . SubStr(hex,2*A_Index-1,2), code, A_Index-1, "Char")
}

Bin2Hex(addr,len) {
   Static fun
   If (fun = "") {
      h=8B4C2404578B7C241085FF7E2F568B7424108A06C0E8042C0A8AD0C0EA052AC2044188018A06240F2C0A8AD0C0EA052AC2410441468801414F75D75EC601005FC3
      VarSetCapacity(fun,StrLen(h)//2)
      Loop % StrLen(h)//2
         NumPut("0x" . SubStr(h,2*A_Index-1,2), fun, A_Index-1, "Char")
   }
   VarSetCapacity(hex,2*len+1)
   dllcall(&fun, "uint",&hex, "uint",addr, "uint",len, "cdecl")
   VarSetCapacity(hex,-1) ; update StrLen
   Return hex
}

XTEA works with 32-bit integers. We have a choice, how to encode them into byte streams. The MCode function uses big endian coding, that is, the most significant byte is written first, to the left (big end first = big endian). Others might use little endian encoding, which can present a problem if you want to exchange encrypted data or keys: you have to cut them into 4-byte chunks (8 hex digits), and reverse the byte order in these blocks.

The following function can come handy, in this case:
Hex2Ints(ByRef code, hex) { ; allocate memory and write little endian integers there
   VarSetCapacity(code, 4 * (n := ceil(StrLen(hex)/8)) )
   Loop %n%
      NumPut("0x" . SubStr(hex,8*A_Index-7,8), code, 4*A_Index-4, "UInt")
}
Another test case from the Python recipe:
>>> z = 'b67c01662ff6964a'.decode('hex')
>>> xtea_decrypt('0123456789012345',z)
'ABCDEFGH'
It can be coded in AHK the following way:
k = 3210765410985432          ; key128 <-- string16 (big endian: 0123456789012345)
Hex2Ints(v,"b67c01662ff6964a") ;compare decrypt to known value:
DllCall(&dec, int,32, uint,&v, uint,&k)
MsgBox % v                    ; DCBAHGFE (big endian: ABCDEFGH)
It also gives the right answer, providing another evidence that olfen's XTEA machine code functions are correct.


Base64 codec, CRC32 are two similar, very useful functions. Any takers?

CBC mode encryption/decryption with XTEA could also be used often. Larger data could be encrypted without AHK loops, the integrity of files could be verified, files could be compared, etc.

Edit 20070919: added notes about endiannes

majkinetor
  • Moderators
  • 4512 posts
  • Last active: May 20 2019 07:41 AM
  • Joined: 24 May 2006
Can this process of converting C function to hexa representation of machine code can be automated some way ?

For instance little converter that will take c function, compile it (lets say that tiny c compiler), disasm it, and give us just text to copy paste.
Posted Image

olfen
  • Members
  • 115 posts
  • Last active: Dec 25 2012 09:48 AM
  • Joined: 04 Jun 2005

Can this process of converting C function to hexa representation of machine code can be automated some way ?

For instance little converter that will take c function, compile it (lets say that tiny c compiler), disasm it, and give us just text to copy paste.

That should be feasible, but before posting corresponding code, I would like to test, if it is possible to directly get the machine code from a Dll via GetProcAddress and Laszlo's Bin2Hex.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Sure, it can be automated, but it is not that simple. I've found no way to force VS'05 or the gcc compiler to inline everything, and if it breaks up the code to subroutines, you have to manually patch the code with short relative addresses, etc. Or, tweak the source code, until it has no subroutines, external references. (I spent several days to code up the long integer division using floating point instructions: the compiler always wanted to call its static library functions.) TCC gives unnecessarily long source code (sometimes by a factor of 2 or more), so I turned to VS'05. It has a free version, you don't need a Unix box (like MinGW), its assembler syntax is much simpler…

I do use a few hotkeys, though. When the C function is compiled, a disassembler is called, its result is saved in a text file, opened in notepad, the function name is searched for, but I manually mark the instructions to the end of the function (there could be more than one returns). Another hotkey copies the instructions and converts them to hex streams, breaks it up to manageable length lines to be pasted in the AHK script. Learning all the quirks of the hotkeys takes more time than do the whole process manually, unless you plan to code dozens of machine code functions. Do you?

majkinetor
  • Moderators
  • 4512 posts
  • Last active: May 20 2019 07:41 AM
  • Joined: 24 May 2006
Or, tweak the source code, until it has no subroutines, external references.
I assumed c function doesn't depend on c stdlib nor it uses anything appart standard C language and/or API functions.

but I manually mark the instructions to the end of the function (there could be more than one returns)

Of course, but perhaps some other disam marks explicitely end of the function or you can put some special instruction before final ret and search for it.

Learning all the quirks of the hotkeys takes more time than do the whole process manually, unless you plan to code dozens of machine code functions. Do you?

Your hotkies are fine, but its your thing, and I don't want to learn them, I prefer more practical solution. I don't plan to create dozens of machine code functions now as I don't have practical way to do it, and its tiresome to do it all manualy, but If I have some nice automated script to do it for me, it would be nice and I would think about this solution for my projects much more.

So, lets analyse your routine.

When the C function is compiled, a disassembler is called, its result is saved in a text file, opened in notepad, the function name is searched for, but I manually mark the instructions to the end of the function

1. Have a GUI with HiEdit control to nicely color your C code. Besides it, have a button "2Hex"
2. When pressed 2Hex adds special instruction before closing bracket of the function, something that will be easily recognised (NOP maybe, perhaps something else, like some rarely used instruction..) then :
3. Compile using env variables for free MS compiler
4. Call dissassembler
5. Search the code for you function name and extract up to the special instruction + 1 line
6. Call ahk function (your current hotkey) that converts ASM instructions to text
Posted Image

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005

I assumed c function doesn't depend on c stdlib nor it uses anything appart standard C language and/or API functions.

Try a simple shift of a 64-bit number. The compiler includes several unnamed functions to the exe (or dll). There are no external references, these functions are in the code, but in different places. If you want machine code, you have to copy them after each other, and edit the addresses. It is hard and error prone.

2. When pressed 2Hex adds special instruction before closing bracket of the function, something that will be easily recognised (NOP maybe, perhaps something else, like some rarely used instruction..)

Unfortunately, the optimizer could remove unnecessary instructions, rearrange lines, writes some of its code after your marker instruction, etc. I could not make it work, but did not spend too much time with it. If someone can, it would be really useful to automate the process.

olfen
  • Members
  • 115 posts
  • Last active: Dec 25 2012 09:48 AM
  • Joined: 04 Jun 2005
I put together a script to get the machine code from a dll without using a disassembler. It works with the dll i made for implementing XTEA.
For getting enough offsets to calculate the length of the machine code to extract, the dummy function "add" was added.
The script will only work if the functions are stored consecutively in the dll.
Given the intricacies pointed out by Laszlo its usefullness is probably very limited. :?
hModule := DllCall("LoadLibrary", "str", "tst.dll")

Exports = add,XTEA_decipher,XTEA_encipher

Loop, parse, Exports, `,
{
  ExportsList .= DllCall("GetProcAddress", Uint,hModule, Str,A_LoopField) . "|" . A_LoopField . "`n"
  #Exports++
}

Sort, ExportsList
MsgBox % ExportsList
StringReplace, ExportsList, ExportsList, `n , |, All 
StringSplit, ex, ExportsList, |


tmp := #Exports
Loop % #Exports - 1
{
  b_ind := (tmp * 2) - 1
  b := ex%b_ind%
  
  a_ind := (tmp * 2) - 3
  a := ex%a_ind%
  
  len := b - a
  f_ind := b_ind - 1
  fn := ex%f_ind%
  MsgBox % fn . "`n`n" . Bin2Hex(a ,len)
  
  tmp--
}

DllCall("FreeLibrary", "UInt", hModule)




Bin2Hex(addr,len) { 
   Static fun 
   If (fun = "") { 
      h=8B4C2404578B7C241085FF7E30568B7424108A168AC2C0E804463C0976040437EB02043080E20F88018AC2413C0976040437EB0204308801414F75D65EC601005FC3 
      VarSetCapacity(fun,StrLen(h)//2) 
      Loop % StrLen(h)//2 
         NumPut("0x" . SubStr(h,2*A_Index-1,2), fun, A_Index-1, "Char") 
   } 
   VarSetCapacity(hex,2*len+1) 
   dllcall(&fun, "uint",&hex, "uint",addr, "uint",len, "cdecl") 
   VarSetCapacity(hex,-1) ; update StrLen 
   Return hex 
}


Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Added notes about data exchange between little endian and big endian XTEA implementations.

majkinetor
  • Moderators
  • 4512 posts
  • Last active: May 20 2019 07:41 AM
  • Joined: 24 May 2006
2Laszlo

I forgot for a second the fact that compilers do mass of things on their own and look at the things too optmisiticaly.

About funny instruction, its just a matter of trial and error to see which instruction is the one that doesn't get touched by particular compiler, but give other reasons you gave, it looks like minor problem...

So, we basicly need something that will unite dependencies of a function, either by injection the code of referented functions into it or by including referenced code parts in text (which probably means fixing old addressses). Seems like a lot of things to do. Perhaps there is somewhere out, some utility doing such thing... :roll: or maybe some compiler with fancy options.
Posted Image