Skip to content

Instantly share code, notes, and snippets.

@stefalie
Forked from JarkkoPFC/morton.h
Created September 30, 2021 18:30
Show Gist options
  • Save stefalie/4829d2e7bc73effbec43080879dfc0e2 to your computer and use it in GitHub Desktop.
Save stefalie/4829d2e7bc73effbec43080879dfc0e2 to your computer and use it in GitHub Desktop.
Faster 16/32bit 2D Morton Code encode/decode functions
uint16_t encode16_morton2(uint8_t x_, uint8_t y_)
{
uint32_t res=x_|(uint32_t(y_)<<16);
res=(res|(res<<4))&0x0f0f0f0f;
res=(res|(res<<2))&0x33333333;
res=(res|(res<<1))&0x55555555;
return uint16_t(res|(res>>15));
}
//----
uint32_t encode32_morton2(uint16_t x_, uint16_t y_)
{
uint64_t res=x_|(uint64_t(y_)<<32);
res=(res|(res<<8))&0x00ff00ff00ff00ff;
res=(res|(res<<4))&0x0f0f0f0f0f0f0f0f;
res=(res|(res<<2))&0x3333333333333333;
res=(res|(res<<1))&0x5555555555555555;
return uint32_t(res|(res>>31));
}
//----
void decode16_morton2(uint8_t &x_, uint8_t &y_, uint16_t mc_)
{
uint32_t res=(mc_|(uint32_t(mc_)<<15))&0x55555555;
res=(res|(res>>1))&0x33333333;
res=(res|(res>>2))&0x0f0f0f0f;
res=res|(res>>4);
x_=uint8_t(res);
y_=uint8_t(res>>16);
}
//----
void decode32_morton2(uint16_t &x_, uint16_t &y_, uint32_t mc_)
{
uint64_t res=(mc_|(uint64_t(mc_)<<31))&0x5555555555555555;
res=(res|(res>>1))&0x3333333333333333;
res=(res|(res>>2))&0x0f0f0f0f0f0f0f0f;
res=(res|(res>>4))&0x00ff00ff00ff00ff;
res=res|(res>>8);
x_=uint16_t(res);
y_=uint16_t(res>>32);
}
@stefalie
Copy link
Author

Even better:
return _pdep_u32(x, 0x55555555) | _pdep_u32(y, 0xaaaaaaaa);

See: https://twitter.com/JarkkoPFC/status/1443462656669663235

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment