From 5e38c27f35d8916770a5e1f9a586c7d73e27bad1 Mon Sep 17 00:00:00 2001 From: tylov Date: Fri, 1 Sep 2023 09:45:58 +0200 Subject: cspan: can now span over a intptr_t size array, but each dimension is still limited to int32_t sizes. --- docs/cspan_api.md | 40 +++++++++++++++++++++++----------------- include/stc/cspan.h | 46 +++++++++++++++++++++++----------------------- 2 files changed, 46 insertions(+), 40 deletions(-) diff --git a/docs/cspan_api.md b/docs/cspan_api.md index 0f345a7e..4875e021 100644 --- a/docs/cspan_api.md +++ b/docs/cspan_api.md @@ -1,9 +1,14 @@ # STC [cspan](../include/stc/cspan.h): Multi-dimensional Array View ![Array](pics/array.jpg) -The **cspan** is templated non-owning *single* and *multi-dimensional* view of an array. It has similarities -with Python's numpy array slicing and C++ [std::span](https://en.cppreference.com/w/cpp/container/span) / -[std::mdspan](https://en.cppreference.com/w/cpp/container/mdspan), and others. +The **cspan** types are templated non-owning *single* and *multi-dimensional* views of an array. +It supports both row-major and column-major layout efficiently, in a addition to slicing +capabilities similar to [python's numpy arrays](https://numpy.org/doc/stable/user/basics.indexing.html). +Note that each dimension is currently limited to int32_t sizes and 8 dimensions (can be extended). + +See also C++ +[std::span](https://en.cppreference.com/w/cpp/container/span) / +[std::mdspan](https://en.cppreference.com/w/cpp/container/mdspan) for similar functionality. ## Header file and declaration **cspan** types are defined by the *using_cspan()* macro after the header is included. @@ -29,14 +34,14 @@ by default (define `STC_NDEBUG` or `NDEBUG` to disable). ```c SpanType cspan_init(TYPE SpanType, {v1, v2, ...}); // make a 1-d cspan from values SpanType cspan_from(STCContainer* cnt); // make a 1-d cspan from a cvec, cstack, cpque (heap) -SpanType cspan_from_n(ValueType* ptr, intptr_t n); // make a 1-d cspan from a pointer and length +SpanType cspan_from_n(ValueType* ptr, int32_t n); // make a 1-d cspan from a pointer and length SpanType cspan_from_array(ValueType array[]); // make a 1-d cspan from a C array intptr_t cspan_size(const SpanTypeN* self); // return number of elements intptr_t cspan_rank(const SpanTypeN* self); // dimensions; compile time constant -intptr_t cspan_index(const SpanTypeN* self, intptr_t x, ..); // index of element +intptr_t cspan_index(const SpanTypeN* self, int32_t x, ..); // offset index at i, j, .. -ValueType* cspan_at(const SpanTypeN* self, intptr_t x, ...); // #args must match input span rank +ValueType* cspan_at(const SpanTypeN* self, int32_t x, ...); // num args is compile-time checked ValueType* cspan_front(const SpanTypeN* self); ValueType* cspan_back(const SpanTypeN* self); @@ -45,8 +50,8 @@ SpanTypeN_iter SpanType_end(const SpanTypeN* self); void SpanType_next(SpanTypeN_iter* it); // make a multi-dim cspan -SpanTypeN cspan_md(ValueType* data, d1, d2, ...); // row-major -SpanTypeN cspan_md_layout(cspan_layout layout, ValueType* data, d1, d2, ...); +SpanTypeN cspan_md(ValueType* data, int32_t d1, int32_t d2, ...); // row-major layout +SpanTypeN cspan_md_layout(cspan_layout layout, ValueType* data, int32_t d1, d2, ...); // transpose a md span. Inverses layout and axes only. void cspan_transpose(const SpanTypeN* self); @@ -55,14 +60,14 @@ bool cspan_is_rowmajor(const SpanTypeN* self); bool cspan_is_colmajor(const SpanTypeN* self); // create a subspan of input span rank. Like e.g. cspan_slice(Span3, &ms3, {off,off+count}, {c_ALL}, {c_ALL}); -SpanType cspan_subspan(const SpanType* span, intptr_t offset, intptr_t count); -SpanType2 cspan_subspan2(const SpanType2* span, intptr_t offset, intptr_t count); -SpanType3 cspan_subspan3(const SpanType3* span, intptr_t offset, intptr_t count); +SpanType cspan_subspan(const SpanType* span, int32_t offset, int32_t count); +SpanType2 cspan_subspan2(const SpanType2* span, int32_t offset, int32_t count); +SpanType3 cspan_subspan3(const SpanType3* span, int32_t offset, int32_t count); // create a sub md span of lower rank. Like e.g. cspan_slice(Span2, &ms4, {x}, {y}, {c_ALL}, {c_ALL}); -OutSpan cspan_submd2(const SpanType2* parent, intptr_t x); // return a 1d subspan from a 2d span. -OutSpanN cspan_submd3(const SpanType3* parent, intptr_t x, ...); // return a 1d or 2d subspan from a 3d span. -OutSpanN cspan_submd4(const SpanType4* parent, intptr_t x, ...); // number of args decides rank of output span. +OutSpan cspan_submd2(const SpanType2* parent, int32_t x); // return a 1d subspan from a 2d span. +OutSpanN cspan_submd3(const SpanType3* parent, int32_t x, ...); // return a 1d or 2d subspan from a 3d span. +OutSpanN cspan_submd4(const SpanType4* parent, int32_t x, ...); // number of args decides rank of output span. // general slicing of an md span. // {i}: reduce rank. {i,c_END}: slice to end. {c_ALL}: use full extent. @@ -71,11 +76,12 @@ OutSpanN cspan_slice(TYPE OutSpanN, const SpanTypeM* parent, {x0,x1}, {y0 ## Types | Type name | Type definition / usage | Used to represent... | |:------------------|:----------------------------------------------------|:---------------------| -| SpanTypeN | `struct { ValueType *data; uint32_t shape[N]; .. }` | SpanType with rank N | -| SpanTypeN`_value` | `ValueType` | The ValueType | +| SpanTypeN_value | `ValueType` | The ValueType | +| SpanTypeN | `struct { ValueType *data; int32_t shape[N]; .. }` | SpanType with rank N | +| `cspan_tupleN` | `struct { intptr_t d[N]; }` | Strides for each rank | +| `cspan_layout` | `enum { c_ROWMAJOR, c_COLMAJOR }` | Multi-dim layout | | `c_ALL` | `cspan_slice(&md, {1,3}, {c_ALL})` | Full extent | | `c_END` | `cspan_slice(&md, {1,c_END}, {2,c_END})` | End of extent | -| `cspan_layout` | `enum { c_ROWMAJOR, c_COLMAJOR }` | Multi-dim layout | ## Example 1 diff --git a/include/stc/cspan.h b/include/stc/cspan.h index 86aefdc0..e058c0e8 100644 --- a/include/stc/cspan.h +++ b/include/stc/cspan.h @@ -81,7 +81,7 @@ int demo2() { \ typedef struct { Self##_value *ref; int32_t pos[RANK]; const Self *_s; } Self##_iter; \ \ - STC_INLINE Self Self##_slice_(Self##_value* d, const int32_t shape[], const int32_t stri[], \ + STC_INLINE Self Self##_slice_(Self##_value* d, const int32_t shape[], const intptr_t stri[], \ const int rank, const int32_t a[][2]) { \ Self s; int outrank; \ s.data = d + _cspan_slice(s.shape, s.stride.d, &outrank, shape, stri, rank, a); \ @@ -106,7 +106,7 @@ int demo2() { #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) -#define using_cspan_tuple(N) typedef struct { int32_t d[N]; } cspan_tuple##N +#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); @@ -139,7 +139,7 @@ typedef enum {c_ROWMAJOR, c_COLMAJOR} cspan_layout; #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, (int32_t[]){__VA_ARGS__}) + \ + (_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_subspanX: (X <= 3) optimized. Similar to cspan_slice(Span3, &ms3, {off,off+count}, {c_ALL}, {c_ALL}); @@ -172,7 +172,7 @@ typedef enum {c_ROWMAJOR, c_COLMAJOR} cspan_layout; #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, ((int32_t[]){__VA_ARGS__}), c_NUMARGS(__VA_ARGS__))} + .stride=*(c_PASTE(cspan_tuple,c_NUMARGS(__VA_ARGS__))*)_cspan_shape2stride(layout, ((intptr_t[]){__VA_ARGS__}), c_NUMARGS(__VA_ARGS__))} #define cspan_transpose(self) \ _cspan_transpose((self)->shape, (self)->stride.d, cspan_rank(self)) @@ -191,25 +191,25 @@ STC_INLINE intptr_t _cspan_size(const int32_t shape[], int rank) { return sz; } -STC_INLINE void _cspan_transpose(int32_t shape[], int32_t stride[], int rank) { +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(int32_t, stride + i, stride + rank); + c_swap(intptr_t, stride + i, stride + rank); } } -STC_INLINE intptr_t _cspan_index(int rank, const int32_t shape[], const int32_t stride[], const int32_t a[]) { +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_LTu(a[rank], shape[rank])); - off += (intptr_t)stride[rank]*a[rank]; + off += stride[rank]*a[rank]; } return off; } #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 int32_t stride[], int rank, int* done); + _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 @@ -217,53 +217,53 @@ STC_API intptr_t #define _cspan_next7 _cspan_next2 #define _cspan_next8 _cspan_next2 -STC_API intptr_t _cspan_slice(int32_t oshape[], int32_t ostride[], int* orank, - const int32_t shape[], const int32_t stride[], +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[][2]); -STC_API int32_t* _cspan_shape2stride(cspan_layout layout, int32_t shape[], int rank); +STC_API intptr_t* _cspan_shape2stride(cspan_layout layout, intptr_t shape[], int rank); #endif // STC_CSPAN_H_INCLUDED /* --------------------- IMPLEMENTATION --------------------- */ #if defined(i_implement) || defined(i_static) -STC_DEF intptr_t _cspan_next2(int32_t pos[], const int32_t shape[], const int32_t stride[], int r, int* done) { +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]; for (; r && pos[r] == shape[r]; --r) { pos[r] = 0; ++pos[r - 1]; - off += stride[r - 1] - (intptr_t)stride[r]*shape[r]; + off += stride[r - 1] - stride[r]*shape[r]; } *done = pos[r] == shape[r]; return off; } -STC_DEF int32_t* _cspan_shape2stride(cspan_layout layout, int32_t shape[], int rank) { +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; - int32_t k = 1, s1 = shape[i], s2; + intptr_t k = 1, s1 = stride[i], s2; - shape[i] = 1; + stride[i] = 1; while (--rank) { i += inc; - s2 = shape[i]; - shape[i] = (k *= s1); + s2 = stride[i]; + stride[i] = (k *= s1); s1 = s2; } - return shape; + return stride; } -STC_DEF intptr_t _cspan_slice(int32_t oshape[], int32_t ostride[], int* orank, - const int32_t shape[], const int32_t stride[], +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[][2]) { intptr_t off = 0; int i = 0, oi = 0; int32_t end; for (; i < rank; ++i) { - off += (intptr_t)stride[i]*a[i][0]; + off += stride[i]*a[i][0]; switch (a[i][1]) { case 0: c_assert(c_LTu(a[i][0], shape[i])); continue; case -1: end = shape[i]; break; -- cgit v1.2.3