flat assembler
Message board for the users of flat assembler.

Index > Main > Thue-Morse Sequence Contest

Goto page Previous  1, 2, 3  Next
Author
Thread Post new topic Reply to topic
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7783
Location: Kraków, Poland
Tomasz Grysztar
One note though: your up_to_T32 won't work, because the bit count for BTx instructions is a signed value (!).

BTW, I find it funny that I managed to use JP instruction for solution, not realizing that the direct definition of problem (which I didn't even care to read Wink) imposes the usage of parity check, even though in a bit different way. Smile
Post 28 Jan 2009, 11:36
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
Easy fixed Wink
Code:
        use32
up_to_T31:
        xor     eax,eax ;bit counter
    .loop:
        shld    ecx,eax,16
        xor     ecx,eax
        xor     ch,cl
        jpe     @f
        btc     [edi],eax
    @@: inc     eax
        jns     .loop                   ;18 bytes    
Post 28 Jan 2009, 11:39
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
Tomasz Grysztar wrote:
BTW, I find it funny that I managed to use JP instruction for solution, not realizing that the direct definition of problem (which I didn't even care to read Wink) imposes the usage of parity check, even though in a bit different way. Smile
Perhaps someone can edit the Wikipedia entry and add a paragraph stating that the output is the 2's parity of the position counter.
Post 28 Jan 2009, 11:42
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
OK, here is the next version of my procedure, has 21 bytes (if I would remove such instructions as 'pushad', 'popad' and 'retn' it could be also 18 byte Wink), one loop, using parity of bits:
Code:
     ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ecx    - ordinal number of the created term,
      ;
   ;       - edi    - pointer to the allocated memory block filled with zero
   ;                  bytes.
   ;
   ThueMorse:
              pushad

          xor     eax, eax
            mov     al, 1
               shl     eax, cl
             xchg    eax, ecx
            xor     edx, edx                

                .Loop:
                  setnp   al
                  or      al, '0'
                   stosb
                       inc     edx
                 loop    .Loop

           popad
               retn
    
and simple application for testing it:
Code:
;
; Written with FASM simple Windows application which presents in human readable
; form terms of the Thue-Morse sequence produced by a given procedure.
;
; (C) Mikolaj Hajduk, 26-28.01.2009.
;
;
format PE GUI 4.0

include  'win32ax.inc'

section '.code' code readable executable

       start:
          n = 6   ; Ordinal number of the created term of the Thue-Morse sequence.

                invoke  LocalAlloc, LMEM_ZEROINIT, (1 shl n) + 1
            test    eax, eax
            jz      exit

            xchg    edi, eax

                mov     ecx, n

          call    ThueMorse

               invoke  MessageBox, 0, edi, "Thue-Morse Sequence", MB_OK

              invoke  LocalFree, edi

  exit:
           invoke  ExitProcess, 0

  ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ecx    - ordinal number of the created term,
      ;
   ;       - edi    - pointer to the allocated memory block filled with zero
   ;                  bytes.
   ;
   ThueMorse:
              pushad

          xor     eax, eax
            mov     al, 1
               shl     eax, cl
             xchg    eax, ecx
            xor     edx, edx                

                .Loop:
                  setnp   al
                  or      al, '0'
                   stosb
                       inc     edx
                 loop    .Loop

           popad
               retn

.end start
    
Post 28 Jan 2009, 11:42
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
MHajduk: Parity is only calculated for the lowest 8 bits in x86. So anything above n=8 may fail.
Post 28 Jan 2009, 11:45
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
MHajduk wrote:
Code:
...
                xor     eax, eax
                mov     al, 1
                shl     eax, cl
...    
Is it shorter to put:
Code:
xor eax,eax
bts eax,ecx    
?
Post 28 Jan 2009, 11:48
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7783
Location: Kraków, Poland
Tomasz Grysztar
revolution wrote:
Perhaps someone can edit the Wikipedia entry and add a paragraph stating that the output is the 2's parity of the position counter.

The very definition of the sequence says exactly this.

If you read it carefully, you'll also notice, that it's not T0, T1, etc. that are really the terms of Thue-Morse sequence, but t0, t1, as:
t0 = 0
t1 = 1
t2 = 1
t3 = 0
etc.

So, in fact, the answer to "What is the smallest routine to generate a Thue-Morse term?" might rather be something like:
Code:
        shld    ecx,eax,16
        xor     ecx,eax 
        xor     ch,cl
        setpo   al    

Input - number of term in EAX. Output - the term value in the lowest bit of EAX. Smile


Last edited by Tomasz Grysztar on 28 Jan 2009, 11:55; edited 2 times in total
Post 28 Jan 2009, 11:50
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
Tomasz Grysztar wrote:
revolution wrote:
Perhaps someone can edit the Wikipedia entry and add a paragraph stating that the output is the 2's parity of the position counter.

The very definition of the sequence says exactly this.
But it doesn't have the word "parity". Any computer programmer should instantly understand it if it did.
Post 28 Jan 2009, 11:52
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
revolution wrote:
MHajduk wrote:
Code:
...
                xor     eax, eax
                mov     al, 1
                shl     eax, cl
...    
Is it shorter to put:
Code:
xor eax,eax
bts eax,ecx    
?
Yes, you are right. Wink
Post 28 Jan 2009, 11:55
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
Tomasz Grysztar wrote:
So, in fact, the answer to "What is the smallest routine to generate a Thue-Morse term?" might rather be something like:
Code:
        shld    ecx,eax,16
        xor     ecx,eax 
        xor     ch,cl
        setpo   al    

Input - number of term in EAX. Output - the term value in the lowest bit of EAX. Smile
11 bytes.

This is also the same length (11 bytes) but has one more instruction:
Code:
    mov     ecx,eax
     bswap   ecx
        xor     ecx,eax 
        xor     ch,cl
        setpo   al    
Post 28 Jan 2009, 12:05
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
But, accordingly to the competition conditions, we are concerned on generation T_{n} elements, not t_{n}. Sequence T is a sequence of sequences of 0's and 1's. Wink
Post 28 Jan 2009, 12:18
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3025
Location: vpcmipstrm
bitRAKE
Although the terms are suffixes of following terms, the reason for passing the term number into the routine is to limit effect on target memory. So, these latest entries are not capable of producing a range of T# terms. Of course, they are still valid entries.

Bravo for finding the parity definition - it was hidden, imho.
http://mathworld.wolfram.com/Thue-MorseSequence.html
At the MathWorld site it is stated at the start!

(I'll update the results after work today, and will update the description to make the output limit more explict.)


Last edited by bitRAKE on 28 Jan 2009, 16:03; edited 1 time in total
Post 28 Jan 2009, 15:55
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
bitRAKE wrote:
Although the terms are suffixes of following terms, the reason for passing the term number into the routine is to limit effect on target memory. So, these latest entries are not capable of producing a range of T# terms.
I was only coding the core idea. Others are welcome to copy/modify/extend my snippets and post record-breaking generic entries.
Post 28 Jan 2009, 16:01
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3025
Location: vpcmipstrm
bitRAKE
Of course, they are still valid entries.
Post 28 Jan 2009, 16:05
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
Code:
  use32

;Input:        edi = pointer to zeroed memory
;     ecx = T value

up_to_T8:
  xor     eax,eax ;bit counter
    .loop:
      test    al,0xff
     jpe     @f
  bts     [edi],eax
    @@:        inc     eax
 bt      eax,ecx
     jnc     .loop
       retn                    ;16 bytes
    

Code:
        use32

;Input:        edi = pointer to zeroed memory
;     ecx = T value

up_to_T16:
 xor     eax,eax ;bit counter
    .loop:
      mov     dl,al
       xor     dl,ah
       jpe     @f
  bts     [edi],eax
    @@:        inc     eax
 bt      eax,ecx
     jnc     .loop
       retn                    ;18 bytes
    

Code:
        use32

;Input:        edi = pointer to zeroed memory
;     ecx = T value

up_to_T31:
 xor     eax,eax ;bit counter
    .loop:
      shld    edx,eax,16
  xor     edx,eax
     xor     dl,dh
       jpe     @f
  bts     [edi],eax
    @@:        inc     eax
 bt      eax,ecx
     jnc     .loop
       retn                    ;22 bytes
    

Code:
        use64

;Input:        rdi = pointer to zeroed memory
;     rcx = T value

up_to_T63:
 xor     rax,rax ;bit counter
    .loop:
      shld    rdx,rax,32
  xor     edx,eax
     shld    ebx,edx,16
  xor     ebx,edx
     xor     bl,bh
       jpe     @f
  bts     [rdi],rax
    @@:        inc     rax
 bt      rax,rcx
     jnc     .loop
       retn                    ;34 bytes
    
Post 29 Jan 2009, 17:03
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
BTW, why this thread is on Heap? Should I move it to Main?
Post 29 Jan 2009, 17:08
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17639
Location: In your JS exploiting you and your system
revolution
LocoDelAssembly wrote:
BTW, why this thread is on Heap? Should I move it to Main?
Main wrote:
General discussion about flat assembler, not related to any particular operating system.
Doesn't seem to fit there.
Post 29 Jan 2009, 17:10
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Heap wrote:
Everything not related to assembly programming should be posted here.


Perhaps it doesn't fit on Main but I think that it fits better on there than here on Heap... (And Main has been used for "General Assembly Discussion" more than just talking about flat assembler exclusively).

I think Main's definition should be rewritten.

For now, thread moved Very Happy
Post 29 Jan 2009, 17:21
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7783
Location: Kraków, Poland
Tomasz Grysztar
LocoDelAssembly wrote:
I think Main's definition should be rewritten.

Perhaps you're right. The main reason for giving it that description was to discourage people from coming and asking questions about MASM/NASM, etc.
Post 29 Jan 2009, 17:27
View user's profile Send private message Visit poster's website Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
Loco wrote:
Perhaps it doesn't fit on Main but I think that it fits better on there than here on Heap...
dear friend, I disagree with you, completely.
MAIN, is for problems and or issues associated with FASM, not assembly language programming.
Ask yourself this simple question:
Is there something about this contest, Thue-Morse, for which use of FASM to implement a solution, poses a problem, when compared, for example, to use of MASM or any other assembler? If the answer is YES, then, this is the proper location for this thread. If, on the other hand, there is NOTHING unique about FASM, vis a vis finding a potential solution to the problem, then, this is a mere application, which DOES NOT BELONG in MAIN.
Heap is not a repository of useless thoughts. It is very suitable for discussions of this type, unless, the proposed solution to Thue-Morse uncovers a flaw with FASM.
Post 29 Jan 2009, 18:03
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.