- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我希望以快速高效的方式用 C 语言编写 Morton Z 顺序编码和解码的两个函数,即。
uint64_t morton_encode(uint32_t xindex, uint32_t yindex, uint32_t zindex);
void morton_decode(uint64_t morton_number, uint32_t *xindex, uint32_t *yindex, uint32_t *zindex);
我之前已经关注过这些问题
how to compute a 3d morton number interleave the bits of 3 ints
我目前基于SO和开源代码的解决方案是
uint64_t spread(uint64_t w) {
w &= 0x00000000001fffff;
w = (w | w << 32) & 0x001f00000000ffff;
w = (w | w << 16) & 0x001f0000ff0000ff;
w = (w | w << 8) & 0x010f00f00f00f00f;
w = (w | w << 4) & 0x10c30c30c30c30c3;
w = (w | w << 2) & 0x1249249249249249;
return w;
}
uint64_t morton_encode(uint32_t x, uint32_t y, uint32_t z) {
return ((spread((uint64_t)x)) | (spread((uint64_t)y) << 1) | (spread((uint64_t)z) << 2));
}
///////////////// For Decoding //////////////////////
uint32_t compact(uint64_t w) {
w &= 0x1249249249249249;
w = (w ^ (w >> 2)) & 0x30c30c30c30c30c3;
w = (w ^ (w >> 4)) & 0xf00f00f00f00f00f;
w = (w ^ (w >> 8)) & 0x00ff0000ff0000ff;
w = (w ^ (w >> 16)) & 0x00ff00000000ffff;
w = (w ^ (w >> 32)) & 0x00000000001fffff;
return (uint32_t)w;
}
void morton_decode(uint64_t morton_number, uint32_t *xindex, uint32_t *yindex, uint32_t *zindex){
*xindex = compact(code);
*yindex = compact(code >> 1);
*zindex = compact(code >> 2);
}
我最近遇到了这个问题(在尝试使用 2D morton 代码时):2d morton code encode decode 64bits
#include <immintrin.h>
#include <stdint.h>
// on GCC, compile with option -mbmi2, requires Haswell or better.
uint64_t xy_to_morton (uint32_t x, uint32_t y)
{
return _pdep_u32(x, 0x55555555) | _pdep_u32(y,0xaaaaaaaa);
}
uint64_t morton_to_xy (uint64_t m, uint32_t *x, uint32_t *y)
{
*x = _pext_u64(m, 0x5555555555555555);
*y = _pext_u64(m, 0xaaaaaaaaaaaaaaaa);
}
据我了解,这不是一个可移植的解决方案,但由于我(将)运行我的代码的每个系统都有 Haswell CPU(即使在 HPC 集群上)。我的问题:
编辑:对于第一季度,我非常接近解决方案,但仍然无法弄清楚
0x55555555 -> 0000 0000 0101 0101 0101 0101 0101 0101 0101 0101
0xaaaaaaaa -> 0000 0000 1010 1010 1010 1010 1010 1010 1010 1010
很明显,掩码是 x 和 y 位交替的。所以对于 3d 我需要一个像这样的面具
0000 0000 01 001 001 001 001 001 001 001 001 001 001 (for x)
0000 0000 01 010 010 010 010 010 010 010 010 010 010 (for y)
0000 0000 01 100 100 100 100 100 100 100 100 100 100 (for z)
^
对于 64 位 morton 代码,我对 ^ 标记之前的位有点困惑,只有 x、y 和 z 的前 21 位(32 位整数)应该重要。
最佳答案
经过一番摆弄后,我找到了一个解决方案,我认为应该在这里分享作为答案。
// on GCC, compile with option -mbmi2, requires Haswell or better.
#include <stdio.h>
#include <limits.h>
#include <immintrin.h>
#include <inttypes.h>
#include <sys/time.h>
#define maask 0x1249249249249249
/* Morton Encoding Mehtod 1 */
uint64_t Z_encode1 (uint32_t x, uint32_t y, uint32_t z)
{
return _pdep_u32(x, maask) | \
_pdep_u32(y,(maask << 1)) | \
_pdep_u32(z,(maask << 2));
}
/* Morton Decoding Method 1 */
uint64_t Z_decode1 (uint64_t m, uint32_t *x, uint32_t *y, uint32_t *z)
{
*x = _pext_u64(m, maask);
*y = _pext_u64(m, (maask << 1));
*z = _pext_u64(m, (maask << 2));
}
// method 2 functions
uint64_t spread(uint64_t w) {
w &= 0x00000000001fffff;
w = (w | w << 32) & 0x001f00000000ffff;
w = (w | w << 16) & 0x001f0000ff0000ff;
w = (w | w << 8) & 0x010f00f00f00f00f;
w = (w | w << 4) & 0x10c30c30c30c30c3;
w = (w | w << 2) & 0x1249249249249249;
return w;
}
uint32_t compact(uint64_t w) {
w &= 0x1249249249249249;
w = (w ^ (w >> 2)) & 0x30c30c30c30c30c3;
w = (w ^ (w >> 4)) & 0xf00f00f00f00f00f;
w = (w ^ (w >> 8)) & 0x00ff0000ff0000ff;
w = (w ^ (w >> 16)) & 0x00ff00000000ffff;
w = (w ^ (w >> 32)) & 0x00000000001fffff;
return (uint32_t)w;
}
uint64_t Z_encode2(uint32_t x, uint32_t y, uint32_t z) {
return ((spread((uint64_t)x)) | (spread((uint64_t)y) << 1) | (spread((uint64_t)z) << 2));
}
void Z_decode2(uint64_t Z_code, uint32_t *xindex, uint32_t *yindex, uint32_t *zindex){
*xindex = compact(Z_code);
*yindex = compact(Z_code >> 1);
*zindex = compact(Z_code >> 2);
}
int main()
{
const int size = 1024;
struct timeval start, stop;
double time_encode1 = 0.0, time_encode2 = 0.0;
double time_decode1 = 0.0, time_decode2 = 0.0;
uint64_t Zindex = 0;
uint32_t xindex=0,yindex=0,zindex=0;
/* method 1 ENCODING benchmark */
gettimeofday(&start, NULL);
for (uint32_t i = 0; i < size; i++){
for (uint32_t j = 0; j < size; j++) {
for (uint32_t k = 0; k < size; k++) {
Zindex = Z_encode1(i, j, k);
}
}
}
gettimeofday(&stop, NULL);
time_encode1 = (double)(stop.tv_usec - start.tv_usec) / 1000000 + (double)(stop.tv_sec - start.tv_sec);
/* method 2 ENCODING benchmark */
gettimeofday(&start, NULL);
for (uint32_t i = 0; i < size; i++){
for (uint32_t j = 0; j < size; j++) {
for (uint32_t k = 0; k < size; k++) {
Zindex = Z_encode2(i, j, k);
}
}
}
gettimeofday(&stop, NULL);
time_encode2 = (double)(stop.tv_usec - start.tv_usec) / 1000000 + (double)(stop.tv_sec - start.tv_sec);
//////////////////////// DECODING ////////////////
/* method 1 DECODING benchmark */
gettimeofday(&start, NULL);
for (uint64_t i = 0; i < size; i++)
Z_decode1(i, &xindex, &yindex, &zindex);
gettimeofday(&stop, NULL);
time_decode1 = (double)(stop.tv_usec - start.tv_usec) / 1000000 + (double)(stop.tv_sec - start.tv_sec);
/* method 1 DECODING benchmark */
gettimeofday(&start, NULL);
for (uint64_t i = 0; i < size; i++)
Z_decode2(i, &xindex, &yindex, &zindex);
gettimeofday(&stop, NULL);
time_decode2 = (double)(stop.tv_usec - start.tv_usec) / 1000000 + (double)(stop.tv_sec - start.tv_sec);
printf("Method1 -> Encoding: %f Decoding: %f\n", time_encode1, time_decode1);
printf("Method2 -> Encoding: %f Decoding: %f\n", time_encode2, time_decode2);
return 0;
}
这是结果
size = 512 ( 512x512x512 = 134217728 numbers)
======================================================
Method 1 -> Encoding: 0.600302sec Decoding: 0.000003sec
Method 2 -> Encoding: 2.778170sec Decoding: 0.000011sec
size = 1024 ( 1024x1024x1024 = 1073741824 numbers)
======================================================
Method 1 -> Encoding: 4.623594sec Decoding: 0.000006sec
Method 2 -> Encoding: 22.339238sec Decoding: 0.000022sec
size = 2048 ( 2048*2048*2048 = 8589934592 numbers)
======================================================
Method 1 -> Encoding: 36.981743sec Decoding: 0.000011sec
Method 2 -> Encoding: 178.164773sec Decoding: 0.000045sec
结论:编码比解码成本高,使用BMI指令集来优化性能。
PS。 - 不可移植,因为需要 Haswell cpu 或更高版本。关于c - 使用位交织的 3D Morton 编码,传统指令集与 BMI2 指令集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50210379/
我在网上搜索但没有找到任何合适的文章解释如何使用 javascript 使用 WCF 服务,尤其是 WebScriptEndpoint。 任何人都可以对此给出任何指导吗? 谢谢 最佳答案 这是一篇关于
我正在编写一个将运行 Linux 命令的 C 程序,例如: cat/etc/passwd | grep 列表 |剪切-c 1-5 我没有任何结果 *这里 parent 等待第一个 child (chi
所以我正在尝试处理文件上传,然后将该文件作为二进制文件存储到数据库中。在我存储它之后,我尝试在给定的 URL 上提供文件。我似乎找不到适合这里的方法。我需要使用数据库,因为我使用 Google 应用引
我正在尝试制作一个宏,将下面的公式添加到单元格中,然后将其拖到整个列中并在 H 列中复制相同的公式 我想在 F 和 H 列中输入公式的数据 Range("F1").formula = "=IF(ISE
问题类似于this one ,但我想使用 OperatorPrecedenceParser 解析带有函数应用程序的表达式在 FParsec . 这是我的 AST: type Expression =
我想通过使用 sequelize 和 node.js 将这个查询更改为代码取决于在哪里 select COUNT(gender) as genderCount from customers where
我正在使用GNU bash,版本5.0.3(1)-发行版(x86_64-pc-linux-gnu),我想知道为什么简单的赋值语句会出现语法错误: #/bin/bash var1=/tmp
这里,为什么我的代码在 IE 中不起作用。我的代码适用于所有浏览器。没有问题。但是当我在 IE 上运行我的项目时,它发现错误。 而且我的 jquery 类和 insertadjacentHTMl 也不
我正在尝试更改标签的innerHTML。我无权访问该表单,因此无法编辑 HTML。标签具有的唯一标识符是“for”属性。 这是输入和标签的结构:
我有一个页面,我可以在其中返回用户帖子,可以使用一些 jquery 代码对这些帖子进行即时评论,在发布新评论后,我在帖子下插入新评论以及删除 按钮。问题是 Delete 按钮在新插入的元素上不起作用,
我有一个大约有 20 列的“管道分隔”文件。我只想使用 sha1sum 散列第一列,它是一个数字,如帐号,并按原样返回其余列。 使用 awk 或 sed 执行此操作的最佳方法是什么? Accounti
我需要将以下内容插入到我的表中...我的用户表有五列 id、用户名、密码、名称、条目。 (我还没有提交任何东西到条目中,我稍后会使用 php 来做)但由于某种原因我不断收到这个错误:#1054 - U
所以我试图有一个输入字段,我可以在其中输入任何字符,但然后将输入的值小写,删除任何非字母数字字符,留下“。”而不是空格。 例如,如果我输入: 地球的 70% 是水,-!*#$^^ & 30% 土地 输
我正在尝试做一些我认为非常简单的事情,但出于某种原因我没有得到想要的结果?我是 javascript 的新手,但对 java 有经验,所以我相信我没有使用某种正确的规则。 这是一个获取输入值、检查选择
我想使用 angularjs 从 mysql 数据库加载数据。 这就是应用程序的工作原理;用户登录,他们的用户名存储在 cookie 中。该用户名显示在主页上 我想获取这个值并通过 angularjs
我正在使用 autoLayout,我想在 UITableViewCell 上放置一个 UIlabel,它应该始终位于单元格的右侧和右侧的中心。 这就是我想要实现的目标 所以在这里你可以看到我正在谈论的
我需要与 MySql 等效的 elasticsearch 查询。我的 sql 查询: SELECT DISTINCT t.product_id AS id FROM tbl_sup_price t
我正在实现代码以使用 JSON。 func setup() { if let flickrURL = NSURL(string: "https://api.flickr.com/
我尝试使用for循环声明变量,然后测试cols和rols是否相同。如果是,它将运行递归函数。但是,我在 javascript 中执行 do 时遇到问题。有人可以帮忙吗? 现在,在比较 col.1 和
我举了一个我正在处理的问题的简短示例。 HTML代码: 1 2 3 CSS 代码: .BB a:hover{ color: #000; } .BB > li:after {
我是一名优秀的程序员,十分优秀!