{"id":110,"date":"2010-06-27T21:17:48","date_gmt":"2010-06-27T20:17:48","guid":{"rendered":"http:\/\/blog.blockos.org\/?p=110"},"modified":"2014-09-21T17:11:18","modified_gmt":"2014-09-21T16:11:18","slug":"gcd-and-destroy","status":"publish","type":"post","link":"https:\/\/blog.blockos.org\/?p=110","title":{"rendered":"GCD and destroy"},"content":{"rendered":"

Some weeks ago I decided to fix once and for all this bloody hdrr<\/a>. As it requires the framebuffer average log luminance, I decided to compute it be generating a pixel accurate mipmap. So for a 320×240 framebuffer we will have the following downsampling steps : (4,4) (4,4) (5,5) (4,3).
\nDon’t ask me why but instead of working on a way to decompose a number, I decided that I needed to find the greatest common divisor of width and height! 10 seconds later thanks to the almighty web search engine I started reading the Wikipedia entry about Binary GCD<\/a>. And after some interweb jumps I ended on this article<\/a>. The Stein\u2019s algorithm looked cool.
\nIf you look at Sputsoft code, you’ll realize that the shift_to_uneven<\/strong> function removes trailing zeros. This can be optimized using GCC builtins. The builtins we need is __builtin_ctz<\/strong> that counts trailing zeros.
\nWe can then replace shift_to_uneven<\/strong> by: <\/p>\n

u >>= __builtin_ctz(u);<\/pre>\n
And the GCD function now looks like this:<\/p>\n
uint32_t gcd( uint32_t c, uint32_t d )
\n{
\n\tuint32_t u,v,s;<\/p>\n
\tu = __builtin_ctz(c);
\n\tv = __builtin_ctz(d);<\/p>\n
\ts = (u < v) ? u : v;\n    \t\n\tu = c >> u;
\n\tv = d >> v;<\/p>\n
\twhile(u != v)
\n\t{
\n\t\tif(u > v)
\n\t\t{
\n\t\t\tu -= v;
\n\t\t\tu >>= __builtin_ctz(u);
\n\t\t}
\n\t\telse
\n\t\t{
\n\t\t\tv -= u;
\n\t\t\tv >>= __builtin_ctz(v);
\n\t\t}
\n\t}
\n\treturn u << s;\n}[\/sourcecode]\n\nTadam!\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Some weeks ago I decided to fix once and for all this bloody hdrr. As it requires the framebuffer average log luminance, I decided to compute it be generating a pixel accurate mipmap. So for a 320×240 framebuffer we will have the following downsampling steps : (4,4) (4,4) (5,5) (4,3).\u2026 Continue reading<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[3],"tags":[27],"_links":{"self":[{"href":"https:\/\/blog.blockos.org\/index.php?rest_route=\/wp\/v2\/posts\/110"}],"collection":[{"href":"https:\/\/blog.blockos.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.blockos.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.blockos.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.blockos.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=110"}],"version-history":[{"count":28,"href":"https:\/\/blog.blockos.org\/index.php?rest_route=\/wp\/v2\/posts\/110\/revisions"}],"predecessor-version":[{"id":980,"href":"https:\/\/blog.blockos.org\/index.php?rest_route=\/wp\/v2\/posts\/110\/revisions\/980"}],"wp:attachment":[{"href":"https:\/\/blog.blockos.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=110"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.blockos.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=110"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.blockos.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=110"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}