ARMv6 assembly solution to a math puzzle

jasonfriday.s

@ ARMv6 solution to the puzzle:
@
@   13 JASONs when added equal FRIDAY.
@   Use only the digits 0 to 9.
@   No leading zeros. Each letter maps to one and
@   only one number.
@
@           JASON + JASON +
@   JASON + JASON + JASON +
@   JASON + JASON + JASON +
@   JASON + JASON + JASON +
@           JASON + JASON = FRIDAY
@
@ Note: this solution assumes each digit can only be used
@ once, i.e., there is a bijection between the digits
@ (0..9) and the letters (j,a,s,o,n,f,r,i,d,y).
@
@ It works by taking a list of the digits (0..9), then generating
@ every permutation of that list. The letter associated with each
@ digit is implied by the position in the list, e.g., 'j' is always
@ the first digit in the list, 'a' the second, and so on.
@
@ Compile on a Raspberri Pi running Raspbian using:
@   as -g jasonfriday.s -o jasonfriday.o
@   ld jasonfriday.o -o jasonfriday
@
@ Russ Ross (github user russross), January 15, 2017

            .global _start

            .equ    sys_exit, 1
            .equ    sys_write, 4
            .equ    stdout, 1

            .data
@ all of the letters that should be reported
@ when a solution is printed
txt:        .ascii  "jason"
            .ascii  "friday"
            .equ    txtlen, .-txt

@ for each letter in "jason", give the offset into the
@ list of digits where that letter's digit can be found
jason:      .byte   0, 1, 2, 3, 4
            .equ    jasonlen, .-jason

@ same for "friday"
friday:     .byte   5, 6, 7, 8, 1, 9
            .equ    fridaylen, .-friday

@ the digits 0..9. this list is permuted in placed
perm:       .byte   0, 1, 2, 3, 4, 5, 6, 7, 8, 9
            .equ    permlen, .-perm

@ a text buffer for preparing a line of output
@ when a solution is found
buffer:     .space  100

            .text
@ kick off the search, then exit when finished
_start:
            @ start the main search
            mov     r0, #0
            bl      permute

            @ exit
            mov     r0, #0
            mov     r7, #sys_exit
            svc     #0

@ generate all permutations of (0..9) and call check on each one
@ pseudo-code:
@   permute(a)
@     if a == length of list - 1
@       check for solution
@       return
@     for (b = a; b < length of list; b++)
@       swap elements a and b
@       permute(a+1)
@       swap elements a and b back
permute:
            @ r0: first position to swap
            @ r1: second position to swap
            @ r2: perm
            @ r3, r4: temp register for swapping

            @ base case: if r0 = permlen-1, check for solution and return
            cmp     r0, #permlen-1
            blt     1f
            push    {r0,lr}
            bl      check
            pop     {r0,pc}

1:
            @ loop r1 from r0 to permlen
            ldr     r2, =perm
            mov     r1, r0
2:
            @ swap position r0 with position r1
            ldrb    r3, [r2, r0]
            ldrb    r4, [r2, r1]
            strb    r3, [r2, r1]
            strb    r4, [r2, r0]

            @ call permute recursively with r0+1
            push    {r0-r2, lr}
            add     r0, r0, #1
            bl      permute
            pop     {r0-r2, lr}

            @ swap back to original positions
            ldrb    r3, [r2, r0]
            ldrb    r4, [r2, r1]
            strb    r3, [r2, r1]
            strb    r4, [r2, r0]

            @ continue loop
            add     r1, r1, #1
            cmp     r1, #permlen
            blt     2b

            @ return
            bx      lr

@ check to see if this mapping of letters to digits
@ satisfies the problem requirements
check:
            @ skip cases with leading zeros, i.e., j=0 or f=0

            @ look up value associated with 'j' in jason
            @ and check if it is a zero
            ldr     r0, =perm
            ldr     r1, =jason
            ldrb    r2, [r1]
            ldrb    r3, [r0,r2]
            cmp     r3, #0
            bxeq    lr

            @ do the same for the 'f' in friday
            ldr     r1, =friday
            ldrb    r2, [r1]
            ldrb    r3, [r0, r2]
            cmp     r3, #0
            bxeq    lr

            @ compute the value of "jason"
            @ r0: perm
            @ r1: jason/friday
            @ r2: index
            @ r3: value of jason * 13
            @ r4: value of friday
            @ r5: temp
            ldr     r0, =perm
            ldr     r1, =jason
            mov     r2, #0
            mov     r3, #0
            b       2f
1:
            @ r3 = r3 * 10
            add     r3, r3, r3, lsl #2
            add     r3, r3, r3

            @ r3 = r3 + value for next digit of jason
            ldrb    r5, [r1,r2]
            ldrb    r5, [r0,r5]
            add     r3, r3, r5

            @ continue loop
            add     r2, r2, #1
2:
            cmp     r2, #jasonlen
            blt     1b

            @ r3 = r3 * 13
            add     r5, r3, r3, lsl #1
            add     r3, r3, r5, lsl #2

            @ compute value of friday
            ldr     r1, =friday
            mov     r2, #0
            mov     r4, #0
            b       4f
3:
            @ r4 = r4 * 10
            add     r4, r4, r4, lsl #2
            add     r4, r4, r4

            @ r4 = r4 + value for next digit of friday
            ldrb    r5, [r1,r2]
            ldrb    r5, [r0,r5]
            add     r4, r4, r5

            @ continue loop
            add     r2, r2, #1
4:
            cmp     r2, #fridaylen
            blt     3b

            @ is jason * 13 = friday?
            cmp     r3, r4
            bxne    lr
            
            @ report a solution (tail call, so b works fine)
            b       report

@ report a solution (mapping of letters to digits) to stdout
report:
            @ r0: buffer
            @ r1: buffer offset
            @ r2: txt
            @ r3: loop index
            @ r4: temp
            @ r5: perm
            @ r6: jason
            @ write the solution to the buffer
            ldr     r0, =buffer
            mov     r1, #0
            ldr     r2, =txt
            mov     r3, #0
            ldr     r5, =perm
            ldr     r6, =jason
            b       2f

1:
            @ write "j=3 " or similar to the buffer

            @ first get the letter
            ldrb    r4, [r2,r3]
            strb    r4, [r0,r1]
            add     r1, r1, #1

            @ add an equal sign
            mov     r4, #'='
            strb    r4, [r0,r1]
            add     r1, r1, #1

            @ now look up the value associated with the letter
            ldrb    r4, [r6,r3]
            add     r4, r4, r5
            ldrb    r4, [r4]
            add     r4, r4, #'0'
            strb    r4, [r0,r1]
            add     r1, r1, #1

            @ add a space
            mov     r4, #' '
            strb    r4, [r0,r1]
            add     r1, r1, #1

            @ continue loop
            add     r3, r3, #1
2:
            cmp     r3, #txtlen
            blt     1b

            @ replace trailing space with a newline
            mov     r4, #'\n'
            sub     r5, r1, #1
            strb    r4, [r0,r5]

            @ write buffer to stdout
            mov     r2, r1
            mov     r1, r0
            mov     r0, #stdout
            mov     r7, #sys_write
            svc     #0

            bx      lr