flat assembler
Message board for the users of flat assembler.

Index > Main > Thue-Morse Sequence Contest

Goto page 1, 2, 3  Next
Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 3056
Location: vpcmipstrm
bitRAKE
What is the smallest routine to generate a Thue-Morse block?
(assume zeroed output memory pointer and term ordinal are passed in registers)

For T(n), a block consists of the first 2^n terms of the the Thue-Morse sequence t(n):

T0 = 0
T1 = 01
T2 = 0110
T3 = 01101001
T4 = 0110100110010110
.
.
.
...output can be in any form: ASCII, binary,etc. A distinction shall be made between entries which output a range of terms without writing additional data to the output buffer, and those which output a single term (which includes all lesser terms as suffixes). In the later case those entries output a single term rather than selecting output range based on parameter passed.

No register preservation is required, but as a leaf routine RET is required. I appreciate the understanding of participants as the contest has gotten broader in scope than originally intended - for the good I hope. Previous entry rankings have been updated to reflect these changes without the need for re-submission.

There are so many ways to generate the sequence.
(the task itself is not difficult)

Winners will exist for each execution environment and output format.
(Decided by participation.)

Results:
Code:
Bytes  Type   Output   Entrant          Notes
   23  32bit  ASCII    Mikolaj Hajduk   T0-?, negative copy
   18  32bit  ASCII    Mikolaj Hajduk   T0-T8, parity
   29  32bit  ASCII    Grom PE          T0-?, substitution map  
   28  16bit  ASCII    Grom PE          T0-?, substitution map

   16  32bit  Binary   revolution       T0-T8, parity
   18  32bit  Binary   revolution       T0-T16, parity
   22  32bit  Binary   revolution       T0-T31, parity
   34  64bit  Binary   revolution       T0-T63, parity

   38  64bit  Binary   revolution       only T64 output
   26  32bit  Binary   revolution       only T32 output
   19  32bit  Binary   revolution       only T31 output
   31  16bit  Binary   Tomasz Grysztar  only T19 output
   16  32bit  Binary   revolution       only T16 output
   12  32bit  Binary   revolution       only T8 output
   17  16bit  Binary   Tomasz Grysztar  only T6 output
5/6/7  *      Binary   Tomasz Grysztar  only T4 output
    4  *      Binary   Tomasz Grysztar  only T3 output
    2  *      Binary    ( Example )     only T0 output    

_________________
¯\(°_o)/¯ unlicense.org


Last edited by bitRAKE on 31 Jan 2009, 15:34; edited 15 times in total
Post 25 Jan 2009, 22:32
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 my corrected solution:
Code:
        ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ebx    - pointer to the allocated memory block filled with zero
   ;                  bytes,
   ;
   ;       - edx    - ordinal number of the created term.
      ;
   ThueMorse:
              pushad

          mov     edi, ebx
            mov     al, '0'
           stosb

           .NextTerm:
                      test    edx, edx
                    jz      .End

                    mov     esi, ebx
                    mov     ecx, edi
                    sub     ecx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               loop    .Loop

                   dec edx

                 jmp     .NextTerm

               .End:
                   popad
                       retn
    
Here you have a program which makes easier testing of this procedure:
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.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    ebx, eax

                mov     edx, n

          call    ThueMorse

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

              invoke  LocalFree, ebx

  exit:
           invoke  ExitProcess, 0

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

          mov     edi, ebx
            mov     al, '0'
           stosb

           .NextTerm:
                      test    edx, edx
                    jz      .End

                    mov     esi, ebx
                    mov     ecx, edi
                    sub     ecx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               loop    .Loop

                   dec edx

                 jmp     .NextTerm

               .End:
                   popad
                       retn

.end start
    


Last edited by MHajduk on 26 Jan 2009, 17:53; edited 1 time in total
Post 26 Jan 2009, 12:48
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
bitRAKE wrote:
(assume zeroed output memory pointer and term sub-script are passed in registers)
I missed it previously. See my post above for the corrected solution.
Post 26 Jan 2009, 17:39
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3056
Location: vpcmipstrm
bitRAKE
Well done. Dropped 20 bytes, too.
Post 26 Jan 2009, 18:04
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Next version of the procedure (one byte smaller than previous):
Code:
   ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ebx    - pointer to the allocated memory block filled with zero
   ;                  bytes,
   ;
   ;       - ecx    - ordinal number of the created term.
      ;
   ThueMorse:
              pushad

          mov     edi, ebx
            mov     al, '0'
           stosb

           jcxz    .End

            .NextTerm:
                      mov     esi, ebx
                    mov     edx, edi
                    sub     edx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               dec     edx
                         jnz     .Loop

                   loop    .NextTerm

               .End:
                   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.01.2009.
;
;
format PE GUI 4.0

include     'win32ax.inc'

section '.code' code readable executable

       start:
          n = 4   ; 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    ebx, eax

                mov     ecx, n

          call    ThueMorse

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

              invoke  LocalFree, ebx

  exit:
           invoke  ExitProcess, 0

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

          mov     edi, ebx
            mov     al, '0'
           stosb

           jcxz    .End

            .NextTerm:
                      mov     esi, ebx
                    mov     edx, edi
                    sub     edx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               dec     edx
                         jnz     .Loop

                   loop    .NextTerm

               .End:
                   popad
                       retn

.end start
    
Post 26 Jan 2009, 19:33
View user's profile Send private message Visit poster's website Reply with quote
Grom PE



Joined: 13 Mar 2008
Posts: 115
Location: i@grompe.org.ru
Grom PE
Ok, I suck, but at least it's different algorithm =)
It allows linear generation.

31 bytes, 32-bit:
Code:
; ebx = pointer
; ecx = term
ThueMorse_by_Grom_PE:
        pushad
      mov     edi, ebx
    mov     esi, ebx
    mov     byte [ebx], '0'
   jecxz   zero

    xor     eax, eax
    inc     eax
 dec     ecx
 shl     eax, cl
     xchg    ecx, eax
x2:
 mov     ah, 0
       lodsb
       cmp     al, '1'
   adc     ah, '0'
   stosw
       loop    x2
zero:
     popad
       ret    
30 bytes, 16-bit:
Code:
org 100h

n = 4
        mov     bx, buffer
  mov     cx, n 
      call    ThueMorse_by_Grom_PE_16bit
  mov     byte [bx + 1 shl n], '$'
  mov     ah, 9
       mov     dx, bx
      int     21h
 int     20h

; bx = pointer
; cx = term
ThueMorse_by_Grom_PE_16bit:
 pusha
       mov     di, bx
      mov     si, bx
      mov     byte [bx], '0'
    jcxz    zero

    xor     ax, ax
      inc     ax
  dec     cx
  shl     ax, cl
      xchg    cx, ax
x2:
   mov     ah, 0
       lodsb
       cmp     al, '1'
   adc     ah, '0'
   stosw
       loop    x2
zero:
     popa
        ret

buffer       rb 1 shl n + 1    
MHajduk, change jcxz to jecxz in your code and you'll have 25 bytes.
Post 27 Jan 2009, 09:06
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Grom PE wrote:
MHajduk, change jcxz to jecxz in your code and you'll have 25 bytes.
Yes, you are right. It's nice tip, thanks. Smile

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

          mov     edi, ebx
            mov     al, '0'
           stosb

           jecxz   .End

            .NextTerm:
                      mov     esi, ebx
                    mov     edx, edi
                    sub     edx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               dec     edx
                         jnz     .Loop

                   loop    .NextTerm

               .End:
                   popad
                       retn
    
Post 27 Jan 2009, 10:18
View user's profile Send private message Visit poster's website Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
I read here that interesting visuals can be constructed using the Thue-Morse sequence.
Post 27 Jan 2009, 12:33
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Very beautiful application of the mathematical idea, indeed. Very Happy I liked especially this tiling:


Image


Source: http://lcni.uoregon.edu/~mark/Geek_art/Simple_recursive_systems/Tesselations/Redundant_Quadrapii/Redundant_Quadrapii_x2.jpg
Post 27 Jan 2009, 12:48
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3056
Location: vpcmipstrm
bitRAKE
Much smaller routines are possible using different algorithms and output formats. For example, if we say the output is limited to just the first term, and parameters are passed in EAX,EDI then "STOSB" would be a valid single byte entry. Sure, it is uninteresting but I am just demonstrating the point that all the outputs are limited - even though we haven't explicitly stated the term limit inherent in the output definition. Another example would be the difference between 32-bit and 16-bit routines -- clearly they have different output limits.
Post 27 Jan 2009, 16:59
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7802
Location: Kraków, Poland
Tomasz Grysztar
OK, so the shortest routine generating T3 as little-endian binary perhaps might be:
Code:
mov al,10010110b
stosb    

Wink

And T4 in 6 bytes of 16-bit code:
Code:
mov al,10010110b
cbw
xor ah,al
stosw    

Yeah, with plain MOV and STOSW it would be only 4 bytes, but this one is more interesting. Wink
Post 27 Jan 2009, 17:21
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3056
Location: vpcmipstrm
bitRAKE
Tomasz, those are valid as are solutions which generate a range of terms.
(Hint: for example, there is a very small way to generate T0-T7.)
Post 28 Jan 2009, 02:12
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7802
Location: Kraków, Poland
Tomasz Grysztar
bitRAKE wrote:
(Hint: for example, there is a very small way to generate T0-T7.)

Well, I've got something for T0-T6:
Code:
        mov     al,10010110b
        mov     dl,al
  @loop:
        stosb
        test    dl,11b
        jp      @f
        not     al
     @@:
        shr     dl,1
        jnz     @loop    

I'm not sure if mine is "very small", but look - I use JP instruction. Wink
It could act as an example for the thread about cases of JP being useful.
Post 28 Jan 2009, 08:47
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: 17717
Location: In your JS exploiting you and your system
revolution
This "generates" T0 in one bit
Code:
db 0b ;T0: assumes little endian bit storage    
This "generates" T1 in two bits
Code:
db 10b ;T1: assumes little endian bit storage    
This "generates" T2 in four bits
Code:
db 0110b ;T2: assumes little endian bit storage    
This "generates" T3 in one byte
Code:
db 10010110b ;T3: assumes little endian bit storage    
This "generates" T4 in two bytes
Code:
dw 0110100110010110b ;T4: assumes little endian bit storage    
This "generates" T5 in four bytes
Code:
dd 10010110011010010110100110010110b ;T5: assumes little endian bit storage    
This "generates" T6 in eight bytes
Code:
dq 0110100110010110100101100110100110010110011010010110100110010110b ;T6: assumes little endian bit storage    
Post 28 Jan 2009, 09:30
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7802
Location: Kraków, Poland
Tomasz Grysztar
As further playing with that JP idea Wink, this 16-bit code generates T19 in binary form (revolution, this one you won't beat that way Wink):
Code:
        xor     bx,bx ; how many bytes generate? 0 gives 65536.

        mov     si,di
        xor     cx,cx
        mov     al,10010110b
  @loop:
        stosb
        mov     dx,[si]
        shr     dx,cl
        test    dl,11b
        jp      @f 
        not     al 
     @@: 
        inc     cx
        and     cl,111b
        jnz     @f
        inc     si
     @@:
        dec     bx
        jnz     @loop    

It assumes DS=ES, but I already saw this assumption be allowed for 16-bit code here. However it fills whole segment with data, so don't try it from .COM file unless you get yourself some free segment. Wink
But by putting some smaller value into BX you may generate smaller amount of data (like 8000h in BX will give you T18).
Post 28 Jan 2009, 10:21
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: 17717
Location: In your JS exploiting you and your system
revolution
Code:
        use32
up_to_T8:
        xor     eax,eax ;bit counter
    .loop:
        jpe     @f
        btc     [edi],eax
    @@: inc     al
        jnz     .loop                   ;11 bytes    
Code:
 use32
up_to_T16:
     xor     eax,eax ;bit counter
    .loop:
      mov     cl,al
       xor     cl,ah
       jpe     @f
  btc     [edi],eax
    @@:        inc     ax
  jnz     .loop                   ;15 bytes    
Code:
        use32
up_to_T32:
        xor     eax,eax ;bit counter
    .loop:
        shld       ecx,eax,16
        xor     ecx,eax
        xor     ch,cl
        jpe     @f
        btc     [edi],eax
    @@: inc     eax
        jnz     .loop                   ;18 bytes    
Post 28 Jan 2009, 10:46
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7802
Location: Kraków, Poland
Tomasz Grysztar
Yeah, much better application of parity check that mine. Smile

But doesn't it assume the memory is pre-initialized?
Post 28 Jan 2009, 11:13
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: 17717
Location: In your JS exploiting you and your system
revolution
Of course it requires this:
bitRAKE wrote:
assume zeroed output memory pointer
else a prefixed rep stosb is in order.
Post 28 Jan 2009, 11:14
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7802
Location: Kraków, Poland
Tomasz Grysztar
Oh, I guess I should read the thread before participating. Very Happy
I even did not read the definition of the series earlier. Wink And now I see that your solution just follows the definition in the most strict sense.


Last edited by Tomasz Grysztar on 28 Jan 2009, 11:18; edited 1 time in total
Post 28 Jan 2009, 11:16
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: 17717
Location: In your JS exploiting you and your system
revolution
Tomasz Grysztar wrote:
Oh, I guess I should read the thread before participating. Very Happy
If all else fails read the instructions Very Happy
Post 28 Jan 2009, 11:18
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 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.