{"id":188,"date":"2018-12-03T20:11:54","date_gmt":"2018-12-03T20:11:54","guid":{"rendered":"http:\/\/threadlocalmutex.com\/?p=188"},"modified":"2018-12-03T20:11:54","modified_gmt":"2018-12-03T20:11:54","slug":"2d-hilbert-curves-in-o1","status":"publish","type":"post","link":"http:\/\/threadlocalmutex.com\/?p=188","title":{"rendered":"2D Hilbert curves in O(1)"},"content":{"rendered":"<p>...sort of.<\/p>\n<p>The core of computing 2D coordinates from a Hilbert index in logarithmic time is a XOR prefix sum. As it so happens, the upper bits of carry-less multiplication with -1 are equivalent to a XOR prefix sum. On an x86 machine with CLMUL and PEXT support, this yields the following \"constant time\" algorithm for mapping a 32bit Hilbert index to 16bit X and Y:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\nvoid hilbertIndexToXY_constantTime(uint32_t i, uint32_t&amp; x, uint32_t&amp; y)\r\n{\r\n\tuint32_t i0 = _pext_u32(i, 0x55555555);\r\n\tuint32_t i1 = _pext_u32(i, 0xAAAAAAAA);\r\n\r\n\tuint32_t A = i0 &amp; i1;\r\n\tuint32_t B = i0 ^ i1 ^ 0xFFFF;\r\n\r\n\tuint32_t C = uint32_t(_mm_extract_epi16(_mm_clmulepi64_si128(_mm_set_epi64x(0, 0xFFFF), _mm_cvtsi32_si128(A), 0b00), 1));\r\n\tuint32_t D = uint32_t(_mm_extract_epi16(_mm_clmulepi64_si128(_mm_set_epi64x(0, 0xFFFF), _mm_cvtsi32_si128(B), 0b00), 1));\r\n\r\n\tuint32_t a = C ^ (i0 &amp; D);\r\n\r\n\tx = (a ^ i1);\r\n\ty = (a ^ i0 ^ i1);\r\n}\r\n<\/pre>\n<p>Of course this isn't really a constant time solution since the CLMUL intrinsic is limited to 64bit operands, and can't be extended to operate on <span class='MathJax_Preview'><img src='http:\/\/threadlocalmutex.com\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> bits in <span class='MathJax_Preview'><img src='http:\/\/threadlocalmutex.com\/wp-content\/plugins\/latex\/cache\/tex_5e079a28737d5dd019a3b8f6133ee55e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> time in any reasonable machine model. In practice, this solution also tends to be a hair slower than the logarithmic time solution since both transferring data into\/out of SSE registers and the CLMUL intrinsic itself are rather high latency operations.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>...sort of. The core of computing 2D coordinates from a Hilbert index in logarithmic time is a XOR prefix sum. As it so happens, the upper bits of carry-less multiplication with -1 are equivalent to a XOR prefix sum. On an x86 machine with CLMUL and PEXT support, this yields the following \"constant time\" algorithm <a class=\"read-more\" href=\"http:\/\/threadlocalmutex.com\/?p=188\">[&hellip;]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts\/188"}],"collection":[{"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=188"}],"version-history":[{"count":3,"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts\/188\/revisions"}],"predecessor-version":[{"id":191,"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts\/188\/revisions\/191"}],"wp:attachment":[{"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=188"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=188"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=188"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}