diff options
Diffstat (limited to 'include/stc/cspan.h')
| -rw-r--r-- | include/stc/cspan.h | 262 |
1 files changed, 142 insertions, 120 deletions
diff --git a/include/stc/cspan.h b/include/stc/cspan.h index ac3e9206..0875ed92 100644 --- a/include/stc/cspan.h +++ b/include/stc/cspan.h @@ -24,9 +24,9 @@ /* #include <stdio.h> #include <stc/cspan.h> -#include <stc/algo/filter.h> +#include <stc/algorithm.h> using_cspan(Span2f, float, 2); -using_cspan(Intspan, int, 1); +using_cspan(Intspan, int); int demo1() { float raw[4*5]; @@ -60,209 +60,231 @@ int demo2() { #ifndef STC_CSPAN_H_INCLUDED #define STC_CSPAN_H_INCLUDED +#include "priv/linkage.h" #include "ccommon.h" #define using_cspan(...) c_MACRO_OVERLOAD(using_cspan, __VA_ARGS__) #define using_cspan_2(Self, T) \ - using_cspan_3(Self, T, 1) + using_cspan_3(Self, T, 1); \ + STC_INLINE Self Self##_from_n(Self##_raw* raw, const intptr_t n) { \ + return (Self){.data=raw, .shape={(int32_t)n}, .stride={.d={1}}}; \ + } \ + struct stc_nostruct #define using_cspan_3(Self, T, RANK) \ typedef T Self##_value; typedef T Self##_raw; \ typedef struct { \ Self##_value *data; \ int32_t shape[RANK]; \ - cspan_idx##RANK stride; \ + cspan_tuple##RANK stride; \ } Self; \ \ typedef struct { Self##_value *ref; int32_t pos[RANK]; const Self *_s; } Self##_iter; \ \ - STC_INLINE Self Self##_from_n(Self##_raw* raw, const intptr_t n) { \ - return (Self){.data=raw, .shape={(int32_t)n}}; \ - } \ - STC_INLINE Self Self##_slice_(Self##_value* v, const int32_t shape[], const int32_t stri[], \ - const int rank, const int32_t a[][2]) { \ - Self s = {.data=v}; int outrank; \ - s.data += _cspan_slice(s.shape, s.stride.d, &outrank, shape, stri, rank, a); \ - c_ASSERT(outrank == RANK); \ + STC_INLINE Self Self##_slice_(Self##_value* d, const int32_t shape[], const intptr_t stri[], \ + const int rank, const int32_t a[][3]) { \ + Self s; int outrank; \ + s.data = d + _cspan_slice(s.shape, s.stride.d, &outrank, shape, stri, rank, a); \ + c_assert(outrank == RANK); \ return s; \ } \ STC_INLINE Self##_iter Self##_begin(const Self* self) { \ - Self##_iter it = {.ref=self->data, .pos={0}, ._s=self}; \ + Self##_iter it = {.ref=self->data, ._s=self}; \ return it; \ } \ STC_INLINE Self##_iter Self##_end(const Self* self) { \ - Self##_iter it = {.ref=NULL}; \ + Self##_iter it = {0}; \ return it; \ } \ STC_INLINE void Self##_next(Self##_iter* it) { \ - it->ref += _cspan_next##RANK(RANK, it->pos, it->_s->shape, it->_s->stride.d); \ - if (it->pos[0] == it->_s->shape[0]) it->ref = NULL; \ + int done; \ + it->ref += _cspan_next##RANK(it->pos, it->_s->shape, it->_s->stride.d, RANK, &done); \ + if (done) it->ref = NULL; \ } \ struct stc_nostruct -#define using_cspan2(Self, T) using_cspan_3(Self, T, 1); using_cspan_3(Self##2, T, 2) +#define using_cspan2(Self, T) using_cspan_2(Self, T); using_cspan_3(Self##2, T, 2) #define using_cspan3(Self, T) using_cspan2(Self, T); using_cspan_3(Self##3, T, 3) #define using_cspan4(Self, T) using_cspan3(Self, T); using_cspan_3(Self##4, T, 4) -typedef struct { int32_t d[1]; } cspan_idx1; -typedef struct { int32_t d[2]; } cspan_idx2; -typedef struct { int32_t d[3]; } cspan_idx3; -typedef struct { int32_t d[4]; } cspan_idx4; -typedef struct { int32_t d[5]; } cspan_idx5; -typedef struct { int32_t d[6]; } cspan_idx6; -#define c_END -1 -#define c_ALL 0,-1 +#define using_cspan_tuple(N) typedef struct { intptr_t d[N]; } cspan_tuple##N +using_cspan_tuple(1); using_cspan_tuple(2); +using_cspan_tuple(3); using_cspan_tuple(4); +using_cspan_tuple(5); using_cspan_tuple(6); +using_cspan_tuple(7); using_cspan_tuple(8); -#define cspan_md(array, ...) \ - {.data=array, .shape={__VA_ARGS__}, .stride={.d={__VA_ARGS__}}} +#define c_END -1 +#define c_ALL 0,c_END +typedef enum {c_ROWMAJOR, c_COLMAJOR} cspan_layout; -/* For static initialization, use cspan_make(). c_make() for non-static only. */ -#define cspan_make(SpanType, ...) \ - {.data=(SpanType##_value[])__VA_ARGS__, .shape={sizeof((SpanType##_value[])__VA_ARGS__)/sizeof(SpanType##_value)}} +/* Use cspan_init() for static initialization only. c_init() for non-static init. */ +#define cspan_init(SpanType, ...) \ + {.data=(SpanType##_value[])__VA_ARGS__, .shape={sizeof((SpanType##_value[])__VA_ARGS__)/sizeof(SpanType##_value)}, .stride={.d={1}}} -#define cspan_slice(OutSpan, parent, ...) \ - OutSpan##_slice_((parent)->data, (parent)->shape, (parent)->stride.d, cspan_rank(parent) + \ - c_static_assert(cspan_rank(parent) == sizeof((int32_t[][2]){__VA_ARGS__})/sizeof(int32_t[2])), \ - (const int32_t[][2]){__VA_ARGS__}) - -/* create a cspan from a cvec, cstack, cdeq, cqueue, or cpque (heap) */ +/* create a cspan from a cvec, cstack, or cpque (heap) */ #define cspan_from(container) \ - {.data=(container)->data, .shape={(int32_t)(container)->_len}} + {.data=(container)->data, .shape={(int32_t)(container)->_len}, .stride={.d={1}}} + +#define cspan_from_n(ptr, n) \ + {.data=(ptr), .shape={n}, .stride={.d={1}}} #define cspan_from_array(array) \ - {.data=(array) + c_static_assert(sizeof(array) != sizeof(void*)), .shape={c_arraylen(array)}} + cspan_from_n(array, c_arraylen(array)) #define cspan_size(self) _cspan_size((self)->shape, cspan_rank(self)) #define cspan_rank(self) c_arraylen((self)->shape) - -#define cspan_index(self, ...) c_PASTE(cspan_idx_, c_NUMARGS(__VA_ARGS__))(self, __VA_ARGS__) -#define cspan_idx_1 cspan_idx_4 -#define cspan_idx_2 cspan_idx_4 -#define cspan_idx_3 cspan_idx_4 -#define cspan_idx_4(self, ...) \ - c_PASTE(_cspan_idx, c_NUMARGS(__VA_ARGS__))((self)->shape, (self)->stride, __VA_ARGS__) // small/fast -#define cspan_idx_5(self, ...) \ - (_cspan_idxN(c_NUMARGS(__VA_ARGS__), (self)->shape, (self)->stride.d, (int32_t[]){__VA_ARGS__}) + \ - c_static_assert(cspan_rank(self) == c_NUMARGS(__VA_ARGS__))) // general -#define cspan_idx_6 cspan_idx_5 - +#define cspan_is_colmajor(self) ((self)->stride.d[0] < (self)->stride.d[cspan_rank(self) - 1]) +#define cspan_is_rowmajor(self) (!cspan_is_colmajor(self)) +#define cspan_get_layout(self) (cspan_is_colmajor(self) ? c_COLMAJOR : c_ROWMAJOR) #define cspan_at(self, ...) ((self)->data + cspan_index(self, __VA_ARGS__)) #define cspan_front(self) ((self)->data) #define cspan_back(self) ((self)->data + cspan_size(self) - 1) +#define cspan_index(self, ...) \ + (_cspan_index(c_NUMARGS(__VA_ARGS__), (self)->shape, (self)->stride.d, (const int32_t[]){__VA_ARGS__}) + \ + c_static_assert(cspan_rank(self) == c_NUMARGS(__VA_ARGS__))) // general -// cspan_subspanN. (N<4) Optimized, same as e.g. cspan_slice(Span3, &ms3, {off,off+count}, {c_ALL}, {c_ALL}); +// cspan_subspanX: (X <= 3) optimized. Similar to cspan_slice(Span3, &ms3, {off,off+count}, {c_ALL}, {c_ALL}); #define cspan_subspan(self, offset, count) \ - {.data=cspan_at(self, offset), .shape={count}} + {.data=cspan_at(self, offset), .shape={count}, .stride=(self)->stride} #define cspan_subspan2(self, offset, count) \ - {.data=cspan_at(self, offset, 0), .shape={count, (self)->shape[1]}, .stride={(self)->stride}} + {.data=cspan_at(self, offset, 0), .shape={count, (self)->shape[1]}, .stride=(self)->stride} #define cspan_subspan3(self, offset, count) \ - {.data=cspan_at(self, offset, 0, 0), .shape={count, (self)->shape[1], (self)->shape[2]}, .stride={(self)->stride}} + {.data=cspan_at(self, offset, 0, 0), .shape={count, (self)->shape[1], (self)->shape[2]}, .stride=(self)->stride} -// cspan_submdN: reduce rank (N<5) Optimized, same as e.g. cspan_slice(Span2, &ms4, {x}, {y}, {c_ALL}, {c_ALL}); -#define cspan_submd4(...) c_MACRO_OVERLOAD(cspan_submd4, __VA_ARGS__) -#define cspan_submd3(...) c_MACRO_OVERLOAD(cspan_submd3, __VA_ARGS__) +// cspan_submd(): Reduce rank (N <= 4) Optimized, same as e.g. cspan_slice(Span2, &ms4, {x}, {y}, {c_ALL}, {c_ALL}); #define cspan_submd2(self, x) \ - {.data=cspan_at(self, x, 0), .shape={(self)->shape[1]}} + {.data=cspan_at(self, x, 0), .shape={(self)->shape[1]}, .stride=(cspan_tuple1){.d={(self)->stride.d[1]}}} +#define cspan_submd3(...) c_MACRO_OVERLOAD(cspan_submd3, __VA_ARGS__) #define cspan_submd3_2(self, x) \ {.data=cspan_at(self, x, 0, 0), .shape={(self)->shape[1], (self)->shape[2]}, \ - .stride={.d={0, (self)->stride.d[2]}}} + .stride=(cspan_tuple2){.d={(self)->stride.d[1], (self)->stride.d[2]}}} #define cspan_submd3_3(self, x, y) \ - {.data=cspan_at(self, x, y, 0), .shape={(self)->shape[2]}} + {.data=cspan_at(self, x, y, 0), .shape={(self)->shape[2]}, .stride=(cspan_tuple1){.d={(self)->stride.d[2]}}} +#define cspan_submd4(...) c_MACRO_OVERLOAD(cspan_submd4, __VA_ARGS__) #define cspan_submd4_2(self, x) \ {.data=cspan_at(self, x, 0, 0, 0), .shape={(self)->shape[1], (self)->shape[2], (self)->shape[3]}, \ - .stride={.d={0, (self)->stride.d[2], (self)->stride.d[3]}}} + .stride=(cspan_tuple3){.d={(self)->stride.d[1], (self)->stride.d[2], (self)->stride.d[3]}}} #define cspan_submd4_3(self, x, y) \ - {.data=cspan_at(self, x, y, 0, 0), .shape={(self)->shape[2], (self)->shape[3]}, .stride={.d={0, (self)->stride.d[3]}}} + {.data=cspan_at(self, x, y, 0, 0), .shape={(self)->shape[2], (self)->shape[3]}, \ + .stride=(cspan_tuple2){.d={(self)->stride.d[2], (self)->stride.d[3]}}} #define cspan_submd4_4(self, x, y, z) \ - {.data=cspan_at(self, x, y, z, 0), .shape={(self)->shape[3]}} + {.data=cspan_at(self, x, y, z, 0), .shape={(self)->shape[3]}, .stride=(cspan_tuple1){.d={(self)->stride.d[3]}}} + +#define cspan_md(array, ...) cspan_md_layout(c_ROWMAJOR, array, __VA_ARGS__) +#define cspan_md_layout(layout, array, ...) \ + {.data=array, .shape={__VA_ARGS__}, \ + .stride=*(c_PASTE(cspan_tuple,c_NUMARGS(__VA_ARGS__))*)_cspan_shape2stride(layout, ((intptr_t[]){__VA_ARGS__}), c_NUMARGS(__VA_ARGS__))} -// private definitions: +#define cspan_transpose(self) \ + _cspan_transpose((self)->shape, (self)->stride.d, cspan_rank(self)) + +// General slicing function; +#define cspan_slice(OutSpan, parent, ...) \ + OutSpan##_slice_((parent)->data, (parent)->shape, (parent)->stride.d, cspan_rank(parent) + \ + c_static_assert(cspan_rank(parent) == sizeof((int32_t[][3]){__VA_ARGS__})/sizeof(int32_t[3])), \ + (const int32_t[][3]){__VA_ARGS__}) + +/* ------------------- PRIVAT DEFINITIONS ------------------- */ STC_INLINE intptr_t _cspan_size(const int32_t shape[], int rank) { intptr_t sz = shape[0]; - while (rank-- > 1) sz *= shape[rank]; + while (--rank) sz *= shape[rank]; return sz; } -STC_INLINE intptr_t _cspan_idx1(const int32_t shape[1], const cspan_idx1 stri, int32_t x) - { c_ASSERT(c_LTu(x, shape[0])); return x; } - -STC_INLINE intptr_t _cspan_idx2(const int32_t shape[2], const cspan_idx2 stri, int32_t x, int32_t y) - { c_ASSERT(c_LTu(x, shape[0]) && c_LTu(y, shape[1])); return (intptr_t)stri.d[1]*x + y; } - -STC_INLINE intptr_t _cspan_idx3(const int32_t shape[3], const cspan_idx3 stri, int32_t x, int32_t y, int32_t z) { - c_ASSERT(c_LTu(x, shape[0]) && c_LTu(y, shape[1]) && c_LTu(z, shape[2])); - return (intptr_t)stri.d[2]*(stri.d[1]*x + y) + z; +STC_INLINE void _cspan_transpose(int32_t shape[], intptr_t stride[], int rank) { + for (int i = 0; i < --rank; ++i) { + c_swap(int32_t, shape + i, shape + rank); + c_swap(intptr_t, stride + i, stride + rank); + } } -STC_INLINE intptr_t _cspan_idx4(const int32_t shape[4], const cspan_idx4 stri, int32_t x, int32_t y, - int32_t z, int32_t w) { - c_ASSERT(c_LTu(x, shape[0]) && c_LTu(y, shape[1]) && c_LTu(z, shape[2]) && c_LTu(w, shape[3])); - return (intptr_t)stri.d[3]*(stri.d[2]*(stri.d[1]*x + y) + z) + w; + +STC_INLINE intptr_t _cspan_index(int rank, const int32_t shape[], const intptr_t stride[], const int32_t a[]) { + intptr_t off = 0; + while (rank--) { + c_assert(c_less_unsigned(a[rank], shape[rank])); + off += stride[rank]*a[rank]; + } + return off; } -STC_API intptr_t _cspan_idxN(int rank, const int32_t shape[], const int32_t stri[], const int32_t a[]); -STC_API intptr_t _cspan_next2(int rank, int32_t pos[], const int32_t shape[], const int32_t stride[]); -#define _cspan_next1(r, pos, d, s) (++pos[0], 1) +#define _cspan_next1(pos, shape, stride, rank, done) (*done = ++pos[0]==shape[0], stride[0]) +STC_API intptr_t + _cspan_next2(int32_t pos[], const int32_t shape[], const intptr_t stride[], int rank, int* done); #define _cspan_next3 _cspan_next2 #define _cspan_next4 _cspan_next2 #define _cspan_next5 _cspan_next2 #define _cspan_next6 _cspan_next2 +#define _cspan_next7 _cspan_next2 +#define _cspan_next8 _cspan_next2 + +STC_API intptr_t _cspan_slice(int32_t oshape[], intptr_t ostride[], int* orank, + const int32_t shape[], const intptr_t stride[], + int rank, const int32_t a[][3]); + +STC_API intptr_t* _cspan_shape2stride(cspan_layout layout, intptr_t shape[], int rank); +#endif // STC_CSPAN_H_INCLUDED -STC_API intptr_t _cspan_slice(int32_t odim[], int32_t ostri[], int* orank, - const int32_t shape[], const int32_t stri[], - int rank, const int32_t a[][2]); +/* --------------------- IMPLEMENTATION --------------------- */ +#if defined(i_implement) || defined(i_static) -/* -------------------------- IMPLEMENTATION ------------------------- */ -#if defined(i_implement) +STC_DEF intptr_t _cspan_next2(int32_t pos[], const int32_t shape[], const intptr_t stride[], int r, int* done) { + intptr_t off = stride[--r]; + ++pos[r]; -STC_DEF intptr_t _cspan_idxN(int rank, const int32_t shape[], const int32_t stri[], const int32_t a[]) { - intptr_t off = a[0]; - c_ASSERT(c_LTu(a[0], shape[0])); - for (int i = 1; i < rank; ++i) { - off *= stri[i]; - off += a[i]; - c_ASSERT(c_LTu(a[i], shape[i])); + for (; r && pos[r] == shape[r]; --r) { + pos[r] = 0; ++pos[r - 1]; + off += stride[r - 1] - stride[r]*shape[r]; } + *done = pos[r] == shape[r]; return off; } -STC_DEF intptr_t _cspan_next2(int rank, int32_t pos[], const int32_t shape[], const int32_t stride[]) { - intptr_t off = 1, rs = 1; - ++pos[rank - 1]; - while (--rank && pos[rank] == shape[rank]) { - pos[rank] = 0, ++pos[rank - 1]; - const intptr_t ds = rs*shape[rank]; - rs *= stride[rank]; - off += rs - ds; +STC_DEF intptr_t* _cspan_shape2stride(cspan_layout layout, intptr_t stride[], int rank) { + int i, inc; + if (layout == c_COLMAJOR) i = 0, inc = 1; + else i = rank - 1, inc = -1; + intptr_t k = 1, s1 = stride[i], s2; + + stride[i] = 1; + while (--rank) { + i += inc; + s2 = stride[i]; + stride[i] = (k *= s1); + s1 = s2; } - return off; + return stride; } -STC_DEF intptr_t _cspan_slice(int32_t odim[], int32_t ostri[], int* orank, - const int32_t shape[], const int32_t stri[], - int rank, const int32_t a[][2]) { +STC_DEF intptr_t _cspan_slice(int32_t oshape[], intptr_t ostride[], int* orank, + const int32_t shape[], const intptr_t stride[], + int rank, const int32_t a[][3]) { intptr_t off = 0; - int i = 0, j = 0; - int32_t t, s = 1; + int i = 0, oi = 0; + int32_t end; + for (; i < rank; ++i) { - off *= stri[i]; - off += a[i][0]; - switch (a[i][1]) { - case 0: s *= stri[i]; c_ASSERT(c_LTu(a[i][0], shape[i])); continue; - case -1: t = shape[i]; break; - default: t = a[i][1]; break; + off += stride[i]*a[i][0]; + switch (a[i][1]) { + case 0: c_assert(c_less_unsigned(a[i][0], shape[i])); continue; + case -1: end = shape[i]; break; + default: end = a[i][1]; + } + oshape[oi] = end - a[i][0]; + ostride[oi] = stride[i]; + c_assert((oshape[oi] > 0) & !c_less_unsigned(shape[i], end)); + if (a[i][2]) { + ostride[oi] *= a[i][2]; + oshape[oi] = (oshape[oi] - 1)/a[i][2] + 1; } - odim[j] = t - a[i][0]; - ostri[j] = s*stri[i]; - c_ASSERT(c_LTu(0, odim[j]) & !c_LTu(shape[i], t)); - s = 1; ++j; + ++oi; } - *orank = j; + *orank = oi; return off; } -#endif + #endif #undef i_opt #undef i_header #undef i_implement #undef i_static -#undef i_extern +#undef i_import |