| … | |
… | |
| 358 | #define ECB_STRINGIFY_EXPR(expr) ((expr), ECB_STRINGIFY_ (expr)) |
358 | #define ECB_STRINGIFY_EXPR(expr) ((expr), ECB_STRINGIFY_ (expr)) |
| 359 | |
359 | |
| 360 | /* This marks larger functions that do not neccessarily need to be inlined */ |
360 | /* This marks larger functions that do not neccessarily need to be inlined */ |
| 361 | /* The idea is to possibly compile the header twice, */ |
361 | /* The idea is to possibly compile the header twice, */ |
| 362 | /* once exposing only the declarations, another time to define external functions */ |
362 | /* once exposing only the declarations, another time to define external functions */ |
| 363 | /* TODO: popssibly static would be best for these at the moment? */ |
363 | /* TODO: possibly static would be best for these at the moment? */ |
| 364 | #define ecb_function_ ecb_inline |
364 | #define ecb_function_ ecb_inline |
| 365 | |
365 | |
| 366 | #if ECB_GCC_VERSION(3,1) || ECB_CLANG_VERSION(2,8) |
366 | #if ECB_GCC_VERSION(3,1) || ECB_CLANG_VERSION(2,8) |
| 367 | #define ecb_attribute(attrlist) __attribute__ (attrlist) |
367 | #define ecb_attribute(attrlist) __attribute__ (attrlist) |
| 368 | #else |
368 | #else |
| … | |
… | |
| 1035 | /*****************************************************************************/ |
1035 | /*****************************************************************************/ |
| 1036 | /* 2d hilbert curves */ |
1036 | /* 2d hilbert curves */ |
| 1037 | |
1037 | |
| 1038 | /* algorithm from the book Hacker's Delight, modified to not */ |
1038 | /* algorithm from the book Hacker's Delight, modified to not */ |
| 1039 | /* run into undefined behaviour for n==16 */ |
1039 | /* run into undefined behaviour for n==16 */ |
| 1040 | static uint32_t |
1040 | static uint32_t ecb_hilbert2d_index_to_coord32 (int n, uint32_t s); |
| 1041 | ecb_hilbert2d_index_to_coord32 (int n, uint32_t s) |
1041 | static uint32_t ecb_hilbert2d_index_to_coord32 (int n, uint32_t s) |
| 1042 | { |
1042 | { |
| 1043 | uint32_t comp, swap, cs, t, sr; |
1043 | uint32_t comp, swap, cs, t, sr; |
| 1044 | |
1044 | |
| 1045 | /* pad s on the left (unused) bits with 01 (no change groups) */ |
1045 | /* pad s on the left (unused) bits with 01 (no change groups) */ |
| 1046 | s |= 0x55555555U << n << n; |
1046 | s |= 0x55555555U << n << n; |
| … | |
… | |
| 1080 | /* now s contains two 16-bit coordinates */ |
1080 | /* now s contains two 16-bit coordinates */ |
| 1081 | return s; |
1081 | return s; |
| 1082 | } |
1082 | } |
| 1083 | |
1083 | |
| 1084 | /* 64 bit, a straightforward extension to the 32 bit case */ |
1084 | /* 64 bit, a straightforward extension to the 32 bit case */ |
| 1085 | static uint64_t |
1085 | static uint64_t ecb_hilbert2d_index_to_coord64 (int n, uint64_t s); |
| 1086 | ecb_hilbert2d_index_to_coord64 (int n, uint64_t s) |
1086 | static uint64_t ecb_hilbert2d_index_to_coord64 (int n, uint64_t s) |
| 1087 | { |
1087 | { |
| 1088 | uint64_t comp, swap, cs, t, sr; |
1088 | uint64_t comp, swap, cs, t, sr; |
| 1089 | |
1089 | |
| 1090 | /* pad s on the left (unused) bits with 01 (no change groups) */ |
1090 | /* pad s on the left (unused) bits with 01 (no change groups) */ |
| 1091 | s |= 0x5555555555555555U << n << n; |
1091 | s |= 0x5555555555555555U << n << n; |
| … | |
… | |
| 1129 | } |
1129 | } |
| 1130 | |
1130 | |
| 1131 | /* algorithm from the book Hacker's Delight, but a similar algorithm*/ |
1131 | /* algorithm from the book Hacker's Delight, but a similar algorithm*/ |
| 1132 | /* is given in https://doi.org/10.1002/spe.4380160103 */ |
1132 | /* is given in https://doi.org/10.1002/spe.4380160103 */ |
| 1133 | /* this has been slightly improved over the original version */ |
1133 | /* this has been slightly improved over the original version */ |
| 1134 | ecb_function_ uint32_t |
1134 | ecb_function_ uint32_t ecb_hilbert2d_coord_to_index32 (int n, uint32_t xy); |
| 1135 | ecb_hilbert2d_coord_to_index32 (int n, uint32_t xy) |
1135 | ecb_function_ uint32_t ecb_hilbert2d_coord_to_index32 (int n, uint32_t xy) |
| 1136 | { |
1136 | { |
| 1137 | uint32_t row; |
1137 | uint32_t row; |
| 1138 | uint32_t state = 0; |
1138 | uint32_t state = 0; |
| 1139 | uint32_t s = 0; |
1139 | uint32_t s = 0; |
| 1140 | |
1140 | |
| … | |
… | |
| 1154 | |
1154 | |
| 1155 | return s; |
1155 | return s; |
| 1156 | } |
1156 | } |
| 1157 | |
1157 | |
| 1158 | /* 64 bit, essentially the same as 32 bit */ |
1158 | /* 64 bit, essentially the same as 32 bit */ |
| 1159 | ecb_function_ uint64_t |
1159 | ecb_function_ uint64_t ecb_hilbert2d_coord_to_index64 (int n, uint64_t xy); |
| 1160 | ecb_hilbert2d_coord_to_index64 (int n, uint64_t xy) |
1160 | ecb_function_ uint64_t ecb_hilbert2d_coord_to_index64 (int n, uint64_t xy) |
| 1161 | { |
1161 | { |
| 1162 | uint32_t row; |
1162 | uint32_t row; |
| 1163 | uint32_t state = 0; |
1163 | uint32_t state = 0; |
| 1164 | uint64_t s = 0; |
1164 | uint64_t s = 0; |
| 1165 | |
1165 | |
