1

Sometimes by rotating a number right we obtain the same number.

eg. 01010101 (85) can be rotated by 2,4,6 places to get the same number.what are the number of times we can rotate a number by different bits to get the same number? For this I wrote the following code:

extern printf                   ; the C function to be called  
SECTION .data                   ; Data section  
msg:    db "The number of possible rotations  are : %d",10,0  
inta1:  dd  1234567   ; integer 1234567  

num: dd  1431655765  

SECTION .text                   ; Code section.  

global  main                ; "C" main program   
main:     
    mov eax, [num]    
    mov ecx,32  
    mov ebx,0  
    mov edx,eax  
.loop:  
    dec ecx  
    cmp ecx,1  
    jl .exit  
    ror eax,1  
    cmp edx,eax  
    jne .loop  
    inc ebx  
    jmp .loop  
.exit:  
        push ebx  
        push    dword msg 
        call    printf        
        add     esp, 8

Output for above code: The number of possible rotations are : 15
When num: 858993459
Output:
The number of possible rotations are : 7
.

Although I get correct answers for 32 bit numbers, I am not able to use a non-32 bit in place of num in the same code to get the correct answer.
eg When I use num :85,
I get the output:
The number of possible rotations are : 0
But it should have been 3
Maybe it is because of padding by zeros in the first remaining bits.(Not sure, Just assuming) How do I use the same set of registers to display the value of possible rotations for a non-32 bit number too?

Saumya Sahay
  • 63
  • 5
  • 1
    What exactly do you mean by _"non-32 bit number"_? Please add the non-working code. – Michael May 11 '16 at 15:42
  • @Michael For example a 8-bit number 01010101 (=85) when right rotated by 2 places gives 01010101 which is again equal to 85. when right rotated by 4 places gives 01010101 which is again equal to 85.when right rotated by 6 places gives 01010101 which is again equal to 85. So the total number of possible rotations shoul be 3 but I get an output as 0. How to solve this? – Saumya Sahay May 11 '16 at 15:45
  • EAX is a 32-bit register. If it contains 85 decimal and you rotate it right you would then have 10000000000000000000000000101010 in binary. If you want to handle 8-bit values use the AL register. – Jim Rhodes May 11 '16 at 15:48
  • @JimRhodes That is my question. How do I get the answer=3 when using num as 85 by using the same set of extended registers? – Saumya Sahay May 11 '16 at 15:50
  • @SaumyaSahay: Then do the rotation on `al` instead if that's the behavior you want. – Michael May 11 '16 at 15:50
  • @Michael I see that al is a 8 bit register. Using al I will not be able to use 32 bit numbers. I want to use 32 bit extended register and find the solution. – Saumya Sahay May 11 '16 at 15:51
  • `al` is the least significant byte of `eax`. if you rotate `al` you'd only rotate those 8 bits. – Michael May 11 '16 at 15:55
  • @Michael Please bear with me if my questions are idiotic as I am really new to this. What if the number is user input, and we do not know, if it's a 8-bit, 16-bit or 32 bit number from before hand? – Saumya Sahay May 11 '16 at 16:10
  • what I mean to ask is how should I alter the code so that no matter whatever random input number(obviously less than equal to 32 bit in size ) I use, I get the required answer. – Saumya Sahay May 11 '16 at 16:13
  • 1
    By that logic, why would 85 (1010101) be an 8-bit number and not a 7-bit number? – Michael May 11 '16 at 16:18
  • This is an interesting question. I would appreciate to see some general answers with theoretical background :-) – zx485 May 11 '16 at 17:32

1 Answers1

1

It sounds like your function / program needs two inputs: the number and the rotation width.

You can use the rol instruction for 8, 16, 32, and 64bit rotates. You'll need different copies of the loop for each operand-size.

If you want to support arbitrary rotation widths, you'll have to emulate them with shifts and masking. (Similar to the pattern of shifts that C compilers recognize as a rotate.)

rcl will do 9, 17, 33, or 65bit rotates, but part of the number is in CF where you can't compare it easily. I don't think rotate-through-carry will be helpful for this.

If you want to infer the rotation width from the number, you might use bsr to find the highest set bit. You could optionally round that up to 8, 16, 32, or 64.

Make sure you test your program with input = 0, because bsr's register result is undefined for 0 inputs. (Its flag result has ZF set).

RE: your actual code:

First of all, your function doesn't return, so you'll just crash, or get lucky and fall-through into a function that does return. Add a ret instruction to the end.

Also, dec already sets flags. You don't need a cmp. You actually don't need a check there at all, since you're guaranteed to find a match after rotating back to the initial value. It was possible to dramatically simplify your loop. It should now run at one iteration per cycle on Intel CPUs.

I also put the format string and so on in read-only data, not private modifiable data.

extern printf

SECTION .rodata                 ; Read-only data section  

msg:  db  "The number of possible rotations  are : %d",10,0  
num:  dd  1431655765  

section .text
global  main
main:
    ;mov ebx,0  ; should be  xor ebx,ebx.  And you need to save/restore ebx if you're going to modify it.

    mov   eax, [num]
    mov   edx,eax
    xor   ecx,ecx

.rotcount:
    ror   eax, 1
    inc   ecx
    cmp   edx, eax  
    jne  .rotcount

    ;; ecx = number of 32bit rotates to produce a match.  Range: 1 to 32

    push    ecx  
    push    dword msg 
    call    printf        
    add     esp, 8

    xor   eax,eax     # return 0, instead of unpredictable behaviour from fall-through
    ret
Community
  • 1
  • 1
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847