Sign in to follow this  
Followers 0
czardas

_InfiniteShift

11 posts in this topic

#1 ·  Posted (edited)

I found a bit of time today to write something, after criticism that people chatting don't write enough code. Well it's perhaps an old school concept, but I wanted to solve it myself. Logical shift on an infinite hex string. Well not really infinite, but it might as well be compared to the small 32/64-bit versions. Please note: it only shifts bits once. If you want an actual infinite shift value (not really recommended) then use a while loop.

Theoretically the code should run faster without calls to Int() , but this appears to be an unfortunate consequence of unfinished development. Don't ask me why that is, because I don't have an answer. Anyway forget that! This function might have been more useful to me about a year ago, but it was fun to figure out how to do it today anyway.

IMPROVED VERSION IN >POST 8

;

Original code

; #FUNCTION# ====================================================================================================================
; Name...........: _InfiniteShift
; Description ...: Shifts all bits one step to the right (or left) in a Hexadecimal string of any length greater than zero.
; Syntax.........: _InfiniteShift($dHex [, $bRightShift = True ])
; Parameters ....: $dHex        - Hexadecimal Input
;                ; $bRightShift - [Optional] Bits shift to the right by default. To shift left, set $bRightShift to False.
; Return values .: Success   - Returns a hexadecimal string with bits shifted one way or the other.
;                  Failure   - Sets @error to 1 if the input contains non-hexadecimal characters.
; Author ........: czardas
; Modified.......:
; Remarks .......: This function performs a logical shift - the return string will be the same length as the original.
; Example .......: ConsoleWrite(_InfiniteShift("BABBA6EBABBA6EBABBA6EBABBA6EBABBA6EBABBA6E") & @LF)
; ===============================================================================================================================

Func _InfiniteShift($dHex, $bRightShift = True)
    If Not StringIsXDigit($dHex) Then Return SetError(1)

    Local $dTargetHx, $dAdjacentHx, $dShiftedHx = ""
    If $bRightShift Or $bRightShift = Default Then
        ; Right Shift
        $dHex = '0' & $dHex
        For $i = 2 To StringLen($dHex)
            $dTargetHx = StringMid($dHex, $i, 1)
            $dAdjacentHx = StringMid($dHex, $i -1, 1)
            $dShiftedHx &= Hex(Int(Floor(Dec($dTargetHx)/2) + Mod(Dec($dAdjacentHx), 2) *8), 1)
        Next

    Else
        ; Left Shift
        $dHex = $dHex & '0'
        For $i = 1 To StringLen($dHex) -1
            $dTargetHx = StringMid($dHex, $i, 1)
            $dAdjacentHx = StringMid($dHex, $i +1, 1)
            $dShiftedHx &= Hex(Int(Mod(Dec($dTargetHx), 8) *2 + (Dec($dAdjacentHx) > 7)), 1)
        Next
    EndIf

    Return $dShiftedHx
EndFunc

Edited by czardas

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

Your problem is that you are using floating point operations when you really don't need to.

For example Floor($n / 2) is equivalent to BitShift($n, 1), without the need for floats to be involved at all. Calls to Int() are the least of your concerns with performance when you are doing conversions to floating point and doing division by 2 like that. Also, with Mod($n, power of 2) you could do it with BitAND($n, power of 2 - 1) for consistency.

Also, it would be considerably faster if done in batches. For doing it in sets of 4, only shifting left, I'd use something like:

Local $a = "123456789ABCDEF"

ConsoleWrite(_Shift($a) & @LF)


; Shift digits to left.
Func _Shift($s)
    Local $sRet = ""
    Local $0s = ["", "000", "00", "0"]

    $s = $0s[BitAND(StringLen($s), 3)] & StringUpper($s)

    Local $cf = 0, $d
    For $i = StringLen($s)-3 To 1 Step -4
        $d = BitShift(Dec(StringMid($s, $i, 4)), -1) + $cf
        $cf = BitShift($d, 16)
        $d = BitAND($d, 0xFFFF)

        $sRet = Hex($d, 4) & $sRet
    Next

    If $cf Then $sRet = Hex($cf, Log($cf) / Log(16) + 1) & $sRet

    Return $sRet
EndFunc   ;==>_Shift

Matt

Edit: And, as final note, if you do want very large shift (i.e., greater than 4) then you can recognise that a shift of 4 just shifts all the digits in hex, so at most you will need to do a shift of 3 with a StringTrimRight in the case of right shifts, or just adding zeros for left shift.

Edited by Mat

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

I wrote a long responce to this, but knoppix crashed before I posted it. Anyway, thanks for the example. I forgot I could shift less than a byte with BitShift() DUH! I don't use BitShift() much because I find it extremely limited, which is the reason I made that mistake.

Regarding the floating point stuff, I wrote the code with version 3.3.6.1 and added Int() to make it compatible with the latest release. This is useful to me at least because I am discovering more about the internal changes in AutoIt. Floor() also seems to be behaving differently. It seemed I needed to add Int() in the 'Left Shift' part of my code too, but I could have made a mistake when testing. I don't see any floating point stuff there at all: Mod(Dec($dTargetHx), 8). I need to fully test all maths functions to fully understand the consequences of the internal changes.

Your example is obviously faster. I did have to modify your code slightly: I don't know if this is a consequence of using an older AutoIt version.

;

; Shift digits to left.
Func _Shift($s)
    Local $iLen = StringLen($s) ; ADDED
    Local $sRet = ""
    Local $0s = ["", "000", "00", "0"]

    $s = $0s[BitAND(StringLen($s), 3)] & StringUpper($s)

    Local $cf = 0, $d
    For $i = StringLen($s)-3 To 1 Step -4
        $d = BitShift(Dec(StringMid($s, $i, 4)), -1) + $cf
        $cf = BitShift($d, 16)
        $d = BitAND($d, 0xFFFF)

        $sRet = Hex($d, 4) & $sRet
    Next

    If $cf Then $sRet = Hex($cf, Log($cf) / Log(16) + 1) & $sRet

    Return StringRight($sRet, $iLen) ; MODIFIED
EndFunc   ;==>_Shift

;

I can't say I fully understand it, but I'm happy you posted it. :)

Edited by czardas

Share this post


Link to post
Share on other sites

Your linux box crashed?  during normal operation?  You will be kicked out of Linus' club for revealing that to Windows users.


,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)

Share this post


Link to post
Share on other sites

Actually I was trying to read an au3 file at the time. I have a suspicion why it crashed though: live DVD running through USB 2.0 - disc read error!

Share this post


Link to post
Share on other sites

Ah yes, there will be leading zeros with my sample, as I add leading to the input string to make it a bit easier. Your solution won't quite be right though when carry is used and digits are added. If you were to do the StringRight before the If $cf Then ... it should work.

It wasn't so much the Mod that I was referring to when I was talking about doing floating point arithmetic. Floor() is a floating point function, and division (as you know from recent discussions) is also always floating point. Whenever you do either of those, AutoIt will assume you wanted to do maths with floats, and so do the conversion. 

ConsoleWrite(_Shift("FFFF") & ", " & Hex(0xFFFF*2, 5) & @LF)
ConsoleWrite(_Shift("FF") & ", " & Hex(0xFF*2, 3) & @LF)


; Shift digits to right.
Func _Shift($s)
    Local $sRet = ""
    Local $0s = ["", "000", "00", "0"]
    Local $lenS = StringLen($s)

    $s = $0s[BitAND($lenS, 3)] & StringUpper($s)

    Local $cf = 0, $d
    For $i = StringLen($s)-3 To 1 Step -4
        $d = BitShift(Dec(StringMid($s, $i, 4)), -1) + $cf
        $cf = BitShift($d, 16)
        $d = BitAND($d, 0xFFFF)

        $sRet = Hex($d, 4) & $sRet
    Next

    If $cf Then
        $sRet = Hex($cf, Log($cf) / Log(16) + 1) & $sRet
    Else
        $sRet = StringTrimLeft($sRet, 3 - Int(Log($d) / Log(16)))
    EndIf

    Return $sRet
EndFunc   ;==>_Shift

To better understand the code, consider what happens if it was only done in batches of 1.

Func _Shift($s)
    Local $sRet = ""

    Local $cf = 0, $d
    For $i = StringLen($s) To 1 Step -1
        $d = BitShift(Dec(StringMid($s, $i, 1)), -1) + $cf
        $cf = BitShift($d, 4)
        $d = BitAND($d, 0xF)

        $sRet = Hex($d, 1) & $sRet
    Next

    If $cf Then $sRet = Hex($cf, Log($cf) / Log(16) + 1) & $sRet

    Return $sRet
EndFunc   ;==>_Shift

For each digit, shift that digit left 1, and add the carry. The next digit on the output will be whatever fits into a hex char, and the carry will be set to the rest.

So if the digit is "F" (15), we shift left 1, and add the carry (0), to get 0x1E, the next digit in the output will be "E", and the carry is set to 0x1.

Share this post


Link to post
Share on other sites

#7 ·  Posted (edited)

Floor() is a floating point function, and division (as you know from recent discussions) is also always floating point. Whenever you do either of those, AutoIt will assume you wanted to do maths with floats, and so do the conversion. 

 

To assume that Floor() means you want to do floating point maths seems horribly insane to me. Floor() always used to return a 32-bit integer - when within range. It took me a long time to get my head around these maths functions and what they do. The internal changes are really complicated, and updating all of my projects is a daunting prospect.

To better understand the code, consider what happens if it was only done in batches of 1.

 

Not unlike my original slow version, which was so educational for me having parsed it the way I did. I'm happy knowing the method is only four times slower than yours. With a few tweaks, 28-bit sections can be shifted (1 nibble has to be reserved) and the rejoining intersections parsed by one of the methods above. The difference should be quite minimal.

I understood the principle of your method Mat, but your variable names are a little vague. What is $cf? (Oh now I get it). I don't get where the logs come into play neither - but that's partly down to my lack of need to use logs, so I'm not accustomed to using them (although I understand the principle - we used log tables at school).  :think: I ought to use them more often.

Please don't think I don't appreciate your input - it's educational. However I didn't think too deeply when I wrote this. I had intended to keep the code quite simple. You have demonstrated how it can be optimized. :)

Edited by czardas

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

Following Mat's guidance, I made some improvements. Here's the result.

;

Local $sTest = "00000005D5DD3700000000"
For $i = -53 To 55 Step 4
    ConsoleWrite(InfiniteShift($sTest, $i) & @LF)
Next

; #FUNCTION# ====================================================================================================================
; Name...........: InfiniteShift
; Description ...: Shifts all bits to the right (or left) in a Hexadecimal string of any length.
; Syntax.........: InfiniteShift($dHex, $iShift)
; Parameters ....: $dHex   - Hexadecimal Input
;                ; $iShift - The number of places to shift bits right. Negative values shift bits to the left.
; Return values .: Success - Returns a hexadecimal string with bits shifted one way or the other.
;                  Failure - Sets @error to 1 if the input contains non-hexadecimal characters
; Author ........: czardas
; Modified.......:
; Remarks .......: This function performs a logical shift - the return string will be the same length as the original.
; Example .......: ConsoleWrite(InfiniteShift("BABBA6EBABBA6EBABBA6EBABBA6EBABBA6EBABBA6E", 42) & @LF)
; ===============================================================================================================================

Func InfiniteShift($dHex, $iShift)
    If Not StringIsXDigit($dHex) Then Return SetError(1)
    $iShift = Int($iShift)
    If $iShift = 0 Then Return SetExtended(1, $dHex)

    Local $dPadding = '0', $iHexShift = Floor(Abs($iShift)/4) ; Whole nibbles to shift.
    While StringLen($dPadding) < $iHexShift
        $dPadding &= $dPadding
    WEnd
    $dPadding = StringLeft($dPadding, $iHexShift) ; Padding can go on either side.
    $dHex = ($iShift > 0) ? StringLeft($dPadding & $dHex, StringLen($dHex)) : StringRight($dHex & $dPadding, StringLen($dHex))

    Local $iBitShift = Mod($iShift, 4) ; Shift value for bits range from 0 to 3.
    If $iBitShift = 0 Then Return $dHex

    Local $aHexPart = StringRegExp($dHex, "(?s).{1,7}", 3), $iBound ; Split to segments of between 1 and 7 nibbles.
    $iBound = UBound($aHexPart)

    If $iShift > 0 Then
        ; Shift right
        $aHexPart[0] = '0' & $aHexPart[0] ; Prefix an out of range zero.
        For $i = 1 To $iBound -1
            $aHexPart[$i] = StringRight($aHexPart[$i -1], 1) & $aHexPart[$i] ; Prefix the final nibble from each previous segment.
        Next
    Else
        ; Shift left
        For $i = 0 To $iBound -2
            $aHexPart[$i] &= StringLeft($aHexPart[$i +1], 1) ; Append the first nibble from each following segment.
        Next
        $aHexPart[$iBound -1] &= '0' ; Append an out of range zero.
    EndIf

    For $i = 0 To $iBound -2
        $aHexPart[$i] = Hex(BitShift(Dec($aHexPart[$i]), $iBitShift)) ; Shift the bits in each segment (32-bits or less).
    Next
    $aHexPart[$iBound -1] = Hex(BitShift(Dec($aHexPart[$iBound -1]), $iBitShift), StringLen($aHexPart[$iBound -1]))

    Local $dShiftedHex = ""
    ; Remove the nibbles added earlier before rejoining the segments.
    If $iShift > 0 Then
        For $i = 0 To $iBound -1
            $dShiftedHex &= StringTrimLeft($aHexPart[$i], 1)
        Next
    Else
        For $i = 0 To $iBound -1
            $dShiftedHex &= StringTrimRight($aHexPart[$i], 1)
        Next
    EndIf

    Return $dShiftedHex
EndFunc ;==> InfiniteShift
Edited by czardas

Share this post


Link to post
Share on other sites

Floor() always used to return a 32-bit integer - when within range. It took me a long time to get my head around these maths functions and what they do. The internal changes are really complicated, and updating all of my projects is a daunting prospect.

What's changed with Floor()?

♡♡♡

.

eMyvnE

Share this post


Link to post
Share on other sites

czardas,

 

Floor() always used to return a 32-bit integer

And still does: ;)

$nNum = 3.142
$nFloor = Floor($nNum)
ConsoleWrite($nFloor & " - " & VarGetType($nFloor) & @CRLF)
>Running:(3.3.12.0):M:\Program\AutoIt3\autoit3.exe "M:\Program\Au3 Scripts\fred2.au3"    
--> Press Ctrl+Alt+F5 to Restart or Ctrl+Break to Stop
3 - Int32
M23

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

#11 ·  Posted (edited)

trancexx, all I know is my original code (working in 3.3.6.1) didn't seem to work with 3.3.8.1 without converting to Int after using Floor(). I just tested Floor() on 3.3.8.1 and on one of the earlier betas.

:

Local $iVar = Floor(1.5)
ConsoleWrite(VarGetType($iVar) & @LF)

With 3.3.8.1 I get Int64, and with 3.3.9.22 beta, I get Int32. In either case, I don't see why my code would not run. It's probably my mistake. I can't tell you what the current release does (Melba posts as I write). I intend to try the current version shortly. Notice I used your ternary operator in my last post. :) I think I need some practice with the new features before I dive in at the deep end.

Edited by czardas

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Similar Content

    • quickbeam
      By quickbeam
      The BitShift funtion apparently does sign extension for 32-bit numbers if the MSb is set.  Is there any way to turn that off and do real (C style) bit shifts?
       
    • czardas
      By czardas
      The shift value for BitShift is described as: (the) Number of bits to shift to the right (negative numbers shift left).

      BitRotate description gives: Performs a bit shifting operation, with rotation.
      The shift value for BitRotate is described as: (the) Number of bits to rotate to the left (negative numbers shift right).

      I noticed this apparent inconsistancy recently after so my question is this: Is there a hidden deeper meaning to this, or is it just a bit of mix up?

      It appears inconsistant (default) behaviour, to me at least.