C & ARM Assembly solution to a math puzzle

jasonfriday2.c

/* C version loosely based on jasonfriday2.s
 *
 * Compile on almost any computer using
 *   gcc -O3 -std=c99 -o jasonfriday jasonfriday2.c
 *
 * Henrik Nordstrom <henrik@henriknordstrom.net> (github user hno)
 * January 17, 2017
 */
#include <stdio.h>
#include <stdlib.h>

static int
itoa(unsigned int n, char *buf)
{
	int len = 0;

	while (n >= 10) {
		int new_n = (n * (unsigned long long)0xcccccccd) >> 35;
		int rem = n - new_n * 10;
		buf[len++] = rem + '0';
		n = new_n;
	}
	buf[len++] = n + '0';
	buf[len] = 0;

	/* Reverse output so highest digit is first */
	for (int i = 0; i <= len/2-1; i++) {
		char t = buf[i];
		buf[i] = buf[len-1-i];
		buf[len-1-i] = t;
	}

	return len;
}

void
solve_jason(void)
{
	for (int jason = 12345; jason <= 1000000/13; jason++) {
		int friday = jason * 13;
		if (friday < 100000 || friday > 987654)
			continue;
		char t_jason[6], t_friday[7];
		itoa(jason, t_jason);
		itoa(friday, t_friday);
		if (t_jason[1] != t_friday[4])
			continue;

		unsigned long seen = 0;
		for (int i = 0; i < 5; i++)
			seen |= 1 << (t_jason[i] - '0');
		for (int i = 0; i < 6; i++)
			seen |= 1 << (t_friday[i] - '0');
		if (seen != (1 << 10)-1)
			continue;

		printf("%d * 13 = %d\n", jason, friday);
	}
}


int
main(int argc, char **argv)
{
	// Repeat 1000 times to allow timing measurements
	for (int i = 0; i < 1000; i++)
		solve_jason();
}

jasonfriday2.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 cycling through all possible values for JASON
@ (12,345 up to 100,000/13) and computing 13 * JASON for each one.
@ It then converts each number to a string and checks the results
@ to see if they match the constraints.
@
@ 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
result:     .ascii  "jason = "
jasontxt:   .space  5
            .ascii  ", friday = "
fridaytxt:  .space  7
            .equ    resultlen, .-result

            .text
_start:
            @ Repeat 1000 times to allow timing measurements
            ldr     r4, =1000
1:
	bl      _solve_jason
	subs     r4, r4, #1
	bne     1b

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

_solve_jason:
            push    {r4-r5, lr}
            @ r4: jason
            @ r5: friday

            @ no leading zeros allows, so start
            @ with jason = 12345
            ldr     r4, =12345
            b       5f
1:
            @ compute friday = 13 * jason
            add     r5, r4, r4, lsl #1
            add     r5, r4, r5, lsl #2

	    @ check friday bounds
	    ldr     r0, =123456
	    cmp     r5, r0
	    blt     4f
	    ldr     r0, =987654
            cmp     r5, r0
	    bgt     4f

            @ convert json to text
            ldr     r0, =jasontxt
            mov     r1, r4
            bl      itoa

            @ convert friday to text
            ldr     r0, =fridaytxt
            mov     r1, r5
            bl      itoa

            @ 'a' in jason and in friday must match
            ldr     r0, =jasontxt
            ldrb    r1, [r0, #1]
            ldr     r0, =fridaytxt
            ldrb    r2, [r0, #4]
            cmp     r1, r2
            bne     4f

            @ check that each digit is used exactly once
            @ set bit #n when we find digit n
            @ end result should be the number 1111111111
            mov     r0, #0
            mov     r1, #0
            mov     ip, #1
            ldr     r2, =jasontxt
2:
            ldrb    r3, [r2,r1]
            sub     r3, r3, #'0'
            orr     r0, r0, ip, lsl r3
            add     r1, r1, #1
            cmp     r1, #5
            blt     2b

            mov     r1, #0
            ldr     r2, =fridaytxt
3:
            ldrb    r3, [r2,r1]
            sub     r3, r3, #'0'
            orr     r0, r0, ip, lsl r3
            add     r1, r1, #1
            cmp     r1, #6
            blt     3b

            ldr     r1, =0b1111111111
            cmp     r0, r1
            bne     4f

            @ found a solution, so print result
            @ append a newline
            mov     r0, #'\n'
            ldr     r1, =fridaytxt
            strb    r0, [r1,#6]

            mov     r0, #stdout
            ldr     r1, =result
            mov     r2, #resultlen
            mov     r7, #sys_write
            svc     #0

4:
            add     r4, r4, #1
5:
            ldr     r0, =1000000/13
            cmp     r4, r0
            ble     1b

	    pop     {r4-r5, pc}


@ itoa(buffer, n) -> number of bytes written
itoa:
            .equ    div10_magic, 0xcccccccd
            push    {r4-r6,lr}
            @ r0: buffer
            @ r1: n
            @ r2: length of output
            @ r3: division magic number
            @ r4: digit
            @ r5: new n
            ldr     r3, =div10_magic
            mov     r2, #0
1:
            @ do a division by 10
            umull   r4, r5, r3, r1          @ multiply by magic number
            mov     r5, r5, lsr #3          @ shift: new_n is in r5
            add     r4, r5, r5, lsl #2      @ compute new_n*5
            sub     r4, r1, r4, lsl #1      @ remainder = n - new_n*5*2
            add     r4, r4, #'0'            @ convert to digit
            strb    r4, [r0,r2]             @ store in buffer
            add     r2, r2, #1              @ length++
            subs    r1, r5, #0              @ n = newn and compare with 0
            bgt     1b

            @ reverse the string
            @ r0: first
            @ r1: last
            @ r2: length of output
            @ r3: firstchar
            @ r4: lastchar
            add     r1, r0, r2
            sub     r1, r1, #1
            bal     3f

2:
            ldrb    r3, [r0]
            ldrb    r4, [r1]
            strb    r3, [r1], #-1
            strb    r4, [r0], #1

3:
            cmp     r0, r1
            blt     2b

            mov     r0, r2
            pop     {r4-r6,pc}