Page 1 of 2

Circular shift

Posted: Sun Dec 16, 2018 7:08 pm
by Ledigimate
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

Re: Circular shift

Posted: Sun Dec 16, 2018 7:48 pm
by dunbarx
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

Re: Circular shift

Posted: Sun Dec 16, 2018 8:39 pm
by Ledigimate
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

Re: Circular shift

Posted: Sun Dec 16, 2018 9:05 pm
by dunbarx
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

Re: Circular shift

Posted: Sun Dec 16, 2018 9:42 pm
by Ledigimate
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.

Re: Circular shift

Posted: Sun Dec 16, 2018 10:24 pm
by dunbarx
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

Re: Circular shift

Posted: Sun Dec 16, 2018 10:54 pm
by Ledigimate
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.

Re: Circular shift

Posted: Mon Dec 17, 2018 12:19 am
by dunbarx
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

Re: Circular shift

Posted: Mon Dec 17, 2018 6:22 am
by Ledigimate
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.

Re: Circular shift

Posted: Mon Dec 17, 2018 7:39 am
by SparkOut
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.

Re: Circular shift

Posted: Mon Dec 17, 2018 8:54 am
by Ledigimate
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.

Re: Circular shift

Posted: Mon Dec 17, 2018 3:39 pm
by [-hh]
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

Re: Circular shift

Posted: Mon Dec 17, 2018 3:40 pm
by dunbarx
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

Re: Circular shift

Posted: Mon Dec 17, 2018 3:49 pm
by [-hh]
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.

Re: Circular shift

Posted: Mon Dec 17, 2018 6:42 pm
by Ledigimate
[-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.