Posted December 19 2008 A series of regex-writing challenges. A series of XSS challenges: here's some unsafe code; exploit it! Shortest code wins. I needed some valid SWF files with constrained character sets for an injection PoC. Putting them here in case someone else needs some. PHP has finally taken the plunge into the 1960s by implementing GOTO. Here's an implementation for Java.
My CSS-fu is weak; please use a recent browser. Random, semi-related image by ~fb~. |
## Bit Tricks, Part I: Exact DivisionGCC has some clever tricks up its sleeve for compiling the humble division operator. This is part 1 of a series of posts on bit-twiddling tricks and micro-optimizations. This one looks at ways to try to optimize the following function:
## Recap: Two's complementInteger arithmetic (in binary) is usually done in two's complement ...00000000010 = 2 ...00000000001 = 1 ...00000000000 = 0 ...11111111111 = -1 ...11111111110 = -2 ...11111111101 = -3 This works rather nicely; if you have -1 in a register and you add one, the carry goes all the way to the left and eventually "falls off the end", and you end up with zero (as you should). To flip the sign of a number, you invert all the bits, and add one: ...00000001100 = 12 ...11111110011 = ～12 = -11 ...11111110100 = ～12 + 1 = -12 ## 2-adic numbersNow consider this infinitely long string of bits, where only half the bits are 1s: ...010101010101 = ?If we multiply it by three, we get ...010101010101 * 11 = ... so apparently the mystery number ...010101010101 = -⅓ ...101010101010 = ～(-⅓) ...101010101011 = ～(-⅓) + 1 = -(-⅓) = ⅓ Let's try multiplying 9 by our "⅓":
It actually works! int exactDiv3(int x) { return x * 0xaaaaaaab; } This works in decimal as well: The next time you need to divide a number by 13, just multiply by ...23076923076923076923077 instead. It's that simple! 91 * 23076923076923076923077 = 2100000000000000000000007... and so, ignoring the high-order digits: 91 * ...076923076923077 = ...000000000000007 = 7 Wikipedia has a nice article about
2-adic numbers BigInteger a = BigInteger.valueOf(3); BigInteger m = BigInteger.ONE.shiftLeft(64); out.println(a.modInverse(m).toString(16)); ## In the real worldSince this trick only works when there is no remainder, GCC will (as far as I know) only use it one situation. When subtracting two pointers to the same array, it needs to divide the raw pointer difference by the element size. This difference will always be an exact multiple of the element size (this is guaranteed by one of the "nasal demon You can force it to accept arbitrary integers by doing something like this (no, I'm not suggesting you use this anywhere):
There's one additional snag, though: If the divisor is an even
number, there is no direct multiplicative inverse. However, since
we're still assuming there is no remainder, it is safe the use a bit
shift to handle the 2 int test(int n) { return divide<20>(n); } ... can be compiled as (to see this, just run ;; essentially return (x>>2) * -858993459; sarl $2, %eax imull $-858993459, %eax, %eax ret ## MicrobenchmarkThis graph shows the runtime for each of the three division implementations: division by a variable using IDIV, division by a constant as optimized by GCC into a multiplication followed by fixups, and the Note how powers of 2 are most efficient (requiring a bitshift only), with odd numbers (multiplication but no shift) as a close second. ## Remainder testingAnother common operation is checking if the remainder is zero: if (x % 7 == 0) { ... This can be simplified to... if (x * inverse(7) <= floor(2**32/7)) { ... ... that is, checking that the result of the inverse multiplication can be multiplied by 7 without overflowing again. As far as I can tell, no compilers actually use this trick. ## CommentsIf your input has limited range, it's possible to compute some constant divisions using a small constant multiply (implemented by the compiler as shifts & adds) and a constant division by a power of 2. I.e. 5*n/16. This is sometimes faster than an exact multiply solution, but this probably depends on the architecture and function computed.
— Eric 2010-01-09 Footnotes: |