Hacker News Reader

Comment by kabdib | Hacker News Reader

I've encountered knee-jerk negative reactions to recursion from most firmware engineers.

Then one day I got one to laugh at this byte-saving routine to do some multiplications:

    X32:    BSR X16
    X16:    BSR X8
    X8:     BSR X4
    X4:     BSR X2
    X2:     ADD A
            RET

Recursion. In assembly language. We were six bytes shy of filling our code space, but we had gobs of stack, and I got about 60 bytes back from our stupid compiler with this. When my cow-orker saw it, he thought for a moment, smiled, said "You're one sick dude, you know that?" and we checked it in.

View on HN

The "calling itself inline" pattern is well known in the demoscene/sizecoding community as a way to repeat something a small fixed number of times with neither an explicit loop nor duplicating code, and probably was independently discovered by quite a few individuals.

Here is one of the more interesting applications, a function that converts a 16-bit word in a register to a string of 4 hex digits in only 24 bytes of code, and can also be called to convert bytes and nybbles (x86):

        ; output value of AX as four hex digits to ES:DI
    write_hex_word:
        xchg al, ah
        call write_hex_byte
        xchg al, ah
        ; output value of AL as two hex digits to ES:DI
    write_hex_byte:
        push ax
        shr al, 4
        call write_hex_nybble
        pop ax
        ; output lower nybble of AL as hex digit to ES:DI
    write_hex_nybble:
        and al, 15
        cmp al, 10
        sbb al, 69h
        das
        stosb
        ret

Thanks. You can learn a lot from the demoscene folks.

Of course, your cow-orkers might wish you hadn't, depending on the amount of restraint you can summon :-)

Dear god. I don't know if we should give you a Nobel Prize or put you in prison. Probably both.

Pretty much that reaction :-)

Can you explain this a bit? I read http://docs.oracle.com/cd/E19455-01/806-3773/instructionset-... but I'm not sure I follow what X32 is.. times 32?

"X32:" etc. are labels, e.g. just names of functions or destinations of jump. Suppose you want to multiply A-reg by 4. Your code calls subroutine X4. That's immediately calls subroutine X2 (BSR X2), which doubles A (ADD A), and return. The return location is the next instruction of BSR X2--which is actually overlapping the subroutine X2. It doubles A again (ADD A), and returns to your code.

I think BSR here stands for "branch to subroutine", i.e. CALL.

I should add this: Why not just shift left? It's been a while, but I think the ADD A was really some 16-bit ADD. The key to making it small was this "inline recursion" thing, which wouldn't have occurred to most of the crusty firmware folks I've worked with because of fear.

ELI someone who knows mips?

Basically equivalent to this C code (assuming BSR = procedure call):

    int x2(int x) { return x + x; }
    int x4(int x) { return x2(x) + x2(x); }
    int x8(int x) { return x4(x) + x4(x); }
    int x16(int x) { return x8(x) + x8(x); }
    int x32(int x) { return x16(x) + x16(x); }

Hmm. How is this recursion?

Maybe I don't understand what the word recursion means, but I thought that you'd have to call yourself directly or indirectly.

It's not recursion in the sense that it calls itself. However, it does divide the problem into smaller (though explicitly defined) chunks, which is still recursion.

You could state it that the multiple by a power of two is the sum of the multiples of one order of magnitude base 2 lower.

You're right. This isn't recursion by any definition I know. Cute, though.

Yes from the answers it seems it is recursion, as long as you stretch the definition of recursion to mean making subroutine calls, or code that can be refactored into a recursive solution.

By these definitions, all but the most trivial code is recursive.

It's equivalent to this recursive function, just change x2(n) to x(n, 2) and so on.

  // e is a power of two
  int mult(x, e)
    return e==1 ? x : mult(x, e/2) + mult(x, e/2)
  end

What instruction set is this?

My fuzzy memories of an STM8, made by ST Microelectonics.

The piece of code in question was to use the chip as a smart power controller. Worked pretty well, aside from the limited code space.

Here's a blog entry about the little project: http://www.dadhacker.com/blog/?p=1911

Apparently the original code did multiplies by 10s, so the leaf routine was a few more instructions.

Brilliant! Let's make sure to include this in the standard tech interview questions set. We only hire the top 1% of the top 1%. Some Assembly required. :D

> Brilliant! Let's make sure to include this in the standard tech interview questions set. We only hire the top 1% of the top 1%.

First of all, that's the top 0.01%. Second of all, with that strategy, no you don't because the top 0.01% are going to walk out of interviews that ask dumb brain teasers. The best programmers are ones who can solve problems in the context of a team and codebase, with the help of the internet and iteration, not solve obscure but not-really-that-hard problems in 15 minutes.

That's the joke. :)

Reply on news.ycombinator.com