_InfiniteShift

[czardas]

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

expandcollapse popup

; #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 June 10, 2014 by czardas

[Mat]

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 June 8, 2014 by Mat

[czardas]

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 June 8, 2014 by czardas

[iamtheky]

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

[czardas]

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!

[Mat]

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.

[czardas]

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).   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 June 10, 2014 by czardas

[czardas]

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

;

expandcollapse popup

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 June 10, 2014 by czardas

[trancexx]

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()?

[Melba23]

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

[czardas]

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 June 10, 2014 by czardas