exercism / x86-64-assembly

Exercism exercises in x86-64 Assembly.
https://exercism.org/tracks/x86-64-assembly
MIT License
22 stars 18 forks source link

Building a training set of tags for x86-64-assembly #189

Closed ErikSchierboom closed 1 year ago

ErikSchierboom commented 1 year ago

Hello lovely maintainers :wave:

We've recently added "tags" to student's solutions. These express the constructs, paradigms and techniques that a solution uses. We are going to be using these tags for lots of things including filtering, pointing a student to alternative approaches, and much more.

In order to do this, we've built out a full AST-based tagger in C#, which has allowed us to do things like detect recursion or bit shifting. We've set things up so other tracks can do the same for their languages, but its a lot of work, and we've determined that actually it may be unnecessary. Instead we think that we can use machine learning to achieve tagging with good enough results. We've fine-tuned a model that can determine the correct tags for C# from the examples with a high success rate. It's also doing reasonably well in an untrained state for other languages. We think that with only a few examples per language, we can potentially get some quite good results, and that we can then refine things further as we go.

I released a new video on the Insiders page that talks through this in more detail.

We're going to be adding a fully-fledged UI in the coming weeks that allow maintainers and mentors to tag solutions and create training sets for the neural networks, but to start with, we're hoping you would be willing to manually tag 20 solutions for this track. In this post we'll add 20 comments, each with a student's solution, and the tags our model has generated. Your mission (should you choose to accept it) is to edit the tags on each issue, removing any incorrect ones, and add any that are missing. In order to build one model that performs well across languages, it's best if you stick as closely as possible to the C# tags as you can. Those are listed here. If you want to add extra tags, that's totally fine, but please don't arbitrarily reword existing tags, even if you don't like what Erik's chosen, as it'll just make it less likely that your language gets the correct tags assigned by the neural network.


To summarise - there are two paths forward for this issue:

  1. You're up for helping: Add a comment saying you're up for helping. Update the tags some time in the next few days. Add a comment when you're done. We'll then add them to our training set and move forward.
  2. You not up for helping: No problem! Just please add a comment letting us know :)

If you tell us you're not able/wanting to help or there's no comment added, we'll automatically crowd-source this in a week or so.

Finally, if you have questions or want to discuss things, it would be best done on the forum, so the knowledge can be shared across all maintainers in all tracks.

Thanks for your help! :blue_heart:


Note: Meta discussion on the forum

ErikSchierboom commented 1 year ago

Exercise: two-fer

Code

section .rodata
ONE_FOR:    db "One for ", 0
YOU:        db "you", 0
ONE_FOR_ME: db ", one for me.", 0

section .text
global two_fer
two_fer:
    ; rdi contains optional word
    ; rsi contains destination buffer
    mov r10, rdi
    mov rdi, rsi
    ; r10 contains optional word
    ; rdi contains destination buffer
    ; ignoring rsi contents.
    ; using rsi to as input param to _CopyToBuffer

_TransferOneFor:
    mov rsi, ONE_FOR
    call _CopyToBuffer

_TestIncoming:
    cmp r10, 0h ;NULL
    jz _TransferYou
    cmp byte [r10], 0h
    jz _TransferYou

_TransferName:
    mov rsi, r10
    call _CopyToBuffer
    jmp _TransferAndOneForMe

_TransferYou:
    mov rsi, YOU
    call _CopyToBuffer

_TransferAndOneForMe:
    mov rsi, ONE_FOR_ME
    call _CopyToBuffer
    mov byte [rdi], 0h
    ret

_CopyToBuffer:
    cmp byte [rsi], 0h
    jz _CopyToBufferEnd
_CopyToBufferStart:
    mov al, byte [rsi]
    mov byte [rdi], al
    inc rdi
    inc rsi
    cmp byte [rsi], 0h
    jnz _CopyToBufferStart
_CopyToBufferEnd:
    ret

Tags:

construct:byte
construct:comment
construct:db
construct:global-label
construct:hexadecimal-number
construct:instruction
construct:label
construct:local-label
construct:mov
construct:parameter
construct:section-directive
construct:string
construct:undefined-value
construct:word
paradigm:imperative
paradigm:structured
ErikSchierboom commented 1 year ago

Exercise: two-fer

Code

 default rel

section .rodata
one_for:     db "One for "
one_for_len:    equ $ - one_for

you:     db "you"
you_len:    equ $ - you

one_for_me:  db ", one for me.", 0
one_for_me_len: equ $ - one_for_me

    ;; Parameters:
    ;; rdi - name (first arg)
    ;; rsi - buffer  (second arg)

section .text
global two_fer

two_fer:
    ; Provide your implementation here
    mov rax, rdi                ; Save the
    mov rdi, rsi                ;set destination to buffer ... ?
    lea rsi, [one_for]          ; lea == load effective address, set source
    mov rcx, one_for_len        ; set str length
                                ;
    rep movsb                   ; append string to buffer somehow?

    test rax, rax               ; check if name is provided
    jne .copy_name              ; if so, append name to buffer
    lea rsi, [you]
    mov rcx, you_len
    rep movsb
    jmp .end

.copy_name:
    mov rsi, rax
    cmp byte [rsi], 0
    je .end

.loop_start:
    movsb                       ; append char to buffer
    cmp byte [rsi], 0
    je .end

.end:
    lea rsi, [one_for_me]
    mov rcx, one_for_me_len
    rep movsb
    ret

Tags:

paradigm:assembly
paradigm:imperative
technique:bit-manipulation
technique:bit-shifting
ErikSchierboom commented 1 year ago

Exercise: two-fer

Code

global two_fer
extern sprintf
; this works on MacOS ... haven't tried on Linux

section .text
; two_fer(char *name, char *buffer) -> void
;       rdi is the address of the name
;       rsi is the address of the buffer
two_fer:
    ; sprintf(char *string, char *format, ...)
    ;     rdi <- address of buffer
    ;     rsi <- address of format
    ;     rdx <- address of name
    ;     rax <- number of floating point arguments
    mov rdx, rdi
    mov rdi, rsi
    xor eax, eax
    lea rsi, [rel format]

    test rdx, rdx ; check if name pointer is NULL
    jnz .perform_format
    lea rdx, [rel you_string]

.perform_format:
    ; Replacing the commented out part with the 'jmp'.
    ; sub rsp, 8
    ; call sprintf
    ; add rsp, 8
    jmp sprintf
    ; ret - not needed !! holy cow !!

section .rodata
format db "One for %s, one for me.", 0x00
you_string db "you", 0x00

Tags:

paradigm:assembly
paradigm:imperative
technique:bit-manipulation
technique:direct-jump
technique:memory-management
ErikSchierboom commented 1 year ago

Exercise: resistor-color

Code

default rel

section .rodata
black:  db "black", 0
brown:  db "brown", 0
red:    db "red", 0
orange: db "orange", 0
yellow: db "yellow", 0
green:  db "green", 0
blue:   db "blue", 0
violet: db "violet", 0
grey:   db "grey", 0
white:  db "white", 0

codes:  dq black, brown, red, orange, yellow
        dq green, blue, violet, grey, white, 0

section .text
global color_code
color_code:
        ;; prepare
        xor ecx, ecx
        lea r10, [rel codes]

.loop:
        ;; load (next) candidate address
        mov rsi, [r10 + rcx * 8]

.l1:
        ;; check that candidate
        mov r9, rdi
        mov al, [r9]
        cmp al, [rsi]
        jnz .not_equal
        test al, 0
        jz .ret_candidate
        inc r9
        inc rsi
        jmp .l1

.ret_candidate:
        mov rax, rcx
.end:
        ret

.not_equal:
        inc rcx
        cmp bl, 10
        jl .loop
        xor eax, eax
        dec rax
        jmp .end

global colors
colors:
        lea rax, [rel codes]
        ret

Tags:

paradigm:assembly
paradigm:imperative
paradigm:structured
technique:bit-manipulation
technique:looping
ErikSchierboom commented 1 year ago

Exercise: space-age

Code

section .text

; c algo:
;
; float age(enum planet planet, int seconds) {
;   float factors[] = {...};
;   int earth_period = 31557600;
;   return seconds / (earth_period * factors[planet]);
; }

global age
age:
    ; rdi = planet
    ; rsi = seconds

    mov r8, factors
    mov r10, earth_period
    mov r11, [8*rdi + r8] ; load factor

    cvtsi2ss xmm0, rsi         ; seconds
    cvtsi2ss xmm1, dword [r10] ; earth_period
    movss xmm2, dword [r11]    ; factor

    mulss xmm1, xmm2
    divss xmm0, xmm1

    ret

section .data
earth_period: dd 31557600

mercury: dd 0.2408467
venus: dd 0.61519726
earth: dd 1.0
mars: dd 1.8808158
jupiter: dd 11.862615
saturn: dd 29.447498
uranus: dd 84.016846
neptune: dd 164.79132

factors: dq mercury, venus, earth, mars, jupiter, saturn, uranus, neptune
factors_len equ $-factors

Tags:

construct:add
construct:assignment
construct:comment
construct:data-definition
construct:division
construct:double
construct:equ-directive
construct:floating-point-number
construct:global-label
construct:immediate-floating-point-number
construct:immediate-number
construct:indexed-access
construct:integral-number
construct:label
construct:memory-access
construct:multiply
construct:named-operand
construct:number
construct:parameter
construct:return
construct:section-directive
construct:variable
construct:visibility
paradigm:imperative
paradigm:reflective
technique:bit-manipulation
technique:bit-shifting
technique:bitwise-operations
technique:math:bit-manipulation
technique:math:division
technique:math:multiplication
uses:bitwise-operations
ErikSchierboom commented 1 year ago

Exercise: hamming

Code

; c algo :
; int distance(const char *a, const char *b) {
;     int dist = 0;
;     int i = 0;
;     while(a[i] && b[i]) {
;         dist += (a[i] == b[i]) ? 0 : 1;
;         i++;
;     }
;     return (a[i] != 0 || b[i] != 0) ? -1 : dist;
; }

section .text
global distance
distance:
    mov rax, 0 ; distance
    mov r8, 0  ; index

loop:
    mov r10b, byte [r8 + rdi]
    mov r11b, byte [r8 + rsi]

    cmp r10b, 0
    je loop_break

    cmp r11b, 0
    je loop_break

    cmp r10b, r11b
    setne r9b
    add rax, r9

    inc r8
    jmp loop
loop_break:

    cmp r10b, 0
    jne return_error

    cmp r11b, 0
    jne return_error

    ret

return_error:
    mov rax, -1
    ret

Tags:

construct:add
construct:boolean
construct:byte
construct:char
construct:comment
construct:compare
construct:global-label
construct:goto
construct:immediate-value
construct:index
construct:instruction
construct:int
construct:integral-number
construct:jump
construct:label
construct:logical-or
construct:memory
construct:mov
construct:number
construct:parameter
construct:return
construct:setne
construct:ternary
construct:text
construct:variable
construct:visibility
paradigm:imperative
paradigm:procedural
technique:boolean-logic
technique:looping
ErikSchierboom commented 1 year ago

Exercise: hamming

Code

section .text
global distance
distance:
    xor     rax, rax
compare_character:
    cmp     byte [rdi], 0x00
    jz      first_exhausted
    cmp     byte [rsi], 0x00
    jz      length_mismatch
    cmpsb
    jz      compare_character
    inc     rax
    jmp     compare_character
first_exhausted:
    cmp     byte [rsi], 0x00
    jz      finished
length_mismatch:
    xor     rax, rax
    dec     rax
finished:
    ret

Tags:

construct:byte
construct:comment
construct:compare
construct:hexadecimal-number
construct:instruction
construct:label
construct:memory-access
construct:parameter
construct:procedure
construct:return
construct:x86-64
paradigm:imperative
paradigm:structured
technique:bit-manipulation
technique:bit-shifting
ErikSchierboom commented 1 year ago

Exercise: allergies

Code

section .data
    allergy_score   dq 1,2,4,8,16,32,64,128 
section .text
global allergic_to
    allergic_to:
        push rbp
        mov rbp,rsp
        ; rdi - item, rsi - allergen
        lea rbx,[allergy_score]
        mov rcx,[rbx+8*rdi] 
        and rcx,rsi
        ; if 0 - false, if !0 - true
        mov rax,rcx
        leave
        ret

global list
list:
        ;1. iterate over array
        ;2. AND with each element
        ;3. Put in buffer, if matched
        ; rdi - allergen, rsi - buffer
        push rbp
        mov rbp,rsp
        mov qword[rsi],0
        cmp rdi,0
        je .leave
        lea rbx,[allergy_score]
        mov rcx,9
        mov r12,0 ;item pointer
        mov  r8,1 ;buffer pointer
    .loop:
        mov rdx,[rbx+8*r12]
        and rdx,rdi
        cmp rdx,0
        je .skip
        inc qword[rsi]        ; inc item_list.size
        mov qword[rsi+4*r8],r12   ; skip item_list.size
        inc r8
    .skip:
        inc r12
        loop .loop
.leave:
        leave
        ret

Tags:

construct:and
construct:comment
construct:data
construct:double
construct:floating-point-number
construct:global-label
construct:immediate
construct:instruction
construct:label
construct:lea
construct:loop
construct:memory-access
construct:multiply
construct:number
construct:parameter
construct:push
construct:qword
construct:return
construct:section
construct:size
construct:text
construct:variable
construct:visibility
paradigm:imperative
paradigm:procedural
technique:looping
ErikSchierboom commented 1 year ago

Exercise: matching-brackets

Code

;; For God so loved the world, that He gave His only begotten Son, 
;; that all who believe in Him should not perish but have everlasting life.
BITS 64
DEFAULT REL
global is_paired

section .data
    ;ascii (40 )41 {123 }125 [91 ]93  - Hallelujah
    pushes_aleluya: db '({[', 0 ;Praise the Lord, could add more bracket types here
    pops_aleluya: db ')}]', 0 ;Hallelujah closing bracket must match opening bracket index

section .text
;extern int is_paired(const char *str_hallelujah);
;INPUT:
;   rdi - null terminated string to check for is_paired
;RETURN:
;   rax - return 0 or 1 if it is a paired

;r8 -> input string ptr aleluya
;r9 -> hold rsp aleluya
;r10 -> opening bracket array (null terminated) aleluya
;r12 -> callee saved - closing bracket array (null terminated) aleluya
;cl -> input string current char aleluya
;dl -> temporary valuye depending upon block aleluya
;r11 -> temporary index into arrays depending upon block aleluya
is_paired:
    mov r8, 0
    push r12
    mov r9, rsp
    push 0
    mov r10, pushes_aleluya
    mov r12, pops_aleluya

_loop_str_aleluya: 
    mov cl, [rdi + r8]
    cmp cl, 0
    je _paired_chk1_aleluya
    inc r8
    mov r11, 0

_loop_pushes_aleluya:
    mov dl, [r10 + r11]
    cmp dl, 0
    je _is_not_push_aleluya
    cmp dl, cl
    je _is_push_aleluya
    inc r11
    jmp _loop_pushes_aleluya

_is_not_push_aleluya:
    mov r11, 0

_loop_pops_aleluya:
    mov dl, [r12 + r11]
    cmp dl, 0
    je _loop_str_aleluya
    cmp dl, cl
    je _is_pops_aleluya
    inc r11
    jmp _loop_pops_aleluya

_is_push_aleluya:
    movzx rdx, byte [r12 + r11]
    push rdx
    jmp _loop_str_aleluya

_paired_chk1_aleluya:
    pop rdx
    cmp rdx, 0
    jne _not_all_closed_aleluya
    mov rax, 1
    pop r12
    ret

_is_pops_aleluya:
    pop rdx
    cmp rdx, 0
    je _empty_pops_stack_error_aleluya

    cmp dl, cl 
    je _loop_str_aleluya
    ; Wrong bracket close if reaching here and fail - Glory to Jesus
_wrong_pops_aleluya:
_empty_pops_stack_error_aleluya:
_not_all_closed_aleluya:
    mov rax, 0
    mov rsp, r9
    pop r12
    ret

Tags:

paradigm:assembly
paradigm:functional
technique:bit-manipulation
technique:bit-shifting
technique:bitwise-operators
technique:higher-order-functions
technique:looping
technique:stack
uses:Stack
ErikSchierboom commented 1 year ago

Exercise: rna-transcription

Code

section .text
global to_rna
to_rna:
    ; Provide your implementation here
    push rbx
    push rdi
    push rsi

    jz to_rna.end
    xor rax, rax
to_rna.loop:
    cmp byte [rdi], 0
    jz to_rna.end
    mov al, byte [rdi]
    cmp al, 'A'
    jz to_U
    cmp al, 'C'
    jz to_G
    cmp al, 'G'
    jz to_C
    cmp al, 'T'
    jz to_A
to_rna.loop.post_translation:
    mov byte [rsi], bl
    inc rdi
    inc rsi
    jmp to_rna.loop

to_rna.end:
    mov byte[rsi], 0
    pop rsi
    pop rdi
    pop rbx
    ret

to_U:
    mov bl, 'U'
    jmp to_rna.loop.post_translation
to_G:
    mov bl, 'G'
    jmp to_rna.loop.post_translation
to_C:
    mov bl, 'C'
    jmp to_rna.loop.post_translation
to_A:
    mov bl, 'A'
    jmp to_rna.loop.post_translation

Tags:

construct:assignment
construct:byte
construct:char
construct:comment
construct:compare
construct:global-label
construct:goto
construct:hexadecimal-number
construct:instruction
construct:jump
construct:label
construct:memory-access
construct:parameter
construct:pop
construct:push
construct:readme
construct:return
construct:string
construct:subtract
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:structured
ErikSchierboom commented 1 year ago

Exercise: reverse-string

Code

section .text
global reverse

; reverse(char *string) -> void
; arguments:
;     rdi is the pointer to the string
; no return value

; This uses the stack to reverse the string.
reverse:
    push rbp
    mov rbp, rsp

    mov rsi, rdi
    xor eax, eax
    cld

.push_bytes:
    lodsb
    cmp al, 0
    jz .pop_bytes
    push ax
    jmp .push_bytes

.pop_bytes:
    cmp rdi, rsi
    jge .done
    pop ax
    stosb
    jmp .pop_bytes

.done:
    xor eax, eax
    leave
    ret

Tags:

construct:asm
construct:comment
construct:global-label
construct:instruction
construct:int
construct:label
construct:memory-access
construct:named-argument
construct:parameter
construct:push
construct:return
construct:string
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:structured
technique:bit-manipulation
technique:bit-shifting
ErikSchierboom commented 1 year ago

Exercise: reverse-string

Code

default rel

section .text
global reverse
reverse:
    mov rsi, rdi
move_to_last_byte:
    inc rsi
    cmp byte[rsi], 0
    jne move_to_last_byte

    dec rsi
swapping:
    cmp rdi, rsi
    ja end
    mov dl, [rsi]
    mov cl, [rdi]
    mov [rdi], dl
    mov [rsi], cl
    inc rdi
    dec rsi
    jmp swapping

end:
    ret

Tags:

x86-64 assembly
bitwise operation
goto
label
mov
paradigm:imperative
paradigm:structured
technique:bit manipulation
technique:looping
ErikSchierboom commented 1 year ago

Exercise: reverse-string

Code

section .text
global reverse
reverse:
    xor rax, rax
    test rdi, rdi
    je .return

.len:
    inc rax
    cmp byte [rdi + rax], 0
    jne .len

    xor rcx, rcx
    dec rax

.rev:
    movzx edx, byte [rdi + rcx]
    movzx esi, byte [rdi + rax]
    mov byte [rdi + rax], dl
    mov byte [rdi + rcx], sil

    inc rcx
    dec rax

    cmp rcx, rax
    jl .rev

.return:
    ret

Tags:

construct:add
construct:byte
construct:cmp
construct:global-label
construct:instruction
construct:je
construct:jl
construct:jne
construct:label
construct:memory-access
construct:mov
construct:parameter
construct:ret
construct:test
construct:variable
construct:x86-64
construct:xor
paradigm:imperative
paradigm:procedural
ErikSchierboom commented 1 year ago

Exercise: pangram

Code

section .text
global is_pangram
is_pangram:
    ; I use eax for 26 flags representing the 26 letters
    xor eax, eax
    ; loop conditions are actually checked twice
    ; once before for fast exit on empty strings
    ; once at the end of the loop for the cycling
    mov cl, [rdi]
    test cl, cl
    je .end
  .loop:
    ; this is a fast to-upper-case hack
    or cl, 32
    ; check boundaries
    cmp cl, 'a'
    jl .next
    cmp cl, 'z'
    jg .next
    ; remember we saw a certain letter
    sub cl, 'a'
    mov ebx, 1
    shl ebx, cl
    or eax, ebx
  .next:
    ; go to next character
    inc rdi
    mov cl, [rdi]
    test cl, cl
    jne .loop
  .end:
    ; fast check if all 26 bits are set
    cmp eax, 67108863
    sete al
    ret

Tags:

construct:comment
construct:compare
construct:global-label
construct:instruction
construct:je-jz
construct:jg
construct:jl
construct:label
construct:loop
construct:mov
construct:or
construct:ret
construct:setcc
construct:shl
construct:sub
construct:test
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:structured
technique:bit-manipulation
technique:bit-shifting
technique:boolean-logic
technique:looping
ErikSchierboom commented 1 year ago

Exercise: pangram

Code

;; For God so loved the world, that He gave His only begotten Son, 
;; that all who believe in Him should not perish but have everlasting life.
BITS 64
DEFAULT REL

section .rodata
alphabet_aleluya: db "abcdefghijklmnopqrstuvwxyz", 0

section .text
global is_pangram
extern malloc ; Hallelujah, not overwrite source, not check again for every letter for uppercase
extern free

;converts upper case to lower
;ascii 65<=UPPER<=90 97<=lower<=122

;rdi - null terminated string to check for is_pangram
;return rax 0 or 1 if it is a pangram
is_pangram:    
    mov rax, 0 ;rax=0 assume false
    cmp rdi, 0     
    jnz not_null_string_aleluya
    ret

not_null_string_aleluya:
    cmp [rdi], byte 0
    jne not_empty_string_aleluya    
    ret

not_empty_string_aleluya:
    ; make string lowercase
    ; find string length
    push r10 ; to hold malloc string
    push r8 ; input ptr aleluya, will have length
    push rbx ; cur char aleluya
    push rsi ; alphabet ptr aleluya
    push r9 ; cur alphabet ptr
    push rcx ; cur alphabet aleluya
    mov r8, 0

find_length_loop_aleluya:
    cmp [rdi + r8], byte 0
    je found_length_aleluya
    inc r8
    jmp find_length_loop_aleluya

found_length_aleluya: ; r8 has length, Hallelujah
    push rdi
    inc r8
    mov rdi, r8
    call malloc wrt ..plt
    pop rdi
    mov r10, rax 
    mov rsi, alphabet_aleluya ; rsi ptr to string for lowercase letters
    mov r9, 0

lowercase_it_loop_aleluya:
    mov cl, [rdi + r9]
    cmp cl, 90
    jnle nochange_aleluya
    cmp cl, 65
    jnge nochange_aleluya
    add cl, 32

nochange_aleluya:
    mov [r10 + r9], cl
    inc r9
    cmp cl, 0
    jne lowercase_it_loop_aleluya

    mov r9, 0
    mov r8, 0
    mov rax, 0

char_loop_aleluya:
    mov bl, [rsi + r9]
    cmp bl, 0 ; Reach end of char string? means all found, Hallelujah
    jz true_return_aleluya ; rax default is 0
    inc r9
    mov r8, 0 

str_loop_aleluya:
    mov cl, [r10 + r8]
    cmp cl, 0
    jz false_return_aleluya ; letter not found in string

    inc r8
    cmp cl, bl
    jne str_loop_aleluya ;letter not match, continue down string Hallelujah    
    je char_loop_aleluya ;letter match, go to next letter Hallelujah

true_return_aleluya:
    mov rax, 1

false_return_aleluya: ; rax kept 0 for default, Hallelujah
    mov rbx, rax ; store these, hallelujah
    mov rcx, rdi

    mov rdi, r10
    call free wrt ..plt

    mov rax, rbx
    mov rdi, rcx

    pop rcx
    pop r9
    pop rsi
    pop rbx
    pop r8
    pop r10

    ; Provide your implementation here
    ret

Tags:

paradigm:assembly
paradigm:functional
technique:bit-manipulation
technique:bit-shifting
technique:bitwise-operators
technique:higher-order-functions
ErikSchierboom commented 1 year ago

Exercise: isogram

Code

section .text
global is_isogram
is_isogram:
    ; I use eax for 26 flags representing the 26 letters
    xor eax, eax
    ; loop conditions are actually checked twice
    ; once before for fast exit on empty strings
    ; once at the end of the loop for the cycling
    mov cl, [rdi]
    test cl, cl
    je .okay
  .loop:
    ; this is a fast to-lower-case hack
    or cl, 32
    ; check boundaries
    cmp cl, 'a'
    jl .next
    cmp cl, 'z'
    jg .next
    ; check if we saw the character already
    sub cl, 'a'
    mov ebx, 1
    shl ebx, cl
    test eax, ebx
    jnz .already_seen
    ; remember we saw the character
    or eax, ebx
  .next:
    ; go to next character
    inc rdi
    mov cl, [rdi]
    test cl, cl
    jne .loop
  .okay:
    xor al, al
    inc al
    ret
  .already_seen:
    xor al, al
    ret

Tags:

construct:comment
construct:global-label
construct:instruction
construct:jump
construct:label
construct:memory-access
construct:mov
construct:parameter
construct:return
construct:string
construct:test
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:structured
ErikSchierboom commented 1 year ago

Exercise: grains

Code

section .text
global square
square:
    xor rax, rax
    mov cl, dil
    dec cl
    test cl, 0xC0
    jnz .end
    inc rax
    shl rax, cl
  .end:
    ret

global total
total:
    xor rax, rax
    not rax
    ret

Tags:

construct:assembly
construct:bitwise-operation
construct:global-label
construct:goto
construct:hexadecimal-number
construct:instruction
construct:label
construct:mov
construct:parameter
construct:ret
construct:shift-left
construct:variable
construct:visibility
paradigm:imperative
paradigm:structured
technique:bit-manipulation
technique:bit-shifting
ErikSchierboom commented 1 year ago

Exercise: grains

Code

section .text
global square
square:
    ; n = rdi
    ; x = 2 ** (n-1)
    movsx rdi, edi
    cmp   rdi, 0
    jle   .return_zero
    mov   rax, rdi
    cmp   rdi, 2
    jle   .end
    mov   rax, 2

.loop:
    dec   rdi
    imul  rax, 2
    cmp   rdi, 2
    jne   .loop

.end:
    ret

.return_zero:
    mov rax, 0
    ret

global total
total:
    ; x = (2 ** 64) - 1
    mov  r8, 64
    mov  rax, 2

    loop2:
    imul rax, 2
    dec  r8
    cmp  r8, 0
    jne  loop2

    dec  rax
    ret

Tags:

paradigm:assembly
paradigm:imperative
technique:bit-manipulation
technique:looping
ErikSchierboom commented 1 year ago

Exercise: difference-of-squares

Code

section .text

global square_of_sum
square_of_sum:
    ; Provide your implementation here
    ; sum(n) = n(n+1)/2
    lea rax, [rdi+1]
    imul rax, rdi
    shr rax, 1
    imul rax, rax   ; squared
    ret

global sum_of_squares
sum_of_squares:
    ; Provide your implementation here
    ; sum(n^2) = n(n+1)(2n+1)/6
    lea rdx, [rdi+1]        ; n+1
    lea rax, [rdx+rdi]  ; 2n+1
    imul rax, rdi
    imul rax, rdx
    mov rdx, 0x2aaaaaaaaaaaaaab
    mul rdx     ; rdx = rax / 6
    mov rax, rdx
    ret

global difference_of_squares
difference_of_squares:
    ; Provide your implementation here
    ; sum(n^2)-sum(n)^2 = n(n+1)(3n^2-n-2)/12
    mov rcx, rdi
    imul rcx, rcx   ; n^2
    lea rax, [rcx+rdi]  ; n(n+1)
    imul rcx, rax   ; n(n+1)*n^2
    add rdi, 2
    imul rax, rdi   ; n(n+1)(n+2)
    mov rdx, 0x5555555555555556
    mul rdx     ; rdx = n(n+1)(n+2)/3
    mov rax, rcx
    sub rax, rdx    ; n(n+1)(n^2-(n+2)/3)
    shr rax, 2      ; n(n+1)(3n^2-n-2)/12
    ret

Tags:

paradigm:assembly
paradigm:imperative
technique:bit-shifting
technique:looping
ErikSchierboom commented 1 year ago

Exercise: binary-search

Code

section .text
; int find(int *array, int size, int value);
;   rdi     pointer to the array
;   rsi     size of the array
;   rdx     value to search for
;   rax     return -1 when value isn't found, otherwise the index where the value was found
global find
find:
    test rdi, rdi           ; check for a null array, test x,x is slightly faster than cmp x,0
    jz  .value_not_found    ; stop if the array is null
;   rcx     store the original array start so we can calculate the correct index at the end
    mov rcx, rdi
.loop:
    test rsi, rsi           ; check length of array
    jle .value_not_found    ; zero/negative length means no match
    mov rax, rsi            ; copy the array size
    shr rax, 1              ; divide the current array size in half to get the middle index to check
;   edx     dword/int version of rdx    
    cmp edx, dword [rdi + rax * 4]    ; test the value at the current index
    jl  .lesser             ; when target values is less than value at current index
    jg  .greater            ; when target values is greater than value at current index
.equal:                     ; value matched, return the index of the current element based on the original array start
    sub rdi, rcx            ; get diference of current array start and the original array start
    shr rdi, 2              ; divide it by 4: the difference is in bytes, but we need it in dwords
    add rax, rdi            ; add the difference to the current index used 
    ret
.lesser:                    ; continue search at lower indices in the array
    mov rsi, rax            ; make the current index, the new size (upper bound) of the array
    jmp .loop               ; continue loop with new bounds for the array
.greater:                   ; continue search at higher indices in the array
    inc rax                 ; get the index of the next element
    sub rsi, rax            ; decrease the array size by the number of elements before the next element
    lea rdi, [rdi + rax * 4]    ; shift the array start to the next element
    jmp .loop               ; continue loop with new bounds for the array
.value_not_found:
    mov rax, -1 ; set return value to indicate value wasn't found
    ret

Tags:

technique:bit manipulation
technique:bit shift
technique:looping
technique:parameter passing
technique:subtract
technique:variable assignment
paradigm:imperative
paradigm:low-level assembly
ErikSchierboom commented 1 year ago

This is an automated comment

Hello :wave: Next week we're going to start using the tagging work people are doing on these. If you've already completed the work, thank you! If you've not, but intend to this week, that's great! If you're not going to get round to doing it, and you've not yet posted a comment letting us know, could you please do so, so that we can find other people to do it. Thanks!