5 ms·
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
by kabdib 11y ago
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.
- mikeash 11y agoDear god. I don't know if we should give you a Nobel Prize or put you in prison. Probably both.
- kabdib 11y agoPretty much that reaction :-)
- quantumtremor 11y agoELI someone who knows mips?
- pbsd 11y agoBasically 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); }
- bbcbasic 11y agoHmm. 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.
- ScottBurson 11y agoYou're right. This isn't recursion by any definition I know. Cute, though.
- bbcbasic 11y agoYes 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.
- LesZedCB 11y agoIt'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.
- sgustard 11y agoIt'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
- blt 11y agoWhat instruction set is this?
- kabdib 11y agoMy 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 http://www.dadhacker.com/blog/?p=1911 Apparently the original code did multiplies by 10s, so the leaf routine was a few more instructions.
- kabdib 11y agoI 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.
- bliti 11y agoBrilliant! 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
- copsarebastards 11y ago> 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.
- bliti 11y agoThat's the joke. :)
- hellbanner 11y agoCan you explain this a bit? I read http://docs.oracle.com/cd/E19455-01/806-3773/instructionset-90/index.html http://docs.oracle.com/cd/E19455-01/806-3773/instructionset-... but I'm not sure I follow what X32 is.. times 32?
- shiro 11y ago"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.
- UnquietTinkerer 11y agoI think BSR here stands for "branch to subroutine", i.e. CALL.
- userbinator 11y agoThe "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
- kabdib 11y agoThanks. 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 :-)