Circular shift

Anything beyond the basics in using the LiveCode language. Share your handlers, functions and magic here.

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller, robinmiller

Ledigimate
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 132
Joined: Mon Jan 14, 2013 3:37 pm

Circular shift

Post by Ledigimate » Sun Dec 16, 2018 7:08 pm

Hi

I'm looking for a way to perform circular shift operations in LiveCode, like can be done in the C language using the bitwise operators << and >>. I could find only these four bitwise operators in the LC dictionary: bitAnd, bitOr, bitXor, and bitNot. Can someone point me in the right direction?

Gerrie
010100000110010101100001011000110110010100111101010011000110111101110110011001010010101101010100011100100111010101110100011010000010101101001010011101010111001101110100011010010110001101100101

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9580
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Circular shift

Post by dunbarx » Sun Dec 16, 2018 7:48 pm

Do you mean something like this, if you had, say, the string "A,B,C,D,E" and wanted "B,C,D,E,A"?

You could, assuming that you have a string in a field 1 and the comma is the item delimiter

Code: Select all

on mouseUp
 answer circular(fld 1,"right")
end mouseUp

function circular data,direction
   if direction = "right" then
      put comma & item 1 of data after data
      delete item 1 of data
   else
      put the last item of data & comma before data
      delete last item of data
   end if
   return data
end circular
You can always pass the delimiter as well, so that even lines and paragraphs could be rotated, or nothing, so that individual chars can be rotated.

But is this what you were looking for?

Craig Newman

Ledigimate
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 132
Joined: Mon Jan 14, 2013 3:37 pm

Re: Circular shift

Post by Ledigimate » Sun Dec 16, 2018 8:39 pm

Hello Craig

Yes I want to do something like that, only it needs to be a bitwise rotation of the individual bits of a 32-bit register, e.g. the number 1234 becomes the number 4644 if you rotate the bits left by 1 position.

edit: sorry, my example is 12-bit integer, not a 32-bit integer
010100000110010101100001011000110110010100111101010011000110111101110110011001010010101101010100011100100111010101110100011010000010101101001010011101010111001101110100011010010110001101100101

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9580
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Circular shift

Post by dunbarx » Sun Dec 16, 2018 9:05 pm

Hi.

Hermann will soon jump all over this. But before he does, please explain how you get 4644 from 1234.

Changing those values to base 2, and then rotating, does not do that, so i am on the wrong track.

Craig

Ledigimate
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 132
Joined: Mon Jan 14, 2013 3:37 pm

Re: Circular shift

Post by Ledigimate » Sun Dec 16, 2018 9:42 pm

dunbarx wrote:
Sun Dec 16, 2018 9:05 pm
Hi.

Hermann will soon jump all over this. But before he does, please explain how you get 4644 from 1234.

Changing those values to base 2, and then rotating, does not do that, so i am on the wrong track.

Craig
Sorry, my bad!! :oops: I used a programmers' calculator to manually do the bit rotation and then afterwards read the OCT value off the screen instead of the decimal value! Sorry!
The number 1234 actually becomes 2468 after rotating the bits left by 1 position.
010100000110010101100001011000110110010100111101010011000110111101110110011001010010101101010100011100100111010101110100011010000010101101001010011101010111001101110100011010010110001101100101

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9580
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Circular shift

Post by dunbarx » Sun Dec 16, 2018 10:24 pm

Ah.

But still not getting it.

Rotating the base 2 value of "1234" ("10011010010") gives "00110100101" which in base 10 is 421.Or if you rotate the other way, 617.

In order to get 2468 from 1234 (double the value), you must double the base 2 string, which requires that you add a "0" to the right side of the string itself. This is not rotating anything, merely doing arithmetic in base 2.

So?

Craig

Ledigimate
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 132
Joined: Mon Jan 14, 2013 3:37 pm

Re: Circular shift

Post by Ledigimate » Sun Dec 16, 2018 10:54 pm

dunbarx wrote:
Sun Dec 16, 2018 10:24 pm
Ah.

But still not getting it.

Rotating the base 2 value of "1234" ("10011010010") gives "00110100101" which in base 10 is 421.Or if you rotate the other way, 617.

In order to get 2468 from 1234 (double the value), you must double the base 2 string, which requires that you add a "0" to the right side of the string itself. This is not rotating anything, merely doing arithmetic in base 2.

So?

Craig
Yes, you are correct, that is if you're working with 11 bits. If we were to represent the number as a 32-bit register, the bits would be "00000000000000000000010011010010", right? And then rotating the bits left by 1 position would take one "0" from the left and add it on the right. Or at least that's what I would expect.
010100000110010101100001011000110110010100111101010011000110111101110110011001010010101101010100011100100111010101110100011010000010101101001010011101010111001101110100011010010110001101100101

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9580
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Circular shift

Post by dunbarx » Mon Dec 17, 2018 12:19 am

Ah, again.

So typically, does a base 2 rotation ignore "leading" zeros?

If I wanted three eggs over easy, I might order "0003" eggs, and if the waiter either had a sense of humor or understood the math I was foisting on him, I would get an eatable breakfast.

In what sense does the rotation operation work in the register? What does the rotated value have to do with the original; what purpose does it serve? It cannot, with leading significant zeros, ever devolve to an actual value. It might, of course, perform other string-like tasks.

I have done that sort of thing with the outputs of an electronic lighting controller. I inverted binary strings, rotated them with their leading zeros just as you are asking to do, etc. to create visual effects. But in all those instances, there was never any relationship with an actual number.

Craig

Ledigimate
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 132
Joined: Mon Jan 14, 2013 3:37 pm

Re: Circular shift

Post by Ledigimate » Mon Dec 17, 2018 6:22 am

So typically, does a base 2 rotation ignore "leading" zeros?
I don't know, I haven't done it before in any programming language.
If I wanted three eggs over easy, I might order "0003" eggs, and if the waiter either had a sense of humor or understood the math I was foisting on him, I would get an eatable breakfast.
:lol: Hehehe
In what sense does the rotation operation work in the register? What does the rotated value have to do with the original; what purpose does it serve? It cannot, with leading significant zeros, ever devolve to an actual value. It might, of course, perform other string-like tasks.

I have done that sort of thing with the outputs of an electronic lighting controller. I inverted binary strings, rotated them with their leading zeros just as you are asking to do, etc. to create visual effects. But in all those instances, there was never any relationship with an actual number.
I can't think of many use cases myself. In fact, I've only ever seen one use case, which is what I'm looking to use it for -- cryptography.
010100000110010101100001011000110110010100111101010011000110111101110110011001010010101101010100011100100111010101110100011010000010101101001010011101010111001101110100011010010110001101100101

SparkOut
Posts: 2839
Joined: Sun Sep 23, 2007 4:58 pm

Re: Circular shift

Post by SparkOut » Mon Dec 17, 2018 7:39 am

About 30 million years ago I cut a couple of teeth and gnashed some gums on Z80 assembler with 8 bit registers. It was a very common process to shift left, shift right, rotate left or rotate right, for a variety of reasons but they were ubiquitous operations. The bit that was rotated or shifted off the end was typically / often copied to a parity bit, or the rotation was sometimes over the 9 bits of the register plus parity bit. I can't remember any of the purposes, but it did make sense at the time.

Ledigimate
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 132
Joined: Mon Jan 14, 2013 3:37 pm

Re: Circular shift

Post by Ledigimate » Mon Dec 17, 2018 8:54 am

Here's what I've got working.

Code: Select all

function rotateBits pNumber, pBitLength, pPositions, pDirection
   local tBase2, tBase2new, tNumLeadingBits
   put baseConvert(pNumber, 10, 2) into tBase2
   put pBitLength - length(tBase2) into tNumLeadingBits
   repeat tNumLeadingBits times
      put "0" before tBase2
   end repeat
   if pDirection is "right" then
      put (char (pBitLength +1 - pPositions) to -1 of tBase2) & (char 1 to (pBitLength - pPositions) of tBase2) into tBase2new
   else
      put (char pPositions +1 to -1 of tBase2) & (char 1 to pPositions of tBase2) into tBase2new
   end if
   return baseConvert(tBase2new, 2, 10)
end rotateBits
If only LC had a bitwise operator that could do the same as << and >> in C, then the above code could be reduced to only 5 lines.
010100000110010101100001011000110110010100111101010011000110111101110110011001010010101101010100011100100111010101110100011010000010101101001010011101010111001101110100011010010110001101100101

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Circular shift

Post by [-hh] » Mon Dec 17, 2018 3:39 pm

As you are comparing your pure LC Script solution to the 32bit C operators:
The browser widget belongs to LC, so we have, besides *2^pPosition and div 2^pPosition, also the following possibility.

Code: Select all

function rotateBits pN, pP, pD -- 32bit numbers only
  if pD is "L" then put "<<" into op -- signed left shift
  else put ">>>" into op -- unsigned right shift
  do "liveCode.JS(" &value(pN)&op&value(pP)& ")" in widget "shift"
  wait 0 millisecs with messages; return the theResult of widget "shift"
end rotateBits
See for the javaScript operators https://developer.mozilla.org/en-US/doc ... _Operators

An application (that creates widget "shift" if not yet present):

Code: Select all

on mouseUp b
  if there is no widget "shift" then
    create widget "shift" as "com.livecode.widget.browser"
    set script of widget "shift" to "on JS v; set theResult of me to v; end JS"
    set javascriptHandlers of widget "shift" to "JS"
  end if
  -- yields 256,1024:
  put rotateBits(2^8,sin(0),"R") &comma& rotateBits(2^8,1+1,"L")
end mouseUp
shiftLock happens

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9580
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Circular shift

Post by dunbarx » Mon Dec 17, 2018 3:40 pm

Hello, Hermann.

Just curious, why are you using explicit terms such as "sin(0)" or "1+1" as parameters?

In switch statements, sometimes if I have a "default" case, that is, after all conditional cases have been handled but there still remain all the other possibilities, I will have as the lastMost case something like:

case 3 = 3
...

That seems to always fire. :wink:

Is that sort of what you are doing here?

Craig

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Circular shift

Post by [-hh] » Mon Dec 17, 2018 3:49 pm

Hi Craig.
why are you using explicit terms such as "sin(0)" or "1+1" as parameters?
Because my above 5 lines function has evaluating parameter expressions included.
This usually reduces the complain about missing "C-features" in LiveCode.

By the way: LC Builder has built-in BitwiseShiftLeft and BitwiseShiftRight operators.
shiftLock happens

Ledigimate
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 132
Joined: Mon Jan 14, 2013 3:37 pm

Re: Circular shift

Post by Ledigimate » Mon Dec 17, 2018 6:42 pm

[-hh] wrote:
Mon Dec 17, 2018 3:39 pm
As you are comparing your pure LC Script solution to the 32bit C operators:
The browser widget belongs to LC, so we have, besides *2^pPosition and div 2^pPosition, also the following possibility.

Code: Select all

function rotateBits pN, pP, pD -- 32bit numbers only
  if pD is "L" then put "<<" into op -- signed left shift
  else put ">>>" into op -- unsigned right shift
  do "liveCode.JS(" &value(pN)&op&value(pP)& ")" in widget "shift"
  wait 0 millisecs with messages; return the theResult of widget "shift"
end rotateBits
See for the javaScript operators https://developer.mozilla.org/en-US/doc ... _Operators

An application (that creates widget "shift" if not yet present):

Code: Select all

on mouseUp b
  if there is no widget "shift" then
    create widget "shift" as "com.livecode.widget.browser"
    set script of widget "shift" to "on JS v; set theResult of me to v; end JS"
    set javascriptHandlers of widget "shift" to "JS"
  end if
  -- yields 256,1024:
  put rotateBits(2^8,sin(0),"R") &comma& rotateBits(2^8,1+1,"L")
end mouseUp
Wow, thanks Hermann!
I now only need it to actually rotate the bits, not just shift them while discarding the bits that were shifted out. One has to actually combine the the two operators to perform a rotation.

Modifying your rotateBits function a bit, I think this would do it:

Code: Select all

function rotateBits pN, pP, pD -- 32bit numbers only
  if pD is "L" then
    do "liveCode.JS((" & value(pN) & "<<" & value(pP) & ") | (" & value(pN) & ">>>" & value(32 - pP) & "))" in widget "shift" -- left rotate
  else
    do "liveCode.JS((" & value(pN) & ">>" & value(pP) & ") | (" & value(pN) & "<<" & value(32 - pP) & "))" in widget "shift" -- rotate right
  end if; wait 0 millisecs with messages; return the theResult of widget "shift"
end rotateBits
As to the BitwiseShiftLeft and BitwiseShiftRight operators, I haven't yet mustered up enough courage to start the LC Builder learning curve. I suppose I could work through the tutorial and then use that instead of JavaScript in a browser widget.

Thank you so much, Hermann! You've impressed, as usual.
010100000110010101100001011000110110010100111101010011000110111101110110011001010010101101010100011100100111010101110100011010000010101101001010011101010111001101110100011010010110001101100101

Post Reply

Return to “Talking LiveCode”