AutoHotkey Community

It is currently May 26th, 2012, 5:30 pm

All times are UTC [ DST ]




Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: BitRotate functions
PostPosted: April 16th, 2009, 5:53 pm 
Offline
User avatar

Joined: September 8th, 2008, 12:26 am
Posts: 1048
Location: Ploieşti, RO
Dunno if anyone will ever need such function but I did, recently, when trying to deal with an encryption system, so I had to quickly put it together. The code is probably ugly and unoptimized, may even contain bugs since it has only been tested with BYTEs.

Anyway, what does it do? It rotates (do not confuse with shifting) the bits in a certain given number, according to the options. Default is one rotation and number type is BYTE (UChar). The function only deals with unsigned values.

• Rotation can be 1 to 63 times (there's no type-specific upper limit yet).
• Types can be UChar (8bit), UShort (16bit), UInt (32bit) and UInt64 (64bit).
• There are separate functions for Left and Right rotation.
• Syntax is simple:
BitRotateL(number, times, type) or
BitRotateR(number, times, type)

The code below includes a graphical example of the functions, for better understanding. It requires a couple of maybe uncommon fonts: Webdings and Wingdings 2, so if you see letters instead of circles and numbered pool-like balls, you need those fonts.

I hope someone would find this useful.

Code:
; BitRotate functions
; by Drugwash April 2009
; v1.3

count := "{zyxwvut"
Gui, Add, Edit, x5 y5 w20 h20 gchar vch Limit1
Gui, Add, Text, x+3 yp+3 w20 h20 vdn, %dec%
Gui, Add, Text, x+3 yp w30 h20 vhn, %hex%
Gui, Font, s36
Gui, Add, Text, x+10 yp w80 h40 vsb,
Gui, Font, s12, Webdings
Gui, Add, Button, x5 y30 w20 h20 glshift, % Chr(51)
Gui, Add, Button, x+3 yp w20 h20 gnoshift, % Chr(60)
Gui, Add, Button, x+3 yp w20 h20 grshift, % Chr(52)
Gui, Font, s14, Wingdings 2
Gui, Add, Text, x5 y+5 w140 h20 vbytes, %byte%
Gui, Add, Text, xp y+1 w140 h20, %count%
Gui, Font
Gui, Show
return

char:
Gui, Submit, NoHide
dec := Asc(ch)
num := dec
GuiControl,, dn, %dec%
format:
SetFormat, Integer, Hex
hex := num
hex += 0
GuiControl,, hn, %hex%
sb := dec
sb += 0
GuiControl,, sb, %sb%
SetFormat, Integer, Dec
byte=
   Loop, 8
      {
      bit := (dec & 2**(8-A_Index)) ? Chr(152) : Chr(153)
         byte := byte . bit
      }
GuiControl,, bytes, %byte%
return

lshift:
BitRotateL(dec)
goto format
return

rshift:
BitRotateR(dec)
goto format
return

noshift:
dec := num
goto format
return

GuiClose:
ExitApp

BitRotateL(ByRef nmb, t="1", type="UChar")
{
r := BRCheck(t, type)
if !r
   return 0
Loop, %t%
   {
   msb := (nmb & 2**(r-1)) ? 1 : 0         ; 2^(r-1) should be the leftmost bit
   nmb := (nmb << 1 & (2**r -1)) + msb   ; 2^r-1 should be number's bytes less extra byte
   }
return 1
}

BitRotateR(ByRef nmb, t="1", type="UChar")
{
r := BRCheck(t, type)
if !r
   return 0
Loop, %t%
   {
   lsb := (nmb & 0x1) ? 2**(r - 1) : 0   ; 2^(r-1) should become the leftmost bit
   nmb := (nmb >> 1) + lsb
   }
return 1
}

BRCheck(a, b)
{
if (a < 1 || a > 63 || b not in UChar,UShort,UInt,UInt64)
   return 0
str = UChar|UShort|UInt|UInt64
Loop, Parse, str, |
   {
   ; find number length in bits
   if (A_LoopField == b)
      {
      mT := 4*(2**A_Index)
      break
      }
   }
return mT
}


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 3:16 am 
Offline

Joined: July 21st, 2006, 12:26 am
Posts: 223
pretty useful, thanks for sharing.

in the seek for the holy grail of perfomance, i was waiting for a native solution (autoit has it)

_________________
                                  [ profile | ahk.net | ahk.talk ]


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 8:10 am 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
Nice! You could compare the speed with the machine code functions, which were posted for 32 and 64 bit rotations here. In the MD5 script the following 32-bit left-rotation function is used:
Code:
rotate(a,b) { ; 32-bit rotate a to left by b bits, bit32..63 garbage
   Return a << b | (a & 0xFFFFFFFF) >> (32-b)
}
You can use any data size (<63 bit) similarly, with masking the result to the desired length. Something like this
Code:
rotate(a,b,n=8) { ; rotate a to left by ±b bits, n bit precision
   b := (b<0)*n+mod(b,n), m := (1<<n)-1
   Return (a << b) & m | a >> (n-b)
}
A rotation to the left by –b bits is the same as rotation to the right by +b bits. The value b can even be larger than the word length.


Last edited by Laszlo on April 17th, 2009, 8:17 am, edited 1 time in total.

Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 8:17 am 
Offline
User avatar

Joined: September 8th, 2008, 12:26 am
Posts: 1048
Location: Ploieşti, RO
Glad to know someone finds it useful. :)

I was strongly considering ASM for this function since it's ridiculously simple (RCL/RCR) but I'm not familiar with ASM embedding in AHK. Will snoop around though.

EDIT
Haha!! Laszlo and I are on the same frequency. :D


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 7:06 pm 
Offline
User avatar

Joined: September 8th, 2008, 12:26 am
Posts: 1048
Location: Ploieşti, RO
Hmm, for some reason I can't get the default ROL32/ROR32 machine code functions in Laszlo's thread to work. They always return the same number as the input. :?

CPU is Intel PIII. The 64bit rotations do work.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 7:34 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
What are the results of the posted test cases?
Code:
MCode(ROL32,"5589E58B45088B4D0C5DD3C0C3") ; Rotate Left  32 bits (unsigned)
MCode(ROR32,"5589E58B45088B4D0C5DD3C8C3") ; Rotate Right 32 bits (unsigned)

SetFormat IntegerFast, Hex
MsgBox % dllcall(&ROL32, "uint", 0x12345678, "UInt",4, "cdecl uint") ; 0x23456781
MsgBox % dllcall(&ROR32, "uint", 0x12345678, "UInt",4, "cdecl uint") ; 0x81234567

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")
}
You can test other shift values, too:
Code:
Loop {
   MsgBox % dllcall(&ROL32, UInt,0x12345678, UInt,A_Index-1)
   MsgBox % dllcall(&ROR32, UInt,0x12345678, UInt,A_Index-1)
}


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 8:04 pm 
Offline
User avatar

Joined: September 8th, 2008, 12:26 am
Posts: 1048
Location: Ploieşti, RO
I'm a little confused on the syntax. In my tests I had:
MsgBox % DllCall(&ROL32, "UInt", nmb, "cdecl UInt")
MsgBox % DllCall(&ROL64, "UInt", nmb, "cdecl UInt64")

The 64bit function worked, the 32bit one didn't. I notice an extra parameter in the above example, the UInt 4. I then tested:
MsgBox % DllCall(&ROL32, "UInt", nmb, "UInt", 4, "cdecl UInt")
and it worked. So how come this difference in syntax? What am I missing?

I've been looking over the timings mentioned here; I believe RCL/RCR would be needed for 64bit operations on 32bit CPUs, while ROL/ROR can safely be used for 32bit and lower operations. It's been a year since I last played with ASM and already forgot the little I managed to learn at the time. Would something like this work (in Borland ASM code)?
Code:
; 8bit rotation
MOV AL, buffer
MOV CL, times
ROL AL, CL
MOV BYTE PTR [buffer], AL
RET

; 16bit rotation
MOV AX, buffer
MOV CL, times
ROL AX, CL
MOV WORD PTR [buffer], AX
RET

; 32bit rotation
MOV EAX, buffer
MOV CL, times
ROL EAX, CL
MOV DWORD PTR [buffer], EAX
RET

buffer=999 ; the number to operate on
times=7 ; rotations count


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 8:18 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
If you omit the second parameter (the number of bit positions to shift), the function takes whatever number is in the unwritten stack position. In some OS versions your script could crash or cause a runtime error.

I don't know much about assembler syntax. The code samples were mostly compiled C code.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 8:44 pm 
Offline
User avatar

Joined: September 8th, 2008, 12:26 am
Posts: 1048
Location: Ploieşti, RO
You're referring to the examples I posted just above your post, right? Here's a quote from the page I linked to above:
Quote:
The destination operand can be a register or a memory location; the count operand is an unsigned integer that can be an immediate or a value in the CL register. The processor restricts the count to a number between 0 and 31 by masking all the bits in the count operand except the 5 least-significant bits.
So there should be no problem. In fact, by omitting that parameter, I think it automatically set the count to zero, since the number was unchanged.

However, it's possible that newer CPUs may have modified instructions; I'm thinking of 64bit CPUs that should (theoretically) allow 0 to 63 rotations. I could be wrong all along though.

The ASM operations are simple:
- copy the number from its buffer to the AL/AX/EAX register
- copy the count to the CL register
- perform byte rotation on the AL/AX/EAX register
- copy the result back to the number's buffer

The usage of registers saves a few CPU clocks and shortens the code by a byte or two.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 17th, 2009, 9:38 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
Drugwash wrote:
by omitting that parameter, I think it automatically set the count to zero
No. AHK pushes all the parameters on the stack. The ROL32 function takes the values at the two topmost stack positions, and uses them, but if you specify only one parameter in the dllcall, the second one will be missing. ROL32 does not know it, it takes the number it thinks the second parameter is, but it could be part of the return address or something else, what happens to be in the place, where the second parameter should have been copied.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: April 18th, 2009, 8:54 am 
Offline
User avatar

Joined: September 8th, 2008, 12:26 am
Posts: 1048
Location: Ploieşti, RO
Ah OK, so it was merely a concidence that the output was indentical to the input.

If I may, it might be a good idea to add these details to the first post in the Machine Code topic, for each function, so interested users wouldn't make the same mistake as I did.


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: XX0, Yahoo [Bot] and 14 guests


You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group