Merge branch 'stclib:master' into modifiedHEADmodified

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